决策树基本流程
决策树基于树结构来进行决策，其包含一个根节点、若干内部结点和若干叶子结点。叶子结点即是决策结果，其他每个结点对应一个属性测试。其基本流程遵循“分而治之”策略。
决策树的生成是一种递归的过程，以下三种情形会导致递归返回：
1、当前结点包含样本属于同一类，无需划分；
2、当前属性集为空，或者属性集的属性取值都相同，无法划分；
3、当前结点的样本集合为空，无可划分。
对于第2种情形，直接返回当前结点为叶子结点，标记为样本最多的类别；对于第3种情形，则将当前结点作为叶子结点，标记为其父结点所含样本最多的类别。
划分选择
目标：决策树的分支结点尽可能属于同一类别，即结点“纯度”尽可能高。
信息增熵（ID3决策树学习算法）
信息熵：度量样本集合纯度的常用指标。
假定样本集合D中第k类样本所占比例为,则D的信息熵定义为：
.
其值越小，纯度越高。|y|表示最终结果可能取值的个数。
信息增熵：
其中V为离散属性a的可能取值个数，标记为，使用a来对D进行划分，可划出V个结点，于是第v个分支结点包含了D中所有在a上取值为
的样本，可记为
.由上式可见，信息增熵越大，纯度提升越大。
增益率（C4.5决策树算法）
信息增熵对可取值数目较多的属性有所偏好。于是引入增益率来选择最优划分属性，以减少信息增熵的偏好影响。
.
IV(a)被称为属性a的固有值，a的取值越多，IV(a)的值通常越大。
增益率与信息增熵恰恰相反，其对可取值数目较少的属性有所偏好。
于是C4.5算法使用了一个启发式：先从候选划分属性中找出信息增熵高于平均水平的属性，再从中选择增益率最高的。
基尼指数（CART决策树算法）
.
基尼指数反映的是在D中随机抽取两个样本，它们类别标记不一致的概率。
与其他指标一样，属性a的基尼指数：
.
划分后选择基尼指数最小的属性作为最优划分属性。
剪枝处理
剪枝是用来对付“过拟合”的。
其基本策略：1、预剪枝：在决策树生成过程中，对每个结点在划分前线进行估计，若当前结点的划分不能带来决策树泛化性能上升，则进行剪枝（停止划分，将当前接结点作为叶子结点）；
2、后剪枝：顾名思义，先从训练集生成一棵完整的决策树，再从底向上对非叶子结点进行考察，如果将该结点剪枝会提高泛化性能，则进行剪枝。
预剪枝
对于预剪枝，其优点在于降低了过拟合的风险、减少决策树的训练时间开销和测试时间开销，但其缺点也很明显，也许有些分支划分在当前不能提升泛化性能，但是在此基础上的后续划分可能显著提升泛化性能，于是有欠拟合的风险。
后剪枝
后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但其缺点就是耗费训练时间开销。
小结
于是我们来总结一下，如何判断决策树泛化性能提升了？这就要用到前面第二章介绍的性能评估的方法，有如留出法、交叉验证法等，划分好训练集和验证集以后，采用上面的几种指标之一来进行属性的划分，有如信息增熵、增益率、基尼指数等，于是最后用剪枝处理来优化决策树的泛化性能。
连续与缺失值
连续值处理
对于上面我们都是针对离散属性来生成决策树的，但现实中还存在连续属性。我们需要对连续属性进行处理才能进行划分。
通常采用二分法对连续属性进行处理。（C4.5决策树算法）
给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将其从大到小排序为.基于划分点t可以将D划分为两部分，子集
。显然对于相邻属性的取值，t在
区间取任意值都可产生相同的划分结果。（就是无论如何取值都可以把D分成两个子集）于是可考察n-1个元素的候选划分点集合：
我们将区间的中位点作为候选划分点。
于是我们可以像考察离散属性那样来考察这些候选划分点，以选出最优划分点，即间接对连续属性进行了考察。
注意与离散属性不同的是，若当前结点划分属性为连续属性，该属性还是可作为其后代结点的划分属性的。（例如在父结点上使用了"密度<=0.223"，而其后代结点可以出现"密度<=0.111"这样的属性）
缺失值处理
对于现实情况，会出现样本不完整的状况，就是样本的一些属性值缺失了。
问题：1、如何在属性值缺失的情况下进行划分属性的选择？
2、给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
对于问题1，给定训练集D和属性a，令表示D中在a上没有缺失值的样本子集，我们可以仅根据
来选择划分属性a，假定a有V个取值
,则
表示
在a上取值为
的样本子集，
表示
中属于第k类的样本子集。
假定我们为每个样本赋予一个权重
，并定义：
.
.
通过以上的定义我们可以将信息增熵(其他指标也可进行推广)的计算式进行推广，即：
对于问题2，如果样本在划分属性a上的取值已知，则将
划入与其取值对应的子结点，且样本权重值在子结点中保持为
.反之，将
划入所有子结点中，其样本权重值调整为
.即将同一个样本以不同概率划入到不同的子结点中去。
多变量决策树
我们把一个属性作为坐标空间的一个坐标轴，若有d个属性，则这些属性就形成一个d维的空间，而用d个属性来描述的一个样本就在这个坐标空间中表示一个数据点。而对样本进行分类，即是在此空间中寻找不同类样本之间的分类边界。决策树生成的分类边界的特点是轴平行，即是其分类边界是由几段与坐标轴平行的线组成的。
其每一段的划分都对应了某个属性取值（边界）。但是折线划分，要进行大量的属性测试，其时间花销会很大。
所以我们采用斜线的划分边界：
所谓的多变量决策树（斜决策树）就是能实现这样斜划分甚至更加复杂划分的决策树。
即我们不再对非叶子结点的某个属性进行测试，而是对属性的线性组合进行测试。即非叶子结点如同一个这样的线性分类器，其中
是属性
的权重，
和
可以在该结点所含的样本集和属性集上学得。于是多变量决策树与单变量决策树不同，其不是为每个非叶子结点寻找一个最优划分属性，而是尝试建立一个最优的线性分类器对属性进行划分。
构建决策树：决策树算法实现
