集成方法（Boosting:以AdaBoost为例）原理以及实现

本文主要是介绍集成方法（Boosting:以AdaBoost为例）原理以及实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

集成方法(boosting又称为提升方法)

提升方法重要概念

1.思路:三个臭皮匠顶个诸葛亮
2.重要概念:
PAC:(Probably approximately correct):概率近似正确
强可学习:PAC中,面对假设模型,如果存在一个多项式的学习算法能够学习它,且正确率很高,那么这个概念就是强可学习
弱可学习:PAC中,面对假设模型,如果存在一个多项式的学习算法能够学习它,且正确率仅仅比随机猜测好,那么这个概念就是弱可学习
注意:强可学习实质上等价于弱可学习

在PAC学习的框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习的

问题: 弱可学习如果提升为强可学习?

方案:对分类问题而言,提升方法就是弱学习算法出发,反复学习,得出一系列弱分类器,组合这些弱分类器,构成一个强分类器，
提升方法:为改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据调用弱分类器算法
给出方案之后,提升方法的两个问题?
1.在每一轮中如何改变训练数据的权值或概率分布
2.如何将弱分类器组合成一个强分类器

AdaBoost给出的解决方案
1.提高那些被前一轮弱分类器错误分类样本的权值,降低被正确分类的样本权值
2.加权多数表决的方法将弱分类器线性组合起来

AdaBoost

Input:DataSet $T=\{(x_1,y_2),(x_2, y_2),...,(x_n, y_n)\} {x_i \in \chi \subseteq R },{y_i \in Y ={-1,+1}} , 弱学习分类器$
Output: $最终分类算法G_{(x)}$

算法实现过程:

step1: 初始化训练数据的权值分布
$D_1 = (W_{11}, W_{12}, ..., W_{1i}, W_{1N}),W_{1i}=\frac{1}{N},i=1,2,...,N$

step2: $对m=1,2,.....,M$ , 表示有m个弱分类器

(a) 使用具有权值分布 $D_m$ 的训练数据集学习,得到基本m个基本分类器
$G_m(x):X -> {-1, +1}$
(b) 计算 $G_m(x)$ 在训练集上的分类误差率
$e_m = P(G_m{x_i}\neq y_i = \sum\limits_{i=1}^{N}W_{mi}I(G_m(x)\neq y_i)$
实质上是错分数据的权值之和
(c) 计算 $G_m(x)的系数$
$\alpha_{m} = \frac{1}{2}\log \frac{1-e_{m}}{e_m}$
(d) 更新训练数据集的权值分布
$D_{(m+1)} = (W_{m+1,1},W_{m+1,2},....,W_{m+1,i},.......,W_{m+1,N}$
$W_{m+1,i} = \frac{W_{mi}}{Z_m} \exp^(-\alpha_{m}y_iG_m(x_i))$
实质上是:指数惩罚函数
$当y_i == G_m(x_i)时: y_i G_m(x_i)=1, 即-\alpha_m y_i G_m(x_i) < 0,权重减小$
$当y_i != G_m(x_i)时: y_i G_m(x_i)=-1, 即-\alpha_m y_i G_m(x_i) > 0,权重增加$

$Z_m是规范化因子 Z_m=\sum\limits_{i=1}^{N}W_{mi}\exp(-alphay_iG_m(x_i))$
这样更新训练数据的权值分布 $D_{m+1}$

step3:构建基本分类器的线性组合
$f(x) = \sum\limits_{m=1}^{M} \alpha_m G_m(x)$
得出最终分类器:
$G(x) = sign(f(x)) = sign(\sum\limits_{m=1}^{M}\alpha_m G_m(x))$

AdaBoost算法说明

(1) 假设训练数据集具有均匀的权值分布,即每个训练样本在基本分类器的学习中作用相同===》在此基础上,首先得出基本分类器
(2) $AdaBoost$ 反复学习基本分类器,在每一轮 $m=1,2,...,M$ 顺次的执行下列操作:

(a)使用当前分布 $D_m$ 加权的训练数据集,学习基本分类器 $G_m(x)$
(b)计算基本分类器 $G_m(x)$ 在加权训练集上的分类误差率
$e_m = P(G_m(x_i)\neq y_i) = \sum\limits_{G_m(x_i)\neq y_i}W_{mi}$
$W_{mi}表示在第m轮更新中,第i个实例的权值,\sum\limits_{i=1}^{N}W_{mi}=1$
表明: $G_m(x)$ 在加权的训练数据集上的分类误差率是被 $G_m(x)$ 误分类样本的权值之和,由此确定数据权值分布 $D_m$ 与基本分类器 $G_m(x)$ 的分类误差率的关系
(c)计算基本分类器 $G_m(x)的系数\alpha_m, \alpha_m表示G_m(x)在最终分类器中的重要性$
$\alpha_m = \frac{1}{2}\log \frac{1-e_m}{e_m}$
性质: 当 $e_m\le \frac{1}{2}时,\alpha_m \ge 0, 并且\alpha_m随着e_m的减小而增大, 所有分类误差率越小的基本分类器在最终分类器中的作用越大$
(d)更新训练数据的权值分布为下一轮做准备
$W_{m+1,i} = \frac{W_{mi}}{Z_m} e^{-\alpha_m}, G_m{x_i}=y_i$
$W_{m+1,i} = \frac{W_{mi}}{Z_m} e^{\alpha_m}, G_m{x_i}=y_i$
$Z_m=\sum\limits_{i=1}^{N}W_{mi}\exp(-alphay_iG_m(x_i))$

即: 在上述的迭代更新中, 被基本分类器 $G_m(x)$ 误分类样本的权值得以扩大,而被正确分类样本的权值得以缩小,实质上 $e^{2\alpha_m}=\frac{e_m}{1-e_m}$ ,使得误分类样本的作用在下一轮的作用中变得更好
不改变训练数据而改变权值分布, 使得训练数据在基本分类器中其不同的作用

（3）线性组合 $f(x)实现M个基本分类器的加权表决, 系数\alpha_m表示基本分类器G_m(x)的重要性,注意: 这里\sum\alpha_m \neq 1$
- $f(x)的符号决定实例x的类$
- $f(x)的绝对值表示分类的确信度$
最终: 利用基本分类器的线性组合构建最终分类器

例题及adaboost算法实现:

这里写图片描述

import numpy as npD = None
fx = dict()def loadDataSet(filename):dataSet, labelMat = list(), list()with open(filename, 'r') as fr:for line in fr.readlines():dataSet.append([int(line.split(',')[0])])labelMat.append([int(line.split(',')[1])])return np.mat(dataSet), np.mat(labelMat)# 三个弱分类器
def weekClassify1(x):if x < 2.5:return 1elif x > 2.5:return -1def weekClassify2(x):if x < 8.5:return 1elif x > 8.5:return -1def weekClassify3(x):if x > 5.5:return 1elif x < 5.5:return -1def calcErrorRate(dataSet, labelMat, func):dataSize = np.shape(labelMat)[0]errorIndex = list()for index in range(len(dataSet)):predict = func(dataSet[index])if predict * labelMat[index] < 0:errorIndex.append(index)return errorIndexdef adaBoost(dataSet, labelMat, funcList):""":param dataSet: 训练数据集 input  特征值:param labelMat: 训练数据集 output 类标记:param funcList: 弱分类器的列表集合:returnfx 字典形式的基本分类器的线性组合"""# step1 初始化训练数据的权值分布global Dglobal fxif D is None:dataSize = np.shape(labelMat)[0]D = np.ones((dataSize, 1)) / dataSizeprint(D)  # [[0.1], [0.1], [0.1].....[0.1]]else:# step2 对m=1,2,....,M# (a) 使用具有权值分布D的训练数据集学习 得到基本分类器 Gm(x)# funcList = [weekClassify1, weekClassify2, weekClassify3]# print(funcList)# (b) 计算Gm(x)在训练数据集上的分类误差率 = 错分类数据权值之和# fx 基本分类器的线性组合errorRateList = list()errorIndexList = list()for funcIndex in range(len(funcList)):errorIndex = calcErrorRate(dataSet, labelMat, funcList[funcIndex])errorIndexList.append(errorIndex)errorRate = 0for index in errorIndex:errorRate += float(D[index])print('errorRate:', errorRate)errorRateList.append(errorRate)# print('min_errorRate', min_errorRate)# (c) 计算Gm(x)的系数   选择弱分类器中错分率最低的分类器 优先计算系数min_errorRate = min(errorRateList)min_funcIndex = errorRateList.index(min_errorRate)print('min_errorRate', min_errorRate)print('min_funcIndex', min_funcIndex)print('错分率最低的分类器索引', min_funcIndex)alpha = (1 / 2) * np.log((1 - min_errorRate) / min_errorRate)# print('alpha1', alpha)# print('alpha2', alpha)print('计算Gm(x)的系数', alpha)# (d) 更新训练数据的权值分布print(errorIndexList[min_funcIndex])print('更新权重')for indexD in range(len(D)):if indexD in errorIndexList[min_funcIndex]:# print('D indexD', D[indexD])D[indexD] = D[indexD] / (2 * min_errorRate)else:D[indexD] = D[indexD] / (2 * (1 - min_errorRate))print(D)# step 3 构建基本分类器的线性组合print('构建基本分类器的线性组合')fx[alpha] = funcList[min_funcIndex]# print('fx', fx)sign_errorIndex = strongClassify(fx, dataSet, labelMat)sign_errorRate = (1 - (float(len(sign_errorIndex)) / len(labelMat))) * 100if sign_errorRate > 90.00:print("最终分类器正确率率大于0.9, 正确率为%.2f %%" % sign_errorRate)# print('fx:', fx)return fxelse:print("当前最终分类器正确率为%.2f %%" % sign_errorRate)print('当前最终分类器误分类个数为: %d' % len(sign_errorIndex))print('继续优化最终分类器fx:', fx)return adaBoost(dataSet, labelMat, funcList)# 最终分类器
def sign(fx, testData):result = 0for key, value in fx.items():result += key * value(testData)if result > 0:result = 1else:result = -1return result# 强分类器验证
def strongClassify(fx, testData, labelMat):errorIndex = list()for index in range(len(testData)):predict = sign(fx, testData[index])# print(predict)if predict != float(labelMat[index]):errorIndex.append(index)print('strongClassify errorIndex', errorIndex)return errorIndexdef main():filename = 'test.txt'dataSet, labelMat = loadDataSet(filename)funcList = [weekClassify1, weekClassify2, weekClassify3]fx = adaBoost(dataSet, labelMat, funcList)print(fx)# correctRate = strongClassify(fx, dataSet, labelMat)# print('AdaBoost StrongClassify CorrectRate:%.2f %%' % correctRate)if __name__ == '__main__':main()

AdaBoost算法误差分析

从定理中化简:训练数据的权值分布公式以及 $Z_m$ 规范化因子公式

二分类问题Adaboost的训练误差界

$Z_m=\sum\limits_{i=1}^{N}W_{mi}\exp(-alphay_iG_m(x_i))$
此时存在两种情况: $第一种: y_i = G_m(x_i) \\ 第二种：y_i != G_m(x_i)$

即: $Z_m = \sum\limits_{y=G_m(x)} W_{mi} e^{-\alpha_m} + \sum\limits_{y \neq G_m(x)} W_{mi} e^{\alpha_m} \\ =(1-e_m) \exp ^{-\alpha_m}+ e_m \exp^{\alpha_m} \\ = 2 \sqrt{ e_m^(1-e_m)} \\ = \sqrt {1-4r^2m}$

其中 $e_m 为误分类权重之和(误分类率), r_m = \frac{1}{2} - e_m$
定理:在二分问题中Adaboost的训练误差为:
$\prod\limits_{m=1}^{M} Z_m = \prod\limits_{m=1}^{M} [2\sqrt {e_m(1-e_m)} = \prod\limits_{m=1}^{M} \sqrt {(1-4r_m^2)} \le \exp (-2\sum\limits_{m=1}^{M} r^2_m)$

$前三项展开Z_m可得,后两项由e^x和\sqrt{1-x}在x=0时使用泰勒公式展开推导可得$

又由公式: $z_m = 2\sqrt {e_m(1-e_m)}$ 带入更新训练数据的权值分布中可得
重点:
$当Gm(x_i)=y_i时, W_{m+1,i}=\frac{W_{mi}}{2(1-e_m)} \\ 当Gm(x_i)!=y_i时, W_{m+1,i}=\frac{W_{mi}}{2e_m}$

定理: AdaBoost的训练误差界

$\frac{1}{N}\sum\limits_{i=1}^{N} (G(x_i) \neq y_i) \le \frac{1}{N}\sum\limits_{i} \exp^{(-y_i f(x_i))} = \prod\limits_{m}Z_m$

其中: $G(x)=sign(f(x))=sign(\sum\limits_{m=1}^{M}\alpha_m G_m(x),最终分类器 \\ f(x) = \sum\limits_{m=1}^{M}\alpha_m G_m(x) , 系数*基本分类器 \\ Z_m = \sum\limits_{i=1}^{N} W_{mi} \exp^(-alpha_m y_i G_m(x_i)), 规范化因子$
证明: $当G(x_i)\neq y_i时, y_if(x_i)\le 0, 此时\exp^{(-y_if(x_i))} \ge 1$
后两项由 $Z_m定义式可证明$
$Z_m=\sum\limits_{i=1}^{N}W_{mi}\exp(-alphay_iG_m(x_i))$
将该式变化可得: $Z_{m+1,i} = W_{mi} \exp ^{(-alpha_m y_i G_m(x_i)}$
可证:
$\frac{1}{N}\sum\limits_{i} \exp^{(-y_i f(x_i))} = \frac{1}{N}\sum\limits_{i} \exp^{(-\sum\limits_{m=1}^{M} \alpha_m G_m(x_i) y_i} \\ = \sum\limits_{i}W_{1i}\prod\limits_{m=1}^{M} \exp^{(-\alpha_m y_i G_m(x_i))} = Z_1\sum\limits_{i}W_{1i}\prod\limits_{m=1}^{M} \exp^{(-\alpha_m y_i G_m(x_i))} \\ = \prod\limits_{m=1}^{M}Z_m$