机器学习-决策树-03-灵析社区

决策树：

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

构建树的原则

我们构建一棵决策树的基本想法就是，我们希望决策树每个叶子节点包含的样本尽可能属于同一个类别，即结点的“纯度”越来越高

决策树划分选择的方法

根据构建树的原则来看，即使得每个结点的纯度尽可能小，那么我们需要一些指标评价“纯度”这个概念。信息熵和基尼指数是两个常用的指标。

决策树算法：

1、熵(Entropy)

信息熵(information entropy)是度量样本集合纯度的常用指标；

假定当前样本集合D中第k类样本所占的比例为 pk(k=1,2,…,|Y|) ,

则D的信息熵为:

Ent(D)的值越小，D的纯度越高(约定：若p=0则plog2p=0)

2、信息增益(Information Gain)

一般而言，信息增益越大，则意味着用属性a来进行划分所获得的纯度提升越大：

ID3就是以信息增益为准则来选择划分属性的

3、增益率

实际上，信息增益对可取值数目较多的属性有所偏好(如编号，在西瓜集中若以编号为划分属性，则其信息增益最大)，为减少由于偏好而带来的不利影响，C4.5算法使用增益率(gain ratio)来选择最优划分属性

其中：

称为属性a的固有值(intrinsic value),属性a的可能数目越多，则IV(a)的值通常越大

然而，增益率准则对可取值数目较少的属性有所偏好，C4.5采用的是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

4、基尼指数

CART(Classification and Regression Tree)使用基尼指数(Gini index)来选择划分属性，数据集的纯度可用基尼值来度量

属性a的基尼指数定义为：

在属性集合A中寻找:

CART决策树使用基尼指数作为属性划分的标准

5、剪枝处理

剪枝(pruning)是决策树学习算法对付过拟合的主要手段，基本策略有预剪枝(prepruning)和后剪枝(post-pruning)

• 预剪枝：在决策树的生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来泛化性能提升则停止划分
• 后剪枝：先生成一个完整的树，然后自底向上对非叶节点考察，若将该节点对应的子数替换为叶节点能提升泛化性能则替换
• 
• 5.1 预剪枝

• 预剪枝的关键在于是否继续进行划分：在上面的西瓜的例子当中，如果我们使用脐部进行划分，那么图中②、③和⑥分别包含编号为{1 ， 2 ， 3 ， 14} 、{6 ， 7 ， 15 ， 17} 和{10 ， 16} 的训练样例，因此这3个结点分别被标记为叶结点“好瓜”、"好瓜"、"坏瓜"此时，验证集中编号为{4 ， 5 ， 8 ，11， 12} 的样例被分类正确，验证集精度为5/7 x 100% = 71.4% > 42.9%。于是，用"脐部"进行划分得以确定。
• 预剪枝使决策树的很多分支都没有展开，不仅降低了过拟合的风险，还显著减少了训练时间和测试时间，但是可能会引起过拟合
• 5.2 后剪枝

• 后剪枝通常比预剪枝保留更多的分值，一般情况下，后剪枝欠拟合风险很小，泛化性能优于预剪枝，但其训练时间比未剪枝和预剪枝都要大得多

连续与缺失值

连续值处理

在C4.5决策树算法当中，使用二分法对连续的数值进行处理：我们可以考察包含n-1个元素的候选划分点集合

我们将每个区间的中位点作为候选划分点，然后我们使用想离散值属性一样来考察这些划分点，选取最优的划分点进行样本集合的划分，例如：

对上图表格当中的例子而言，设置密度为：

根据Gain的计算公式可以得到属性”密度“的信息增益位0.262，对应于划分点0.381。同时按照之前的离散值的计算方法，计算离散属性的信息增益的值：

Gain(D ，色泽) = 0.109; Gain(D ，根蒂) = 0.143;

Gain(D ，敲声) = 0.141; Gain(D ，纹理) = 0.381;

Gain(D ，脐部) = 0.289; Gain(D ， 触感) = 0.006;

Gain(D ，密度) = 0.262; Gain(D ，含糖率) = 0.349.

可以发现纹理的信息增益是最大的，所以我们选择”纹理“作为根节点作为划分属性，然后每个结点划分过程递归进行，最终生成如图所示的决策树：

缺失值的处理

一些数据由于敏感等原因，部分数据可能会出现缺失的情况，例如下面的情况：

在决策树的C4.5算法当中，我们使用了没有缺失值的样本子集进行树的构建。以上述表格为例子举例，没有缺失值的样例子集包含编号为{2，3，4，6，7，8，9，10，11，12，14，15，16，17}的14个样例（总共有17个样例）。那么相应的信息熵为：

其分别在”色泽“属性上取值为”青绿“，”乌黑“以及”浅白“的样本子集，那么有：

因此在样本子集上，其信息增益为：

那么在样本集上的”色泽“的信息增益为，要乘以其没有缺失的样例数量除以全部的样例数量：

在上述文章提及的变量为，其中每个样本的权重 wk为1：

决策树算法优缺点

优点：

1. 决策树具有高度可解释性；
2. 需要很少的数据预处理；
3. 适用于低延迟应用。

劣势：

1. 很可能对噪声数据产生过拟合。决策树越深，由噪声产生过拟合的可能性就越大。一种解决方案是对决策树进行剪枝。

代码演示-Decision Tree