机器学习(决策树)
介绍
决策树(decision tree)，也称为判定树，是一类常见的机器学习的方法。
一般，一棵决策树包含1个根节点,若干内部结点,若干叶结点。叶结点对应决策结果，其他每个结点对应一个属性测试，根结点包含样本全集。
目的
决策树学习的目的是为了产生一棵泛化能力强(处理未见示例的能力强)的决策树，基本流程遵循简单且直观的分而治之(divide-and-conquer)策略。
简单示例
上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色节点表示判断条件，橙色节点表示决策结果，箭头表示在一个判断条件在不同情况下的决策路径，图中红色箭头表示了上面例子中女孩的决策过程。
这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。
划分选择
决策树的生成是一个递归的过程。决策树的学习关键在于如何选择最优划分属性。随着划分过程的不断进行，我们希望决策树的分支节点包含的样本尽可能属于同一类，即结点的纯度(purity)越来越高。那么度量样本集合纯度的指标是什么呢？
- 信息熵(information entropy))是常用的一种指标。信息熵的值越小，样本集合的纯度越高。
- 1.信息增益(information gain)越大，就意味着使用属性a来划分所获得的纯度提升越大。信息增益准则对可取值数目较多的属性有所偏好。
注：信息增益 = 分类前信息熵 - 分类后信息熵 - 2.增益率(intrinsic value). C4.5决策树算法采用的。增益率对可取值数目较少的属性有所偏好，因此，C4.5决策树算法不是直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
- 3.基尼指数(Gini index). 基尼值越小，数据集的纯度越高。
剪枝处理(pruning)
剪枝是决策树学习算法对付 过拟合(决策树分支过多，把训练集的特点当作所有数据都具有的一般性质)的主要手段。
- 预剪枝(prepruning)： 决策树在生成的过程中，对于每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
- 优点：降低了过拟合的风险，显著减少了决策树的训练时间开销和测试时间开销
- 缺点：可能导致欠拟合
- 后剪枝(postpruning)：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。后剪枝决策树比预剪枝决策树保留了更多的分支。
- 优点：后剪枝决策树的欠拟合风险较小，泛化性能往往优于预测剪枝决策树。
- 缺点：需要自底向上对树中的所有非叶结点进行逐一考察，训练时间开销大得多。
如何判断决策树泛化性能是否提升呢？
待填坑。。。
连续与缺失值处理
1. 连续值处理
=> 连续属性离散化技术 => 二分法(bi-partition)
2. 缺失值处理1
2(1)如何在属性值缺失的情况下进行划分属性选择？
(2)给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？