分类算法之决策树

一、原理

决策树是一种非参数的监督学习方法，它主要用于分类和回归。决策树的目的是构造一种模型，使之能够从样本数据的特征属性中，通过学习简单的决策规则——IF THEN，从而预测目标变量的值。

二、重要概念

不确定性函数I：是事件U发生概率p的单调递减函数

信息熵：当事件U有多种可能情况时，多个不确定性函数I的平均不确定性即为信息熵，信息熵是事物混乱性的度量标准。

其中S是样本集合，p(ui)表示S中第i类样本的比例

三、有哪些决策树算法

目前常用的决策树的算法包括ID3（Iterative Dichotomiser 3）、C4.5和CART（Classification And Regression Tree）。前两种算法主要应用的是基于信息熵的方法，而第三种应用的是基尼系数的方法。

1. ID3算法（基础）

核心思想：前面我们提到过信息熵，表示样本分布的混乱程度，如果我们能够找到一个属性对其进行分类，例如根据颜色，将水果分成两个样本集，那么这两个样本的信息熵加权求和之后，总的熵会减小，即逐渐变为有秩序，那么这个信息熵减小的值我们称为信息增益(Information Gain)，决策树的核心思想就是每次找到信息增益最大的属性进行节点分裂。

该式表示，总样本集D在经过对A属性进行分类后的信息增益。因此我们在D内遍历所有属性，选择信息增益最大的那个特征属性进行分类。在下次迭代循环中，我们只需对上次分类剩下的样本集合计算信息增益，如此循环，直至不能再分类为止。

缺陷：ID3应用的是信息增益的方法，因此会更倾向选择那些包括很多种类的特征属性，即哪个属性A中的n多，那么这个A的信息增益就可能更大。我们可以这样理解：如果有一个属性，可以将原样本分为N类，每个类别中只有1个样本，那么每个类别中的熵就是最小值0，这样加权求和后，信息增益就是最大的了。我们应该避免出现这样的情况。

2.C4.5算法

它与ID3算法的作者是同一个人，我们可以将C4.5理解为ID3的扩展。针对ID3的缺陷，C4.5使用信息增益率这一准则来衡量混乱度（也叫非纯度），即：

其中，SI(D, A)表示分裂信息值，它的定义为：

后续类似于ID3，再选择信息增益率最大的那个特征属性作为分类属性。

3.CART算法

CART算法是由Breiman等人首先提出，与前两者的最明显的两个区别：

① CART依据的是基尼系数，而非信息增益或信息增益率。

针对特征属性A，分类后的基尼指数为：

核心思想：选择基尼指数最小的那个特征属性作为分类属性。

② CART树必为二叉树，它包括分类树和回归树两种。

分类树的算法：

对于二分类属性，我们直接选择基尼系数最小的那个属性作为分类属性。如果特征属性A中有多于2个的值，即n>2，这时我们就需要一个阈值β，它把D分割成了D和D两个部分，不同的β得到不同的D和D，我们重新设D的样本数为L，D的样本数为R，因此有L+R=N。

进一步，求基尼系数的最小值，可以转变为求下式的SG最大值：

回归树的算法：

两者的不同之处是，分类树的样本输出（即响应值）是类别，属于离散值，如判断蘑菇是有毒还是无毒，周末去看电影还是不去。而回归树的样本输出是数值的形式，属于连续值，比如给某人发放房屋贷款的数额就是具体的数值，可以是0到120万元之间的任意值。为了得到回归树，我们就需要把适合分类的非纯度度量参数换成适合回归的非纯度度量参数。因此我们将均方误差替代基尼系数：

式中N表示D集合的样本数量，y和r分别为第i个样本的输出值和预测值。如果我们把样本的预测值用样本输出值的平均来替代，则转化为：

如果针对于某个属性A，我们把集合D划分为s个部分，则划分后的均方误差为：

类似于信息增益，上两式求差值后，即为划分后的误差减小：

我们寻求的是最大化的误差减小，又因为CART是二叉树，所以转化为：

问题最后转化为求方括号内的△LLS最大值：

到这里，我们总结一下CART分类树和回归树：

Ⅰ. 特征为类的分类树：

① 对于两类问题，即样本的分类（响应值）只有两种情况：响应值为0和1，按照特征属性的类别的样本响应值为1的数量的多少进行排序。例如我们采集20个样本来构建是否踢球分类树，设出去踢球的响应值为1，不踢球的响应值为0，直接带入公式计算SG值。

② 对于非两类问题，采用的是层次聚类的方法。如一共有14个样本，按照由小至大的顺序为：abcdefghijklmn，第一次分叉为：a|bcdefghijklmn，竖线“|”的左侧被划分到左分支，右侧被划分到右分支，带入公式计算SG值，然后第二次分叉：ab|cdefghijklmn，同理带入公式计算SG值，，以此类推，得到这13次分叉的最大值，该种分叉方式即为最佳的分叉方式，其中阈值β为分叉的次数。

Ⅱ. 特征为数值的分类树：

由于特征属性是用数值进行表示，我们就按照数值的大小顺序排序，求出相邻两值间的平均数，根据此数值，按照上面非两类的问题进行计算。

Ⅲ. 特征为类的回归树：

计算每种特征属性各个种类的平均样本响应值，按照该值的大小进行排序，然后依次带入公式计算△LLG值，求最大值。

Ⅳ. 特征为数值的回归树：

该种情况与特征为数值的分类树相同，就按照数值的大小顺序依次带入公式计算△LLG值，求最大值。

四、训练决策树的四个问题

Q1：如何处理异常数据？

Q2：某些样本缺失了某个特征属性，但该特征属性又是最佳分叉属性，那么如何对该样本进行分叉呢？

解决办法：

一种是直接把该样本删除掉；

一种是用各种算法估计该样本的缺失属性值；

一种是用另一个特征属性来替代最佳分叉属性，该特征属性被称为替代分叉属性。因此在计算最佳分叉属性的同时，还要计算该特征属性的替代分叉属性，以防止最佳分叉属性缺失的情况。

Q3：如何避免过拟合问题？

由于决策树的建立完全是依赖于训练样本，因此该决策树对该样本能够产生完全一致的拟合效果。但这样的决策树对于预测样本来说过于复杂，对预测样本的分类效果也不够精确。这种现象就称为过拟合。

将复杂的决策树进行简化的过程称为剪枝，它的目的是去掉一些节点，包括叶节点和中间节点。剪枝常用的方法有预剪枝和后剪枝两种。预剪枝是在构建决策树的过程中，提前终止决策树的生长，从而避免过多的节点的产生。该方法虽然简单但实用性不强，因为我们很难精确的判断何时终止树的生长。后剪枝就是在决策树构建完后再去掉一些节点。常见后剪枝方法有四种：悲观错误剪枝（PEP）、最小错误剪枝（MEP）、代价复杂度剪枝（CCP）和基于错误的剪枝（EBP）。

Q4：如何选择训练集和测试集？

一般会采取Cross-Validation法（交叉验证）：比如一共有10组数据：

第一次.  1到9做训练数据， 10做测试数据

第二次.  2到10做训练数据，1做测试数据

第三次. 1，3到10做训练数据，2做测试数据，以此类推

做10次，然后大平均错误率。这样称为 10 folds Cross-Validation。

比如 3 folds Cross-Validation 指的是数据分3份，2份做训练，1份做测试。 

以上

个人总结，欢迎交流~

ps：更多内容，可以关注公众号【bigdata_x】对话框回复“见面礼”，获取免费的大数据学习资源。

树立人生目标的四个建议：

1.找到自己想要什么

2.直面恐惧成长得更快

3.寻找帮助别人的机会

4.按照理想中的标准行事