0.概述
1.决策树(Decision Tree,DT)分类算法
决策树是一种常见的分类与回归模型，主要呈树结构，每一个节点代表一个集合，一条边代表一种属性，而叶子节点则表示对应的类别或值。根据节点分裂规则的不同，主要分为三种方法。
ID3算法
ID3算法采用的是选择一个特征使得分裂前后样本集合的不确定性降低最大，也就是信息增益最大。
计算方式：g(D,A)=H(D)-H(D/A)。H(D)表示分裂前对应样本集合的经验熵，而H(D/A)表示在A特征划分下的样本经验熵，也就是由特征A进行子集划分后的经验熵之和。
ID3算法采用信息增益最大的方式，对于一个节点而言，其对应的样本集合如果所有的类别不是一类，且样本集合不为空，逐个选择特征计算信息增益，选择最大的信息增益，如果其信息增益大于阈值，则按照对应的特征进行样本划分（分裂），然后对每个子节点和样本，循环上述的方法，否则停止。
C4.5算法
C4.5算法是ID3算法的改进，由于ID3计算方式会导致选择特征时倾向于选择值较多的特征，C4.5引入了信息增益比的方式。即当前特征下计算的信息增益除以此特征对应的经验熵，基于C4.5的决策树的生产方式与上述类似。
剪枝规则：剪枝的思想就是比较当前节点的下对应的整棵决策树的损失函数，与返回到其父节点上对应的损失函数，当父节点下对应的损失函数比子节点下的损失函数更小时，可以进行剪枝，将父节点变为叶子节点，去掉其子节点。至于决策树的损失函数，是各个叶子节点上的经验熵与节点样本数之积的总和，加上aT，T为叶子节点数。其中前半部分用于表征决策树的训练误差，而aT则代表了决策树的复杂程度。根据剃刀准则，只有在训练误差足够下的同时，模型也足够简单，这样的模型才是最好的，能够防止过拟合。
CART算法
CART算法也是对分裂规则进行改进，可以用来进行分类与回归，能够处理连续的数据。CART分类规则是选择特征A，使得划分前后基尼系数比的降低最大，也就是划分后左右节点的基尼系数之和最小。
在使用CART树进行回归时，可以采用基于方差的形式，由于回归时标签都是连续值，因此使用方差较为合适。即分别挑选一个特征，基于此特征下，逐个遍历特征值，将样本划分为左右子集（2层循环，第一层为特征数，第二层为某个特征对应的取值），计算左右子集的方差之和，找到所有的特征下特征值对应的方差最小的那个特征和特征值，作为划分特征和阈值，进行节点的分裂。CART树的生成方式是二叉树的形式，与上述两种方法有些微不同。但是大体的步骤相同。
剪枝规则：采用的是分别记录由根节点到各个节点下对应的决策树的损失函数序列，找到在设定值a下决策树对训练数据的预测误差最小对应的树结构。
2.随机森林(RandomForests/RandomTrees)
随机森林类似bagging思想，对样本进行多次采用，并以此生成多颗决策树，通过投票获得判别结果。
随机森林中的每棵树与决策树的区别：主要包括3点：
1）.样本随机采样:n=2/3*N;就是说对训练样本而言，每棵树从样本集中采用大约2/3的样本进行决策树的训练；
2）.特征随机抽取：k<<K;对于样本集中的特征，不是逐个遍历所有的特征进行划分，而是在所有的特征中随机选择k个特征，从这k个特征中找到最优的划分特征，以此对节点的样本进行划分，因此用过的特征可能还会出现。
3）.无剪枝：由于随机森林在进行训练样本选择时是随机抽样的，选择划分特征时也是随机的，因此不需要进行剪枝。
OBB无偏估计：一般对于所有的训练样本，抽取2/3的样本数进行决策树的训练，那么大约有1/3的样本没有被抽取到，由limN-∞ (1-1/N)^N求得。这些样本成为袋外样本，利用这些样本对随机森林中的决策树进行预测误差的估计，称为obb无偏估计。
3.霍夫森林(HoughForests)
主要用来进行目标检测，也有人用来进行头部姿态估计。它与随机森林相比，往往还需要每个样本到目标中心的距离值，作为额外的输入。
对于分裂规则：对于样本集合，包括特征、标签以及中心距离，首先生成二值测试特征集，对于当前节点的样本集，选择一个二值测试特征集中的一个特征，将样本集划分为两个子集{0,1}，对于0、1子集，分别随机选择类别不确定规则与位置不确定规则（可进行分类或回归，CART规则）计算总误差。遍历所有的二值测试集中的特征，找到最小的总误差对应的二值测试特征，将当前节点的样本集进行左右划分。此外当达到停止条件时就停止分裂。
4.Boosting算法
Boosting算法是一种把若干个分类器整合为一个分类器的方法，在boosting算法产生之前，还出现过两种比较重要的将多个分类器整合为一个分类器的方法，即boostrapping方法和bagging方法。boosting算法的思想受到bootstraping思想和bagging想的启发而产生，大致原理是通过训练多个分类器作为一个模型，提升决策能力。我们先简要介绍一下bootstrapping方法和bagging方法。
(1)boosttraping ：是一种样本抽样方式，对一个样本集N，只采样其中的一部分子样本m个，放入模型中去学习，一般是有放回的抽样。跟随机森林中的样本随机选取一样。
主要步骤：
i)重复地从一个样本集合D中采样n个样本
ii)针对每次采样的子样本集，进行统计学习，获得假设Hi
iii)将若干个假设进行组合，形成最终的假设Hfinal
iv)将最终的假设用于具体的分类任务
(2)bagging：其思想是指对一个样本集N，分别抽样m个子集合，每个子集分别对应一个模型进行训练。最后的输出结果为各个模型的结果投票。即对分类问题，各个类别结果相加取最大，对于回归问题，各模型输出的平均值。
主要思路:
i)训练分类器
从整体样本集合中，抽样n* < N个样本 针对抽样的集合训练分类器Ci。
ii)分类器进行投票，最终的结果是分类器投票的优胜结果。
述这两种方法，都只是将分类器进行简单的组合，实际上，并没有发挥出分类器组合的威力来。直到1989年，Yoav Freund与 Robert Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而获得了2003年的哥德尔奖（Godel price）。
Schapire还提出了一种早期的boosting算法，其主要过程如下：
i)从样本整体集合D中，不放回的随机抽样n1 < n 个样本，得到集合 D1
训练弱分类器C1
ii)从样本整体集合D中，抽取 n2 < n 个样本，其中合并进一半被 C1 分类错误的样本。得到样本集合 D2
训练弱分类器C2
iii)抽取D样本集合中，C1 和 C2 分类不一致样本，组成D3
训练弱分类器C3
iv)用三个分类器做投票，得到最后分类结果
到了1995年，Freund and schapire提出了现在的adaboost算法，其主要框架可以描述为：
i)循环迭代多次
更新样本分布
寻找当前分布下的最优弱分类器
计算弱分类器误差率
ii)聚合多次训练的弱分类器
现在，boost算法有了很大的发展，出现了很多的其他boost算法，例如：logitboost算法，gentleboost算法等等。我们将着重介绍adaboost算法的过程和特性。
5.Adaboost算法
Adaboost算法能够进行实际应用的boosting算法。
Adaboost算法主要步骤：
a.初始化样本的权值为1/n。
b.基于样本与权值训练弱分类器；这里的弱分类器就是个二分类器。
c.根据分类器对样本进行判别，如果判别正确，此样本的权值降低，判别错误，降低样本的权值，同时根据识别率计算出此分类器的权值。
d.利用改变权值的样本训练下一个分类器；
e.循环得到N个分类器与其对应的权值；
f.基于加权的分类器组合成为最终的模型。
Adaboost算法模型简单，不容易过拟合，无需调参，优点挺多。但是其实也是需要根据样本类型来使用。
Adaboost的特点
1）每次迭代改变的是样本的分布，而不是重复采样（re weight)
2）样本分布的改变取决于样本是否被正确分类
总是分类正确的样本权值低
总是分类错误的样本权值高（通常是边界附近的样本）
3）最终的结果是弱分类器的加权组合
权值表示该弱分类器的性能
Adaboost的优点:
1)adaboost是一种有很高精度的分类器
2)可以使用各种方法构建子分类器，adaboost算法提供的是框架
3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单
4)简单，不用做特征筛选
5)不用担心overfitting！
6.多分类Adaboost
在日常任务中，我们通常需要去解决多分类的问题。而前面的介绍中，adaboost算法只能适用于二分类的情况。因此，在这一小节中，我们着重介绍如何将adaboost算法调整到适合处理多分类任务的方法。
目前有三种比较常用的将二分类adaboost方法:
1、adaboost M1方法
主要思路： adaboost组合的若干个弱分类器本身就是多分类的分类器。
在训练的时候，样本权重空间的计算方法不变，在解码的时候，选择一个最有可能的分类
2、adaboost MH方法
主要思路： 组合的弱分类器仍然是二分类的分类器，将分类label和分类样例组合，生成N个样本，在这个新的样本空间上训练分类器。
3、对多分类输出进行二进制编码
主要思路：对N个label进行二进制编码，例如用m位二进制数表示一个label。然后训练m个二分类分类器，在解码时生成m位的二进制数。从而对应到一个label上。
最后，我们可以总结下adaboost算法的一些实际可以使用的场景：
1）用于二分类或多分类的应用场景
2）用于做分类任务的baseline
无脑化，简单，不会overfitting，不用调分类器
3）用于特征选择（feature selection)
4）Boosting框架用于对badcase的修正
只需要增加新的分类器，不需要变动原有分类器
由于adaboost算法是一种实现简单，应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器，同时具有分类错误率上界随着训练增加而稳定下降，不会过拟合等的性质，应该说是一种很适合于在各种分类场景下应用的算法。
7.GBD
误差函数的梯度。根据第一个模型可以写出对应的误差函数，通过最小化误差函数得到第一个模型的参数，此时再加入第二个模型，形成新的误差函数，此时模型一的参数已知了，通过最小化新的误差函数，得到第二个模型的参数。在每次得到的误差函数，对每个模型的参数的导数，为误差函数的梯度。
8.GBDT
GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。
GBDT主要由三个概念组成：Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage (算法的一个重要演进分枝，目前大部分源码都按该版本实现）。搞定这三个概念后就能明白GBDT是如何工作的。
DT(回归树)
决策树分为两大类，回归树和分类树。GBDT中的树都是回归树，不是分类树。回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值。
以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和 除以 N。
GB(梯度迭代)
GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。
比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。这就是Gradient Boosting在GBDT中的意义
那么哪里体现了Gradient呢？其实回到第一棵树结束时想一想，无论此时的cost function是什么，是均方差还是均差，只要它以误差作为衡量标准，残差向量(-1, 1, -1, 1)都是它的全局最优方向，这就是Gradient。
讲到这里我们已经把GBDT最核心的概念、运算过程讲完了！没错就是这么简单。不过讲到这里很容易发现三个问题：
1）使用回归决策树和GBDT有时最终效果相同，为何还需要GBDT呢？
答案是过拟合。过拟合是指为了让训练集精度更高，学到了很多”仅在训练集上成立的规律“，导致换一个数据集当前规律就不适用了。其实只要允许一棵树的叶子节点足够多，训练集总是能训练到100%准确率的（大不了最后一个叶子上只有一个instance)。在训练精度和实际精度（或测试精度）之间，后者才是我们想要真正得到的。
2）Gradient呢？不是“G”BDT么？
到目前为止，我们的确没有用到求导的Gradient。在当前版本GBDT描述中，的确没有用到Gradient，该版本用残差作为全局最优的绝对方向，并不需要Gradient求解.
3）这不是boosting吧？Adaboost可不是这么定义的。
这是boosting，但不是Adaboost。GBDT不是Adaboost Decistion Tree。就像提到决策树大家会想起C4.5，提到boost多数人也会想到Adaboost。Adaboost是另一种boost方法，它按分类对错，分配不同的weight，计算cost function时使用这些weight，从而让“错分的样本权重越来越大，使它们更被重视”。Bootstrap也有类似思想，它在每一步迭代时不改变模型本身，也不计算残差，而是从N个instance训练集中按一定概率重新抽取N个instance出来（单个instance可以被重复sample），对着这N个新的instance再训练一轮。由于数据集变了迭代模型训练结果也不一样，而一个instance被前面分错的越厉害，它的概率就被设的越高，这样就能同样达到逐步关注被分错的instance，逐步完善的效果。Adaboost的方法被实践证明是一种很好的防止过拟合的方法，但至于为什么则至今没从理论上被证明。GBDT也可以在使用残差的同时引入Bootstrap re-sampling，GBDT多数实现版本中也增加的这个选项，但是否一定使用则有不同看法。re-sampling一个缺点是它的随机性，即同样的数据集合训练两遍结果是不一样的，也就是模型不可稳定复现，这对评估是很大挑战，比如很难说一个模型变好是因为你选用了更好的feature，还是由于这次sample的随机因素。
Shrinkage(缩减)
Shrinkage的思想认为，每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。本质上，Shrinkage为每棵树设置了一个weight，累加时要乘以这个weight，但和Gradient并没有关系。这个weight就是step。就像Adaboost一样，Shrinkage能减少过拟合发生也是经验证明的，目前还没有看到从理论的证明。
9.GBDT的适用范围
该版本GBDT几乎可用于所有回归问题（线性/非线性），相对logistic regression仅能用于线性回归，GBDT的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。
参考：
http://baidutech.blog.51cto.com/4114344/743809/
http://blog.csdn.net/tianxiaguixin002/article/details/47701881