决策树

1. 模型背景

决策树（decision tree）是一类常见的机器学习方法。以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新示例进行分类，这个把样本分类的任务，可看作对“当前样本属于正类吗？”这个问题的“决策”或“判定”过程。顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。

决策树学习也是资料探勘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。

2. 模型原理

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy系统的凌乱程度，使用算法ID3, **.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

分类树（决策树）是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

3. 实施分析步骤

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单而直观的“分而治之”（divide-and-conquer）策略。如下图所示：

图 决策树学习基本算法

决策树的构造过程一般分为3个部分，分别是特征选择、决策树生产和决策树裁剪。

• 特征选择

特征选择表示从众多的特征中选择一个特征作为当前结点分裂的标准，如何选择特征有不同的量化评估方法，从而衍生出不同的决策树，如ID3（通过信息增益选择特征）、**.5（通过信息增益比选择特征）、CART（通过Gini指数选择特征）等。

• 信息增益

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为），则D的信息熵定义为：

Ent（D）的值越少，则D的纯度越高。

假定离散属性a有V个可能的取值{a1， a2， …， aV}，若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为aV的样本，记为Dv。由信息熵并且考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重，即样本数越多的分支结点影响越大，于是可计算出用属性a对样本集D进行划分所获得的“信息增益”（information gain）

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择，著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

• 信息增益率

信息增益准则对可取值数目较多的属性有所偏好（如编号），为减少这种偏好可能带来的不利影响，**.5决策树算法不直接使用信息增益，而是使用增益率（gain ratio）来选择最优划分属性。采用与信息熵相同的符号表示，增益率定义为

其中

称为属性的“固有值”（intrinsic value）。属性a的可能数目越多（即V越大），则IV（a）的值通常会越大。需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此**.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于水平的属性，再从中选择增益率最高的。

• 基尼指数

CART分类树采用基尼指数（Gini index）选择划分属性。数据集D的纯度可用基尼指数度量：

Gini（D）反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此Gini(D)越小，数据集D的纯度越高。

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

在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即.

决策树特征选择目的（准则）：使用某特征对数据集划分之后，各数据子集的纯度要比划分钱的数据集D的纯度高（也就是不确定性要比划分前数据集D的不确定性低）

• 决策树的生成

根据选择的特征评估标准，从上至下递归地生成子结点，直到数据集不可分则停止决策树停止生长。这个过程实际上就是使用满足划分准则的特征不断的将数据集划分成纯度更高，不确定行更小的子集的过程。对于当前数据集的每一次划分，都希望根据某个特征划分之后的各个子集的纯度更高，不确定性更小。

• 决策树的裁剪

决策树容易过拟合，一般需要剪枝来缩小树结构规模、缓解过拟合。决策树的基本策略有预剪枝（prepruning）和后剪枝（post-pruning）。

预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点；后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。

4. 输入输出参数设置

决策树（decision tree）是一类常见的机器学习方法。以二分类任务为例，我

当特征数据是连续值时，需要对数据进行离散化处理（如考试得分0～100，1～59为不及格，60～80为达标，80～100为优秀），这样离散处理后的数据可以用来构建决策树；计算划分后子数据集的信息熵时，加上一个与类别个数成正比的正则项来作为最后的信息熵：这样当算法选择的某个类别较多的特征，使信息熵较小时，由于受到正则项的“惩罚”，导致最终的信息熵也较大。这样通过合适的参数可以使算法训练得到某种程度的平衡。

Python中sklearn.tree.DecisionTreeClassifier类实现决策树算法，其中几个典型的参数解释如下图所示：

模型调参注意事项如下：

当样本少数量但是样本特征非常多的时候，决策树很容易过拟合，样本数比特征数多一些会比较容易建立健壮的模型；如果样本数量少但是样本特征非常多，在拟合决策树模型前，推荐先做维度规约，比如主成分分析（PCA），特征选择（Losso）或者独立成分分析（ICA）。这样特征的维度会大大减小。

推荐多用决策树的可视化，同时先限制决策树的深度（比如最多3层），这样可以先观察下生成的决策树里数据的初步拟合情况，然后再决定是否要增加深度。注意观察样本的类别情况（主要指分类树），如果类别分布非常不均匀，就要考虑用class_weight来限制模型过于偏向样本多的类别。

决策树的数组使用的是numpy的float32类型，如果训练数据不是这样的格式，算**先做copy再运行；如果输入的样本矩阵是稀疏的，推荐在拟合前调用csc_matrix稀疏化，在预测前调用csr_matrix稀疏化。

5. 运行效果评价

• 优点

决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。

对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。

• 缺点

对连续性的字段比较难预测。

对有时间顺序的数据，需要很多预处理的工作。

当类别太多时，错误可能就会增加的比较快。

一般的算法分类的时候，只是根据一个字段来分类。

6. 模型应用

以气象数据为例来说明决策树创建的过程。

在没有使用特征划分类别的情况下，有9个yes和5个no，当前的熵为：

假设我们以 outlook 特征划分数据集，对该特征每项指标分别统计：在不同的取值下 play 和 no play 的次数：

此时各分支的熵计算如下：

因此如果用特征outlook来划分数据集的话，总的熵为：

那么最终得到特征属性outlook带来的信息增益为：IG(outlook)=0.940−0.694=0.246，然后用同样的方法，可以分别求出temperature，humidity，windy的信息增益。IG(temperature)=0.029，IG(humidity)=0.152，IG(windy)=0.048。可以得出使用outlook特征所带来的信息增益最大，所以应该首先选择outlook来划分数据集。然后继续划分各个分支的数据集，知道每个分支下的所有实例都具有相同的分类。最终构造出决策树：