分类算法
将决策树之前，首先提一下分类问题。在机器学习中，预测问题是一类很重要的问题。所谓预测，就是根据一些特征的取值，去推断它可能的标记。例如，根据一家公司的经营情况，财务数据，资本实力等特征，去预测这家公司是否会在贷款后违约，以此帮助银行作出相应的决策。
在预测问题中，如果标记是连续值，那么该问题是一个回归问题；如果标记是离散值，那该问题是分类问题；如果标记为空值，那就可能是一个聚类问题。此外，根据有无标记，又可以分为监督学习（有标记）和无监督学习（无标记）。
所谓分类，就是利用训练数据集通过一定的算法模型而得到分类规则，也就是得到一个，其中
是一个样本的特征向量，也就是各个特征的取值。
则是输出的结果，考虑到这是分类问题，所以
一般取成离散值。而
，就是我们的想要得到的分类规则。
常见的分类算法有决策树算法、贝叶斯&朴素贝叶斯、支持向量机、逻辑回归、神经网络等等。本篇文章我们对决策树进行介绍。
决策树的构建
这是一个基本的决策树模型，是已经求解出的规则。当我们拿出一个新的西瓜，想要判断它是不是好瓜时，我们就需要从上往下去进行判断。它的纹理怎么样？如果纹理模糊，我们就推测他是一个坏瓜；如果纹理稍微模糊一些，我们再去看看触感；如果纹理很清晰，我们就去看看根蒂怎么样。一步步往下走，我们就可以得到最终的预测结果。
所以问题来了，这棵树是怎么构造出来的？为什么要先看它的纹理，为什么纹理清晰后要看根蒂，纹理稍糊要看触感而纹理模糊就直接判断是坏瓜呢？
这就涉及到决策树学习的关键问题，如何选择划分枝干的最优属性。
我们希望划分后，会有怎样的效果呢？显然，我们希望在不断地划分过程中，可以使得每一个分支节点所包含的样本尽可能属于同一类别，节点的纯度越来越高。
例如上面的决策树，倘若我们从样本数据中发现，所有触感硬滑的都是好瓜，所有触感软滑的都是坏瓜，那我们何必把纹理当作第一个判断属性呢？直接判断触感就可以区分出好瓜坏瓜了。
因此，我们可以认为，选择划分属性的一个重要标准，就是它可以尽可能地使相应分出去的节点所包含的样本，具有一样的类别，具有更高的纯度。
那如何来衡量这种纯度呢？
我们使用熵，来衡量这种纯度。
信息熵
信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合中第
类样本所占的比例为
，则
的信息熵定义为
其中是标记的取值个数。同时我们约定，
时，
。
此时，当某一个，而其他的
时，该样本集合的纯度最高（只存在一种标记）而熵
达到最小。当所有的
时，样本集合的纯度最低（此时等比例的存在所有标记）而熵
达到最大。
由上面的例子我们可以知道，当样本集合的熵越大，说明样本集合纯度越低；熵越小，其纯度越高。当我们推广到一棵树上，我们有理由认为，如果我们每一步都选择使系统的熵降低最多的属性，相应的叶子节点的纯度会更高，我们也就能更快而准确的作出预测。
于是，我们引入了信息增益的概念。
信息增益和属性选择
假定离散属性有
个不同的取值
，如果使用
这一属性对样本集
进行划分，则会产生
个分支节点。其中第
个节点包含了
中所有属性
上取值为
的样本，记为
。我们可以根据上面的公式，计算出
的信息熵
。
考虑到每一个分支节点所包含的样本数目不同，给每个分支节点赋予权重，
表示集合
中的样本数目。这样，样本数越多的分支节点的影响力越大，我们便可以计算出根据属性
对样本集
进行划分后所得到的信息增益
即信息熵的减少量。而就是集合
根据属性
划分后，相应的子树的信息熵。
如上文所述，我们需要选择的用于划分的属性，就是使得信息熵减小最多的属性，这样子叶结点的整体纯度会更高。因此，我们需要计算出所有属性的信息增益，选择信息增益最大的属性作为划分依据。
基本算法
接下来简单描述一下构造决策树的基本算法（贪心）。
Step 1：所有的数据都在根节点，属性都是种类字段（连续属性离散化）。
Step 2：计算所有属性的信息增益，选择信息增益最大的进行划分，生成相应的叶子节点
Step 3：在达到终止条件之前，不断重复第二步，对叶子节点进行划分
那算法的终止条件是什么呢？
一般而言，如果一个叶子节点包含的所有样本都属于同一类，则不需要继续划分了。如果当前的数据集没有任何属性可用于划分，但依然不完全纯净，那按照少数服从多数的原则设定其标记值，并停止划分。如果分到某个节点时，某个值（例如纯度）达到了给定的阈值，则停止划分，设定标记值。
举个例子
对于上述数据集，我们首先计算总体样本的熵。可以发现，
，所以
下面我们来计算一下，使用“色泽”作为划分属性的信息增益。色泽这一属性有三个取值，所以相应的集合被划分为。
代表色泽为青绿，包含六个样例
。其中正例有3个，负例有3个，所以其信息熵
代表色泽为乌黑，包含六个样例
。其中正例有4个，负例有2个，所以其信息熵
代表色泽为浅白，包含五个样例
。其中正例有1个，负例有4个，所以其信息熵
所以其信息增益
同理可得，,
,
,
,
。显然，“纹理”的信息增益最大，所以将纹理作为第一个用于划分的属性。
接着，对于纹理分出的三个叶结点继续进行划分，选择信息增益最大的属性作为划分依据，不断迭代，最终得到一棵完整的决策树。
其他选择属性的依据
信息增益固然适合作为选择属性的依据，但是倘若我们把每一个样本的编号也看作一个属性，会发现它的信息增益最大。因为这样就划分出了十七个叶结点，且每个叶结点都是具有100%纯度的。显然，即使我们训练出了这样的树，对于一个新的样本，我们是难以作出有效的预测的。
可以发现，信息增益这一指标，更加偏爱取值较多的属性，有时候很难得到一棵泛化能力较强的决策树。
因此，我们可以引入其他指标作为选择属性的依据，如信息增益率、基尼系数等等。此处仅作为一个引入，有兴趣的自行查阅。
剪枝
剪枝也是一个构造决策树过程中不可缺少的一个步骤，分为预剪枝和后剪枝。剪枝的目的是提高决策树的泛化能力，这里暂时不做详细介绍，以后有机会再谈。
优缺点
最后提一下决策树的优缺点。
优点：
- 可以生成可理解的规则，具有较强的解释性
- 计算量相对而言不是很大
- 可以处理连续和种类字段，对数据要求不高
- 决策树可以清晰的显示哪些字段比较重要
缺点：
- 对连续性的字段较难预测
- 对于有时间顺序的数据，需要做很多预处理
- 当类别太多时，错误可能增加的比较快
- 一次只能根据一个字段分类
