统计学习方法 读书笔记（五）
读书笔记仅供个人学习使用
本文主要参考书籍为《统计学习方法》（李航）第二版
参考
Sunning_001的博客
决策树是一种基本的分类与回归方法。
决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。
（1）是if-then规则的集合
（2）是定义在特征空间与类空间上的条件概率分布
模型的主要优点有：具有可读性，分类速度快
显然，决策树在逻辑上以树的形式存在，包含根节点、内部结点和叶节点。
根节点：包含数据集中的所有数据的集合
内部节点：每个内部节点为一个判断条件，并且包含数据集中满足从根节点到该节点所有条件的数据的集合。根据内部结点的判断条件测试结果，内部节点对应的数据的集合别分到两个或多个子节点中。
叶节点：叶节点为最终的类别，被包含在该叶节点的数据属于该类别。
简而言之，决策树是一个利用树的模型进行决策的多分类模型，简单有效，易于理解。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。
决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。
决策树的定义分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。
用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。
图中圆和方框分别表示内部结点和叶结点
生动的例子参照自Sunning_001的博文
一位母亲给自己的女儿介绍对象
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的挑剔过程就是一个典型的决策树，即相当于通过年龄、长相、收入和是否公务员将对象分为两个类别：见和不见。
假设这个女孩对男人的要求是：
1.30岁以下
2.长相中等以上
3.高收入者或中等以上收入
4.公务员
那么使用下图就能很好地表示女孩的决策逻辑（即一个决策树模型）
从这个例子出发，我们可以很好地理解书中这样的描述
【可以将决策树看成一个if-then规则的集合，转换成if-then规则的过程】：
由决策树的根结点到叶结点的每一条路径构建一条规则；
路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论
决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备
每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。(这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件)
条件概率分布的理解决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上，将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。条件概率分布可以表示为P(Y|X)，X取值于给定划分下单元的集合，Y取值于类的集合。各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。
决策树学习决策树学习本质上是从训练数据集中归纳出一组分类规则。可能有多个，可能没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。
决策树学习的损失函数：通常是正则化的极大似然函数
决策树学习的策略：是以损失函数为目标函数的最小化
因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题，得到的决策树是次最优(sub-optimal)的。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。
剪枝：决策树可能对训练数据有很好的分类能力，但可能发生过拟合现象.。所以需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点.
特征选择：如果特征数量很多，在决策树学习开始时对特征进行选择，只留下对训练数据有足够分类能力的特征。
由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，决策树的剪枝则考虑全局最优。
特征选择特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。
通常特征选择的准则是信息增益或信息增益比
设有随机变量(X,Y)，其联合概率分布为：P(X=xi)=pi,i=1,2,⋯ ,n P(X=x_i)=p_i,i=1,2,\cdots,nP(X=xi)=pi,i=1,2,⋯,n
则随机变量X的熵定义为H(X)=−∑i=1npilogpiH(X)=-\sum_{i=1}^n p_i \log p_iH(X)=−i=1∑npilogpi
当嫡和条件嫡中的概率由数据估计(特别是极大似然估计)得到时，所对应的嫡与条件嫡分别称为经验熵( empirical entropy)和经验条件嫡(empirical conditional entropy )。
信息增益信息增益：表示得知特征X的信息而使得类Y的信息的不确定性减少的程度表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益g(D,A)
定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差
g(D,A)=H(D)−H(D∣A)g(D,A)=H(D)-H(D|A)g(D,A)=H(D)−H(D∣A)
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中的类与特征的互信息。
决策树学习应用信息增益准则选择特征。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）D,计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征
信息增益算法
信息增益比：特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验H(D)之比:
gR=g(D,A)HA(D)g_R=\frac{g(D,A)}{H_A(D)}gR=HA(D)g(D,A)
基尼指数准则
分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为
Gini(p)=∑k=1kpk(1−pk)=1−∑k=1kpk2Gini(p)=\sum_{k=1}^{k}{{}{p_k(1-p_k)}}=1-\sum_{k=1}^{k}{p_k^2}Gini(p)=k=1∑kpk(1−pk)=1−k=1∑kpk2
基尼值代表了从D中随机选择两个样本，其类别不一致的概率。
有了基尼值后，可以在此基础上定义基尼指数：
Gini(D)=1−∑k=1K(∣Ck∣∣D∣)2Gini(D)=1-\sum_{k=1}^{K}{(\frac{|C_k|}{|D|})^2}Gini(D)=1−k=1∑K(∣D∣∣Ck∣)2
可以看出基尼指数越小，说明纯度越高，我们可以通过选择基尼指数小的属性来划分子节点。
决策树的生成目前常用的决策树的算法包括ID3（Iterative Dichotomiser 3，第3代迭戈二叉树）、C4.5和CART（ClassificationAnd Regression Tree，分类和回归树）。前两种算法主要应用的是基于熵的方法，而第三种应用的是基尼指数的方法。
ID3ID3算法: ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征。
ID3算法只有树的生成，所以该算法生成的树容易产生过拟合
输入:训练数据集 D， 特征集 A 阔值 ε:
输出:决策树 T。
(1) 若 D 中所有实例属于同一类 CkC_kCk ， 则 T 为单结点树，并将类 CkC_kCk 作为该结点 的类标记，返回 T;
(2) 若 A= Ø，则 T 为单结点树，并将 D 中实例数最大的类 CkC_kCk 作为该结点的类 标记，返回 T;
(3) 否则，按算法 5.1 计算 A 中各特征对 D 的信息增益，选择信息增益最大的特 征 AgA_gAg;
(4) 如果 AgA_gAg的信息增益小于阔值 ε，则置 T 为单结点树，并将 D 中实例数最大 的类 CkC_kCk 作为该结点的类标记，返回 T;
(5) 否则，对 AgA_gAg 的每 -可能值句，依 Ag=aiA_g=a_iAg=ai 将 D 分割为若干非空子集 DiD_iDi将DiD_iDi 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 T， 返回 T;
(6) 对第 i 个子结点，以DiD_iDi为训练集，以 A一{Ag} 为特征集，递归地调用步 (1)~ 步 (5) ，得到子树TiT_iTi ,返回TiT_iTi。
C4.5与ID3算法相似，不同是用信息增益比来选择特征，故不在赘述。
剪枝决策树的生成算法容易构建过于复杂的决策树，产生过拟合。
决策树的剪枝：在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning)。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型.
决策树的剪枝往往通过极小化决策树整体的损失函数(loss fimction)或代价函数( cost function)来实现。
设树T的叶结点个数为|T|, t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个，k=1,2,…,K，Ht(T)为叶结点t上的经验嫡，a>=0为参数，则决策树学习的损失函数可以定义为
C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示平莫型复杂度，参数a>=0控制两者之间的影响。剪枝，就是当a确定时，选择损失函数最小的模型，即损失函数最小的子树。损失函数正好表示了对模型的复杂度和训练数据的拟合两者的平衡。
决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合，学习局部的模型；
决策树剪枝通过优化损失函数还考虑了减小模型复杂度，学习整体的模型。
利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。
CART算法分类与回归树(classification and regression tree, CART)模型同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。
CART算法由以下两步组成
(1)决策树生成：基于训练数据集生成决策树，牛成的决策树要尽量大；
(2)决策树剪枝：用验证数据集对己生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
CART生成：对回归树用平方误差最小化准则，对分类树用基尼指数(Gini index)最小化准则，进行特征选择。
回归树的生成：
分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点.
CART剪枝
CART剪枝算法由两步组成首先从生成算法产生的决策树T0底端开始不断剪枝，直到T0的根结点，形成一个子树序列代｛T0,T1,...,Tn｝｛T_0,T_1,...,T_n｝｛T0,T1,...,Tn｝；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
(1) 剪枝。形成一个子树序列
在剪枝过程中，计算子树的损失函数:
可以用递归的方法对树进行剪枝，将a从小增大，a0<a1<...<an<a_0<a_1<...<a_n<a0<a1<...<an<+无穷，产生一系列的区间[ai，ai+1)[a_i，a_{i+1})[ai，ai+1)，i =0,1,…,n；剪枝得到的子树序列对应着区间[ai，ai+1)[a_i，a_{i+1})[ai，ai+1)，i =0,1,…,n的最优子树序列｛T0,T1,...,Tn｝｛T_0,T_1,...,T_n｝｛T0,T1,...,Tn｝，序列中的子树是嵌套的。
对T0中每一内部结点t，计算
表示剪枝后整体损失函数减少的程度，在T0T_0T0中剪去g(t)最小的TtT_tTt，将得到的子树作为T1T_1T1，同时将最小的g(t)设为a1a_1a1，T1T_1T1为区间[a1，a2)[a_1，a_2)[a1，a2)的最优子树。如此剪枝下去，直至得到根结点。在这一过程中，不断地增加a的值，产生新的区间。
(2) 在剪枝得到的子树序列｛T0,T1,...,Tn｝｛T_0,T_1,...,T_n｝｛T0,T1,...,Tn｝中通过交叉验证选取最优子树TaT_aTa
具体地，利用独立的验证数据集，测试子树序列｛T0,T1,...,Tn｝｛T_0,T_1,...,T_n｝｛T0,T1,...,Tn｝中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树｛T0,T1,...,Tn｝｛T_0,T_1,...,T_n｝｛T0,T1,...,Tn｝都对应于一个参数a0,a1,...,ana_0, a_1, ... , a_na0,a1,...,an。所以，当
最优子树TkT_kTk确定时，对应的aka_kak也确定了，即得到最优决策树TaT_aTa。
作者：多好篝火
