决策树定义

决策树是一种特殊的树形结构，一般由节点和有向边组成。其中每个内部节点表示一个特征或属性，而每一个有向边包含有判断条件代表一个测试输出，每个叶节点代表一个类别。一般的，一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。叶节点对应于决策结果，其他每个节点则对应于一个属性测试。每个节点包含的样本集合根据属性测试的结果被划分到子节点中，根节点包含样本全集，从根节点到每个叶节点的路径对应了一个判定测试序列。决策树是常用的分类学习算法（分类树），当然也能用于处理回归问题（回归树），同时也适合集成学习比如随机森林。

分类树

分类树是一种描述对实例进行分类的树形结构。在使用分类树进行分类时，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点。这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。

假设给定训练数据集：D={(x1,y1),(x2,y2),...,(xN,yN)}

其中，xi=(xi(1), xi(2),... , xi(n))T, 为输入实例，即特征向量，n为特征个数，i = 1，2 … ，N，N为样本容量，yi∈{1,2,...,K}为类标。

分类树学习的目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

决策树模型

在机器学习中，决策树是一个预测模型，它代表的是对象属性（特征）与对象值（标签）之间的一种映射关系。

决策树模型是比较简单直观的，可以理解为一系列if-this-then-that语句，对于一个给定的模型，可以非常方便的输入数据进行预测。

决策树主要有根节点，内部节点（非叶子节点），分支，以及叶子节点构成。具体的含义如 决策树的内部构造图：

如果我们想探索泰坦尼克号沉没事件中，什么样的人更有可能存活，使用决策树模型就是一个不错的选择。

决策树分类算法

输入：
训练集：D = ( x 1 , y 1 ) , ( x 2 , y 2 ) , ? , ( x N , y N )
 属性集：A = a 1 , a 2 , ? , a n
过程：
函数T r e e G e n e r a t e ( D , A ) TreeGenerate(D, A)TreeGenerate(D,A)
输出：
以node为根节点的决策树
算法：
生成结点根node
if D 中样本全属于同一类别Ck then
将node标记为Ck类叶结点
return
end if
if A=? OR D中样本在A 上取值相同 then
将node标记为叶结点，其类别标记为D 中样本数最多的类
return
end if
从A 中选择最优划分属性a?
? for a ?的每一个值a?v do
为node生成一个分支：令Dv 表示D DD中在a?上取值为a?的样本子集
if Dv 为空 then
将分支结点标记为叶结点，其类别标记为D DD中样本最多的类
return
else
以TreeGenerate ( Dv , A ? {a?}) 为分支结点
end if
end for

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去，如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

从上述过程中就可以看出，决策树的生成是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回

• 当前结点包含的样本全属于同一类别，无需划分
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
• 当前结点包含的样本集合为空，不能划分

在第二种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别。在第三种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。这两种情形的处理实质不同：第二种情况是在利用当前结点的后验分布，而第三种情况则是把父结点的样本分布作为当前结点的先验分布。

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

可以看出，决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

构建决策树模型

构建决策树模型主要有3个步骤，先进行特征选择，根据评价指标来生成决策树，最后再进行模型优化。

具体的流程图如下，

决策树生成的过程是通过来衡量不同特征对信息混乱程度降低的效果来进行选择。不同的评价标准决定了特征排序的优先顺序，从而影响了模型的准确性。

决策树模型评价标准和数学知识

流程图中展示的3种最常用的评价标准（信息增益，信息增益比，基尼系数），每一种对应一个不同的模型。

为了方便理解，我们将会从最基础的熵的概念开始，逐级递进。

熵（entropy）

概念：熵是顺序/混乱的衡量标准，表示信息/数据的混乱程度。越混乱，熵越大，越有序，熵越小，即数据的纯度越高，数据越趋于一致。

例子：一个凌乱的房间的熵比较高，信息增益低，当你将房间归类整理之后，这个房间的熵会降低，信息增益提高。

公式：

1）对应一个概率：

2）对一个整体的状态（计算所有概率类别下的信息期望）

经验熵(empirical entropy)

概念：事件的熵是通过样本估计的，即为样本数据中数出来的

公式：

经验熵(empirical entropy)

注释：H(D)经验熵，|D| 样本容量，K个类别，Ck 样本数量

条件熵(conditional entropy)

概念：在已知随机变量X的条件下，衡量随机变量Y的不确定性。

公式：

信息增益 Information Gain

含义：通过得知特征X，对lable Y的信息不确定性的减少程度

公式：集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差 g(D,A)=H(D)?H(D∣A)

信息增益比 Gain Ratio

定义：集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之比

公式：

基尼系数（Gini index ）

由于前面熵有很多对数运算，运算速度相对较慢，基尼系数很好的解决了这个问题，它可以得到和信息增益类似的结果，但不需要对数运算，且提高了运算效率。

含义：数据集中随机选择的数据点被错误分类的可能性，通过参数优化，他可以最小化误分类的概率。

公式：

k个分类，第k个分类的概率为p(k)，计算胜率的方法。因为常见的模型构建都采用二分类的形式，公式如下，

分类误差对比：

决策树的优缺点

优点

• 决策树易于理解和实现。对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型>属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
• 易于通过静态测试来对模型进行评测，可以测定模型可信度;如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
• 相比贝叶斯算法，决策树的优势在于构造过程不需要任何领域知识或参数设置，在实际应用中，对于探测式的知识发现，决策树更加适用。

缺点

• 对连续性的字段比较难预测，需要对连续数据做分段处理。
• 对有时间顺序的数据，需要很多预处理的工作。
• 当类别太多时，错误可能就会增加的比较快。
• 一般的算法分类的时候，只是根据一个字段来分类。

总结：

本文简单介绍了一下决策树的定义，模型和算法，构建决策树模型的步骤以及评估标准相关的数学知识，后面会结合原理 以实例的形式展示决策树模型的构建和编码实现。