Suppose we want to know whether Joe will play football today. We have a dataset containing information about weather such as outlook, wind, and humidity and the decision he made (to play or not to play). We take this training data set and create a decision tree taking the appropriate split attributes and split points to get as pure subsets as possible (i.e. the leafs of the tree being subsets with, ideally, either all 'YES-Joe played', or all 'NO-Joe didn't play').

This method is obviously not certain, because it doesn't mean if the subset is pure (in case of, let's say, sunny weather, low wind and normal humidity) it would be pure if we had more data. He might just as well decide not to play in such conditions. But all this method does is it assumes his decisions are not completely random but are motivated by this set of weather conditions. Can we actually call decision tree learning a heuristic method? It's not formal and doesn't guarantee desired results, so I'm guessing we could. I'm writing this to make sure I understand what's going on here, please correct me if I'm wrong.

Now, the proper question regarding the Wikipedia article about decision tree learning. About gini impurity, it says:

Gini impurity can be computed by summing the probability of each item being chosen times the probability of a mistake in categorizing that item. It reaches its minimum (zero) when all cases in the node fall into a single target category.

I absolutely agree with the second sentence. It's the probability that two randomly selected items don't belong to the same class, which is really basic math:

$$1-\sum_{i=1}^{m} f_i^{2}$$ where $f_i$ is the fraction of items labeled with value $i$ in the set.

However, I'm not sure about validity of the first sentence. How is this:

$$\sum_{i=1}^{m} f_i(1-f_i)$$

the probability of each item being chosen times the probability of a mistake in categorizing that item? $f_i$ is just the probability that the randomly selected item from the training data set (right?) belongs to class $i$. $1-i$ is the probability the randomly selected item doesn't belong to class $i$.

Obviously we want to categorize new data not contained in the training dataset. If $0.9$ of items in the subset of the training set belong to the class $1$, and $0.1$ of items belong to class $2$, then we have $0.9$ chance the new example will be labelled correctly. We multiply by the probability this item should be classified to a different class (if it's zero, then we are certain it belongs to the right class, assuming the training data set tells us something). But it's not the only way we could have defined gini impurity, right? I could say, well, let's calculate it by raising $f$ to third, or fourth power: $$1-\sum_{i=1}^{m} f_i^{3}$$

would it still be a reasonable measure of impurity? I guess so.

  • $\begingroup$ Essentially a duplicate of Gini index - formal or heuristic? by the same author. Voting to close. $\endgroup$ – Anony-Mousse -Reinstate Monica Jun 7 '15 at 21:33
  • 1
    $\begingroup$ The other is the weaker duplicate. If someone asks two similar or overlapping questions, the weaker should be closed, not both of them. If they both overlap a stronger existing question, that's grounds for closure. $\endgroup$ – Nick Cox Jun 8 '15 at 8:49

It is a good measure if you can find a probabilistic model that gives a reason to use this formula.

So what is your reason to use the third power?

You can easily find a reason to use the square, i.e. a statistical process where this probability arises.

  • $\begingroup$ If you're asking me for a reason to use third power, then I can ask the same question - why do we square it? Is squaring somehow better than 3rd or 4th power? I guess not. $\endgroup$ – user4205580 Jun 7 '15 at 21:20
  • $\begingroup$ Well, you pretty much gave an explanation for the 2nd power above. You didn't fully work it out, but you are on the right track. It's really easy to find a model where the squared probability arises. But I don't see a convincing model where the probability of being correct would yield third powers. The square wasn't chosen for fun, it was chosen with a reason. If you want to use the third or fourth power, what would be the reason to do so (beyond "I can write the code to do so".) $\endgroup$ – Anony-Mousse -Reinstate Monica Jun 7 '15 at 21:32

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.