Study Decision Tree

ID3¶

Steps to build a decision tree¶

1. 计算当前集合S中数据的熵$H(S)=-\sum_{i=1}^m p_i\log(p_i)$。其中m为feature的数目。
2. 遍历没有被split的feature们，计算按各个feature进行split后的熵增益$IG_{A, S}=H(S) - \sum_{i=1}^{K_A} p_{sub_i}H(sub_i)$。
3. 选择熵增益最大的feature进行split，并生成对应的树节点。对分成的子集合递归调用step 1。

CART¶

CART stands for Classification And Regression Trees.

如何进行split的测试¶

每次split都是二分的，针对不同的数值情况有：

1. 类别的数据，从所有类别中选择所有的可能的划分，除了空集。
2. 数值的数据，把所有值从小到大排序，选择所有$a=\frac{(x_k+x_{k+1})}{2}$来进行划分。
3. 顺序的数据，选择$x_{min} < a < x_{max}$来进行划分。

Gini impurity （用于分类）¶

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

Gini impurity的差值被拿来进行split，使用的思路和ID3中的IG类似。

Squared error （用于regression）¶

$$\sum(y-E(y))^2$$

求$p_l{\sum(y_l-E(y_l))^2}+p_r{\sum(y_r-E(y_r))^2}$的最小划分。

Advantages of Decision Tree¶

• 容易理解和实现
• 可以处理连续和离散的数据
• 可以处理多分类问题

Disadvantages of Decision Tree¶

• 容易overfitting
• 有可能不稳定，小的数据变化会造成完全不同的树
• 数据分布不是很均匀的话，容易导致high bias。