基于聚類選擇的分類器集成

摘要：提出了一種基于聚類選擇的分類器集成方法，通過聚類把模式特征空間劃分成不相交的區域，對于初始分類器集合，各區域給出分類器的刪除分值，各分類器總分值確定其刪除優先級別，由刪除優先級別選擇一組分類器組成集成。理論分析和實驗結果表明，基于聚類選擇的分類器集成方法能夠更好地對模式進行分類。

關鍵詞：分類器集成; 聚類； 分類器選擇； 差異性； 神經網絡

中圖分類號：TP18文獻標志碼：A

文章編號：1001-3695(2007)12-0085-03

實際應用中總是希望設計的模式識別系統能獲得最好的分類性能。為了實現這個目標，經典的方法是設計出一系列的分類器后，選擇具有最好性能的分類器作為最終使用的分類器。然而，不同的分類器本質上提供了對模式分類的補償信息，它們的集成有可能獲得比單一分類器更好的性能^[1]。因此，分類器集成^[2]引起了研究人員的廣泛關注，已經成為模式識別和機器學習領域的研究熱點。

分類器集成比單個分類器更有效的充分必要條件是集成中的分類器不僅是精確的而且是錯誤差異的。一般構造滿足上述條件的分類器方法有^[2]：不同的分類器采用不同的訓練數據；不同的分類器采用不同特征向量的模式表示；采用不同類型的分類器或對同一分類器采用不同的結構。顯然可以同時使用幾種方法生成分類器集成。對于神經網絡分類器，Partridge^[3]比較了各種方法生成錯誤差異分類器的能力，他指出不同的分類器采用不同的訓練數據、不同的分類器采用不同的類型是其中最好的兩種方法。

上述生成分類器集成的方法采取的是直接生成集成中個體分類器策略；生成的個體分類器不一定是錯誤差異的，即不同的個體分類器在特征空間產生的錯誤不一定分布在不同的區域。特別地，在集成中可能存在分類能力相似的分類器。對于一個實際的模式識別系統，在保證其分類能力的前提下，集成中個體分類器數目越少，系統的復雜性越低。既然直接策略不能得到最優的分類器集成，研究人員提出了另一種分類器集成設計策略——間接策略，即“過產生，再選擇”（overproduce and choose）策略^[4]。

對于間接策略，過產生階段可以采用直接策略生成集成的各種方法生成集成中個體分類器；再選擇階段是對過產生階段的優化，其目的是為了得到最好的分類器集成，即分類識別性能最好的分類器。因此識別的準確率或最小錯誤率是最直接的標準。由于認識到集成中個體分類器差異性與集成性能之間的關系，研究人員試圖用差異性引導再選擇階段對分類器的選擇^[5]。對差異性量化的形式各種各樣^[6]，不同的差異性度量的性質以及它們之間的關系，特別是它們與集成性能的關系還需要進一步研究。既然用直接策略生成的集成中有可能存在性能相近的分類器，對集成中個體分類器進行聚類就有可能從集成中選取一部分分類器重新組成新的集成，并且其中的個體分類器性能各不相同。Giacinto和Roli^[4]提出了一種基于分類器相關錯誤概率聚類的選擇性集成方法，取得了較好的效果，他們把在過產生階段生成的分類器成對進行考慮。但集成中個體分類器是一個整體，對各分類器分別進行考察不能體現它們的整體行為特性。為此，提出一種新的基于聚類的選擇性分類器集成(classifiers ensemble based on clustering and selection，CECS)方法，既考慮了經選擇形成的分類器集成中個體分類器的錯誤差異性，又考慮了集成行為的整體性。

1基于聚類的選擇性分類器集成

分類器集成采用“過產生，再選擇”的策略。假設經過過產生階段已生成了一組分類器。為了使再選擇階段得到的分類器具有錯誤差異性，即不同的分類器產生的錯誤是不相關的，把特征空間劃分成子區域，希望分類器錯誤出現在不同的子區域。

1．1特征空間劃分

劃分特征空間采用聚類方法，MacQueen^[7]提出的k－均值算法是一個著名的聚類學習算法。它根據相似度距離迭代地更新向量集的聚類中心。當聚類中心不再變化或滿足某些停止條件時，則停止迭代過程得到最終的聚類結果。k－均值算法的具體步驟為：

a)隨機選擇k個數據項作為聚類中心；

b)根據相似度距離公式，將數據集中的每一項數據分配到離它最近的聚類中去；

c)計算新的聚類中心；

d)若聚類中心未發生改變，算法結束；否則跳轉到b)。

由于所選擇的相似度距離公式的不同，k－均值算法所得到的聚類結果將存在較大的差異。為了簡化討論，本文采用歐氏距離作為k－均值算法的相似度距離公式。但值得注意的是，本文工作對其他距離公式同樣適用。

1．2算法原理

經過對特征空間的劃分，得到了k個不同的模式區域，k的大小決定特征空間劃分的粗細程度。一個可用于實際模式分類系統的分類器具有能夠被接受的識別率，只要k足夠大，總能保證分類器在一些區域的識別率為100%。

假設已生成m個分類器，希望選擇出l個分類器組成最終集成。Patridge和Yates^[8]提出了一種選擇性分類器集成方法，他們從m個分類器中選出l個分類能力最好的分類器組成最后集成。本文的算法思想是基于k個不同的模式區域投票選擇出l個分類器組成最后集成，也就是從m個分類器中刪除m-l個分類器組成最后集成。

算法中，數據集聚類數目k、過產生分類器數目m、最后經選擇生成的集成中個體分類器數目l、刪除分類器數目ld，都是需要預先設定的參數。設定k為數據類別數的兩倍，ld為l+3。l決定于集成的規模。

經步驟e)的處理，某些分類器的分值有可能相同。筆者采用它們在訓練數據集上的識別率確定其刪除的先后次序。

2實驗

為了驗證CECS算法的有效性，把用該算法生成的分類器集成與Patridge等人^[8]提出的算法（choose the best）生成的分類器集成以及直接由過產生得到的分類器組成的集成（overproduce ensemble）與這組分類器中最好的分類器（best）進行了比較。設定在過產生階段生成的分類器數目為40，在再選擇階段選取的分類器數目為20，所有分類器均為多層感知器神經網絡。

2．1實驗數據

實驗數據來自ELENA計劃數據庫^[9]和UCI數據庫^[10]。本文選擇了四個數據集。很多研究人員認為這些數據集有獨特的特性，它們被廣泛應用于分類器性能的比較。這四個數據集分別是clouds、phoneme、satimage、waveform。數據集的具體信息如表1所示。

2．2過產生分類器

在過產生階段生成三層（輸入層、隱層、輸出層）感知器（MLP）神經網絡分類器。設定隱層節點數為5，輸入節點數為數據屬性數，輸出節點數為數據類別數。神經網絡的訓練采用了MATLAB中的神經網絡工具箱^[12]，設定訓練步數為500；其他參數均采用MATLAB中的缺省設置。

過產生階段分類器的產生過程采用boosting技術^[11]，該技術可以產生一系列個體神經網絡分類器。各神經網絡的訓練集取決于在其之前產生的神經網絡的表現，被已有神經網絡錯誤判定的示例以較大的概論出現在新的神經網絡訓練集中。這樣，新神經網絡將能夠處理對已有神經網絡來說很困難的示例。

目前，分類器集成的研究主要集中在兩個方面：集成中個體分類器的生成和個體分類器輸出的結合。個體分類器結論結合常采用多數投票法，本文也采用多數投票法結合分類器結論。

2．3實驗結果

每個數據集隨機分成五組。其中一組作為測試集，其余四組的并集作為初始訓練集。對分類器集成的性能測試采用五倍交叉驗證方法。五組示例中，每一組都有一次作為測試集。實驗結果如表2所示（表中為五次測試結果的平均值）。

從表2可以看出，大多數情況下，Patridge和Yates^[8]提出的算法得到的集成比直接由過產生得到的分類器組成的集成有效。但這種算法不一定優于過產生的分類器中最好的分類器。采用本文提出的算法得到的分類器集成均優于過產生的分類器中最好的分類器，也優于Patridge和Yates提出的算法得到的集成。這是因為本文算法在盡可能采用性能最好的分類器前提下，盡可能采用具有差異性的分類器。

3結束語

分類器集成是模式識別和機器學習領域研究的熱點。分類器集成成功的關鍵是集成中個體分類器表現出的錯誤差異性，即不同分類器的錯誤分布在特征空間不同的區域。研究人員對集成中個體分類器的產生方法進行了多年探索研究，對分類器的錯誤差異性的量化還沒有一個有效的方法，這使得由已有方法產生的分類器集成中存在分類器冗余。因此，對集成中分類器進行進一步的選擇，以簡化分類器系統的設計是完全有必要的。本文提出一種基于聚類選擇的分類器集成方法，既考慮了分類器錯誤的分布特性，又考慮了分類器的分類識別能力。實驗結果說明這種算法是有效的。

本文提出的算法還存在以下問題，需要進一步研究：

a）本文算法首先需要劃分特征空間，盡管聚類方法是一種很好的方法，但把特征空間分成子區域的個數需要設定。對不同的數據集，它們在空間的分布有各自的特點。最優的區域個數如何確定需要進一步研究。

b）在本文算法中，特征空間各子區域需要推薦可以刪除的分類器數目。如果數目太大，有可能把精度高的分類器刪除；數目太小，又會刪除錯誤差異性較大的分類器。因此，各子區域備選刪除分類器數目需進一步研究。

c）多層感知器神經網絡具有不穩定性，即不同的訓練數據可能產生性能差別很大的神經網絡，這有助于生成錯誤差異較大的分類器。這是本文使用多層感知器神經網絡作為分類器的主要原因。但不同類型的神經網絡，特別是不同類型的分類器有可能更利于生成錯誤差異的集成。不同類型的分類器使用會使分類識別系統的設計過于復雜。在一個集成中，使用哪幾種類型的分類器更好需要研究。

d）集成中分類器的差異性的量化方法已有多種形式，但還沒有一種方法與集成性能之間存在直接聯系。因此，對差異性的量化表達式需要研究。

參考文獻：

［1］OPITZ D， MACLIN R. Popular ensemble methods: an empirical study[J]. Journal of Artificial Intelligence Research， 1999，11(1):169－198.

［2］DIETTERICH T G. Ensemble methods in machine learning [C]//Proc of the 1st International Workshop on Multiple Classifier Systems. New York: Springer－Verlag， 2000:1－15.

［3］PARTRIDGE D. Network generalization differences quantified[J]. Neural Networks， 1996，9(2):263-271.

［4］GIACINTO G， ROLI F. An approach to the automatic design of multiple classifier[J]. Pattern Recognition， 2001，22(1):25-33.

［5］AKSELA M， LAAKSONEN J T. Using diversity of errors for selecting members of a committee classifier[J]. Pattern Recognition， 2006，39(4):608-623.

［6］BROWN G， WYATT J， HARRIS R， et al. Diversity creation me－thods: a survey and categorisation[J]. Journal of Information Fusion， 2005，6(1):5-20.

［7］MacQUEEN J B. Some methods for classification and analysis of multi－variate observations[C]//Proc of the 5th Berkeley Symp on Mathematical Statistics and Probability. Berkeley:Univ of California， 1967:281-297.

［8］PATRIDGE D， YATES W B. Engineering multiversion neural－net systems[J]. Neural Computation， 1996，8(4):869-893.

［9］UCL Machine Learning Group. ELENA database[DB/OL]. [2006-08-01].http://www.dice.ucl.ac.be/mlg/DataBases/ELENA.

［10］MURPHY P M， AHA D W. UCI repository of machine learning database[DB/OL]. [2006-08-01].http://www.ics.uci.edu/~mlearn/MLRepository.html.

［11］BAUER E， KOHAVI R. An empirical comparison of voting classification algorithms: bagging， boosting and variants[J]. Machine Learning， 1999，36(1-2):105－139.

［12］DEMUTH H， BEALE M. Neural network toolbox for use with MATLAB[M]. Natick: The MathWorks Inc， 1998:53－106.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”