决策树模型

简介

决策树算法在机器学习中算是很经典的一个算法系列了。它既可以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林。决策树的学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。决策树算法：ID3（利用信息增益对特征做选择）,C4.5（利用信息增益率对特征做选择）,CART（CART生成与CART剪枝）

ID3算法

ID3算法的特征选择与信息增益

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树的学习效率。特征选择是决定哪个特征来划分特征空间。

熵是度量了事物的不确定性，越不确定的事物熵就越高。越确定的事物概率也就越高，所以熵是和概率成反比，又要变成加法的形式，所以就在$p_(x)$p(​x)前加log并取负，就变成了信息量，再对信息量关于$p_(x)$p(​x)求期望,即为熵的表达式（我的理解是熵是各个权重信息量的和，权重即为他的概率表示在整体中的比例）。
表达式如下：$H(X) = -\sum\limits_{i=1}^{n}p_i logp_i$H(X)=−i=1∑n​pi​logpi​
熵越大，随机变量的不确定性因素就越大。$0<=H_(p)<log_(p)$0<=H(​p)<log(​p)

一个变量X的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：$H(X,Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i,y_i)$H(X,Y)=−i=1∑n​p(xi​,yi​)logp(xi​,yi​)

条件熵$H_(Y|X)$H(​Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性。表达式为：$H(X|Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(y_i|x_i) = \sum\limits_{i=1}^{n}p(y_i)H(Y|X=x_i)$H(X∣Y)=−i=1∑n​p(xi​,yi​)logp(yi​∣xi​)=i=1∑n​p(yi​)H(Y∣X=xi​)


我们刚才提到H(X)度量了X的不确定性，条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性，那么H(X)-H(X|Y)呢？从上面的描述大家可以看出，它度量了X在知道Y以后不确定性减少程度，这个度量我们在信息论中称为互信息，记为I(X,Y)。在决策树ID3算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。(比如在某棵根节点的时候熵比较小，因为有分类，但是到了只有单类的叶节点的时候，这时事物是确定的，只有一个分类所以熵为0，他们之间的差就是信息增益)。
用下面这个图很容易明白他们的关系。左边的椭圆代表H(X),右边的椭圆代表H(Y),中间重合的部分就是我们的互信息或者信息增益I(X,Y), 左边的椭圆去掉重合部分就是H(X|Y),右边的椭圆去掉重合部分就是H(Y|X)。两个椭圆的并就是H(X,Y)。

信息增益表示得知特征X的信息而使得类Y得信息不确定性减少的程度。
$g_(D,A)=H_(D)-H(D|A)$g(​D,A)=H(​D)−H(D∣A)

ID3决策树的生成

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法：从根节点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上的方法构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一棵决策树。

ID3决策树算法不足

   a)ID3没有考虑连续特征

   b)ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。

   c) ID3算法对于缺失值的情况没有做考虑

   d) 没有考虑过拟合的问题

决策树C4.5算法

我们讲到ID3算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。

对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为a1,a2,…,am,则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示为：$T_(i)=\frac{a_(i)+a_(i+1)} 2$T(​i)=2a(​i)+a(​i+1)​ 。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为$a_(t)$a(​t),则小于$a_(t)$a(​t)的值为类别1，大于$a_(t)$a(​t)的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

对于第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比的变量$I_R(X,Y)$IR​(X,Y)，它是信息增益和特征熵的比值。表达式如下：$I_R(D,A) = \frac{I(A,D)}{H_A(D)}$IR​(D,A)=HA​(D)I(A,D)​
其中D为样本特征输出的集合，A为样本特征，对于特征熵$H_A(D) = -\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$HA​(D)=−i=1∑n​∣D∣∣Di​∣​log2​∣D∣∣Di​∣​
其中n为特征A的类别数， Di为特征A的第i个取值对应的样本个数。|D|为样本个数。

C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间。

   1)由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。后面在下篇讲CART树的时候我们会专门讲决策树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。

   2)C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。

   3)C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。

   4)C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。

   
   
   
参考资料：
[1] 刘建平决策树原理（上）：https://www.cnblogs.com/pinard/p/6050306.html
[2] 统计学习方法