1、什么是决策树？
& & & & 决策树是一种类似于流程图的树结构。其中，每个内部结点（非树叶结点）表示在一个属性上的测试，每个分枝代表该测试的一个输出，而每个树叶结点存放一个类标号。树的最顶层结点是根节点。内部结点用矩形表示，而叶结点用椭圆表示。决策树可以是二叉的，也可以是非二叉的（根据不同的决策树算法而定）。一棵典型的决策树如下图：
2、如何使用决策树分类？
& & & &给定一个类标号未知的元组X，在该决策树上测试该元组的属性值。跟踪一条由根到叶结点的路径，该叶结点就存放着该元组的类预测。
3、为什么决策树分类器如此流行？
& & &（1）决策树分类器的构造不需要任何领域知识或参数设置，因此适合于探测式知识发现。
& & &（2）决策树可以处理高维数据。
& & &（3）获取的知识用树的形式表示是直观的，并且容易被人理解。
& & &（4）决策树归纳的学习和分类步骤是简单和快速的。
& & &（5）一般而言，决策树分类器具有很好的准确率。
4、决策树算法
& & & &&属性选择度量：是一种选择分裂准则，把给定类标记的训练元组的数据分区D“最好地”划分成单独类的启发式方法。理想情况下，D划分后的每个小分区都是纯的（即落在一个给定分区的所有元组都属于相同的类）。“最好的”分类准则是最接近这种情况的划分。
& & & & 根据分裂属性选择度量的不同，决策树的常见算法有ID3（度量：信息增益）、C4.5（度量：增益率）、CART（度量：基尼指数）。当然，决策树算法之间的差别也包括用于剪枝的机制等。
& & & & 它们都采用贪心（即非回溯）的方法，其中决策树以自顶向下递归的分治法构造。大多数决策树算法都沿用这种自顶向下方法，从训练元组集和它们相关联的类标号开始构造决策树。随着树的构建，训练集递归地划分成较小的子集。这些子集分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则当前已经正确地划分数据分类，无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内。
& & & & 基本决策树算法概括在下图中：
图 &由训练元组归纳决策树的基本算法
& & & &递归的终止条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。
4.1 &ID3算法（信息增益）
& & & & ID3算法（Iterative&Dichotomiser3&& 迭代的二分器3代）是一位机器学习研究人员J.Ross&Quinlan开发的决策树算法。
& & & & ID3算法的核心思想：以信息增益作为属性选择度量（该度量基于香农在研究消息的值或“信息内容”的信息论方面的先驱工作），选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。
& & & & 思想：
& & & &（1）自顶向下的贪婪搜索遍历可能的决策树空间构造决策树
& & & &（2）从“哪一个属性将在树的根节点被测试”开始；
& & & &（3）使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试。
& & & &（4）然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。
& & & &（5）重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。
& & & & & 信息增益：原来的信息需求（仅基于类比例）与新的信息需求（对属性A划分后）之间的差。
& & & & & & & & & & & & & &&
& & & & & & & & &Gain（A）告诉我们通过属性A上的划分我们得到了多少。选择具有最高增益Gain（A）的属性A作为分裂属性。这等价于在“能做最佳分类”的属性A上划分，使得完成 元组分类还需要的信息最小（即最小化InfoA（D））
& & & & & 对D中的元组分类所需的期望信息由下式给出：
& & & & & & & & & & & & & &
& & & & & 其中，pi是D中任意元组属于类Ci的非零概率，Info（D）又称为D的熵。
& & & & & 离散属性A（具有v个不同的观测值）对D进行属性划分后所需要的期望信息：& &&
& & & & & & & & & & & & & & & &
& & & & & &需要的期望信息越小，分区的纯度越高。
& & & & & &例子：
顾客数据库标记类的训练元组
& & & & & & & & 首先，计算对D中元组分类所需要的期望信息：
& & & & & & & & & & & & & & & & &
& & & & & & & &下一步，需要计算每个属性的期望信息需求（先计算属性age）。
& & & & & & & & & & & & & & & &&
& & & & & & & & & & & & & & & &&
& & & & & & & & 类似地，可以计算Gain（income）=0.029位 & Gain（student）=0.151位 & Gain（credit_rating）=0.048位。
& & & & & & & & 由于age在属性中具有最高的信息增益，所以它被选作分裂属性。并且每个属性值生长出一个分枝，然后元组据此划分。
& & & & & & & & 其中，落在分区age=“middle_age”的元组都属于相同的类。由于它们都属于类“yes”，所以要在该分枝的端点创建一个树叶，并用“yes”标记。 算法返回的最终决策树 & 如下图：
& & & & & & & & & & &这个决策树只是一个属性分裂后的决策树，还需在每个分枝上递归地进行属性分裂（比如，在youth这个分枝上的剩下元组中，可以对student属性进行分裂，因为这样分类后信息增益最大，student是no（yes），class是no（yes））。
&&&&&&&&上面我们说的分裂属性都是离散值的，如果是连续值的我们怎么计算它们的信息增益呢？
&&&&&&& 假设属性A是连续值的，而不是离散值的（例如，假定有属性age的原始值，而不是该属性的离散化版本。）对于这种情况，必须确定A的“最佳”分裂点，其中分裂点是A上的阈值。
&&&&&&& 首先，将A的值按递增序排序。典型地，每对相邻值的中点被看作可能的分裂点。这样，给定A的v个值，则需要计算v-1个可能的划分。对于A的每个可能的分裂点，计算Info（D），其中分区的个数为2，A具有最小期望信息需求的点选作A的分裂点。D1是满足A&=split_poin的元组集合，而D2是满足A&split_poin的元组集合。这样的话，就转换成离散属性的计算了。
& & & & 在此，顺便介绍一下，根据属性分裂准则划分元组的三种可能性：
4.2& C4.5算法（增益率）
& & & & ID3的缺点：信息增益度量偏向具有许多输出的测试。换句话说，它倾向于选择具有大量值的属性。例如，考虑充当唯一标识符的属性，如product_ID。在product_ID的划分将导致大量分区（与值一样多），每个只包含一个元组。由于每个分区都是纯的，所以基于该划分对数据集D分类所需要的信息为Infoproduct_ID(D)=0。因此，通过对该属性的划分得到的信息增益最大。显然，这种划分对分类没有用。C4.5的出现就是为了克服这种偏倚。
& & & & C4.5：也是Quinlan提出来的，它是对ID3算法的改进，这些改进包括处理数值属性、缺失值、噪声数据和由决策树产生规则的方法。
& & & & C4.5采用增益率作为属性选择度量，增益率定义为：
& & & & & & & & & & & & & & & & & & & & & & &
& & & & & & & & &选择具有最大增益率的属性作为分裂属性。然而需要注意的是，随着划分信息趋向于0，该比率变得不稳定。为了避免这种情况，增加一个约束：选取的测试的信息增益必须较大，至少与考察的所有测试的平均增益一样大。比如我们可以先计算每个属性的增益，然后仅对那些增益高过平均值的属性应用增益率测试。
& & & & &其中，分裂信息度量被定义为(分裂信息用来衡量属性分裂数据的广度和均匀)：
& & & & & & & & & & & & & & & & & & & & & & &
& & & & &例子：
& & & & &事务数据库中属性income的增益率的计算：
& & & & & & & & & & & & & & & & & & & & & & &
& & & & & & & & & & & & & & & & & & & & & & &&
4.3& CART算法（基尼指数）
& & & &&CART：分类和回归树（ClassificationAnd Regression Tree）算法由Breiman等人于1984年提出的。它是以二叉树的形式给出，易于理解、使用和解释。如果目标变量是离散的，则该树为分类树（classification
tree），而对于连续数值目标变量，则该树称为回归树（regression tree）。
& & & & Gini指数：是一种不等性度量，由意大利统计学家Corrado Gini提出，并于1912年发表在他的文章“Variabilita e mutabilita”中。它通常用来度量收入不平衡，但是它可以用来度量任何不均匀分布。Gini指数是一个0—1之间的数。其中0对应于完全相等（其中每个人都具有相同的收入），而1对应于完全不相等（其中一个人具有所有收入，而其他人收入都为零）。
& & & & &基尼指数度量数据分区或训练元组集D的不纯度，定义为：
& & & & & & & & & & & & & & & & & & & & & &&
其中pi是D中元组属于Ci类的概率，对m个类计算和。
& & & & &基尼指数考虑每个属性的二元划分。
& & & （1）首先考虑A是离散值属性的情况，其中A具有v个不同值出现在D中。如果A具有v个可能的值，则存在2v个可能的子集。例如，如果income具有3个可能的值{low,medium,high}，则可能的子集具有8个。不考虑幂集（{
low,medium,high}）和空集（{ }），因为从概念上讲，它不代表任何分裂。因此，基于A的二元划分，存在2v&-2中形成数据集D的两个分区的可能方法。
当考虑二元划分裂时，计算每个结果分区的不纯度的加权和。例如，如果A的二元划分将D划分成D1和D2，则给定该划分，D的基尼指数为
& & & & & & & & & & & & & & & & & & & & & & & &
选择该属性产生最小基尼指数的子集作为它的分裂子集。
& & & （2）对于连续值属性，其策略类似于上面介绍的信息增益所使用的策略。
& & & & & & & & 对于离散或连续值属性A的二元划分导致的不纯度降低为
& & & & & & & & & & & & & & & & & & & & & & & &&
& & & & & & & & 最大化不纯度降低（或等价地，具有最小基尼指数）的属性选为分裂属性。该属性和它的分裂子集（对于离散值的分裂属性）或分裂点（对于连续值的分裂属性）一起 & & & & 形成分裂准则。
& & & & 例子：
& & & & 继续使用“顾客数据库”进行介绍。
& & & （1）计算D的不纯度：
& & & & & & & & & & & & & & & & & & & & & & &&
& & & （2）为了找出D中元组的分裂准则，需要计算每个属性的基尼指数。从属性income开始，并考虑每个可能的分裂子集。考虑子集{low，medium}，基于该划分计算出的基尼指数为：
& & & & & & & & & & & & & & & & & & & & & & &
& & & & 类似地，其余子集划分的基尼指数值是：0.458（子集{low，high}和{medium}）和0.450（子集{medium，high}和{low}）。因此，属性income的最好划分在{low，medium}（或{high}） 上，因为它最小化基尼指数。
& & & &评估属性age，得到{youth，senior}（或{middle_aged}）为age的最好划分，具有基尼指数0.357；
& & & &属性student和credit_rating都是二元的，分别具有基尼指数&#和0.429。
& & & （3）属性age和分裂子集{youth，senior}产生最小的基尼指数。二元划分“age属于{youth，senior}？”导致D中元组的不纯度降低最大，并返回作为分裂准则。从它生长出两个分枝，并且相应地划分元组。
5、决策树算法之间的比较
& & & &信息增益偏向于多值属性。尽管增益率调整了这种偏倚，但是它倾向于产生不平衡的划分，其中一个分区比其他分区小得多。基尼指数偏向于多值属性，并且当类的数量很大时会有困难。它还倾向于导致相等大小的分区和纯度。尽管是有偏的，但是这些度量在实践中产生相当好的结果。
& & & & 决策树为什么要剪枝？
& & & & 原因是避免决策树过拟合(Overfitting)样本。前面的算法生成的决策树非常详细并且庞大，每个属性都被详细地加以考虑，决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话，你会发现对于训练样本而言，这个树表现完好，误差率极低且能够正确得对训练样本集中的样本进行分类。训练样本中的错误数据也会被决策树学习，成为决策树的部分，但是对于测试数据的表现就没有想象的那么好，或者极差，这就是所谓的过拟合(Overfitting)问题。
& & & & “如何进行剪枝？”有两种常用的剪枝方法：先剪枝和后剪枝
& & & & 先剪枝：通过提前停止树的构建（例如，通过决定在给定的节点不再分裂或划分训练元组的子集）而对树“剪枝”。一旦停止，结点就成为树叶。该树叶可以持有子集元组中最频繁的类，或这些元组的概率分布。
& & & & 在构造树时，可以使用诸如统计显著性、信息增益、基尼指数等度量来评估划分的优劣。如果划分一个结点的元组导致低于预定义阈值的划分，则给定子集的进一步划分将停止。然而，选取一个适当的阈值是困难的。高阈值可能导致过分简化的树，而低阈值可能使得树的简化太少。
& & & & &例子：限定树的最大生长高度为3
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
& & & & 后剪枝：它由“完全生长”的树剪去子树。通过删除节点的分枝并用树叶替换它而剪掉给定结点上的子树。该树叶的类标号用子树中最频繁的类标记。
& & & & 例子：
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
& & & & 决策树算法用的是什么剪枝？
& & & & CART使用的是：代价复杂度（后剪枝方法的一种实例）剪枝算法。
& & & &该方法把树的复杂度看作树中树叶结点的个数和树的错误率的函数（其中，错误率是树误分类的元组所占的百分比）。它从树的底部开始。对于每个内部结点N，计算N的子树的代价复杂度和该子树剪枝后N的子树（即用一个树叶节点替换）的代价复杂度，比较这两个值。如果剪去结点N的子树导致较小的代价复杂度，则剪掉该子树；否则，保留该子树。
& & & & C4.5使用的是：悲观剪枝。它类似于代价复杂度方法，因为它也使用错误率评估，对子树剪枝做出决定。
& & & & 剪枝后还可能存在什么困扰？
& & & & 另外，对于组合方法，先剪枝和后剪枝可以交叉使用。后剪枝所需要的计算比先剪枝多，但是通常产生更可靠的树。
& & & &尽管剪枝后的树一般比未剪枝的树更紧凑，但是他们仍然可能很大、很复杂。决策树可能受到重复和复制的困扰，使得他们很难解释。
& & & &沿着一条给定的分枝反复测试一个属性时就会出现重复。复制是树中存在重复的子树。这些情况影响了决策树的准确率和可解释性。
& & & &解决办法：（1）使用多元划分（基于组合属性的划分）（2）使用不同形式的知识表示（如规则），而不是决策树。
& & & & 更多关于剪枝的内容（特别是代价复杂度剪枝和悲观剪枝），可以参考文献：
& & & &&决策树分类及剪枝算法研究_张宇（哈尔滨理工大学）
& & & &&决策树学习及其剪枝算法研究_王黎明（武汉理工大学）
7、可伸缩性与决策树归纳（后期续写）
本文已收录于以下专栏：
相关文章推荐
先验概率，后验概率，似然概率，条件概率，贝叶斯，最大似然
总是搞混，这里总结一下常规的叫法：先验概率：事件发生前的预判概率。可以是基于历史数据的统计，可以由背景常识得出，也可以是人的主观观点给出。一...
决策树是一种自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于一类。
      决策树学习算法优点是，它可以自学习。在学习...
事件本质是属性。同时事件总是属于一个方法类型，所以说事件是方法指针。
在集成学习之Adaboost算法原理小结中，我们对Boosting家族的Adaboost算法做了总结，本文就对Boosting家族中另一个重要的算法梯度提升树(Gradient Boosting De...
CART分类与回归树与GBDT(Gradient Boost Decision Tree)
在2006年12月召开的 IEEE 数据挖掘国际会议上，与会的各位专家选出了当时的十大数据挖掘算法（ top 10 data mining algorithms ）。本博客已经介绍过的位列十大算法之中...
用信息增益来构建决策树感觉计算量好大啊，下面介绍新的一种构建决策树的方法
首先我要引入两个新的概念：基尼系数和基尼指数
基尼系数的作用和信息熵的作用类，都是用来度量数据集的纯度的，公式如下：
在CART里面划分决策树的条件是采用Gini
Index，定义如下：
gini(T)=1-sumnj=1p2j
其中，( p_j )是类j在T中的相对频率，当类在T中是倾斜的时，gini(T)...
在讲随机森林前，我先讲一下什么是集成学习。集成学习通过构建并结合多个分类器来完成学习任务。集成学习通过将多个学习器进行结合，常可获得比单一学习器更好的泛化性能。
考虑一个简单例子：在二分类任务中，假定...
import java.util.HashM
import java.util.LinkedL
import java.util.L
import jav...
他的最新文章
讲师：王哲涵
讲师：王渊命
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)Posts - 807,
Articles - 0,
Comments - 14
21:19 by GarfieldEr007, ... 阅读,
机器学习概念
机器学习 (Machine Learning) 是近 20 多年兴起的一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。
机器学习理论主要是设计和分析一些让计算机可以自动学习的算法。机器学习算法是一类从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。因为学习算法中涉及了大量的统计学理论，机器学习与统计推断学联系尤为密切，也被称为统计学习理论。在算法设计方面，机器学习理论关注可以实现的、行之有效的学习算法。很多相关问题的算法复杂度较高，而且很难找到固有的规律，所以部分的机器学习研究是开发容易处理的近似算法。
机器学习在数据挖掘、计算机视觉、自然语言处理、生物特征识别、搜索引擎、医学诊断、检测信用卡欺诈、证券市场分析、DNA 序列测序、语言与手写识别、战略游戏与机器人运用等领域有着十分广泛的应用。它无疑是当前数据分析领域的一个热点内容。
机器学习的算法繁多，其中很多算法是一类算法，而有些算法又是从其他算法中衍生出来的，因此我们可以按照不同的角度将其分类。本文主要通过学习方式和算法类似性这两个角度将机器学习算法进行分类。
监督式学习：从给定的训练数据集中学习出一个函数，当新的数据到来时，可以根据这个函数预测结果。监督学习的训练集需要包括输入和输出，也可以说是特征和目标。训练集中的目标是由人标注的。常见的监督式学习算法包括回归分析和统计分类。
非监督式学习：与监督学习相比，训练集没有人为标注的结果。常见的非监督式学习算法有聚类。
半监督式学习：输入数据部分被标识，部分没有被标识，介于监督式学习与非监督式学习之间。常见的半监督式学习算法有支持向量机。
强化学习：在这种学习模式下，输入数据作为对模型的反馈，不像监督模型那样，输入数据仅仅是作为一个检查模型对错的方式，在强化学习下，输入数据直接反馈到模型，模型必须对此立刻作出调整。常见的强化学习算法有时间差学习。
算法类似性
决策树学习：根据数据的属性采用树状结构建立决策模型。决策树模型常常用来解决分类和回归问题。常见的算法包括 CART (Classification And Regression Tree)、ID3、C4.5、随机森林 (Random Forest) 等。
回归算法：试图采用对误差的衡量来探索变量之间的关系的一类算法。常见的回归算法包括最小二乘法 (Least Square)、逻辑回归 (Logistic Regression)、逐步式回归 (Stepwise Regression) 等。
聚类算法：通常按照中心点或者分层的方式对输入数据进行归并。所有的聚类算法都试图找到数据的内在结构，以便按照最大的共同点将数据进行归类。常见的聚类算法包括 K-Means 算法以及期望最大化算法 (Expectation Maximization) 等。
人工神经网络：模拟生物神经网络，是一类模式匹配算法。通常用于解决分类和回归问题。人工神经网络算法包括感知器神经网络 (Perceptron Neural Network) 、反向传递 (Back Propagation) 和深度学习等。
集成算法：用一些相对较弱的学习模型独立地就同样的样本进行训练，然后把结果整合起来进行整体预测。集成算法的主要难点在于究竟集成哪些独立的较弱的学习模型以及如何把学习结果整合起来。这是一类非常强大的算法，同时也非常流行。常见的算法包括 Boosting、Bagging、AdaBoost、随机森林 (Random Forest) 等。
决策树是附加概率结果的一个树状的决策图，是直观的运用统计概率分析的图法。机器学习中决策树是一个预测模型，它表示对象属性和对象值之间的一种映射，树中的每一个节点表示对象属性的判断条件，其分支表示符合节点条件的对象。树的叶子节点表示对象所属的预测结果。
决策树案例
图 1. 决策树案例图
图 1 是一棵结构简单的决策树，用于预测贷款用户是否具有偿还贷款的能力。贷款用户主要具备三个属性：是否拥有房产，是否结婚，平均月收入。每一个内部节点都表示一个属性条件判断，叶子节点表示贷款用户是否具有偿还能力。例如：用户甲没有房产，没有结婚，月收入 5K。通过决策树的根节点判断，用户甲符合右边分支 (拥有房产为&否&)；再判断是否结婚，用户甲符合左边分支 (是否结婚为否)；然后判断月收入是否大于 4k，用户甲符合左边分支 (月收入大于 4K)，该用户落在&可以偿还&的叶子节点上。所以预测用户甲具备偿还贷款能力。
决策树建立
本文上一节已经讨论如何用一棵决策树进行分类。本节将通过特征选择、剪枝，介绍如何根据已有的样本数据建立一棵决策树。
首先介绍下特征选择。选择一个合适的特征作为判断节点，可以快速的分类，减少决策树的深度。决策树的目标就是把数据集按对应的类标签进行分类。最理想的情况是，通过特征的选择能把不同类别的数据集贴上对应类标签。特征选择的目标使得分类后的数据集比较纯。如何衡量一个数据集纯度，这里就需要引入数据纯度函数。下面将介绍两种表示数据纯度的函数。
信息熵表示的是不确定度。均匀分布时，不确定度最大，此时熵就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。
假设在样本数据集 D 中，混有 c 种类别的数据。构建决策树时，根据给定的样本数据集选择某个特征值作为树的节点。在数据集中，可以计算出该数据中的信息熵：
图 2. 作用前的信息熵计算公式
其中 D 表示训练数据集，c 表示数据类别数，Pi 表示类别 i 样本数量占所有样本的比例。
对应数据集 D，选择特征 A 作为决策树判断节点时，在特征 A 作用后的信息熵的为 Info(D)，计算如下：
图 3. 作用后的信息熵计算公式
其中 k 表示样本 D 被分为 k 个部分。
信息增益表示数据集 D 在特征 A 的作用后，其信息熵减少的值。公式如下：
图 4. 信息熵差值计算公式
对于决策树节点最合适的特征选择，就是 Gain(A) 值最大的特征。
基尼指数是另一种数据的不纯度的度量方法，其公式为：
图 5. 基尼指数计算公式
其中 c 表示数据集中类别的数量，Pi 表示类别 i 样本数量占所有样本的比例。
从该公式可以看出，当数据集中数据混合的程度越高，基尼指数也就越高。当数据集 D 只有一种数据类型，那么基尼指数的值为最低 0。
如果选取的属性为 A，那么分裂后的数据集 D 的基尼指数的计算公式为：
图 6. 分裂后的基尼指数计算公式
其中 k 表示样本 D 被分为 k 个部分，数据集 D 分裂成为 k 个 Dj 数据集。
对于特征选取，需要选择最小的分裂后的基尼指数。也可以用基尼指数增益值作为决策树选择特征的依据。公式如下：
图 7. 基尼指数差值计算公式
在决策树选择特征时，应选择基尼指数增益值最大的特征，作为该节点分裂条件。
接下来介绍剪枝。在分类模型建立的过程中，很容易出现过拟合的现象。过拟合是指在模型学习训练中，训练样本达到非常高的逼近精度，但对检验样本的逼近误差随着训练次数而呈现出先下降后上升的现象。过拟合时训练误差很小，但是检验误差很大，不利于实际应用。
决策树的过拟合现象可以通过剪枝进行一定的修复。剪枝分为预先剪枝和后剪枝两种。
预先剪枝指在决策树生长过程中，使用一定条件加以限制，使得产生完全拟合的决策树之前就停止生长。预先剪枝的判断方法也有很多，比如信息增益小于一定阀值的时候通过剪枝使决策树停止生长。但如何确定一个合适的阀值也需要一定的依据，阀值太高导致模型拟合不足，阀值太低又导致模型过拟合。
后剪枝是在决策树生长完成之后，按照自底向上的方式修剪决策树。后剪枝有两种方式，一种用新的叶子节点替换子树，该节点的预测类由子树数据集中的多数类决定。另一种用子树中最常使用的分支代替子树。
预先剪枝可能过早的终止决策树的生长，后剪枝一般能够产生更好的效果。但后剪枝在子树被剪掉后，决策树生长的一部分计算就被浪费了。
决策树模型评估
建立了决策树模型后需要给出该模型的评估值，这样才可以来判断模型的优劣。学习算法模型使用训练集 (training set) 建立模型，使用校验集 (test set) 来评估模型。本文通过评估指标和评估方法来评估决策树模型。
评估指标有分类准确度、召回率、虚警率和精确度等。而这些指标都是基于混淆矩阵 (confusion matrix) 进行计算的。
混淆矩阵是用来评价监督式学习模型的精确性，矩阵的每一列代表一个类的实例预测，而每一行表示一个实际的类的实例。以二类分类问题为例，如下表所示：
表 1. 混淆矩阵
&预测的类&
P (Positive Sample)：正例的样本数量。
N(Negative Sample)：负例的样本数量。
TP(True Positive)：正确预测到的正例的数量。
FP(False Positive)：把负例预测成正例的数量。
FN(False Negative)：把正例预测成负例的数量。
TN(True Negative)：正确预测到的负例的数量。
根据混淆矩阵可以得到评价分类模型的指标有以下几种。
分类准确度，就是正负样本分别被正确分类的概率，计算公式为：
图 8. 分类准确度计算公式
召回率，就是正样本被识别出的概率，计算公式为：
图 9. 召回率计算公式
虚警率，就是负样本被错误分为正样本的概率，计算公式为：
图 10. 虚警率计算公式
精确度，就是分类结果为正样本的情况真实性程度，计算公式为：
图 11. 精确度计算公式
评估方法有保留法、随机二次抽样、交叉验证和自助法等。
保留法 (holdout) 是评估分类模型性能的最基本的一种方法。将被标记的原始数据集分成训练集和检验集两份，训练集用于训练分类模型，检验集用于评估分类模型性能。但此方法不适用样本较小的情况，模型可能高度依赖训练集和检验集的构成。
随机二次抽样 (random subsampling) 是指多次重复使用保留方法来改进分类器评估方法。同样此方法也不适用训练集数量不足的情况，而且也可能造成有些数据未被用于训练集。
交叉验证 (cross-validation) 是指把数据分成数量相同的 k 份，每次使用数据进行分类时，选择其中一份作为检验集，剩下的 k-1 份为训练集，重复 k 次，正好使得每一份数据都被用于一次检验集 k-1 次训练集。该方法的优点是尽可能多的数据作为训练集数据，每一次训练集数据和检验集数据都是相互独立的，并且完全覆盖了整个数据集。也存在一个缺点，就是分类模型运行了 K 次，计算开销较大。
自助法 (bootstrap) 是指在其方法中，训练集数据采用的是有放回的抽样，即已经选取为训练集的数据又被放回原来的数据集中，使得该数据有机会能被再一次抽取。用于样本数不多的情况下，效果很好。
决策树建模
在本节中，将通过 R 和 IBM SPSS 两种建模工具分别对其实际案例进行决策树建模。
R 是一个用于统计计算及统计制图的优秀的开源软件，也是一个可以从大数据中获取有用信息的绝佳工具。它能在目前各种主流操作系统上安装使用，并且提供了很多数据管理、统计和绘图函数。
下面本节就将使用 R 所提供的强大的函数库来构建一棵决策树并加以剪枝。
清单 1. 构建决策树及其剪枝的 R 代码
# 导入构建决策树所需要的库
library("rpart")
library("rpart.plot")
library("survival")
# 查看本次构建决策树所用的数据源
# 通过 rpart 函数构建决策树
fit &- rpart(Surv(pgtime,pgstat)~age+eet+g2+grade+gleason+ploidy,stagec,method="exp")
# 查看决策树的具体信息
print(fit)
printcp(fit)
# 绘制构建完的决策树图
plot(fit, uniform=T, branch=0.6, compress=T)
text(fit, use.n=T)
# 通过 prune 函数剪枝
fit2 &- prune(fit, cp=0.016)
# 绘制剪枝完后的决策树图
plot(fit2, uniform=T, branch=0.6, compress=T)
text(fit2, use.n=T)
根据代码，运行步骤如下：
导入需要的函数库。当然如果本地开发环境没有相应的库的话，还需要通过 install.packages 函数对库进行安装。
查看本次构建决策树的数据源。stagec 是一组前列腺癌复发的研究数据。
通过 rpart 函数构建决策树，以研究癌复发与病人年龄、肿瘤等级、癌细胞比例，癌细胞分裂状况等之间的关系。
查看决策树的具体信息。
绘制构建完成的决策树图。
通过 prune 函数对该决策树进行适当的剪枝，防止过拟合，使得树能够较好地反映数据内在的规律并在实际应用中有意义。
绘制剪枝完后的决策树图。
该案例决策树的拟合结果与剪枝前后的树如下图所示：
图 12. 决策树案例拟合图
图 13. 未剪枝的决策树图
图 14. 剪枝后的决策树图
IBM SPSS Modeler 是一个预测分析平台，能够为个人、团队、系统和企业做决策提供预测性信息。它可提供各种高级算法和技术 (包括文本分析、实体分析、决策管理与优化)，帮助您选择可实现更佳成果的操作。
在 SPSS Modeler 中有很多应用实例，其中就包括一个决策树算法模型的案例。此示例使用名为 druglearn.str 的流，此流引用名为 DRUG1n 的数据文件。这些文件可在任何 IBM SPSS Modeler 安装程序的 Demos 目录中找到。操作步骤如下：
添加&变量文件&节点 GRUGln，打开该节点，添加 DRUGln 文件。
创建新字段 Na_to_K, 通过对 Na 和 K 数据的观察，发现可以用 Na 和 K 的比例来预测药物 Y。
添加过滤器 (Discard Fields)，过滤掉原始的字段 Na 和 K，以免在建模算法中重复使用。
添加类型节点 (Define Types)，设置字段的角色，将药物字段设置为目标，其他的字段设置为输入。
添加 C5.0 节点，使用默认的参数设置。
点击运行，生成一个模型 Drug，如下图所示。
图 15. 模型流图
在生成模型 Drug 以后，我们可以在模型页面中浏览 Drug 模型。打开 Drug 模型以后，可在规则浏览框中以决策树形式显示 C5.0 节点所生成的规则集。还可以通过更复杂的图表形式查看同一决策树。如下图所示：
图 16. 生成模型的决策树图
本文主要通过一个决策树的典型案例，着重从特征选择、剪枝等方面描述决策树的构建，讨论并研究决策树模型评估准则，最后基于 R 语言和 SPSS 这两个工具，分别设计与实现了决策树模型的应用实例。通过较多的统计学公式和案例图表，生动地展示了一棵决策树是如何构建并将其应用到实际场景中去的。
本文也展开讨论了分类算法之间的相互比较和优缺点，特征选择与剪枝各种方法之间的相互比较，各个评估方法的优缺点等。通过这些讨论与分析，能够以更好的方法论来解决实际生产环境下的问题。
同时，决策树只是整个机器学习领域的冰山一角，而机器学习领域又是当前大数据分析领域的热点，因此还有很多很多值得我们去学习、去研究的地方。
参考资源 (resources)
参考，了解更多机器学习的概念知识。
查看文章&&，了解更多机器学习中的算法分类。
查看文章&&，了解更多基于 R 对实际案例的应用。
from:&/developerworks/cn/analytics/library/ba-1507-decisiontree-algorithm/index.html}