决策树法
1、决策树模型与学习
1.1、决策树模型
分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点和有向边组成。结点分为两种，内部结点和叶子结点；内部结点表示一个特征或者属性；叶子结点表示一个类。
用决策树分类，从根结点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点上。这时每一个子结点对应于该特征的一个取值。如此递归对实例进行测试并分配。直到到达叶结点，最后将实例分到叶结点的实例中。 
上图是一个决策树的示意图，图中圆圈表示内部结点，方框表示叶结点。
1.2、决策树与if-then规则
可以将决策树看成一个if-then规则的集合，其规则是：由决策树的根结点到叶结点的每一条路径构建一天规则；路径上内部结点的特征对应着规则的条件，而叶结点对应着规则的结论。决策树路径或者其对应的if-then规则集合具有一个重要的性质。互斥并且完备。
1.3、决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布，这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或者区域，并在每个单元上定义了一个类的概率分布就构成了条件概率分布。决策树的一条路径对应于划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X表示特征的随机变量，Y表示类的随机变量；那么这个条件概率分布可以表示为P（Y|X）,X取值于给定划分的单元的集合。Y取值于类的集合。各叶结点（单元）上的条件概率往往偏向某一个类，即属于某一类概率大。决策树分类时将该结点的实例强行分到条件概率大的哪一类去。
1.4、决策树学习
假设给定训练数据集 
其中x_i=〖(x_i^1,x_i^2,⋯,x_i^n)〗^T为输入实例（特征向量），n为特征个数，y_i∈{1,2,⋯,K}是类标记，i=1,2,⋯,N, N是样本容量。学习的目的是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确分类。
决策树学习的本质就是从训练集数据归纳出一组分类的规则。与训练集不相矛盾的决策树（即能对训练进行正确分类的决策树）可能有多个，也可能一个没有。我们需要一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
决策树学习的算法通常是一个递归选择最优特征，并根据该特征对训练数据集进行划分，使得对各个子数据集有一个最好的分类的过程，这一过程对应着特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有数据都放在根结点上，选择一个最优的特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去。如果还有子集不能正确分类，就对这些子集选择新的最优特征，继续分割，如此递归下去，知道所有训练数据子集都正确的分类，或者没有适合的特征为止。这样就构成了一颗决策树。
以上方法对训练数据集有很好的分类能力，但是容易发生过拟合现象（也就是测试数据集未必能很好的分类）。这个时候我们需要对已生成的决策树进行自下而上的剪枝，去掉过于细化的叶结点。决策树常用的算法有ID3、C4.5、CART。
2、特征选择
2.1、特征选择问题
特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习效率。通过特征选择的准则是信息增益或信息增益比。
2.2、信息增益
熵于条件熵定义：在信息论与概率统计中，熵是表示随机变量的不确定性的度量。设X是一个取有限值的离散随机变量，其概率分布为： 
则随机变量X的熵定义为： 
若p_i=0则定义0log0=0。式中对数以2或者e为底部，这时熵的单位分别称为比特（bit）和纳特（nat）。由定义可知，熵只依赖于X的分布，不依赖X的取值，所以上式可以写成。 
熵越大，随机变量的不确定性也大。同时0≤H(P)≤log(n)。
熵于概率变化曲线如图： 
设有随机变量（X, Y）其联合概率分布为： 
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。H(Y|X)定义为X给定条件下，Y的条件概率分布熵对X的数学期望。 
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益是g(D, A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差即：
g(D, A)= H(D) - H(D|A)
一般地，熵H(X)与条件熵H(Y|X)之差称为互信息，决策树学习中的信息增益等价于训练数据中类与特征的互信息。
决策树学习应用信息增益准则选择特征，给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A给定条件下对数据集D进行分类不确定性。那么他们之间差即信息增益就表示由于特征A而使得对数据集D的分类不确定性减少的程度。
根据信息增益准则的特征选择方法是：对训练数据集（或者子集）D，计算其每个特征的信息增益，并比较他们的大小。选择信息增益最大的特征。
- 信息增益算法：
输入：训练数据集D和特征A;
输出：特征A对训练数据集D的信息增益g(D，A)
2.3、信息增益比
信息增益比的大小是相对于训练数据集而言的，并没有绝对的意义。在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值就会偏大。反之信息增益值会偏小。使用信息增益比可以对这个问题进行校正。
信息增益比：特征A对训练数据集D的信息增益比定义为其信息增益g(D，A)与训练数据集D的经验熵H(D)之比： 
3、决策树的生成
3.1、ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归构建决策树。具体方法：从跟结点开始，对结点计算所有可能的特征信息增益，选择信息增益最大的特征作为结点特征。由该特征的不同取值建立子结点；再对子结点递归调用以上方法，构建决策树；直到所有特征的信息增益均很小或者没有特征可以现在为止。最后得到一个决策树。ID3算法相当于用极大似然法进行概率模型的选择。
- ID3算法：
输入：训练数据集D， 特征集A， 阈值ε。
输出：决策树T。
3.2、C4.5算法
C4.5算法与ID3算法类似，C4.5算法对ID3算法进行了改进，C4.5算法生成过程中，利用的是信息增益比来选择特征。
- C4.5算法：
输入：训练数据集D， 特征集A， 阈值ε。
输出：决策树T。 
4、决策树剪枝
前面提到决策树容易产生过拟合现象。为此我们需要对其剪枝处理。剪枝是从已生成的树上裁掉一些子树或子结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。
决策树剪枝往往是通过极小化决策树整体的损失函数（代价函数）来实现的。设树T有叶结点个数为|T|，t是树T的叶结点，该叶结点有N_t个样本点，其中k类样本点数有个N_tk，k=1,2,⋯,K。为叶结点t上的经验熵。a≥0为参数，则决策树学习的损失函数可以定义为： 
在损失函数中， 
表示模型对训练数据的预测误差，即模型与训练数据的拟合程度。|T|为模型复杂度α≥0控制两者之间的影响。较大的α促使选择较简单的模型树，较小的α促使选择较复杂的模型树。α=0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
剪枝就是α当确定时，选择损失函数最新的模型。当α确定，子树越大，往往训练数据拟合越好。但是模型的复杂度就越高；相反，子树越小，往往与训练数据的拟合就越低，但是往往与训练数据拟合不好，损失函数正好表示两者的平衡。
- 剪枝算法
输入：生成的树模型T，参数α
输出：修剪后树模型T_α。
5、CART算法
CART(classification and regression tree)算法同样由特征选择、树生成、剪枝组成。既可以用于分类也可以用于回归。
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布学习方法。CART假设决策树是二叉树，内部结点特征取值为“是”和“否”，左边分支取“是”，右边分支取“否”。
CART算法有两步：
（1） 决策树生成：基于训练数据集生成决策树，生成决策树要尽量大；
（2） 决策树剪枝：用验证数据集对已经生成的决策树进行剪枝，并选择最优子树，这时用损失函数最小作为剪枝的标准。
5.1、CART生成
决策树生成就是递归构建二叉决策树的过程。对于回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择生成二叉决策树。
回归树生成
假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集
考虑如何生成回归树。
一个回归树对应着输入空间（即特征空间）的一个划分以及在划分单元上的输出值。假设已将输入空间划分为M个单元R_1,R_2⋯,R_M，并且在每个单元R_m上有固定的输出值c_m，于是回归树模型可表示为：
当输入空间划分确定时，可以用平方误差∑_(x_i∈R_M)[(y_i-f(x_i ))]^2 来表示回归树对于训练数据的预测误差。单元R_m上c_m的最优值c ̂_m是R_m上所有输入实例x_i对应输出y_i的均值。
对输入空间划分：
选择第j个变量x^j和它的取值s，作为切分变量和切分点。并定义两个区域：
然后寻找最优切分变量j和最优切分点s。具体的求解：
对于固定输入变量j可以找到最优切分点s。
遍历所有的输入变量，找到最优的切分变量j构成一个对（j, s），依次将输入空间划分为两个区域。接着对每个区域重复上述划分过程。知道满足停止条件位置。这样就生成了一颗回归树，这样的回归树通常称为最小二乘回归树。
最小二乘回归树算法：
输入：训练数据集D;
输出：回归树f(x)
在训练数据集所在输入空间中，递归地将每个区域划分为两个子区域并决定每个区域上输出值，构建二叉决策树；
分类树生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
基尼指数：
分类问题中，假设有K个类，样本点属于第K类概率p_k，则概率分布的基尼指数定义为：
对于二类分类问题，若样本点属于第1类的概率为p，则概率分布的基尼指数为：Gini（p）=2p(1-p)
对于给定的样本集合D，其基尼指数为：
这里C_k是D中属于第k类样本子集，K是类个数。
如果样本集合D根据特征A是否取某一可能值a被分割和两部分，即
则在特征A的条件下，集合D的基尼指数定义为：
Gini(D)基尼指数表示集合D的不确定性，基尼指数Gini(D,A)表示A=a分割后集合D的不确定性，基尼指数越大，样本集合的不确定性就越大。这点和熵类似。
CART生成算法：
输入：训练数据集D，停止计算条件；
输出：CART决策树。
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树。
5.2、CART剪枝
CART剪枝算法是从“完全生长”的决策树低端剪去一些子树，使决策树变小（模型变简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成；首选从生成算法产生的决策树低端开始不断剪枝，直到的根结点，形成一个子树序列{T_1,T_2,⋯T_n}；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
在剪枝过程中计算子树的损失函数： 
其中，T为任意子树，C(T)为对训练数据集的预测误差（如基尼指数），|T|为子树的叶结点个数，α≥0为参数。C_α (T)为参数时的子树T的整体损失。参数α权衡训练数据的拟合程度与模型复杂度。
对于固定的α，一定存在使损失函数C_α (T)最小的子树，将其表示为T_α。T_α在损失函数C_α (T)最小的意义下是最优的。当α很大的时候，最优子树T_α偏小，当α很小的时候，最优子树T_α偏大。极端情况α=0时，整体树是最优的，α=+∞根结点组成的单结点树是最优的；具体的： 
CART剪枝算法：
输入：CART算法生成的二叉决策树T_0；
输出：最优决策树T_α。
6、总结
决策树是一种实例分成树型结构的分类器，主要有ID3算法、C4.5算法、CART算法。他们都是通过选择最优特征来进行分类，ID3算法使用的信息增益最大，C4.5算法使用的信息增益比最大，CART算法使用的基尼指数最小来确定最优特征。信息增益和信息增益比引入了熵的概念，熵是描述不确定性的概念，通过熵来描述信息增益和信息增益比。这三种算法生成的决策树都容易产生过拟合。因此引用了剪枝方法来去除过拟合，剪枝主要判断条件是通过剪枝前后损失函数大小进行比较，通过迭代，当某一个枝被剪去后，损失函数最小，则就剪去该枝。