淺談多分類器動態(tài)集成技術(shù)

姜季春 王 蔚 令狐紅英

（1.貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2.貴州燃?xì)狻醇瘓F(tuán)〉有限責(zé)任公司，貴州 貴陽 550000；3.貴州師范學(xué)院，貴州 貴陽 550001）

0 引言

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

1 多分類器集成

1.1 背景

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

1.2 多分類器集成的框架

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

圖1 多分類器集成框架圖

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

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

（2）排序級輸出：通常用于目標(biāo)類別數(shù)目眾多的情況，且輸出的類別按可能性由大到小進(jìn)行排序；

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

1.3 單分類器的設(shè)計

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

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

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

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

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

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

1.4 單分類器的集成方式

在訓(xùn)練得到一組單分類器之后，即可進(jìn)行單分類器的輸出集成，以獲得待分類樣本的目標(biāo)類別。單分類器的集成分為全部集成和部分集成兩種類別：

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

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

2 多分類器動態(tài)集成技術(shù)

2.1 動態(tài)集成技術(shù)的原理

動態(tài)集成的原理是利用不同的分類模型的錯誤分布信息來指導(dǎo)分類器的集成過程，即是對于給定的一個待分類樣本，盡可能地選擇那些能夠?qū)⑵湔_分類的分類器進(jìn)行分類。其原理為不同類型的分類器具有不同的錯誤分布，而對于同種類型的分類器來說，錯誤分布往往集中于某一特定的區(qū)域中。唐春生和金以慧[7]在研究中給出了動態(tài)集成技術(shù)的4個基本出發(fā)點(diǎn)：

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

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

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

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

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

2.2 多分類器動態(tài)集成的框架和方法

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

（1）在訓(xùn)練集TS中訓(xùn)練生成一組單分類C；

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

（3）得到各個單分類器在能力區(qū)域內(nèi)的性能，這一過程需要根據(jù)待分類樣本Xt的自身特征來確定。隨后自適應(yīng)地選擇部分分類器或者指定分類器權(quán)重用于最終的動態(tài)集成分類。

圖2 多分類器動態(tài)集成的框架

要實(shí)現(xiàn)分類器動態(tài)集成，關(guān)鍵在于如何構(gòu)建能力區(qū)域和選擇何種集成方法[8]。能力區(qū)域的構(gòu)建需要選擇出一組能夠反映單分類器預(yù)測性能的樣本集，單分類器在樣本中訓(xùn)練得到的分類器必須具備良好的分類效果。

總結(jié)一下目前流行的能力區(qū)域構(gòu)建方法：

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

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

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

集成方法的選擇也是分類器動態(tài)集成中的重要環(huán)節(jié)之一。流行的集成方式有：

（1）動態(tài)選擇方法。該方法的思想是通過對待分類樣本的特征分析從單分類器序列中選擇部分性能優(yōu)良的單分類器實(shí)現(xiàn)集成分類。

（2）動態(tài)投票方法。該方法的思想是在分類迭代過程中根據(jù)待分類樣本的特征為各個單分類器動態(tài)分配權(quán)重，然后執(zhí)行加權(quán)集成分類。

（3）結(jié)合動態(tài)選擇和動態(tài)投票的混合集成方法。該方法集合了前兩種方法的優(yōu)勢，先根據(jù)待分類樣本特征選擇單分類器序列，再為其動態(tài)分配權(quán)重，最后執(zhí)行集成判決。

3 多分類器動態(tài)集成技術(shù)的不足

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

4 結(jié)束語

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

［1］Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社,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，F(xiàn)ilippo 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].軟件學(xué)報,2003(6)：1103-1109.

［8］歐吉順.多分類器動態(tài)集成技術(shù)研究[D].江蘇：江蘇大學(xué)計算機(jī)科學(xué)與通信工程學(xué)院,2010.