毛莎莎,熊 霖,焦李成,張 爽,陳 博

(西安電子科技大學(xué)智能感知與圖像理解教育部重點實驗室,陜西西安 710071)

利用旋轉(zhuǎn)森林變換的異構(gòu)多分類器集成算法

毛莎莎,熊 霖,焦李成,張 爽,陳 博

(西安電子科技大學(xué)智能感知與圖像理解教育部重點實驗室,陜西西安 710071)

為了增強集成系統(tǒng)中各分類器之間的差異性,提出了一種使用旋轉(zhuǎn)森林策略集成兩種不同模型分類器的方法,即異構(gòu)多分類器集成學(xué)習(xí)算法.首先采用旋轉(zhuǎn)森林對原始樣本集進行變換劃分,獲得新的樣本集;然后通過特定比例選擇分類精度高的支撐矢量機或分類速度較快的核匹配追蹤作為基本的集成個體分類器,并對新樣本集進行分類,獲得其預(yù)測標(biāo)記;最后結(jié)合兩種模型下的預(yù)測標(biāo)記.該算法通過結(jié)合兩種不同分類器模型,實現(xiàn)了精度和速度互補,將二者混合集成后改善了集成系統(tǒng)泛化誤差,相比單個模型集成提高了系統(tǒng)分類性能.對UCI數(shù)據(jù)集和遙感圖像數(shù)據(jù)集的仿真實驗結(jié)果表明,文中算法相比單一分類器集成縮短了運行時間,同時提高了系統(tǒng)的分類準(zhǔn)確率.

集成分類器;旋轉(zhuǎn)森林;支撐矢量機;核匹配追蹤

近年來,分類器集成[1-3]已成為機器學(xué)習(xí)領(lǐng)域研究的主流和熱點.分類器集成是指將多個分類器進行結(jié)合以此來提高單個分類器的分類性能的學(xué)習(xí)方法,它是集成學(xué)習(xí)在有監(jiān)督分類中的典型應(yīng)用.1990年,Hansen和Salamon[4]首先提出了神經(jīng)網(wǎng)絡(luò)集成,并且證明集成多個網(wǎng)絡(luò)能增強單個弱神經(jīng)網(wǎng)絡(luò)的泛化能力.隨后,支撐矢量機集成[6]被提出,表明集成學(xué)習(xí)不僅能改善單個弱分類器性能,也能提高強分類器性能.目前,許多分類器集成方法[2,5,14,18]已經(jīng)被提出,同時也被應(yīng)用到圖像分類[7]、醫(yī)學(xué)圖像處理[8]等領(lǐng)域.

在一個分類器集成系統(tǒng)中,一個分類器相當(dāng)于集成學(xué)習(xí)中的一個個體,因此,它也被稱為一個集成個體.根據(jù)已有集成方法,表明集成分類器能有效提高分類性能.然而,在實際應(yīng)用中大部分的研究者均采用多個同質(zhì)的分類器進行集成,如所有個體分類器都是神經(jīng)網(wǎng)絡(luò)、決策樹等.研究表明,一個有效的集成系統(tǒng)不僅應(yīng)該包含一組精度較高的分類器,同時分類器的錯誤分類也應(yīng)該分布在輸入空間的不同部分[9-10].換句話說,一個理想的集成系統(tǒng)應(yīng)該包含一組精確的且盡可能不同的分類器.1999年Opitz[11]給出集成學(xué)習(xí)的廣義定義,即只要是使用多個分類器來解決問題就是集成學(xué)習(xí),這表明集成系統(tǒng)不局限于單一模型分類器.1997年Margineantu和Dietterich[12]提出‘Kappa-error’圖來展現(xiàn)集成性能,以Bagging和Boosting為例表明集成個體差異性和個體誤差的關(guān)系:分類器間的差異性影響集成系統(tǒng)性能,差異性越大則集成分類器性能越好,同時差異性的增加卻以分類器自身的誤差增大為代價.

支撐矢量機(Support Vector Machine,SVM)[9]是最先采用核技術(shù)的算法,它在解決小樣本問題,特別是高維小樣本非線性問題中有許多獨有的優(yōu)勢,因此,被廣泛地應(yīng)用于分類和回歸問題,并取得了巨大的成功.核匹配追蹤(Kernel Matching Pursuit,KMP)[10]是近年來新提出的一種模式識別方法,受啟發(fā)于支撐矢量機,但卻比支撐矢量機具有更為稀疏的解.雖然支撐矢量機和核匹配追蹤是兩種比較好且應(yīng)用廣泛的分類器,但是仍然存在分類精度依賴參數(shù)選擇、支撐矢量機計算復(fù)雜度高,以及核匹配追蹤在訓(xùn)練樣本規(guī)模較大時存在推廣能力差等問題.基于以上原因,文中提出了一種基于旋轉(zhuǎn)森林變換[2]的異構(gòu)分類器集成的方法,不同類型的分類器可以提供關(guān)于被處理數(shù)據(jù)互補的信息,從而降低單一模型的近似誤差,提高集成精度.同時,通過集成兩種不同模型分類器增強差異性,以此避免在單一模型集成中通過降低個體性能來滿足個體差異性需求的弊端.

1 異構(gòu)多分類器集成

1.1 旋轉(zhuǎn)森林變換

由于集成學(xué)習(xí)的分類器構(gòu)建要求包含一組精度較高的分類器,而且這些分類器的差異要盡可能地大.按照集成系統(tǒng)的構(gòu)造方法來劃分,集成系統(tǒng)[13]可以分為:基于不同訓(xùn)練數(shù)據(jù)集的構(gòu)造方式,如Bagging算法[14];基于不同特征集的構(gòu)造方式,如隨機子空間算法等;基于同一訓(xùn)練數(shù)據(jù)集不同重抽樣技術(shù)的構(gòu)造方式等.旋轉(zhuǎn)森林策略[2]主要是對集成分類器的原始樣本特征進行處理,通過一定的特征提取變換獲得集成所需的新樣本,并且在保證分類準(zhǔn)確性的前提下,增加集成分類器個體間的差異性.其主要思想如下:

給定初始樣本集S(N×D),其中N和D分別是樣本個數(shù)和樣本特征數(shù).首先,將樣本的特征隨機劃分為K個特征子集(無重復(fù)抽取),每個特征子集的特征數(shù)為M(M=DK),基于特征子集獲得K個樣本子集{Si}(i=1,…,K),若特征數(shù)不能整除,則將剩余特征加入第K組特征.然后,采用主成分分析變換方法對樣本子集Si進行特征轉(zhuǎn)換,獲得M個特征向量,并選擇M′個非零特征值對應(yīng)的特征向量組成一個特征向量矩陣ai=[ai1,…,aiM′],將獲得的K個特征向量矩陣合并獲得矩陣R,其中ai位于R的第i個M行和M列位置.最后,找出R中特征向量對應(yīng)在初始樣本中的特征及特征初始位置(維數(shù)),將每個特征向量按照對應(yīng)特征初始位置重新排列,得到新的特征向量矩陣R*,最后由R*產(chǎn)生新樣本Snew=S·R*.

旋轉(zhuǎn)森林策略是針對集成分類器間的差異性和集成分類器的準(zhǔn)確性兩個方面提出的.研究表明,當(dāng)使用經(jīng)典集成策略時,集成分類器個數(shù)一般選擇15到25個才能取得較好的分類性能,同時也意味著其比使用單個分類器分類消耗更多的時間,而旋轉(zhuǎn)森林策略能夠使得分類器個數(shù)降在10個以下時仍能取得好的分類結(jié)果,且改善Bagging算法的波動性.因此,文中采用旋轉(zhuǎn)森林策略構(gòu)造每個集成分類器的訓(xùn)練樣本,通過集成個體數(shù)目減少有效縮短集成運行時間,同時保證集成分類正確率.

1.2 混合異構(gòu)多分類器集成

根據(jù)吳建鑫[5]等對集成系統(tǒng)泛化誤差的分析,在集成泛化誤差E、各個體泛化誤差均值ˉE和個體平均總體相關(guān)度ˉA之間存在關(guān)系E=ˉE-ˉA,因而要增強集成系統(tǒng)的泛化能力,就應(yīng)使各個體分類器之間盡可能不相關(guān),同時保證個體分類器自身誤差小.文獻[15]給出集成系統(tǒng)的錯誤率與單個分類器的相關(guān)性,兩者的關(guān)系表示為

其中,ρ表示分類器誤差之間的相關(guān)性,EOptimalBayes表示在所有條件概率已知情況下使用貝葉斯規(guī)則得到的錯誤識別率.當(dāng)ρ=0時,集成系統(tǒng)的誤差隨著分類器數(shù)目的增加按比例減小;當(dāng)ρ=1時,集成系統(tǒng)的誤差等于單個分類器的誤差.因此,式(1)表明當(dāng)個體差異性越大且個體誤差越小時集成誤差越小.

目前,大部分的分類器集成建立在同一種分類器模型上,對此研究較為成熟,并且也證明其能獲得好的分類性能.然而,根據(jù)理論分析得出,如果個體分類器之間的誤差相關(guān)性ρ(0＜ρ≤1)越小,則集成系統(tǒng)的誤差越小,但同時如果增大分類器的誤差ˉE,對集成系統(tǒng)性能提高則會產(chǎn)生負(fù)作用.因此,采用單一模型進行集成已經(jīng)不能滿足更高集成性能的要求.為了獲得更小的集成誤差E,文中提出了一種異構(gòu)多分類器集成的方法,即將支撐矢量機和核匹配追蹤兩種不同的核學(xué)習(xí)器同時集成,選用旋轉(zhuǎn)森林策略獲得個體分類器的訓(xùn)練樣本子集.其目的在于增強分類器間的差異性,同時克服分類器誤差增大對集成性能的影響.首先,由于兩種不同模型的分類器自身的分類機理不同,因此,產(chǎn)生的誤差分布將會有差異,且集成分類器的誤差E由支撐矢量機和核匹配追蹤共同獲得,即

其中,Es和Ek分別表示個體支撐矢量機和核匹配追蹤的分類誤差,Ls和Lk分別表示個體支撐矢量機和核匹配追蹤分類器的個數(shù).依據(jù)文獻[16]中總結(jié)的10種衡量差異性標(biāo)準(zhǔn),文中選用重合失敗多樣性(Coincident Failure Diversity,CFD)標(biāo)準(zhǔn),多樣性的值越大則差異性越大.由于文中提出異構(gòu)分類器集成方法,因此,分類器間的差異性不再依靠單一分類器模型獲得,而是由兩者共同決定,則對于隨機抽取的一個樣本,其分類誤差應(yīng)該由不同模型的最大誤差產(chǎn)生,即

其中,psi和pki分別為兩個分類器對隨機抽取樣本的誤分概率,p0為ps0和pk0的最大值.根據(jù)式(3),表明異構(gòu)分類器集成可獲得較單一模型集成更高的多樣性值,即增強差異性.此外,支撐矢量機和核匹配追蹤分類器集成能相互彌補自身不足,比如,當(dāng)訓(xùn)練樣本個數(shù)較多時,支撐矢量機執(zhí)行的時間長,甚至?xí)霈F(xiàn)內(nèi)存溢出無法計算的情況,而核匹配追蹤在處理大樣本個數(shù)的分類中取得較支撐矢量機更好的效果.此外,核匹配追蹤算法比支撐矢量機算法運行速度快,因此,將二者結(jié)合既可處理樣本數(shù)量較大的數(shù)據(jù),同時也可縮短分類時間.文中算法具體步驟如下:

step 1 輸入初始樣本X,樣本包括D個特征,集成分類器個數(shù)Ls和Lk,L=Ls+Lk;

step 2 對X的D個特征進行等劃分,獲得K個具有不同特征的樣本子集,Xk表示第k個樣本子集,每個子集具有M個特征,M=DK;

step 3 對K個樣本子集進行如下處理:

step 4 對R重新排列得R*,獲得新樣本Xnew,Xnew=XR*;

step 5 Xnew作為分類器的樣本,選擇分類器(支撐矢量機或核匹配追蹤)訓(xùn)練獲得一個集成子分類器Cls或者Clk(l=1,…,L).返回step 2,循環(huán)L次,獲得集成分類器組Ω={C1,…,CL};

step 6 分別使用L個分類器對測試樣本集進行分類,獲得預(yù)測函數(shù){fl}和預(yù)測標(biāo)記{hl};

step 7 對預(yù)測函數(shù)和預(yù)測標(biāo)記進行投票處理,獲得集成分類器最終預(yù)測標(biāo)記Henc.

文中方法在最終集成分類器時,采用了投票準(zhǔn)則將其結(jié)合.然而,在大部分的分類器集成中,最終的集成結(jié)果是通過對預(yù)測標(biāo)記h進行投票表決產(chǎn)生的,但也因此出現(xiàn)一個問題:如果集成分類器的個數(shù)為偶數(shù),則投票獲得的集成分類器最終預(yù)測標(biāo)記中會出現(xiàn)零值,也就是無法獲得標(biāo)記.為了解決此問題,文中將判決函數(shù)f作為投票對象,并通過下式獲得一個樣本x的最優(yōu)判決函數(shù)[17]fbest(x)和最優(yōu)預(yù)測標(biāo)記hbest(x):

2 實驗結(jié)果與分析

本節(jié)將通過兩個實驗來驗證文中方法的有效性,分別對UCI數(shù)據(jù)和6類飛機圖像進行分類性能測試.實驗中使用計算機的配置為Intel(R)Xeon(TM),CPU6300(3.60 GHz),內(nèi)存2.75 GB,MATLAB7.0.其中,支撐矢量機和核匹配追蹤分類器均采用徑向基作為核函數(shù):

在實驗中,集成分類器的個數(shù)設(shè)為6,支撐矢量機和核匹配追蹤分類器按一比一的比例進行集成.另外,對于每個數(shù)據(jù)集,支撐矢量機和核匹配追蹤分類器的參數(shù)分別通過十倍交叉驗證獲得.對于多類數(shù)據(jù)分類,文中采用一對一策略進行處理.

2.1 UCI數(shù)據(jù)集分類

實驗選擇了10個常用UCI數(shù)據(jù)集進行測試,實驗結(jié)果如表1所示.在表1中,數(shù)據(jù)集后括號中分別表示數(shù)據(jù)集的樣本數(shù)和特征維數(shù)(樣本數(shù)×特征維數(shù)),并且時間和分類準(zhǔn)確率均為50次集成的平均值.實驗中旋轉(zhuǎn)森林策略采用75%的采樣率,并且樣本特征劃分根據(jù)每個數(shù)據(jù)集的特征數(shù)確定,劃分子集數(shù)在2～6之間.

表1 UCI數(shù)據(jù)集3種方法分類結(jié)果比較

從表1可以看出,10個數(shù)據(jù)集中有9個數(shù)據(jù)在文中算法下獲得了更高的識別率,而支撐矢量機集成(SVM集成)算法只有1個勝出,核匹配追蹤集成(KMP集成)算法只有1個與文中算法同時勝出(但KMP集成算法的運行時間縮短).仿真實驗結(jié)果驗證了集成不同模型的分類器能夠改善集成個體間的差異性和分類器自身誤差,進而提高集成系統(tǒng)分類性能.同時,文中算法所需的分類時間基本上介于支撐矢量機集成算法和核匹配追蹤集成算法之間,尤其對于數(shù)據(jù)樣本稍大的數(shù)據(jù),在精度略有提高的基礎(chǔ)上,文中算法比支撐矢量機集成算法快很多.由此可以證明異構(gòu)支撐矢量機和核匹配追蹤分類器集成比單個分類器集成具有更好的分類性能,可以在分類準(zhǔn)確率高和分類速度方面有較好的折中.

2.2 飛機圖像的識別

該實驗選用了613幅6類飛機圖像,其大小為128×128,6類飛機部分示例圖如圖1所示.實驗中分別采用不同種類特征提取方法獲得飛機特征,如采用小波分解、Contourlet分解和Brushlet分解提取了相應(yīng)的能量和方差特征.對于能量特征,文中采用L1范數(shù)能量測度:

其中,M×N為子帶大小,coef(i,j)為該子帶中第i行和第j列的系數(shù)值.對于方差特征,計算公式為

其中,Mean為該子帶系數(shù)的均值.

圖1 6類飛機圖像

在文中算法中,特征子集的劃分決定生成的新樣本,從而影響集成分類器之間的差異性,因此,為了更好說明異構(gòu)分類器集成的推廣性能,實驗中分別將飛機圖像的每種特征進行多個子集劃分,實驗結(jié)果如表2所示.其中,準(zhǔn)確率和時間均為50次集成的平均值,并且每個特征后面括號里表示原始特征維數(shù),后面一列中數(shù)字表示劃分子集個數(shù).從表2結(jié)果中明顯看出,文中算法較單個同質(zhì)分類器集成能獲得更好的分類性能,并且結(jié)合兩個分類器性能和時間的優(yōu)勢.此外,根據(jù)表2最后1行(Number)中列出13次實驗中具有最好分類性能的次數(shù),可知文中算法獲勝10次,而支撐矢量集成和核匹配追蹤集成僅獲勝2次和1次,這也暗示文中算法能夠獲得更高的分類精度,并且文中方法獲得好的分類性能并不取決于某種特定特征,而是對于大部分的特征都能取得好的分類性能,換言之,其較單個分類器集成具有更強的泛化能力.

表2 6類飛機圖像3種方法分類結(jié)果比較

3 結(jié)束語

筆者提出了一種將不同模型分類器集成的方法,即支撐矢量機和核匹配追蹤分類器集成,并且使用旋轉(zhuǎn)森林變換策略獲得個體分類器訓(xùn)練樣本子集.該方法主要從集成分類器模型自身誤差和分類器間差異性兩個因素出發(fā),通過結(jié)合不同模型的分類器來增加差異性,同時可以互相彌補分類器模型自身不足,以此改善集成性能.使用旋轉(zhuǎn)森林策略減少集成分類器的個數(shù),改善了個體分類準(zhǔn)確度和個體間差異性兩個因素相互限制的缺陷.UCI數(shù)據(jù)集和圖像數(shù)據(jù)實驗結(jié)果表明,文中算法較單一模型分類器集成能夠獲得更好的分類性能,在減少運行時間的同時,能夠提高或保持好的分類準(zhǔn)確率.

[1]Kuncheva L I.Combining Pattern Classifiers:Methods and Algorithms[M].New Jersey:John Wiley&Sons,2004.

[2]Rodriguez J J,Kuncheva L I,Alonso C J.Rotation Forest:A New Classifier Ensemble Method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(10):1619-1630.

[3]Zhang L,Zhou W D.Sparse Ensemble Using Weighted Combination Methods based on Linear Programming[J]. Pattern Recognition,2011,44(1):97-106.

[4]Hansen L K,Salamon P.Neural Network Ensembles[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1990,12(10):993-1001.

[5]吳建鑫,周志華,沈?qū)W華,等.一種選擇性神經(jīng)網(wǎng)絡(luò)集成構(gòu)造方法[J].計算機研究與發(fā)展,2000,37(9):1039-1044.

Wu Jianxin,Zhou Zhihua,Shen Xuehua,et al.A Selective Constructing Approach for Neural Network Ensemble[J]. Journal of Computer Research and Development,2000,37(9):1039-1044.

[6]李青,焦李成.利用集成支撐矢量機提高分類性能[J].西安電子科技大學(xué)學(xué)報,2007,34(1):68-70.

Li Qing,Jiao Licheng.Improvement Classification Performance by The Support Vector Machine Ensemble[J].Journal of Xidian University,2007,34(1):68-70.

[7]Alham N K,Li M Z,Liu Y,et al.A Distributed SVM Ensemble for Image Classification and Annotation[C]//9th International Conference on Fuzzy Systems and Knowledge Discovery.Piscataway:IEEE,2012:1581-1584.

[8]Ghorai S,Mukherjee A,Sengupta S,et al.Cancer Classification from Gene Expression Data by NPPC Ensemble[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics,2011,8(3):659-671.

[9]Vapnik V.The Nature of Statistical Learning Theory[M].Berlin:Springer-Verlag,1999.

[10]Vincent P,Bengio Y.Kernel Matching Pursuit[J].Machine Learning,2002,48(1-3):165-187.

[11]Opitz D W.Feature Selection for Ensemble[C]//Proceedings of the National Conference on Artificial Intelligence.New York:ACM,1999:379-384.

[12]Margineantu D D,Dietterich T G.Pruning Adaptive Boosting[C]//Proceedings of the 14th International Conference on Machine Learning.New York:ACM,1997:211-218.

[13]焦李成,公茂果,王爽,等.自然計算、機器學(xué)習(xí)與圖像理解前沿[M].西安:西安電子科技大學(xué)出版社,2008.

[14]Breiman L.Bagging Predictors[J].Machine learning,1996,24(2):123-140.

[15]Tumer K,Ghosh J.Ensembles of Radial Basis Function Networks for Spectroscopic Detection of Cervical Precancer[J]. IEEE Transactions on Biomedical Engineering,1998,45(8):953-961.

[16]Kuncheva L I,Whitaker C J.Measures of Diversity in Classifier Ensembles and Their Relationship with the Ensemble Accuracy[J].Machine Learning,2003,51(2):181-207.

[17]Valentini G,Muselli M,Ruffino F.Bagged Ensembles of Support Vector Machines for Gene Expression Data Analysis [C]//Proceedings of the International Joint Conference on Neural Networks.Piscataway:IEEE,2003:1844-1849.

[18]Yuan Hanning,Fang Meng,Zhu Xingquan.Hierarchical Sampling for Multi-Instance Ensemble Learning[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(12):2900-2905.

(編輯:李恩科)

Isomerous multiple classifier ensemble via transformation of the rotating forest

MAO Shasha,XIONG Lin,JIAO Licheng,ZHANG Shuang,CHEN Bo
(Ministry of Education Key Lab.of Intelligent Perception and Image Understanding, Xidian Univ.,Xi’an 710071,China)

In order to boost the diversity among individual classifiers of an ensemble,a new ensemble method is proposed that combines two different classifier models via a transformation of rotation forest, named by isomerous multiple classifier ensemble.Firstly,the original samples are transformed and divided by the rotating forest to obtain new samples.Then support vector machine with the high accuracy of classification or kernel matching pursuit with the speedy classification is selected as a basic classifier model based on a special proportion,the selected classifier is used to classify the new samples,and the predictive labels are obtained.Finally,the predictive labels given by two different models are combined to obtain the final predictive labels of an ensemble.Particularly,the proposed method achieves the complementarity of accuracy and speed by combining two different classifier models,and it is important that isomerous classifier ensemble improve the generalization error of an ensemble and increases the classification performance.According to the experimental results of classification for UCI datasets and remote sensing image datasets,it is illustrated that the proposed method shortens obviously the running time and improves the accuracy of classification,compared with an ensemble based on the single classifier model.

classifier ensemble;rotation forest;support vector machine;kernel matching pursuit

TP181

A

1001-2400(2014)05-0048-06

2013-07-08< class="emphasis_bold">網(wǎng)絡(luò)出版時間:

時間:2014-01-12

國家重點基礎(chǔ)研究發(fā)展計劃資助項目(2013CB329402);國家自然科學(xué)基金資助項目(61003198,60702062);高等學(xué)校學(xué)科創(chuàng)新引智計劃(111計劃)資助項目(B07048)

毛莎莎(1985-),女,西安電子科技大學(xué)博士研究生,E-mail:skymss@126.com.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.009.html

10.3969/j.issn.1001-2400.2014.05.009