采用互補信息熵的分類器集成差異性度量方法

趙軍陽,韓崇昭,韓德強,張春霞

(1.第二炮兵工程大學202教研室, 710025, 西安;2.西安交通大學電子與信息工程學院, 710049, 西安;3.西安交通大學數學與統計學院, 710049, 西安)

?

采用互補信息熵的分類器集成差異性度量方法

趙軍陽1,2,韓崇昭2,韓德強2,張春霞3

(1.第二炮兵工程大學202教研室, 710025, 西安;2.西安交通大學電子與信息工程學院, 710049, 西安;3.西安交通大學數學與統計學院, 710049, 西安)

針對多分類器系統差異性評價中無法直接處理模糊數據的問題,提出了一種采用互補信息熵的分類器集成差異性度量(CIE)方法。首先利用訓練數據生成一系列基分類器,并對測試數據進行分類,將分類結果依次組合生成分類數據空間;然后采用模糊關系條件下的互補信息熵度量分類數據空間蘊含的不確定信息量,據此信息量判斷基分類器間的差異性;最后以加入基分類器后數據空間差異性增加為選擇分類器的基本準則,構建集成分類器系統,用于驗證CIE差異性度量與集成分類精度之間的關系。實驗結果表明,與Q統計方法相比,利用CIE方法進行分類器集成,平均集成分類精度提高了2.03%,分類器系統集成規模降低約17%,而且提高了集成系統處理多樣化數據的能力。

分類器集成;差異性;互補信息熵;模糊關系

分類器集成是指針對某一問題,將一系列基分類器進行組合,來提高分類的精度和泛化性能的方法。目前,多分類器集成已得到廣泛而深入的研究,并成為機器學習、模式識別等領域的主要研究方向之一。很顯然,如果進行組合的是相同且無差異的分類器,集成系統并不能提高整體分類效果。因此,要提高多分類器系統的性能,基分類器必須具有一定的差異性,即要求B分類器能將A分類器錯誤分類的樣本重新劃分到正確的類別。

分類器差異性的研究主要涉及分類器差異性生成模式、差異性度量方法、差異性與集成分類性能關系以及如何利用差異性度量優化分類器集成系統等方面的研究[1-2]。其中,分類器差異性生成模式的研究是提高集成系統性能的基礎[3],也是眾多文獻的研究熱點。差異性的獲得可通過采用不同類型的分類器、設置分類器的不同參數配置和采用不同的訓練數據集來實現[4]。如何度量分類器間的差異性是研究者需要關注的另一個重要問題。分類器差異性的正確度量和分析對于設計性能優良的分類器系統至關重要。目前,國內外學者已經提出一些度量分類器差異性的方法,以期對分類器系統差異特性進行統計分析[5-9],如Kuncheva總結的Q統計、雙錯度量和熵度量等[5],Windeatt提出的基于模式的度量方法[6];或者指導分類器集成系統的優化設計與實現[10-14],以提高分類器的集成性能?，F有的一些方法雖然能在一定程度上表示分類器之間的差異性,但主要是從分類器正確分類和錯誤分類的一致性角度出發進行定義,必須根據標準類別信息首先對分類器輸出結果的正確性進行判別,無法直接度量分類器本身蘊含的分類信息。為此本文從信息熵角度出發研究如何直接度量分類器的差異性,提出一種基于互補信息熵的分類器差異性度量(CIE)方法,根據不同分類器所蘊含不確定信息量的差別來實現分類器的差異性評價,并分析差異性度量方法與系統集成性能之間的聯系。數據實驗表明,本文方法能有效度量分類器差異性,在降低分類器集成規模的同時,提高或保持集成系統的集成分類精度。

1 常用的差異性度量方法

目前比較常用的差異性度量方法主要可以分為兩類:成對度量方法[5]和非成對度量方法[15]。

1.1 成對度量方法

成對差異度量方法首先計算分類器系統中每一對分類器之間的差異性度量值,L個分類器對應L(L-1)/2對差異值,然后對各差異值求取平均值得到系統的差異度。以下介紹幾種常見的成對度量方法。

(1)相關系數(Correlation Coefficient,ρ)

ρi,j=(N11N00-N01N10)/[((N11+N10)(N01+

N00)(N11+N01)(N10+N00))1/2]

(1)

式中:N01表示分類器Di和Dj的聯合分類輸出概率,0表示Di分類錯誤,1表示Di分類正確;其余定義類似。

(2)Q統計(Q-statistic,Q)

(2)

(3)不一致度量(Disagreement Measure,Dis)

(3)

(4)雙錯度量(Double-Fault Measure,DDF)

(4)

1.2 非成對度量方法

非成對差異性度量方法不強調分類器兩兩之間的關系,而是對整個分類器集合進行計算得到系統的差異度。

(1)熵度量(Entropy,E)

(5)

式中:l(xi)表示在一組L個分類器中,將樣本xi正確分類的分類器個數;N為樣本數。

(2)KW方差(Kohavi-Wolpert variance,DKW)

(6)

(3)Kappa度量(Interrater agreement,κ)

(7)

(4)難點度量(Difficulty,θ)

θ=var(Z)

(8)

式中:Z表示對于隨機給定的輸入x,分類正確的分類器在所有集成分類器中的比率。

(5)廣義差異性度量(Generalised Diversity,DG)

(9)

式中:p(1)表示1個分類器的出錯概率;p(2)表示2個分類器的出錯概率。

(6)一致錯誤差異性度量(Coincident Failure Diveristy,DCF)

(10)

式中:p0表示所有個體部分類正確;pi表示L個分類器中有i個得出錯誤分類結果的概率。

2 互補信息熵差異性度量與集成

2.1 模糊近似空間中的互補信息熵

為了度量數據空間蘊含的不確定信息,目前已提出多種信息熵度量方法,但無論是Shannon信息熵[16]還是梁吉業提出的粗糙集中的信息熵模型[17]均要求數據空間滿足一定的等價關系,只能處理離散數據。然而,實際的數據未必存在明確的邊界區分,需利用連續特征函數進行描述,通過模糊隸屬函數進行處理。為了適應任意模糊關系下的信息度量,文獻[18]對Shannon熵進行改進,提出了模糊關系下的信息熵模型;作者則在文獻[19]中考慮類別劃分的補集,提出了任意模糊關系下的互補信息熵模型,可以直接處理連續或模糊數據。

定義1 設U={x1,x2,…,xn}為有限非空論域,R是U上的任意模糊關系,則模糊近似空間(U,R)的互補信息熵[19]定義為

(11)

2.2 互補信息熵差異性度量方法

上節介紹的差異性度量方法不僅要求分類器的輸出結果為0/1模式,而且需要預先判斷分類器輸出的正確性,無法直接度量分類器輸出信息,不能適應連續或模糊數據的集成處理。互補信息熵則不僅能應用于模糊信息系統的信息處理,而且無需預先離散化,也可以度量分類器系統所蘊含的信息量。為此,本文將其用于分析分類器的差異性,提出一種采用互補信息熵的差異性度量方法。

假設分類器系統中基分類器ci的分類輸出結果為Oi={oi1,oi2,…,oiN},將各基分類器的輸出組合起來構成一個新的分類數據空間,即U={oij|i=1,…,L;j=1,…,N},其中,L表示分類器個數,N表示樣本個數,每一個分類器的輸出即為數據空間U中的一個數據對象,各個分類器間的差異性越大,則蘊含的互補信息熵也越大,由此得到一種新的差異性度量方法。

定義2 設O={o1,o2,…,oL}為有限非空論域,R是O上的任意模糊關系,則基于互補信息熵的差異性度量方法(Complement Information Entropy, CIE)定義為

(12)

式中:|[oi]R|表示在第i個分類器輸出的各樣本對象結果在模糊關系R下的勢。

定義2基于不同分類器間的相似關系,綜合度量基分類器對各個原始樣本數據的分類效果及其互補信息,給出基分類器集合的差異性,省略了對分類器輸出結果的正確性判別過程,具有更好的適應性。DCIE值越大,則差異性越大,可用于指導基分類器的評價和選擇。為此,本文依據互補信息熵差異性度量方法提出增量式的基分類器差異重要性評價方法,其定義如下。

定義3 給定一個基分類器集成系統(O,C),O為有限非空論域,C為所有分類器集合,B?C,?ci∈C-B,則分類器ci關于分類器集合B中的差異重要性定義為

S(ci,B)=DCIE(B∪{ci})-DCIE(B)

(13)

該定義以基分類器集成系統差異性增加為基本準則。若加入一個基分類器后,集成系統的差異性增加,則保留該分類器;若集成系統的差異性降低,則舍去該分類器。基于該準則可實現基分類器的自動選擇,有利于降低集成規模。

2.3 基于互補信息熵差異重要性評價的選擇性集成方法

為了驗證CIE差異性度量方法與集成分類精度之間的關系,設計了一種基于互補信息熵分類器差異性評價的集成方法(簡稱CIE集成方法),即首先將原始數據集劃分為訓練集和測試集,然后采用Bootstrap采樣方法在訓練集上生成N個數據子集,再基于這些數據子集對基分類器進行訓練得到每個數據對象的分類輸出結果。在基分類器訓練結束后,基于定義3評價當前分類器對基分類器集合的重要程度。如果重要性大于0,則保留該分類器;若重要性小于等于0,則舍去該分類器,繼續評價下一個分類器。將選擇的基分類器輸出結果通過多數投票法進行組合,可得到最終的分類結果。

CIE集成方法步驟如下。

步驟1 初始條件。令U←有限數據集,C←初始空分類集成系統。

步驟2 生成訓練子集。利用Bootstrap采樣方法生成N個訓練子集。

步驟3 訓練基分類器。在每個訓練子集上訓練單一分類器,得到N個分類器集合{Ci}i=1,…,N。

步驟4 基分類器性能評價與選擇。根據式(13)分類器差異重要性評價結果自動選擇分類器加入集成系統C。

步驟5 生成分類器集成系統。將加入的各基分類器組合得到最終的分類器集成系統C*,利用多數投票方法組合輸出結果。

步驟6 集成系統分類精度評價?；?0折交叉驗證方法評價集成系統C*的分類精度。

CIE集成方法在運行過程中無需重復進行類別標記,利用差異性評價方法對在樣本采樣后的訓練子集中生成的基分類器進行選擇,不僅能夠提高分類器間的差異性,也有助于降低分類器系統的集成規模和復雜度,提高系統的識別效果。

3 數據實驗分析

3.1 實驗數據

本文利用機器學習領域常用的加州大學Irvine分校UCI(University of California Irvine)數據庫[20]中的12種數據集對CIE集成方法的性能進行驗證實驗,涉及醫學診斷、客戶分類、污水處理、車輛分析和葡萄酒識別等方面,詳細信息如表1所示。12種數據集的類別數為2～13類,特征值均為數值類型,特征既有連續型,也有離散型,特征維數在4～56之間,樣本數在32到1 000之間。

表1 UCI實驗數據

3.2 CIE集成方法分類性能比較實驗

在開始算法性能實驗前,需首先設置基分類器的訓練個數N,各方法的分類精度為P。從表1中隨機選取Wbc、Cre、Wat和Wdbc 4個數據集,并選擇常用的決策樹(decision tree, DT)和支持向量機(support vector machine, SVM)作為基分類器,其中SVM核函數采用徑向基函數。在此基礎上,分析集成系統訓練的基分類器數量對CIE方法集成分類性能的影響,實驗結果如圖1所示。

(a)WBC (b)Cre

(c)Wat (d)Wdbc圖1 不同基分類器數對算法分類性能的影響

由圖1可知,隨著分類器數量的增加,集成分類精度存在先升后穩的趨勢,甚至還會降低,表明分類器數量并非越多越好,滿足集成系統的選擇需要即可。為提高集成系統的訓練效率,以下統一設置N=10。

進行CIE集成方法的分類性能驗證實驗,并將結果與Bagging(Bag)、Adaboost(Ada)和RSM等主要集成算法進行分析比較。首先將數據集樣本隨機劃分為20份,循環將其中9份組合作為訓練集,剩余1份作為測試集,并在每個循環中生成10個基分類器作為候選集合,然后根據重要性評價方法自動選擇合適的分類器組合得到分類器集成系統。Bagging、Adaboost和RSM等集成算法采用新西蘭Waikato大學開發的WEKA機器學習軟件對數據集進行分類實驗。所有算法的參數設置均為WEKA的默認設置。

(a)BC (b)WBC

(c)Cre (d)Cle

(e)Der (f)LC

(g)Iris (h)Veh

(i)Wat (j)Win

(k)Ion (l)Wdbc圖2 以決策樹為基分類器時幾種集成算法的分類性能比較

(a)BC (b)WBC

(c)Cre (d)Cle

(e)Der (f)LC

(g)Iris (h)Veh

(i)Wat (j)Win

圖2和圖3分別為采用決策樹和SVM為基分類器時,上述方法在這些數據集上的分類性能比較結果。從圖中結果可以得出:

(k)Ion (l)Wdbc圖3 以SVM為基分類器時幾種集成算法的分類性能比較

(1)CIE集成方法的分類性能在多數數據集上接近或超過Bagging、Adaboost和RSM算法,表明以差異性評價作為選擇分類器的標準是可行的;

(2)當采用決策樹為基分類器時,CIE集成方法在半數數據集上獲得最優性能,而當采用SVM為基分類器時,CIE集成方法在8個數據集上性能表現突出,在Cle、LC、Iris、Wat和Wdbc這5個數據集上表現更為明顯,如在Cle上的分類精度相比Bagging算法提高了38.5%。

3.3 CIE差異性度量方法性能分析實驗

在CIE集成方法框架下,為了比較CIE度量方法與其他差異性度量方法的性能差異,引入Q統計、熵度量、KW方差和雙錯度量等常用方法替換CIE差異性度量方法,并與原始CIE集成方法進行比較。圖4和圖5是分別以決策樹和SVM為基分類器時的精度對比結果。對圖4、圖5的結果分析可得如下結果。

圖4 以決策樹為基分類器時幾種差異性度量方法的集成分類性能比較

圖5 以SVM為基分類器時幾種差異性度量方法的集成分類性能比較

(1)采用決策樹作為基分類器時,基于CIE度量集成后的系統分類精度與基于其他4種差異性度量方法相比,在6個數據集上獲得最佳分類效果;采用SVM作為基分類器時也在4個數據集上獲得最高精度;在其余數據集上的分類性能則與其他方法相近,表明CIE差異性度量方法可有效應用于分類器集成系統的差異性評價,并指導分類器集成系統設計和優化。

(2)通過對圖4和圖5實驗結果的統計分析可以看出,CIE度量方法綜合性能最優,在不同基分類器條件下均取得了最高平均分類精度,如表2所示。其次是熵度量和雙錯度量方法。熵度量和雙錯度量在文獻[5]中也指出其具有較好的差異性度量能力,整體性能表現要優于Q統計和KW方差。

表2 幾種差異性度量方法下CIE集成方法的

圖6 以決策樹為基分類器時幾種差異性度量方法集成的分類器個數比較

圖7 以SVM為基分類器時幾種差異性度量方法集成的分類器數比較

圖6和圖7給出了本節實驗過程中,基于上述差異性度量方法的集成系統最終選擇的基分類器個數。由圖中可知,無論采用何種差異性度量方法,多分類器系統集成的平均分類器個數在2.1～4.0之間。與傳統上多達幾十甚至上百個分類器的復雜集成系統相比,CIE方法可在選擇少量基分類器的同時,獲得較優的分類性能,平均比Q統計方法生成的集成系統規模降低17%左右。

通過上述實驗,基于CIE差異性評價的集成算法具有在選擇較少基分類器的基礎上,保持或提高分類器系統性能的能力。互補信息熵差異性度量方法在度量多分類器系統差異性方面是有效的,在分類器集成過程中的應用也是可行的。

4 結 論

為了滿足直接度量分類器差異性的多樣性需求,提高分類數據處理的能力,本文提出了一種互補信息熵差異性度量方法,并利用分類器重要性評價選擇基分類器進行集成。該方法能夠直接處理分類器的輸出結果,不受0/1模式限制;此外,通過對分類器系統信息量的直接度量,省略了對分類結果正確性的判別,適用于半標記和未標記數據的處理。實驗結果驗證了本文方法在分類器集成應用方面的有效性和可行性。

需要指出的是,CIE集成方法在分類器選擇過程中僅采用了差異性指標,雖然有效降低了系統的集成規模,但未考慮與集成精度的平衡問題,對系統的泛化能力可能會有一定影響。目前在如何實現分類器系統差異性和集成精度的有效平衡以及對系統的影響方面尚缺乏理論依據,下一步工作將在集成系統的優化方面進行研究和探索。

[1] KUNCHEVA L I, SKURICHINA M, DUIN R P W. An experimental study on diversity for bagging and boosting with linear classifiers [J]. Information Fusion, 2002, 3(4): 245-258.

[2] BROWN G, KUNCHEVA L I. “Good” and “bad” diversity in majority vote ensembles [C]∥Proceedings of International Conference on Multiple Classifier Systems. Berlin, Germany: Springer, 2010: 124-133.

[3] 張宏達, 王曉丹, 韓鈞, 等. 分類器集成差異性研究 [J]. 系統工程與電子技術, 2009, 31(12): 307-3012. ZHANG Hongda, WANG Xiaodan, HAN Jun, et al. Survey of diversity researches on classifier ensembles [J]. Systems Engineering and Electronics, 2009, 31(12): 3007-3012.

[4] NASCIMENTO D, COELHO A, CANUTO A. Integrating complementary techniques for promoting diversity in classifier ensembles: a systematic study [J]. Neurocomputing, 2014, 138: 347-357.

[5] KUNCHEVA L I, WHITAKER C J. Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy [J]. Machine Learning, 2003, 51: 181-207.

[6] WINDEATT T. Diversity measures for multiple classifier system analysis and design [J]. Information Fusion, 2005, 6(1): 21-36.

[7] HAGHIGHI M S, VAHEDIAN A, YAZDI H S. Creating and measuring diversity in multiple classifier systems using support vector data description [J]. Applied Soft Computing, 2011, 11(8): 4931-4942.

[8] KRAWCZYK B, WOZNIAK M. Diversity measures for one-class classifier ensembles [J]. Neurocomputing, 2004, 126: 36-44.

[9] YIN X C, HUANG K Z, HAO H W, et al. A novel classifier ensemble method with sparsity and diversity [J]. Neurocomputing, 2014, 134: 214-221.

[10]BI Y X. The impact of diversity on the accuracy of evidential classifier ensembles [J]. International Journal of Approximate Reasoning, 2012, 53(4): 584-607.

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

[12]RASHEED S, STASHUK D W, KAMEL M S. Diversity-based combination of non-parametric classifiers for EMG signal decomposition [J]. Pattern Anal Applic, 2008, 11(3/4): 385-408.

[13]楊春, 殷緒成, 郝紅衛, 等. 基于差異性的分類器集成有效性分析及優化集成 [J]. 自動化學報, 2014, 40(4): 660-674. YANG Chun, YIN Xucheng, HAO Hongwei, et al. Classifier ensemble with diversity: effectiveness analysis and ensemble optimization [J]. Acta Automatica Sinica, 2014, 40(4): 660-674.

[14]楊長盛, 陶亮, 曹振田, 等. 基于成對差異性度量的選擇性集成方法 [J]. 模式識別與人工智能, 2010, 23(4): 565-571. YANG Changsheng, TAO Liang, CAO Zhentian, et al. Pairwise diversity measures based selective ensemble method [J]. PR&AI, 2010, 23(4): 565-571.

[15]谷雨. 分類器集成中的多樣性度量 [J]. 云南民族大學學報: 自然科學版, 2012, 21(1): 59-65. GU Yu. Measure diversity classifier ensemble [J]. Journal of Yunnan National University: Natural Science, 2012, 21(1): 59-65.

[16]LIU W Y, WU Z H, PAN G. An entropy-based diversity measure for classifier combining and its application to face classifier ensemble thinning [C]∥Proceedings of International Conference on Sinobiometrics. Berlin, Germany: Springer, 2004: 118-124.

[17]LIANG J, CHIN K, DANG C. A new method for measuring uncertainty and fuzziness in rough set theory [J]. International Journal of General Systems, 2002, 31(4): 331-342.

[18]YU D, HU Q, WU C. Uncertainty measures for fuzzy relations and their applications [J]. Applied Soft Computing, 2007, 7(3): 1135-1143.

[19]ZHAO J, ZHANG Z, HAN C, et al. Complement information entropy for uncertainty measure in fuzzy rough set and its application [J]. Soft Computing, 2015, 19(7): 1997-2010.

[20]BLAKE C L. MERZ C L. UCI repository of machine learning databases [EB/OL]. (2007-10-12) [2015-05-08]. http:∥www.ics.uci.edu/～mlearn/MLRepository.html.

[本刊相關文獻鏈接]

蘭景宏,劉勝利,吳雙,等.用于木馬流量檢測的集成分類模型.2015,49(8):84-89.[doi:10.7652/xjtuxb201508014]

喻明讓,張英杰,陳琨,等.考慮調整時間的作業車間調度與預防性維修集成方法.2015,49(6):16-21.[doi:10.7652/xjtuxb201506003]

楊宏暉,王蕓,孫進才,等.融合樣本選擇與特征選擇的AdaBoost支持向量機集成算法.2014,48(12):63-68.[doi:10.7652/xjtuxb201412010]

王羨慧,覃征,張選平,等.采用仿射傳播的聚類集成算法.2011,45(8):1-6.[doi:10.7652/xjtuxb201108001]

馬超,陳西宏,徐宇亮,等.廣義鄰域粗集下的集成特征選擇及其選擇性集成算法.2011,45(6):34-39.[doi:10.7652/xjtuxb201106006]

(編輯 劉楊)

A Novel Measure Method for Diversity of Classifier Integrations Using Complement Information Entropy

ZHAO Junyang1,2,HAN Chongzhao2,HAN Deqiang2,ZHANG Chunxia3

(1. Staff Room 202, The Second Artillery Engineering University, Xi’an 710025, China; 2. School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China; 3. School of Mathematics and Statistics,Xi’an Jiaotong University, Xi’an 710049, China)

A novel diversity measure method using complement information entropy (CIE) is proposed to solve the problem that the diversity estimation of multiple classifier systems is unable to deal directly with fuzzy data. A set of base classifiers is generated by using training data, and then is used to label test data. The outputs of the classifiers are reorganized into a new classification data space. Then the complement information entropy model is introduced under fuzzy relation to measure uncertainty information of the new space and the uncertainty information is used to estimate the diversity of base classifiers. Finally, an ensemble system is constructed based on the criterion that the ensemble diversity of the classifier set increases when a base classifier is added, and the ensemble system is used to validate the performance of CIE. Experimental results and a comparison with theQ-statistic method show that the average classification accuracy of CIE increases by 2.03%, and the number of ensemble classifiers reduces by 17%. Moreover, CIE also improves the ability of ensemble systems to process diverse data.

classifier ensemble; diversity; complement information entropy; fuzzy relation

2015-06-21。

趙軍陽(1981—),男,講師,博士后;韓崇昭(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61074176,41174162);中國博士后科學基金資助項目(2013M532048)。

時間:2015-11-27

10.7652/xjtuxb201602003

TP391.4

A

0253-987X(2016)02-0013-07

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20151127.2115.002.html