Decision tree, a common machine learning method, is somewhat like a flowchart. A sample is divided into a set according to the value it takes on some feature, and this is done recursively

Basic algorithm

Input: training set $D=\\{(\mathbf{x_1},y_1),(\mathbf{x_2},y_2),...,(\mathbf{x_m},y_m)\\}$; attribute set $A=\\{a_1,a_2,...,a_d\\}$

Output: a decision tree with node as the root node

Simple process:

Using some splitting criterion, the optimal feature is selected to split the samples, and this is done recursively, finally yielding the branch nodes of the decision tree

What matters is finding the currently optimal splitting attribute so that the samples contained in the branch nodes of the decision tree belong to the same class as much as possible, that is, the purer the node the better

Basic routine

Information entropy and information gain

Suppose the proportion of samples of the k-th class in the current sample set D is $p_k \ (k=1,2,3,...,\vert y\vert)$, then the information entropy of D is defined as:

$$Ent(D) = -\sum_{k=1}^{\vert y\vert} p_k\log_{2}p_k$$

where by convention, if $p=0$ then $p\log_{2}p = 0$; we have $0 \le Ent(D) \le \log_{2}\vert y\vert$, and the smaller the value of $Ent(D)$, the lower the purity of D

If attribute a has V possible values $\\{a^1,a^2,...,a^V\\}$, splitting the sample set D by a produces V branch nodes, where the v-th branch node contains all samples in D whose value on attribute a is $a^v$, denoted $D^v$; then the information gain obtained by splitting the sample set with attribute a is:

$$Gain(D,a) = Ent(D)-\sum_{v=1}^V \frac{\vert D^v\vert}{\vert D\vert} Ent(D^v)$$

Generally speaking, the larger the information gain, the greater the purity improvement obtained by splitting with attribute a, so we can use information gain as the splitting criterion; this is the ID3 decision tree learning algorithm

Gain ratio

Above we used information gain as our splitting criterion, but information gain prefers attributes with more categories. If we had a feature column of id, then information gain would preferentially choose the id feature for splitting, which is not our purpose. For this reason, we consider adding a regularization term proportional to the number of categories to the information gain, which gives the gain ratio (also called information gain ratio):

$$ \begin{aligned} Gain\_raito(D,a) = \frac{Gain(D,a)}{IV(a)} \\ IV(a) = -\sum_{v=1}^V \frac{\vert D^v\vert}{\vert D\vert} \log_{2}\frac{\vert D^v\vert}{\vert D\vert} \end{aligned} $$

The gain ratio criterion prefers attributes with fewer values, so the C4.5 decision tree algorithm adds a heuristic design on top of the gain ratio: first find the attributes among the candidate splitting attributes whose information gain is above average, and then choose the one with the highest gain ratio among them

Gini index

Information entropy is a measure of the uncertainty of information, and in fact also a measure of the purity of information; the Gini index is also a measure in this respect, computed as follows:

$$ \begin{aligned} Gini(D) & = \sum_{k=1}^{\vert y\vert} \sum_{k‘ \neq k} p_kp_{k’} \\ & = \sum_{k=1}^{\vert y\vert} p_k(1-p_k) \\ & = 1-\sum_{k=1}^{\vert y\vert} {p_k}^2 \end{aligned} $$

where $p_k$ denotes the probability that a sample belongs to the k-th class; Gini(D) reflects the probability that two samples drawn at random from dataset D have inconsistent class labels, so the smaller Gini(D) is, the higher the purity of dataset D

For attribute a, the Gini index is the weighted sum of the Gini indices of the values of attribute a, that is:

$$Gini\_index(D,a) = \sum_{v=1}^V \frac{\vert D^v\vert}{\vert D\vert} Gini(D^v)$$

So among the candidate attribute set A, we should choose the attribute that minimizes the Gini index after splitting as the optimal splitting attribute:

$$a_* = argmin_{a \in A} Gini\_index(D,a)$$

Splitting based on the Gini index is the CART decision tree algorithm

Optimization

For the overfitting of a decision tree, there are mainly two methods: pre-pruning and post-pruning

Pre-pruning

Pre-pruning means that during the construction of the decision tree, each node is evaluated before and after splitting; if splitting the current node cannot improve the generalization performance of the decision tree, splitting stops and the current node becomes a leaf node

Post-pruning

Post-pruning means that after the decision tree has been fully constructed, the non-leaf nodes are examined bottom-up; if replacing the subtree corresponding to a node with a leaf node improves the generalization performance, the subtree is replaced by a leaf node

Comparison of pre- and post-pruning

Item	Pre-pruning	Post-pruning
Training time cost	Small	Large
Testing time cost	Small	Small
Overfitting risk	Small	Small
Underfitting risk	Large	Small

In terms of generalization performance: post-pruning is better than pre-pruning

Use in Scikit-learn

See the official site for the concrete API parameters:

sklearn.tree.DecisionTreeClassifier

Reference

Zhou Zhihua’s Watermelon Book and Li Hang’s Statistical Learning Methods