基于噪聲自檢測的并行AdaBoost算法

徐 堅 陳優廣

(華東師范大學 上海 200062)

0 引 言

數據分類問題作為數據挖掘領域中一個非常重要的研究方向，主要由兩個階段構成：學習和分類。學習階段使用已知類別標記的數據集作為學習算法的輸入，構筑分類器，而分類階段則使用上一階段得到的分類器預測未知標記數據的類別[1]。用于構筑分類器的方法有很多，如SVM、決策樹和樸素貝葉斯模型等。在這些算法不斷成熟完備的過程中，出現了諸如裝袋(Bagging)、提升(Boosting)和隨機森林等提高分類準確率的技術，這些被稱為集成學習技術[2]。集成學習的原理為通過一定規則將一系列弱分類器集成提升為強分類器，再使用強分類器預測未知樣本的類別標記。集成算法中，最具代表性的就是AdaBoost算法，該算法基于PAC框架提出,是集成算法中應用最為廣泛的算法[3]。AdaBoost算法在諸如人臉識別，文本分類等諸多領域表現出眾，算法通過反復迭代，可以將弱分類器的集合提升為強分類器,并且使訓練誤差以指數速度下降，訓練集上的錯誤率趨近0[4]。但是AdaBoost算法同時也有一些缺點，Adaboost的每次迭代都依賴上一次迭代的結果，這就造成了算法需要嚴格按照順序進行，隨著迭代次數的升高，算法的時間成本也會相應的增大?；谶@個缺點，Stefano Merler在2006年時提出了P-AdaBoost算法。利用AdaBoost在經過一定迭代次數的訓練之后，并行地求出剩余弱分類器對應權重的訓練誤差，并證明了在經過足夠次數的順序迭代之后，并行AdaBoost的分類準確率跟傳統AdaBoost相比基本相同甚至更高。然而他們沒有考慮到數據集中存在的噪聲會對結果造成負面的影響。AdaBoost本身是一個噪聲敏感的算法，這是由于該算法在每次迭代時，都會將上次訓練中分錯的樣本的權重加大，讓本次訓練的弱分類器更加關注這個被分錯的樣本。如果該錯分樣本是一個噪聲，那么這個本來是噪聲的樣本的權重會在后續迭代過程中不斷加大，導致后續弱分類器的分類準確率下降，最終導致整個模型的準確率隨之下降[5]。

同時，在P-AdaBoost算法中，噪聲比例的上升會導致算法構筑分類模型需要順序迭代的次數變多，時間成本變高，得到的最終模型的分類準確度也會降低[6]。本文為了提高并行AdaBoost算法的分類準確率和健壯性，選擇基于P-AdaBoost算法進行改進，在核心算法流程上保留了其構建模型時間較短的優勢。同時通過修改權重分布的初始值，并利用噪聲自檢測方法減少數據集中的噪聲對訓練結果的影響，提出了一種名為ND-PAdaBoost (nosie-detection PAdaBoost)的算法，進一步提升算法訓練結果的準確度。

1 AdaBoost算法概述

Adaboost的基本思想是通過不斷迭代，利用已知類別標記的訓練集訓練出一系列弱分類器，然后將這些弱分類器線性結合在一起，得到一個分類準確率更高的強分類器?；诸惼鞯挠柧毸惴ǚN類很多，可以使用決策樹、樸素貝葉斯等，還有學者提出也能使用神經網絡作為算法的基分類器[7]。

AdaBoost算法流程如下：

輸入：

1) 含有N個已知樣本的訓練集:

S={(x1,y1),(x2,y2),…,(xN,yN)}

(1)

2) 任意作為基分類器的分類算法。

輸出：集成的最終模型G(x)。

步驟1初始化訓練集每個樣本的訓練權重，均勻分布，每個樣本賦值相同的權重。表示為：

(2)

步驟2以T表示算法迭代的輪數，t表示是第t次迭代，Dt表示第t次迭代之后的樣本權重分布，對于每一輪迭代有如下操作：

(1) 使用設置好權重Dt的訓練集和選擇的分類器算法進行訓練，得到一個基分類器ht(x)∈{-1,+1}。

(2) 計算上一步中得到的分類器在訓練集上分類的誤差率，記為et：

(3)

其中：I(x)為指示函數，在x為真時取值為1，反之則為0。

(4) 利用得到的該分類器的誤差率，計算該分類器對應的權重為：

(4)

該權重表示當前分類器在最終模型中的比重，也是最終模型中該分類器對應的系數。

(5) 更新訓練數據集的樣本權重，Dt+1=(wt+1,1,wt+1,2,…,wt+1,i,…,wt+1,N)，有：

(5)

(6)

其中：Zt作為歸一化因子，用以確保每一輪的樣本權重和為1。

步驟3將經過迭代后得到的一系列基分類器及其相應權重線性組合得到最終分類器，表示為：

(7)

2 P-AdaBoost算法概述

P-AdaBoost算法利用AdaBoost中權重分布的特性，通過一定次數的順序迭代，用一種概率分布擬合樣本權重的分布函數，使得后續訓練得到的基分類器不用再通過上一次訓練的結果更新計算本輪的權重，讓后續的訓練過程能夠并行執行，優化了算法的時間成本，算法的建模效率得到明顯提升。

2.1 權重動態分布

一權重的動態分布包含著許多關鍵的信息，這些信息在AdaBoost算法構建模型的時候起到了至關重要的作用[8]。AdaBoost訓練基分類器時可以將樣本簡單地分為2類：易分類樣本和難分類的樣本。易分類樣本在訓練分類器的時候不容易被分錯，根據AdaBoost算法原理，這些樣本的權重會逐輪次降低，對新分類器訓練起到的影響會越來越小。而難分類樣本的權重并不會向一個固定值收斂，隨著迭代次數的增加可能會發生隨機波動。

一些研究人員的工作證明了難分類樣本的權重分布遵從以下兩個事實:(1) 對于任意一個難分類點，在基分類器數趨于無窮的情況下，該點的權重分布收斂于一個可確定的穩定分布；(2) 這一分布能夠用參數選擇適當的伽馬分布來表示[9]，這使得算法能夠并行計算出每輪迭代的樣本權重。

2.2 P-AdaBoost算法流程

輸入：

1) 含有N個已知樣本的訓練集S={(x1,y1),(x2,y2),…,(xN,yN)}；

2) 任意作為基分類器的分類算法。

輸出：集成的最終模型G(x)。

步驟2順序迭代S輪的AdaBoost算法，保存每一輪的到的權重結果wi(s),s=1,2,…,S。

步驟4對S=S+1,S+2,…,T做如下操作(該循環能夠并行執行)。

(3) 計算該模型對應的誤差率es。

如果es<0.5，進行下一步。

步驟5輸出最終模型：

2.3 P-AdaBoost算法分析

(8)

式中：α和θ的值是通過均值μ和方差σ2求解得到的，有如下關系：

μ=αθ

(9)

σ2=αθ2

(10)

3 ND-PAdaBoost算法概述

3.1 數據集不平衡問題

數據集中的數據分布不平衡問題在分類問題中經常出現，其主要表現為某一類的樣本數遠大于其他類別的樣本數。而少數類又恰好是最需要學習的概念，由于少數類數據可能和某一特殊、重要的情形相關，造成了這類數據難以被識別。

諸如AdaBoost、P-AdaBoost等標準的學習算法考慮的是一個平衡數據集，當這些算法用到不平衡數據集時，可能會生成一個局部優化的分類模型，導致經常錯分少數類樣本[11]。因此AdaBoost和P-AdaBoost在平衡數據框架下分類準確率較高，然而在處理不平衡數據集時，分類準確率可能會下降。造成這種現象的主要原因如下：

(1) 分類準確率這種用以指導學習過程的，衡量全局性能的指標可能會偏向多數類，對少數類不利。

(2) 預測正例樣本的分類規則可能非常的特殊，其覆蓋率很低，訓練過程中適應那些少數類的規則可能被丟棄。

(3) 規模非常小的少數類可能會被錯誤的當做噪聲數據，同時真正的噪聲會降低分類器對少數類的識別性能。

3.2 數據集中噪聲樣本的檢測

真實世界中的數據集包含著各種各樣的噪聲。由于AdaBoost算法框架的特性，這些包含在數據集中的噪聲會對算法生成的最終模型造成負面影響，導致過擬合的出現。造成這種結果的原因是AdaBoost算法在每次迭代之后會將之前分錯的樣本的權重提高，下一次迭代訓練的分類器會著重針對這類權重高的樣本學習，以此來最小化損失函數。然而由于大部分的噪聲樣本都不符合分類器的學習規則，導致噪聲樣本是很難被分類正確的。傳統的AdaBoost沒有對這種噪聲樣本進行處理，導致了這些樣本隨著迭代輪次的增長權重越來越大，后續訓練的分類器偏向于這些權重大的噪聲樣本進行訓練，使整個模型容易過擬合。而那些真正需要被正確分類的樣本沒有得到充分的學習，分類器的分類準確度下降，最終造成集成模型的分類準確度下降[12]。

為了找出樣本集中包含的噪聲樣本，本文考慮了這樣的一種思路，因為每一個樣本都是樣本空間中的一個點。對于一個樣本點(xi,yi)，已知一個分類模型ht(x)，如果該點在分類模型上取值yi與它鄰近的點都不同，那么就有理由相信該點其實是一個噪聲點。這是因為在分類的過程中，相同分類的點針對于一個已經訓練出來的分類模型ht(x)的取值總是相近的。這標志了它們屬于同一種分類并且這些點往往都集中分布在近鄰的位置。如果這時有一個鄰近點(其歐氏距離在一定范圍內)的取值與其相鄰的點在ht(x)上的取值都不同，這就說明了這個點即不能劃歸到另外一個分類。在歐氏距離上該點跟這些已分類點鄰近，又不能將該點劃為本分類，因為分類器的取值不同，所以該點就是一個噪聲點?；谶@一思想，本文提出了一種基于k鄰近算法的噪聲檢測算法，并采用模擬隨機噪聲的方式進行驗證，由于是隨機噪聲，所以無需在算法中針對噪聲的分布做處理，算法流程如下：

輸入：樣本集S={(x1,y1),(x2,y2),…,(xN,yN)}，在S上訓練得到的分類器ht(x)，k鄰近算法的系數k。

輸出：噪聲樣本集NS和非噪聲樣本集NNS。

步驟1對于每一個樣本(xi,yi)循環進行如下操作：

計算(xi,yi)點可能為一個噪聲點的概率為：

(11)

其中：I(x)為指示函數，在x為真時取值為1，反之則為0。

步驟2計算此概率在整個樣本集上的平均為：

(12)

步驟3對于S上的每一個樣本(xi,yi)做如下操作：

3.3 算法流程

考慮到迭代部分和并行部分對噪聲處理的需求不同，本文在順序迭代部分只將噪聲的權重置為0，在進入并行流程之前用當前的分類器對數據集進行一次噪聲監測，只保留非噪聲樣本為新的訓練數據集。

詳細的算法流程如下：

輸入：

1) 含有N個已知樣本的訓練集S={(x1,y1),(x2,y2),…,(xN,yN)}，其中xi為樣本矢量，yi∈{-1,+1}；

2) 任意作為基分類器的分類算法。

輸出：集成的最終模型G(x)。

步驟2順序迭代S輪的AdaBoost算法，在得到本輪訓練生成的分類器ht(x)時，使用分類器對當前數據集運行噪聲檢測算法，將標記為噪聲樣本的權重設置為0，非噪聲樣本的權重按照傳統算法進行更新。保存每一輪的到的權重結果wi(s)，s=1,2,…,S；

步驟3使用當前生成的集成分類器：

對數據集運行噪聲檢測算法,得到NS和NNS，使用NNS作為新的數據集S′；

步驟5對S=S+1,S+2,…,T做如下操作(該循環能夠并行執行)：

(3) 計算該模型對應的誤差率es。

如果es<0.5，進行下一步；

步驟6輸出最終模型：

4 實 驗

4.1 數據集

本文采用UCI(加州大學歐文分校)提供的機器學習公共數據集(見表1)，用以驗證本文的算法相比于P-adaBoost、傳統的AdaBoost和Bagging算法在相同數據集下分類結果的準確率更高。

表1 數據集

4.2 實驗方法

本文實驗基于Weka平臺，使用Java語言實現了ND-PAdaBoost算法。由于受實驗條件所限,只模擬了ND-PAdaBoost算法并行運行的情況，由于模擬并不改變算法更新權重值的邏輯，所以其結果的分類準確率與算法真正并行運行的分類準確率一致，不影響對ND-PAdaBoost算法的評估和比較。實驗對比了本文提出的ND-PAdaBoost算法和P-AdaBoost、傳統AdaBoost、Bagging這四種算法在無噪聲情況下的分類準確率。由于這四種算法流程上存在并行訓練和連續迭代訓練的區別，為了能充分驗證本文提出算法ND-PAdaBoost的效果，該實驗規定除Bagging算法外，其他含有連續迭代過程的算法的迭代輪次為100次。保證前三種算法的時間成本基本相同，并且本文通過反復實驗證明了100次的順序迭代足夠使ND-PAdaBoost和P-AdaBoost算法估計出可信的樣本權重分布。同時規定ND-PAdaBoost、P-AdaBoost和Baggaging這三種并行算法訓練的總基分類器數目為500個，k鄰近算法的系數設置為5%。實驗記錄各算法在無噪聲下的分類準確率。

此外，為了說明本文改進權重初始值對算法分類準確率的提高產生了正面影響。本文在上述所有數據集上分別使用不同的初始值下的ND-PAdaBoost算法訓練分類模型，NDP-AdaBoost的其余條件保持不變。通過比較最終分類模型的準確率來證明修改后的權重初始值有助于提高最終模型的分類準確率。

4.3 實驗結果

實驗結果如表2所示，其中加粗部分是每組數據集中正確率最高的，下劃線部分是每組數據集中分類正確率最低的。通過該實驗結果表明，ND-PAdaBoost算法即使在無噪聲的數據集上的分類準確率相比于其他三種算法也有所提升。

表2 無噪聲下各算法的分類準確率(100次迭代)

取Titanic、Diabetes數據集為例，比較前三種算法在不同噪聲比例下的分類準確率。結果如表3所示。

表3 不同噪聲比例下各算法分類準確率

根據每組在不同噪聲比例下的分類準確率繪制如圖1和圖2所示。

圖1 Titanic數據集折線圖

圖2 Diabetes數據集折線圖

由圖1、圖2可以看出，ND-PAdaBoost算法相比于P-AdaBoost和傳統的AdaBoost對噪聲有更好的兼容性，能夠在含有噪聲的數據集上取得更穩定的表現。隨著噪聲比例的增加，ND-PAdaBoost算法的分類準確率與P-AdaBoost和AdaBoost差距明顯，一直維持在較高的水平。

表4 不同權重初始值下ND-PAdaBoost算法分類準確率

5 結 語

本文從AdaBoost算法的框架出發，基于AdaBoost的并行改進算法P-AdaBoost,針對P-AdaBoost對噪聲敏感，含有噪聲的數據集會嚴重影響P-AdaBoost分類準確度的問題，提出了一個噪聲自檢測方法,并修改了原始樣本權重分布的初始值。本文使用了UCI數據集對提出的改進方法進行了多番驗證。實驗結果表明，本文提出的算法在輸入數據集含噪聲的場景下具有更好的分類準確率。然而，本文提出的模型只準對二分類問題有效，如果需要推廣到多分類問題上，還需要對模型進行修改。本算法中所需順序迭代次數的取值是通過反復實驗測定的，關于這個取值的最優數值還需要進一步的研究和探討。

[1] 周志華.機器學習[M].北京:清華大學出版社,2016:121-145.

[2] Breiman L.Bagging predictors[J].Machine Learning,1996,24(2):123-140.

[3] Breiman L.Random Forests[J].Machine Learning,1996,24(2):123-140.

[4] Nie Q,Jin L,Fei S.Probability estimation for multi-class classification using AdaBoost[J].Pattern Recognition,2014,47(12):3931-3940.

[5] 曹瑩,苗啟廣,劉家辰,等.AdaBoost算法研究進展與展望[J].自動化學報,2013,39(6):745-758.

[6] Merler S,Caprile B,Furlanello C.Parallelizing AdaBoost by weights dynamics[J].Computational Statistics & Data Analysis,2007,51(5):2487-2498.

[7] 李翔,朱全銀.Adaboost算法改進BP神經網絡預測研究[J].計算機工程與科學,2013,35(8):96-102.

[8] Caprile B,Furlanello C,Merler S.Highlighting Hard Patterns via AdaBoost Weights Evolution[J].Lecture Notes in Computer Science,2002,2364:72-80.

[9] Collins M.Logistic regression,Adaboost and bregman distances[J].Machine Learning,2002,48(1):253-285.

[10] Htike K K.Efficient determination of the number of weak learners in AdaBoost[J].Journal of Experimental & Theoretical Artificial Intelligence,2016,29(5):1-16.

[11] Lee W,Jun C,Lee J.Instance categorization by support vector machines to adjust weights in AdaBoost for imbalanced data classification[J].Information Sciences,2017,381:92-103.

[12] Barrow D K,Crone S F.A comparison of AdaBoost algorithms for time series forecast combination[J].International Journal of Forecasting,2016,32(4):1103-1119.