ML——决策树

       决策树是基于树结构来进行决策的，根节点包含样本全集，其每个内部节点对应于一个属性测试，每个分支代表这个特征属性经测试后的输出，叶节点对应于决策结果。决策树进行决策的过程就是从根节点开始，测试待分类项目中相应的特征属性，并按其值选择输出分支，直到到达叶节点得出决策结果。

熵

       熵是随机变量的不确定性度量，熵越大，随机变量越混乱，不确定性越大，定义如下：

                                        

其中为第k类样本所占的比例。

       决策树的基本思想就是以信息熵为度量构造一棵熵值下降最快的树，到叶节点处熵值为零，此时每个叶节点中的实例都属于同一类。因此构造决策树可以选择信息熵下降最快的分支作为分裂的分支，判断信息熵下降情况的有三种算法：

ID3算法

信息增益：表示得知属性a的信息而使得数据集D分类的不确定性减少的程度。假定离散属性a有V个可能的取值，其中第v个分支节点包含了数据集D中所有属性a上取值为的样本，代表数据集所有样本的个数，代表第k类数据的个数 ，则属性a对样本的信息增益为：

ID3算法就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂，递归的构建决策树。具体算法如下：

ID3的不足：

1）ID3算法偏向于对多值属性（eg.ID值）进行分裂，这样虽然能使划分更纯净，但这种划分对分类而言毫无意义；

2）ID3没有考虑连续特征，限制了其用途；

3）ID3算法对缺失值的情况没有做考虑；

4）ID3算法只有树的生成，生成的树容易产生过拟合。

C4.5算法

针对多值属性偏向性上的改进：

C4.5算法与ID3算法类似，但对ID3算法进行了改造。首先针对ID3算法采用信息增益进行属性选择易造成其偏向多值属性分裂的特点，C4.5算法提出了用信息增益率来选择最优划分属性，定义如下：

特征数越多的特征对应的信息熵越大，作为分母可以校正信息熵易偏向于取值较多的特征的问题。

针对连续值的处理：

C4.5算法采用二分法对连续属性进行处理：给定样本集D和连续属性a，假定a在D上出现了n个不同取值，并从小到大排序为，则C4.5取相邻两样本值的中位数作为划分点，划分点集合为：   

                      

基于划分点t可将D划分为属性值小于t的样本集和属性值大于t的样本集，最后计算基于不同划分点的信息增益，取使信息增益最大的划分点进行划分。

针对缺失值的处理：

C4.5算法解决了两方面的缺失值问题：1）在属性值缺失时进行划分属性选择；2）给定划分属性，对样本在该属性上的值缺失时的情况进行划分。

对问题1），C4.5首先对各样例设置一个权重，将有属性值缺失的数据集D划分为了两部分，在属性a上无缺失值的子集D1和在属性a上有缺失值的子集D2，然后计算D1上对应属性a的加权后的信息增益率，最后乘上无缺失值样本所占的比例。

对问题2），C4.5将缺失属性的样本同时划入所有的分支，不过将该样本的权重按各个分支的样本数量比例来分配。

针对过拟合的处理:

引入正则化系数进行初步的剪枝。

C4.5的不足：

C4.5剪枝方法还可以进一步优化，由于使用了熵模型，计算复杂度较高。C4.5生成的是多叉树，运算效率不如二叉树，且该算法只能用于分类，对于回归任务束手无策。

CART决策树

CART是Classification and Regression Tree的简称，即它既能完成分类任务又能实现回归任务。

CART分类树对连续值的处理的基本思想类似于C4.5，区别在于选择划分点时CART分类树使用的是基尼系数，选择划分后基尼指数最小的属性作为最优划分属性。对离散值则是不停的二分离散特征，找到基尼指数最小的组合并建立二叉树结点。

CART回归树与分类树的建立算法大体上类似，区别在于：

1）样本输出不同。分类树的输出值是离散的，而回归树的输出值是连续的；

2）度量优化目标不同。分类树使用基尼指数度量划分点的好坏情况，而回归树是用均方误差最小准则求解每个单元上的最优值；

3）决策树建立后做预测的方式不同。分类树采用叶节点里概率最大的类别作为当前结点的预测类别，回归树是用最终叶子的均值或者中位数来预测输出结果。

剪枝

剪枝是为了避免决策树模型发生过拟合，常用的剪枝方法有两种：预剪枝和后剪枝。

预剪枝：在划分前，计算不进行划分时单节点决策树的分类精度，当划分结点后决策树模型分类精度提高则继续划分，否则不对该结点进行划分并将其化为叶结点。

后剪枝：先从训练集生成一棵完整的决策树，自底向上对非叶结点进行考察，若剪掉对应的子树并替换为叶结点能得到分类精度的提升，则实行剪枝。

CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

也就是说，CART树的剪枝算法可以概括为两步，第一步是从原始决策树生成各种剪枝效果的决策树，第二部是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。

后剪枝通常比预剪枝保留了更多的分支，欠拟合风险小，泛化性能更优，但训练时间要更长。

参考：

周志华《机器学习》

李航《统计学习方法》

http://blog.csdn.net/qq_30091945