机器学习之决策树

机器学习之决策树

上一章节，我们了解了什么是逻辑回归，逻辑回归就是将所有的特征变换为概率后，通过大于某一阈值的划分为一类，小于某一阈值的划为另一类，而决策树呢，就是将每一个特征都做分类。下面我们看一下直观的图。

如果遇到一个人是否去相亲的问题，逻辑回归的处理逻辑是这样的：

而决策树的处理逻辑是这样的：

决策树模型其实就是模拟一个人的决策过程。更加接近人的思维方式，可以产生可视化的分类，模型的可解释性非常强，是一个类似于流程图的树形结构，树内部的每一个节点代表着对一个特征的测试，树的分支代表着测试的结果，而树的每一个节点代表着一个类别。

训练过程：通过对训练样本的分析来确定划分属性。

预测过程：将测试样本从根节点放进树模型，沿着属性划分的路径，直到叶子节点处。

决策树的基本流程：

图片来自周志华的西瓜书

显然，决策树的生产就是一个递归的过程，他的中止条件是：

1、当前节点包含的样本全部都是同一类别，不需要再划分；

2、当前属性集为空，或者说当前所有样本的所有属性取值相同，无法划分；

3、当前节点包含的样本集合为空，不能划分；

那么，怎样选择最优的划分属性呢，这才是决策树最关键的地方，好比方说你相亲，按长相这个属性划分，肯定比按吃不吃辣这个属性划分，尽可能的把相亲和不相亲划分开。那么接下来，我们说一说衡量把样本划分得纯不纯的指标。

信息熵：信息熵是度量样本‘纯度’最常用的指标之一。假设当前样本D中第k类样本所占比例为p_k ,那么，D的信息熵定义为：

信息增益：信息增益直接以信息熵为基础，计算当前划分对信息熵的变化。

你会发现基于信息增益，你会发现，他偏好于可取值比较多的属性，但是，比如一个班，按学号来划分信息增益是最大的，但是是没有意义的，所以，信息增益率来了。

信息增益率：

属性a的可取值越多，IV（a）就越大，信息增益率就越少。

基尼指数：

在候选集中选取那个使划分后基尼指数最小的属性进行划分。

模型中的用法：

ID3算法

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

C4.5算法

C4.5算法与ID3算法决策树的生成过程相似，C4.5算法对ID3算法进行了改进。它是用信息增益率（比）来 选择特征。

这里的改进主要是针对样本特征来作。 
（1）基本决策树要求特征A取值为离散值，如果A是连续值，假如A有v个取值，则对特征A的测试可以看成是对v-1个可能条件的测试，其实可以把这个过程看成是离散化的过程，只不过这种离散的值间隙会相对小一点；当然也可以采用其他方法，比如将连续值按段进行划分，然后设置亚变量； 
（2）特征A的每个取值都会产生一个分支，有的时候会导致划分出来的子集样本量过小，统计特征不充分而停止继续分支，这样在强制标记类别的时候也会带来局部的错误。针对这种情况可以采用A的一组取值作为分支条件；或者采用二元决策树，每一个分支代表一个特征取值的情况（只有是否两种取值)。 
（3）某些样本在特征A上值缺失，针对这种空值的情况，可以采用很多方法，比如用其他样本中特征A出现最多的值来填补空缺，比如采用均值、中值等，甚至在某些领域的数据中可以采用样本内部的平滑来补值，当样本量很大的时候也可以丢弃这些有缺失值的样本。 
（4）随着数据集的不断减小，子集的样本量会越来越小，所构造出的决策树就可能出现碎片、重复、复制等总是。这时可以利用样本的原有特征构造新的特征进行建模； 
（5）信息增益法会倾向于选择取值比较多的特征（这是信息熵的定义决定了的），针对这一问题，人们提出了增益比率法（gain ratio），将每个特征取值的概率考虑在内，及gini索引法，χ2χ2条件统计表法和G统计法等。

决策树之——CART算法（classification and regression tree）

既可以做分类，也可以做回归。只能形成二叉树。

分支条件：二分类问题

分支方法：对于连续特征的情况：比较阈值，高于某个阈值就属于某一类，低于某个阈值属于另一类。对于离散特征：抽取子特征，比如颜值这个特征，有帅、丑、中等三个水平，可以先分为帅和不帅的，不帅的里面再分成丑和中等的。

得分函数（y）：对于分类树取得是分类最多的那个结果（也即众数），对于回归树取得是均值。

损失函数：其实这里的损失函数，就是分类的准则，也就是求最优化的准则

对于分类树（目标变量为离散变量）：同一层所有分支假设函数的基尼系数的平均。

对于回归树（目标变量为连续变量）：同一层所有分支假设函数的平方差损失

分裂准则：

对于分类树（目标变量为离散变量）：使用基尼系数作为分裂规则。比较分裂前的gini和分裂后的gini减少多少，减少的越多，则选取该分裂规则

对于回归树（目标变量为连续变量）：使用最小方差作为分裂规则。只能生成二叉树。

CART分类树算法对于连续特征和离散特征处理的改进

        对于CART分类树连续值的处理问题，其思想和C4.5是相同的，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5使用的是信息增益比，则CART分类树使用的是基尼系数。

　    具体的思路如下，比如m个样本的连续特征A有m个，从小到大排列为a1,a2,...,am，则CART算法取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示为：

。对于这m-1个点，分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为,则小于的值为类别1，大于的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与ID3或者C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

　　对于CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。

回忆下ID3或者C4.5，如果某个特征A被选取建立决策树节点，如果它有A1,A2,A3三种类别，我们会在决策树上一下建立一个三叉的节点,这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把A分成{A1}和{A2,A3}{A1}和{A2,A3}, {A2}和{A1,A3}{A2}和{A1,A3}, {A3}和{A1,A2}{A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3}{A2}和{A1,A3},然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的节点。同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。

决策树的行成我们说完后，现在我们来说说万一树生长的太复杂了怎么办呢，那就要进行剪枝，剪枝，就是问了防止模型过拟合。

剪枝分为预剪枝和后剪枝：

预剪枝：边建立决策树边进行剪枝的操作（更实用）

在决策树生成分支的过程，除了要进行基础规则的判断外，还需要利用统计学的方法对即将分支的节点进行判断，比如统计χ2或统计信息增益，如果分支后使得子集的样本统计特性不满足规定的阈值，则停止分支；但是阈值如何选取才合理是比较困难的。

后剪枝：当建立完决策树后来进行剪枝操作

在决策树充分生长后，修剪掉多余的分支。根据每个分支的分类错误率及每个分支的权重，计算该节点不修剪时预期分类错误率；对于每个非叶节点，计算该节点被修剪后的分类错误率，如果修剪后分类错误率变大，即放弃修剪；否则将该节点强制为叶节点，并标记类别。产生一系列修剪过的决策树候选之后，利用测试数据（未参与建模的数据）对各候选决策树的分类准确性进行评价，保留分类错误率最小的决策树。

最后，我们来总结一下决策树的优缺点：

首先我们看看决策树算法的优点：

　　1）简单直观，生成的决策树很直观。

　　2）基本不需要预处理，不需要提前归一化，处理缺失值。

　　3）使用决策树预测的代价是O(log2m)。 m为样本数。

　　4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。

　　5）可以处理多维度输出的分类问题。

　　6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释

　　7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。

　　8） 对于异常点的容错能力好，健壮性高。

　　我们再看看决策树算法的缺点:：

　　1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

　　2）决策树会因为样本发生一点点的改动（特别是在节点的末梢），导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

　　3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。

　　4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。

　　5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。