# Decision tree learning

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.

• Essentially a duplicate of Gini index - formal or heuristic? by the same author. Voting to close. – Anony-Mousse -Reinstate Monica Jun 7 '15 at 21:33
• 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. – Nick Cox Jun 8 '15 at 8:49