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

时间 2019-12-08 标签机器学习入门二集成学习 adaboost 算法 python 实现

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

个体与集成

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

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

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

Boosting

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

算法流程

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

输入：训练集 $D=\{(x_1,y_1),.....,(x_m,y_m)\}$ ，基学习算法 $\xi$ ，训练次数T
过程：
1. $\cal D_1(x)=1/m.\quad\quad$ (表示第一轮时每一个样本的权重是相等的)
2. $for\quad t=1,2,3,...,T\quad\quad do:$
3. $\quad\quad h_t=\xi(D,\cal D_t);$
4. $\quad\quad \varepsilon_t=P_{x-\cal D_t}(h_t(x)\not= f(x));\quad\quad$ ( $f(x)是真实函数$ )
5. $\quad\quad if\quad \varepsilon_t>0.5\quad then\quad break$
6. $\quad\quad \alpha_t=\frac1 2 ln(\frac{1-\varepsilon_t}{\varepsilon_t});$
7. 数组

D_{t + 1} (x) = \frac{D_{t} (x)}{Z_{t}} \times {\begin{cases} e x p (- α_{t}), & i f h_{t} (x) = f (x) \\ e x p (α_{t}), & i f h_{t} (x) \neq f (x) \end{cases}

$\quad\quad\cal D_{t+1}(x)=\frac{\cal D_t(x)}{Z_t}\times \begin{cases} exp(-\alpha_t),&if\quad h_t(x)=f(x)\\ exp(\alpha_t),&if\quad h_t(x)\not=f(x) \end{cases}$

= \frac{D_{t} (x) e x p (- α_{t} f (x) h_{t} (x))}{Z_{t}}

$\quad\quad =\frac{\cal D_t(x)exp(-\alpha_tf(x)h_t(x))}{Z_t}\quad\quad$

Z_{t}

$Z_t$ 是规范化因子，确保

D_{t + 1}

$\cal D_{t+1}$ 是一个分布。
8.

e n d f o r

$end \quad for$
输出：

H (x) = s i g n (\sum_{t = 1}^{T} α_{t} h_{t} (x))

$H(x)=sign(\sum^{T}_{t=1}\alpha_th_t(x))$

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

AdaBoost算法是基于加性模型，即基学习器的线性组合： $H(x)=\sum_{t=1}^{T}\alpha_th_t(x)\quad\quad\quad（1）$
来最小化指数损失函数： $l_{exp}(H|\cal D)={\Bbb E}_{x-{\cal D}}[e^{-f(x)\it H(x)}]\quad\quad \sf（2）$
这里咱们采用指示函数 $\Bbb I(.)$ ，当括号内的表达式取值为真时，函数值为1，不然为0。
在AdaBoost算法中，第一个基分类器 $h_1$ 是经过直接将基学习算法用于初始数据分布而得。此后迭代的生成 $h_t$ 和 $\alpha_t$ ，当基学习器 $h_t$ 基于分布 $\cal D_t$ 产生后，该基学习器的权重 $\alpha_t$ 应使得 $\alpha_th_t$ 最小化指数损失函数。
由此，相似于式（2），有：
网络

\begin{array}{rcl} (1) & l_{e x p} (α_{t} h_{t} | D) & = & E_{x - D} [e^{- f (x) α_{t} h_{t}}] \\ (2) & = & E_{x - D} [e^{- α_{t}} I (f (x) = h_{t} (x)) + e^{α_{t}} I (f (x) \neq h_{t} (x))] \\ (3) & = & e^{- α_{t}} P_{x - D_{t}} (f (x) = h_{t} (x)) + e^{α_{t}} P_{x - D_{t}} (f (x) \neq h_{t} (x)) \\ (4) & = & e^{- α_{t}} (1 - ε_{t}) + e^{α_{t}} ε_{t} \end{array} （ 3 ）

$\begin{eqnarray}l_{exp}(\alpha_th_t|\cal D)&=&{\Bbb E}_{x-{\cal D}}[e^{-f(x)\alpha_th_t}]\\ &=&{\Bbb E}_{x-{\cal D}}[e^{-\alpha_t}\Bbb I(f(x)=h_t(x))+e^{\alpha_t}\Bbb I(f(x)\not= h_t(x))]\\ &=&e^{-\alpha_t}P_{x-\cal D_t}(f(x)=h_t(x))+e^{\alpha_t}P_{x-\cal D_t}(f(x)\not=h_t(x))\\ &=&e^{-\alpha_t}(1-\varepsilon_t)+e^{\alpha_t}\varepsilon_t \end{eqnarray}\quad\quad（3）$
考虑指数损失函数的导数：

对于

h_{t}

$h_t$ 。AdaBoost算法在得到

H_{t - 1}

$H_{t-1}$ 以后样本分布将进行调整，使下一轮的基学习器

h_{t}

$h_t$ 能纠正

H_{t - 1}

$H_{t-1}$ 的一些错误，理想的

h_{t}

$h_t$ 能纠正

H_{t - 1}

$H_{t-1}$ 的所有错误，即最小化：

该结果代表理想的

h_{t}

$h_t$ 将在分布

D_{t}

$\cal D_t$ 下最小化分类偏差。考虑到

D_{t}

$\cal D_t$ 和

D_{t + 1}

$\cal D_{t+1}$ 的关系，有：

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

AdaBoost算法的特色

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

Bagging和随机森林

Bagging算法

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

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

随机森林

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

AdaBoost的python实现

此次不是本身的代码，找到一个大佬的代码。svg

# -*- 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类库的参考博客
 借用图片的博客

结语

初入计算机，请你们多多指教嘛，真诚欢迎一块儿讨论，共同窗习~~~持续更新中……