机器学习升级版 决策树和随机森林
基于样本和特征的双重随机性。
之所以有那么多种的处理办法，是因为没有某一种是十分有效的。
CART
classification and regression tree
统计学习方法 决策树
决策树( decision tree)是一种基本的分类与回归方法。这里主要是用于分类的决策树.决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是 if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。
其主要优点是模型具有可读性,分类速度快。学习时,利用训练数据根据损失函数最小化的原则建立决策树模型。预测时,对新的数据,利用决策树模型进行分类。
决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。
决策树模型与学习
决策树模型
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边( directed edge)组成。
结点有两种类型:内部结点( internal node)和叶结点( leaf node)。内部结点表示一个特征或属性,叶结点表示一个类。
用决策树分类,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点;这时,每一个子结点对应着该特征的一个取值.如此递归地对实例进行测试并分配,直至达到叶结点.最后将实例分到叶结点的类中。
圆代表内部节点，方框代表叶节点。
决策树与if-then规则
可以将决策树看成一个 if-then规则的集合.将决策树转换成 if-then规则的过程是这样的:由决策树的根结点到叶结点的每一条路径构建一条规则;路径上内部结点的特征对应着规则的条件,而叶结点的类对应着规则的结论.决策树的路径或其对应的 if-then规则集合具有一个重要的性质:互斥并且完备.这就是说,每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖.这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布。假设X为表示特征的随机变量,Y为表示类的随机变量,那么这个条件概率分布可以表示为：
X取值与给定划分下单元的集合，Y取值于类的集合。各叶节点上的条件概率往往偏向某一类，即属于某一类的概率较大。决策树分类时将该节点的实例强行分到条件概率大的那一类去。
决策树学习
决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不
相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能
一个也没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的
泛化能力。
决策树学习用损失函数表示这一目标,如下所述,决策树学习的损失函数通常是正则化的极大似然函数.决策树学习的策略是以损失函数为目标函数的最小化。
当损失函数确定以后,学习问题就变为在损失函数意义下选择最优决策树的问题,因为从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中决策树学习算法通常采用启发式方法,近似求解这一最优化问题.这样得到的决策树是次最优(sub- optimal)的。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。
生成的决策树可能对训练数据有很好的分类能力,但对未知的测试数据却未必有很好的分类能力,即可能发生过拟合现象.我们需要对已生成的树自下而上进行剪枝,将树变得更简单,从而使它具有更好的泛化能力。
如果特征数量很多,也可以在决策树学习开始的时候,对特征进行选择,只留下对训练数据有足够分类能力的特征。
决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程.由于决策树表示一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型.决策树的生成对应于模型的局部选择,决策树的剪枝对应于模型的全局选择.决策树的生成只考虑局部最优,相对地,决策树的剪枝则考虑全局最优。
特征选择
特征选择问题
特征选择在于选取对训练数据具有分类能力的特征.这样可以提高决策树学习的效率.如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的,经验上扔掉这样的特征对决策树学习的精度影响不大,通常特征选择的准则是信息增益或信息增益比。
信息增益
信息增益的算法
输入训练集D和特征A：
输出：特征A对训练数据集D的信息增益g(D,A)。
A3，A4类似，最后比较各特征的信息增益值。由于特征A3的信息增益值最大，所以选择特征A3作为最优特征。
信息增益比
信息增益比定义
决策树的生成
ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树.具体方法是:从根结点( root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点;再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止,最后得到一个决策树.ID3相当于用极大似然法进行概率模型的选择。
算法（ID3算法）
ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。而且ID3还存在着不能直接处理连续型特征的问题。只有事先将连续型特征离散化，才能在ID3算法中使用，但这种转换过程会破坏连续型变量的内在特性。
C4.5的生成算法
C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。
算法（C4.5的生成算法）
决策树的剪枝
决策树生成算法递归地产生决策树,直到不能继续下去为止,这样产生的树往往对训练数据的分类很准确,但对未知的测试数据的分类却没有那么准确,即出现过拟合现象.过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,解决这个问题的办法是考虑决策树的复杂度,对已生成的决策树进行简化。
在决策树学习中将已生成的树进行简化的过程称为剪枝( pruning).具体地,剪枝从已生成的树上裁掉一些子树或叶结点,并将其根结点或父结点作为新的叶结点,从而简化分类树模型。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶节点个数为|T|，t是树T的叶节点，该
C（T）表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数α≥0控制两者之间的影响。较大的α促使选择较简单的模型（树），较小的α促使选择较复杂的模型（树）。α=0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
剪枝,就是当α确定时,选择损失函数最小的模型,即损失函数最小的子树.当α值确定时,子树越大,往往与训练数据的拟合越好,但是模型的复杂度就越髙;相反,子树越小,模型的复杂度就越低,但是往往与训练数据的拟合不好,损失函数正好表示了对两者的平衡。
算法（树的剪枝算法）
输入：生成算法产生的整个树T，参数α；
输出：修剪后的子树Tα。
- 计算每个结点的经验熵。
- 递归地从树的叶节点向上回缩。
- 返回2，直至不能继续为止，得到损失函数最小的子树Tα。
式(515)只需考虑两个树的损失函数的差,其计算可以在局部进行,所以,决策树的剪枝算法可以由一种动态规划的算法实现。
CART算法
CART：classification and regression tree
CART算法有两步：
- 决策树生成，基于训练数据集生成决策树，生成的决策树要尽量大
- 决策树剪枝，用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
CART生成
决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
回归树的生成
用人话解释：回归树的原理及Python实现 - 李小文的文章 - 知乎
https://zhuanlan.zhihu.com/p/43939904
就是把连续的数据分为几个区间，问题的关键就是分割点的选取。
分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
生成方法与ID3决策树类似。
CART剪枝
CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小(模型变简单)，从而能够对未知数据有更准确的预测。
CART剪枝算法由两步组成:首先从生成算法产生的决策树To底端开始不断剪枝,直到To的根结点，形成一个子树序列{T1,…,Tn};然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
剪枝，形成一个子树序列
在剪枝过程中，计算子树的损失函数:
T为任意子树，C（T）为训练数据的预测误差（如基尼指数），|T|为子树的叶节点个数，α≥0为参数，Cα（T）为参数是α时的子树T的整体损失。参数α权衡训练数据的拟合程度与模型的复杂度。
对固定的α,一定存在使损失函数C(T)最小的子树，将其表示为Tα. Tα在损失函数Cα(T)最小的意义下是最优的.容易验证这样的最优子树是唯一的.当α大的时候，最优子树Tα偏小;当α小的时候，最优子树Tα偏大. 极端情况，当α=0时，整体树是最优的，当α趋近正无穷时，根结点组成的单结点树是最优的.
从整体树T0开始剪枝，对T0的任意内部节点t，以t为单结点树的损失函数是
以t为根结点的子树Tt的损失函数是
当α=0及α充分小时，有不等式
当α增大时，在某一α有
当α再增大时，不等式反向。只要
Tt与t有相同的损失函数值，而t的节点少，因此t比Tt更可取，对Tt进行剪枝。
为此，对T0中每一内部结点t，计算
它表示剪枝后整体损失函数减少的程度.在T0中剪去g(t)最小的Tt,将得到的子
树作为T1，同时将最小的g(t)设为α1. T1为区间[α1,α2)的最优子树.
如此剪枝下去，直到得到根节点。在这一过程中，不断增加α的值，产生新的区间。
在剪枝得到的子树序列T0,T1,…,Tn中通过交叉验证选取最优子树Tα
具体地，利用独立的验证数据集，测试子树序列T0,T1,…,Tn中各棵子树的平方误差或基尼指数.平方误差或基尼指数最小的决策树被认为是最优的决策树.在子树序列中，每棵子树T1,T2,.,Tn都对应于一个参数α1,α2,…,αn,.所以，当最优子树Tk确定时，对应的ak也确定了，即得到最优决策树Tα。
CART剪枝算法
西瓜书 树剪枝
可以采用留出法，即预留一部分数据用作“验证集”以进行性能评估。
预剪枝
预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但在另一方面，有些分支的当前划分虽不能提高泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。
后剪枝
后剪枝先从训练集生成一颗完整决策树。
对比可得，后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般来说，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶节点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大。
博客
回归树：
回归树与线性回归的对比：
西瓜书 Bagging与随机森林
欲得到泛化性能强的集成,集成中的个体学习器应尽可能相互独立;虽然“独立”在现实任务中无法做到，但可以设法使基学习器尽可能具有较大的差异.给定一个训练数据集,一种可能的做法是对训练样本进行采样，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器.这样，由于训练数据不同,我们获得的基学习器可望具有比较大的差异.然而，为获得好的集成，我们同时还希望个体学习器不能太差.如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习,这显然无法确保产生出比较好的基学习器.为解决这个问题，我们可考虑使用相互有交叠的采样子集.
Bagging
Bagging是并行式集成学习最著名的代表，直接基于自助采样法（bootstrap sampling）。给定包含m个样本的数据集,我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中,这样,经过m次随机采样操作,我们得到含m个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的则从未出现，由式(2.1)可知, 初始训练集中约有63.2%的样本出现在采样集中.
我们可采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合.这就是Bagging的基本流程.在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法.若分类预测时出现两个类收到同样票数的情形,则最简单的做法是随机选择一个,也可进一步考察学习器投票的置信度来确定最终胜者.
自助采样过程还给Bagging带来了另一个优点:由于每个基学习器只使用了初始训练集中约63.2%的样本,剩下约36.8%的样本可用作验证集来对泛化性能进行“包外估计”。
包外样本还有许多其他用途.例如当基学习器是决策树时，可使用包外样本来辅助剪枝,或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理;当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险.
从偏差方差分解的角度看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。
随机森林
随机森林(Random Forest,简称RF) 是Bagging的一个扩展变体. RF在以决策树为基学习器构建Bagging集成的基础上,进一步在决策树的训练过程中引入了随机属性选择.具体来说，传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性;而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度。若k=d则基决策树的构建与传统决策树相同，一般，推荐k=log2d。
随机森林简单、容易实现、计算开销小，令人惊奇的是，它在很多现实任务中展现出强大的性能,被誉为“代表集成学习技术水平的方法”.可以看出，随机森林对Bagging只做了小改动,但是与Bagging中基学习器的“多样性”仅通过样本扰动(通过对初始训练集采样)而来不同，随机森林中基学习器的多样性不仅来自样本扰动,还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升.
随机森林的收敛性与Bagging相似，起始性能往往相对较差，特别是在集成中只包含一个基学习器时。这不难理解，因为通过引入属性扰动，随机森林中个体学习器的性能往往有所降低，但是随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差值得一提的是,随机森林的训练效率常优于Bagging,因为在个体决策树的构建过程中, Bagging使用的是“确定型”决策树,在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的“随机型”央策树则只需考察一个属性子集.
结合策略
学习器结合的好处
学习器结合会带来三个方面的好处：
- 统计方面，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能会因为误选而导致泛化性能不佳，结合多个学习器则会减小这一风险。
- 计算方面，学习算法往往会陷入局部极小,有的局部极小点所对应的泛化性能可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险。
- 表示方面，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效,而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。
平均法
对于数值型输出，最常见的就是平均法。简单平均法
加权平均法
投票法
绝对多数投票法
即若某标记得票过半数，则预测为该标记，否则拒绝预测。相对多数投票法
即预测为得票最多的标记，若同时又多个标记获最高票，则从中随机选取一个。加权投票法
与加权平均法类似。
标准的绝对多数投票法提供了“拒绝预测”选项,这在可靠性要求较高的学习任务中是一个很好的机制.但若学习任务要求必须提供预测结果，则绝对多数投票法将退化为相对多数投票法.因此,在不允许拒绝预测的任务中,绝对多数、相对多数投票法统称为“多数投票法”。
硬投票：输出预测的类标记，软投票，输出一个概率估计。
实践
决策树
算法实现。
背景：贷款放贷与否
https://github.com/zdkswd/MLcode/blob/master/%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0/%E5%86%B3%E7%AD%96%E6%A0%91.py
scikit-learn决策树
使用scikit-learn实现。
背景：配隐形眼镜
https://github.com/zdkswd/MLcode/tree/master/scikit-learn-code/scikit-learn%E5%86%B3%E7%AD%96%E6%A0%91
回归树
关键词：CART，预剪枝，后剪枝
回归树与分类树比较类似，不同的是分类树最后的决策的结果是离散型的值，回归树决策的结果是输出一个实数。实例中的实数输出（就是叶子节点）的是四个样本的平均值（四个样本是在进行预剪枝时设置的值）。
CART回归树这里使用最小总方差法选取划分特征。示例中采用的是REP（错误率降低剪枝）。还有一种方法叫做PEP（悲观剪枝）把一颗子树（具有多个叶子节点）用一个叶子节点来替代的话，比起REP剪枝法，它不需要一个单独的测试数据集。
本例中既有预剪枝又有后剪枝。一般来说都是结合着使用。
scikit-learn随机森林
待解决问题，在scikit-learn的随机森林中如何决定k值。
https://github.com/zdkswd/MLcode/blob/master/scikit-learn-code/scikit-learn%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97.py
百面机器学习
树形结构与销售诊断等场景下的决策过程十分相似。
问题1 决策树有哪些常用的启发函数？
问：常用的决策树算法有ID3，C4.5，CART，它们构件树所使用的启发式函数各是什么，除了构建准则外，它们之间的区别与联系是什么？
答： ID3-最大信息增益 C4.5-最大信息增益比 CART-最大基尼指数
ID3采用信息增益作为评价标准，除了一些逆天特征（如与分类结果保持一致的特征）会倾向于取值较多的特征，因为信息增益反映的是给定条件以后不确定性减小的程度，特征取值越多就意味着确定性越高，也就是信息增益越大。这在实际应用中是一个缺陷。这种分类的泛化能力是非常弱的。因此C4.5实际上是对ID3进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力。
从样本角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量时，通过对数据排序后找到类别不同的分割点作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换为布尔型，从而将连续型变量转换为多个取值区间的离散型变量。而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量。
从应用角度，ID3和C4.5只能用于分类任务，而CART可以用于分类也可以用于回归。（回归使用最小平方误差准则）
从实现细节，优化过程等角度，三种决策树有所不同。ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理。ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，因此最后形成一颗二叉树，且每个特征可以被重复使用。ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的数结构进行对比。
如何对决策树进行剪枝
问：决策树的剪枝通常有两种方法，预剪枝与后剪枝，各自是如何进行的？又各有什么优缺点？
答：预剪枝具有思想简单，算法简单，效率高等特点，适合解决大规模问题。但如何准确地估计何时停止树的生长（例如确定深度或阈值），针对不同问题会有很大的差别，需要一定经验判断。且预剪枝存在一定局限性，有欠拟合的风险。
后剪枝的核心思想是让算法生成一颗完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点代替，该结点的类别同样按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝。相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大。
剪枝过程在决策树模型中占据着及其重要的位置。有很多研究表明，剪枝比树的生成过程更为关键。对于不同划分标准生成的过拟合决策树，在经过剪枝后都能保留最重要的属性划分，因此最终的性能差距并不大。理解剪枝方法的理论，在实际应用中根据不同的数据类型，规模，决定使用何种决策树以及对应的剪枝策略，灵活变通，找到最优选择。
常见的后剪枝方法包括REP，PEP，MEP，CVP，OPP等方法，这些剪枝方法各有利弊，关注不同的优化角度。