十分鐘演算法小故事之Adaboost演算法

編輯：AI小迷妹

引言

高二（1）班的小明同學為了能夠識別小區中的常見的兩種不同類型的小鳥(麻雀和燕子)，想設計一個分類器。首先，分類器有一些輸入的特徵，比如鳥的外形類型的特徵，顏色類型的特徵，紋理（羽毛）類型的特徵。小明用SVM分類器來分類這兩種鳥，發現效果不是很好，於是小明想到，我能不能訓練多個分類器，也就是三個臭皮匠賽過諸葛亮的策略。這就是本章要講的Adaboost (Adaptive Boosting) 演算法，它屬於集成學習的範疇。下圖顯示了集成學習的示意圖。

什麼是集成學習

集成學習通過將多個弱的學習器進行結合，常可獲得比單一學習器更好的性能。首先需要產生一組「個體學習器」，再用一個策略將它們結合起來。

1）個體學習器：可以選擇決策樹，神經網路。集成時可以所有個體學習器屬於同一類演算法（全是決策樹，或全是神經網路），也可以來自不同的演算法。

2）結合的策略：例如分類問題，可以用投票法，即少數服從多數。

假設小明訓練了三個分類器，然後拿這三個分類器在三個測試樣本上進行實驗，其中√表示分類正確，×表示分類錯誤。在這裡我們結合的策略選擇投票法，也就是集成學習的結果服從「少數服從多數」。

在圖（a）中，每個分類器都不錯，有66%的分類精度， 而且三個分類起有所不同，集成之後的結果達到了100%。

在圖（b）中，每個分類器也都有66%的分類精度，但是三個分類器沒有差別，集成之後性能沒有提高。

在圖（c）中，每一個分類器精度比較差，只有33.3%，集成學習的結果變得更糟。

從這個例子我們得知：要獲得好的集成結果，個體學習器應該要「好」並且要有差異性。也就是個體學習器本身不能效果太差（臭皮匠技術不能太差），同時要有多樣性（每個臭皮匠要有不同於其他人的一技之長）。

Adaboost演算法

Boosting演算法是一種將弱學習器提升為強學習器的演算法，這種演算法的工作機制就是先從初始訓練集訓練出一個基學習器，再根據基學習器的表現對訓練樣本進行調整，使得先前基學習器做錯的訓練樣本在後續得到更多的關注，然後在調整後的訓練樣本分布下訓練下一個基學習器，如此重複，直到分類器的個數到達一個指定的閾值N就停止，然後將這N個基學習器加權結合。最著名的代表就是Adaboost演算法。

我們以麻雀和燕子分類的例子來了解如何實現Adaboost演算法。下圖中「+」 和 「-」分別表示燕子和麻雀兩種類別，我們在實現分類的過程就是使用水平或者垂直的直線作為分類器將「+」 和 「-」區分開，從而實現分類。

圖1 初始的樣本分布

第一步，我們先訓練第一個基分類器h1，圖2。很明顯經過h1的分類，有三個樣本（「+」）分錯了。所以這三個點的權重要變大一些。然後形成一個新的樣本分布。

圖2 經過h1的分類

第二步，基於這個新的分布再訓練一個基分類器，獲得一個新的樣本分布以及第二個基分類器h2，如圖3。

圖3 經過h2的分類

我們可以看到，有三個紅色的」-」是分錯的，這是我們需要重點照顧的對象，因此要把權重加大。同時靠近分類邊界的藍色的」+」是上次分錯的，也要重點關注。

於是樣本的分布就變成了下面的樣子：

圖4 經過h1,h2分類後的樣本分布

第三步，基於這個新的樣本分布，我們需要訓練新的分類器h3。

圖5 經過h3的分類

於是最後的分類器，是三個基分類器的線性組。如下圖所示：

Adaboost演算法實現

實戰練習

【問題定義】

利用scikit-learn庫的Adaboost演算法來以對Iris數據集進行分類，Iris數據集分為3類（圖5），每類50個數據，每個數據包含4個屬性。可通過花萼長度，花萼寬度，花瓣長度，花瓣寬度4個屬性預測鳶尾花卉屬。

【解題思路】

1）首先從sklearn中導入模塊：

from sklearn.model_selection import cross_val_score

from sklearn.ensemble import AdaBoostClassifier

2）然後準備數據

from sklearn.datasets import load_iris

iris = load_iris()

iris數據集包含兩部分，一部分是iris.data是一個150*4維的矩陣，表示150個樣本，每一個樣本的特徵維度是4.另外是對應的標籤，維度是150*1.

3）因為該問題是個分類問題，所以創建一顆分類樹AdaBoostClassifier，調用Scikit-Learn中的相關函數：

clf = AdaBoostClassifier(n_estimators=100) #迭代100次，等價於創建100個基分類器

4）上面創建好的clf是一顆分類器，必須給它喂數據進行訓練，然後進行測試。我們隨機選取100個樣本做訓練，餘下的測試

import numpy as np

population=np.arange(iris.data.shape[0])

np.random.shuffle(population)

#將數據進行shuffle

N = 100

ind = population[0:N]

ind1 = population[N:]

train_data = iris.data[ind,]

test_data = iris.data[ind1,]

train_label = iris.target[ind,]

test_label = iris.target[ind1,]

clf.fit(train_data,train_label)

clf.score(test_data, test_label)

訓練好之後餘下的進行測試

clf.score(test_data, test_label)

1.0

說明Adaboost在測試集上完全分對了

總的程序如下：

-----------------------------------------------------------------

from sklearn.model_selection import cross_val_score

from sklearn.ensemble import AdaBoostClassifier

from sklearn.datasets import load_iris

import numpy as np

iris = load_iris()

clf = AdaBoostClassifier(n_estimators=100)

population =np.arange(iris.data.shape[0])

np.random.shuffle(population)#將數據進行shuffle

N = 100

ind = population[0:N]

ind1 = population[N:]

train_data = iris.data[ind,]

test_data = iris.data[ind1,]

train_label = iris.target[ind,]

test_label = iris.target[ind1,]

clf.fit(train_data,train_label)

clf.score(test_data, test_label)

------------------------------------------------------------------

想學習了解人工智慧知識的小夥伴們，請關註：

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！