王玲娣, 徐 華

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

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

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

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

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

1 AdaBoost算法

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

算法1AdaBoost算法.

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

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

fort=1 toT

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

計(jì)算ht的加權(quán)錯(cuò)誤率

ε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è)計(jì)

本文提出一種自適應(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)練樣本的不同. 將一個(gè)大的訓(xùn)練樣本集根據(jù)相似度分成多個(gè)組, 在每組進(jìn)行分類訓(xùn)練, 這樣就在分類器訓(xùn)練前顯性地增加了差異性, 從而不用在訓(xùn)練過程中考慮如何平衡差異性和分類正確率的問題, 因?yàn)椴町愋栽谟?xùn)練樣本劃分時(shí)分類器訓(xùn)練前即給予了保證, 而分類正確率即成了在分類器訓(xùn)練過程中唯一需要考慮的因素.

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

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

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

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

AdaBoost算法訓(xùn)練出的分類器對(duì)樣本類別進(jìn)行判定時(shí)有對(duì)判定結(jié)果的置信度, 整體集成綜合考慮具體測(cè)試樣本與各分組的相似度及AdaBoost分類器的置信度, 按照加權(quán)投票策略進(jìn)行, 其中每組分類器的權(quán)值針對(duì)測(cè)試樣本自適應(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算法的第一步是對(duì)訓(xùn)練樣本進(jìn)行分組, 將相似的樣本歸到同一組中, 不相似的劃分到不同組中, 再分別進(jìn)行AdaBoost訓(xùn)練. 其中樣本分組基于k-均值算法實(shí)現(xiàn). 相似度是聚類的基礎(chǔ), 常用特征空間中的距離作為度量標(biāo)準(zhǔn)計(jì)算兩個(gè)樣本間的相似度, 距離越小越相似. 假設(shè)X為樣本空間, 每個(gè)樣本xi∈X,xi=(xi1,xi2,…,xim), 其中m表示樣本的維數(shù)(特征). 經(jīng)典的距離度量標(biāo)準(zhǔn)是m維特征空間的歐氏距離：

(1)

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

(2)

算法2k-均值算法.

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

2) repeat;

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

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

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

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

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

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

(3)

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

(4)

然后根據(jù)

(5)

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

(6)

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

(7)

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

2.4 算法描述

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

算法3AECA算法.

輸入： 訓(xùn)練集, 驗(yà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個(gè)簇, 并得到k個(gè)質(zhì)心

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

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

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

6) if accuracy>Top_Accuracy:

Best_cents=cents

Best_classifiers=classifiers

Top_Accuracy=accuracy

7) end for

輸出： Best_cents, Best_classifiers.

3 實(shí) 驗(yàn)

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

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

(8)

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

3.2 實(shí)驗(yàn)結(jié)果分析

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

3.2.1 分類正確率比較 分類正確率實(shí)驗(yàn)結(jié)果列于表2, 其中最后一列表示AECA算法在每個(gè)數(shù)據(jù)集的分類表現(xiàn)排序, 在置信水平95%的情形下, 比較4種算法在基分類器數(shù)目為50時(shí)的分類正確率. 由表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)與隨機(jī)森林算法基本相同, 在Messidor與Transfusion數(shù)據(jù)集的表現(xiàn)不是最好, 但也不是最差. 因此, AECA算法的總體表現(xiàn)優(yōu)于其他3種常用集成算法.

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

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

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

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

(9)

(10)

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

表4 4種算法的秩水平

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

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