劉 杰，張 平，高萬夫

(1.吉林大學 計算機科學與技術學院，長春 130012；2.吉林大學 符號計算與知識工程教育部重點實驗室，長春 130012；3.吉林大學 軟件學院，長春 130012)

0 引 言

隨著大數據時代的到來，各種各樣類型的數據信息呈現指數級增長。如何快速、準確地從龐雜的信息中選擇出最有價值的信息變得越來越重要。降維技術就是解決這一類問題的重要手段。目前主要的降維技術主要包括特征提取和特征選擇兩種[1]。特征提取就是將原有的高維數據轉換為低維數據，改變了原始特征的物理意義；特征選擇則是從原有的高維數據中挑選出最有價值的特征，保留原始特征的物理特性。在簡單用于找出那些有價值的特征時，兩種降維技術作用是一樣的，但如果研究者想要分析所選出來的特征的實際意義，那么，特征選擇方法更優(yōu)越，它可以更好地幫助研究者分析所選出來的特征的潛在意義。

根據選擇策略的不同，特征選擇算法一般分為封裝法(Wrapper)、嵌入法(Embedded)和過濾法(Filter)3類[2]。封裝法是依賴于分類器的一種方法，它一般分為兩步：①選出一個特征子集；②評估這個子集的分類表現。重復步驟①和②直到選出合適的子集。封裝法分類表現一般比較好，但缺點是太過依賴具體的分類器容易出現過擬合，并且執(zhí)行效率較低。嵌入法是將特征選擇集成在學習機訓練過程中，通過優(yōu)化一個目標函數，在訓練分類器的過程中實現特征選擇。嵌入法相對于封裝法執(zhí)行效率較高，但是構造一個合適的函數優(yōu)化模型往往比較困難。相比較而言，過濾法是效率最高的一種選擇策略，它獨立于任何分類器，并且具有較好的泛化能力，因此應用廣泛，尤其是基于信息論的過濾法。對于特征子集的搜索策略，一般分為啟發(fā)式搜索、隨機搜索和完全搜索3種[4，5]。本文使用的是啟發(fā)式搜索策略中的序列向前搜索方法。

基于信息論的特征選擇算法是當前的研究熱點。傳統(tǒng)的基于互信息的特征選擇算法都將候選特征與類標簽的互信息值作為相關項，例如mRMR[6]，但它們卻忽略了候選特征與類標簽的相關性是隨著已選特征的加入而動態(tài)改變的。本文將候選特征與類標簽在已知已選特征下的條件互信息作為相關項，去掉那些與已選特征冗余關系強烈的候選特征，選出最有意義的特征。為證明本文提出的相關性概念——條件相關性，比傳統(tǒng)的相關性優(yōu)越，接下來給出理論說明。另外，在10個真實數據集上分別對本文條件相關特征選擇(Conditional relevance feature selection，CRFS)算法與其他7種特征選擇算法進行比較，其中JMI[7]與本文算法的框架相似，mRMR、CIFE[8]、DISR[9]和ICAP[10]都是特征選擇領域的經典算法，FIM[11]和IWFS[12]分別是2013年和2015年提出的算法。這8種特征選擇算法都是基于信息論的過濾特征選擇算法，它們不依賴于具體的分類器，利用2個經典的分類器(1近鄰(1NN)和樸素貝葉斯(NB))對它們進行分類表現測試，并給出實驗效果圖和選出來的最高準確率，最后對8種算法在10個數據集上的運行時間進行對比。

1 信息論的一些基本概念

假設X,Y和Z是3個n維的離散隨機變量，X={x1,x2,…,xn}，Y={y1,y2,…,yn}，Z={z1,z2,…,zn}。信息熵的定義如下[13-16]：

(1)

式中：p(xi)為隨機事件xi發(fā)生的概率。

變量的不確定性越大，熵就越大，所提供的信息量也就越大。聯(lián)合信息熵的定義如下：

(2)

式中：p(xi,yj)=p(X=xi,Y=yj)。

式(2)表示隨機變量X和Y同時發(fā)生的不確定性大小。條件熵的定義如下：

(3)

式(3)表示在聯(lián)合隨機變量集XY中，所有X|Y是否發(fā)生的平均不確定的大小。

相對熵的定義如下：

(4)

由相對熵的概念可以定義平均互信息為[15]：

(5)

式(5)為互信息的定義，由定義可知互信息可以表示為熵的形式，具體如下：

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

(6)

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

(7)

I(X;Y)=H(X)+H(Y)-H(X,Y)

(8)

根據式(6)～(8)可知：平均互信息可以理解為兩個隨機變量之間的關聯(lián)程度，即給定一個隨機變量后，對另一個隨機變量不確定性的削弱程度。因而互信息取值最小為0，意味著給定一個隨機變量對確定另一個隨機變量沒有幫助，即兩個隨機變量相互獨立；最大取值為隨機變量的熵，意味著給定一個隨機變量，能完全消除另一個隨機變量的不確定性。類似于條件熵，條件互信息用相對熵表示如下：

I(X;Y|Z)=

D(P(xi,yj,zk)||P(yj|zk)P(zk))

(9)

式(9)也可以寫成如下形式:

I(X;Y|Z)=

(10)

條件互信息可以表示成熵的形式，具體如下:

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

(11)

I(X;Y|Z)=

H(XZ)+H(YZ)-H(XYZ)-H(Z)

(12)

其中，熵、條件熵、互信息、條件互信息的值均大于等于零。

2 條件相關特征選擇方法

2.1 條件相關性

特征選擇的目標是從高維特征中選出那些與類標簽最相關的一個特征子集。傳統(tǒng)的基于信息論的特征選擇算法認為候選特征與類標簽的互信息值越大代表該候選特征越重要。它們把候選特征的選擇過程看成一個個獨立的事件，而事實上，候選特征與類標簽的相關性是隨著已選特征的加入而不斷改變的。

圖1 H(Xk),H(Xs),H(Y)關系圖Fig.1 Relationship of H(Xk),H(Xs) and H(Y)

圖1中，Xk為候選特征，Xs為已選特征，Y為類標簽。傳統(tǒng)的相關性是候選特征與類標簽的互信息I(Xk;Y)，即圖1中的1+2部分，然而，從圖1中可以看出，由于2部分在之前選擇已選特征Xs的過程中已經計算過，即它同時屬于候選特征和已選特征與類標簽的相關性，所以它是候選特征與已選特征對于類標簽的冗余部分；條件相關性是指圖1中的1部分，將它定義為候選特征與類標簽的相關性，用條件互信息表示，即I(Xk;Y|Xs)。從圖1中可以看出：1部分代表候選特征與類標簽真正的相關性，有效避免了2部分產生的冗余作用。由于在特征選擇的過程中，已選特征的個數不斷增多，為考慮到所有已選特征與候選特征的冗余關系，本文提出全新的條件相關性CMI，用候選特征與類標簽在每一個已選特征條件下的條件互信息之和表示：

(13)

式中：S為已選特征集。

下面用一個例子形象地說明條件相關性與傳統(tǒng)相關性相比所具有的優(yōu)勢。

表1 樣例及類標簽Table 1 Samples and classes

如表1所示，其中Oi(i=1,2,…,6)為樣例，Xk(k=1,2,…,7)為特征，Y為類標簽。分別用條件相關性和傳統(tǒng)的相關性對表1的例子進行特征選擇。條件相關性是動態(tài)變化的，即式(13)，傳統(tǒng)的相關性為I(Xk;Y),下面根據表1分別計算兩種相關性。執(zhí)行過程如下所示。

(1)當k=1時，計算所有特征與類標簽的互信息：

I(X1;Y)=0.0817;I(X2;Y)=0.0817

I(X3;Y)=0.0817;I(X4;Y)=0.1909

I(X5;Y)=0.1909;I(X6;Y)=0.0000

I(X7;Y)=0.4591

由以上比較I(Xi;Y)，第1個被選出來的特征為X7，此時已選特征集S={X7}，候選特征集為{X1,X2,X3,X4,X5,X6}；此時，條件相關性與傳統(tǒng)相關性選擇的特征一樣，都是X7。

(2)當k=2時，計算候選特征在已選特征集下的條件互信息：

CMI(X1;Y|S)=0.0817

CMI(X2;Y|S)=0.0817

CMI(X3;Y|S)=0.2075

CMI(X4;Y|S)=0.7771×10-15

CMI(X5;Y|S)=0.0817

CMI(X6;Y|S)=0.2075

由以上比較CMI(Xi;Y|S)，第2個被選出來的特征為X3，而傳統(tǒng)的相關性算法選擇的是X4，此時已選特征集S={X7,X3}，候選特征集為{X1,X2,X4,X5,X6}。

(3)當k=3時，計算候選特征在已選特征集下的條件互信息：

CMI(X1;Y|S)=0.3333

CMI(X2;Y|S)=0.6667

CMI(X4;Y|S)=0.1258

CMI(X5;Y|S)=0.2075

CMI(X6;Y|S)=0.4591

由以上比較CMI(Xi;Y|S)，第3個被選出來的特征為X2，而傳統(tǒng)的相關性算法選擇的是X5，此時已選特征集S={X7,X3,X2}。由傳統(tǒng)的相關性選擇的特征集合為S′={X7,X4,X5}。

分析以上執(zhí)行過程可以看出：選擇第一個特征時，通過步驟(1)的計算，利用條件相關性和傳統(tǒng)相關性均選擇與類標簽最相關的特征X7，即與Y互信息的最大值。在選擇第2個特征時，按傳統(tǒng)相關性選擇X4，而利用條件相關性則選擇X3。雖然I(X4;Y)>I(X3;Y)，但是此時已選特征集S中已有X7，所以需要考慮X4和X3在已選特征X7的影響下與Y的相關性。通過計算I(X4;X7)=0.3167，I(X3;X7)=0.1110×10-15≈0可知I(X4;X7)>I(X3;X7)，即X4與X7的相關性大于X3與X7的相關性，而計算I(X4;Y|X7)=0.7771×10-15≈0，I(X3;Y|X7)=0.2075，說明X4在已選特征X7的影響下，幾乎沒有為分類提供新的信息并且與X7有較高的相關性，實質上表明X4為冗余特征，其提供了與X7相似的信息；而I(X3;Y|X7)>I(X3;Y)，說明X3在X7的影響下為分類提供了更多信息。在選擇第3個特征時，同樣需要考慮已選特征集的影響，有效剔除冗余特征，從而選擇提供更多分類信息的特征。

至此，條件相關性選擇出來的特征集合可以有效地對樣例進行分類，這個集合稱為最佳特征子集。而利用傳統(tǒng)相關性并沒有選擇出最佳特征子集。所以，通過圖1的分析和表1的例子可以看出，條件相關性與傳統(tǒng)的相關性相比具有更好的分類效果。根據條件相關性的特點，本文提出一種條件相關的特征選擇算法CRFS。

2.2 條件相關特征選擇方法

由于條件相關性的計算與傳統(tǒng)的相關性不同，它并不是將候選特征的選擇過程看成一個個獨立的事件，而是基于每一個已選特征動態(tài)變化的。根據其這一特點本文設計了一個全新的特征選擇算法：

(14)

對于每一個候選特征依次計算式(14)，將獲得的最大值對應的候選特征加入到S中，迭代此過程直到滿足規(guī)定的特征數目。具體執(zhí)行過程的偽代碼如下所示。

輸入：原始特征集F，類標簽Y，閾值K

輸出：選擇的特征對應索引集S

① S=?

② Maxs =?

③ k = 0

④ for each Xk∈F

⑤ 根據式(6)計算 I(Xk; Y)

⑥ end for

⑦ S(1) = argmax( I(Xk; Y) )

⑧ Xs=F[S(1)]

⑨ F = F - {S(1)}

⑩ k = k+1

R(Xk)=I(Xk;Y | Xs) - I(Xk;Xs)

①～③行是初始化過程，將要選擇的特征個數k設為0，臨時存放候選特征最大值的一個變量Maxs設為空，將要選擇的特征集合S設為空；④～⑥行，是算法選擇第一個特征，計算在原始特征集合F中的每一個特征與類標簽的互信息，選擇互信息最大的特征作為第一個已選特征；⑦～行，依次選擇每一個使得式(14)最大的特征，然后將該特征加入已選集合S中，不斷重復此過程，直到k達到閾值。

3 實驗結果及分析

在10個真實數據集上對條件相關特征選擇算法進行實驗，具體數據集描述如表2所示[17]。對于這些數據集，將特征子集數目限制在30個。實驗給出這10個數據集在兩個分類器1近鄰(1NN)和樸素貝葉斯(NB)上平均準確率效果圖，以及這8個特征選擇算法在10個數據集上達到的最高平均準確率。

表2 數據集描述Table 2 Description of datasets

表2中：PCMAC是文本數據；warpPIE10P和Yale屬于人臉圖像數據；lung、colon、Prostate_GE、GLIOMA、CLL_SUB_111、SMK_CAN_187和GLI_85為生物學數據。從表2和以上描述可以看出：實驗數據來源廣泛，并且數據既有多分類又有二分類。除了PCMAC和colon是離散的，其他數據集均是連續(xù)的。離散數據可以使特征選擇算法更有效，所以在本文中采用Akadi等[10]的離散方法，將所有連續(xù)數據離散化。

針對這10個真實數據集，分別對7個生物數據集采用留一法驗證，因為它們都屬于數據樣例較少，而特征數維度較高的數據結構，其他3個數據集采用10次十折交叉驗證法。對這10個數據集利用1近鄰和樸素貝葉斯兩種分類器進行分類，計算兩個分類器的平均準確率，實驗效果如圖2所示。

從圖2可以看出：條件相關特征選擇算法取得了不錯的分類效果。為了進一步證實本文算法的優(yōu)勢，表3列出了8種算法在10個數據集上執(zhí)行2個分類器獲得的最高平均準確率，其中黑色加粗數值代表8種特征選擇算法中取得的最高平均準確率的最大值。

從表3可以看出：在兩個分類器的分類下，本文算法在10個數據集中的最高平均準確率均取得最高，其中在colon和Prostate_GE兩個數據集上與JMI同時取得最高，在最后一行顯示的10個數據集的平均準確率上，8種特征選擇算法的平均最高準確率分別是87.67%，85.61%，85.59%，79.96%，83.52%，85.35%，81.68%和85.20%?？梢钥闯?條件相關特征選擇算法有明顯優(yōu)勢。

對CRFS算法的時間復雜度進行討論：假設選擇的特征數目為n，數據集總的特征數目為N，那么CRFS算法的時間復雜度為O(n×N)。事實上進行比較的其他7種算法的時間復雜度也均為O(n×N)。但由于各種算法使用的評價函數不同，導致函數值的求解效率有所差別，這將直接影響對于同一數據集各種算法的執(zhí)行時間。8種算法在10個數據集上的具體運行時間如表4所示。本次實驗在Python2.7環(huán)境下運行，電腦硬件設備配置如下：處理器為Intel(R) Core(TM)2 Quad CPU 安裝內存4.00 GB。對于CRFS、FIM、mRMR、CIFE、JMI、ICAP算法的評價函數均使用互信息、條件互信息或聯(lián)合互信息的線性組合，這些算法的執(zhí)行時間差別較小，且較IWFS和DISR運行時間較短。IWFS的評價函數使用乘法的形式，并在計算權重過程中引入了熵，增加了計算時間。DISR的評價函數使用除法的形式，并使用了計算較復雜的3個變量聯(lián)合熵H(Xk,Xs,Y)，所以DISR是執(zhí)行效率最低的一種算法。

綜上，通過與其他7種算法的分類準確率和算法執(zhí)行時間的比較可以看出，本文CRFS算法取得了不錯的效果。

圖2 10個數據集在分類器上的準確率Fig.2 Accuracy of classifier achieved with 10 data sets

表3 8種算法在分類器上的最高平均準確率比較Table 3 Comparison of highest average accuracy of 8 algorithms on classifiers %

表4 8種算法在10個數據集上的運行時間比較Table 4 Comparison of run time of 8 algorithms on 10 data sets s

4 結束語

本文提出了一種新的基于條件相關性概念的條件相關特征選擇CRFS算法，首先在理論和實驗上說明了條件相關性與傳統(tǒng)的相關性相比有一定的優(yōu)勢；然后用CRFS算法與其他7種特征選擇算法FIM，mRMR，CIFE，DISR，JMI，IWFS和ICAP在10個真實數據集上進行了對比實驗。實驗結果表明，CRFS算法具有一定的優(yōu)勢。然而，由于數據特征維數的不斷增加，數據間的關系變得越來越復雜，如何客觀、快速地找出數據間真實的關系仍是一項艱巨而緊迫的任務。在未來的研究工作中，將對不同類型的數據進行劃分，給出具體適用于某一類數據的特征選擇算法。

參考文獻：

[1] Bennasar M,Hicks Y,Setchi R. Feature selection using joint mutual information maximisation[J]. Expert Systems with Applications,2015,42(22):8520-8532.

[2] Zhao Z,Morstatter F,Sharma S,et al. Advancing feature selection research-ASU feature selection repository[J/OL]. [2017-03-02].http:∥eprints.kku.edu.sa/65/1/ZhaoEtAl.pdf.

[3] Bolón-Canedo V,Sánchez-Maroo N,Alonso-Betanzos A, et al. A review of microarray datasets and applied feature selection methods[J]. Information Sciences,2014,282(5):111-135.

[4] 劉元寧，王剛，朱曉冬，等. 基于自適應多種群遺傳算法的特征選擇[J]. 吉林大學學報：工學版，2011,41(6):1690-1693.

Liu Yuan-ning,Wang Gang,Zhu Xiao-dong,et al. Feature selection based on adaptive multi-population genetic algorithm[J]. Journal of Jilin University(Engineering and Technology Edition),2011,41(6):1690-1693.

[5] 姚登舉,楊靜,詹曉娟. 基于隨機森林的特征選擇算法[J]. 吉林大學學報：工學版,2014,44(1):137-141.

Yao Deng-ju,Yang Jing,Zhan Xiao-juan. Feature selection algorithm based on random forest[J]. Journal of Jilin University(Engineering and Technology Edition),2014,44(1):137-141.

[6] Peng H C,Long F H,Ding C. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(8):1226-1238.

[7] Yang H H, Moody J. Data visualization and feature selection: new algorithms for nongaussian data[J]. Advances in Neural Information Processing Systems,1999,12:687-693.

[8] Lin D,Tang X. Conditional infomax learning: an integrated framework for feature extraction and fusion[C]∥European Conference on Computer Vision,Graz,Austria,2006:68-82.

[9] Meyer P E,Schretter C,Bontempi G. Information-theoretic feature selection in microarray data using variable complementarity[J]. IEEE Journal of Selected Topics in Signal Processing,2008,2(3):261-274.

[10] Akadi A E,Ouardighi A E,Aboutajdine D. A powerful feature selection approach based on mutual information[J]. International Journal of Computer Science & Network Security,2008,8(4):116-121.

[11] Bennasar M,Setchi R,Hicks Y. Feature interaction maximisation[J]. Pattern Recognition Letters,2013,34(14):1630-1635.

[12] Zeng Z,Zhang H,Zhang R,et al. A novel feature selection method considering feature interaction[J]. Pattern Recognition,2015,48(8):2656-2666.

[13] 石峰,莫忠息. 信息論基礎[M]. 3版. 武漢:武漢大學出版社，2014:14-52.

[14] 趙曉群. 信息論基礎及應用[M]. 北京:機械工業(yè)出版社，2015:27-53.

[15] Zhao Juan,Zhou Yi-wei,Zhang Xiu-jun,et al. Part mutual information for quantifying direct associations in networks[J]. Proceedings of the National Academy of Sciences,2016,113(18):5130-5135.

[16] Schreiber T. Measuring information transport[J/OL]. [2017-03-06].http:∥citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3215&rep=rep1&type=pdf.

[17] Li J D,Cheng K W,Wang S H,et al. Feature selection:a data perspective[J/OL].[2017-03-06].https:∥arxiv.org/pdf/1601.07996.pdf.