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

徐 堅 陳優(yōu)廣

(華東師范大學 上海 200062)

0 引 言

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

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

1 AdaBoost算法概述

Adaboost的基本思想是通過不斷迭代，利用已知類別標記的訓練集訓練出一系列弱分類器，然后將這些弱分類器線性結(jié)合在一起，得到一個分類準確率更高的強分類器。基分類器的訓練算法種類很多，可以使用決策樹、樸素貝葉斯等，還有學者提出也能使用神經(jīng)網(wǎng)絡(luò)作為算法的基分類器[7]。

AdaBoost算法流程如下：

輸入：

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

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

(1)

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

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

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

(2)

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

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

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

(3)

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

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

(4)

該權(quán)重表示當前分類器在最終模型中的比重，也是最終模型中該分類器對應(yīng)的系數(shù)。

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

(5)

(6)

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

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

(7)

2 P-AdaBoost算法概述

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

2.1 權(quán)重動態(tài)分布

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

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

2.2 P-AdaBoost算法流程

輸入：

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

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

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

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

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

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

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

步驟5輸出最終模型：

2.3 P-AdaBoost算法分析

(8)

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

μ=αθ

(9)

σ2=αθ2

(10)

3 ND-PAdaBoost算法概述

3.1 數(shù)據(jù)集不平衡問題

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

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

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

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

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

3.2 數(shù)據(jù)集中噪聲樣本的檢測

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

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

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

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

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

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

(11)

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

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

(12)

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

3.3 算法流程

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

詳細的算法流程如下：

輸入：

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

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

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

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

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

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

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

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

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

步驟6輸出最終模型：

4 實 驗

4.1 數(shù)據(jù)集

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

表1 數(shù)據(jù)集

4.2 實驗方法

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

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

4.3 實驗結(jié)果

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

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

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

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

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

圖1 Titanic數(shù)據(jù)集折線圖

圖2 Diabetes數(shù)據(jù)集折線圖

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

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

5 結(jié) 語

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

[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īng)網(wǎng)絡(luò)預測研究[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.