姜季春 王 蔚 令狐紅英

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

0 引言

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

1 多分類(lèi)器集成

1.1 背景

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

1.2 多分類(lèi)器集成的框架

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

圖1 多分類(lèi)器集成框架圖

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

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

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

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

1.3 單分類(lèi)器的設(shè)計(jì)

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

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

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

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

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

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

1.4 單分類(lèi)器的集成方式

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

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

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

2 多分類(lèi)器動(dòng)態(tài)集成技術(shù)

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

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

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

（2）針對(duì)不同的樣本，各個(gè)分類(lèi)器的分類(lèi)效果是有差別的；

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

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

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

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

如圖2所示為多分類(lèi)器集成的框架的三個(gè)主要部分：

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

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

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

圖2 多分類(lèi)器動(dòng)態(tài)集成的框架

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

為了在各個(gè)應(yīng)用領(lǐng)域中更好地滿(mǎn)足人們對(duì)分類(lèi)性能的需求，由于分類(lèi)器動(dòng)態(tài)集成技術(shù)更加靈活、更具針對(duì)性，并且能夠取得更好的分類(lèi)效果，因此成為了機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域的一個(gè)研究熱點(diǎn)，分析和研究分類(lèi)器動(dòng)態(tài)集成技術(shù)具有較高的理論價(jià)值和應(yīng)用價(jià)值。本文介紹了分類(lèi)器動(dò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］唐春生,金以慧.基于全信息矩陣的多分類(lèi)器集成方法[J].軟件學(xué)報(bào),2003(6)：1103-1109.

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