徐 堅 陳優(yōu)廣

(華東師范大學(xué) 上海 200062)

0 引 言

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

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

1 AdaBoost算法概述

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

AdaBoost算法流程如下：

輸入：

1) 含有N個已知樣本的訓(xùn)練集:

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

(1)

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

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

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

(2)

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

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

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

(3)

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

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

(4)

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

(5) 更新訓(xùn)練數(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ù)訓(xùn)練得到的基分類器不用再通過上一次訓(xùn)練的結(jié)果更新計算本輪的權(quán)重，讓后續(xù)的訓(xùn)練過程能夠并行執(zhí)行，優(yōu)化了算法的時間成本，算法的建模效率得到明顯提升。

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

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

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

2.2 P-AdaBoost算法流程

輸入：

1) 含有N個已知樣本的訓(xù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，進(jìn)行下一步。

步驟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ù)遠(yuǎn)大于其他類別的樣本數(shù)。而少數(shù)類又恰好是最需要學(xué)習(xí)的概念，由于少數(shù)類數(shù)據(jù)可能和某一特殊、重要的情形相關(guān)，造成了這類數(shù)據(jù)難以被識別。

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

(1) 分類準(zhǔn)確率這種用以指導(dǎo)學(xué)習(xí)過程的，衡量全局性能的指標(biāo)可能會偏向多數(shù)類，對少數(shù)類不利。

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

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

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

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

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

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

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

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

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

(11)

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

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

(12)

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

3.3 算法流程

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

詳細(xì)的算法流程如下：

輸入：

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

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

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

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

步驟3使用當(dāng)前生成的集成分類器：

對數(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，進(jìn)行下一步；

步驟6輸出最終模型：

4 實 驗

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

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

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

4.2 實驗方法

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

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

4.3 實驗結(jié)果

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

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

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

表3 不同噪聲比例下各算法分類準(zhǔn)確率

根據(jù)每組在不同噪聲比例下的分類準(zhǔn)確率繪制如圖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算法的分類準(zhǔn)確率與P-AdaBoost和AdaBoost差距明顯，一直維持在較高的水平。

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

5 結(jié) 語

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

[1] 周志華.機器學(xué)習(xí)[M].北京:清華大學(xué)出版社,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ìn)展與展望[J].自動化學(xué)報,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算法改進(jìn)BP神經(jīng)網(wǎng)絡(luò)預(yù)測研究[J].計算機工程與科學(xué),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.