1、决策树
决策树是基于树的结构来进行决策的，通常在经过一系列的判断或“子决策”之后，得出最终的决策，也即是我们最终所希望获得的结论。
决策树学习的目的：得到一颗泛化能力强，即处理未见示例能力强的决策树
2、决策树的构成
3、决策树生成的基本算法
决策树生成是一个递归过程，有三种情形导致递归返回
当前结点包含的样本全属于同一类，无需分类。此处直接将当前结点标记为C类（C类为样本类别）叶子结点。
当前属性集为空，或者所有样本在所有属性上取值相同，无法划分。
当前结点包含的样本集合为空，不能划分，分支结点标记为叶子结点，类别标记为当前样本集合中同类样本最多的类。
在第2种情形下，把当前结点标记为叶结点，但类别设定为该结点所含样本最多的类别。在第3种情形下，把当前结点标记为叶节点，但类别设定为其父结点所含样本最多的类别。它们的不同点是 ，第2种是利用当前结点的后验分布，第3种则是把父结点的样本分布作为当前结点的先验分布。
4、划分选择
问题：如何选择最优化分属性，我们希望结点的“纯度”越来越高
信息增益
信息熵：度量样本集合纯度最常用的一种指标。其公式如下：
的值越小，则
的纯度越高，
代表的是当前样本集合
信息增益：对于同一属性的不同取值计算出其信息熵后赋予权重，样本数越多的分枝其影响越大，由此可以计算出信息增益。
一般而言，信息增益越大，则意味着使用该属性来进行划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择。
增益率
在C4.5决策树算法中，不直接使用信息增益，而是使用“增益率”来选择最优划分属性。
增益率定义：
其中
C4.5是使用一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼指数
CART决策树常用基尼指数来选择划分属性
基尼值：数据集的纯度度量
基尼指数：
基尼指数小的属性作为最优化分属性。
5、剪枝
剪枝是解决策树学习算法“过拟合”的主要手段，基本策略有“预剪枝”和“后剪枝”
6、连续值与缺失值
连续值处理
问题：连续属性的可取值数目不再有限
处理方法：使用二分法对连续值进行处理，即是以某一个值为分界，对父结点进行划分，则正是C4.5决策树算法中采用的机制。
缺失值处理
问题一：如何在属性值缺失的情况下进行划分属性选择？（相应最优划分属性如何确定）
为样本赋予权重，再计算信息增益以确定最优划分属性。
问题二：给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？（即样本缺失该属性应如何划分）
样本x取值已知，则划入相应的子结点，并保持其权值w。
样本x取值未知，则划入全部子结点中，并调整其权值，即是以不同的概率划入到不同的子结点去。
7、多变量决策树
在面对复杂的决策树时，由于要进行大量的属性测试，使用平行于轴的分类边界，预测时间开销会很大，而多变量决策树就是一种实现斜划分甚至更复杂划分的决策树，它不是寻找一个最优化分属性，而是试图建立一个合适的线性分类器。
