淺談多分類器動態集成技術

姜季春 王 蔚 令狐紅英

（1.貴州大學計算機科學與技術學院，貴州 貴陽 550025；2.貴州燃氣〈集團〉有限責任公司，貴州 貴陽 550000；3.貴州師范學院，貴州 貴陽 550001）

0 引言

分類技術是數據挖掘、機器學習及模式識別中一個重要的研究領域，已在生物認證、手寫體識別和文字識別、醫療診斷、圖像識別、網絡安全入侵檢測等眾多領域得到廣泛應用。分類的準確性是衡量分類器性能的最重要指標之一，集成分類器的目的在于獲得高性能的分類結果。分類器集成主要是通過對多個單分類器進行組合來提高分類性能。盡管傳統的集成分類技術已經應用到很多領域，但隨著科技的發展，人們對應用結果有了更高的要求。這就意味著人們希望通過對傳統的靜態集成分類技術的改進，得到滿足應用領域深層次要求的高性能的集成算法。于是，多分類器動態集成技術應運而生，研究分類器集成技術以提高集成分類的性能指標，已成為眾多領域的研究熱點。

1 多分類器集成

1.1 背景

分類器集成利用單分類器的互補功能，獲得比單個分類器更好的分類性能。按照是否針對待分類樣本的具體特征來自適應地選取分類器，得到靜態集成(Static Ensemble)和動態集成(Dynamic Ensemble)兩種多分類器集成方法。多分類器靜態集成方法在訓練過程中就將最終識別模型的分類器權重和數目都確定下來，就這意味著在分類預測的過程中所有待分類樣本均使用相同的識別模型。和靜態集成方法相比較，分類器動態集成方法在預測過程中會根據待分類樣本的具體特征來自適應地選取適合的分類器進行集成，這種特性說明動態集成具有更好的針對性和靈活性。另外，分類器動態集成受抽取樣本的影響小于靜態集成，可以顯著提高分類系統的泛化能力，進而有效地保證了分類的精度。

1.2 多分類器集成的框架

多分類器集成系統雖然可以有效提高分類的精度，但是構造多分類器系統確是一個復雜的事情。由于目前對于多分類器集成技術的理論分析還不盡完善，在應用的過程中主要依賴于學者們的實踐經驗。通常來說，多分類器集成問題包含分類器集合的構造和組合方法兩大部分。分類器集合構造部分用于生成多個分類器，組合方法部分則是通過某種方法根據單個分類器的預測情況形成最終的判決，其框架如圖所示[1]。

圖1 多分類器集成框架圖

在分類器集成系統中，組成識別模型的單個分類器的輸出形式要受到所使用的集成方法的影響。一般來說，單個分類器有決策級輸出、排序級輸出和度量級輸出三種主要的輸出形式。通常而言，集成的信息量和單分類器的輸出等級有關。單分類器的輸出級別越高，所集成的信息就越豐富，理論上可以獲得的分類結果就越好。單分類器的三種輸出形式如下：

（1）決策級輸出：沒有其他附加的信息，輸出結果僅用于單純的分類決策，如身份識別后輸出接受和拒絕兩種結果；

（2）排序級輸出：通常用于目標類別數目眾多的情況，且輸出的類別按可能性由大到小進行排序；

（3）度量級輸出：輸出的結果為概率、信度、距離等度量值。

1.3 單分類器的設計

在單分類器的設計中，一些方法考慮顯示地實現分類器的多樣性，另一些方法則是隱含地實現了分類器的多樣性。將已知的單分類器設計方法歸納如下：

（1）在同一個訓練集中生成一組不同類型的單分類器[2]。比如使用決策樹、神經網絡、貝葉斯分類算法訓練單分類器，將這些類型不同的單分類器作為集成所用的成員分類器。這組分類器在分類的側重點和效果上存在差別，并且所得分類結果的輸出表示方法也不相同，因此在使用這些單分類器集成分類結果的時候需要進行調整。

（2）從初始的訓練樣本中抽取得到不同的訓練集，訓練多個類型相同的單分類器[3-4]。這種方法通過可重復的隨機抽樣，根據樣本分類的難易程度分別賦予不同的權重得到多個訓練集，從而訓練出一組具有多樣性的單分類器。

（3）根據樣本的屬性特征劃分不同的訓練樣本子集生成多個單分類器，實現分類器的多樣性[5]。將一個大的特征向量空間劃分為若干較小的特征空間，分別構建一個單分類器，再將這些單分類器集成到一起。這種方法比在整個特征空間中訓練一個分類器獲得更高的時間、空間效率。

（4）通過調整訓練樣本的標記屬性得到不同的訓練集，分別訓練得到單分類器[6]。這種方法不僅改變了訓練樣本的標記屬性，同時也增加了訓練樣本標記屬性的噪聲，從而實現分類器之間的多樣性。

（5）合并類別標號。對于類別數目較大的訓練集，隨機將多個類別的樣本劃為兩個子集，并將同一子集中的訓練樣本歸為一類。對于合并后的兩類訓練集用擬合算法訓練單分類器。這種方法通過多次重復的隨機類別合并得到成員分類器。

1.4 單分類器的集成方式

在訓練得到一組單分類器之后，即可進行單分類器的輸出集成，以獲得待分類樣本的目標類別。單分類器的集成分為全部集成和部分集成兩種類別：

（1）直接進行集成，即是集成全部單分類器。如果通過訓練集生成的單分類器分類精度和相互之間的多樣性較高，則可以直接采取某種集成方法來融合各個單分類器的輸出結果。

（2）進行選擇性集成。許多集成方法都選擇使用大量單分類以得到較高的分類性能，但是這種做法會帶來一些問題，例如增加計算和存儲的開銷；隨著單分類器規模的增加，難以保證分類器之間的差異度等等。有研究證明只選擇一部分適合的單分類器同樣可以取得集成所有分類器的分類性能，甚至得到更好的分類效果。這類研究方法的主要思想是首先生成一組初始單分類器序列，然后根據一定的準則從中選擇合適的單分類器進行集成。

2 多分類器動態集成技術

2.1 動態集成技術的原理

動態集成的原理是利用不同的分類模型的錯誤分布信息來指導分類器的集成過程，即是對于給定的一個待分類樣本，盡可能地選擇那些能夠將其正確分類的分類器進行分類。其原理為不同類型的分類器具有不同的錯誤分布，而對于同種類型的分類器來說，錯誤分布往往集中于某一特定的區域中。唐春生和金以慧[7]在研究中給出了動態集成技術的4個基本出發點：

（1）在樣本空間中，不同的樣本處于不同的區域，并且具有不同的特征；

（2）針對不同的樣本，各個分類器的分類效果是有差別的；

（3）在樣本空間的不同區域，同一個分類器的分類性能會有所變化；

（4）分類器對最終判決具有一定的支持作用，且分類器輸出的不同待測類別與實際類別之間存在一定的相似性。

根據以上內容總結得出分類器動態集成的思想：分析對于不同待分類樣本所在區域上的各個單分類器的性能，使其自適應地選擇一組分類器，最后利用某些特定的組合方法集成判決分類結果。分類器動態集成方法考慮了各個單分類器的特性和待分類樣本的自身特征，具有比靜態集成方法更好的針對性和靈活性。通常來說，動態集成方法能夠獲得比靜態集成方法更好的分類效果。

2.2 多分類器動態集成的框架和方法

如圖2所示為多分類器集成的框架的三個主要部分：

（1）在訓練集TS中訓練生成一組單分類C；

（2）使用訓練集TS或測試集VS來生成能力區域RoC(Region of Competence)；

（3）得到各個單分類器在能力區域內的性能，這一過程需要根據待分類樣本Xt的自身特征來確定。隨后自適應地選擇部分分類器或者指定分類器權重用于最終的動態集成分類。

圖2 多分類器動態集成的框架

要實現分類器動態集成，關鍵在于如何構建能力區域和選擇何種集成方法[8]。能力區域的構建需要選擇出一組能夠反映單分類器預測性能的樣本集，單分類器在樣本中訓練得到的分類器必須具備良好的分類效果。

總結一下目前流行的能力區域構建方法：

（1）基于KNN的方法。該方法的核心思想是假如一個樣本在特征空間里的k個最相鄰的大多數樣本都屬于某一個類別，則該樣本也被判為這個類別，并具有這個類別上樣本的特性。KNN方法經常使用歐幾里德距離、曼哈頓距離等來求解，在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來判決待分樣本所屬的類別，如DCS-LA（Hard Selection）方法，DCS-LA（Soft Selection）方法，KNORA-E 方法等。

（2）基于不同數據集的方法。該方法是通過利用一定的技術得到不同的能力區域，用于構建單分類器，如AO-DCS算法等。

（3）基于聚類的方法。該方法采用聚類算法產生規定數目的訓練樣本集，在分類階段通過計算待分類樣本和樣本集聚類中心的距離得到距離最近的一組訓練樣本進行分類。如CS（Clustering and Selection）方法，M3CS方法等。

集成方法的選擇也是分類器動態集成中的重要環節之一。流行的集成方式有：

（1）動態選擇方法。該方法的思想是通過對待分類樣本的特征分析從單分類器序列中選擇部分性能優良的單分類器實現集成分類。

（2）動態投票方法。該方法的思想是在分類迭代過程中根據待分類樣本的特征為各個單分類器動態分配權重，然后執行加權集成分類。

（3）結合動態選擇和動態投票的混合集成方法。該方法集合了前兩種方法的優勢，先根據待分類樣本特征選擇單分類器序列，再為其動態分配權重，最后執行集成判決。

3 多分類器動態集成技術的不足

和靜態集成分類方法相比，分類器動態集成方法在預測時可以動態地、實時地組合單分類器或者為其分配權重，獲得更好地分類性能。但是動態集成本身存在一些缺點，在應用過程中需要注意。比如，動態集成過程中需要調用其他方法，如特征選擇、聚類分析、KNN方法等；由于待分類樣本和訓練集分布的差異引起分類性能顯著下降；對于不同的待分類樣本進行分類器序列的優選，造成算法時間復雜度的增加；還有部分動態集成方法，為了追求優良的局部性能，需要一些特定的訓練集，當訓練集規模不足的情況下就會影響分類性能。

4 結束語

為了在各個應用領域中更好地滿足人們對分類性能的需求，由于分類器動態集成技術更加靈活、更具針對性，并且能夠取得更好的分類效果，因此成為了機器學習和數據挖掘等領域的一個研究熱點，分析和研究分類器動態集成技術具有較高的理論價值和應用價值。本文介紹了分類器動態集成技術的原理、框架和方法，總結了該技術在應用中存在的一些不足之處，為后繼的應用研究提供了理論參考。

［1］Jiawei Han,Micheline Kamber.數據挖掘概念與技術[M].北京：機械工業出版社,2004.

［2］W.B.Langdon，S.J.Barrett，B.F.Buxton.Combining decision trees and neural networks for drug discovery[C].Genetic Programming Proceedings of the 5th European Conference，EuroGP 2002，Kinsale，Ircland,2002,60-70.

［3］Y.Freund，R.E.Schapire.Experiments withane wboosting algorithm[C].Proceedings of the13th International Conferenceon Machine Learning，Morgan Kau fmann,1996,148-156.

［4］Loris Nanni，Alessandra Lumini.Fuzzy Bagging：A novel ensemble of classifiers[J].Pattern Recognition,2006（39）：488-490.

［5］YongSeog Kima，W.Nick Streetb，Filippo Mencaer.Optimal ensemble construction viameta-evolutionary ensembles[J].Expert Systems with Applications,2006(30)：705-714.

［6］Gonzalo Martinez-Munoz，Alberto Suarez.Switching class labels to generate classification ensembles[J].Pattern Recognition，2005，（38）：1482-1494.

［7］唐春生,金以慧.基于全信息矩陣的多分類器集成方法[J].軟件學報,2003(6)：1103-1109.

［8］歐吉順.多分類器動態集成技術研究[D].江蘇：江蘇大學計算機科學與通信工程學院,2010.