决策树（Decision Tree）

1.关于决策树

通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

女儿：多大年纪了？

母亲：26。

女儿：长的帅不帅？

母亲：挺帅的。

女儿：收入高不？

母亲：不算很高，中等情况。

女儿：是公务员不？

母亲：是，在税务局上班呢。

女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，图1表示了女孩的决策逻辑。

图1

如果你作为一个女生，你会优先考虑哪个条件：长相？收入？还是年龄。在考虑年龄条件时使用25岁为划分点，还是35岁为划分点。有这么多条件，用哪个条件特征先做if，哪个条件特征后做if比较优呢？还有怎么确定用特征中的哪个数值作为划分的标准。这就是决策树机器学习算法的关键了。

2.信息论基础

首先，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：

$H(X) = -\sum\limits_{i=1}^{n}p_i logp_i$

如抛一枚硬币为事件 $T$ ， $P(正) = \frac{1}{2}$ ， $P(正) = \frac{1}{2}$ ， $H(T) = -(\frac{1}{2}log\frac{1}{2} + \frac{1}{2}log\frac{1}{2}) = log2$

掷一枚骰子为事件 $G$ ， $P(1) = P(2) = ... = P(6) = \frac{1}{2}$ ，

$H(G) = -\sum\limits_{1}^{6}\frac{1}{6} log\frac{1}{6} =log6$

$H(G) > H(T)$ ，显然掷骰子的不确定性比投硬币的不确定性要高。

熟悉了单一变量的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：

$H(X,Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i,y_i)$

有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们在知道Y以后X剩下的不确定性。表达式：

$H(X|Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i|y_i) = \sum\limits_{j=1}^{n}p(y_j)H(X|y_j)$

我们刚才提到 $H(X)$ 度量了 $X$ 的不确定性，条件熵 $H(X|Y)$ 度量了我们在知道 $Y$ 以后 $X$ 剩下的不确定性，那么 $H(X)-H(X|Y)$ 呢？它度量了 $X$ 在知道 $Y$ 以后不确定性减少程度，这个度量我们在信息论中称为互信息，记为 $I(X,Y)$ 。

信息熵 $H(X)$ ，联合熵 $H(X,Y)$ ，条件熵 $H(X|Y)$ ，互信息 $I(X,Y)$ 之间的关系由图2所示：

图2

3.决策树ID3算法

在决策树的ID3算法中，互信息 $I(X,Y)$ 被称为信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。

下面我们用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：

设L、F、H和D表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益：

$H(D) = -(0.7log_{2} 0.7 + 0.3log_{2} 0.3) = 0.879$

$H(D|L) = -[0.3(\frac{1}{3} log_{2} \frac{1}{3} + \frac{2}{3} log_{2} \frac{2}{3}) + 0.4(\frac{1}{4} log_{2} \frac{1}{4} + \frac{3}{4} log_{2} \frac{3}{4}) + 0.3(\frac{0}{3} log_{2} \frac{0}{3} + \frac{3}{3} log_{2} \frac{3}{3})] = 0.603$

$I(D,L) = H(D) - H(D|L) = 0.879-0.603 = 0.276$

因此日志密度的信息增益是0.276。用同样方法得到H和F的信息增益分别为0.033和0.553。因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果图3表示：

图3

在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。

但是ID3算法中还存在着一些不足之处：

1.ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。

2.ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为 $\frac{1}{2}$ ，另一个变量为3个值，各为 $\frac{1}{3}$ ，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。（信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大）如河校正这个问题呢？为了解决这些问题我们有了C4.5算法。

4.决策树C4.5算法

对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为 ${a_1,a_2,...,a_m}$ 。则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点 $T_i$ 表示为： $T_i = \frac{a_i+a_{i+1}}{2}$ 。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为 $a_t$ ，取大于 $a_t$ 为类别1，小于 $a_t$ 为类别2。这样我们就做到了连续特征的离散化。

对于第二个问题，信息增益作为标准容易偏向于取值较多的特征。C4.5中提出了信息增益比：

$I_R(D,A) = \frac{I(A,D)}{H(A)}$

即特征 $A$ 的对数据集 $D$ 的信息增益与特征 $A$ 信息熵的比，信息增益比越大的特征和划分点，分类效果越好。某特征中值得种类越多，特征对应的特征熵越大，它作为分母，可以校正信息增益导致的问题。

回到上面的例子： $I(D,L) =0.276，I(D,F) = 0.533，I(D,H) =0.033$

$H(L)= -(0.3log_20.3+0.4log_20.4+0.3log_20.3) = 1.571$

$I_R(D,L) = \frac{I(D,L)}{H(L)} = \frac{0.276}{1.571} = 0.176$

同样可得： $I_R(D,F) = 0.35$ ， $I_R(D,H) = 1$ 。

因为F具有最大的信息增益比，所以第一次分裂选择F为分裂属性，分裂后的结果图3表示。

再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。

5.分类回归树(Classification and Regression Tree，CART）模型

看完上述材料，我们知道在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值种类多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。

在分类问题中，假设有 $K$ 个类别，第 $k$ 个类别的概率为 $p_{k}$ ,则基尼系数为：

$Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$

对于给定的样本 $D$ ，假设有 $K$ 个类别，第 $k$ 个类别的数量为 $C_{k}$ ，则样本的基尼系数为:

$Gini(D) = 1-\sum\limits_{k=1}^{K}(\frac{|C_k|}{|D|})^2$

特别的，对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数为：

$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$

回到上面的例子：

$Gini(D) =2*0.3*(1-0.3) = 0.42$

$Gini(D,L) = 0.3(1-\frac{1}{3} ^2 -\frac{2}{3} ^2 ) + 0.4(1-\frac{1}{4} ^2 - \frac{3}{4} ^2) + 0.3(1-\frac{3}{3} ^2 - \frac{0}{3} ^2)=0.283$

同理得： $Gini(D,F) = 0.55$ ， $Gini(D,H) = 0.4$ 。

因为L具有最小的基尼系数，所以第一次分裂选择L为分裂属性。