2023年第十三屆MathorCup高校數(shù)學(xué)建模挑戰(zhàn)賽

資料思路分享Q群：714452621

集成算法概念

在機(jī)器學(xué)習(xí)算法中，有一種算法叫做集成算法，AdaBoost 算法是集成算法的一種。我們先來看下什么是集成算法。

通常，一個 Boss 在做一項(xiàng)決定之前，會聽取多個 Leader 的意見。集成算法就是這個意思，它的基本含義就是集眾算法之所長。

前面已經(jīng)介紹過許多算法，每種算法都有優(yōu)缺點(diǎn)。那么是否可以將這些算法組合起來，共同做一項(xiàng)決定呢？答案是肯定的。這就誕生了集成算法（Ensemble Methods）。

集成算法的基本架構(gòu)如下：

算法的組合有多種形式，比如將不同的算法集成起來，或者將同一種算法以不同的形式集成起來。

常見的集成算法有四大類：

• bagging：裝袋法，代表算法為 RandomForest（隨機(jī)森林）。

• boosting：提升法，代表算法有 AdaBoost，XGBoost 等。

• stacking：堆疊法。

• blending：混合法。

多個算法以不同的方式可以組合成集成算法，如果再深入探究的話，不同的集成方法也可以組合起來：

如果將 boosting 算法的輸出作為bagging 算法的基學(xué)習(xí)器，得到的是 MultiBoosting 算法； 如果將 bagging 算法的輸出作為boosting 算法的基學(xué)習(xí)器，得到的是 IterativBagging 算法。 對于集成算法的集成，這里不再過多介紹。

bagging 與 boosting 算法

bagging和 boosting是兩個比較著名的集成算法。

bagging 算法

bagging 算法是將一個原始數(shù)據(jù)集隨機(jī)抽樣成 N 個新的數(shù)據(jù)集。然后將這N 個新的數(shù)據(jù)集作用于同一個機(jī)器學(xué)習(xí)算法，從而得到 N 個模型，最終集成一個綜合模型。

在對新的數(shù)據(jù)進(jìn)行預(yù)測時(shí)，需要經(jīng)過這 N 個模型（每個模型互不依賴干擾）的預(yù)測（投票），最終綜合 N 個投票結(jié)果，來形成最后的預(yù)測結(jié)果。

boosting 算法

boosting 算法的含義為提升學(xué)習(xí)，它將多個弱分類器組合起來形成一個強(qiáng)分類器。

boosting 算法是將一個原始數(shù)據(jù)集使用同一個算法迭代學(xué)習(xí) N 次，每次迭代會給數(shù)據(jù)集中的樣本分配不同的權(quán)重。

分類正確的樣本會在下一次迭代中降低權(quán)重，而分類錯誤的樣本會在下一次迭代中提高權(quán)重，這樣做的目的是，使得算法能夠?qū)ζ洳簧瞄L（分類錯誤）的數(shù)據(jù)不斷的加強(qiáng)提升學(xué)習(xí)，最終使得算法的成功率越來越高。

每次迭代都會訓(xùn)練出一個新的帶有權(quán)重的模型，迭代到一定的次數(shù)或者最終模型的錯誤率足夠低時(shí)，迭代停止。最終集成一個強(qiáng)大的綜合模型。

在對新的數(shù)據(jù)進(jìn)行預(yù)測時(shí)，需要經(jīng)過這 N 個模型的預(yù)測，每個模型的預(yù)測結(jié)果會帶有一個權(quán)重值，最終綜合 N 個模型結(jié)果，來形成最后的預(yù)測結(jié)果。

boosting 算法中每個模型的權(quán)重是不相等的，而bagging 算法中每個模型的權(quán)重是相等的。

AdaBoost 算法

AdaBoost 算法是非常流行的一種 boosting 算法，它的全稱為 Adaptive Boosting，即自適應(yīng)提升學(xué)習(xí)。

AdaBoost 算法由Freund 和 Schapire 于1995 年提出。這兩位作者寫了一篇關(guān)于AdaBoost 的簡介論文，這應(yīng)該是關(guān)于AdaBoost 算法的最權(quán)威的資料了。為了防止鏈接丟失，我將論文下載了，放在了這里。

AdaBoost 算法 和 SVM 算法被很多人認(rèn)為是監(jiān)督學(xué)習(xí)中最強(qiáng)大的兩種算法。

AdaBoost 算法的運(yùn)行過程如下：

1. 為訓(xùn)練集中的每個樣本初始化一個權(quán)重 wi，初始時(shí)的權(quán)重都相等。

2. 根據(jù)樣本訓(xùn)練出一個模型 Gi，并計(jì)算該模型的錯誤率 ei 和權(quán)重 ai。

3. 根據(jù)權(quán)重 ai 將每個樣本的權(quán)重調(diào)整為 wi+1，使得被正確分類的樣本權(quán)重降低，被錯誤分類的樣本權(quán)重增加（這樣可以著重訓(xùn)練錯誤樣本）。

4. 這樣迭代第2，3 步，直到訓(xùn)練出最終模型。

這個過程中，我們假設(shè) x 為樣本，Gi(x) 為第 i 輪訓(xùn)練出的模型，ai 為 Gi(x) 的權(quán)重，一共迭代 n 輪，那么最終模型 G(x) 的計(jì)算公式為：

示例代碼

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from numpy import *

# 模擬創(chuàng)建數(shù)據(jù)集
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]
? ?#返回?cái)?shù)據(jù)集和標(biāo)簽
? ?return datMat, classLabels

# 通過閾值比較對數(shù)據(jù)進(jìn)行分類
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
? ?"""
? ?Function： ? 通過閾值比較對數(shù)據(jù)進(jìn)行分類

? ?Input： ? ? ?dataMatrix：數(shù)據(jù)集
? ? ? ? ? ? ? ?dimen：數(shù)據(jù)集列數(shù)
? ? ? ? ? ? ? ?threshVal：閾值
? ? ? ? ? ? ? ?threshIneq：比較方式：lt，gt

? ?Output： retArray：分類結(jié)果
? ?"""
? ?#新建一個數(shù)組用于存放分類結(jié)果，初始化都為1
? ?retArray = ones((shape(dataMatrix)[0],1))
? ?#lt：小于，gt；大于；根據(jù)閾值進(jìn)行分類，并將分類結(jié)果存儲到retArray
? ?if threshIneq == 'lt':
? ? ? ?retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
? ?else:
? ? ? ?retArray[dataMatrix[:, dimen] > threshVal] = -1.0
? ?#返回分類結(jié)果
? ?return retArray

# 找到最低錯誤率的單層決策樹
def buildStump(dataArr, classLabels, D):
? ?"""
? ?Function： ? 找到最低錯誤率的單層決策樹

? ?Input： ? ? ?dataArr：數(shù)據(jù)集
? ? ? ? ? ? ? ?classLabels：數(shù)據(jù)標(biāo)簽
? ? ? ? ? ? ? ?D：權(quán)重向量

? ?Output： bestStump：分類結(jié)果
? ? ? ? ? ? ? ?minError：最小錯誤率
? ? ? ? ? ? ? ?bestClasEst：最佳單層決策樹
? ?"""
? ?#初始化數(shù)據(jù)集和數(shù)據(jù)標(biāo)簽
? ?dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
? ?#獲取行列值
? ?m,n = shape(dataMatrix)
? ?#初始化步數(shù)，用于在特征的所有可能值上進(jìn)行遍歷
? ?numSteps = 10.0
? ?#初始化字典，用于存儲給定權(quán)重向量D時(shí)所得到的最佳單層決策樹的相關(guān)信息
? ?bestStump = {}
? ?#初始化類別估計(jì)值
? ?bestClasEst = mat(zeros((m,1)))
? ?#將最小錯誤率設(shè)無窮大，之后用于尋找可能的最小錯誤率
? ?minError = inf
? ?#遍歷數(shù)據(jù)集中每一個特征
? ?for i in range(n):
? ? ? ?#獲取數(shù)據(jù)集的最大最小值
? ? ? ?rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max()
? ? ? ?#根據(jù)步數(shù)求得步長
? ? ? ?stepSize = (rangeMax - rangeMin) / numSteps
? ? ? ?#遍歷每個步長
? ? ? ?for j in range(-1, int(numSteps) + 1):
? ? ? ? ? ?#遍歷每個不等號
? ? ? ? ? ?for inequal in ['lt', 'gt']:
? ? ? ? ? ? ? ?#設(shè)定閾值
? ? ? ? ? ? ? ?threshVal = (rangeMin + float(j) * stepSize)
? ? ? ? ? ? ? ?#通過閾值比較對數(shù)據(jù)進(jìn)行分類
? ? ? ? ? ? ? ?predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
? ? ? ? ? ? ? ?#初始化錯誤計(jì)數(shù)向量
? ? ? ? ? ? ? ?errArr = mat(ones((m,1)))
? ? ? ? ? ? ? ?#如果預(yù)測結(jié)果和標(biāo)簽相同，則相應(yīng)位置0
? ? ? ? ? ? ? ?errArr[predictedVals == labelMat] = 0
? ? ? ? ? ? ? ?#計(jì)算權(quán)值誤差，這就是AdaBoost和分類器交互的地方
? ? ? ? ? ? ? ?weightedError = D.T * errArr
? ? ? ? ? ? ? ?#打印輸出所有的值
? ? ? ? ? ? ? ?#print("split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError))
? ? ? ? ? ? ? ?#如果錯誤率低于minError，則將當(dāng)前單層決策樹設(shè)為最佳單層決策樹，更新各項(xiàng)值
? ? ? ? ? ? ? ?if weightedError < minError:
? ? ? ? ? ? ? ? ? ?minError = weightedError
? ? ? ? ? ? ? ? ? ?bestClasEst = predictedVals.copy()
? ? ? ? ? ? ? ? ? ?bestStump['dim'] = i
? ? ? ? ? ? ? ? ? ?bestStump['thresh'] = threshVal
? ? ? ? ? ? ? ? ? ?bestStump['ineq'] = inequal
? ?#返回最佳單層決策樹，最小錯誤率，類別估計(jì)值
? ?return bestStump, minError, bestClasEst

# 找到最低錯誤率的單層決策樹
def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
? ?"""
? ?Function： ? 找到最低錯誤率的單層決策樹

? ?Input： ? ? ?dataArr：數(shù)據(jù)集
? ? ? ? ? ? ? ?classLabels：數(shù)據(jù)標(biāo)簽
? ? ? ? ? ? ? ?numIt：迭代次數(shù)

? ?Output： weakClassArr：單層決策樹列表
? ? ? ? ? ? ? ?aggClassEst：類別估計(jì)值
? ?"""
? ?#初始化列表，用來存放單層決策樹的信息
? ?weakClassArr = []
? ?#獲取數(shù)據(jù)集行數(shù)
? ?m = shape(dataArr)[0]
? ?#初始化向量D每個值均為1/m，D包含每個數(shù)據(jù)點(diǎn)的權(quán)重
? ?D = mat(ones((m,1))/m)
? ?#初始化列向量，記錄每個數(shù)據(jù)點(diǎn)的類別估計(jì)累計(jì)值
? ?aggClassEst = mat(zeros((m,1)))
? ?#開始迭代
? ?for i in range(numIt):
? ? ? ?#利用buildStump()函數(shù)找到最佳的單層決策樹
? ? ? ?bestStump, error, classEst = buildStump(dataArr, classLabels, D)
? ? ? ?#print("D: ", D.T)
? ? ? ?#根據(jù)公式計(jì)算alpha的值，max(error, 1e-16)用來確保在沒有錯誤時(shí)不會發(fā)生除零溢出
? ? ? ?alpha = float(0.5 * log((1.0 - error) / max(error, 1e-16)))
? ? ? ?#保存alpha的值
? ? ? ?bestStump['alpha'] = alpha
? ? ? ?#填入數(shù)據(jù)到列表
? ? ? ?weakClassArr.append(bestStump)
? ? ? ?#print("classEst: ", classEst.T)
? ? ? ?#為下一次迭代計(jì)算D
? ? ? ?expon = multiply(-1 * alpha * mat(classLabels).T, classEst)
? ? ? ?D = multiply(D, exp(expon))
? ? ? ?D = D / D.sum()
? ? ? ?#累加類別估計(jì)值
? ? ? ?aggClassEst += alpha * classEst
? ? ? ?#print("aggClassEst: ", aggClassEst.T)
? ? ? ?#計(jì)算錯誤率，aggClassEst本身是浮點(diǎn)數(shù)，需要通過sign來得到二分類結(jié)果
? ? ? ?aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m,1)))
? ? ? ?errorRate = aggErrors.sum() / m
? ? ? ?# print("total error: ", errorRate)
? ? ? ?#如果總錯誤率為0則跳出循環(huán)
? ? ? ?if errorRate == 0.0: break
? ?#返回單層決策樹列表和累計(jì)錯誤率
? ?return weakClassArr
? ?#return weakClassArr, aggClassEst

# AdaBoost分類函數(shù)
def adaClassify(datToClass, classifierArr):
? ?"""
? ?Function： ? AdaBoost分類函數(shù)

? ?Input： ? ? ?datToClass：待分類樣例
? ? ? ? ? ? ? ?classifierArr：多個弱分類器組成的數(shù)組

? ?Output： sign(aggClassEst)：分類結(jié)果
? ?"""
? ?#初始化數(shù)據(jù)集
? ?dataMatrix = mat(datToClass)
? ?#獲得待分類樣例個數(shù)
? ?m = shape(dataMatrix)[0]
? ?#構(gòu)建一個初始化為0的列向量，記錄每個數(shù)據(jù)點(diǎn)的類別估計(jì)累計(jì)值
? ?aggClassEst = mat(zeros((m,1)))
? ?#遍歷每個弱分類器
? ?for i in range(len(classifierArr)):
? ? ? ?#基于stumpClassify得到類別估計(jì)值
? ? ? ?classEst = stumpClassify(dataMatrix, classifierArr[i]['dim'], classifierArr[i]['thresh'], classifierArr[i]['ineq'])
? ? ? ?#累加類別估計(jì)值
? ? ? ?aggClassEst += classifierArr[i]['alpha']*classEst
? ? ? ?#打印aggClassEst，以便我們了解其變化情況
? ? ? ?#print(aggClassEst)
? ?#返回分類結(jié)果，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高校數(shù)學(xué)建模挑戰(zhàn)賽

資料思路分享Q群：714452621