随机森林

单颗决策树缺点：易过拟合的缺点
传统机器学习处理过拟合通常采用集成学习 (多颗树投票)

随机森林的生成方法【在bagging的基础上+CART树】：
1.从总数为N样本集中通过重采样的方式产生n个样本 (Bootstrap)
2.假设样本特征数目为a，对n个样本选择其中k个特征， 用建立决策树的方式获得最佳分割点
3.重复m次，产生m棵决策树
4.对于分类问题，按多棵树分类器投票决定最终分类结果；
对于回归问题，由多棵树预测值的均值决定最终预测结果

随机森林的随机性
1、每棵树的训练样本是随机的。
2、每棵树的训练特征集合也是随机从所有特征中抽取的。
两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）

使用随机森林去弥补特征向量中的缺失值
对于训练集中的缺失值，可以使用均值，0等方式进行预填充，然后使用随机森林分类，**同一个分类下的数据，更新缺失值，**如果是分类变量缺失，用众数补上，如果是连续型变量缺失，用中位数补上，然后再次使用随机森林分类更新缺失值，4-6轮后可以达到一个比较好的效果。

使用随机森林对特征重要性进行评估
详见集成学习ensemble之随机森林。利用了袋外错误率OOB来做决策。

随机森林为什么不能用全样本去训练m颗决策树
全样本训练忽视了局部样本的规律（各个决策树趋于相同），对于模型的泛化能力是有害的，使随机森林算法在样本层面失去了随机性。

随机森林分类效果（错误率）与两个因素有关：
森林中任意两棵树的相关性：相关性越大，错误率越大；
森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。
减小特征选择个数m，树的相关性和分类能力也会相应的降低；
增大m，两者也会随之增大。
所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。

OOB（Out Of Bag）袋外错误率
在bootstrapping的过程中，有些数据可能没有被选择，这些数据称为out-of-bag(OOB) examples。

1/N：每次抽样的概率
OOB：不管如何，总是接近于1/e

袋外错误率的应用
在随机森林中，有了out-of-bag(OOB) examples，我们就不需要拿出一部分数据了，out-of-bag(OOB) examples就是那部分没有用到的数据，我们可以直接当成验证集来使用。
obb error = 被分类错误数 / 总数
随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计。
Breiman [1996b]在对 bagged 分类器的错误率估计研究中, 给出实证证据显示，out-of-bag 估计 和使用与训练集大小一致的测试集所得到的错误率一样精确. 所以, 使用out-of-bag error 估计可以不在另外建立一个测试集.

关于调参：
1.如何选取K，可以考虑有N个属性，取K=根号N
2.最大深度（不超过8层）
3.棵数
4.最小分裂样本树
5.类别比例

随机森林的优点
具有极高的准确率
引入两阶段随机 防止过拟合很好的抗噪声能力
既能处理离散型数据，也能处理连续型数据，数据集无需规范化
训练可以高度并行化且性能普遍较好，对于大数据时代的大样本训练速度有优势
能处理很高维度的数据，并且不用做特征选择
训练速度快
可以得到变量重要性排序
能有效处理缺失值，就算存在大量的数据缺失，随机森林也能较好地保持精确性，一方面因为随机森林随机选取样本和特征，另一方面因为它可以继承决策树对缺失数据的处理方式。如果缺失数据的样本只是少量，随机森林甚至可以帮助去估计缺失值。
由于采用了随机采样，训练出的模型的方差小，对generlization error(泛化误差)使用的是无偏估计模型，泛化能力强
对于不平衡数据集来说，随机森林可以平衡误差。当存在分类不平衡的情况时，随机森林能提供平衡数据集误差的有效方法。（对正类和反类分别进行重采样或欠采样,

随机森林的缺点：
当随机森林中的决策树个数很多时，训练时需要的空间和时间会较大
对于许多统计建模者来说，随机森林给人的感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的参数和随机种子之间进行尝试。

可能有很多相似的决策树，掩盖了真实的结果
对于小数据或者低维数据（特征较少的数据），可能不能产生很好的分类（随机性大大降低了）。（处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的长处）

执行数据虽然比boosting等快（随机森林属于bagging），但比单只决策树慢多了，且精度一般不如boosting方法

随机森林在解决回归问题时，并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续的输出。当进行回归时，随机森林不能够做出超越训练集数据范围的预测，这可能导致在某些特定噪声的数据进行建模时出现过度拟合。（PS:随机森林已经被证明在某些噪音较大的分类或者回归问题上会过拟合）。

随机森林为什么不容易过拟合
随机森林由很多树组合在一起，单看每一棵树都可以是过拟合的，但是，既然是过拟合，就会拟合到非常小的细节上，因此随机森林通过引入随机性，让每一棵树拟合的细节不同，这时再把这些树组合在一起，过拟合的部分就会自动被消除掉。
所以随机森林不容易过拟合，但这不是绝对的，随机森林也是有可能出现过拟合的现象，只是出现的概率相对低。
就好比人类社会，有计算机的专家，也有神经生物学的专家，还有一个天文学的专家，这就像三颗过拟合的树，对于各自领域性能都很优秀，但对于宗教这类知识，三个人都不是很懂。由于三个人都处在同一个社会中，在社会中长久下来也有或多或少的接触过这方面的知识，于是三个人可以通过综合判断，得出宗教方面的一些正确答案。
当在随机森林中，如果我们用了远大于需求个数的树，就会发生过拟合的现象。所以一般在构建随机森林时我们会使用oob袋外错误率来修正模型的结构。

随机森林算法训练时主要需要调整哪些参数
1、n_estimators：随机森林建立子树的数量。较多的子树一般可以让模型有更好的性能，但同时会让代码变慢，严重的时候甚至还会导致过拟合！故需要通过交叉验证或者袋外错误率oob估计来选择最佳的随机森林子树数量。
2、max_features：随机森林允许单个决策树使用特征的最大数量。增加max_features一般能提高模型的性能，因为在每个树节点上，我们有更多的选择可以考虑。然而，这未必完全是对的，因为它降低了单个树的多样性（泛化能力），但这正是随机森林的一大特点。可以肯定的是，增加max_features会降低算法的速度，同时还会使得模型更加容易过拟合，因此，我们需要适当的平衡和选择最佳的max_features。
3、max_depth：决策树的最大深度。随机森林默认在决策树的建立过程中不会限制其深度，这也是随机森林的一大特点，其不必担心单棵树的过拟合。
4、min_samples_split：内部节点再划分所需要的最小样本数。如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。
5、min_samples_leaf：叶子节点最少样本数。这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。
6、max_leaf_nodes：最大叶子节点数。通过限制最大叶子节点数，可以防止过拟合，默认是“None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。
7、min_impurity_split：节点划分最小不纯度。这个值限制了决策树的增长，如果某节点的不纯度（基于基尼系数，均方差，信息增益等）小于这个阈值，则该节点不再生成子节点。即为叶子节点。一般不推荐改动，默认值为1e-7。
概括一下，别看有整整7点，其实后5点全都是预剪枝的策略，在随机森林中，如果实在是为了防止过拟合等，可以采取预剪枝策略也就是上述的3-7方法。但对于随机森林这个模型而言，真正要调整的参数就n_estimators和max_features两个，而且在一般情况下，不需要怎么调就可以得到不错的结果。

GBDT

gbdt全称梯度下降树，

训练过程
gbdt通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练。
弱分类器一般会选择为CART TREE（也就是分类回归树）。由于上述高偏差和简单的要求 每个分类回归树的深度不会很深。最终的总分类器 是将每轮训练得到的弱分类器加权求和得到的（也就是加法模型）。
模型一共训练M轮，每轮产生一个弱分类器 ，gbdt 通过经验风险极小化来确定下一个弱分类器的参数。具体到损失函数本身的选择也就是L的选择，有平方损失函数，0-1损失函数，对数损失函数等等。如果我们选择平方损失函数，那么这个差值其实就是我们平常所说的残差。

1.是希望损失函数能够不断的减小，
2.是希望损失函数能够尽可能快的减小。
所以如何尽可能快的减小呢？让损失函数沿着梯度方向的下降。这个就是gbdt 的 gb的核心了。

gbdt如何选择特征？
gbdt选择特征的细节其实是想问你CART Tree生成的过程。
gbdt的弱分类器默认选择的是CART TREE。其实也可以选择其他弱分类器的，选择的前提是低方差和高偏差。框架服从boosting 框架即可。

CART TREE 生成的过程其实就是一个选择特征的过程。
假设我们目前总共有 M 个特征。
第一步我们需要从中选择出一个特征 j，做为二叉树的第一个节点。
然后对特征 j 的值选择一个切分点 m.
一个样本的特征j的值如果小于m，则分为一类，
如果大于m,则分为另外一类。如此便构建了CART 树的一个节点。
其他节点的生成过程和这个是一样的。
现在的问题是在每轮迭代的时候，如何选择这个特征 j,以及如何选择特征 j 的切分点 m:
原始的gbdt的做法非常的暴力，首先遍历每个特征，然后对每个特征遍历它所有可能的切分点，找到最优特征 m 的最优切分点 j。
如何衡量我们找到的特征 m和切分点 j 是最优的呢？ 我们用定义一个函数：

gbdt 如何构建特征 ?
gbdt 本身是不能产生特征的，但是我们可以利用gbdt去产生特征的组合。
在CTR预估中，工业界一般会采用逻辑回归去进行处理,在我的上一篇博文当中已经说过，逻辑回归本身是适合处理线性可分的数据，如果我们想让逻辑回归处理非线性的数据，其中一种方式便是组合不同特征，增强逻辑回归对非线性分布的拟合能力。
Facebook 在2014年 发表的一篇论文便是这种尝试下的产物，利用gbdt去产生有效的特征组合，以便用于逻辑回归的训练，提升模型最终的效果。

GBDT 如何用于分类 ？
首先明确一点，gbdt 无论用于分类还是回归一直都是使用的CART 回归树。不会因为我们所选择的任务是分类任务就选用分类树，这里面的核心是因为gbdt每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候，弱分类器的输出的结果相减是有意义的。残差相减是有意义的。

如果选用的弱分类器是分类树，类别相减是没有意义的。上一轮输出的是样本 x 属于 A类，本一轮训练输出的是样本 x 属于 B类。 A 和 B 很多时候甚至都没有比较的意义，A 类- B类是没有意义的。

我们具体到分类这个任务上面来，我们假设样本 X 总共有 K类。来了一个样本 x，我们需要使用gbdt来判断 x 属于样本的哪一类。

其实我们可以用一个k维向量 [0,1,0] 来表示。0表示样本不属于该类，1表示样本属于该类。针对样本有k类的情况，我们实质上是在每轮的训练的时候是同时训练k颗树。

为何GBDT受人青睐
缺失数据处理：Decision Tree 可以很好的处理 missing feature，这是他的天然特性，因为决策树的每个节点只依赖一个 feature，如果某个 feature 不存在，这颗树依然可以拿来做决策，只是少一些路径。像逻辑回归，SVM 就没这个好处。

Decision Tree 可以很好的处理各种类型的 feature，也是天然特性，很好理解，同样逻辑回归和 SVM 没这样的天然特性。

对特征空间的 outlier 有鲁棒性，因为每个节点都是 x <