【机器学习入门二】集成学习及AdaBoost算法的python实现

本文主要基于周志华老师的《机器学习》第八章内容

个体与集成

集成学习通过构建并结合多个学习器来完成学习任务。集成学习的一般结构如图所示：

先产生一组个体学习器，在用某种策略把它们结合在一起。个体学习器通常有一个现有的学习算法从训练数据产生，如决策树桩和BP神经网络。个体学习器可以使相同类型的也可以是不同类型的，比如全是神经网络或者同事含有神经网络和决策树桩。
集成学习通过将多个学习器进行结合，通常可以获得比单一学习器显著优越的泛化性能，尤其是弱学习器（即泛化性能略优于随机猜测的学习器，比如在二分类问题上精度略高于50%的分类器）。从理论上来说，使用弱学习器集成就足以获得好的性能。
如何提高集成学习的性能？这要求个体学习器应该“好而不同”。书上的例子很好且简单易懂，这里直接拿来。
在二分类任务中，假定三个分类器在三个测试样本上的表现分别如下面的三个表所示，
其中对号表示分类正确，叉号表示分类错误，集成策略选择投票法。在（a）中，每个分类器都只有66.6%的精度，但是集成学习后达到了100%，（b）中，三个分类器完全一样，集成后没有区别，（c）中，每个分类器的精度都只有33.3%，集成后结果更差。这个例子直观的解释了为什么应该好而不同，即个体学习器要比较准确，并且各个个体学习器之间还要有一定的差异性。

集成学习根据个体学习器的生成方式可以分为2大类，如果个体学习器存在强依赖关系、必须串行生成的序列化方法，典型代表是Boosting。第二种是个体学习器之间不存在强依赖关系，可以同时生成的并行化方法，如Bagging和随机森林（Random Forest）。

Boosting

Boosting是一族可将弱学习器提升为强学习器的算法。算法的流程为：先从初始训练集训练出一个个体学习器，再根据该学习器的表现对训练样本的分布进行调整，使得先前学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个个体学习器，如此反复进行，直到个体学习器的数量达到事先指定的值T或者集成的误差已经小于阈值，最终将这些个体学习器进行加权结合。

算法流程

Boosting算法族中最著名的是AdaBoost算法。下面是算法的过程：

---

输入：训练集D={(x1,y1),.....,(xm,ym)}$D=\{(x_1,y_1),.....,(x_m,y_m)\}$，基学习算法ξ$\xi$，训练次数T
过程：
1. D1(x)=1/m.${\mathcal{D}}_{\mathcal{1}}\mathcal{(}\mathcal{x}\mathcal{)}\mathcal{=}\mathcal{1}\mathcal{/}\mathcal{m}\mathcal{.}$(表示第一轮时每个样本的权重是相等的)
2. fort=1,2,3,...,Tdo:$fort=1,2,3,...,Tdo:$
3. ht=ξ(D,Dt);$h_t=\xi (D,{\mathcal{D}}_{\mathcal{t}}\mathcal{)}\mathcal{;}$
4. εt=Px−Dt(ht(x)≠f(x));${\epsilon }_t=P_{x-{\mathcal{D}}_{\mathcal{t}}}(h_t(x)\ne f(x));$(f(x)是真实函数$f(x)是真实函数$)
5. ifεt>0.5thenbreak$if{\epsilon }_t>0.5thenbreak$
6. αt=12ln(1−εtεt);${\alpha }_t=\frac{1}{2}ln(\frac{1-{\epsilon }_t}{{\epsilon }_t});$
7.

Dt+1(x)=Dt(x)Zt×{exp(−αt),exp(αt),ifht(x)=f(x)ifht(x)≠f(x)$${\mathcal{D}}_{\mathcal{t}\mathcal{+}\mathcal{1}}\mathcal{(}\mathcal{x}\mathcal{)}\mathcal{=}\frac{{\mathcal{D}}_{\mathcal{t}}\mathcal{(}\mathcal{x}\mathcal{)}}{{\mathcal{Z}}_{\mathcal{t}}}\times \{\begin{array}{ll}exp(-{\alpha }_t),& if{h}_t(x)=f(x)\\ exp({\alpha }_t),& if{h}_t(x)\ne f(x)\end{array}$$

=Dt(x)exp(−αtf(x)ht(x))Zt$$=\frac{{\mathcal{D}}_{\mathcal{t}}\mathcal{(}\mathcal{x}\mathcal{)}\mathcal{e}\mathcal{x}\mathcal{p}\mathcal{(}\mathcal{-}{\alpha }_{\mathcal{t}}\mathcal{f}\mathcal{(}\mathcal{x}\mathcal{)}{\mathcal{h}}_{\mathcal{t}}\mathcal{(}\mathcal{x}\mathcal{)}\mathcal{)}}{Z_t}$$

Zt$Z_t$是规范化因子，确保Dt+1${\mathcal{D}}_{\mathcal{t}\mathcal{+}\mathcal{1}}$是一个分布。
8. endfor$endfor$
输出：H(x)=sign(∑Tt=1αtht(x))$H(x)=sign(\sum _{t=1}^T{\alpha }_t{h}_t(x))$

---

基于加性模型对算法的证明

AdaBoost算法是基于加性模型，即基学习器的线性组合：H(x)=∑Tt=1αtht(x)（1）$H(x)=\sum _{t=1}^T{\alpha }_t{h}_t(x)（1）$
来最小化指数损失函数：lexp(H|D)=Ex−D[e−f(x)H(x)]（2）$l_{exp}(H|\mathcal{D}\mathcal{)}\mathcal{=}{\mathbb{E}}_{\mathcal{x}\mathcal{-}\mathcal{D}}\mathcal{[}{\mathcal{e}}^{\mathcal{-}\mathcal{f}\mathcal{(}\mathcal{x}\mathcal{)}\mathit{H}\mathit{(}\mathit{x}\mathit{)}}\mathcal{]}\mathsf{（}\mathsf{2}\mathsf{）}$
这里我们采用指示函数I(.)$\mathbb{I}(.)$，当括号内的表达式取值为真时，函数值为1，否则为0。
在AdaBoost算法中，第一个基分类器h1$h_1$是通过直接将基学习算法用于初始数据分布而得。此后迭代的生成ht$h_t$和αt${\alpha }_t$，当基学习器ht$h_t$基于分布Dt${\mathcal{D}}_{\mathcal{t}}$产生后，该基学习器的权重αt${\alpha }_t$应使得αtht${\alpha }_t{h}_t$最小化指数损失函数。
由此，类似于式（2），有：

lexp(αtht|D)====Ex−D[e−f(x)αtht]Ex−D[e−αtI(f(x)=ht(x))+eαtI(f(x)≠ht(x))]e−αtPx−Dt(f(x)=ht(x))+eαtPx−Dt(f(x)≠ht(x))e−αt(1−εt)+eαtεt(1)(2)(3)(4)（3）$$\begin{array}{}\text{(1)}& l_{exp}({\alpha }_t{h}_t|\mathcal{D}\mathcal{)}& =& {\mathbb{E}}_{x-\mathcal{D}}[e^{-f(x){\alpha }_t{h}_t}]\text{(2)}& & =& {\mathbb{E}}_{x-\mathcal{D}}[e^{-{\alpha }_t}\mathbb{I}(f(x)=h_t(x))+e^{{\alpha }_t}\mathbb{I}(f(x)\ne h_t(x))]\text{(3)}& & =& e^{-{\alpha }_t}{P}_{x-{\mathcal{D}}_{\mathcal{t}}}(f(x)=h_t(x))+e^{{\alpha }_t}{P}_{x-{\mathcal{D}}_{\mathcal{t}}}(f(x)\ne h_t(x))\text{(4)}& & =& e^{-{\alpha }_t}(1-{\epsilon }_t)+e^{{\alpha }_t}{\epsilon }_t\end{array}（3）$$

考虑指数损失函数的导数：

对于ht$h_t$。AdaBoost算法在获得Ht−1$H_{t-1}$之后样本分布将进行调整，使下一轮的基学习器ht$h_t$能纠正Ht−1$H_{t-1}$的一些错误，理想的ht$h_t$能纠正Ht−1$H_{t-1}$的全部错误，即最小化：

该结果表明理想的ht$h_t$将在分布Dt${\mathcal{D}}_{\mathcal{t}}$下最小化分类误差。考虑到Dt${\mathcal{D}}_{\mathcal{t}}$和Dt+1${\mathcal{D}}_{\mathcal{t}\mathcal{+}\mathcal{1}}$的关系，有：

这样我们就得到了算法更新样本权重和个体分类器权重的参数。

AdaBoost算法的特点

在上面的算法过程的第五步的意思是，Boosting算法在训练的每一轮迭代都要检查当前的基学习器是否满足基本条件（这里是表示这个基学习器是不是比随机猜测的效果要好），一旦条件不满足，则当前的基学习器及被抛弃且学习过程停止。
从方差-偏差的角度来看，Boosting主要关注降低偏差，即使期望输出与实际结果尽量吻合（方差的意思是学习器在样本数相同的不同训练集下产生的不同）。因此Boosting算法能基于泛化性能相当弱的学习器构造出很强的集成。

Bagging和随机森林

Bagging算法

可以证明，要想得到泛化性能很强的集成，集成中的个体学习器应该尽可能相互独立（证明过程见《机器学习》第8章172页）。但是“独立”在现实世界中显然无法达到，但是可以设法使基学习器尽可能有较大的差异。一种可能的做法是对给定的训练集采样，产生若干个不同的子集，再从每个数据子集训练出一个基学习器，这样，因为每个基学习器的训练样本不同，他们相互之间就可以有较大的差距。

图为Bagging算法的流程图。
给定一个包含m个样本的数据集，一种通常的采样方法是先随机取出一个样本，再将其放回初始数据集，使得下次采样时该数据集仍然有可能被抽到。这样，经过m次采样，可以得到一个和初始数据集同样大小的新的数据集。初始训练集中约有63.2%的样本出现在采样集中。
这样，我们可以得到T个采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合，这就是Bagging算法的基本流程。在集成时，通常采用简单投票法，对回归则采用简单平均。如果分类预测时出现两个类别得到的票数一样多，则随机选取一个类别，也可以进一步学习器投票的置信度来确定最终类别。
从偏差-方差分解的角度来看，和AdaBoost不同的是，Bagging算法主要关注于降低方差（方差的简单理解见前面，深入研究请见《机器学习》2.5节），因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

随机森林

随机森林RF自Bagging算法扩展而来。RF在以决策树为基学习器构建bagging集成的基础上，进一步在决策树的训练过程中加入了随机属性选择。
方法是对基决策树的每一个节点，先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。如果当前属性集合共有d个属性，则推荐取k=log2(d)$k=lo{g}_2(d)$。
显然Bagging基学习器中的多样性仅来自样本的扰动，而随机森林的多样性来自样本和属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加进一步提升。
显然随机森林的训练效率要优于以决策树为个体学习器的bagging，因为Bagging会考察当前节点的全部属性，而随机森林只考察一部分属性。

AdaBoost的python实现

这次不是自己的代码，找到一个大佬的代码。

# -*- coding: utf-8 -*-
"""
Created on Thu Jun 01 09:29:18 2017
Adaboost
@author: liujiping
"""
import numpy as np

def loadSimData():
    '''
    输入：无
    功能：提供一个两个特征的数据集
    输出：带有标签的数据集
    '''
    datMat = np.matrix([[1. ,2.1],[2. , 1.1],[1.3 ,1.],[1. ,1.],[2. ,1.]])
    classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat, classLabels

def stumpClassify(dataMatrix,dimen,thresholdValue,thresholdIneq):
    '''
    输入：数据矩阵，特征维数，某一特征的分类阈值，分类不等号
    功能：输出决策树桩标签
    输出：标签
    '''
    returnArray =  np.ones((np.shape(dataMatrix)[0],1))
    if thresholdIneq == 'lt':
        returnArray[dataMatrix[:,dimen] <= thresholdValue] = -1
    else:
        returnArray[dataMatrix[:,dimen] > thresholdValue] = -1
    return returnArray

def buildStump(dataArray,classLabels,D):
    '''
    输入：数据矩阵，对应的真实类别标签，特征的权值分布
    功能：在数据集上，找到加权错误率（分类错误率）最小的单层决策树，显然，该指标函数与权重向量有密切关系
    输出：最佳树桩（特征，分类特征阈值，不等号方向），最小加权错误率，该权值向量D下的分类标签估计值
    '''
    dataMatrix = np.mat(dataArray); labelMat = np.mat(classLabels).T
    m,n = np.shape(dataMatrix)
    stepNum = 10.0; bestStump = {}; bestClassEst = np.mat(np.zeros((m,1)))
    minError = np.inf
    for i in range(n):
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max()
        stepSize = (rangeMax - rangeMin)/stepNum
        for j in range(-1, int(stepNum)+1):
            for thresholdIneq in ['lt', 'gt']:
                thresholdValue =  rangeMin + float(j) * stepSize
                predictClass = stumpClassify(dataMatrix,i,thresholdValue,thresholdIneq)
                errArray =  np.mat(np.ones((m,1)))
                errArray[predictClass == labelMat] = 0
                weightError = D.T * errArray
                #print "split: dim %d, thresh: %.2f,threIneq:%s,weghtError %.3F" %(i,thresholdValue,thresholdIneq,weightError)
                if weightError < minError:
                    minError = weightError
                    bestClassEst = predictClass.copy()
                    bestStump['dimen'] = i
                    bestStump['thresholdValue'] = thresholdValue
                    bestStump['thresholdIneq'] = thresholdIneq
    return bestClassEst, minError, bestStump

def adaBoostTrainDS(dataArray,classLabels,numIt=40):
    '''
    输入：数据集，标签向量，最大迭代次数
    功能：创建adaboost加法模型
    输出：多个弱分类器的数组
    '''
    weakClass = []#定义弱分类数组，保存每个基本分类器bestStump
    m,n = np.shape(dataArray)
    D = np.mat(np.ones((m,1))/m)
    aggClassEst = np.mat(np.zeros((m,1)))
    for i in range(numIt):
        print "i:",i
        bestClassEst, minError, bestStump = buildStump(dataArray,classLabels,D)#step1:找到最佳的单层决策树
        print "D.T:", D.T
        alpha = float(0.5*np.log((1-minError)/max(minError,1e-16)))#step2: 更新alpha
        print "alpha:",alpha
        bestStump['alpha'] = alpha
        weakClass.append(bestStump)#step3:将基本分类器添加到弱分类的数组中
        print "classEst:",bestClassEst
        expon = np.multiply(-1*alpha*np.mat(classLabels).T,bestClassEst)
        D = np.multiply(D, np.exp(expon))
        D = D/D.sum()#step4:更新权重，该式是让D服从概率分布
        aggClassEst += alpha*bestClassEst#steo5:更新累计类别估计值
        print "aggClassEst:",aggClassEst.T
        print np.sign(aggClassEst) != np.mat(classLabels).T
        aggError = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T,np.ones((m,1)))
        print "aggError",aggError
        aggErrorRate = aggError.sum()/m
        print "total error:",aggErrorRate
        if aggErrorRate == 0.0: break
    return weakClass

def adaTestClassify(dataToClassify,weakClass):
    dataMatrix = np.mat(dataToClassify)        
    m =np.shape(dataMatrix)[0]
    aggClassEst = np.mat(np.zeros((m,1)))
    for i in range(len(weakClass)):
        classEst = stumpClassify(dataToClassify,weakClass[i]['dimen'],weakClass[i]['thresholdValue']\
                                 ,weakClass[i]['thresholdIneq'])
        aggClassEst += weakClass[i]['alpha'] * classEst
        print aggClassEst
    return np.sign(aggClassEst)
if __name__  ==  '__main__':
    D =np.mat(np.ones((5,1))/5)
    dataMatrix ,classLabels= loadSimData()
    bestClassEst, minError, bestStump = buildStump(dataMatrix,classLabels,D)
    weakClass = adaBoostTrainDS(dataMatrix,classLabels,9)            
    testClass = adaTestClassify(np.mat([0,0]),weakClass)

调用sklearn的AdaBoost类库

首先导入需要的类库

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_gaussian_quantiles

调用sklearn生成符合2维正太分布的2分类数据：

# 生成2维正态分布，生成的数据按分位数分为两类，500个样本,2个样本特征，协方差系数为2
X1, y1 = make_gaussian_quantiles(cov=2.0,n_samples=500, n_features=2,n_classes=2, random_state=1)
# 生成2维正态分布，生成的数据按分位数分为两类，400个样本,2个样本特征均值都为3，协方差系数为2
X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,n_samples=400, n_features=2, n_classes=2, random_state=1)
#讲两组数据合成一组数据
X = np.concatenate((X1, X2))
y = np.concatenate((y1, - y2 + 1))
plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)

生成效果如图所示
用基于决策树的Adaboost来做分类拟合。

bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=2, min_samples_split=20, min_samples_leaf=5),
                         algorithm="SAMME",
                         n_estimators=200, learning_rate=0.8)
bdt.fit(X, y)

显示拟合区域并且绘制预测结果和预测边界

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
                     np.arange(y_min, y_max, 0.02))

Z = bdt.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)
plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)
plt.show()

效果如图所示：

AdaBoost算法的C++实现

最近课程较多，忙于学业。先立个flag，会尽快实现并分享给大家 :)

参考资料

周志华老师的《机器学习》
用python实现adaboost的博客
sklearn的Adaboost类库的参考博客
借用图片的博客

结语

初入计算机，请大家多多指教嘛，真诚欢迎一起讨论，共同学习~~~持续更新中……