基于實例的強分類器快速集成方法

許業旺，王永利，趙忠文

1.南京理工大學 計算機科學與工程學院，南京 210094； 2.裝備學院 復雜電子系統仿真重點實驗室，北京 101416)(*通信作者電子郵箱381181495@qq.com)

基于實例的強分類器快速集成方法

許業旺1*，王永利1，趙忠文2

1.南京理工大學 計算機科學與工程學院，南京 210094； 2.裝備學院 復雜電子系統仿真重點實驗室，北京 101416)(*通信作者電子郵箱381181495@qq.com)

針對集成分類器由于基分類器過弱，需要犧牲大量訓練時間才能取得高精度的問題，提出一種基于實例的強分類器快速集成方法——FSE。首先通過基分類器評價方法剔除不合格分類器，再對分類器進行精確度和差異性排序，從而得到一組精度最高、差異性最大的分類器；然后通過FSE集成算法打破已有的樣本分布, 重新采樣使分類器更多地關注難學習的樣本，并以此決定各分類器的權重并集成。實驗通過與集成分類器Boosting在UCI數據庫和真實數據集上進行比對，Boosting構造的集成分類器的識別精度最高分別能達到90.2%和90.4%，而使用FSE方法的集成分類器精度分別能達到95.6%和93.9%；而且兩者在達到相同精度時，使用FSE方法的集成分類器分別縮短了75%和80%的訓練時間。實驗結果表明，FSE集成模型能有效提高識別精度、縮短訓練時間。

強分類器集成模型；基分類器評價方法；集成算法；樣本分布；集成學習

0 引言

集成學習(Ensemble Learning)是使用一系列學習器進行學習，并使用某種規則把各個學習結果進行整合從而獲得比單個學習器更好的學習效果的一種機器學習方法。它可以有效地提高學習系統的泛化能力，因此集成學習作為機器學習界的研究熱點，目前已經廣泛應用于文本與語音識別[1]、協同過濾推薦[2]、輔助醫療診斷[3]、遙感信息處理[4]、系統故障診斷[5]等多個領域。

分類器集成是集成學習一個重要的研究方向，目前主要集成算法主要包括Boosting和Bagging，而不考慮數據集的影響，Boosting方法的集成分類器效果明顯優于Bagging[6]。在大部分相關文獻中，集成過程往往選擇神經網絡[7]、樸素貝葉斯[8-9]、決策樹[10-11]等算法訓練出成百上千個弱分類器(識別率稍高于0.5)再進行集成。這一做法存在以下不足：一方面，使用數量巨大的分類器將導致更大的計算和存儲開銷；另一方面，此類基分類器差異本身就很小，而當多次訓練使得基分類器數目增加之后，分類器之間的差異會更小。周志華等已經驗證，集成學習的效果取決于基分類器之間的差異性[12-15]。本文從參與集成的基分類器的分類準確性和差異性兩方面考慮：準確性方面，本文選擇識別率較高的強分類器作為基分類器，不僅能保障識別精度，還可以大幅提高集成效率；差異性方面，本文將差異性評價方法應用到分類器集成中，使集成系統的識別精度得到進一步提高。

在選定好基分類器之后，分類器之間的輸出集成方法就成為實現集成學習系統的關鍵。目前常見的分類器集成方法有投票法[16]、線性組合法、證據理論法、模糊積分法等，它們在一定條件下均可以提高集成學習系統的性能。然而，這些方法都只是根據分類器的統計性能賦予分類器以相應的權值，而沒有考慮各個樣本的具體情況。比如投票法它的基本思想是：由基分類器對樣本進行預測，每一個基分類器對自己所預測的類投一票，得到票數最多的類就是該樣本的最終預測結果。這種集成方法往往會導致結果更傾向于那些易于識別的樣本，而對于那些容易出錯的樣本，由于大部分分類器識別錯誤，導致最終結果也是錯誤的，無法發揮那些識別率較低，卻具有很高差異性的分類器的作用。本文從基于實例的角度，采取多次改變樣本權重以設定各分類器權重的思想，設

計了一種基于集成學習的強分類器集成模型，并提出了一種FSE(Fast Strong-classifiers Ensemble)集成算法來設定模型中基分類器的權重。最后通過算法分析和實驗結果表明，本文模型的精度優于所有用于集成的基分類器以及常用集成方法，具有更優的精度以及更好的泛化能力,同時由于使用的分類器屬于強分類器，極大地縮短了訓練模型的時間,使其更具有實際應用價值。

1 定義與模型

差異性是高泛化能力集成的必要條件，為了使選擇的基分類器具有很高的差異度，本文從識別率和差異性的角度設定了一種基分類器評價方法，從眾多強分類器中選擇最佳的基分類器集成組合。最后使用FSE算法集成所選的基分類器形成具有精度高、訓練時間短的超強分類器。該模型包括訓練模塊和測試模塊兩部分，如圖1所示。

圖1 強分類器集成模型

訓練模塊主要分為五部分：1)提取特征；2)數據抽樣；3)訓練基分類器；4)挑選基分類器；5)設置基分類器權重。

測試模塊主要分為四部分：1)提取特征；2)數據抽樣；3)使用集成分類器；4)輸出結果。

下面對模塊中出現的各步驟進行詳細說明：

提取特征 訓練模塊和測試模塊均使用人工神經網絡(Artificial Neural Network, ANN)對數據集進行特征提取。由于本文主要采用基于實例思想，更關注當前樣本權值分配，使用ANN可以在面對新樣本時快速而有效地建立新的目標函數。

數據抽樣 訓練模塊的數據抽樣部分對經過ANN提取特征后的有標簽數據集進行分層抽樣，得到訓練數據集1和訓練數據集2。其中訓練數據集1供訓練分類器使用；而訓練數據集2供訓練FSE集成分類器使用。測試模塊的數據抽樣部分對經過ANN提取特征后的無標簽數據集進行分層抽樣得到測試數據集，供測試FSE集成分類器使用。

訓練基分類器 該部分使用訓練數據集1對多種機器學習算法進行訓練，得到對應的分類器。

挑選基分類器 該部分使用本文所提的基分類器評價方法在訓練好的分類器中挑選用于集成的基分類器。

設置基分類器權重 該部分使用FSE算法和訓練數據集2為上一步驟中得到的基分類器設置各自權重，最終加權得到FSE集成分類器。

使用集成分類器 使用測試數據集對得到的集成分類器進行測試，并輸出數據集的類別標簽作為結果。

2 算法描述

2.1 基分類器評價方法

集成學習的效果取決于基分類器之間的差異性，因此在選擇基分類器之前必須先設定選擇分類器的度量標準。為此，本文采用識別率和差異度來度量。

定義1 識別率。

設存在分類器Ci，非空樣本集S被分類器正確分類的樣本集合為Si，N(S)為S中所含樣本的個數，T為分類器的識別率，其定義如式(1)所示：

Ti=N(Si)/N(S)

(1)

定義2 差異度。

設存在兩個分類器Ci和Cj，非空樣本集S被兩個分類器正確分類的樣本集合分別為Si和Sj，F為兩個分類器的差異度，N(S)為S中所含樣本的個數，則Cj對于Ci的差異度定義如式(2)所示：

(2)

由定義2可知，Fj→i越大，則Cj與Ci間差異性越大；反之，差異性越小。

本模型中設定的分類器可能不止兩種，這對于最終的集成分類器的泛化能力提高是有利的。不過也因此，需對式(1)的公式作進一步定義。假設在已有分類器Ci和Cj集成的基礎上加上Ck，則Ck對于Ci和Cj集成分類器的差異度可定義為式(3)：

(3)

其中:Fk→ij越大，則Ck與Ci和Cj集成分類器差異性越大；反之，差異性越小。

根據上述的選擇基分類器度量標準的定義，本文設計了一種基分類器評價算法(如算法1所示)。它的主要思想是先按照識別率在強分類器集合Q中對分類器進行排序，剔除不合格分類器，并得到識別率最高的分類器C1；然后在剩余分類器集合中找出與分類器C1差異度最大的分類器C2，將C1與C2進行集成。重復以上步驟，得到最終分類器組合。評價基分類器偽代碼如下所示。

算法1 評價基分類器。

輸入:Q{Qi|i=1,2,…,n}; 輸出:C{Ci|i=1,2,…,l+1}

//所有分類器集合

1)

Fori=1 ton-1 do

2)

IfTQi≤T′ Then

3)

刪除TQi

4)

End if

//設置閾值T′剔除集合中不合格分類器

5)

IfTQi+1≥TQiThen

6)

C1=Qi+1

7)

End if

8)

End for

//尋找識別率最高的分類器C1

9)

Q=1-C1

10)

C=C1

11)

Whilel≠0(1≤l≤n-1) do

12)

Forj=1 ton-ldo

13)

IfFQj+1→C≥FQj→CThen

14)

C2=Qj+1

15)

End if

16)

End for

//尋找與集成分類器C差異度最大的分類器C2

17)

C=C∪C2

18)

Q=Q-C2

19)

l--

20)

End while

21)

ReturnC{Ci|i=1,2,…,l+1}

在基分類器有數量限制的情況下，按照該算法在強分類器集合Q中得到識別率最高、泛化能力最強的基分類器組合C。其中：語句1)是分類器排序過程，執行了n-1次；語句11)執行了l次；語句12)作為11)的內層循環執行了n-l次。所以算法1的時間復雜度是O(n+l(n-l))，其中n是供選擇的強分類器個數，l是需要的基分類器個數。

2.2FSE

通過算法1選定好基分類器之后，強分類器之間的集成方法就成為了實現集成學習系統的關鍵。本文提出了FSE算法——一種基于實例的強分類器快速集成算法。算法核心思想是：打破已有的樣本分布, 重新采樣使分類器更多地關注難學習的樣本，并以此決定各分類器的權重。在描述算法之前，需要先作一些定義。

定義3 錯分率。

ER=1-T

(4)

其中：ER表示分類器對樣本錯誤分類的比例；T是分類器識別率。

定義4 權重。

W=I/N

(5)

其中：W表示某樣本d在總樣本D中的重要程度；I表示單體樣本訓練最終分類器的能力;N表示所有樣本訓練最終分類器的能力。

FSE算法開始時，所有樣本被賦予相同的權重1/N，訓練算法1中得到的基分類器，并挑選出最佳分類器。每一輪結束后更新樣本權重：增加被錯誤分類樣本的權重，減少被正確分類樣本的權重，這樣迫使分類器在隨后的迭代中更加關注那些難以分類的樣本。重復以上步驟，直到算法滿足結束條件為止。算法的輸入為N對訓練樣本與標簽的集合{(Xj,Yj)|j=1,2,…,N}，其中X為樣本，Y為類標簽；最終分類器C*作為算法的輸出；分類器C{Ci|i=1,2,…,l}為算法1中得到的基分類器集合。FSE偽代碼如下所示。

算法2 FSE。

輸入:{(Xj,Yj)|j=1,2,…,N}； 輸出:C*

//最終集成分類器

1)

w={wj=1/N|j=1,2,…,N}

//初始化各樣本權重

2)

t=l

//根據算法1選擇的基分類器數目確定循環次數

3)

Whilet≠0

4)

Fori=1 tol-1 do

5)

IfERCi+1≤ERCiThen

6)

7)

End if

8)

End for

9)

10)

Ifεi=0 Then

11)

Break

12)

End if

13)

14)

//在下一次循環中更改wj樣本權重，其中Zj是規泛化因子，

//使所有樣本和為1

15)

t--

16)

End while

17)

本文提出的FSE算法主要有如下優勢：

1)通過基分類器評價方法選取多個具有差異性的強分類器組合，并在FSE算法中將其作為基分類器，增加了分類器的多樣性，在保證精度的情況下，提高了最終集成結果的泛化能力。

2)FSE算法使用算法1中得到的強分類器作為基分類器，讓迭代次數等于選取的基分類器個數，使得訓練時間大幅度縮減。

該算法中，語句1)執行了N次，語句3)執行了l次，語句4)作為語句3)的內層循環執行了l-1次。所以算法2的時間復雜度是O(N+l*(l-1))。其中:l是算法1中挑選出的基分類器個數，N為訓練樣本個數。

3 實驗及結果分析

3.1 實驗環境及數據集

本文的實驗是用MatlabR2010b在CPU為2.53GHz、內存容量為4GB計算機上進行。實驗中使用UCI數據庫[17]中的chess數據集作為實驗樣本，基本情況見表1。該數據分為獲勝和非獲勝兩類。數據集已提取完特征，每組36維特征數組。數據抽樣階段，抽取2 000個樣本作為分類器訓練集；抽取400個樣本作為集成訓練集；抽取600個樣本作為集成測試集。

由于本文模型處理的是原始數據，實驗數據集還使用了真實數據集chair，基本情況見表1。數據分為椅子和非椅子兩類，圖片分辨率為800×800。提取特征階段，使用ANN自主進行特征提取，每個樣本形成一組64維特征數組。數據抽樣階段，抽取600個樣本作為分類器訓練集；抽取300個樣本作為集成訓練集；抽取100個樣本作為集成測試集。

表1 數據集的基本情況

3.2 挑選基分類器與未挑選集成分類器精確度對比

由于機器學習算法有很多，對應的推廣更是不計其數，所以窮舉所有強分類器并挑選最佳分類器顯然是不現實的，因此，僅針對常用機器學習分類器以及chess數據集，使用本文所提的基分類器評價方法得到分類器組合方案，部分結果見表2。

表2 分類器集成方案

由于Boosting方法的集成分類器效果明顯優于Bagging，對比實驗中，采用Boosting算法來訓練并產生新基分類器，即重復地隨機選擇樣本子集作為訓練集；采用的基分類器是CART樹。利用Boosting算法從訓練樣本中隨機選取一些樣本組成10、15、20、25個樣本子集，并用它們生成的10、15、20、25個基分類器組合，分別計算它們識別率并用其對集成訓練樣本進行識別，根據識別率進行排序，挑選識別率最高的一組。利用基分類器評價算法在常用分類器中選出對應數量的差異性最大的基分類器組合，最后分別計算各自識別率。兩者均用投票法和線性組合法完成分類器集成，表3給出了使用Boosting方法和使用基分類器評價方法構造的不同分類器組合的識別率。

表3 使用不同方法構造的不同集成分類器識別率 %

由表3可以看出，在chess數據集下，未利用基分類器評價方法的集成分類器精度在分類器數量為20和25時最高達到90.2%；相同數量的基分類器組合情況下，利用本文的基分類器評價方法的集成分類器識別率最高達到93.9%和92.2%。在chair數據集下，集成方法為投票法情況下，利用基分類器評價方法的集成分類器分類精度比未用的集成分類器在分類器數量為10時最高提高了5.4%；集成方法為線性組合情況下，識別率在分類器數量為15時最高提高了4.5%。由此可見，利用基分類器評價方法可以有效提高集成分類器的識別率,而且構造多分類器集成系統時，分類器數量并非越多越好。

3.3FSE集成方法與常用集成方法識別率對比

為了對比使用FSE集成方法與常用集成方法的區別，在3.2節使用基分類器評價方法構造的分類器實驗基礎上增加本文所提的FSE集成方法，具體結果見表4。

表4 FSE集成方法與常用集成方法識別率 %

3.4FSE集成模型與Boosting分類器+常用集成方法實驗時間對比

為了檢驗FSE集成模型的性能，本實驗以FSE模型和Boosting算法訓練時間為標準，比較兩者達到相對穩定識別率時的時間消耗,具體結果見圖2、3。

由圖2可以看出，由于Boosting使用的是識別率略高于50%的弱分類器，所以在實驗1開始集成分類器的識別率僅略高于50%，但隨著時間增加，其識別率有顯著提高。chess數據集下，Boosting+常用集成方法訓練到4min時識別率達到90%左右，不過識別率變化大幅減小，但仍然保有上升趨勢；而FSE集成模型在1min左右即達到90%的高識別率，后續部分僅為了對比讓其繼續執行相應時間，雖然偶爾出現輕微的過學習狀態(識別率下降)，但實際應用過程中，當達到穩定識別率且不需要繼續提高識別率情況下，后續的過程是沒有必要的。圖3也保有此類規律。

本實驗中chess數據集下FSE集成模型的比Boosting+常用集成模型縮短了75%訓練時間，chair數據集下縮短了80%訓練時間。由此可得，FSE集成模型有效地加快了訓練速度。

圖2 chess數據集下時間消耗對比

圖3 chair數據集下時間消耗對比

4 結語

針對集成分類器犧牲存儲和計算來提高精度的問題，本文提出一種基于實例的強分類器快速集成方法。該方法通過基分類器評價方法挑選差異性最大的分類器組合，然后利用FSE算法對分類器進行集成。本文采用了2個真實數據集進行驗證，結果表明FSE不僅提高了識別精度，還大幅度縮短了訓練時間。今后的研究工作中，將著重考慮利用深度學習知識改進分類器評價方法和集成算法。

)

[1]SILVAC,LOTRICU,RIBEIROB,etal.Distributedtextclassificationwithanensemblekernel-basedlearningapproach[J].IEEETransactionsonSystems,Man,andCybernetics,PartC:ApplicationsandReviews, 2010, 40(3): 287-297.

[2]BARA,ROKACHL,SHANIG,etal.Improvingsimplecollaborativefilteringmodelsusingensemblemethods[C]//Proceedingsofthe11thInternationalWorkshoponMultipleClassifierSystems,LNCS7872.Berlin:Springer, 2013: 1-12.

[3]ZHOUZH,JIANGY,YANGYB,etal.Lungcancercellidentificationbasedonartificialneuralnetworkensembles[J].ArtificialIntelligenceinMedicine, 2002, 24(1): 25-36.

[4]BORGHYSD,YVINECY,PERNEELC,etal.Supervisedfeature-basedclassificationofmulti-channelSARimages[J].PatternRecognitionLetters, 2006, 27(4): 252-258.

[5]ZUOL,HOUL,WUW,etal.FaultdiagnosisofanalogICbasedonwaveletneuralnetworkensemble[C]//ISNN2009:Proceedingsofthe6thInternationalSymposiumonNeuralNetworks,LNCS5553.Berlin:Springer, 2009: 772-779.

[6]POLIKARR.Ensemblelearning[M]//ZHANGC,MAY.EnsembleMachineLearning.Berlin:Springer, 2012: 1-34.

[7]LIUCL.Classifiercombinationbasedonconfidencetransformation[J].PatternRecognition, 2005, 38(1): 11-28.

[8]SHIPPCA,KUNCHEVALI.Relationshipsbetweencombinationmethodsandmeasuresofdiversityincombiningclassifiers[J].InformationFusion, 2002, 3(2): 135-148.

[9]JIANGL,CAIZ,ZHANGH,etal.NaiveBayestextclassifiers:alocallyweightedlearningapproach[J].JournalofExperimentalandTheoreticalArtificialIntelligence, 2013, 25(2): 273-286.

[10]YUKSELSE,WILSONJN,GADERPD.Twentyyearsofmixtureofexperts[J].IEEETransactionsonNeuralNetworksandLearningSystems, 2012, 23(8): 1177-1193.

[11]SHIL,WANGQ,MAX,etal.Spamemailclassificationusingdecisiontreeensemble[J].JournalofComputationalInformationSystems, 2012, 8(3): 949-956.

[12]SCHAPIRERE,FREUNDY,BARTLETTPL,etal.Boostingthemargin:anewexplanationfortheeffectivenessofvotingmethods[J].AnnalsofStatistics, 1998, 26(5): 1651-1686.

[13]LIUY,YAOX.Ensemblelearningvianegativecorrelation[J].NeuralNetworks, 1999, 12(10): 1399-1404.

[14]ZHANGY,BURERS,STREETWN.Ensemblepruningviasemi-definiteprogramming[J].JournalofMachineLearningResearch, 2006, 7(3): 1315-1338.

[15]LIN,ZHOUZH.Selectiveensembleunderregularizationframework[C]//Proceedingsofthe8thInternationalWorkshoponMultipleClassifierSystems.Berlin:Springer, 2009: 293-303.

[16]JIANGM,YIX,LINGN.Framelayerbitallocationschemeforconstantqualityvideo[C]//Proceedingsofthe2004IEEEInternationalConferenceonMultimediaandExpo.Piscataway,NJ:IEEE, 2004, 2: 1055-1058.

[17]FRANKA,ASUNCIONA.UCIMachineLearningRepository[DB/OL]. [2016- 03- 15].http://www.ics.uci.edu/?mlearn/.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61170035, 61272420, 61502233),theJiangsuProvinceScienceandTechnologyAchievementTransformationProjectsofSpecialFunds(BA2013047),theJiangsuProvinceSixTalentPeaksProject(WLW-004),theNnationalDefenseScienceandTechnologyKeyLaboratoryofBasicResearchProjects(DXZT-JC-ZZ-2013-019),theMilitaryAcademyofPre-ResearchProject(62201070151),theFundamentalResearchFundsfortheCentralUniversities(30916011328).

XU Yewang, born in 1991, M. S. candidate. His research interests include data mining, big data information security.

WANG Yongli, born in 1974, Ph. D., professor. His research interests include database, data mining, big data processing, intelligent service, cloud computing.

ZHAO Zhongwen, born in 1974, M. S., associate professor. His research interests include information system, multidimensional information, situation comprehension.

Fast ensemble method for strong classifiers based on instance

XU Yewang1*, WANG Yongli1, ZHAO Zhongwen2

(1. Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing Jiangsu 210094, China;2. National Key Laboratory of Complex Electronic System Simulation, Academy of Equipment, Beijing 101416, China)

Focusing on the issue that the ensemble classifier based on weak classifiers needs to sacrifice a lot of training time to obtain high precision, an ensemble method of strong classifiers based on instances named Fast Strong-classifiers Ensemble (FSE) was proposed. Firstly, the evaluation method was used to eliminate substandard classifier and order the restclassifiers by the accuracy and diversity to obtain a set of classifiers with highest precision and maximal difference. Secondly, the FSE algorithm was used to break the existing sample distribution, to re-sample and make the classifier pay more attention to learn the difficult samples. Finally, the ensemble classifier was completed by determining the weight of each classifier simultaneously. The experiments were conducted on UCI dataset and customized dataset. The accuracy of the Boosting reached 90.2% and 90.4% on both datasets respectively, and the accuracy of the FSE reached 95.6% and 93.9%. The training time of ensemble classifier with FSE was shortened by 75% and 80% compared to the ensemble classifier with Boosting when they reached the same accuracy. The theoretical analysis and simulation results show that FSE ensemble model can effectively improve the recognition accuracy and shorten training time.

strong classifiers ensemble model; base classifier evaluation method; ensemble algorithm; sample distribution; ensemble learning

2016- 07- 29;

2016- 09- 28。 基金項目:國家自然科學基金資助項目(61170035,61272420,61502233);江蘇省科技成果轉化專項資金資助項目(BA2013047);江蘇省六大人才高峰項目(WLW-004);國防科技重點實驗室基礎研究項目(DXZT-JC-ZZ-2013-019);兵科院預研項目(62201070151);中央高校基本科研業務費專項資金資助項目(30916011328)。

許業旺(1991—),男,江蘇淮安人,碩士研究生,主要研究方向：數據挖掘、大數據信息安全; 王永利(1974—),男,哈爾濱佳木斯人,教授,博士,主要研究方向：數據庫、數據挖掘、大數據處理、智能服務、云計算; 趙忠文(1974—),男,北京人,副教授,碩士,主要研究方向：信息系統、多維信息、態勢綜合。

1001- 9081(2017)04- 1100- 05

10.11772/j.issn.1001- 9081.2017.04.1100

TP391

A