利用旋轉森林變換的異構多分類器集成算法

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

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

利用旋轉森林變換的異構多分類器集成算法

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

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

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

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

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

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

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

1 異構多分類器集成

1.1 旋轉森林變換

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

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

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

1.2 混合異構多分類器集成

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

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

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

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

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

step 1 輸入初始樣本X,樣本包括D個特征,集成分類器個數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作為分類器的樣本,選擇分類器(支撐矢量機或核匹配追蹤)訓練獲得一個集成子分類器Cls或者Clk(l=1,…,L).返回step 2,循環L次,獲得集成分類器組Ω={C1,…,CL};

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

step 7 對預測函數和預測標記進行投票處理,獲得集成分類器最終預測標記Henc.

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

2 實驗結果與分析

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

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

2.1 UCI數據集分類

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

表1 UCI數據集3種方法分類結果比較

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

2.2 飛機圖像的識別

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

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

其中,Mean為該子帶系數的均值.

圖1 6類飛機圖像

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

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

3 結束語

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

[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]吳建鑫,周志華,沈學華,等.一種選擇性神經網絡集成構造方法[J].計算機研究與發展,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].西安電子科技大學學報,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]焦李成,公茂果,王爽,等.自然計算、機器學習與圖像理解前沿[M].西安:西安電子科技大學出版社,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">網絡出版時間:

時間:2014-01-12

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

毛莎莎(1985-),女,西安電子科技大學博士研究生,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