2023MathorCup建模思路 - 案例：AdaBoost 算法
2023年第十三届MathorCup高校数学建模挑战赛
资料思路分享Q群：714452621
在机器学习算法中，有一种算法叫做集成算法，AdaBoost 算法是集成算法的一种。我们先来看下什么是集成算法。
通常，一个 Boss 在做一项决定之前，会听取多个 Leader 的意见。集成算法就是这个意思，它的基本含义就是集众算法之所长。
前面已经介绍过许多算法，每种算法都有优缺点。那么是否可以将这些算法组合起来，共同做一项决定呢？答案是肯定的。这就诞生了集成算法（Ensemble Methods）。
集成算法的基本架构如下：
算法的组合有多种形式，比如将不同的算法集成起来，或者将同一种算法以不同的形式集成起来。
常见的集成算法有四大类：
bagging：装袋法，代表算法为 RandomForest（随机森林）。
boosting：提升法，代表算法有 AdaBoost，XGBoost 等。
stacking：堆叠法。
blending：混合法。
多个算法以不同的方式可以组合成集成算法，如果再深入探究的话，不同的集成方法也可以组合起来：
如果将 boosting 算法的输出作为bagging 算法的基学习器，得到的是 MultiBoosting 算法； 如果将 bagging 算法的输出作为boosting 算法的基学习器，得到的是 IterativBagging 算法。 对于集成算法的集成，这里不再过多介绍。
bagging 与 boosting 算法
bagging和 boosting是两个比较著名的集成算法。
bagging 算法
bagging 算法是将一个原始数据集随机抽样成 N 个新的数据集。然后将这N 个新的数据集作用于同一个机器学习算法，从而得到 N 个模型，最终集成一个综合模型。
在对新的数据进行预测时，需要经过这 N 个模型（每个模型互不依赖干扰）的预测（投票），最终综合 N 个投票结果，来形成最后的预测结果。
boosting 算法
boosting 算法的含义为提升学习，它将多个弱分类器组合起来形成一个强分类器。
boosting 算法是将一个原始数据集使用同一个算法迭代学习 N 次，每次迭代会给数据集中的样本分配不同的权重。
分类正确的样本会在下一次迭代中降低权重，而分类错误的样本会在下一次迭代中提高权重，这样做的目的是，使得算法能够对其不擅长（分类错误）的数据不断的加强提升学习，最终使得算法的成功率越来越高。
每次迭代都会训练出一个新的带有权重的模型，迭代到一定的次数或者最终模型的错误率足够低时，迭代停止。最终集成一个强大的综合模型。
在对新的数据进行预测时，需要经过这 N 个模型的预测，每个模型的预测结果会带有一个权重值，最终综合 N 个模型结果，来形成最后的预测结果。
boosting 算法中每个模型的权重是不相等的，而bagging 算法中每个模型的权重是相等的。
AdaBoost 算法
AdaBoost 算法是非常流行的一种 boosting 算法，它的全称为 Adaptive Boosting，即自适应提升学习。
AdaBoost 算法由Freund 和 Schapire 于1995 年提出。这两位作者写了一篇关于AdaBoost 的简介论文，这应该是关于AdaBoost 算法的最权威的资料了。为了防止链接丢失，我将论文下载了，放在了这里。
AdaBoost 算法 和 SVM 算法被很多人认为是监督学习中最强大的两种算法。
AdaBoost 算法的运行过程如下：
为训练集中的每个样本初始化一个权重 wi，初始时的权重都相等。
根据样本训练出一个模型 Gi，并计算该模型的错误率 ei 和权重 ai。
根据权重 ai 将每个样本的权重调整为 wi+1，使得被正确分类的样本权重降低，被错误分类的样本权重增加（这样可以着重训练错误样本）。
这样迭代第2，3 步，直到训练出最终模型。
这个过程中，我们假设 x 为样本，Gi(x) 为第 i 轮训练出的模型，ai 为 Gi(x) 的权重，一共迭代 n 轮，那么最终模型 G(x) 的计算公式为：
示例代码
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from numpy import *
# 模拟创建数据集
def loadSimpData():
datMat = mat([[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, threshVal, threshIneq):
"""
Function： 通过阈值比较对数据进行分类
Input： dataMatrix：数据集
dimen：数据集列数
threshVal：阈值
threshIneq：比较方式：lt，gt
Output： retArray：分类结果
"""
#新建一个数组用于存放分类结果，初始化都为1
retArray = ones((shape(dataMatrix)[0],1))
#lt：小于，gt；大于；根据阈值进行分类，并将分类结果存储到retArray
if threshIneq == 'lt':
retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
else:
retArray[dataMatrix[:, dimen] > threshVal] = -1.0
#返回分类结果
return retArray
# 找到最低错误率的单层决策树
def buildStump(dataArr, classLabels, D):
"""
Function： 找到最低错误率的单层决策树
Input： dataArr：数据集
classLabels：数据标签
D：权重向量
Output： bestStump：分类结果
minError：最小错误率
bestClasEst：最佳单层决策树
"""
#初始化数据集和数据标签
dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
#获取行列值
m,n = shape(dataMatrix)
#初始化步数，用于在特征的所有可能值上进行遍历
numSteps = 10.0
#初始化字典，用于存储给定权重向量D时所得到的最佳单层决策树的相关信息
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)))
#如果预测结果和标签相同，则相应位置0
errArr[predictedVals == labelMat] = 0
#计算权值误差，这就是AdaBoost和分类器交互的地方
weightedError = D.T * errArr
#打印输出所有的值
#print("split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError))
#如果错误率低于minError，则将当前单层决策树设为最佳单层决策树，更新各项值
if weightedError < minError:
minError = weightedError
bestClasEst = predictedVals.copy()
bestStump['dim'] = i
bestStump['thresh'] = threshVal
bestStump['ineq'] = inequal
#返回最佳单层决策树，最小错误率，类别估计值
return bestStump, minError, bestClasEst
# 找到最低错误率的单层决策树
def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
"""
Function： 找到最低错误率的单层决策树
Input： dataArr：数据集
classLabels：数据标签
numIt：迭代次数
Output： weakClassArr：单层决策树列表
aggClassEst：类别估计值
"""
#初始化列表，用来存放单层决策树的信息
weakClassArr = []
#获取数据集行数
m = shape(dataArr)[0]
#初始化向量D每个值均为1/m，D包含每个数据点的权重
D = mat(ones((m,1))/m)
#初始化列向量，记录每个数据点的类别估计累计值
aggClassEst = mat(zeros((m,1)))
#开始迭代
for i in range(numIt):
#利用buildStump()函数找到最佳的单层决策树
bestStump, error, classEst = buildStump(dataArr, classLabels, D)
#print("D: ", D.T)
#根据公式计算alpha的值，max(error, 1e-16)用来确保在没有错误时不会发生除零溢出
alpha = float(0.5 * log((1.0 - error) / max(error, 1e-16)))
#保存alpha的值
bestStump['alpha'] = alpha
#填入数据到列表
weakClassArr.append(bestStump)
#print("classEst: ", classEst.T)
#为下一次迭代计算D
expon = multiply(-1 * alpha * mat(classLabels).T, classEst)
D = multiply(D, exp(expon))
D = D / D.sum()
#累加类别估计值
aggClassEst += alpha * classEst
#print("aggClassEst: ", aggClassEst.T)
#计算错误率，aggClassEst本身是浮点数，需要通过sign来得到二分类结果
aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m,1)))
errorRate = aggErrors.sum() / m
# print("total error: ", errorRate)
#如果总错误率为0则跳出循环
if errorRate == 0.0: break
#返回单层决策树列表和累计错误率
return weakClassArr
#return weakClassArr, aggClassEst
# AdaBoost分类函数
def adaClassify(datToClass, classifierArr):
"""
Function： AdaBoost分类函数
Input： datToClass：待分类样例
classifierArr：多个弱分类器组成的数组
Output： sign(aggClassEst)：分类结果
"""
#初始化数据集
dataMatrix = mat(datToClass)
#获得待分类样例个数
m = shape(dataMatrix)[0]
#构建一个初始化为0的列向量，记录每个数据点的类别估计累计值
aggClassEst = mat(zeros((m,1)))
#遍历每个弱分类器
for i in range(len(classifierArr)):
#基于stumpClassify得到类别估计值
classEst = stumpClassify(dataMatrix, classifierArr[i]['dim'], classifierArr[i]['thresh'], classifierArr[i]['ineq'])
#累加类别估计值
aggClassEst += classifierArr[i]['alpha']*classEst
#打印aggClassEst，以便我们了解其变化情况
#print(aggClassEst)
#返回分类结果，aggClassEst大于0则返回+1，否则返回-1
return sign(aggClassEst)
datMat, classLabels = loadSimpData()
classifierArr = adaBoostTrainDS(datMat, classLabels, 30)
print(classifierArr)
print(adaClassify([0,0], classifierArr))
print(adaClassify([[5,5],[0,0]], classifierArr))
2023年第十三届MathorCup高校数学建模挑战赛
资料思路分享Q群：714452621
