一種基于聚類和AdaBoost的自適應(yīng)集成算法

王玲娣, 徐 華

(江南大學(xué) 化工物聯(lián)網(wǎng)工程學(xué)院, 江蘇 無錫 214122)

機器學(xué)習(xí)所關(guān)注的問題之一是利用已有數(shù)據(jù)訓(xùn)練出一個學(xué)習(xí)器, 使其對新數(shù)據(jù)盡可能給出最精確的估計. 集成學(xué)習(xí)為該問題提供了一種有效可行的解決方式, 與一般的機器學(xué)習(xí)算法目的相同, 分類仍然是集成學(xué)習(xí)的基本目標, 但集成學(xué)習(xí)將多個分類器的分類結(jié)果進行某種組合來決定最終結(jié)果, 以此取得比單個分類器更好的性能. 常用的集成學(xué)習(xí)算法有AdaBoost[1],Bagging(bootstrap aggregating)[2]和隨機森林[3]等. 其中, AdaBoost算法由于其簡單的流程及較理想的效果, 已成功應(yīng)用于人臉檢測[4-5]、車輛識別[6]、疾病診斷[7]和目標跟蹤[8-9]等實際問題中.

集成學(xué)習(xí)主要包括兩個組成部分： 1) 構(gòu)造差異性大且準確率高的基分類器； 2) 基分類器組合規(guī)則, 如簡單投票法, 包括多數(shù)投票、一致表決、最小投票等. 一般增加差異性可分為顯性和隱性兩種方式. 顯性方式是指最大化某個與差異性相關(guān)的目標函數(shù), 集成不同的基分類器[10-12]. 隱性方式是指從訓(xùn)練樣本或樣本特征入手, 通過構(gòu)造不同的訓(xùn)練子集或特征子集來訓(xùn)練不同的基分類器, 如姚旭等[13]利用粒子群算法(PSO)尋找使AdaBoost依樣本權(quán)重抽取的數(shù)據(jù)集分類錯誤率最小化的最優(yōu)特征權(quán)重分布, 根據(jù)該最優(yōu)權(quán)重分布對特征隨機抽樣生成隨機子空間, 以增大基分類器間的差異性, 并提出一種基于AdaBoost和匹配追蹤的選擇性集成算法[14]； 文獻[15]整合特征選擇和Boosting思想提出了BPSO-Adaboost-KNN集成算法. Parvin等[16]提出了一種基于分類器選擇聚類技術(shù)的集成分類框架, 先利用聚類技術(shù)將基分類器分組, 再從不同組中選擇基分類器組合, 完成選擇性集成; Xiao等[17]提出了一種基于監(jiān)督聚類的用于信用評估的分類方法, 先利用聚類方法將每個類別的樣本聚類分組, 再將不同類別、不同組的樣本組合在一起構(gòu)成不同的訓(xùn)練子集, 最后在訓(xùn)練子集上生成一組不同的基分類器.

AdaBoost使用加權(quán)多數(shù)投票規(guī)則組合基分類器, 基分類器的權(quán)重對不同的測試樣本都是固定不變的, 并未考慮到測試樣本與基分類器之間的適應(yīng)性, 且AdaBoost在訓(xùn)練基分類器的過程中, 一直聚焦在錯分樣本上, 錯分樣本的權(quán)重逐步增加, 會導(dǎo)致正確分類樣本的權(quán)重過低, 基分類器傾向于在樣本空間的部分區(qū)域有較好的效果, 其他區(qū)域的樣本被忽略. 這也是AdaBoost對噪音敏感的原因. 所以, 需要區(qū)別對待不同的測試樣本, 充分挖掘基分類器的分類能力, 使基分類器的權(quán)重可針對不同的測試樣本自適應(yīng)調(diào)整.

針對上述問題, 受文獻[16-17]的啟發(fā), 并結(jié)合集成學(xué)習(xí)對基分類器的要求, 本文提出一種基于聚類和AdaBoost的自適應(yīng)集成方法. 一方面利用聚類分組確保不同組的基分類器之間的差異性, 每組分別進行AdaBoost訓(xùn)練, 以保證較高的局部分類正確率； 另一方面結(jié)合測試樣本到不同分組中心的距離及AdaBoost對此樣本判別的置信度動態(tài)調(diào)整基分類器的權(quán)重.

1 AdaBoost算法

AdaBoost算法是一個自適應(yīng)地改變訓(xùn)練樣本分布的迭代過程, 使基分類器聚焦在難分的樣本上. 其原理是： 訓(xùn)練集中的每個樣本均被賦予一個權(quán)值, 構(gòu)成向量D, 并初始化為相等值, 然后根據(jù)某種基分類器訓(xùn)練算法得到第一個基分類器, 再根據(jù)該分類器的錯誤率調(diào)整訓(xùn)練樣本權(quán)重, 降低被正確分類的樣本權(quán)重, 提高被錯誤分類的樣本權(quán)重. 基于改變的樣本分布, 繼續(xù)訓(xùn)練基分類器. 如此往復(fù), 便可得到一組基分類器. AdaBoost算法如下.

算法1AdaBoost算法.

輸入： 訓(xùn)練集{(x1,y1),(x2,y2),…,(xm,ym)}, 其中類標簽yi∈{-1,1}； 迭代次數(shù)T.

初始化D1(i)=1/m, 第一次迭代時每個樣本的權(quán)重均為1/m.

fort=1 toT

在Dt下訓(xùn)練得到基分類器ht;

計算ht的加權(quán)錯誤率

εt=∑Dt(i)[ht(xi)≠yi],

其中[ht(xi)≠yi]是指示函數(shù), 若ht(xi)≠yi成立, 則返回1, 否則返回0;

更新樣本權(quán)值:

其中Zt是歸一化因子;

end for

2 基于聚類和AdaBoost的自適應(yīng)集成方法設(shè)計

本文提出一種自適應(yīng)集成方法(adaptive ensemble method based on clustering and AdaBoost, AECA).

2.1 算法思想

差異性是集成學(xué)習(xí)的基礎(chǔ), 如果是同一算法在不同設(shè)置下的集成, 則差異性一般源于基分類器的訓(xùn)練樣本, 這樣同一算法在不同訓(xùn)練樣本下即可訓(xùn)練出不同的基分類器. 經(jīng)典的集成方法Bagging和AdaBoost都是同一算法在不同設(shè)置下的集成, 其差異性源于訓(xùn)練樣本的不同. 將一個大的訓(xùn)練樣本集根據(jù)相似度分成多個組, 在每組進行分類訓(xùn)練, 這樣就在分類器訓(xùn)練前顯性地增加了差異性, 從而不用在訓(xùn)練過程中考慮如何平衡差異性和分類正確率的問題, 因為差異性在訓(xùn)練樣本劃分時分類器訓(xùn)練前即給予了保證, 而分類正確率即成了在分類器訓(xùn)練過程中唯一需要考慮的因素.

圖1為一個二維二分類問題, 其中“●”和“■”表示兩類數(shù)據(jù). 由圖1可見， 對于子集S1, 分類函數(shù)y1可成功地將“●”和“■”所表示的兩類樣本正確分類； 在子集S2中, 分類函數(shù)y2也能對兩類樣本點正確分類. 但一個單分類器則很難以高的正確率將這兩類樣本區(qū)分. 至于常用的集成算法, 如Bagging, 是通過隨機重采樣構(gòu)造一組基分類器, 隨機選擇的樣本有可能均勻地來自子集S1和S2, 這樣基分類器的正確率可能會很低, 從而導(dǎo)致最終集成性能的下降. 此外, 基分類器間的差異性也不能保證. 而先對訓(xùn)練樣本聚類, 分成若干個子集, 再分組分類, 則可有效解決上述問題. 通過聚類將訓(xùn)練樣本分成子集S1和S2, 這些子集分別表示了樣本的不同空間特征, 再根據(jù)某種分類算法各自訓(xùn)練分類器, 即可得到局部正確率較高的兩個分類器.

對于測試樣本, 與該測試樣本較相似的訓(xùn)練樣本分組上訓(xùn)練出的分類器對其正確分類的可能性更大. 因此本文在每個分組上根據(jù)AdaBoost算法訓(xùn)練出一個強分類器, 然后組成一個更強大的分類器. AECA算法過程如圖2所示. 由圖2可見, AECA算法有兩個重要組成部分：

1) 先對訓(xùn)練樣本進行聚類分組, 再在每組樣本上根據(jù)AdaBoost算法訓(xùn)練得到分類器{H1,H2,…,Hk}；

2) 將訓(xùn)練得到的分類器進行整體集成.

AdaBoost算法訓(xùn)練出的分類器對樣本類別進行判定時有對判定結(jié)果的置信度, 整體集成綜合考慮具體測試樣本與各分組的相似度及AdaBoost分類器的置信度, 按照加權(quán)投票策略進行, 其中每組分類器的權(quán)值針對測試樣本自適應(yīng)調(diào)節(jié).

圖1 樣本聚類示例Fig.1 Examples of sample clustering

圖2 AECA算法示意圖Fig.2 Schematic diagram of AECA algorithm

2.2 訓(xùn)練樣本分組訓(xùn)練

AECA算法的第一步是對訓(xùn)練樣本進行分組, 將相似的樣本歸到同一組中, 不相似的劃分到不同組中, 再分別進行AdaBoost訓(xùn)練. 其中樣本分組基于k-均值算法實現(xiàn). 相似度是聚類的基礎(chǔ), 常用特征空間中的距離作為度量標準計算兩個樣本間的相似度, 距離越小越相似. 假設(shè)X為樣本空間, 每個樣本xi∈X,xi=(xi1,xi2,…,xim), 其中m表示樣本的維數(shù)(特征). 經(jīng)典的距離度量標準是m維特征空間的歐氏距離：

(1)

k-均值算法是發(fā)現(xiàn)給定數(shù)據(jù)集k個簇的算法, 簇個數(shù)由用戶給定, 每一簇均通過質(zhì)心, 即簇中所有點的中心描述. 假設(shè)cls(i)表示第i個簇, 由n個樣本組成, 則該簇的質(zhì)心centroid(i), 即簇中所有數(shù)據(jù)的均值:

(2)

算法2k-均值算法.

1) 隨機選擇k個樣本作為初始質(zhì)心;

2) repeat;

3) 根據(jù)式(1)計算樣本與每個質(zhì)心的距離, 將樣本指派到距離最近的質(zhì)心表示的簇中, 形成k個簇;

4) 根據(jù)式(2)重新計算每個簇的質(zhì)心;

5) until質(zhì)心不發(fā)生變化.

初始質(zhì)心的選擇是k-均值算法的關(guān)鍵步驟, 常見的方法是隨機地選取初始質(zhì)心, 但當質(zhì)心隨機初始化,k-均值的不同運行將產(chǎn)生不同的結(jié)果. 故需要重復(fù)運行多次, 在有限的迭代次數(shù)中, 找到一個相對較優(yōu)的目標函數(shù)值. 為了評價最后聚類質(zhì)量的好壞, 通常使用誤差的平方和作為度量聚類質(zhì)量的目標函數(shù), 但本文的目的不是聚類結(jié)果的好壞, 而是為更好地分類, 故本文使用分類正確率作為目標函數(shù). 原始數(shù)據(jù)集中樣本特征值可能是不同取值范圍的, 為了避免樣本某一個特征值遠大于其他特征值, 影響計算結(jié)果, 本文先將訓(xùn)練樣本集進行數(shù)值歸一化, 將任意取值范圍的特征值根據(jù)

轉(zhuǎn)化到0～1區(qū)間內(nèi), 其中: oldValue表示原特征值; max和min分別表示該特征的最大和最小值.

2.3 分類器自適應(yīng)權(quán)值計算

(3)

為計算各分類器對測試樣本自適應(yīng)的權(quán)重w, 首先計算測試樣本到各簇質(zhì)心的距離, 距離越近權(quán)值越大. 假設(shè)測試樣本集為X={x1,x2,…,xm}, 根據(jù)歐氏距離計算測試樣本xi與簇質(zhì)心Sk之間的距離dik, 構(gòu)成距離矩陣:

(4)

然后根據(jù)

(5)

將距離矩陣轉(zhuǎn)換成各個簇分類器對測試樣本的權(quán)值矩陣:

(6)

得到各簇分類器對測試樣本的權(quán)值矩陣后, 即可進行最后的集成, 因為各簇的分類器是根據(jù)AdaBoost算法訓(xùn)練得到的, AdaBoost算法產(chǎn)生的強分類器除了對樣本有一個預(yù)測類別, 還有置信度margin值. 對于二分類問題, AECA算法進行強分類器最后的集成前, 要保留置信度, 待乘以具體的針對測試樣本的自適應(yīng)權(quán)值后相加再取符號. 對測試樣本的預(yù)測根據(jù)

(7)

計算得到. 這樣各簇的強分類器中基分類器的權(quán)值固定, 但針對不同樣本置信度是不同的, 且在最后的集成中, 強分類器對測試樣本的權(quán)值是自適應(yīng)的.

2.4 算法描述

首先, 將總樣本集分成訓(xùn)練集、驗證集和測試集三部分, 且三部分互斥.k-均值算法的目標函數(shù)是驗證集的分類準確率, 在多次迭代中取驗證正確率最高的聚類結(jié)果. 一次迭代過程如圖2所示, 先通過k-均值算法將訓(xùn)練樣本集分成多個簇, 每個簇以簇質(zhì)心為代表; 然后在每個簇上進行AdaBoost訓(xùn)練分別得到一個強分類器, 當數(shù)據(jù)集較大時, 該步驟可以并行處理; 最終按照加權(quán)投票策略將多個強分類器組合, 其中每個強分類器的權(quán)值根據(jù)測試樣本到每個簇質(zhì)心的距離計算得出, 原則是距離越近權(quán)值越大, 權(quán)值之和為1. 關(guān)于每組樣本上AdaBoost的基分類器數(shù)目的取值, 在給定總的基分類器數(shù)目的情況下, 每組基分類器的數(shù)目取值按照組與組之間的樣本數(shù)之比分配, 而簇數(shù)k則取實驗數(shù)據(jù)集的類別數(shù).

算法3AECA算法.

輸入： 訓(xùn)練集, 驗證集, 基分類器數(shù)目N, 循環(huán)次數(shù)T.

1) 初始化Top_Accuracy=0, Best_cents=Null, Best_Classifiers=Null

2) fort=1 toT:

3) 根據(jù)k-均值算法將訓(xùn)練集分成k個簇, 并得到k個質(zhì)心

4) 根據(jù)AdaBoost算法分別在k個簇上進行訓(xùn)練, 得到k個強分類器classifiers

5) 在驗證集上, 根據(jù)式(6)計算k個強分類器的自適應(yīng)權(quán)值

根據(jù)式(8)計算驗證集的分類正確率accuracy

6) if accuracy>Top_Accuracy:

Best_cents=cents

Best_classifiers=classifiers

Top_Accuracy=accuracy

7) end for

輸出： Best_cents, Best_classifiers.

3 實 驗

3.1 實驗環(huán)境及數(shù)據(jù)集

AECA算法基于Python 2.7語言實現(xiàn), Bagging、隨機森林和AdaBoost算法均源自Python機器學(xué)習(xí)工具包sicikt-learn(http://scikit-learn.org/stable/index.html). 實驗共用UCI(http://archive.ics.uci.edu/ml/datasets.html)中的10個數(shù)據(jù)集, 各數(shù)據(jù)集信息列于表1. 由表1可見, 數(shù)據(jù)集Horse,ILPD,Pima中有部分數(shù)據(jù)缺失, Horse的缺失高達30%. 一般可將缺失值用0或平均值替代, 本文實驗中使用屬性平均值替代缺失值. 在計算分類正確率時, 為保證計算的準確性, 使用十折交叉驗證法. 其中AECA算法需要驗證集, 從9份訓(xùn)練集中隨機抽取10%的數(shù)據(jù)作為驗證集, 余下的數(shù)據(jù)則作為訓(xùn)練集. 另外一份作為測試數(shù)據(jù)集, 這樣訓(xùn)練集、驗證集和測試集并無交叉, 循環(huán)次數(shù)為20. 利用雙邊估計t檢驗法計算95%的置信水平下的分類正確率均值的置信區(qū)間, 計算公式如下：

(8)

表1 實驗數(shù)據(jù)集信息

3.2 實驗結(jié)果分析

本文將從兩方面驗證AECA算法的有效性: 1) 比較Bagging、隨機森林、AdaBoost算法及AECA算法在相同集成規(guī)模下的分類正確率； 2) 從統(tǒng)計的角度, 根據(jù)秩和檢驗法比較AECA算法與其他3種集成算法差別是否統(tǒng)計顯著.

3.2.1 分類正確率比較 分類正確率實驗結(jié)果列于表2, 其中最后一列表示AECA算法在每個數(shù)據(jù)集的分類表現(xiàn)排序, 在置信水平95%的情形下, 比較4種算法在基分類器數(shù)目為50時的分類正確率. 由表2可見, AECA算法在Australian,German,Heart,Horse,ILPD,Pima和Sonar等數(shù)據(jù)集上的分類正確率均高于其他3種集成算法, 分別比排在第二位的算法高1.74%,0.1%,4.45%,4.97%,2.57%,4.74%. AECA算法的分類正確率在Breast數(shù)據(jù)集上的表現(xiàn)與隨機森林算法基本相同, 在Messidor與Transfusion數(shù)據(jù)集的表現(xiàn)不是最好, 但也不是最差. 因此, AECA算法的總體表現(xiàn)優(yōu)于其他3種常用集成算法.

表2 AECA算法與其他3種集成算法的分類正確率(%)比較

為了更直觀地觀察4種集成算法的分類性能, 參考文獻[18]中的統(tǒng)計量進行分析比較, 統(tǒng)計結(jié)果列于表3. 表3為每種算法在所有數(shù)據(jù)集上的正確率比較, 若用row表示第一種算法的分類正確率, col表示第二種算法的分類正確率, row/col表示這兩種算法的正確率比值, 若row/col>1, 則表示第一種算法的分類性能優(yōu)于第二種算法, 否則相反. 其中“贏/平/敗”值表示win/tie/loss統(tǒng)計量, 這3個值分別表示row>col, row=col, row

表3 4種算法的分類統(tǒng)計結(jié)果

3.2.2 顯著性差異檢驗 利用秩和檢驗法對上述結(jié)果進行分析, 以得到更具統(tǒng)計意義的實驗結(jié)論. 秩水平的計算公式為

(9)

(10)

其中:k表示比較的算法數(shù);J表示每種算法的實驗次數(shù);α表示置信水平;qα可查“The Studentized Range Statistic”表得到. 本文實驗比較4種算法在置信水平為95%(即α=0.05)情形下的分類效果, 故k=4,J=10,q0.05=1.860, 代入式(10)可得臨界值為1.073 87. 4種算法的統(tǒng)計結(jié)果列于表4.

表4 4種算法的秩水平

由表4可見, Bagging、隨機森林、AdaBoost和AECA算法的秩水平之差分別為1.7,1.1,1.7, 均大于差異臨界值1.073 87. 故本文提出的AECA算法與常用集成算法Bagging、隨機森林、AdaBoost的差異是統(tǒng)計顯著的, 且AECA算法可獲得更高的分類正確率, 因此, AECA算法是有效的.

綜上所述, 本文提出了一種基于聚類和AdaBoost的自適應(yīng)集成算法, 該算法首先利用聚類將訓(xùn)練樣本分組, 充分利用訓(xùn)練樣本信息, 使得組內(nèi)樣本相似度高, 組間差異性大, 從而既保證了不同組上的分類器差異, 又可得到一個較高的局部分類正確率; 最后集成借助AdaBoost的margin值以及測試樣本到各組的距離, 使用加權(quán)投票策略, 達到各組分類器權(quán)值對測試樣本自適應(yīng)調(diào)節(jié)的目的, 充分挖掘了分類器的分類能力, 從而得到較高的整體集成分類性能. 實驗結(jié)果驗證了該算法的有效性.