统计学习---决策树
决策树
定义在特征空间与类空间上的条件概率分布。
学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型；
预测时，对新的数据，利用决策树模型进行分类。
3步走：特征选择，决策树的生成，决策树的修剪
决策树模型
是一个树形结构，内部结点表示一个特征或属性，叶结点表示一个类。
用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至到达叶结点。最后将实例分到叶结点的类中。
If-then规则
由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
条件概率分布
决策树表示给定特征条件下类的条件概分布。
定义在特征空间的一个划分上。
将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
决策树的一条路径对应于划分中的一个单元。
决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。
假设X表示特征的随机变量，Y表示类的随机变量，那么上述的条件概率就表示为P(Y|X).
决策树学习
本质是从训练数据集中归纳出一组分类规则。
决策树学习是由训练数据集估计条件概率模型。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类过程。
对应着特征空间的划分，也对应着决策树的构建。
开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其分割，构建相应结点，一直递归下去直到所以训练数据集都被基本正确分类。这就生成了一棵决策树。
这样构建的决策树可能太细法了，不能对未知数据有一个很好的分类，出现过拟合的现象。那咋办？要么分好之后修剪，要么一开始就先进行特征选择。
特征选择
决定用哪个特征来划分特征空间。
特征选择的的准则是信息增益和信息增益熵
信息增益
熵：随机变量不确定性的度量
熵只依赖于随机变量X的分布，与X的取值无关。
熵越大，随机变量的不确定性就越大。
条件熵：在已知随机变量X的条件下随机变量Y的不确定性。
H(Y|X)随机变量X给定的条件下随机变量Y的条件熵，定义为X给定条件下Y的条件概率分布的熵对X的数学期望。
当熵和条件熵的概率由数据估计（极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。
信息增益：
决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益表示由于特征A而使得对数据集D的分类的不确定性减少的程度。
信息增益大的特征具有更强的分类能力。
选择特征方法是：队训练数据集D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
增益信息的算法
信息增益比
---------------------------------------------------------------------------------------------------------------------------------------------------------------
决策树的生成
ID3算法
从根结点开始，对结点计算所以可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归的调用以上方法，构建决策树；直到所以特征的信息增益均很小或没有特征可以选择为止。相当于用最大似然法进行概率模型的选择。
C4.5
与ID3算法相似，用信息增益比来选择特征
决策树的修剪
生成算法递归产生的决策树容易出现过拟合，因为在于学习时过多的考虑如何提高训练数据的正确分类而产生了较为复杂的决策树。
如何解决？考虑决策树的复杂度，对已生成的决策树进行简化。
简化的过程称为剪枝，从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。
|T|表示模型的复杂度。
CART算法
分类与回归数模型
是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。
CART假设决策树是二叉树，内部结点特征的取值为“是”或“否”，左边取是，右边取否。
等价于递归地二分每个特征，将输入空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART生成
递归地构建决策二叉树的过程。
对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
回归树的生成
分类树的生成
基尼指数
生成树算法
CART剪枝
首先从生成算法产生的决策树低端开始不断剪枝，直到根结点，形成一个子树序列；
然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选出最优子序列。
- 在剪枝过程中计算损失函数
- 在剪枝得到子序列中通过交叉验证选取最优子树
利用独立的验证数据集，测试子树序列中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。
CART剪枝算法