Finding the Root

You may have thought we were done with decisions trees. I am done with respect to discussing general approaches and types of problems. You could say that we're moving from a view of the forest, to finding the root for our tree. However, there is a bit more to explore when it comes to the underlying mathematical functions associated with navigating data to construct our trees.

Some time ago I introduced the concept of a cost function and gave a specific example in the Gini coefficient. Gini calculations are useful for a specific type of decision tree algorithm referred to as CART or classification and regression trees. For other algorithms, such as Iterative Dichotomizer 3 (ID3), we need another method.

Iterative Dichotomiser Decisions

Strictly speaking, we're not computing a split cost when using the ID3 algorithm. Whereas CART works with binary decisions, ID3 implements a greedy search to construct a top-down decision tree. Thus, ID3 doesn't split on a decision in the strictest sense.

Rather, the algorithm constructs decisions based on entropy and information gain. More specifically, we need to select what we can construe as a best fitting attribute as we iterate over the set of possible decision trees; top-down or root node first. I think how well a selected attribute represents a classification is at the heart of an ID3-based. This is where entropy and information gain enter the picture.

Entropy and Information Gain

Entropy, or the measure of homogeneity within the data, yields a value of either one or zero. If the data are the same, entropy is zero. Otherwise, we get an entropy metric of one if the data are equally divided. Why are those the only possible values? Remember, we're dealing with decision trees! ID3 creates subsets within a tree structure, based on the entropy metric- zeroes are grouped together as are ones.

In turn, information gain relies on our concept of entropy. As information gain goes up, the decision split reduces entropy. Specifically, information gain uses the entropy measure from each potential decision branch split, starting with the root node and moving outward towards the lowest leaves.

Whew. That's deep...

The simple equation associated with information gain paints a clearer picture:

Gain (T,X) = Entropy +(T) – Entropy(T,X)

Thus, we can imagine that there is an inner, hidden simulation. The simulation factors potential decisions represented by attribute splits, and comparatively evaluated according to the highest information gain measure.

I view this as a type of path finding or even (network) routing protocol. The technical aspects of this analogy may be worth exploring in the near future. Until then, we ought to begin thinking about alternatives to decision trees. Perhaps a good place to visit next is with our neighbors.