OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› R语言›R语言教程

机器学习实战 AdaBoost算法 python3实现 R语言实现

原作者: [db:作者] 来自: [db:来源] 收藏邀请

机器学习实战里面对各种算法的解释都比较详尽，但是python的更新导致里面部分代码运行错误。在搜集了众多资料后发现并没有人跑来把机器学习实战这本书的python3写一下。可能大佬们觉得这小菜一碟，所以我在学习的时候把代码整理了一下放到这里希望可以帮助一些和我一样刚刚开始学习python，但是拿着一堆python2的代码无从下手的小码农们。

本文原理部分来自网络。

如有错误欢迎指正。

其实AdaBoost算法可以看做有一个老师在看着你做作业，你做错了就打你一下，那么你下次在遇到相同的题的时候就会特别小心，错的概率就小了。慢慢的你就可以把每一道题都做对了，这个时候老师就可以下班了。当然，这个老师不会再你做对的时候给你块糖吃。

3.测试算法：基于AdaBoost的分类 17

4.在一个难数据集上应用AdaBoost 18

5.AdaBoost和SVM 20

五、R语言实现 20

一、原理

AdaBoost（Adaptive Boosting，自适应提升）算法是由来自AT&T实验室的Freund和Schapire于1995年首次提出，该算法解决了早期Boosting算法的一些实际执行难题，而且该算法可以作为一种从一系列弱分类器中产生一个强分类器的通用方法。正由于AdaBoost算法的优异性能，Freund和Schapire因此获得了2003年度的哥德尔奖（Gödel Prize，该奖是在理论计算机科学领域中最负盛名的奖项之一）。

假设我们有一个集合{(x₁, y₁),(x₂, y₂), …, (x_N,y_N)}，每一个数据项x_i是一个表示事物特征的矢量，y_i是一个与其相对应的分类y_i∈{-1, 1}，即x_i要么属于-1，要么属于1。AdaBoost算法通过M次迭代得到了一个弱分类器集合{k₁, k₂,…, k_M}，对于每一个数据项x_i来说，每个弱分类器都会给出一个分类结果来，即k_m(x_i)∈{-1, 1}。这M个弱分类器通过某种线性组合（式1所示）就得到了一个强分类器C_m，这样我们就可以通过C_m来判断一个新的数据项x_k是属于-1，还是1。这就是一个训练的过程。

二、 Boosting算法的发展历史

Boosting算法是一种把若干个分类器整合为一个分类器的方法，在boosting算法产生之前，还出现过两种比较重要的将多个分类器整合为一个分类器的方法，即boostrapping方法和bagging方法。我们先简要介绍一下bootstrapping方法和bagging方法。

1）bootstrapping方法的主要过程

　　主要步骤：

i)重复地从一个样本集合D中采样n个样本

ii)针对每次采样的子样本集，进行统计学习，获得假设H_i

iii)将若干个假设进行组合，形成最终的假设H_final

iv)将最终的假设用于具体的分类任务

2）bagging方法的主要过程 -----bagging可以有多种抽取方法

　　主要思路：

i)训练分类器

　　从整体样本集合中，抽样n^* < N个样本针对抽样的集合训练分类器C_i

ii)分类器进行投票，最终的结果是分类器投票的优胜结果

　　但是，上述这两种方法，都只是将分类器进行简单的组合，实际上，并没有发挥出分类器组合的威力来。直到1989年，Yoav Freund与 Robert Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而获得了2003年的哥德尔奖（Godel price）。

Schapire还提出了一种早期的boosting算法，其主要过程如下：

i)从样本整体集合D中，不放回的随机抽样n₁< n个样本，得到集合 D₁

　　训练弱分类器C₁

ii)从样本整体集合D中，抽取 n₂< n个样本，其中合并进一半被C₁ 分类错误的样本。得到样本集合D₂

　　训练弱分类器C₂

iii)抽取D样本集合中，C₁ 和 C₂ 分类不一致样本，组成D₃

　　训练弱分类器C₃

iv)用三个分类器做投票，得到最后分类结果

　　到了1995年，Freund and schapire提出了现在的adaboost算法，其主要框架可以描述为：

i)循环迭代多次

　　更新样本分布

　　寻找当前分布下的最优弱分类器

　　计算弱分类器误差率

ii)聚合多次训练的弱分类器

三、 Adaboost 举例

也许你看了上面的介绍或许还是对adaboost算法云里雾里的，没关系，百度大牛举了一个很简单的例子，你看了就会对这个算法整体上很清晰了。

下面我们举一个简单的例子来看看adaboost的实现过程：

图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。

　　第一步：

根据分类的正确率，得到一个新的样本分布D₂，一个子分类器h₁

其中划圈的样本表示被分错的。在右边的途中，比较大的“+”表示对该样本做了加权。

也许你对上面的ɛ1，ɑ1怎么算的也不是很理解。下面我们算一下，不要嫌我啰嗦，我最开始就是这样思考的，只有自己把算法演算一遍，你才会真正的懂这个算法的核心，后面我会再次提到这个。

算法最开始给了一个均匀分布 D 。所以h1 里的每个点的值是0.1。ok，当划分后，有三个点划分错了，根据算法误差表达式得到误差为分错了的三个点的值之和，所以ɛ1=(0.1+0.1+0.1)=0.3，而ɑ1 根据表达式的可以算出来为0.42. 然后就根据算法把分错的点权值变大。如此迭代，最终完成adaboost算法。

　　第二步：

　　根据分类的正确率，得到一个新的样本分布D₃，一个子分类器h₂

　　第三步：

　　得到一个子分类器h₃

　　整合所有子分类器：

因此可以得到整合的结果，从结果中看，及时简单的分类器，组合起来也能获得很好的分类效果，在例子中所有的。

四、Python实现

1.构建弱分类器

from numpy import *

def loadSimpData():#单层决策树难以处理的一个著名问题

datMat = 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

单层决策树生成函数：

伪代码：

将最小错误率minError设为正无穷

对数据集中地每一个特征（第一次循环）：

对每个步长（第二层循环）：

对每个不等号（第三层循环）：

建立一棵单层决策树并利用加权数据集对他进行测试

如果错误率低于minError。则将当前单层决策树设为最佳单层决策树

返回最佳单层决策树

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):

"""

通过阈值比较对数据进行分类，一边为1一边为-1

"""

retArray = ones((shape(dataMatrix)[0],1))

if threshIneq == 'lt':

retArray[dataMatrix[:,dimen] <= threshVal] = -1.0 #或许应该为1

else:

retArray[dataMatrix[:,dimen] > threshVal] = -1.0

return retArray

def buildStump(dataArr,classLabels,D):

"""

在一个加权数据集中循环，并找到具有最低错误率的单层决策树

"""

dataMatrix = mat(dataArr); labelMat = mat(classLabels).T

m,n = shape(dataMatrix)

numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1)))

minError = inf

for i in range(n):#对数据集中的每一个特征（第一次循环）

rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();

stepSize = (rangeMax-rangeMin)/numSteps

for j in range(-1,int(numSteps)+1):#每个步长（第二次循环）

for inequal in ['lt', 'gt']:#每个不等号（第三次循环）

"""

建立一颗单层决策树并利用加权数据集对他进行测试

"""

threshVal = (rangeMin + float(j) * stepSize)

predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)

errArr = mat(ones((m,1)))#设置初始值为1

errArr[predictedVals == labelMat] = 0#predictedVals中的值和labelMat的真正类别标签值相等则为0，否则为1

weightedError = D.T*errArr #adaboost和分类器进行交互的地方

if weightedError < minError:#如果错误率低于minError则将当前单层决策树设为最佳单层决策树

minError = weightedError

bestClasEst = predictedVals.copy()

bestStump['dim'] = i

bestStump['thresh'] = threshVal

bestStump['ineq'] = inequal

return bestStump,minError,bestClasEst

检验函数：

from numpy import*

import adaboost

datMat,classLabels = adaboost.loadSimpData() #导入数据集和类别标签

print(datMat,classLabels)

D = mat(ones((5,1))/5)

print(adaboost.buildStump(datMat,classLabels,D))

结果：

[[ 1. 2.1]

[ 2. 1.1]

[ 1.3 1. ]

[ 1. 1. ]

[ 2. 1. ]] [1.0, 1.0, -1.0, -1.0, 1.0]

({'dim': 0, 'thresh': 1.3, 'ineq': 'lt'}, matrix([[ 0.2]]), array([[-1.],

[ 1.],

[-1.],

[ 1.]]))

2.完整Adaboost算法的实现

基于单层决策树的AdaBoost训练过程

对每次迭代：

利用buildStump（）函数找到最佳的单层决策树

将最佳的单层决策树加入到单层决策树数组

计算alpha

计算新的权重向量D

更新累积类别估计值

如果错误率等于0.0，则退出循环

def adaBoostTrainDS(dataArr,classLabels,numIt=40):

"""

dataArr：数据集。classLabels:类别标签。numIt:迭代次数：唯一需要用户指定的参数。

"""

weakClassArr = []

m = shape(dataArr)[0]

D = mat(ones((m,1))/m)

aggClassEst = mat(zeros((m,1)))

for i in range(numIt):#对每次迭代。

bestStump,error,classEst = buildStump(dataArr,classLabels,D)

#函数buildStump()输入：权重向量D。返回：利用D得到的具有最小错误率的单层决策树，最小错误率，以及估计的类别向量

print("D:",D.T)

alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#1e-16确保没有错误是不会发生除零溢出。

bestStump['alpha'] = alpha

weakClassArr.append(bestStump)#把最佳单层决策树加入到单层决策树组。

print("classEst:",classEst)

expon = multiply(-1*alpha*mat(classLabels).T,classEst)

D = multiply(D,exp(expon))

D = D/D.sum()

aggClassEst += alpha*classEst

print("aggClassEst:",aggClassEst.T)

aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones((m,1)))

errorRate = aggErrors.sum()/m

print("total error: ",errorRate)

if errorRate == 0.0: break #错误为0时退出循环

return weakClassArr,aggClassEst

函数检验：

import adaboost

datMat,classLabels = adaboost.loadSimpData()

classifierArray= adaboost.adaBoostTrainDS(datMat,classLabels,9)

print(classifierArray)

结果：

D: [[ 0.2 0.2 0.2 0.2 0.2]]

初始错误率相等都为0

classEst: [[-1.]

[ 1.]

[-1.]

[ 1.]]

对第一个数据判断错误。所以下一次迭代中第一个数据的权重增加

aggClassEst: [[-0.69314718 0.69314718 -0.69314718 -0.69314718 0.69314718]]

total error: 0.2

D: [[ 0.5 0.125 0.125 0.125 0.125]]

第一个数据权重增加，其他数据权重减少

classEst: [[ 1.]

[ 1.]

[-1.]

[-1.]]

此时第一个数据的分类正确，最后一个数据的分类错误，相应的增加最后一个数据的权重，减少其他数据的权重

aggClassEst: [[ 0.27980789 1.66610226 -1.66610226 -1.66610226 -0.27980789]]

total error: 0.2

D: [[ 0.28571429 0.07142857 0.07142857 0.07142857 0.5 ]]

classEst: [[ 1.]

[ 1.]

[ 1.]]

aggClassEst: [[ 1.17568763 2.56198199 -0.77022252 -0.77022252 0.61607184]]

total error: 0.0

错误率为零，跳出循环

([{'dim': 0, 'thresh': 1.3, 'ineq': 'lt', 'alpha': 0.6931471805599453}, {'dim': 1, 'thresh': 1.0, 'ineq': 'lt', 'alpha': 0.9729550745276565}, {'dim': 0, 'thresh': 0.90000000000000002, 'ineq': 'lt', 'alpha': 0.8958797346140273}], matrix([[ 1.17568763],

[ 2.56198199],

[-0.77022252],

[ 0.61607184]]))

上述数组包含三个字典，其中包含分类所需要的所有信息。此时一个分类器已经构建成功，为了观察错误率，我们需要编写分类的一些代码。

3.测试算法：基于AdaBoost的分类

目的：将弱分类器的训练过程从程序中抽出来，然后应用到某个具体的实例上去。

AdaBoost分类函数

def adaClassify(datToClass,classifierArr):

输入：由一个或多个待分类样例daToClass以及多个弱分类器组成的数组classifierArr

输出：aggClassEst的符号，即aggClassEst大于0则返回+1，小于0则返回-1

dataMatrix = mat(datToClass)

m = shape(dataMatrix)[0]

aggClassEst = mat(zeros((m,1)))

for i in range(len(classifierArr)):

classEst = stumpClassify(dataMatrix,classifierArr[i]['dim'],\

classifierArr[0][i]['thresh'],\

classifierArr[0][i]['ineq'])

aggClassEst += classifierArr[0][i]['alpha']*classEst

print(aggClassEst)

return sign(aggClassEst)

检验函数：

import adaboost

datArr,labelArr = adaboost.loadSimpData()

classifierArr = adaboost.adaBoostTrainDS(datArr,labelArr,30)

print(adaboost.adaClassify([0,0],classifierArr))

结果：

[[-0.69314718]]

[[-1.66610226]]

[[-1.]]

4.在一个难数据集上应用AdaBoost

步骤：

1. 收集数据：提供的文本文件

2. 准备数据：确保类别标签是+1，-1，而不是1，0

3. 分析数据：手工检查数据

4. 训练算法：在数据上，利用AdaBoostTrainDS（）函数训练出一系列的分类器。

5. 测试算法：我们拥有两个数据及。在不采用随机抽样的方法下，我们就会对AdaBoost和Logistic回归的结果进行完全的对等比较。

6. 使用算法：观察该例子上的错误率。不过，也可以构建一个Web网站，让驯马是输入马的症状然后预测马是否会死去。

自适应数据加载函数：

导入文件：

def loadDataSet(fileName):

numFeat = len(open(fileName).readline().split('\t')) #get number of fields

dataMat = []; labelMat = []

fr = open(fileName)

for line in fr.readlines():

lineArr =[]

curLine = line.strip().split('\t')

for i in range(numFeat-1):

lineArr.append(float(curLine[i]))

dataMat.append(lineArr)

labelMat.append(float(curLine[-1]))

return dataMat,labelMat

函数检验：

from numpy import*

import adaboost

datArr,labelArr = adaboost.loadDataSet("horseColicTraining2.txt")

classifierArray = adaboost.adaBoostTrainDS(datArr,labelArr,10)

testArr,testLabelArr = adaboost.loadDataSet("horseColicTest2.txt")

prediction10 = adaboost.adaClassify(testArr,classifierArray)

errrArr=mat(ones((67,1)))

print(errrArr[prediction10!=mat(testLabelArr).T].sum()

结果

total error: 0.284280936455

total error: 0.247491638796

total error: 0.254180602007

total error: 0.240802675585

total error: 0.220735785953

total error: 0.247491638796

total error: 0.230769230769

18.0

5.AdaBoost和SVM

AdaBoost和SVM是监督学习中最强大的两种算法。实际上，这两者之间拥有不少相似之处。我们可以把弱分类器想象成SVM中的一个核函数，也可以按照最大化某个最小间隔的方式重写AdaBoost算法。而他们的不同在于其所定义的间隔计算方式有所不同，因此大哦哦之的结构也不同。特别是在高维空间下，这两者之间的差异就会更加明显。