2
$\begingroup$

I'm currently studying Chapter 7 ("Modeling with Decision Trees") of the book "Programming Collective intelligence".

I find the output of the function mdclassify() p.157 confusing. The function deals with missing data. The explanation provided is:

In the basic decision tree, everything has an implied weight of 1, meaning that the observations count fully for the probability that an item fits into a certain category. If you are following multiple branches instead, you can give each branch a weight equal to the fraction of all the other rows that are on that side.

From what I understand, an instance is then split between branches.

Hence, I simply don't understand how we can obtain:

{'None': 0.125, 'Premium': 2.25, 'Basic': 0.125}

as 0.125+0.125+2.25 does not sum to 1 nor even an integer. How was the new observation split?

The code is here:

https://github.com/arthur-e/Programming-Collective-Intelligence/blob/master/chapter7/treepredict.py

Using the original dataset, I obtain the tree shown here:

screenshot

Can anyone please explain me precisely what the numbers precisely mean and how they were exactly obtained?

PS : The 1st example of the book is wrong as described on their errata page but just explaining the second example (mentioned above) would be nice.

Improve this question
$\endgroup$
3
  • $\begingroup$ What are these numbers? What precisely do you do to obtain them? $\endgroup$
    – Wojciech Walczak
    Apr 25, 2015 at 15:38
  • $\begingroup$ Thanks for your interest. I obtain these numbers by entering : mdclassify(['google','France',None,None],tree). The results are the same as the ones obtained by the book. I simply do not understand them. mdclassify() is a function used to classify observations when there are missing attributes, but using a weighting process (so the observation is split around different branches in a unequal manner). NB : When an observation fulfill a condition, it goes on the right branch. So here in some way the observation is split on the 3 branches of the right side. But what are these figures? $\endgroup$
    – PLL
    Apr 25, 2015 at 17:40
  • $\begingroup$ The second link is dead now. Can you fix it? Or perhaps remove it? $\endgroup$
    – VividD
    May 10, 2017 at 21:16

1 Answer 1

Reset to default
1
$\begingroup$

There are four features:

  • referer,
  • location,
  • FAQ,
  • pages.

In your case, you're trying to classify an instance where FAQ and pages are unknown: mdclassify(['google','France',None,None], tree).

Since the first known attribute is google, in your decision tree you're only interested in the edge that comes out of google node on the right-hand side.

There are five instances: three labeled Premium, one labeled Basic and one labeled None.

Instances with labels Basic and None split on the FAQ attribute. There's two of them, so the weight for both of them is 0.5.

Now, we split on the pages attribute. There are 3 instances with pages value larger than 20, and two with pages value no larger than 20.

Here's the trick: we already know that the weights for two of these were altered from 1 to 0.5 each. So, now we have three instances weighted 1 each, and 2 instances weighted 0.5 each. So the total value is 4.

Now, we can count the weights for pages attribute:

  • pages_larger_than_20 = 3/4
  • pages_not_larger_than_20 = 1/4 # the 1 is: 0.5 + 0.5

All weights are ascribed. Now we can multiply the weights by the "frequencies" of instances (remembering that for Basic and None the "frequency" is now 0.5):

  • Premium: 3 * 3/4 = 2.25 # because there are three Premium instances, each weighting 0.75;
  • Basic: 0.5 * 1/4 = 0.125 # because Basic is now 0.5, and the split on pages_not_larger_than_20 is 1/4
  • None: 0.5 * 1/4 = 0.125 # analogously

That's at least where the numbers come from. I share your doubts about the maximum value of this metric, and whether it should sum to 1, but now that you know where these numbers come from you can think how to normalize them.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Wow ! Thanks ! To check my understanding, I tried to apply the same reasoning to the 3 branches at the left but I don't manage to get appropriate results. If I enter mdclassify(['digg', None, None, None], tree) I'm getting {'Basic': 2.4615384615384617, 'None': 0.8653846153846154}. Can you please explain me how it works ? I thought we would have : 1) Dividing one unit of weight for page>20: None:3 and Basic1 : 0.75 and 0.25 2) Then counting the weight for for FAQ attribute * Yes to FAQ = 4/5 * No to FAQ = 1/5 Thus for None I would expect to get 0.75/5=0.15. Where am I wrong ? $\endgroup$
    – PLL
    Apr 26, 2015 at 9:34
  • $\begingroup$ Try either running the script in debug mode, or add print statements in mdclassify() function and carefully observe what's going on. In short, in this digg-None-None-None case we got: Basic==1, None==3, thus: Basic==1*0.25 and None==3*0.75. Then we go up to attribute "2:yes" and we got: Basic==4, and (Basic==0.25, None==2.25). The Basic==4 probability is: 4/6.5==0.61, and 4*0.615==2.46 after multiplication. The probability of the second leaf is: 2.5/6.5==0.38. So, finally we got: Basic==(4*0.615)+(0.25*0.38)=2.55, and None==2.25*0.38=0.85. I get approx. results like these. $\endgroup$
    – Wojciech Walczak
    Apr 26, 2015 at 13:41
  • $\begingroup$ Ok, it's clear now ! You nailed it ! Many thanks ! $\endgroup$
    – PLL
    Apr 26, 2015 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.