1.Adaboost概念

提升方法的思路是綜合多個分類器，得到更準確的分類結果。即“三個臭皮匠頂個諸葛亮”。《統計學習方法》稱AdaBoost是提升算法的代表，所謂提升算法，指的是一種常用的統計學習方法，應用廣泛且有效。在分類問題中，它通過改變訓練樣本的權重，學習多個分類器，并將這些分類器進行線性組合，提髙分類的性能。
AdaBoost算法的基本思想：
1）多輪訓練，多個分類器
2）每輪訓練增加錯誤分類樣本的權值，降低正確分類樣本的權值
3）降低錯誤率高的分類器的權值，增加正確率高的分類器的權值

2.Adaboost算法流程

給定一個二類分類的訓練數據集， $T={(x1,y1),(x2,y2),…(xn,yn)}T=\{({x_1},y_1),({x_2},y_2),\dots({x_n},y_n)\}$ ,其中 $χ_i∈X? R^n$ 表示實例的特征向量, $yi∈Y∈{+1,?1}y_i∈Y\in\{+1,-1\}$ , $X$ 是實例空間， $Y$ 是標記集合。AdaBoost利用以下算法，從訓練數據中學習一系列弱分類器或基本分類器，并將這些弱分類器線性組合成為一個強分類器。
AdaBoost算法
輸入：訓練數據集 $T={(x1,y1),(x2,y2),…(xn,yn)}T=\{({x_1},y_1),({x_2},y_2),\dots({x_n},y_n)\}$ ,其中 $χ_i∈X? R^n$ , $yi∈Y∈{+1,?1}y_i∈Y\in\{+1,-1\}$ ；弱學習算法；
輸出：最終分類器 $G (x)$ 。
(1)初始化訓練數據的權值分布

$D_1=(W_{11},...,W_{1i},...,W_{1n})$

每個w的下標由兩部分構成，前一個數表示當前迭代次數，與D的下標保持一致，后一個數表示第幾個權值，與位置保持一致。初始情況下，每個權值都是均等的。
(2)對 $m = 1, 2, . . . M$
（這里的M表示訓練的迭代次數，是由用戶指定的。每輪迭代產生一個分類器，最終就有M個分類器，當然我們也可以設置一些條件，滿足某些條件時跳出迭代，例如，所有樣本都分對了，誤差為0時，跳出迭代）：
(a)使用具有權值分布的訓練數據集學習，得到基本分類器

$Gm(x):X→{+1,?1}G_m(x):X{\rightarrow} \{+1,-1\}$

(b)在 $G_m(x)$ 訓練數據集上的分類誤差率

$em=∑iNP(Gm(xi)≠yi)=∑iNwmiI(Gm(xi)≠yi))e_m=\sum_i^NP(G_m(x_i){\neq}y_i)=\sum_i^Nw_{mi}I(G_m(x_i){\neq}y_i))$

分類誤差率這個名字可能產生誤解，這里其實是個加權和。
(c）計算 $G_m(x)$ 的系數

$αm=12log1?emem\alpha_m = \frac{1}{2}log{\frac{1-e_m}{e_m}}$

這里的對數是自然對數。 $a_m$ 表示 $G_m(x)$ 在最終分類器中的重要性。由式 $αm=12log1?emem\alpha_m = \frac{1}{2}log{\frac{1-e_m}{e_m}}$ 可知，當 $e_m<=1/2$ 時， $a_m>=0$ ,并且 $a_m$ 隨著 $e_m$ 的減小而增大，所以分類誤差率越小的基本分類器在最終分類器中的作用越大。

(d)更新訓練數據集的權值分布

$D_{m+1}=(W_{m+1,1},...,W_{m+1,i},...,W_{m+1,n})$

$wm+1,i=wm,iZme?αmyiGm(xi)w_{m+1, i}=\frac{w_{m, i}}{Z_m}e^{-\alpha_my_iG_m(x_i)}$

y只有正負一兩種取值，所以上式可以寫作：

$wm+1,i={wmiZme?am,Gm(xi)=yiwmiZmeam,Gm(xi)≠yiw_{m+1,i}=\begin{cases} \frac{w_{mi}}{Z_m}e^{-a_m},G_m(x_i)=y_i \\ \frac{w_{mi}}{Z_m}e^{a_m},G_m(x_i){\neq}y_i \end{cases}$

這里， $Z_m$ 是規范化因子

$Zm=∑i=1Nwmiexp(?αmyiGm(xi))Z_m=\sum_{i=1}^Nw_{m i}exp({-\alpha_my_iG_m(x_i)})$

它使 $D_{m+1}$ 成為一個概率分布。
由此可知，被基本分類器誤分類樣本的權值得以擴大，而被正確分類樣本的權值卻得以縮小。兩相比較，誤分類樣本的權值被放大 $e2am=1?ememe^{2am} = {\frac{1-e_m}{e_m}}$ 倍。因此，誤分類樣本在下一輪學習中起更大的作用。不改變所給的訓練數據，而不斷改變訓練數據權值的分布，使得訓練數據在基本分類器的學習中起不同的作用，這是AdaBoost的一個特點。

(3)構建基本分類器的線性組合:

$f(x)=∑m=1MamGm(x)f(x)=\sum_{m=1}^{M}a_mG_m(x)$

得到最終分類器:

$G(x)=sign(f(x))=sign(∑m=1MamGm(x))G(x)=sign(f(x))=sign(\sum_{m=1}^{M}a_mG_m(x))$
這里需要注意的是，我們得到的是M個f(x)方程，需要將每個方程的結果求和，最好只取結果的正負號，在Adaboost中我們的預測結果與數值是無關的。

3.完整代碼

代碼運行結果：
在這里插入圖片描述

# -*- coding: utf-8 -*-
"""@Time    : 2018/12/04 13:58@Author  : hanzi5@Email   : hanzi5@yeah.net@File    : Adaboost.py@Software: PyCharm
"""
import numpy as np
#import pandas as pd
import matplotlib
import matplotlib.pyplot as pltmatplotlib.rcParams['font.family']='SimHei'  # 用來正常顯示中文
plt.rcParams['axes.unicode_minus']=False     # 用來正常顯示負號def splitDataSet(dataSet, i, value,types='lt'):"""
#劃分數據集，只進行一次劃分的樹，將劃分后的結果返回:param dataSet: 數據:param i: 特征的下標:param value: 閾值:param types: 大于或小于:return: 分類結果，注意返回的直接就是1，-1分類結果"""retArray = np.ones((np.shape(dataSet)[0],1))     # 默認類型都為1if types=='lt':   # 使用(小于等于value)劃分數據，滿足條件的將結果值改為-1retArray[dataSet[:,i]<=value]= -1.0  elif types=='gt': # 使用(大于value)劃分數據，滿足條件的將結果值改為-1retArray[dataSet[:,i]>value]= -1.0  return retArray def bulidSimpleTree(dataSet,y,D):"""
創建一個最簡單的樹，只進行一次劃分，相當于一個樹樁:param dataSet: 數據特征矩陣:param y: 標簽向量:param D: 訓練數據的權重向量:return: 最佳決策樹,最小的錯誤率加權和,最優預測結果"""m,n=dataSet.shape                      # 樣本行數及列數numFeatures = len(dataSet[0]) - 1      # 最后一列為y，計算x特征列數numSteps=10                            # 用于計算步長，進行numSteps等分minError=np.inf                        # 初始化損失值bestTree={}                            # 使用dict存儲最優的一系列樹for i in range(numFeatures):           # 遍歷所有x特征列# i=0rangeMin = dataSet[:, i].min()     # 該xi維的最小值rangeMax = dataSet[:, i].max()     # 該xi維的最大值stepSize = (rangeMax - rangeMin) / numSteps # 步長for j in range(-1,int(numSteps) + 1):    # 循環尋找最優切分點# j=-1for inequal in ['lt', 'gt']:         # 遍歷(lt小于等于)及(gt大于)# inequal=1value = (rangeMin + float(j) * stepSize) # 切分值predictedVals = splitDataSet(dataSet, i, value, inequal)  # 獲取切分后的數據errArr = np.mat(np.ones((m, 1)))errArr[predictedVals == y] = 0  # 預測正確的樣本對應的錯誤率為0,否則為1weightedError=D.T*errArr        # 《統計學習方法》李航P138，8.1，計算訓練數據上的分類誤差率if weightedError < minError:    # 記錄最優樹樁決策樹分類器minError = weightedError    # 計算錯誤率加權和bestClasEst = predictedVals.copy() # 最好的預測結果bestTree['column'] = i             # 維度xbestTree['splitValue'] = value     # 切分值bestTree['ineq'] = inequal         # 切分方法(lt小于等于)及(gt大于)return bestTree, minError, bestClasEst# 基于單層決策樹的adaboost分類器
def adaboost(dataSet,maxLoop=100):"""
基于單層決策樹的ada訓練:param dataSet: 樣本x及y:param maxLoop: 迭代次數:return: 一系列弱分類器及其權重,樣本分類結果"""adaboostTree=[]m,n=dataSet.shape                     # 樣本行數及列數y=dataSet[:,-1].reshape((-1,1))       # 將y提取出來，方便進行計算D = np.array(np.ones((m,1))/m)        # 將每個樣本的權重初始化為均等，有多少條數據就有多少個daggClassEst = np.mat(np.zeros((m,1))) # 每個數據點的類別估計累計值for i in range(maxLoop):              # maxLoop超參數，總迭代次數bestTree, minError, bestClasEst=bulidSimpleTree(dataSet,y,D)alpha=0.5*np.log((1-minError)/(minError+0.00001)) # 《統計學習方法》李航P139，8.2，計算Gm的系數，分母加一個小數避免除數為0bestTree['alpha'] = alpha.getA()[0][0]            # 將matrix中的值提取出來，并加入到bestTree中adaboostTree.append(bestTree)                     # 將樹存入list中存儲D=D*np.exp(-alpha.getA()[0][0]*y*bestClasEst)     # 更新權重D，《統計學習方法》李航P139，8.3-8.5，計算Gm(x)的系數D=D/D.sum()                                       # 歸一化權重值，統計學習方法》李航P139，8.5，計算Zm# 計算所有分類器的誤差,如果為0則終止訓練aggClassEst += alpha.getA()[0][0]*bestClasEst     # 分類估計累計值，adaboost是線性運行的，需要將每次的樹預測結果相加aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(y),np.ones((m,1))) # aggClassEst每個元素的符號代表分類結果,如果與y不等則表示錯誤，統計學習方法》李航P138，8.8errorRate = aggErrors.sum()/m                     # 平均分類誤差print( "total error: ",errorRate)if errorRate == 0.0:                              # 平均分類誤差等于0的，說明數據已經全部分類正確，跳出循環breakreturn adaboostTree,aggClassEstdef adaClassify(data, adaboostTree):"""
對預測數據進行分類:param data: 預測樣本x及y:param adaboostTree: 使用訓練數據，訓練好的決策樹:return: 預測樣本分類結果"""dataMatrix = np.mat(data)  m = np.shape(dataMatrix)[0]aggClassEst = np.mat(np.zeros((m, 1)))for i in range(len(adaboostTree)):                     # 遍歷所有adaboostTree，將估計值累加classEst = splitDataSet(dataMatrix, adaboostTree[i]['column'], adaboostTree[i]['splitValue'], adaboostTree[i]['ineq'])  aggClassEst += adaboostTree[i]['alpha'] * classEst # 分類估計累計值，adaboost是線性運行的，需要將每次的樹預測結果相加result = np.sign(aggClassEst)                          # 只取正負號，《統計學習方法》李航P139，8.8return resultdef plotData(dataSet):"""
數據畫圖"""type1_x1 = []type1_x2 = []type2_x1 = []type2_x2 = []# 取兩類x1及x2值畫圖type1_x1 = dataSet[dataSet[:,-1] == -1][:,:-1][:,0].tolist()type1_x2 = dataSet[dataSet[:,-1] == -1][:,:-1][:,1].tolist()type2_x1 = dataSet[dataSet[:,-1] == 1][:,:-1][:,0].tolist()type2_x2 = dataSet[dataSet[:,-1] == 1][:,:-1][:,1].tolist()# 畫點fig = plt.figure()ax = fig.add_subplot(111)ax.scatter(type1_x1,type1_x2, marker='s', s=90)ax.scatter(type2_x1,type2_x2, marker='o', s=50, c='red')plt.title('Adaboost訓練數據')if __name__ == '__main__':print('\n1、Adaboost，開始')dataSet = np.array([[ 1. , 2.1, 1 ],[ 2. , 1.1, 1 ],[ 1.3, 1. , -1],[ 1. , 1. , -1],[ 2. , 1. , 1 ]])#classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]# 畫圖print('\n2、Adaboost數據畫圖')plotData(dataSet)print('\n3、計算Adaboost樹')adaboostTree,aggClassEst=adaboost(dataSet)# 對數據進行分類print('\n4、對[5,5],[0, 0]點，使用Adaboost進行分類：')print( adaClassify([[5,5],[0, 0]], adaboostTree))