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

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

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

机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。

数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。

从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

一个决策树包含三种类型的节点：

决策节点：通常用矩形框来表示。
	是对几种可能方案的选择，即最后选择的最佳方案。
	如果决策属于多级决策，则决策树的中间可以有多个决策点，
	以决策树根部的决策点为最终决策方案。
机会节点：通常用圆圈来表示。
	代表备选方案的经济效果（期望值），
	通过各状态节点的经济效果的对比，
	按照一定的决策标准就可以选出最佳方案。
	由状态节点引出的分支称为概率枝，
	概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。
终结点：通常用三角形来表示。
	将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。

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

决策树同时也可以依靠计算条件概率来构造。

剪枝是决策树停止分支的方法之一，剪枝有分预先剪枝和后剪枝两种。

预先剪枝是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生“视界局限”，就是一旦停止分支，使得节点N成为叶节点，就断绝了其后继节点进行“好”的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法，导致产生的树不纯度降差最大的地方过分靠近根节点。

后剪枝中树首先要充分生长，直到叶节点都有最小的不纯度值为止，因而可以克服“视界局限”。然后对所有相邻的成对叶节点考虑是否消去它们，如果消去能引起令人满意的不纯度增长，那么执行消去，并令它们的公共父节点成为新的叶节点。这种“合并”叶节点的做法和节点分支的过程恰好相反，经过剪枝后叶节点常常会分布在很宽的层次上，树也变得非平衡。

后剪枝技术的优点是克服了“视界局限”效应，而且无需保留部分样本用于交叉验证，所以可以充分利用全部训练集的信息。但后剪枝的计算量代价比预剪枝方法大得多，特别是在大样本集中，不过对于小样本的情况，后剪枝方法还是优于预剪枝方法的。

优点

1. 决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。
2. 对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
3. 易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。

缺点

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

决策树基本上就是把我们以前的经验总结出来。

如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？


在这里我们先介绍两个指标：纯度和信息熵。

你可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上，我们可以用纯度来表示，纯度换一种方式来解释就是让目标变量的分歧最小。

举个例子，假设有 3 个集合：

集合 1：6 次都去打篮球；
集合 2：4 次去打篮球，2 次不去打篮球；
集合 3：3 次去打篮球，3 次不去打篮球。
按照纯度指标来说，集合 1> 集合 2> 集合 3。因为集合1 的分歧最小，集合 3 的分歧最大。

表示信息的不确定度

在信息论中，随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性，信息学之父香农引入了信息熵的概念，并给出了计算信息熵的数学公式：

p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数。存在一种度量，它能帮我们反映出来这个信息的不确定度。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。

举个例子，假设有 2 个集合：

• 集合 1：5 次去打篮球，1 次不去打篮球；
• 集合 2：3 次去打篮球，3 次不去打篮球。

在集合 1 中，有 6 次决策，其中打篮球是 5 次，不打篮球是 1 次。那么假设：类别 1 为“打篮球”，即次数为 5；类别 2 为“不打篮球”，即次数为 1。那么节点划分为类别1的概率是 5/6，为类别2的概率是1/6，带入上述信息熵公式可以计算得出：

同样，集合 2 中，也是一共 6 次决策，其中类别 1 中“打篮球”的次数是 3，类别 2“不打篮球”的次数也是 3，那么信息熵为多少呢？我们可以计算得出：

从上面的计算结果中可以看出，信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低。

我们在构造决策树的时候，会基于纯度来构建。而经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）。

信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。在计算的过程中，我们会计算每个子节点的归一化信息熵，即按照每个子节点在父节点中出现的概率，来计算这些子节点的信息熵。所以信息增益的公式可以表示为：

公式中 D 是父亲节点，Di 是子节点，Gain(D,a)中的 a 作为 D 节点的属性选择。

假设D 天气 = 晴的时候，会有 5 次去打篮球，5 次不打篮球。其中 D1 刮风 = 是，有 2 次打篮球，1 次不打篮球。D2 刮风 = 否，有 3 次打篮球，4 次不打篮球。那么a 代表节点的属性，即天气 = 晴。

针对图上这个例子，D 作为节点的信息增益为：

也就是 D 节点的信息熵 -2 个子节点的归一化信息熵。2个子节点归一化信息熵 =3/10 的 D1 信息熵 +7/10 的 D2 信息熵。

我们基于 ID3 的算法规则，完整地计算下我们的训练集，训练集中一共有 7 条数据，3 个打篮球，4 个不打篮球，所以根节点的信息熵是：

如果你将天气作为属性的划分，会有三个叶子节点 D1、D2 和D3，分别对应的是晴天、阴天和小雨。我们用 + 代表去打篮球，- 代表不去打篮球。那么第一条记录，晴天不去打篮球，可以记为 1-，于是我们可以用下面的方式来记录 D1，D2，D3：

D1(天气 = 晴天)={1-,2-,6+}
D2(天气 = 阴天)={3+,7-}
D3(天气 = 小雨)={4+,5-}

我们先分别计算三个叶子节点的信息熵：

因为 D1 有 3 个记录，D2 有 2 个记录，D3 有2 个记录，所以 D 中的记录一共是 3+2+2=7，即总数为 7。所以 D1 在 D（父节点）中的概率是 3/7，D2在父节点的概率是 2/7，D3 在父节点的概率是 2/7。那么作为子节点的归一化信息熵 = 3/70.918+2/71.0=0.965。

因为我们用 ID3 中的信息增益来构造决策树，所以要计算每个节点的信息增益。

天气作为属性节点的信息增益为，Gain(D , 天气)=0.985-0.965=0.020。

同理我们可以计算出其他属性作为根节点的信息增益，它们分别为：

Gain(D , 温度)=0.128
Gain(D , 湿度)=0.020
Gain(D , 刮风)=0.020

我们能看出来温度作为属性的信息增益最大。因为 ID3 就是要将信息增益最大的节点作为父节点，这样可以得到纯度高的决策树，所以我们将温度作为根节点。其决策树状图分裂为下图所示：

然后我们要将上图中第一个叶节点，也就是 D1={1-,2-,3+,4+}进一步进行分裂，往下划分，计算其不同属性（天气、湿度、刮风）作为节点的信息增益，可以得到：

Gain(D , 天气)=0
Gain(D , 湿度)=0
Gain(D , 刮风)=0.0615

我们能看到刮风为 D1 的节点都可以得到最大的信息增益，这里我们选取刮风作为节点。同理，我们可以按照上面的计算步骤得到完整的决策树，结果如下：

于是我们通过 ID3 算法得到了一棵决策树。ID3 的算法规则相对简单，可解释性强。同样也存在缺陷，比如我们会发现ID3 算法倾向于选择取值比较多的属性。这样，如果我们把“编号”作为一个属性（一般情况下不会这么做，这里只是举个例子），那么“编号”将会被选为最优属性 。但实际上“编号”是无关属性的，它对“打篮球”的分类并没有太大作用。

所以 ID3 有一个缺陷就是，有些属性可能对分类任务没有太大作用，但是他们仍然可能会被选为最优属性。这种缺陷不是每次都会发生，只是存在一定的概率。在大部分情况下，ID3 都能生成不错的决策树分类。针对可能发生的缺陷，后人提出了新的算法进行改进。

因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵

当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。

ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。

悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。

C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，C4.5 选择具有最高信息增益的划分所对应的阈值。

针对数据集不完整的情况，C4.5 也可以进行处理。

假如我们得到的是如下的数据，你会发现这个数据中存在两点问题。第一个问题是，数据集中存在数值缺失的情况，如何进行属性选择？第二个问题是，假设已经做了属性划分，但是样本在这个属性上有缺失值，该如何对样本进行划分？

我们不考虑缺失的数值，可以得到温度 D={2-,3+,4+,5-,6+,7-}。温度 = 高：D1={2-,3+,4+}；温度 = 中：D2={6+,7-}；温度 = 低：D3={5-} 。这里 + 号代表打篮球，- 号代表不打篮球。比如ID=2 时，决策是不打篮球，我们可以记录为 2-。

所以三个叶节点的信息熵可以结算为：

这三个节点的归一化信息熵为 3/60.918+2/61.0+1/6*0=0.792。

针对将属性选择为温度的信息增益率为：
Gain(D′, 温度)=Ent(D′)-0.792=1.0-0.792=0.208
D′的样本个数为 6，而 D 的样本个数为 7，所以所占权重比例为 6/7，所以 Gain(D′，温度) 所占权重比例为6/7，所以：
Gain(D, 温度)=6/7*0.208=0.178

这样即使在温度属性的数值有缺失的情况下，我们依然可以计算信息增益，并对属性进行选择。

首先 ID3 算法的优点是方法简单，缺点是对噪声敏感。训练数据如果有少量错误，可能会产生决策树分类错误。C4.5 在 IID3 的基础上，用信息增益率代替了信息增益，解决了噪声敏感的问题，并且可以对构造树进行剪枝、处理连续数值以及数值缺失等情况，但是由于 C4.5 需要对数据集进行多次扫描，算法效率相对较低。