【機器學習入門二】集成學習及AdaBoost算法的python實現

時間 2019-12-08 標籤機器學習入門二集成學習 adaboost 算法 python 實現

本文主要基於周志華老師的《機器學習》第八章內容html

個體與集成

集成學習經過構建並結合多個學習器來完成學習任務。集成學習的通常結構如圖所示：

先產生一組個體學習器，在用某種策略把它們結合在一塊兒。個體學習器一般有一個現有的學習算法從訓練數據產生，如決策樹樁和BP神經網絡。個體學習器可使相同類型的也能夠是不一樣類型的，好比全是神經網絡或者同事含有神經網絡和決策樹樁。
集成學習經過將多個學習器進行結合，一般能夠得到比單一學習器顯著優越的泛化性能，尤爲是弱學習器（即泛化性能略優於隨機猜想的學習器，好比在二分類問題上精度略高於50%的分類器）。從理論上來講，使用弱學習器集成就足以得到好的性能。
如何提升集成學習的性能？這要求個體學習器應該「好而不一樣」。書上的例子很好且簡單易懂，這裏直接拿來。
在二分類任務中，假定三個分類器在三個測試樣本上的表現分別以下面的三個表所示，
其中對號表示分類正確，叉號表示分類錯誤，集成策略選擇投票法。在（a）中，每一個分類器都只有66.6%的精度，可是集成學習後達到了100%，（b）中，三個分類器徹底同樣，集成後沒有區別，（c）中，每一個分類器的精度都只有33.3%，集成後結果更差。這個例子直觀的解釋了爲何應該好而不一樣，即個體學習器要比較準確，而且各個個體學習器之間還要有必定的差別性。

集成學習根據個體學習器的生成方式能夠分爲2大類，若是個體學習器存在強依賴關係、必須串行生成的序列化方法，典型表明是Boosting。第二種是個體學習器之間不存在強依賴關係，能夠同時生成的並行化方法，如Bagging和隨機森林（Random Forest）。python

Boosting

Boosting是一族可將弱學習器提高爲強學習器的算法。算法的流程爲：先從初始訓練集訓練出一個個體學習器，再根據該學習器的表現對訓練樣本的分佈進行調整，使得先前學習器作錯的訓練樣本在後續受到更多關注，而後基於調整後的樣本分佈來訓練下一個個體學習器，如此反覆進行，直到個體學習器的數量達到事先指定的值T或者集成的偏差已經小於閾值，最終將這些個體學習器進行加權結合。web

算法流程

Boosting算法族中最著名的是AdaBoost算法。下面是算法的過程：算法

輸入：訓練集 $D=\{(x_1,y_1),.....,(x_m,y_m)\}$ ，基學習算法 $\xi$ ，訓練次數T
過程：
1. $\cal D_1(x)=1/m.\quad\quad$ (表示第一輪時每一個樣本的權重是相等的)
2. $for\quad t=1,2,3,...,T\quad\quad do:$
3. $\quad\quad h_t=\xi(D,\cal D_t);$
4. $\quad\quad \varepsilon_t=P_{x-\cal D_t}(h_t(x)\not= f(x));\quad\quad$ ( $f(x)是真實函數$ )
5. $\quad\quad if\quad \varepsilon_t>0.5\quad then\quad break$
6. $\quad\quad \alpha_t=\frac1 2 ln(\frac{1-\varepsilon_t}{\varepsilon_t});$
7. 數組

D_{t + 1} (x) = \frac{D_{t} (x)}{Z_{t}} \times {\begin{cases} e x p (- α_{t}), & i f h_{t} (x) = f (x) \\ e x p (α_{t}), & i f h_{t} (x) \neq f (x) \end{cases}

$\quad\quad\cal D_{t+1}(x)=\frac{\cal D_t(x)}{Z_t}\times \begin{cases} exp(-\alpha_t),&if\quad h_t(x)=f(x)\\ exp(\alpha_t),&if\quad h_t(x)\not=f(x) \end{cases}$

= \frac{D_{t} (x) e x p (- α_{t} f (x) h_{t} (x))}{Z_{t}}

$\quad\quad =\frac{\cal D_t(x)exp(-\alpha_tf(x)h_t(x))}{Z_t}\quad\quad$

Z_{t}

$Z_t$ 是規範化因子，確保

D_{t + 1}

$\cal D_{t+1}$ 是一個分佈。
8.

e n d f o r

$end \quad for$
輸出：

H (x) = s i g n (\sum_{t = 1}^{T} α_{t} h_{t} (x))

$H(x)=sign(\sum^{T}_{t=1}\alpha_th_t(x))$

基於加性模型對算法的證實

AdaBoost算法是基於加性模型，即基學習器的線性組合： $H(x)=\sum_{t=1}^{T}\alpha_th_t(x)\quad\quad\quad（1）$
來最小化指數損失函數： $l_{exp}(H|\cal D)={\Bbb E}_{x-{\cal D}}[e^{-f(x)\it H(x)}]\quad\quad \sf（2）$
這裏咱們採用指示函數 $\Bbb I(.)$ ，當括號內的表達式取值爲真時，函數值爲1，不然爲0。
在AdaBoost算法中，第一個基分類器 $h_1$ 是經過直接將基學習算法用於初始數據分佈而得。此後迭代的生成 $h_t$ 和 $\alpha_t$ ，當基學習器 $h_t$ 基於分佈 $\cal D_t$ 產生後，該基學習器的權重 $\alpha_t$ 應使得 $\alpha_th_t$ 最小化指數損失函數。
由此，相似於式（2），有：
網絡

\begin{array}{rcl} (1) & l_{e x p} (α_{t} h_{t} | D) & = & E_{x - D} [e^{- f (x) α_{t} h_{t}}] \\ (2) & = & E_{x - D} [e^{- α_{t}} I (f (x) = h_{t} (x)) + e^{α_{t}} I (f (x) \neq h_{t} (x))] \\ (3) & = & e^{- α_{t}} P_{x - D_{t}} (f (x) = h_{t} (x)) + e^{α_{t}} P_{x - D_{t}} (f (x) \neq h_{t} (x)) \\ (4) & = & e^{- α_{t}} (1 - ε_{t}) + e^{α_{t}} ε_{t} \end{array} （ 3 ）

$\begin{eqnarray}l_{exp}(\alpha_th_t|\cal D)&=&{\Bbb E}_{x-{\cal D}}[e^{-f(x)\alpha_th_t}]\\ &=&{\Bbb E}_{x-{\cal D}}[e^{-\alpha_t}\Bbb I(f(x)=h_t(x))+e^{\alpha_t}\Bbb I(f(x)\not= h_t(x))]\\ &=&e^{-\alpha_t}P_{x-\cal D_t}(f(x)=h_t(x))+e^{\alpha_t}P_{x-\cal D_t}(f(x)\not=h_t(x))\\ &=&e^{-\alpha_t}(1-\varepsilon_t)+e^{\alpha_t}\varepsilon_t \end{eqnarray}\quad\quad（3）$
考慮指數損失函數的導數：

對於

h_{t}

$h_t$ 。AdaBoost算法在得到

H_{t - 1}

$H_{t-1}$ 以後樣本分佈將進行調整，使下一輪的基學習器

h_{t}

$h_t$ 能糾正

H_{t - 1}

$H_{t-1}$ 的一些錯誤，理想的

h_{t}

$h_t$ 能糾正

H_{t - 1}

$H_{t-1}$ 的所有錯誤，即最小化：

該結果代表理想的

h_{t}

$h_t$ 將在分佈

D_{t}

$\cal D_t$ 下最小化分類偏差。考慮到

D_{t}

$\cal D_t$ 和

D_{t + 1}

$\cal D_{t+1}$ 的關係，有：

這樣咱們就獲得了算法更新樣本權重和個體分類器權重的參數。

AdaBoost算法的特色

在上面的算法過程的第五步的意思是，Boosting算法在訓練的每一輪迭代都要檢查當前的基學習器是否知足基本條件（這裏是表示這個基學習器是否是比隨機猜想的效果要好），一旦條件不知足，則當前的基學習器及被拋棄且學習過程中止。
從方差-誤差的角度來看，Boosting主要關注下降誤差，即便指望輸出與實際結果儘可能吻合（方差的意思是學習器在樣本數相同的不一樣訓練集下產生的不一樣）。所以Boosting算法能基於泛化性能至關弱的學習器構造出很強的集成。app

Bagging和隨機森林

Bagging算法

能夠證實，要想獲得泛化性能很強的集成，集成中的個體學習器應該儘量相互獨立（證實過程見《機器學習》第8章172頁）。可是「獨立」在現實世界中顯然沒法達到，可是能夠設法使基學習器儘量有較大的差別。一種可能的作法是對給定的訓練集採樣，產生若干個不一樣的子集，再從每一個數據子集訓練出一個基學習器，這樣，由於每一個基學習器的訓練樣本不一樣，他們相互之間就能夠有較大的差距。

圖爲Bagging算法的流程圖。
給定一個包含m個樣本的數據集，一種一般的採樣方法是先隨機取出一個樣本，再將其放回初始數據集，使得下次採樣時該數據集仍然有可能被抽到。這樣，通過m次採樣，能夠獲得一個和初始數據集一樣大小的新的數據集。初始訓練集中約有63.2%的樣本出如今採樣集中。
這樣，咱們能夠獲得T個採樣集，而後基於每一個採樣集訓練出一個基學習器，再將這些基學習器進行結合，這就是Bagging算法的基本流程。在集成時，一般採用簡單投票法，對迴歸則採用簡單平均。若是分類預測時出現兩個類別獲得的票數同樣多，則隨機選取一個類別，也能夠進一步學習器投票的置信度來肯定最終類別。
從誤差-方差分解的角度來看，和AdaBoost不一樣的是，Bagging算法主要關注於下降方差（方差的簡單理解見前面，深刻研究請見《機器學習》2.5節），所以它在不剪枝決策樹、神經網絡等易受樣本擾動的學習器上效用更爲明顯。dom

隨機森林

隨機森林RF自Bagging算法擴展而來。RF在以決策樹爲基學習器構建bagging集成的基礎上，進一步在決策樹的訓練過程當中加入了隨機屬性選擇。
方法是對基決策樹的每個節點，先從該節點的屬性集合中隨機選擇一個包含k個屬性的子集，而後再從這個子集中選擇一個最優屬性用於劃分。若是當前屬性集合共有d個屬性，則推薦取 $k=log_2(d)$ 。
顯然Bagging基學習器中的多樣性僅來自樣本的擾動，而隨機森林的多樣性來自樣本和屬性擾動，這就使得最終集成的泛化性能可經過個體學習器之間差別度的增長進一步提高。
顯然隨機森林的訓練效率要優於以決策樹爲個體學習器的bagging，由於Bagging會考察當前節點的所有屬性，而隨機森林只考察一部分屬性。機器學習

AdaBoost的python實現

此次不是本身的代碼，找到一個大佬的代碼。svg

# -*- coding: utf-8 -*-
""" Created on Thu Jun 01 09:29:18 2017 Adaboost @author: liujiping """
import numpy as np

def loadSimData():
    ''' 輸入：無 功能：提供一個兩個特徵的數據集 輸出：帶有標籤的數據集 '''
    datMat = np.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

def stumpClassify(dataMatrix,dimen,thresholdValue,thresholdIneq):
    ''' 輸入：數據矩陣，特徵維數，某一特徵的分類閾值，分類不等號 功能：輸出決策樹樁標籤 輸出：標籤 '''
    returnArray =  np.ones((np.shape(dataMatrix)[0],1))
    if thresholdIneq == 'lt':
        returnArray[dataMatrix[:,dimen] <= thresholdValue] = -1
    else:
        returnArray[dataMatrix[:,dimen] > thresholdValue] = -1
    return returnArray

def buildStump(dataArray,classLabels,D):
    ''' 輸入：數據矩陣，對應的真實類別標籤，特徵的權值分佈 功能：在數據集上，找到加權錯誤率（分類錯誤率）最小的單層決策樹，顯然，該指標函數與權重向量有密切關係 輸出：最佳樹樁（特徵，分類特徵閾值，不等號方向），最小加權錯誤率，該權值向量D下的分類標籤估計值 '''
    dataMatrix = np.mat(dataArray); labelMat = np.mat(classLabels).T
    m,n = np.shape(dataMatrix)
    stepNum = 10.0; bestStump = {}; bestClassEst = np.mat(np.zeros((m,1)))
    minError = np.inf
    for i in range(n):
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max()
        stepSize = (rangeMax - rangeMin)/stepNum
        for j in range(-1, int(stepNum)+1):
            for thresholdIneq in ['lt', 'gt']:
                thresholdValue =  rangeMin + float(j) * stepSize
                predictClass = stumpClassify(dataMatrix,i,thresholdValue,thresholdIneq)
                errArray =  np.mat(np.ones((m,1)))
                errArray[predictClass == labelMat] = 0
                weightError = D.T * errArray
                #print "split: dim %d, thresh: %.2f,threIneq:%s,weghtError %.3F" %(i,thresholdValue,thresholdIneq,weightError)
                if weightError < minError:
                    minError = weightError
                    bestClassEst = predictClass.copy()
                    bestStump['dimen'] = i
                    bestStump['thresholdValue'] = thresholdValue
                    bestStump['thresholdIneq'] = thresholdIneq
    return bestClassEst, minError, bestStump

def adaBoostTrainDS(dataArray,classLabels,numIt=40):
    ''' 輸入：數據集，標籤向量，最大迭代次數 功能：建立adaboost加法模型 輸出：多個弱分類器的數組 '''
    weakClass = []#定義弱分類數組，保存每一個基本分類器bestStump
    m,n = np.shape(dataArray)
    D = np.mat(np.ones((m,1))/m)
    aggClassEst = np.mat(np.zeros((m,1)))
    for i in range(numIt):
        print "i:",i
        bestClassEst, minError, bestStump = buildStump(dataArray,classLabels,D)#step1:找到最佳的單層決策樹
        print "D.T:", D.T
        alpha = float(0.5*np.log((1-minError)/max(minError,1e-16)))#step2: 更新alpha
        print "alpha:",alpha
        bestStump['alpha'] = alpha
        weakClass.append(bestStump)#step3:將基本分類器添加到弱分類的數組中
        print "classEst:",bestClassEst
        expon = np.multiply(-1*alpha*np.mat(classLabels).T,bestClassEst)
        D = np.multiply(D, np.exp(expon))
        D = D/D.sum()#step4:更新權重，該式是讓D服從機率分佈
        aggClassEst += alpha*bestClassEst#steo5:更新累計類別估計值
        print "aggClassEst:",aggClassEst.T
        print np.sign(aggClassEst) != np.mat(classLabels).T
        aggError = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T,np.ones((m,1)))
        print "aggError",aggError
        aggErrorRate = aggError.sum()/m
        print "total error:",aggErrorRate
        if aggErrorRate == 0.0: break
    return weakClass

def adaTestClassify(dataToClassify,weakClass):
    dataMatrix = np.mat(dataToClassify)        
    m =np.shape(dataMatrix)[0]
    aggClassEst = np.mat(np.zeros((m,1)))
    for i in range(len(weakClass)):
        classEst = stumpClassify(dataToClassify,weakClass[i]['dimen'],weakClass[i]['thresholdValue']\
                                 ,weakClass[i]['thresholdIneq'])
        aggClassEst += weakClass[i]['alpha'] * classEst
        print aggClassEst
    return np.sign(aggClassEst)
if __name__  ==  '__main__':
    D =np.mat(np.ones((5,1))/5)
    dataMatrix ,classLabels= loadSimData()
    bestClassEst, minError, bestStump = buildStump(dataMatrix,classLabels,D)
    weakClass = adaBoostTrainDS(dataMatrix,classLabels,9)            
    testClass = adaTestClassify(np.mat([0,0]),weakClass)

調用sklearn的AdaBoost類庫

首先導入須要的類庫

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_gaussian_quantiles

調用sklearn生成符合2維正太分佈的2分類數據：

# 生成2維正態分佈，生成的數據按分位數分爲兩類，500個樣本,2個樣本特徵，協方差係數爲2 X1, y1 = make_gaussian_quantiles(cov=2.0,n_samples=500, n_features=2,n_classes=2, random_state=1) # 生成2維正態分佈，生成的數據按分位數分爲兩類，400個樣本,2個樣本特徵均值都爲3，協方差係數爲2 X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,n_samples=400, n_features=2, n_classes=2, random_state=1) #講兩組數據合成一組數據 X = np.concatenate((X1, X2)) y = np.concatenate((y1, - y2 + 1)) plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)

生成效果如圖所示
用基於決策樹的Adaboost來作分類擬合。

bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=2, min_samples_split=20, min_samples_leaf=5), algorithm="SAMME", n_estimators=200, learning_rate=0.8) bdt.fit(X, y)

顯示擬合區域而且繪製預測結果和預測邊界

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
                     np.arange(y_min, y_max, 0.02))

Z = bdt.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)
plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)
plt.show()

效果如圖所示：

AdaBoost算法的C++實現

最近課程較多，忙於學業。先立個flag，會盡快實現並分享給你們 :)

參考資料

周志華老師的《機器學習》
用python實現adaboost的博客
 sklearn的Adaboost類庫的參考博客
 借用圖片的博客

結語

初入計算機，請你們多多指教嘛，真誠歡迎一塊兒討論，共同窗習~~~持續更新中……