一種基于關聯信息熵度量的特征選擇方法

董紅斌　滕旭陽　楊　雪

(哈爾濱工程大學計算機科學與技術學院　哈爾濱　150001)

?

一種基于關聯信息熵度量的特征選擇方法

董紅斌滕旭陽楊雪

(哈爾濱工程大學計算機科學與技術學院哈爾濱150001)

(donghongbin@hrbeu.edu.cn)

特征選擇旨在從原始集合中選擇一個規模較小的特征子集，該子集能夠在數據挖掘和機器學習任務中提供與原集合近似或者更好的表現.在不改變特征物理意義的基礎上，較少特征為數據提供了更強的可解讀性.傳統信息論方法往往將特征相關性和冗余性分割判斷，無法判斷整個特征子集的組合效應.將數據融合領域中的關聯信息熵理論應用到特征選擇中，基于該方法度量特征間的獨立和冗余程度.利用特征與類別的互信息與特征對組合構建特征相關矩陣，在計算矩陣特征值時充分考慮了特征子集中不同特征間的多變量關系.提出了特征排序方法，并結合參數分析提出一種自適應的特征子集選擇方法.實驗結果表明所提方法在分類任務中的有效性和高效性.

特征選擇；聯合信息熵；組合效應；多變量關系；相關矩陣

近年來各行業數據量的指數級增長為數據挖掘與機器學習任務帶來了新的挑戰.在處理數據量龐大、數據維度高的任務時，首先對數據進行降維是一個行之有效的手段.降維的目的在于用較低維的數據保持原有數據的特性，在完成數據任務時能提供與原數據集近似或更優的表現.目前主流的降維手段有特征提取與特征選擇2種[1].特征提取方法將原有特征集合數據轉換到一個更低維的新特征空間，主成分分析(principalcomponentanalysis,PCA)和線性判別分析(lineardiscriminantanalysis,LDA)等是特征提取的代表性方法.特征選擇則通過一個特定的評估函數來評價特征或特征組合，進而從原始特征集合中選擇出一個維度更低的特征子集.兩者最本質的區別在于特征選擇沒有改變原始特征的物理意義，在需要理解數據的潛在意義與原始特性時傾向于使用特征選擇方法，在僅需要提供數據辨識能力時傾向于使用特征提取方法.

根據特征子集評估策略的不同，可將特征選擇技術大致分為3類[2]：Filter模型、Wrapper模型和Embedded模型.Filter模型僅依賴數據的內在特性來選擇特征，而不依賴任何具體的學習算法指導.Wrapper模型則需要一個預先設定的學習算法，將特征子集在其算法上的表現作為評估來確定最終的特征子集.Embedded模型則是在學習算法的目標分析過程中包含變量選擇，將此作為訓練過程的一部分以獲得特征相關性，例如C4.5和LARS方法.Wrapper模型因其高復雜性往往只在具體學習任務中使用.而數據規模龐大時，Filter模型因其高效性和良好的泛化能力則更為理想.根據特征選擇的輸出結果，又可將特征選擇分為特征權重和子集選擇2類方法.特征權重方法根據評估函數得出的特征重要程度對其進行排序，具體選擇多少特征需要人工控制.子集選擇方法則根據對子集的整體評估，輸出評估最優的特征子集.

特征選擇作為一種數據預處理手段近年來被廣泛應用到各行各業中，例如社會網絡[3]、入侵檢測[4]、生物信息[5]、圖像分析[6]和自然語言處理[7]等.在大規模數據集中往往存在大量的無關和冗余特征，而特征選擇的主要任務則是在選擇相關特征的同時去除冗余特征.在選取特征時各種有效的度量手段作為評估函數應用到特征選擇中，例如信息論度量、一致性度量、關聯度量、依賴性度量和距離度量等.1994年由Battiti[8]提出的MutualInformation特征選擇方法衡量特征與類別標簽的相關程度，兩者的互信息越多，該特征越重要；Yu等人[9]2004年提出的FCBF方法使用了信息論中的對稱不確定性來衡量2個特征的相關性，結合Markovblanket技術刪除冗余特征；mRMR作為一種經典的信息論特征選擇方法在2005年由Peng等人[10]提出，該方法基于互信息計算兼顧特征與類別之間的相關性與特征之間冗余度.以上3種廣為流行的特征選擇方法在考慮特征冗余程度時，均是比較特征與特征之間成對的冗余性，而沒有判斷特征加入或刪除后特征子集整體組合信息程度的變化.而特征選擇過程中，特征的組合效應近年來得到了學者們的重視.Sun等人[11-12]將合作博弈理論中的班次哈弗權力指數以及夏普利值使用到特征選擇方法中，用以評估特征在整個特征子集中的組合影響力，然而在創建候選聯盟(生成部分可選子集)時耗費了大量的時間.Dong與楊曇等人[13-14]研究使用進化算法和群體智能度量特征子集的組合效應，但算法往往無法形成固定規模的特征子集.文獻[15]中段潔與胡清華等人提出基于粗糙集依賴度量的特征子集選擇方法.Liu等人[16]基于此考慮了特征加入后子集依賴性的整體變化，結合Markovblanket理論提出一種新的依賴盈余特征選擇方法，該方法較合作博弈理論方法時間復雜度降低，但依然相對耗時.ReliefF[17]和CFS-FS[18]則分別是基于距離度量和基于關聯度量的2種經典特征選擇方法,ReliefF缺乏對特征子集組合效應的度量，CFS-FS則不能有效處理特征間的冗余關系.

關聯信息熵的概念來源于多傳感器數據融合領域，是一種度量系統冗余信息的方法.由Wang等人[19]提出并利用該技術度量多傳感器系統中的重疊和獨立信息，該方法將多變量間相關關系的信息度量計算為[0,1]的閉區間范圍.事件之間的獨立程度越大，冗余程度(重疊)越小，對應的關聯信息熵越大.

本文將每一維特征作為一個傳感器，為傳感器信息度量和特征信息度量之間建模，進而使用關聯信息熵度量特征子集的組合效應.有別于傳統信息論方法，該方法充分考慮了特征子集中不同特征間的多變量關系，并在結果中同時體現了特征的關聯關系和冗余關系.為了驗證算法的有效性，實驗分別在UCI中小規模數據集和大規模數據集中進行分析，在分類正確率和運行時間上驗證了本文所提方法的高效性.

1　預備知識

1.1特征選擇概述

數據集D中含有k個樣本D={d1,d2,…,dk}，并且對于D中每個樣本di都有特征集合X={x1,x2,…,xn}，其中包含n維特征，di∈n.對于分類問題，可將D中樣本劃分為目標集合C中的m個不同的類別C={c1,c2,…,cm}.特征選擇的目的是在原始特征集合X中尋找到一個最佳特征子集S，其中S含有p維特征(p

特征選擇通常包括4個組件：特征子集生成、子集評估、終止條件和結果驗證.基于一個確定的搜索策略，特征子集生成組件首先生成候選特征子集P′；進而使用確定的評估函數對每一個候選特征子集進行度量，并與之前最佳候選特征子集做比較，如果新的特征子集表現更加優越，那么替換原有最佳特征子集.生成和評估過程循環直到滿足終止條件.最終所選的特征子集需要用一些給定的學習算法進行結果驗證.

1.2互信息原理

在香農的信息熵理論中，熵用于度量隨機變量信息的不確定性.H(X)通常用作描述離散隨機變量X={x1,x2,…,xn}的熵值，xi是變量X的可能取值，p(xi)為概率密度函數.

(1)

當已知2個離散變量X和Y的聯合概率密度p(x,y)時,X與Y的聯合熵計算為:

(2)

H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y).

(3)

對于給定變量Y，變量X的條件熵將小于或等于其各自單獨的熵.當熵值為零時，說明變量X完全依賴變量Y.反之當且僅當2個變量相互獨立時，條件熵等于其熵，變量Y對X不提供任何有用信息.

(4)

基于以上不確定性的熵值計算，互信息表示2個變量所分享的信息量：

I(X;Y)=H(X)-H(Y|X)=H(Y)-H(X|Y)=

H(X)+H(Y)-H(X,Y),

(5)

當2個變量的互信息值越大，則意味著2個變量相關程度越緊密；當互信息為0時，則意味著2個變量完全不相關，如圖1所示[20]：

Fig. 1　Relationships between entropy and mutual information.圖1　熵與互信息的關系圖

1.3關聯信息熵理論

假設一個多變量系統具有n個變量，該系統在時刻t(t=1,2,…,m)的多變量時間序列矩陣為P，則有：

P=(yi(t))1≤t≤m，1≤i≤n，P∈m×n，

(6)

其中,P為實數矩陣，yi(t)表示第i個變量在時刻t的取值.通過對矩陣P進行中心化和標準化處理后得到多變量時間序列矩陣Q：

(7)

計算相關矩陣R：

R=QTQ，R∈m×n.

(8)

對于n個傳感器的關聯矩陣R可以推導為如下：

(9)

1)

(10)

2)

(11)

每個傳感器對系統整體信息的貢獻可用其特征值表示.依據信息論計算原理，關聯信息熵的計算如下：

(12)

因單位陣I的特征值均為1，根據熵計算式(12)可計算HI=1.故：

(13)

2　使用關聯信息熵度量的特征選擇方法

本文研究從特征選擇的基本要求入手，兼顧特征與類別間的相關性以及特征與特征間的冗余性.文章的模型構建將原始特征空間作為多傳感器系統，將每一維特征作為一個傳感器，在該環境中使用關聯信息熵度量來判斷特征之間的組合效應，減少特征之間的冗余信息.基于這種度量，本節將提出一種特征排序算法(featuresortingbasedoncorrelationinformationentropymeasurement,CMFS)，進而將重疊信息進行閾值η調控，設計一個自適應子集規模的特征選擇方法(adaptivefeaturesubsetselectionalgorithmbasedoncorrelationinformationentropymeasurementandη,CMFS-η).

2.1模型描述

原始特征集合X={x1,x2,…,xn}作為含有n個變量的多變量系統，其中每個特征xi等價于一個傳感器.這里不同于原傳感器系統，本文不使用樣本在n維特征下的具體數據作為輸入，而是將樣本的類別信息C={c1,c2,…,cm}作為系統的時間序列.基于特征與樣本類別間的相關性，構造一個可度量的多元變量模型F，此處F等價于1.3節中的矩陣P的轉置，具體形式為

矩陣中元素Ii j是每一個特征與相應類別的互信息：

I(xi;cj)=H(xi)+H(cj)-H(xi,cj).

(14)

由于關聯信息度量側重于考慮多變量之間的冗余(重疊)關系，因此如果將樣本在每一維特征下的數據作為輸入，無法兼顧特征與類別之間相關性的度量.在高維多樣本的空間中，本模型的構建不僅將互信息作為信號輸入度量了特征相關性，而且能大大縮減多變量模型的體積，符合特征選擇任務的基本要求.

(15)

(16)

計算特征相關矩陣：

(17)

相關矩陣Rel滿足對稱性，矩陣中的每一個元素代表2個特征在相同類別信息下的相似度.

該過程首先將k×n的原始數據空間壓縮為m×n(m?n，n?k )的矩陣，雖然在計算特征相關矩陣時矩陣維度升至n×n，但仍大大縮減了數據空間.

2.2特征排序算法CMFS

從線性空間的角度看，在一個定義了內積的線性空間里，對一個n階對稱方陣進行特征分解，就是產生了該空間的n個標準正交基，然后把矩陣投影到這n個基上.n個特征向量就是n個標準正交基，而特征值的規模則代表矩陣在每個基上的投影長度.特征值越大說明矩陣在對應的特征向量上方差越大、功率越大.在數據挖掘的任務中，最大特征值對應的特征向量方向上包含最多的信息量.本文所使用的關聯信息熵上從特征集合的角度判斷其組合效應，由特征集合得到特征值計算出的關聯信息熵判斷了特征組合所包含的信息量，同時也度量了特征間的冗余.

CMFS算法使用關聯信息熵作為子集評估組件，搜索方式采用序列搜索.與傳統的序列算法流程不同的是，所提方法首先使用反向刪除的策略，選取第1個特征.基于第1個特征，再使用正向添加的策略，對特征集合進行擴充排序.在序列搜索特征選擇的過程中，第1個特征的確定起著非常重要的作用，基于互信息的方法，例如：MIFS，mRMR，MIFS-U等都是將與類別互信息最大的特征作為第1個特征放入集合.該方式忽略了特征間的組合效應，而本文從整體獲得該特征與整體失去該特征的關聯信息熵變化出發，選取特征缺失后使整體冗余信息增量最大的作為第1個特征，特征的選取方式如下：

Info(i)= Hall-Hmiss(xi)，

(18)

Hall為全體特征下的關聯信息熵，Hmiss(xi)為失去特征xi的關聯信息熵.

引理1. 若xi=argmax(Info(i))，特征xi為整體提供最多信息.

整體集合在失去特征xi后冗余信息量上升最大，證明xi與其余特征整體相關，為整體提供了最多信息.

證畢.

假設已排序的特征集合為S，則未排序特征集合為X-S.對于xi∈X-S，添加特征xi到集合S中，擴充后的相關矩陣記為Reladd，計算擴充集合的關聯信息熵：

(19)

引理2. xi=argmax(Hadd(i))，特征xi為當前排序特征集合提供最多信息.

添加該特征后，當前排序特征集合獲得了最少量的冗余信息，獲得最大量的差異信息.

證畢.

反向刪除是為了確保第1個特征與整體相關，而非冗余特征.而正向擴充的目的是為了確保在排序后的特征集合中選取任意p>1個特征構成的特征集合是低冗余高相關.具體過程如算法1所示：

算法1. 關聯信息熵度量的特征排序算法.

輸入：數據集D、特征集合X、類別信息C;

輸出：排序后的特征集合S.

① S=?；

②Foreachxi∈X，cj∈C

③ 根據式(14)計算Ii j，得到矩陣F；

④EndFor

⑤ 根據式(15)(16)進行中心化和標準化得到矩陣QF；

⑥ 根據式(17)得到特征相關矩陣Rel；

⑧Foreachxi∈X

⑨ 根據式(18)計算Info(i)；

⑩EndFor

2.3自適應子集選擇方法CMFS-η

該部分考慮引入閾值η 進行子集規模的控制，簡稱為CMFS-η.不同于傳統的特征個數閾值，η的引入是從信息度量的角度進行控制：

(20)

由式(20)看出,η是對冗余信息的控制，該參數仍然確保每次加入的特征帶來了最低的冗余信息，但當帶來的冗余信息超出1-η的限定時，算法終止迭代.至此，算法再添加剩余特征中的任何特征都將帶來高于1-η的冗余信息.因此該過程可自適應地形成子集規模，無需特征個數的硬劃分，并確保了冗余信息盡可能少.具體過程如算法2所示：

算法2. 關聯信息熵度量的自適應特征選擇算法.

輸入：數據集D、特征集合X、類別信息C；

輸出：排序后的特征集合S.

對于η 的具體取值，將在實驗部分進行詳細分析.

2.4計算復雜度分析

3　實驗結果與分析

為了驗證本文提出算法的高效性，本文選擇了UCI數據集中14個數據集，采用4個部分進行驗證：1)針對特征維度適中，樣本與類別數目較少的數據集進行實驗分析，驗證本文所提排序算法在手動設置特征子集規模下的有效性；2)對η在高維數據集中的表現進行分析，判斷其在控制特征規模與分類正確率2方面的表現，得到相應閾值；3)在高維樣本數據集下驗證所提CMFS與CMFS-η的有效性；4)給出時間效率的對比.本文實驗特征排序與子集選擇部分的運行環境為Matlab2013a，分類正確率運行環境為weka3.7.對數據的離散化處理采用經典的MDL方法[21].部分實驗結果參見文獻[14，22].

3.1CMFS算法在中小規模數據中的結果分析

本部分選用8個UCI數據集進行驗證，數據集各項指標如表1所示：

Table 1　Descriptions of UCI Benchmark Datasets表1　UCI數據集描述

實驗對比的特征選擇方法有FCBF，IG，Cfs，ReliefF，Dependency.以上方法分別是信息熵特征選擇、基于關聯性特征選擇、基于距離度量特征選擇以及基于一致性度量特征選擇的代表性算法.為了驗證算法性能，選取SVM，CART，Na?veBayes三個分類器使用10折交叉驗證對選擇的特征進行分類測試，取最優結果.本文所提CMFS方法在本部分實驗中對8個數據集的特征進行排序，最終手動選擇5，1，5，7，2，2，5，5個特征，平均約減了53.5%的數據規模.具體的分類結果如表2～4所示.表中數值數據表示各特征選擇方法選擇的特征子集在相應數據集下使用分類器得到的分類正確率，其中加粗數據表示為該行分類效果最高正確率，Avg行的表示平均分類正確率.表格最后一行WTL表示該列方法與所提出CMFS方法相比在8個數據集上Win(勝于)Tie(平手)Lose(弱于)的次數.表格中對部分數據集進行簡稱：Austr，CrdApr，Mamm，Pima分別為對應表1中的1，3，6，7個數據集.

Table 2　Classification Accuracy with SVM Classifiers表2　SVM分類器的分類正確率

Table 3　Classification Accuracy with CART Classifiers表3　CART分類器的分類正確率

Table 4　Classification Accuracy with Na?ve Bayes Classifiers表4　Na?ve Bayes分類器的分類正確率

從表2中可以看到，所提方法在SVM分類器下分別在Austr，CrdApr，Pima數據集中取得了最好的分類正確率.在Blood數據集與其他特征選擇方法獲得了相同的分類正確率.在Heart數據集中僅落后ReliefF方法0.08%.在該分類器下CMFS沒有取得最高平均分類正確率，弱于最優0.27%，但是在WTL指標中除弱于ReliefF方法，均優于其他方法，平均獲得了52.5%的勝率.

所提方法在CART分類器下的表現優于在SVM分類器下的表現，如表3所示.在各個特征選擇方法選擇與表2相同的特征子集空間中，CMFS在該分類器下取得了最好的平均分類正確率，并高于次優1.5%.從表3中可看到所提方法在Austr，CrdApr，Iris和Pima數據集中取得了最好的分類正確率.在Blood數據集中，所提方法比ReliefF落后0.1%的正確率，在Mamm數據集中落后最優0.11%.WTL指標中均優于其他方法，平均獲得了87.5%的勝率.

CMFS在Na?veBayes分類器下仍然保持優勢，在前7個數據集中均取得了最高的分類正確率.并且平均正確率高于第2名1.77%.在WTL指標中均優于其他方法，平均獲得了90%的勝率，如表4所示.

本部分實驗結果驗證了所提CMFS方法雖然在SVM分類器下性能非最佳，但仍然取得了較高的分類正確率和勝率.綜合其在3個分類器下的表現，驗證了CMFS算法在非高維中小規模數據集下的有效性.

3.2η參數的性能分析

本部分實驗將通過對超高維數據集上的運行，分析η參數的合理取值范圍.在中小規模數據集中，算法運行時間短，η的意義不顯著.而在超高維數據中，η的調控將在迭代擴充特征的過程中縮減大量的運行時間.所選取的超高維UCI數據集如表5所示，數據維度從33維升至618維.

Table 5　Descriptions of UCI Benchmark Datasets表5　UCI數據集描述

η調控的意義在于既保證特征維度的降低，又要保證較高的分類正確率.因此實驗將對這2方面進行分析. 為確保參數的泛化效果，本文將采用SVM，1-NN，Na?veBayes三種分類器上的平均分類正確率作為參考，結果如圖2，3所示：

Fig. 2　The relationship between number of features and parameter η.圖2　特征維度與參數η的關系圖

1) 維度的比較.從圖2(a)與圖2(b)中可以看出參數η對特征子集的規模有一個較好的控制，η=0.1時，在算法2中意味著允許加入的特征帶了0.9的冗余信息，對冗余信息的限定較低所以圖中看出，特征子集規模等于特征原始集合規模，此時方法相當于特征排序算法.隨著η數值的升高，冗余擴充特征帶來的冗余信息少于1-η，特征子集規模將變得越來越小.6個數據集中，η>0.4時，特征子集規模均縮小.而0.6≤η≤0.7時，特征數目對比原特征集合已經有了巨幅縮減，并趨于平穩態勢.η>0.7時，意味著僅允許特征帶來0.3的冗余，特征子集規模變化較小.

2) 平均分類正確率的比較.在噪聲較小的數據集中，隨著特征子集規模的減小，平均分類正確率也會隨之下降.在噪聲較多的數據集中，例如：Sonar和Arrhythmia，平均分類正確率會隨著刪除無關與冗余特征先升高再下降，如圖3所示.對比參數與維度的關系，當η<0.35時，除Sonar數據集(在圖2(a)中，特征維度此處有較大變化)，平均分類正確率等同于原有特征集合.當0.6≤η≤0.7時，平均分類正確率在噪聲較小的數據集中，有小幅度下滑；在噪聲較多的數據集中平均分類正確率有顯著提升.當η>0.7時，各個數據集上的正確率則有顯著的下滑趨勢.

Fig. 3　Relationship between average classification accuracy and parameter η .圖3　平均分類正確率與參數η的關系圖

綜合上述分析，當0.6≤η≤0.65時可大大縮減特征子集規模同時保證較高的平均分類正確率.該參數為自適應特征子集規模提供了指導.其優勢將繼續在實驗3.3節中說明.

3.3CMFS與CMFS-η在高維數據中的表現

本部分選取的實驗數據集為3.2節中介紹的6個超高維數據集.為了驗證算法的泛化能力，本部分將3.1節中的特征選擇對比算法與分類器進行部分調整.選擇了FCBF，IG，ReliefF，mRMR這4種方法，選取了SVM，1-NN，Na?veBayes三種分類器，分類時依然采用10折交叉驗證.具體分類正確率的實驗結果如表6～8所示.本部分實驗增加了選擇特征個數的對比，#Feature為特征選擇后特征子集的規模.為了公平對比，CMFS算法選擇與其他算法幾乎同等規模的子集進行對比，而CMFS-η算法根據3.2節實驗結果，取值0.6≤η≤0.65自適應選擇子集規模.但由于Isolet為超高維數據集，雖然在自適應算法η=0.65時分別取得了88.17%，78.02%，90.96%的平均分類正確率并大大優于其他方法，但形成的特征子集規模較大，為了保證公平性此數據集中η=0.8，以獲得相似規模的特征子集.在其余5個數據集的自適應算法中η=0.65.其中FCBF與CMFS-η為子集選擇算法，而IG，ReliefF，mRMR，CMFS為特征排序算法.由于子集選擇算法選擇的子集規模比排序算法手動限制規模大，因此分類性能會優于排序算法.具體結果如表6～8所示.

Table 6　Comparison of Classification Accuracy and Number of Features with SVM Classifiers表6　SVM分類器的分類正確率與特征數目對比

Table 7　Comparison of Classification Accuracy and Number of Features with 1-NN Classifiers表7　1-NN分類器的分類正確率與特征數目

Table 8　Comparison of Classification Accuracy and Number of Features with Na?ve Bayes Classifiers表8　Na?ve Bayes分類器的分類正確率與特征數目

表6是各個特征選擇算法在SVM分類器上的表現，可以看出CMFS-η在5個數據集上均取得了最高的分類正確率，并且取得了最高的平均分類正確率.在Isolet數據集中算法獲得了第二高的平均分類正確率，僅比FCBF算法少了2.19%.CMFS-η獲得了96.67%的勝率.CMFS方法在SVM分類器上的表現也十分優異，平均正確率僅比FCBF算法少了0.13%，并且在3個數據集中獲得了次優的正確率，而且算法本身選擇限定的特征子集規模除Arrhythmia數據集外均小于FCBF所選擇的子集規模.CMFS方法在5個數據集中的表現均優于IG，ReliefF，mRMR這3種特征排序方法，在Arrhythmia數據集中選擇比IG算法少一個特征的情況下，分類正確率僅落后0.44%.在1-NN分類器中，CMFS-η依然保持著最佳的平均分類正確率，結果如表7所示.算法在Syntheticcontrol，Multi-featurepixel，Isolet這3個數據集上取得了最佳分類效果.在其他3個數據集中取得了第2名的分類效果，整體勝率為90%.CMFS在該分類器下表現整體優于IG，ReliefF算法，但稍弱于mRMR方法，整體平均正確率落后0.93%.盡管如此，CMFS在Sonar，Syntheticcontrol，Multi-featurepixel這3個數據集上也取得優于mRMR方法的分類正確率.

對比表8中Na?veBayes分類器的實驗結果，可以看出CMFS-η的在分類任務中的優勢，整體平均正確率比第2名的FCBF算法高出4.99%.在Sonar，Syntheticcontrol，Arrhythmia數據集上取得了最佳分類效果.在其余3個數據集中也取得了與FCBF近似的正確率，并獲得90%的勝率.CMFS算法在此分類器表現優于IG，ReliefF，mRMR算法，并在5個數據集中上均保持優于3種算法的分類正確率.

通過上述實驗分析在子集選擇方法中，CMFS-η方法優于FCBF方法；在特征排序算法中，提出的CMFS方法優于IG，ReliefF，mRMR算法.整體效果本文提出的CMFS-η最優.

3.4算法時間對比

Cofs是文獻[11]中提出的基于合作博弈的特征選擇方法，該方法充分考慮了特征的組合效應，并取得了非常優秀的分類性能，然而該方法時間復雜度高，在每次生成候選特征子集時算法時間復雜度呈指數級，導致耗時較多.mRMR方法與本文所提算法時間復雜度接近，因此本部分選取這2種方法進行運行時間對比.為對比效果差異，在同樣環境設置中選取4個維度遞增的高維數據集運行3種算法.具體結果如表9所示：

Table 9　Running Time on UCI Datasets表9　在UCI數據集上運行時間對比

通過1.4節分析，提出算法的時間復雜度對樣本維度依賴較高，而對樣本數目依賴較小.mRMR方法不僅對特征維度依賴較高，對樣本數目依賴程度更高.從表9中數據得出，CMFS-η算法運行時間最快.在Synthetic數據集中，樣本數為特征維度的10倍，CMFS-η算法的運行時間0.16s，約為mRMR算法的12，約為Cofs算法的17.在Multi-featurepixel數據集中，樣本數約為特征維度的8倍，CMFS-η算法的運行時間約為mRMR算法的110，約為Cofs算法的120.由于Arrhythmia數據集中存在大量取值相同的特征，因此在計算之時已經減少了特征維度，所以在該數據集中，CMFS-η算法的運行時間更具優勢，約為mRMR算法的7100，約為Cofs算法的3100.在Isolet數據集中CMFS-η算法的運行時間約為Cofs算法13，僅比mRMR算法少約16s.這是因為Isolet是超高維數據，而且樣本數目約為2.5倍，因此CMFS-η算法運行時間相對較少，但不會出現成倍縮減，符合前文對時間復雜度的分析.綜上，在樣本數遠遠大于其樣本維度時，本文算法優勢將變得更加明顯.

4　結束語

本文針對特征成組后缺少組合效應度量的問題，研究了多傳感器領域中的關聯信息熵的性質，并將其引入到特征選擇任務中，完成其模型的映射與構建.基于關聯互信息本文提出了特征排序算法CMFS與自適應子集選擇算法CMFS-η，給出了算法復雜度分析，證明其優于典型的mRMR算法.通過在不同規模數據集上的實驗，驗證了所提算法的有效性和高效性.在中小規模數據集中通過手動限定特征個數，CMFS方法獲得了6種算法中的最佳平均分類正確率.通過對參數η在特征維度與分類正確率2方面的討論與設置，CMFS-η算法自適應選擇子集并在大規模高維數據集中獲得了整體平均92.22%的勝率.實驗最后給出了運行時間，對比表明算法任務執行的效率.

本文提出的特征選擇方法在分類精度和運行速度上具備良好的性能，對于處理大規模數據的實際問題具有應用價值.但本文選取的是單標簽數據集進行分類任務的比較，未來將進行多標簽數據集標簽成組相關性和特征與多標簽相關性的研究，比較單標簽與多標簽在度量冗余信息時的差異.

[1]BennasarM,HicksY,SetchiR.Featureselectionusingjointmutualinformationmaximisation[J].ExpertSystemswithApplications, 2015, 42(22): 8520-8532

[2]ZhaoZheng,MorstatterF,SharmaS,etal.Advancingfeatureselectionresearch-ASUfeatureselectionrepository[R].Phoenix,AZ:SchoolofComputing,Informatics,andDecisionSystemsEngineering,ArizonaStateUniversity,Tempe, 2010

[3]TangJiliang,LiuHuan.Unsupervisedfeatureselectionforlinkedsocialmediadata[C] //Procofthe18thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2012: 904-912

[4]EesaAS,OrmanZ,BrifcaniAMA.Anovelfeature-selectionapproachbasedonthecuttlefishoptimizationalgorithmforintrusiondetectionsystems[J].ExpertSystemswithApplications, 2015, 42(5): 2670-2679

[5]SaeysY,InzaI,LarraagaP.Areviewoffeatureselectiontechniquesinbioinformatics[J].Bioinformatics, 2007, 23(19): 2507-2517

[6]SinghD,GnanaAA,BalamuruganS,etal.Anovelfeatureselectionmethodforimageclassification[J].OptoelectronicandAdvancedMaterials-RapidCommunications, 2015, 9(11//12): 1362-1368

[7]MengJiana,LinHongfei,YuYuhai.Atwo-stagefeatureselectionmethodfortextcategorization[J].Computers&MathematicswithApplications, 2011, 62(7): 2793-2800

[8]BattitiR.Usingmutualinformationforselectingfeaturesinsupervisedneuralnetlearning[J].IEEETransonNeuralNetworks, 1994, 5(4): 537-550

[9]YuLei,LiuHua.Efficientfeatureselectionviaanalysisofrelevanceandredundancy[J].TheJournalofMachineLearningResearch, 2004, 5: 1205-1224

[10]PengHanchuan,LongFuhui,DingC.Featureselectionbasedonmutualinformationcriteriaofmax-dependency,max-relevance,andmin-redundancy[J].IEEETransonPatternAnalysisandMachineIntelligence, 2005, 27(8): 1226-1238

[11]SunXin,LiuYanheng,LiJin,etal.Usingcooperativegametheorytooptimizethefeatureselectionproblem[J].Neurocomputing, 2012, 97: 86-93

[12]SunXin,LiuYanheng,LiJin,etal.Featureevaluationandselectionwithcooperativegametheory[J].PatternRecognition, 2012, 45(8): 2992-3002

[13]DongHongbin,TengXuyang,ZhouYang,etal.Featuresubsetselectionusingdynamicmixedstrategy[C] //Procof2015IEEECongressonEvolutionaryComputation.Piscataway,NJ:IEEE, 2015: 672-679

[14]YangTan,FengXiang,YuHuiqun.Featureselectionalgorithmbasedonthemulti-colonyfairnessmodel[J].JournalofComputerResearchandDevelopment, 2015, 52(8): 1742-1756 (inChinese)

(楊曇, 馮翔, 虞慧群. 基于多群體公平模型的特征選擇算法[J]. 計算機研究與發展, 2015, 52(8): 1742-1756)

[15]DuanJie,HuQinghua,ZhangLingjun,etal.Featureselectionformulti-labelclassificationbasedonneighborhoodroughset[J].JournalofComputerResearchandDevelopment, 2015, 52(1): 56-65 (inChinese)

(段潔, 胡清華, 張靈均, 等. 基于鄰域粗糙集的多標記分類特征選擇算法[J]. 計算機研究與發展, 2015, 52(1): 56-65)

[16]LiuYong,TangFeng,ZengZzhiyong.Featureselectionbasedondependencymargin[J].IEEETransonCybernetics, 2015, 45(6): 1209-1221

[17]Robnik-ikonjaM,KononenkoI.TheoreticalandempiricalanalysisofReliefFandRReliefF[J].MachineLearning, 2003, 53(1//2): 23-69

[18]HallMA.Correlation-basedfeatureselectionfordiscreteandnumericclassmachinelearning[C] //Procofthe17thIntConfofMachineLearning(ICML).SanFrancisco:MorganKaufmann, 2000: 359-366

[19]WangQiang,ShenYi,ZhangYe,etal.Fastquantitativecorrelationanalysisandinformationdeviationanalysisforevaluatingtheperformancesofimagefusiontechniques[J].IEEETransonInstrumentationandMeasurement, 2004, 53(5): 1441-1447

[20]WangZhichun,LiMinqiang,LiJuanzi.Amulti-objectiveevolutionaryalgorithmforfeatureselectionbasedonmutualinformationwithanewredundancymeasure[J].InformationSciences, 2015, 307: 73-88

[21]FayyyadUM,IraniKB.Multi-intervaldiscretizationofcontinuous-valuedattributesforclassificationlearning[C] //Procofthe13thIntJointConfonArtificialIntelligence.SanFrancisco,CA:MorganKaufmann, 1993: 1022-1027

[22]SunXin,LiuYanheng,XuMantao,etal.Featureselectionusingdynamicweightsforclassification[J].Knowledge-BasedSystems, 2013, 37: 541-549

DongHongbin,bornin1963.ProfessorandPhDsupervisorinHarbinEngineeringUniversity.Hismainresearchinterestsincludemulti-agentsystemandmachinelearning.

TengXuyang,bornin1987.PhDcandidateinHarbinEngineeringUniversity.Hismainresearchinterestsincludemachinelearningandintelligentinformationprocessing.

YangXue,bornin1986.PhDcandidateinHarbinEngineeringUniversity.Hermainresearchinterestsincludeintelligentoptimizationalgorithmandauctiononlineadvertising.

FeatureSelectionBasedontheMeasurementofCorrelationInformationEntropy

DongHongbin,TengXuyang,andYangXue

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001)

Featureselectionaimstoselectasmallerfeaturesubsetfromtheoriginalfeatureset.Thesubsetcanprovidetheapproximateorbetterperformanceindataminingandmachinelearning.Withouttransformingphysicalcharacteristicsoffeatures,fewerfeaturesgiveamorepowerfulinterpretation.Traditionalinformation-theoreticmethodstendtomeasurefeaturesrelevanceandredundancyseparatelyandignorethecombinationeffectofthewholefeaturesubset.Inthispaper,thecorrelationinformationentropyisappliedtofeatureselection,whichisatechnologyindatafusion.Basedonthismethod,wemeasurethedegreeoftheindependenceandredundancyamongfeatures.Thenthecorrelationmatrixisconstructedbyutilizingthemutualinformationbetweenfeaturesandtheirclasslabelsandthecombinationoffeaturepairs.Besides,withtheconsiderationofthemultivariablecorrelationofdifferentfeaturesinsubset,theeigenvalueofthecorrelationmatrixiscalculated.Therefore,thesortingalgorithmoffeaturesandanadaptivefeaturesubsetselectionalgorithmcombiningwiththeparameterareproposed.Experimentresultsshowtheeffectivenessandefficiencyonclassificationtasksoftheproposedalgorithms.

featureselection;correlationinformationentropy;groupeffect;multivariablecorrelation;correlationmatrix

2016-03-17；

2016-05-30

國家自然科學基金項目(61472095，61502116)；黑龍江省教育廳智能教育與信息工程重點實驗室開放基金項目

滕旭陽 (teng_xuyang@126.com)

TP18

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(61472095, 61502116)andtheOpenFoundationoftheHeilongjiangProvincialEducationDepartmentKeyLaboratoryofIntelligentEducationandInformationEngineering.