决策树算法简述：ID3，C4.5，CART

1. 决策

我理解的决策就是根据当前已有的条件，得出一个结果。

如以下这个简单的例子：

ID	Leg	Color	Bite	Type
1	short	yellow	yes	cat
2	long	black	yes	cat
3	long	yellow	yes	cat
4	short	yellow	no	cat
-1	long	yellow	no	dog
-2	short	white	yes	dog
-3	long	white	yes	dog
-4	long	white	no	dog
-5	short	black	no	dog

以上这个也叫做决策表。通过 腿长，颜色，是否咬人 来判断是 猫 还是 狗。

2. 决策树

我们可以将以上的表格转换成一棵树：

决策树

每次决策的时候从根节点出发，根据属性值选择子树，直到叶子节点就是一个决策。

3. ID3算法

构建树的时候，把哪个属性放在根节点，哪个属性放在第二层节点，就值得我们思考了。可以预想到，根据不同的顺序，构建出来的决策树的构造可能是不一样的。如果树中的节点越少，那么平均每次决策所需要的判断次数也就越少，算法的效率就越高。

ID3算法就是为了构造出一棵较优的（注意，不一定最优）的树，使得每次决策的平均判断次数更少。

3.1 信息熵

在高中学过，熵表示一个系统的无序程度。比如刚整理好的房间的熵值就比你住过两周不收拾以后的房间的熵值要小。

而 信息熵 是类似的，其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。

假设一个随机变量 $X$ 的取值为 $X=\{x_1, x_2, ...,x_n\}$ ，每一种取到的概率为 $P=\{p_1,p_2,...,p_n\}$ ，那么 $X$ 的熵值为：
$\begin{aligned} E(X) = -\sum\limits_{i=1}^{n}p_i\log_2p_i \end{aligned}$
注意，虽然前面有个负号，但是熵值是正的。

以上面的决策为例， $Type = \{cat, dog\}$ ，其概率分别是 $\{\frac{4}{9}， \frac{5}{9} \}$ ，那么其熵值为：
$\begin{aligned} E(Type) = -(\frac{4}{9} \log_2\frac{4}{9}+\frac{5}{9}\log_2\frac{5}{9}) = 0.9911 \end{aligned}$

3.2 条件熵

还是以上的例子，如果把所有的样本仅按照 Leg 进行分类的话，可以分成两类：

按Leg分类

分别计算熵值，可得：
$\begin{aligned} E(long) &= -(\frac{2}{5} \log_2 \frac{2}{5}+\frac{3}{5}\log_2\frac{3}{5}) = 0.9710 \\ E(short) &= -(\frac{1}{2}\log_2\frac{1}{2}+\frac{1}{2}\log_2\frac{1}{2}) = 1 \end{aligned}$
因此，划分后的熵值为：
$\begin{aligned} E(Type|Leg) &= \frac{5}{9}\cdot E(long)+\frac{4}{9}\cdot E(short) \\&=\frac{5}{9}\cdot 0.9710+\frac{4}{9}\cdot 1 \\&= 0.9839 \end{aligned}$
因此信息增益为：
$\begin{aligned} G(Leg)=E(Type)-E(Type|Leg)=0.0071 \end{aligned}$

3.3 ID3 算法

ID3 算法就是找出信息增益最大的属性，然后将其当成根节点，然后对于由此划分得到的子数据，重复以上的步骤。

同样的方法计算 Color 属性的信息增益：

按Color分类

$\begin{aligned} E(yellow) &= -(\frac{3}{4} \log_2\frac{3}{4}+\frac{1}{4}\log_2\frac{1}{4}) = 0.8113 \\ E(black) &= -(\frac{1}{2} \log_2\frac{1}{2}+\frac{1}{2}\log_2\frac{1}{2}) = 1 \\ E(white) &= -(\frac{0}{3} \log_2\frac{0}{3}+\frac{3}{3}\log_2\frac{3}{3}) = 0 \\ E(Type|Color) &= \frac{4}{9}\cdot E(yellow)+\frac{2}{9}\cdot E(black) + \frac{3}{9}\cdot E(white) = 0.5828 \\ G(Color) &= E(Type)-E(Type|Color) = 0.4083 \end{aligned}$
再算Bite 属性的信息增益：

按Bite分类

$\begin{aligned} E(yes) &= -(\frac{3}{5}\log_2\frac{3}{5}+\frac{2}{5}\log_2\frac{2}{5}) = 0.9710 \\ E(no) &= -(\frac{1}{4} \log_2\frac{1}{4}+\frac{3}{4}\log_2\frac{3}{4}) = 0.8113 \\ E(Type|Bite) &= \frac{5}{9}\cdot E(yes)+\frac{4}{9}\cdot E(no) = 0.9000 \\ G(Bite) &= E(Type)-E(Type|Bite) = 0.0911 \end{aligned}$
很明显，Color 属性以绝对的优势胜出，当选根节点。

于是数据被 Color 分成了三部分，对每一部分数据，去除 Color 属性的影响，按以上的方法递归生成决策树，这里就不赘述了。

但是ID3算法的缺点是很明显的（虽然我自己不觉得明显，但是书上都这么说）：

ID3算法不能处理连续的数据

这个很好理解，假设有一个属性是精确到小数点后三位的体重值，那么可能所有样本的值都不一样，则该属性的信息增益最大。ID3算法就会仅使用该属性，把每个样本都分到单独的一类中。即，反正体重都不一样，那根据体重来判断就完事了~
ID3算法倾向于选择取值较多的属性

信息增益反映的给定一个条件以后不确定性减少的程度，必然是分得越细的数据集确定性更高，也就是条件熵越小，信息增益越大。

4. C4.5算法

为了克服 “ID3算法倾向于选择取值较多的属性” 的缺点，C.45算法使用了信息增益率来代替信息增益。其思想就是，增加一个惩罚，取值越多的属性惩罚越大，以此来平衡其选择。

如果使用C.45的话，上面的公式就变成：
$\begin{aligned} GR(Leg) = \frac{G(Leg)}{E(Leg)} \end{aligned}$
复习一下， $E(Leg)$ 就是将样本按照属性 Leg 划分以后的信息熵。

可以得到：
$\begin{aligned} E(Leg) &= -(\frac{4}{9} \log_2\frac{4}{9}+\frac{5}{9}\log_2\frac{5}{9}) = 0.9911 \\ GR(Leg) &= \frac{G(Leg)}{E(Leg)} = \frac{0.0071}{0.9911} = 0.0072 \end{aligned}$

同样的方法计算 Color 属性的信息增益率：

$\begin{aligned} E(Color) &= -(\frac{4}{9}\log_2\frac{4}{9}+\frac{2}{9}\log_2\frac{2}{9}+\frac{3}{9}\log_2\frac{3}{9}) = 1.5305 \\ GR(Color) &= \frac{G(Color)}{E(Color)} = \frac{0.4083}{1.5305} = 0.2668 \end{aligned}$
再算Bite 属性的信息增益率：
$\begin{aligned} E(Bite) &= -(\frac{5}{9}\log_2\frac{5}{9}+\frac{4}{9}\log_2\frac{4}{9}) = 0.9911 \\ GR(Bite) &= \frac{G(Bite)}{E(Bite)} = \frac{0.0911}{0.9911} = 0.0919 \end{aligned}$
可以看到，虽然还是 Color 属性的信息增益率最高，但是值已经被压缩了，而另外两个属性的值得到了小幅度的上升，各个属性之间的差异更小了。

5. CART 算法

上述两个算法生成的树中，一个节点有几个子节点取决于该属性的取值数量，而CART算法生成的则是二叉树。

Chart算法则使用了一个叫做 Gini系数 的东西，假设一个随机变量 $X$ 的取值为 $X=\{x_1, x_2, ...,x_n\}$ ，每一种取到的概率为 $P=\{p_1,p_2,...,p_n\}$ ，那么 $X$ 的为：
$\begin{aligned} Gi(X)=1-\sum \limits_{i=1}^{n}p_i^2 \end{aligned}$
如果根据属性 $R$ 把数据 $D$ 划分为 $\{D_1,D_2\}$ ，则：
$\begin{aligned} Gi(D, R)=\frac{|D_1|}{|D|}Gi(D_1)+\frac{|D_2|}{|D|}Gi(D_2)=Gi(R) \end{aligned}$
则Gini系数增益为：
$\begin{aligned} \Delta Gi(R)=Gi(D)-Gi(D,R) \end{aligned}$
按照惯例，使用上面的例子计算一下：

首先算出整个数据集的 Gini 系数：
$\begin{aligned} Gi(Type) &= 1 - (\frac{5}{9})^2 - (\frac{4}{9})^2 = 0.4938 \end{aligned}$

对于 Leg 属性：

按Leg分类

$\begin{aligned} Gi(long) &= 1 - (\frac{2}{5})^2 - (\frac{3}{5})^2 = 0.48 \\ Gi(short) & = 1 - (\frac{1}{2})^2 - (\frac{1}{2})^2 = 0.5 \\ Gi(Leg) &= \frac{5}{9} \cdot 0.48+\frac{4}{9} \cdot 0.5 = 0.4889 \\ \Delta Gi(Leg) &= Gi(Type)-Gi(Leg) = 0.005 \end{aligned}$

对于 Color 属性，就比较麻烦了，因为有三个取值，但是CART生成的是二叉树，因此就会有三种情况。

按Color分类

case 1：

$\begin{aligned} Gi(yellow) &= 1 - (\frac{3}{4})^2 - (\frac{1}{4})^2 = 0.375 \\ Gi(black\&white) &= 1 - (\frac{1}{5})^2 - (\frac{4}{5})^2 = 0.320 \\ Gi_1(Color) &= \frac{4}{9} \cdot 0.375 + \frac{5}{9} \cdot 0.320 = 0.3827 \\ \Delta Gi_1(Color) &= Gi(Type)-Gi_1(Color) = 0.1111 \end{aligned}$

case 2：

$\begin{aligned} Gi(black) &= 1 - (\frac{1}{2})^2 - (\frac{1}{2})^2 = 0.5 \\ Gi(yellow\&white) &= 1 - (\frac{3}{7})^2 - (\frac{4}{7})^2 = 0.4898 \\ Gi_2(Color) &= \frac{2}{9} \cdot {0.5} + {\frac{7}{9}} \cdot 0.4898 = 0.4921 \\ \Delta Gi_2(Color) &= Gi(Type)-Gi_2(Color) = 0.0017 \end{aligned}$

case 3：

$\begin{aligned} Gi(white) &= 1 - (\frac{0}{3})^2 - (\frac{3}{3})^2 = 0 \\ Gi(yellow\&black) &= 1 - (\frac{4}{6})^2 - (\frac{2}{6})^2 = 0.4444 \\ Gi_3(Color) &= \frac{3}{9} \cdot 0 +\frac{6}{9} \cdot 0.4444 = 0.1975 \\ \Delta Gi_3(Color) &= Gi(Type)-Gi_3(Color) = 0.2936 \end{aligned}$

对于 Bite 属性：