2
$\begingroup$

I implemented decision tree according by Russell and Norvig AIMA (in the 3rd edition, p.704).

Assumption

The given formula for calculating entropy does not work for the cases when you have all positives examples, or all negative ones.

For binary outcomes:

$$B(q) = -(q * lg_2(q)+(1-q) * lg_2(1-q))$$

$$q=\frac{p}{p+n}$$

p denotes number of positives, n negatives

So I made a correction, that in such cases nothing is computed, and simply zero (total order) is returned.

Exact fit problem

Let's say you have info about population in USA, and you would like to filter out all people living in Boston. However if you have in your attributes social number, you could assign "Boston" (or "not Boston") with pin-point accuracy.

So when DT computes gain per each attribute, when it comes to social number, all of the sudden gain is maximum, because each attribute value (particular social number) gives immediate outcome about location. Let's take a look at the equation (I rewrite equation for remainder, maximum gain = minimum remainder):

$$ Remainder(A) = \sum_{k=1}^d \frac{p_k+n_k}{p+n}B(\frac{p_k}{p_k+n_k}) $$

B denotes entropy, k indicates given class (value of attribute)

So, having n people DT divided entire population into n subsets, each of 1 person. It was possible because entropy of such subset is zero, product is thus also zero, and the sum in effect is zero.

I will have n edges from root node (an overkill and overfit at the same time), yet for DT it is optimal.

Question

How to prevent such effect? AIMA touches this problem too lightly for me (p.707).

My guess

Every multi-value attribute convert into binary-value set of attributes. For example for colors -- convert:

color = { red, orange, blue }

into

is_red = { true, false }
is_orange = { true, false }
is_blue = { true, false }

This way I could avoid zero-entropy problem, and if I finally get to such situation it would be for good reason. Second, I could be sure about number of edges, so implicitly this factor would be embedded into implementation (in AIMA this is out of control, see the equation above, number of edges -- k -- is not used as a factor).

Another approach would be adding k as an entropy factor of edges. However I have no clue how to do it reliably.

$\endgroup$
  • $\begingroup$ What's the problem? You have a variable (SSN) that makes a perfect fit of Boston-notBoston possible. The measure reflects that. $\endgroup$ – Peter Flom - Reinstate Monica Apr 2 '12 at 10:26
  • $\begingroup$ @Peter Flom, keeping the example -- rewind one year forward, and you will have thousands more people. You run DT on them and all of the sudden they are not classified as Boston (or not, depending how you define "else" edge). Such DT is useless -- not only it has N edges (where N is the size of the training data set), but also overfits (it works only on training data and nothing else). So it is as problem ;-). Btw. it is not only me, who sees the problem, as I said, in AIMA (for example) it is mentioned too, just without solid discussion about solving it. $\endgroup$ – greenoldman Apr 2 '12 at 12:22
  • $\begingroup$ Ah ha! I had misunderstood. I thought the SSN somehow told the location of birth. In this case, why include SSN in the variables available for the tree? Is it useful? $\endgroup$ – Peter Flom - Reinstate Monica Apr 2 '12 at 21:46
  • $\begingroup$ @Peter Flom, SSN tells the place in sense that if you gather all data from all people it will tell you, but after another birth, you don't know anything about SSN->place. Well, this is just an example to easier understand the problem -- however in practice I indeed have similiar trait, and I was wishing DT would take into account number of edges. I didn't anticipate the effect of zero entropy in outcome set. $\endgroup$ – greenoldman Apr 3 '12 at 11:59
1
$\begingroup$

Sounds like a standard overfitting problem - your model is too flexible, so it ends up fitting the training data exactly in a way that does not generalize. You can solve it by making the model less flexible. Usually, in decision trees, it is done by limiting the number of edges from each node to 2 and limiting the depth of the tree. You can also enforce that each leaf node should have a minimum of a certain number of samples.

If your features are not binary or ordinal, you will need to create dummy variables as you mentioned in your post (e.g. is_red, is_green etc.).

$\endgroup$

Your Answer

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

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