决策树是一个非常简单的算法，至少其思想是非常简单的。生活中我们经常会使用，看几个例子。
场景1，母亲给女儿介绍男朋友，下面是二人的对话：

女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。

女儿通过年龄、长相、收入、是否是公务员将男人分为两个类别：见和不见。女孩选择见或不见的过程就是决策树决策的过程。假设女孩对男朋友的要求是：30岁以下、长相中等以上、高收入者或者中等收入以上的公务员。我们可以构造如下一个决策树：

其中，绿色节点表示判断条件，蓝色节点（叶子节点）表示决策结果，左右箭头称作分支。过去的专家系统往往就使用决策树。

再看一个例子，平面上有一些点，我们需要找到一个函数（曲线）把它们分开。如果是线性可分的情况，直觉上我们会画一条直线来切分平面，它的方程与x,y两个属性均有关，可以表示为：

而对于决策树，通常每次决策（平面划分）只与一个特征相关（x或y）。也就是说，我们只能画水平或竖直的线：

决策树同样适用于线性不可分的情况（并非最优划分）：

接下来，我们使用下面的数据集看下构造决策树的一些关键点。该数据集有2个特征：f1和f2，然后label是是否属于鱼类，共5条样本：

如何构造根据f1、f2两个特征判断是否属于鱼类的决策树？下面是2种可能的决策树：

哪个更好？为什么？构造决策树时，需要确定在哪个特征/属性上面划分数据集，我们称该属性为分裂属性。如何确定分裂属性？

大原则：划分后，让无序数据变得更加有序。

那如何评估数据的有序程度呢？有两种：信息增益（Information Gain）和基尼不纯度（Gini Impurity）。

我们平时说“xxx事情包含的信息量很大”，直观感受就是这个事情的不确定性很大。其实有专门一门学科是专门研究信息的：信息论（这个课还是我大学时的专业课，当时觉得太理论，没什么意思，现在…唉）。这个学科的创始人香农（Claude Elwood Shannon）提出了量化一个系统包含信息量多少的概念——熵（Entropy），单位是比特（bit），它衡量的是随机变量的不确定性。其定义如下：

如果有一个系统S内存在多个事件S=E1,…,EnS=E1,…,En，每个事件的概率分布P=p1,…,pnP=p1,…,pn，则每个事件本身的信息为（单位是bit）：Ie=−log2piIe=−log2pi。
​

熵是信息的期望值，即整个系统的平均信息量：Hs=∑ni=1piIe=−∑ni=1pilog2piHs=∑i=1npiIe=−∑i=1npilog2pi

举个例子，比如英语有26个字母，如果每个字母在文章中出现的次数均等的话，则在这篇文章中每个字母的信息量为：Ie=−log2126=4.7Ie=−log2126=4.7。整个文章的熵为：Hs=∑26i=1126∗4.7=126∗4.7∗26=4.7Hs=∑i=126126∗4.7=126∗4.7∗26=4.7。因为这里假设每个事件发生概率一样，所以单个事件信息量就等于整个系统的平均信息量。所以，熵描述的其实是随机变量的不确定性。对于确定的系统，熵为0。

那什么是信息增益？这就涉及到条件熵的概念：条件熵——在一个条件下，随机变量的不确定性。而信息增益就是“熵 – 条件熵”。表示在一个条件下，信息不确定性减少的程度。放到决策树这里，就是当选用某个特征划分数据集，系统前后信息发生的变化。计算公式为：Gainsplit=H(p)−∑ki=1ninH(i)Gainsplit=H(p)−∑i=1kninH(i)。即使用某个特征（split）划分数据集以后，得到的信息增益为划分前数据集的熵减去划分后的数据集的熵。下面以前面的鱼类为例，看具体如何计算：

划分前整个数据集为：{是，是，否，否，否} ，对应的熵为：H=−25log225−35log235=0.97H=−25log225−35log235=0.97

如果使用特征f1划分数据集，得到两个数据子集：

• f1=是，S1：{是，是，否}，对应的熵为：Hf1=是=−23log223−13log213=0.92Hf1=是=−23log223−13log213=0.92
• f1=否：S2：{否，否}，对应的熵为：Hf1=否=−1log21=0Hf1=否=−1log21=0

所以，按f1划分后获得的信息增益为：

Gainf1=H−(35Hf1=是+25Hf1=否)=0.97−35∗0.92−25∗0=0.42Gainf1=H−(35Hf1=是+25Hf1=否)=0.97−35∗0.92−25∗0=0.42

同理，可以计算按照f2划分数据集以后得到的信息增益为：

Gainf2=H−(45Hf1=是+15Hf1=否)=0.97−45∗1−15∗0=0.17Gainf2=H−(45Hf1=是+15Hf1=否)=0.97−45∗1−15∗0=0.17

通过对比，使用f1划分数据集，获得的信息增益大于使用f2划分，也就是使用f1划分使得系统的不确定性下降的更多，所以使用f1优于f2.

除了信息增益，还有一种常用的评价标准——基尼不纯度（Gini Impurity）：将来自集合中的某种结果随机应用于集合中某一数据项的预期误差率。英文定义是这样的：

Gini impurity (named after Italian mathematician Corrado Gini) is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset.

英文的定义其实更好理解一些，就是你随机从一个集合里面选择一个元素，然后根据这个集合的分布情况随机给这个数据选择一个类别，选择错误可能性的一个描述。维基百科给的计算公式如下：

其中pipi是选中第ii个样本的概率。根据公式可以看到，基尼不纯度的取值范围是[0, 1)。当一个集合完全去定，即里面只有一种元素，则基尼不纯度为0，因为你随机选一个样本，再随机猜一个类别，肯定是不会错的，因为集合里面就只有一种样本；如果一个集合里面全是不同的元素（即混乱程度比较高），则基尼不纯度趋于1，也好理解，你随机选一个样本，随便猜一个种类，因为每个样本都不一样，当n趋于无穷大的时候，猜对的概率几乎为0。所以，不管是信息熵，还是基尼不纯度，衡量的都是一个集合的混乱程度。值越大，越混乱，包含的信息量也越大。对于决策树，使用基尼不纯度和熵的差别非常小：

• 熵对于混乱集合的惩罚略重于基尼不纯度；
• 熵的计算量略大于基尼不纯度。

以二分决策为例，此时p1+p2=1，因此：

对应的曲线图如下：

有了树的划分标准以后，就是根据特征进行递归划分数据集，满足下面任一条件，递归结束：

• 遍历完所有划分数据集的属性
• 每个分支下的所有实例都具有相同的分类

如果遍历完所有属性，类标签仍不唯一，一般采用多数表决的方法决定该叶子节点的分类。

决策树的一个缺点在于很容易过拟合，一般通过剪枝操作来解决改问题，根据剪枝的时机分为两种：

• 预剪枝(prepruning)：在这种方法中，树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长。为了做到这一点，需要采用更具有限制性的结束条件，例如，当观察到的不纯性度量的增益（或估计的泛化误差的改进）低于某个确定的阈值时就停止扩展叶节点。这种方法的优点在于避免产生过分拟合训练数据的过于复杂的子树。然而，很难为提前终止选取正确的阈值。阈值太高将导致拟合不足的模型，而阈值太低就不能充分的解决过拟合的问题。此外，即便使用已有的属性得不到显著的增益，接下来的划分也可能产生较好的子树。
• 后剪枝(postpruning)：在该方法中，初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树。修剪有两种方法：
  • 用新的叶节点替换子树，该叶节点的类标号由子树下记录中的多数类确定。
  • 用子树中最常使用的分支代替子树。当模型不能再改进时终止剪枝步骤。

两种方法各有优劣：与先剪枝相比，后剪枝倾向于产生更好的结果，因为不像先剪枝，后剪枝是根据完全增长的决策树做出的剪枝决策，先剪枝则可能过早终止了决策树的生长。然而，对于后剪枝，当子树被剪掉后，生长完全决策树的额外计算就被浪费了。

目前常见的决策树算法有：

• ID3 (Iterative Dichotomiser 3) ：该算法只能处理标称型数据集。我们之前构造决策树中使用的方法就是ID3算法，该算法使用信息增益作为分裂特征选取的标准。ID3算法可以归纳为以下几点：
  • 使用所有没有使用的属性并计算与之相关的样本熵值
  • 选取其中熵值最小的属性
  • 生成包含该属性的节点
• C4.5：ID3的优化版本，主要有两个优化点：
  • 不仅可以处理标称型数据，还可以处理数值型数据。
  • 使用信息增益率而不是信息增益，改善了分裂特征偏向于具有大量值属性的问题。
• C5.0：C4.5的优化版本，更高效且内存占用更小，但注册了专利，所以使用的比较少。
• CART(Classification and Regression Trees)：CART算法采用一种二分递归分割的技术，算法总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶结点都只有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树。CART算法适用于样本特征的取值为是或非的场景，对于连续特征的处理则与C4.5算法相似。scikit-learn里面使用的就是优化过的CART算法。

其中除了CART使用基尼不纯度外，前面集中都是用的是信息增益作为选择分类属性的标准。下面看scikit-learn中决策树的一个例子：

from sklearn.datasets import load_iris
from sklearn import tree
import graphviz

iris = load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)

dot_data = tree.export_graphviz(clf, out_file=None,
                         feature_names=iris.feature_names,
                         class_names=iris.target_names,
                         filled=True, rounded=True,
                         special_characters=True)
graph = graphviz.Source(dot_data)
graph.render("iris")

复制

上面的代码生成的决策树如下：

目前已经很少有单独使用决策树作为最终算法模型的场景了，一般都会选取基于决策树的更好的集成算法。下面是决策树大致发展过程的一个概括：

后面的文章会介绍这些集成算法。

参考文献：

• Wikipedia: Decision tree learning
• http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
• http://www.jiarui-blog.com/2017/08/10/决策树-1/
• http://www.jiarui-blog.com/2017/08/28/decision-tree-2/
• https://github.com/MangoLiu/mangoliu.github.io/blob/master/机器学习_决策树.md