正则化是结构风险最小化策略的实现统计学习⽅法李航---第5章决策树
第5章决策树
决策树(decision tree)是⼀种基本的分类与回归⽅法。本章主要讨论⽤于分类的决策树。决策树模型呈树形结构，在分类问题中，表⽰基于特征对实例进⾏分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利⽤训练数据，根据损失函数最⼩化的原则建⽴决策树模型。预测时，对新的数据，利⽤决策树模型进⾏分类。决策树学习通常包括3个步骤：特征选择、决策树的⽣成和决策树的修剪。
5.1 决策树模型与学习
定义5.1 (决策树) ：分类决策树模型是⼀种描述对实例进⾏分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node )和叶结点(leaf node)。内部结点表⽰⼀个特征或属性，叶结点表⽰⼀个类。
⽤决策树分类，从根结点开始，对实例的某⼀特征进⾏测试，根据测试结果，将实例分配到其⼦结点；这时，每⼀个⼦结点对应着该特征的⼀个取值。如此递归地对实例进⾏测试并分配，直⾄达到叶结点。最后将实例分到叶结点的类中。
图中圆和⽅框分别表⽰内部结点和叶结点.
决策树与if-then规则
可以将决策树看成⼀个if-then规则的集合，转换成if-then规则的过程：由决策树的根结点到叶结点的每⼀条路径构建⼀条规则；路径上内部结点的特征对应着规则的条件，⽽叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有⼀个重要的性质：互斥并且完备，每⼀个实例都被⼀条路径或⼀条规则所覆盖，⽽且只被⼀条路径或⼀条规则所覆盖。这⾥所谓覆盖是指实例的特征与路径上的特征⼀致或实例满⾜规则的条件。
决策树与条件概率分布
决策树还表⽰给定特征条件下类的条件概率分布。这⼀条件概率分布定义在特征空间的⼀个划分(partition)上，将特征空间划分为互不相交的单元(cell)或区域(region)，并在每个单元定义⼀个类的概率分布就构成了⼀个条件概率分布。
决策树的⼀条路径对应于划分中的⼀个单元。决策树所表⽰的条件概率分布由各个单元给定条件下类的条件概率分布组成。条件概率分布可以表⽰为P(Y|X)，X取值于给定划分下单元的集合，Y取值于类的集合。各叶结点(单元)上的条件概率往往偏向某⼀个类，即属于某⼀类的概率较⼤。决策树分类时将该结点的实例强⾏分到条件概率⼤的那⼀类去。
决策树学习
决策树学习本质上是从训练数据集中归纳出⼀组分类规则。可能有多个，可能没有。我们需要的是⼀个与训练数据⽭盾较⼩的决策树，同时具有很好的泛化能⼒。
从另⼀个⾓度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有⽆穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，⽽且对未知数据有很好的预测。
决策树学习的损失函数：通常是正则化的极⼤似然函数
决策树学习的策略：是以损失函数为⽬标函数的最⼩化
因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采⽤启发式⽅法，近似求解这⼀最优化问题，得到的决策树是次最优(sub-optimal)的。
决策树学习的算法通常是⼀个递归地选择最优特征，并根据该特征对训练数据进⾏分割，使得对各个⼦数据集有⼀个最好的分类的过程。
剪枝：决策树可能对训练数据有很好的分类能⼒，但可能发⽣过拟合现象.。所以需要对已⽣成的树⾃下
⽽上进⾏剪枝，将树变得更简单，从⽽使它具有更好的泛化能⼒。具体地，就是去掉过于细分的叶结点，使其回退到⽗结点，甚⾄更⾼的结点，然后将⽗结点或更⾼的结点改为新的叶结点.
特征选择：如果特征数量很多，在决策树学习开始时对特征进⾏选择，只留下对训练数据有⾜够分类能⼒的特征。
由于决策树表⽰⼀个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的⽣成对应模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的⽣成只考虑局部最优，决策树的剪枝则考虑全局最优。
5.2 特征选择
特征选择问题：特征选择在于选取对训练数据具有分类能⼒的特征。通常特征选择的准则是信息增益或信息增益⽐。
设有随机变量(X,Y)，其联合概率分布为：
条件嫡H(Y|X)表⽰在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件嫡(conditional entropy)
H(Y|X)，定义为X给定条件下Y的条件概率分布的嫡对X的数学期望：
当嫡和条件嫡中的概率由数据估计(特别是极⼤似然估计)得到时，所对应的嫡与条件嫡分别称为经验熵( empirical entropy)和经验条件嫡(empirical conditional entropy )。
信息增益(information gain)表⽰得知特征X的信息⽽使得类Y的信息的不确定性减少的程度.
定义5.2(信息增益)：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验嫡H(D)与特征A给定条件下D的经验条件嫡H(D|A)之差，即
决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
根据信息增益准则的特征选择⽅法是：对训练数据集(或⼦集)D，计算其每个特征的信息增益，并⽐较它们的⼤⼩，选择信息增益最⼤的特征。
|D|表⽰其样本容量，即样本个数。设有K个类C k，k=1,2,...,K，|C k|为属于类C k的样本个数。根据特征A的取值将D划分为n个⼦集
D1,D2,...,D n,|D i|为D i的样本个数。记⼦集D i中属于类C k的样本的集合为D ik。
信息增益值的⼤⼩是相对于训练数据集⽽⾔的，并没有绝对意义。在分类问题困难时，也就是说在训练数据集的经验嫡⼤的时候，信息增益值会偏⼤，反之，信息增益值会偏⼩。
定义5.3 信息增益⽐：特征A对训练数据集D的信息增益⽐g R(D,A)定义为其信息增益g(D,A)与训练数据集D的经验H(D)之⽐:
5.3 决策树的⽣成
ID3算法: ID3算法的核⼼是在决策树各个结点上应⽤信息增益准则选择特征。
ID3算法只有树的⽣成，所以该算法⽣成的树容易产⽣过拟合
C4.5算法：与ID3算法相似，不同是⽤信息增益⽐来选择特征。
5.4 决策树的剪枝
决策树的⽣成算法容易构建过于复杂的决策树，产⽣过拟合。、
决策树的剪枝：在决策树学习中将已⽣成的树进⾏简化的过程称为剪枝(pruning)。具体地，剪枝从已⽣成的树上裁掉⼀些⼦树或叶结点，并将其根结点或⽗结点作为新的叶结点，从⽽简化分类树模型.
决策树的剪枝往往通过极⼩化决策树整体的损失函数(loss fimction)或代价函数( cost function)来实现。
设树T的叶结点个数为|T|, t是树T的叶结点，该叶结点有N t个样本点，其中k类的样本点有N tk个，k=1,2,
...,K，H t(T)为叶结点t上的经验
嫡，a>=0为参数，则决策树学习的损失函数可以定义为
C(T)表⽰模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表⽰平莫型复杂度，参数a>=0控制两者之间的影响。剪枝，就是当a确定时，选择损失函数最⼩的模型，即损失函数最⼩的⼦树。损失函数正好表⽰了对模型的复杂度和训练数据的拟合两者的平衡。
决策树⽣成只考虑了通过提⾼信息增益(或信息增益⽐)对训练数据进⾏更好的拟合，学习局部的模型；
决策树剪枝通过优化损失函数还考虑了减⼩模型复杂度，学习整体的模型。
利⽤损失函数最⼩原则进⾏剪枝就是⽤正则化的极⼤似然估计进⾏模型选择。
5.5  CART算法
分类与回归树(classification and regression tree, CART)模型同样由特征选择、树的⽣成及剪枝组成，既可以⽤于分类也可以⽤于回归。CART算法由以下两步组成
(1)决策树⽣成：基于训练数据集⽣成决策树，⽜成的决策树要尽量⼤；
(2)决策树剪枝：⽤验证数据集对⼰⽣成的树进⾏剪枝并选择最优⼦树，这时⽤损失函数最⼩作为剪枝的标准。
CART⽣成：对回归树⽤平⽅误差最⼩化准则，对分类树⽤基尼指数(Gini index)最⼩化准则，进⾏特征选择。
回归树的⽣成：
分类树的⽣成
分类树⽤基尼指数选择最优特征，同时决定该特征的最优⼆值切分点.
定义5.4(基尼指数)：分类问题中，假设有K个类，样本点属于第k类的概率为p k，则概率分布的基尼指数定义为
对于给定的样本集合D，其基尼指数为
如果样本集合D根据特征A是否取某⼀可能值a被分割成D1和D2两部分，则在特征A的条件下，集合D的基尼指数定义为
CART剪枝
CART剪枝算法由两步组成⾸先从⽣成算法产⽣的决策树T0底端开始不断剪枝，直到T0的根结点，形成⼀个⼦树序列代｛T0,T1,...,T n｝；然后通过交叉验证法在独⽴的验证数据集上对⼦树序列进⾏测试，从中选择最优⼦树。
(1) 剪枝。形成⼀个⼦树序列
在剪枝过程中，计算⼦树的损失函数:
可以⽤递归的⽅法对树进⾏剪枝，将a从⼩增⼤，a0<a1<...<a n<+⽆穷，产⽣⼀系列的区间[a i，a i+1)，i =0,1,...,n；剪枝得到的⼦树序列对应着区间[a i，a i+1)，i =0,1,...,n的最优⼦树序列{T0, T1, ... , Tn}，序列中的⼦树是嵌套的。
对T0中每⼀内部结点t，计算
表⽰剪枝后整体损失函数减少的程度，在T0中剪去g(t)最⼩的T t，将得到的⼦树作为T1，同时将最⼩的g(t)设为a1，T1为区间[a1，a2)的最优⼦树。如此剪枝下去，直⾄得到根结点。在这⼀过程中，不断地增加a的值，产⽣新的区间。
(2) 在剪枝得到的⼦树序列T0, T1, ... , T n中通过交叉验证选取最优⼦树T a
具体地，利⽤独⽴的验证数据集，测试⼦树序列T0, T1, ... , T n中各棵⼦树的平⽅误差或基尼指数。平⽅误差或基尼指数最⼩的决策树被认为是最优的决策树。在⼦树序列中，每棵⼦树T0, T1, ... , T n都对应于⼀个参数a0, a1, ... , a n。所以，当
最优⼦树T k确定时，对应的a k也确定了，即得到最优决策树T a。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。