2
$\begingroup$

Since I don't have CS background I will most probably ask this question the wrong way. I need to choose a node from a tree, where I include all beneath this node leafs in a validation.

I have a data set from a big web directory that categorized websites. I already wrangled the data around so the root of every category is the language of the website. The Categories for each website look like this:

English/Computer/Hardware/CPUs/Intel
English/Computer/Hardware
English/Computer/Hardware/Motherboards
English/Computer/Hardware/Networking/
                ...
German/Computer/Hardware
German/Computer/Software
German/Computer
                ...

The trees I constructed can have both leafs and branches kinda like a directory structure with files and folders. I represented every individual languages as such a tree, where each node knows how many leaves it self has and all the branches beneath it. They look like that:

                                   English
                                     300
                                      |
                          A --------------------- B
                         120                     180
                          |                       |
                          E                C ----------- D
                         80               10            160  

Now theses Category trees can go deep up, to up to 20 nodes and many (end)nodes only have very few leafs 1-10 in a tree with over a million leafs overall. Additionally the non-english trees have significantly less leafs, nodes, and depth.

As I wrote in the beginning, I want to pick a sub node and all the leafs beneath it to test some models, that look for similarity in websites. The amount of leafs should be representative for the data set but also as specific, category wise, as possible. My first intuition was to pick nodes that hold about 1% of the sum of all leafs in the tree. But I have no idea if this is a) specific enough and b) representative enough. It is just a number that sounds good that I can not backup with anything.

So my question, is there an algorithm that can give me such a number? So that I don't have to just pull it out of a hat?

$\endgroup$
  • 1
    $\begingroup$ This is in no way a question in computer science. It's at best a question in statistics. To formulate it as a statistical question you will need to do a fair amount of modeling, and even then you will need to plug inside some formula your certainty level. Without a model, there isn't any algorithmic question here. $\endgroup$ – Yuval Filmus Mar 21 '17 at 20:19
  • 1
    $\begingroup$ Define "specific enough" and "representative enough". $\endgroup$ – Raphael Mar 21 '17 at 21:06
  • $\begingroup$ Sorry I'm still working on it i will post an awsner to it. $\endgroup$ – Thagor Apr 11 '17 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.