决策树（decision tree）是一种依托于策略抉择而建立起来的树。机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。 树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，从根节点到叶节点所经历的路径对应一个判定测试序列。决策树可以是二叉树或非二叉树，也可以把他看作是 if-else 规则的集合，也可以认为是在特征空间上的条件概率分布。决策树在机器学习模型领域的特殊之处，在于其信息表示的清晰度。决策树通过训练获得的 “知识”，直接形成层次结构。这种结构以这样的方式保存和展示知识，即使是非专家也可以很容易地理解。

决策树的优点：

决策树的缺点：

一棵“树”，目的和作用是“决策”。一般来说，每个节点上都保存了一个切分，输入数据通过切分继续访问子节点，直到叶子节点，就找到了目标，或者说“做出了决策”。举个例子： 现在有人给你介绍对象，你打听到对方的特点：白不白，富不富，美不美，然后决定去不去相亲。根据以往经验，我们给出所有可能性：

有人给介绍新的对象的时候，我们就要一个个特点去判断，于是这种判断的过程就可以画成一棵树，例如根据特点依次判断：

这就是决策树，每一层我们都提出一个问题，根据问题的回答来走向不同的子树，最终到达叶子节点时，做出决策（去还是不去）。可以看到，决策树没有任何特别的地方。

当然，如果我们先考虑富不富，再考虑白不白，则得到的树又不相同：

所以，决策树其实就是根据已知的经验来构建一棵树。可以认为是根据数据的某个维度进行切分，不断重复这个过程。当然，如果切分的顺序不同，会得到不同的树。

如果仔细观察，我们发现决策树中有一些叶子节点是可以合并的，合并之后，到达某个节点时就不需要进行额外的决策，例如切分顺序“白，富，美”得到的决策树合并后如下：

而“富，白，美”的决策树合并后变成

可以看到上面这棵树则只有 4 个叶子节点，少于“白，富，美”的 5 个节点。这就是决策树间最大的区别，不同决策树合并后得到树叶子节点的个数是不同的，后面我们会看到，叶子节点越少，往往决策树的泛化能力越高，所以可以认为训练决策树的一个目标是减少决策树的叶子节点 。

ID3是由J.Ross Quinlan在1986年开发的一种基于决策树的分类算法。该算法是以信息论为基础，以信息熵核信息增益为衡量标准，从而实现对数据的归纳分类。根据信息增益运用自顶向下的贪心策略是ID3建立决策树的主要方法。运用ID3算法的主要优点是建立的决策树的规模比较小，查询速度比较快。这个算法建立在“奥卡姆剃刀”的基础上，即越是小型的决策树越优于大的决策树。但是，该算法在某些情况下生成的并不是最小的树型结构。

信息量

信息量在是作为信息“多少”的度量，这里的信息就是你理解的信息，比如一条新闻，考试答案等等。假设我们听到了两件事，分别如下：

仅凭直觉来说，事件B的信息量比事件A的信息量要大。究其原因，是因为事件A发生的概率很大，事件B发生的概率很小。所以当越不可能的事件发生了，我们获取到的信息量就越大。越可能发生的事件发生了，我们获取到的信息量就越小。那么：

如已知事件Xi已发生，则表示Xi所含有或所提供的信息量：

如果是以2为底数，单位是bit；如果以e为底数，单位是nat；如果以10为底数，单位是det；

例如，今天下雨的概率是0.5，则包含的信息量为

比特；同理，下雨天飞机正常起飞的概率为0.25，则信息量为

比特。

信息熵

信息熵（Entropy）是接受信息量的平均值，用于确定信息的不确定程度，是随机变量的均值。信息熵越大，信息就越凌乱或传输的信息越多，熵本身的概念源于物理学中描述一个热力学系统的无序程度。信息熵的处理信息是一个让信息的熵减少的过程。

假设X是一个离散的随机变量，且它的取值范围为

，每一种取到的概率分别是

，那么 X 的熵定义为:

条件熵

在决策树的切分里，事件

可以认为是在样本中出现某个标签/决策。于是

可以用所有样本中某个标签出现的频率来代替。但我们求熵是为了决定采用哪一个维度进行切分，因此有一个新的概念条件熵：

这里我们认为 Y 就是用某个维度进行切分，那么 y 就是切成的某个子集合于是 H(X|Y=y) 就是这个子集的熵。因此可以认为就条件熵是每个子集合的熵的一个加权平均/期望。

信息增益

信息熵表示的是不确定度。均匀分布时，不确定度最大，此时熵就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益（Kullback-Leibler divergence）用于度量属性A对降低样本集合X熵的贡献大小。信息增益可以衡量某个特征对分类结果的影响大小。信息增益越大，越适用对X进行分析。

有了信息熵的定义后，信息增益的概念便很好理解了，表示分类后，数据整体信息熵的差值。我们假设特征集中有一个离散特征a，它有V个可能的取值

,如果使用特征

来对样本

进行划分，那么会产

个分支节点，其中第

个分支节点中包含的样本集。我们记为

。于是，可计算出特征

对样本集

进行划分所获得的信息增益为：

解释下上面公式，其实特征a对样本集D进行划分所获得的信息增益 即为 样本集D的信息熵减去经过划分后各个分支的信息熵之和。由于每个分支节点，所包含的样本数不同，所有在计算每个分支的信息熵时，需要乘上对应权重

,即样本数越多的分支节点对应的影响越大。

ID3算法流程

输入：数据集D，特征集A

输出：ID3决策树

ID3算法的应用

我们以实际案例来更加深入的学习整个算法流程。

计算过程如下：

ID3算法的Python实现

参考链接：https://segmentfault.com/a/1190000015083169

ID3算法的优点与缺点

ID3算法的优点：

ID3算法简单，但是其缺点也不少：

C4.5是J.Ross Quinlan基于ID3算法改进后得到的另有一个分类决策树算法。C4.5是算法继承了ID3算法的优点，且改进后的算法产生的分类规则易于理解，准确率高。同时，该算法也存在一些缺点，如算法效率低，值适合用于能够驻留于内存的数据集。正在ID３算法的基础上，C4.5算法进行了以下几点改进：

以信息增益作为准则来进行划分属性有什么缺点？假设有14个样本的数据，增加一列特征data = [1,2,3,4,5,6,7,8,9,10,11,12,13,14]，根据公式，可以算出对应的信息增益为：Gain(D,data) = 0.940, 我们发现，它所对应的信息增益远大于其他特征，所以我们要以data特征，作为第一个节点的划分。这样划分的话，将产生14个分支，每个分支对应只包含一个样本，每个分支节点的纯度已达到最大，也就是说每个分支节点的结果都非常确定。但是，这样的决策树，肯定不是我们想要的，因为它根本不具备任何泛化能力。如何避免这个问题呢，我们引入增益率这个概念，改为使用增益率来作为最优划分特征的标准。

信息增益率

C4.5算法应用实例

C4.5算法Python实现

参考链接：https://github.com/Rudo-erek/decision-tree/blob/master/decisionTreeC45.py

在数据挖掘中，决策树主要有两种类似：分类树和决策树。分类树的输出是样本的类别，回归树的输出是一个实数。分类和回归树，即CART（Classification And Regression Tree）,最先由Breiman等提出，也属于一类决策树。CART算法由决策树生成和决策树剪枝两部分组成：

CART算法既可以用于创建分类树，也可以用于创建回归树。CART算法的重要特点包含以下三个方面：

ID3、C4.5、CART之间的区别

基尼指数

其中算法的停止条件有：

应用实例：决策划分

针对上述离散型数据，按照体温为恒温和非恒温进行划分。其中恒温时包括哺乳类5个、鸟类2个，非恒温时包括爬行类3个、鱼类3个、两栖类2个，如下所示我们计算D1,D2的基尼指数。

然后计算得到特征体温(A1)下数据集的Gini指数，最后我们选择Gain_Gini最小的特征和相应的划分。

CART算法Python实现