集成算法往往被称为三个臭皮匠，赛过一个诸葛亮，集成算法的起源是来自与PAC中的强可学习和弱可学习，如果类别决策边界可以被一个多项式表示，并且分类正确率高，那么就是强学习的，如果分类正确率不高，仅仅只是比随机猜测好一点，那么就是弱可学习，后来有人证明强可学习和弱可学习是等价的，那么弱可学习就可以提升为强可学习，集成就是其中一个方法。本文的代码都在我的github。
引言
不过三个臭皮匠真的能赛过一个诸葛亮吗？很明显不是，一个科研专家并不是几个普通人就能比得上的，很多时候，一个人能比得上千军万马，而且这里的皮匠是裨将的意思，也就是副将，他们可以从不同的角度来指出问题的所在，这才能抵得上只在大营中的诸葛亮。那么多个学习器的组合，真的能获得比最好的单一学习器更好的性能吗？生活中总说不怕神一样的队友，只怕猪一样的队友，这里的单一学习器最好是好而不同，这就是集成算法的俩个核心，就是准确性和多样性，那么满足了好而不同就能更好吗？在实验中，训练数据往往并不能包含全部的数据情况，在数据不充分的条件下，如果我们从不同的假设空间角度来学习或者学习到不同数据分布的假设，并且学习的都是正确的，那么就能从多角度来看待问题，这样就能减小错误的风险了。所以并不是随便几个算法集成起来就能够得到一个更好的结果，这几个算法必须要多样并且准确。
但是准确性和多样性是存在冲突，准确率很高之后，再提升多样性就会牺牲准确率，因为准确率高了之后，说明模型与训练数据分布的偏差很低了，这时的模型往往就会固定成一个样子，因而就没有多样性，泛化能力就降低了，方差就会变大，这也是集成算法的核心问题，偏差小了，方差自然就大，大白话就是在训练数据上的准确率很高的话，在测试数据上的准确率就不行了，没有很强的泛化能力，产生过拟合现象。那么从降低方差和降低偏差的俩个角度来看，自然就有了俩种思路bagging和boosting。补充一下偏差和方差，偏差指的是算法的期望预测与真实预测之间的偏差程度，反应了模型本身的拟合能力；方差度量了同等大小的训练集的变动导致学习性能的变化，刻画了数据扰动所导致的影响。
bagging
如果模型偏差小，方差很大，比如不剪枝的决策树就容易过拟合，那么如何降低方差，自然要从多样性入手，多样性有俩种分别是数据多样性和模型多样性。对于数据多样性，在面对同一堆数据，可以采用有放回的采样，就是随便选择一个数据，再把数据放回到数据集，之后再选择。这样重复并且重叠的采样方式产生了样本扰动，具有了多样性。对于模型多样性，采用的都是性能较好的相互独立的分类器，这里的相互独立非常重要，这就让模型之间没有了依赖关系，每个人都可以从自己的角度来思考问题。那么我们就可以使用有放回的采样得到多个数据集，用这些数据集分别训练多个独立模型，再将这些模型的结果结合，这就是Bagging的基本思想了。过程可以看下图
之前讲过决策树算法，决策树算法就是易受数据的扰动，这个其实就是决策树过拟合的表现。之前也说过这种过拟合的表现其实也被称为偏差小，方差大。如果对决策树进行bagging的话，就会形成random forest。
随机森林(random forest)
随机森林就是以决策树为基学习器构建bagging集成的基础上，进一步在决策树训练过程中引入随机属性选择。就是每个基分类器都是决策树，但是基决策树的特征选择都是从该特征集合中随机一个子集，从子集中选出最优的，这种属性扰动生成的每个决策树都是独立并且不同，就能做到模型多样性。之后使用有放回的采样数据，形成每个决策树的训练数据，这样就能做到了样本扰动。这样不同数据，随机属性生成的多个决策树就能满足集成算法的要求。
在之前我实现的随机森林中，对于特征的随机选择，有俩种思路，一种就是每一个结点都是随机选择一些特征，选择其中最好的特征，通常是log2d，还有一种就是也可以每棵树只选择固定的特征子集来选择。对于实现，我的代码中使用的就是第二种，对每棵树选出特征子集来对树进行创建。
// 提取数据
dataSet,labelSet = dataSE.extractData()
#森林中数的个数
numTree = 50
#森林
forest = []
#查看每个数据的选中情况
choiceDataNum = [0 for i in range(len(dataSet))]
#建立每棵决策树
for i in range(numTree):
#首先选出数据集和特征子集
childData,chidFeatures,noUseData = randomSample(dataSet,labelSet)
#建立决策树
childTree = Tree.buildTree(childData,chidFeatures)
Tree.printTree(childTree)
forest.append(childTree)
for i in range(len(noUseData)):
choiceDataNum[i] += noUseData[i]
testData = produceData(choiceDataNum,dataSet)
results = []
correct = 0
#开始测试每个测试集
for data in testData:
results = []
for tree in forest:
result = Tree.classify(data,tree,labelSet)
#print(list(result.keys()))
results.append(list(result.keys()))
#print(results)
feaNum = 0
noFeaNum = 0
resultData = 'feafits'
#采用投票法，票数最多的就是类别
for i in range(len(results)):
#print('result[i]',results[i])
if results[i][0] == 'feafits':
feaNum += 1
else:
noFeaNum += 1
#print(feaNum,noFeaNum)
if feaNum < noFeaNum:
resultData = 'nofeafits'
print('结果是',resultData)
results.append(resultData)
print('实际结果是：',data[-1])
if resultData == data[-1]:
correct += 1
ccur = (correct / len(testData))*100
print('精确度:',ccur)
boosting
boosting方法是关注偏差，基于性能相当弱的简单学习器构建出很强的集成。它不像bagging，各学习器都是独立的，它的学习器之间具有很强的依赖关系，这是因为它关注的是降低偏差，所以它做的就是每次都会在上一轮基础上更加拟合原数据，这样就可保证偏差，既然训练过程出来的模型能够保证偏差，那么需要选择方差更小的单个学习器，就是更简单的学习器。我们也可以看成它是通过不断地调整样本分布来训练学习器，使得学习器针对不同的训练数据分布，它更像每个人就只学习一种技能，最后大家合在一起使用干活，少了谁都不行。
有一些算法是通过调整数据权重来调整样本分布的，而数据权重是通过loss调整。但是在这个思想基础下，有着俩个不同的想法，第一个就是如果样本训练的不够好，也就是模型无法拟合这个数据，那么对于这个样本要给予更高的权重，这类工作就是hard negative mining和focal loss，第二个想法就是从易到难学习，慢慢增加难度，最终如果还有样本的loss依旧很大，那么认为这类样本是离群点，强行拟合很容易造成性能的下降，这类工作就是curriculum learning和self-paced learning。可以看出这俩种算法思想基本上是完全相反，第一类认为模型拟合不好的数据，应该尽力去fit，第二种认为模型拟合不好的数据，可能是训练的标签有误，这其实是对数据分布的不同假设的缘故，如果感兴趣可以看看这篇文章，而我们的adaboost就是第一种。
adaboost
adaboost通过调整数据权重来不断地调整样本分布，并且使用的是增大分类错误的样本权重，使后面的学习器更加关注那些分类错误的数据，按照这样的过程重复训练出M个学习器，最后进行加权组合，它更像我们高中时期记错题到错题集中，然后在错题集上反复做的过程。具体算法过程如下图所示
从上面看出我们需要更新数据权重，还需要得到各学习器的权重进行结合。这里就有了俩个问题，如何更新数据权重？如何确定各学习器的权重？那么我们就推导一下这个算法是如何出来的，首先假设的就是模型为加法模型，损失函数是指数损失。
先来看我们的模型函数就是\(f(x) = \sum\limits_{m=1}^M\alpha_mG_m(x)\)，指数损失函数就是\(L(y,f(x)) = e^{-yf(x)}\)，假设模型在m次迭代中，前m-1个系数\(\alpha\)和基学习器\(G(x)\)都是固定的，那么模型函数就会变成\(f_m(x) = f_{m-1}(x) + \alpha_mG_m(x)\)，这样的话，最小化损失函数与\(\alpha_m\)和\(G_m(x)\)有关。那么现在我们的目标就是损失函数最小的时候，求出\(\alpha_m\)和\(G_m(x)\)的值，公式表示如下
这里的N就是N个训练数据\(((x_1,y_1),(x_2, y_2),...(x_N, y_N))\)。
我们设置\(w_i^m = e^{-y_i(f_{m-1}(x_i))}\)，代入其中
之后我们将整个数据集分成俩部分，一部分是分类正确的，还有一部分是分类错误的
下面将之转化成只有\(y \neq G_m(x)\)的数据
这里最终的式子可以看出最小化损失函数就是最小化带权误差率，误差率就是\(\epsilon_m = \frac{\sum\limits_{y \ne G_m(x)}w_i^m}{\sum\limits_{n=1}^Nw_i^m}\)，我们对最终的式子求\(\alpha_m\)导数使之等于0就能得到
式子的俩边同时乘以\(e^{\alpha_m}\)可以得到
我们可以根据误差率式子\(\epsilon_m = \frac{\sum\limits_{y \ne G_m(x)}w_i^m}{\sum\limits_{n=1}^Nw_i^m}\)，将上面的式子进行化简
这里我们就得到了分类器的权重\(\alpha_m = \frac{1}{2}ln\frac{1 - \epsilon_m}{\epsilon_m}\)，我们再回头看我们的模型函数\(f_m(x) = f_{m-1}(x) + \alpha_mG_m(x)\)，从\(w_i^m = e^{-y_i(f_{m-1}(x_i))}\)，我们可以转化成\(w_i^{m+1} = e^{-y_i(f_m(x_i))}\)，带入其中就是
我们知道\(w_i^m = e^{-y_i(f_{m-1}(x_i))}\)，带入其中就是
最终再加入一个规范化因子\(Z_m\)，使得\(w^{m+1}\)成为一个概率分布
其中规范化因子就是
这样就得到了权重的更新公式就是\(w_i^{m+1} = \frac{w_i^m}{Z_m}e^{-y_i\alpha_mG_m(x_i)}\)，我们还可以从权重公式\(w_i^{m+1} = w_i^me^{-y_i\alpha_mG_m(x_i)}\)可以看出，如果分类正确，那么\(y_i = G_m(x_i)\)，那么权重的更新就是\(w_i^{m+1} = w_i^me^{-\alpha_m}\)，权重就是在减少，反之就是在增大。
此时我们可以得出adaboost算法的全部过程：
- 设置每个样本的初始权重值
- 将数据、类别和样本权重放入弱学习器中，选出分类效果最好的
（1）根据列来循环，计算出步长，用于后面选择阈值
（2）循环阈值来进行切分，找出最好的那个，并且记录列，阈值，正反
（3）找出所有列中最好的那个阈值返回
补充:这里是只是根据一个维度进行切分，因而每次都是在所有列中选择 - 根据错误率计算alphas，更新权重值，并且计算alpha值
- 将此分类放入弱学习器结果中
- 利用alpha和结果计算值，利用sign来查看错误，错误为0，则完成，否则继续
下面我们再看一个例子来加深一下印象，
我们的基础学习器使用的是树桩决策树。首先初始化每个样本的权重，我们使用的是平均值，那么\(w_i^{1} = 0.1\)，
对m=1，之后根据权重和数据设置基学习器，因为是树桩，我们只要找出阈值使得误差率最低就好了，先找出所有的切分点1.5，2.5，3.5，4.5，5.5，6.5，7.5，8.5，9.5，之后计算所有切分点的误差率，找出最低误差率的时候切分点为2.5，误差率就是\(\epsilon_1 = \frac{0.3}{1} = 0.3\)，
然后根据上面的公式\(\alpha_m = \frac{1}{2}ln\frac{1 - \epsilon_m}{\epsilon_m}\)来求我们得出的这个基分类器的权重，
之后根据上面得到的权重更新公式\(w_i^{m+1} = \frac{w_i^m}{Z_m}e^{-y_i\alpha_mG_m(x_i)}\)，先计算规范化因子\(Z_m\)，它的公式就是\(Z_m = \sum\limits_{i=1}^Nw_i^me^{-\alpha_my_iG_m(x_i)}\)
之后计算\(w_1^2\)
然后依次更新所有数据权重，最后得到(0.07143，0.07143，0.07143，0.07143，0.07143，0.07143，0.16667，0.16667，0.16667，0.07143)，此时的分类器就是\(f_1(x) = 0.4236G_1(x)\)，将这个\(sign(f_1(x))\)来测试所有的训练集，发现错了三个，那么继续更新。
对于 m = 2，先计算所有切分点的误差率，可以得到8.5的时候误差率最低，最低\(\epsilon_2 = \frac{0.07143\times3}{0.07143\times7+0.16667\times3} = 0.2143\)，和上面的过程一样计算基分类器的权重\(\alpha_2 = 0.6496\)，再更新所有数据的权重，此数据上有三个误分类点，此时的分类器就是\(f_2(x) = 0.4236G_1(x) + 0.6496G_2(x)\)，将这个\(sign(f_2(x))\)来测试所有的训练集，发现错了三个，那么继续更新。
对于 m = 3，先计算所有切分点的误差率，可以得到5.5的时候误差率最低，最低\(\epsilon_3 = 0.1820\)，和上面的过程一样计算基分类器的权重\(\alpha_3 = 0.7514\)，再更新所有数据的权重，此数据上有三个误分类点，此时的分类器就是\(f_3(x) = 0.4236G_1(x) + 0.6496G_2(x) + 0.7514G_3(x)\)，将这个\(sign(f_3(x))\)来测试所有的训练集，发现全部正确，那么停止完成。
那么最终的分类器就是
#numIt就是循环次数，返回整个分类器
def adaboostTraining(dataSet,labelSet,numIt = 40):
dataMat = np.mat(dataSet)
ResultMat = np.mat(labelSet).T
weakResult = []
m,n = dataMat.shape
#判断数据是否已经分类好了
result = np.mat(np.zeros((m,1)))
#设置出初始样本权重值
Weights = np.mat(np.ones((m,1))/m)
for i in range(numIt):
#选择最好的弱学习器
stumpClass,errorRate,classResult = choiceBestWeak(dataMat,\
ResultMat,Weights)
#计算出alphas的值,防止错误率为0时
alphas = float(0.5*np.log((1-errorRate)/max(errorRate,1e-16)))
stumpClass['alphas'] = alphas
#放入到结果学习器中
weakResult.append(stumpClass)
#更新样本权重值
temp = np.multiply(-1*alphas*ResultMat,classResult)
#print('temp',temp)
tempTop = np.multiply(Weights,np.exp(temp))
Weights = tempTop/sum(Weights)
#查看是否分类完全正确,全部分类正确就完成
#print('alphas',alphas)
#print('classResult',classResult)
result += alphas*classResult
error = np.multiply(np.sign(result) != ResultMat\
,np.ones((m,1)))
errorR = error.sum()/m
#print('errorR',errorR)
if errorR == 0:
break
return weakResult
那么adaboost为什么要用指数损失函数，可不可以使用其他的损失函数？当然也是可以的，但是如果用了其他的损失函数，推导过程就不同，并且只是boosting家族中的另一个算法而已了，adaboost使用指数损失函数就是计算和表达简单，我们可以从下表看一下换损失函数会变成什么算法。
如果使用adaboost对一些好分割的数据进行分类的话，你会发现，adaboost不会过拟合，并且还会出现一个特别奇怪的现象：当训练集的误差率减小到0的时候，如果你继续增加基础分类器，也就是让算法继续运行下来，它的测试误差率也会下降。这一点周志华老师在2014年的CCL中也讨论过，其中能解释比较清楚的就是Boosting Margin，一组数据它的测试误差率能够达到0，说明数据集比较好分割，margin也就可以看成是它分类的置信度，也许刚开始分类的时候，它只有60%的把握分对，之后再继续训练，就有了80%的把握，margin就可以看成这个置信度，confidence变得越来越大，决策边界自然也会越来越公正，自然结果也更加可靠了，后面SVM还会谈到这个margin。
提升树
提升树是以分类树或者回归树作为基本分类器的提升方法，并且有着大量的引用，一度被认为是与SVM一样具有很强泛化能力的算法。与adaboost使用数据权重不同，普通的提升树是利用残差进行计算的，并且多用于回归问题中，利用最小均方损失函数学习残差回归树。对于它的过程，我们可以先来大概看一下cart回归树的过程，利用最小化均方误差来找出最优属性的最好切分点，首先就是找出一个属性的所有切分点，然后对所有的切分点做均方误差，找出最小误差的那个切分点，计算所有属性的最小切分点，得到最优属性的最好切分点。然后将数据分成俩个分支之后，继续在数据集上寻找最优属性的最好切分点。普通的提升树中的一棵回归树的建立和它一样，都是不断地利用最小化均方误差来找出最优属性的最好切分点，只不过提升树是许多回归树，每颗回归树拟合的数据不同，从一开始的训练数据到之后的残差数据，最后的结果就是所有树的结果加在一起。回归结果与真实结果差距越大的数据，那么下一次残差也越大，这其实也变相的增大了分错的数据权重。提升树说起来很抽象，先来整理一下过程。
- 初始化\(f_0(x) = 0\)，最开始的拟合函数就是0;
- i = 0,1,2...., 进行循环计算残差，\(r_{mi} = y_i - f_{m-1}(x_i)\);
- 通过均方误差拟合数据\(((x_1,r_{m1}),(x_2,r_{m2}),....,(x_i,r_{mi}))\)，学习到一个回归树，得到T(x)
(1). 找出一个属性的所有切分点；
(2). 计算所有切分点的均方误差；
(3). 得到均方误差最小的那个切分点；
(4). 计算出所有属性的最好切分点，之后找出最优属性的最好切分点，作为节点；
(5). 直到每个叶子节点年龄都唯一或者叶子节点个数达到了预设终止条件，如果不唯一，叶子节点的值就是平均值，注意，它并不会删除用过的属性，会循环用； - 更新\(f_m(x) = f_{m-1}(x) + T(x)\);
- 达到循环停止条件，便得到了回归问题提升树\(f_M(x)\);
- 测试的结果就是所有回归树的结果相加。
普通提升树的损失函数是均方误差，残差作为每一轮的损失，而且均方误差能够很好的拟合残差，但是损失函数有很多种，这些一般性的损失函数无法很好的拟合残差。对此，Freidman提出用损失函数的负梯度代替残差作为每一轮损失的近似值，之后通过拟合负梯度每轮产生一个cart回归树。
- 初始化\(f_0(x) = arg\min\limits_c\sum\limits_{i=1}^NL(y_i,c)\)，这个是选取初始值，不同损失函数初始值选取不同，因为它要让损失函数达到最小，经常对损失函数求导等于0来找出c的求解公式，因为是argmin，所以\(f_0(x) = c\)，比如均方差就是平均数;
- i = 0,1,2...., 进行循环计算梯度，\(r_{mi} = -\frac{\partial L(yi, f_{m-1}(x_i))}{\partial x_i}\);
- 通过一般误差函数拟合数据\(((x_1,r_{m1}),(x_2,r_{m2}),....,(x_i,r_{mi}))\)，学习到一个回归树，得到T(x)
(1). 找出一个属性的所有切分点；
(2). 计算所有切分点的一般误差函数；
(3). 得到一般误差函数最小的那个切分点；
(4). 计算出所有属性的最好切分点，之后找出最优属性的最好切分点，作为节点；
(5). 直到每个叶子节点年龄都唯一或者叶子节点个数达到了预设终止条件，如果不唯一，叶子节点的值就是第一步中损失函数求导等于0来得到的值，注意，它并不会删除用过的属性，会循环用； - 更新\(f_m(x) = f_{m-1}(x) + l_rT(x)\)，可以设置一个学习率\(l_r\);
- 达到循环停止条件，便得到了回归问题提升树\(f_M(x)\);
- 测试的结果就是所有回归树的结果相加。
再来看一个例子熟悉一下
如果我们设置生成5棵树，并且每棵树的最大深度为3，学习率\(l_r = 0.1\)，我们使用均方差作为损失函数，这样也能与普通提升树联系起来，那么下面来看过程
第一步就是初始化\(f_0(x) = arg\min\limits_c\sum\limits_{i=1}^NL(y_i,c)\)，直接对均方差损失函数进行求导，并且等于0。
令导数等于0
所以初始化\(c = \frac{1.1+1.3+1.7+1.8}{4} = 1.475 = f_0(x)\)
第二步就是循环计算梯度，先计算本次的梯度就是\(-\frac{\partial L(y_i, c)}{\partial c} = y_i - c\)，将之代入可以得到本次需要拟合的数据。
第三步就是通过一般误差函数拟合上面得到的数据，寻找回归树的最佳属性的最好切分点。先看年龄，分别查找出全部的切分点，分别是6，14，25.5，然后使用误差函数计算误差，切分点6的时候，左边只有数据1，右边有数据7，21，30，先计算出左边的MSE，只有一个数据，那肯定就是0，再计算右边的MSE，先计算期望，\(\frac{-0.175+0.225+0.325}{3} = 0.125\)，然后再将数据与期望相减平方得到MSE，\((-0.175-0.125)^2 + (0.225-0.125)^2 + (0.325-0.125)^2 = 0.14\)，再将俩边的MSE相加就得到了切分点6的\(MSE_6 = 0.14\)，按照这个步骤计算出全部属性的全部切分点的MSE。
选择年龄切分点14作为节点，那么我们的树就是
因为我设置树的深度是3，这里才是2，那么还需要再来一次，先划分左节点，左节点的数据只有0，1，按照上面的步骤计算年龄切分点6和体重切分点25的MSE，
我们选择年龄切分点6，之后同样计算右节点，同样是选择年龄切分点25.5，那么最后的树就是
我们还需要计算出叶子节点的值，我们需要对损失函数求导，等于0，第一步的时候我们就计算出来
那么叶子节点的值就是平均值，我们可以计算出来，那么树就是
第四步更新\(f_1(x) = f_{0}(x) + l_rT(x)\)，可以设置一个学习率\(l_r\)，\(T(x)\)就是这棵树，如果用表达式的话，就是\(f_1(x) = f_{0}(x) + l_r\sum\limits_{j=1}^{4}\Upsilon_{j1}\)
第五步就是不断地循环，然后直到创建了五棵树达到了停止条件，得到最后的回归树，用数学表达就是
第六步就是测试数据，将测试数据放进所有的树中，然后相加起来
如果你在竞赛中使用过它，你就会发现它即使树的深度很浅，但是依旧能够达到很高的精度，但是隔壁的随机森林树的深度却很高，你也许会认为它比随机森林还好，其实这就是俩者的算法特性造成，随机森林降低的就是方差，偏差有基学习器作为保障的，boosting降低的就是偏差，方差是基学习器作为保障的，既然基学习器保障方差，那么基学习器一定不会很深，不然就会过拟合了，方差就会减小的。
其实我们思考思考就会发现残差不就是全局最优方向嘛，而且残差就是均方差损失函数的梯度，那也说明它其实也是一种特殊的梯度。
如果懂了GBDT，那么你再看XGBoost，就能看得懂思想原理了，因为XGBoost本质上就是GBDT的一种高效的工业界实现，外加一些算法上的优化，最主要的就是GBDT是利用的梯度，XGBoost是利用的二阶泰勒展开，更加准确，并且XGBoost还利用了并行化实现和缺失值的处理等等操作。
总结
以前我一直觉得集成算法可以称得上思想和效果都很好的算法，并且从降低方差和偏差角度出发，也能理解它的基本原理，但是你在研究中使用集成算法的时候，要想集成算法效果好的话，就必须要考虑基学习器的选择，当然在竞赛中，很多时候直接使用XGBoost也能得到一个很好的结果。当然集成算法还有思考点，就是如何将所有基学习器的结果结合，这方面也有很多的方法。本文的代码都在我的github。