面向函數(shù)型數(shù)據(jù)的動態(tài)互信息特征選擇方法*

馬 忱，姜高霞，王文劍

1.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，太原 030006

2.山西大學(xué) 計算智能與中文信息處理教育部重點(diǎn)實驗室，太原 030006

1 引言

現(xiàn)實中的數(shù)據(jù)集朝著大規(guī)模方向發(fā)展，并呈現(xiàn)指數(shù)型增長的趨勢。這種增長不僅僅是數(shù)據(jù)量的增長，數(shù)據(jù)的呈現(xiàn)形式也越來越多樣化，函數(shù)型數(shù)據(jù)[1]（functional data，F(xiàn)D）正是一種常見的、數(shù)據(jù)信息量大的數(shù)據(jù)。它是指在某個連續(xù)集（通常指時間、心理空間或物理空間等）上的一組測量，例如按時間記錄的經(jīng)濟(jì)數(shù)據(jù)，書寫時筆尖的運(yùn)動軌跡，某個時間段某個地區(qū)溫度和濕度的變化，青春期人體身高，體重的變化，人體的心電圖，語音框架數(shù)據(jù)等都是函數(shù)型數(shù)據(jù)。一般來說，函數(shù)型數(shù)據(jù)含有更多的數(shù)據(jù)特征，因此相較于傳統(tǒng)離散數(shù)據(jù)具有較好的分類性能。然而函數(shù)型數(shù)據(jù)特征維數(shù)較高，這將導(dǎo)致參數(shù)估計的準(zhǔn)確率下降，進(jìn)而直接影響學(xué)習(xí)算法的性能和效率[2]。此外，與大量數(shù)據(jù)特征同時存在的還有一些冗余特征和不相關(guān)特征，這些特征的存在會影響分類器的性能和分類效果。不僅如此，大量的冗余特征和不相關(guān)特征還會顯著增加計算的時間復(fù)雜度和內(nèi)存需求，這些不足在數(shù)據(jù)特征數(shù)目較大時尤為突出。為了克服這一問題，特征選擇往往是十分必要的。

特征選擇的主要目標(biāo)就是尋找機(jī)器學(xué)習(xí)算法性能優(yōu)化的最小子集[3]。特征選擇可以為機(jī)器學(xué)習(xí)算法帶來很多好處[4]，如降低測量成本和存儲要求，應(yīng)對由于訓(xùn)練樣本集的有限性造成的分類性能下降的問題，降低訓(xùn)練時間，便于數(shù)據(jù)的可視化和理解。機(jī)器學(xué)習(xí)的不斷進(jìn)步也在推動著特征選擇方法的發(fā)展，常見的特征選擇方法分為3類[5]：封裝式（wrapper）特征選擇方法、嵌入式（embedded）特征選擇方法和過濾器式（filter）特征選擇方法。

相較于其他兩種特征選擇方法，過濾器式特征選擇方法不僅能達(dá)到多數(shù)分類器的分類精度[6]，而且計算復(fù)雜度較低。這種優(yōu)勢在處理大規(guī)模數(shù)據(jù)或在線數(shù)據(jù)等時表現(xiàn)明顯。通常情況下，過濾器方法主要有相關(guān)性度量、距離度量、信息度量[7]和一致性度量[8]等。由于信息度量是借助信息理論中互信息的概念來量化特征間的不確定性程度，故不要求預(yù)先假定數(shù)據(jù)分布是已知的，可以解決變量間的非線性關(guān)系，從整體的角度來評估特征間的相關(guān)性，剔除無關(guān)特征，有效地選出關(guān)鍵特征[9]，因此被廣泛應(yīng)用于濾波方法[10]。目前已經(jīng)提出了許多基于熵作為特征選擇模型[11-12]。Lewis[13]提出最基本的基于互信息的信息增益理論，在此基礎(chǔ)上，Battiti[14]的互信息特征選擇（mutual information for selecting features，MIFS）方法和Peng等人[15]的最大相關(guān)最小冗余（max-relevance and min-redundancy，mRMR）方法豐富了互信息理論。隨著互信息理論的發(fā)展，產(chǎn)生有聯(lián)合互信息理論[16-19]和條件互信息理論[20-21]指導(dǎo)的特征選擇方法。

以上方法對傳統(tǒng)數(shù)據(jù)是有效的，但是并不能很好地完成函數(shù)型數(shù)據(jù)的特征選擇，將合適的特征選擇方法用于函數(shù)型數(shù)據(jù)分析是簡化計算和提高數(shù)據(jù)可分性判據(jù)的有效手段，如Gómez-Verdejo等人[22]在Kraskov等人[23]的互信息理論基礎(chǔ)上提出一種改進(jìn)的條件互信息特征選擇方法，可以不受概率分布和數(shù)據(jù)形式的影響，更好地適合于函數(shù)型數(shù)據(jù)的分類問題。然而在特征選擇過程中需要用搜索策略和評價函數(shù)來共同完成，這就導(dǎo)致了以下兩方面問題：一是搜索過程的隨機(jī)性導(dǎo)致每次特征選擇結(jié)果的不確定性，使該方法不穩(wěn)定；二是每次迭代結(jié)束后可識別樣本對再次計算評價函數(shù)的影響，造成特征子集分類精度的降低。因此本文針對這兩個問題，提出了關(guān)于函數(shù)型數(shù)據(jù)的動態(tài)互信息特征選擇方法。此外，在動態(tài)互信息特征選擇方法的基礎(chǔ)上，考慮已選特征對待選特征影響，提出一種動態(tài)條件互信息特征選擇方法。在UCR數(shù)據(jù)集上的實驗結(jié)果表明方法的有效性。

2 動態(tài)互信息特征選擇方法

在特征選擇中，最優(yōu)特征子集是一個與類高度相關(guān)，但不互相關(guān)聯(lián)的特征集合，信息論的方法在量化的特征不確定程度度量上有很大的優(yōu)勢。傳統(tǒng)的信息論特征選擇方法屬于過濾器特征選擇方法，即選定某一評價函數(shù)來對特征進(jìn)行評價。這一過程往往伴隨著特征的遍歷過程選擇不同的遍歷方法可能得到不同的特征子集，使特征選擇的結(jié)果不具有穩(wěn)定性，且在每次搜索過程中往往會出現(xiàn)信息的冗余，因而本文提出的動態(tài)選擇過程避免了信息冗余的出現(xiàn)，分類器的分類結(jié)果直接判定每次迭代過程，可以提高特征選擇過程的時間效率和特征選擇結(jié)果的分類精度。

本文所指動態(tài)的過程是每個特征所帶來的信息對學(xué)習(xí)器分類的影響，每次縮小樣本集，將可以識別的樣本去除，不僅避免了可識別樣本的信息冗余，同時在樣本量高的數(shù)據(jù)集中可以明顯縮短特征選擇的時間。

2.1 函數(shù)型數(shù)據(jù)特征矩陣

為保證函數(shù)型數(shù)據(jù)信息的完整性，本文將得到的數(shù)據(jù)采用以下兩種方法進(jìn)行處理。將采集到的離散數(shù)據(jù)，先經(jīng)過B-樣條基擬合，轉(zhuǎn)換為函數(shù)型數(shù)據(jù)，再將離散數(shù)據(jù)采用五階多項式擬合，通過統(tǒng)計擬合后的各點(diǎn)對應(yīng)的函數(shù)特性，得到函數(shù)型數(shù)據(jù)的特征矩陣。具體過程如下：

（1）將一個序列數(shù)為m的函數(shù)型數(shù)據(jù)表示為FD：

（2）在每個數(shù)據(jù)上取n個采樣點(diǎn)，用采樣點(diǎn)處的一階導(dǎo)數(shù)、與坐標(biāo)軸所圍成的面積、五階多項式系數(shù)、波動范圍和基本統(tǒng)計學(xué)信息表示每個樣本的特征向量Ai：

其中，fi′(xj)表示fi(x)在xj(j=1,2,…,n)處的一階導(dǎo)數(shù)；S表示與坐標(biāo)軸圍成的面積；C5,C4,…,C0表示五階多項式系數(shù)；μ、σ、κ、β分別表示均值、標(biāo)準(zhǔn)差、峰度和偏度。

（3）得到的函數(shù)數(shù)據(jù)特征矩陣E為：

2.2 動態(tài)互信息特征選擇

熵（entropy）表達(dá)的是某個系統(tǒng)的混亂程度，系統(tǒng)越混亂，其熵值就越高；反之，系統(tǒng)越有序，則其對應(yīng)的熵值也就越低。信息理論中，熵通常也稱作信息熵或Shannon熵。它主要采用數(shù)值形式表達(dá)隨機(jī)變量取值的不確定性程度，目的是刻畫信息含量的多少。假定X、Y、Z是3個隨機(jī)變量，X={x1,x2,…,xL},Y={y1,y2,…,yM},Z={z1,z2,…,zN},p(?)表示變量取值的概率，則X的不確定程度表示為它的信息熵：

條件熵定義為在已知一個變量的條件下，另外一個變量的不確定性程度：

互信息（mutual information）是為了衡量兩個變量間相互依賴強(qiáng)弱程度而引入的，它表示兩個變量間共同擁有信息的含量。將兩個變量之間的互信息定義為：

條件互信息是指給定某個隨機(jī)變量的條件下，其他兩個變量之間的相互依賴程度。也就是說，它是表達(dá)在已知某種情況發(fā)生的情況下，其余事物之間的相互關(guān)聯(lián)程度，即當(dāng)隨機(jī)變量Z已知時，變量X和Y關(guān)于Z的條件互信息為：

特征選擇的目的是盡可能地選擇保留原始特征信息的特征子集?；谛畔⒄摰奶卣鬟x擇方法分為特征冗余項和特征關(guān)聯(lián)項兩部分。無論是線性方法還是非線性方法，通常的標(biāo)準(zhǔn)是最小化特征冗余，同時最大化特征相關(guān)度。在基于信息理論的特征選擇中，通常選擇某一信息量的值作為特征選擇的評價函數(shù)，通過某一搜索策略進(jìn)行特征過濾，從而從特征集合中選出當(dāng)前方法所認(rèn)為的最優(yōu)特征子集。

以基本互信息理論為評價函數(shù)，計算函數(shù)特征矩陣E中的每個特征Ai與類標(biāo)簽Y的互信息：

其中，p(?)為概率值。將得到的每個特征的互信息值進(jìn)行重新排序，按照值的大小降序排列得到排序的特征矩陣M，這意味著在后續(xù)特征選擇過程中，互信息值大的特征將被優(yōu)先考慮加入特征子集中。

從學(xué)習(xí)算法的角度對數(shù)據(jù)進(jìn)行分析，可將樣本分為已識別樣本和未識別樣本兩類。將已排序的特征依次加入特征子集，每加入一個新的特征，則重新使用分類器學(xué)習(xí)并分類，將可以識別的樣本從樣本集合中去除，達(dá)到相應(yīng)的停止條件則輸出最終的特征子集。本文所用的停止條件為：所有的樣本都能被正確識別或特征子集的個數(shù)已達(dá)到用戶定義的最大值δ。這意味著當(dāng)樣本集中所有樣本都能被已選的特征子集所識別，特征選擇過程將結(jié)束；或達(dá)到了特征子集所能容納特征的最大數(shù)目時，仍有部分樣本未能識別，但已超出了用戶定義的最大分類特征數(shù)，則忽略未能識別的樣本，輸出當(dāng)前特征子集；其他情況出現(xiàn)時，則繼續(xù)執(zhí)行特征選擇過程。通常情況下，函數(shù)型數(shù)據(jù)的特征子集的特征個數(shù)不超過10個，因此本文在后續(xù)實驗中設(shè)置特征子集中特征個數(shù)最大值δ為10。DMI（dynamic mutual information）算法的主要步驟總結(jié)如下。

算法1DMI算法

輸入：序列數(shù)為m的函數(shù)型數(shù)據(jù)FD。

輸出：最優(yōu)特征子集E′。

（1）將函數(shù)型數(shù)據(jù)按照式（2）和式（3）求得函數(shù)型數(shù)據(jù)的特征矩陣E，初始化空的最優(yōu)特征子集E′。

（2）計算每個特征與類別之間的互信息，并將特征按照互信息值的大小降序排列，得到排序特征矩陣M。

（3）將特征矩陣M中每一個特征按順序加入特征子集E′，每次循環(huán)過程在LIBSVM分類器中進(jìn)行學(xué)習(xí)和分類，每次將可以正確分類的樣本去掉，如果所有樣本都被正確分類或達(dá)到用戶定義的特征最大數(shù)閾值δ，輸出當(dāng)前特征子集E′。

2.3 動態(tài)條件互信息特征選擇

考慮到在特征選擇過程中已經(jīng)選入特征子集中的特征對未選入特征子集的特征會有一定的影響，將特征選擇過程中特征集合的變化分為兩類：已選特征集和待選特征集。初始狀態(tài)時，待選特征子集為所有特征的集合，已選特征子集為空集。隨著特征選擇過程的進(jìn)行，在考察每個待選特征時，都考慮每個已選特征對它的影響。因此，本文用J(?)表示評價函數(shù)，用Aj表示已選特征，Ak表示待選特征，Y表示類標(biāo)簽，則已選特征對待選特征的影響表示為它們之間的條件互信息，即：

通過計算每個已選特征對當(dāng)前待選特征的量化影響值，選出其中的最大值Jmax，將當(dāng)前最大值Jmax與初始最大值Imax進(jìn)行比較，如果Jmax＞Imax，則說明待選特征在已選特征的影響下，依然帶來了較多的信息量，因此將當(dāng)前待選特征Ak加入已選特征子集，并將Imax的值更新為Jmax；反之，如果Jmax≤Imax，則說明在已選特征的影響下，待選特征不能提供更多的信息量，則認(rèn)為當(dāng)前待選特征是冗余的或不能帶來新的信息量的，故不將當(dāng)前特征加入到已選特征子集中。每次特征子集發(fā)生變化后，都將當(dāng)前的特征子集在分類器中重新進(jìn)行學(xué)習(xí)和分類，將可以正確分類的樣本從樣本集合中去除，直到所有的樣本都被正確識別或達(dá)到用戶定義的特征子集的最大個數(shù)δ，則停止特征選擇過程。DCMI（dynamic conditional mutual information）算法的主要步驟總結(jié)如下。

算法2DCMI算法

輸入：序列數(shù)為m的函數(shù)型數(shù)據(jù)FD。

輸出：最優(yōu)特征子集E′。

（1）將函數(shù)型數(shù)據(jù)按照式（2）和式（3）求得函數(shù)型數(shù)據(jù)的特征矩陣E，初始化空的最優(yōu)特征子集E′，最大條件互信息值為0。

（2）計算每個特征與類別之間的互信息，并將特征按照互信息值的大小降序排列，得到排序特征矩陣M。

（3）將排序特征矩陣M中前兩個特征X1和X2加入已選特征子集E′，將J=I(X2;Y|X1)置為最大值Jmax。

（4）依次向特征子集E′中加入候選特征子集中的特征，并計算J(?)值，如果所有樣本都被正確分類或達(dá)到用戶定義的特征最大數(shù)閾值δ，輸出當(dāng)前特征子集E′。

（5）如果當(dāng)前J(?)小于或等于Jmax，則將當(dāng)前特征從E′中丟棄；如果當(dāng)前J(?)大于Jmax，則更新Jmax為當(dāng)前J(?)值，使用LIBSVM分類器進(jìn)行學(xué)習(xí)和分類，將可以正確分類的樣本去掉，返回步驟4。

2.4 時間復(fù)雜度分析

對于m×n維函數(shù)型數(shù)據(jù)特征矩陣，m為樣本個數(shù)，n為特征數(shù)，k為特征選擇迭代次數(shù)，k的最大值為n。

在互信息估值階段，計算的時間復(fù)雜度為O(n2)，在迭代計算過程中，時間復(fù)雜度為O(kmn)或O(k2mn)。在實際計算過程中，時間復(fù)雜度和其他基于互信息理論的特征選擇方法相同，需花費(fèi)較多的時間。

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)與實驗設(shè)計

實驗數(shù)據(jù)采集自UCR時序分類數(shù)據(jù)集（http：//www.cs.ucr.edu/～eamonn/time_series_data/），其中二分類數(shù)據(jù)13組（序號為1～13），多分類數(shù)據(jù)10組（序號為14～23），由于采集到的數(shù)據(jù)為離散數(shù)據(jù)，因此首先將數(shù)據(jù)經(jīng)過B樣條基擬合，轉(zhuǎn)換為函數(shù)型數(shù)據(jù)，再計算出函數(shù)型數(shù)據(jù)的特征矩陣。實驗數(shù)據(jù)詳見表1。數(shù)據(jù)的平滑、擬合以及實驗部分均在Matlab環(huán)境下實現(xiàn)，所用計算機(jī)環(huán)境為Intel?CoreTM2 Duo CPU，2.93 GHz和2.94 GHz，內(nèi)存8 GB，64位操作系統(tǒng)。

Table 1 Experimental datasets表1 實驗數(shù)據(jù)集

將本文提出的DMI方法和DCMI方法與基于函數(shù)型數(shù)據(jù)的條件互信息CMI（conditional mutual information）[17]特征選擇方法、最大相關(guān)最小冗余（mRMR）[15]方法和最大條件互信息方法（conditional mutual information maximize，CMIM）[20]進(jìn)行所選特征子集規(guī)模和分類精度的對比，并將上述結(jié)果與不進(jìn)行特征選擇而直接進(jìn)行分類（空白對照FD）的結(jié)果進(jìn)行了比較。此外，文獻(xiàn)[24]提出了一種面向函數(shù)型數(shù)據(jù)的快速特征選擇方法，本文與此方法也進(jìn)行了對比，說明本文方法的有效性。

3.2 實驗結(jié)果及分析

（1）特征子集規(guī)模的比較

因為mRMR方法和CMIM方法得到的是特征集合的排序，并未給出確定的特征數(shù)目，所以本文只比較了DMI方法和DCMI方法與CMI方法最優(yōu)特征子集之間的特征規(guī)模差異。

每種方法選出的最優(yōu)特征子集數(shù)目如表2和表3所示。表中加粗項為當(dāng)前數(shù)據(jù)中所選特征子集數(shù)目最小值。從表中可看出，在二分類問題和多分類問題中，3種方法的所選特征子集的特征數(shù)目都遠(yuǎn)小于函數(shù)型數(shù)據(jù)的原始特征集合。在大多數(shù)數(shù)據(jù)集上，特征比例不足10%，只有少數(shù)數(shù)據(jù)集特征比例高于10%，但這種情況出現(xiàn)時原始特征數(shù)據(jù)也較少（不足100）。在二分類問題中，CMI方法所選特征子集規(guī)模最小的情況只出現(xiàn)在一個數(shù)據(jù)集中，有兩個數(shù)據(jù)集的特征子集規(guī)模與DCMI方法相同且達(dá)到最小；在多分類問題中，各數(shù)據(jù)集的最小規(guī)模特征子集均出現(xiàn)在DMI方法或DCMI方法中，且在部分?jǐn)?shù)據(jù)集上遠(yuǎn)小于CMI方法。由此可見，DMI方法和DCMI方法的特征子集規(guī)模是較小的，在后期的分類計算中具有一定的優(yōu)勢。

Table 2 Feature number of each method in binary classification表2 二分類特征選擇特征數(shù)目

Table 3 Feature number of each method in multi-class classification表3 多分類特征選擇特征數(shù)目

為了更好地比較特征選擇過程所選特征的數(shù)目，計算出所選特征數(shù)目占總特征的比例，如圖1和圖2所示。從圖中可看出，在二分類問題中，CMI方法所選特征的比例在9組數(shù)據(jù)上都高于DMI方法和DCMI方法，說明在二分類問題中，DMI方法和DCMI方法都能獲得較小的特征子集，對于數(shù)據(jù)的簡化效果明顯；DCMI方法在5組數(shù)據(jù)上特征比例低于DMI方法，說明在二分類問題中DMI方法和DCMI方法在所選特征子集規(guī)模方面效果相近。在多分類問題中，CMI方法所選特征的比例在8組數(shù)據(jù)上都高于DMI方法和DCMI方法，且CMI方法特征數(shù)目比DMI方法和DCMI方法多出的特征數(shù)目遠(yuǎn)大于CMI方法比DMI方法和DCMI方法少的情況，同樣說明DMI方法和DCMI方法可以獲得較小的特征子集即可完成相應(yīng)的分類問題；DMI方法和DCMI方法選擇的特征比例相近，所選特征個數(shù)相同的有3組數(shù)據(jù)，且特征子集規(guī)模最大相差為8個特征，說明這兩種方法在特征子集的規(guī)模上效果相近。

Fig.1 Feature ratio of each method in binary classification圖1 二分類各方法特征比例

Fig.2 Feature ratio of each method in multi-class classification圖2 多分類各方法特征比例

特征個數(shù)和特征比例的平均值如表4所示。從表中可看出CMI方法的特征個數(shù)和特征比例都明顯大于DMI方法和DCMI方法，故從整體上看，本文提出的方法得到的特征子集規(guī)模小于CMI方法。

Table 4 Average of feature number and feature ratio表4 特征個數(shù)和特征比例平均值

（2）分類效果的比較

將DMI方法和DCMI方法與3種對比方法CMI、mRMR和CMIM進(jìn)行分類精度的比較。其中，DMI、DCMI和CMI的最優(yōu)特征子集與表2和表3相同，參照DMI方法和DCMI方法得到的特征子集規(guī)模，將對比方法mRMR方法和CMIM方法的特征子集數(shù)目設(shè)為10，既保證了這兩種方法的分類精度較高，同時保證了參與對比的各方法特征子集規(guī)模相近，最大程度上保證了對比的公平性。

每種方法在各個數(shù)據(jù)集上的分類精度如表5和表6所示。表中詳細(xì)記錄了二分類問題和多分類問題在4種不同情況下進(jìn)行特征選擇的結(jié)果所對應(yīng)的特征子集分類精度，以及各方法在不同數(shù)據(jù)上的精度平均值。從表中可看出DMI和DCMI方法的精度明顯好于其他方法，且在精度的平均值方面得到印證。此外，DCMI方法的分類精度效果也優(yōu)于DMI方法。在二分類問題中，除個別數(shù)據(jù)集（數(shù)據(jù)集6）外，DMI方法具有較好的分類效果，說明DMI方法在一定程度上克服了傳統(tǒng)互信息特征選擇方法的不足，在特征子集的分類精度上有了一定的提高；DCMI方法在大多數(shù)數(shù)據(jù)集上的分類精度較好，在表現(xiàn)不是最好的數(shù)據(jù)集上，與分類精度最高的方法差別較小，如數(shù)據(jù)集4、9和13。在多分類問題中，有7組數(shù)據(jù)在使用DMI方法和DCMI方法時，分類效果明顯好于其他方法，且提高明顯，說明DMI方法和DCMI方法在多分類問題中有較高的特征選擇效果，較高的分類精度；DCMI方法的分類精度在5個數(shù)據(jù)集上好于DMI方法，說明這兩種方法在分類精度上的差別并不明顯，但相較于DMI方法分類精度好于DCMI方法的情況，DCMI方法好于DMI方法時，精度差別更為明顯，反映出DCMI方法在多數(shù)情況下，能保持較高的分類精度。

為了更好地描述每種方法在各個數(shù)據(jù)集上的分類精度，弱化不同數(shù)據(jù)集之間分類精度的差異，將每種方法在對應(yīng)數(shù)據(jù)集上的分類效果進(jìn)行排序，每種方法對應(yīng)排名的頻次統(tǒng)計見表7和表8，表中的列表示方法，行表示方法排名，內(nèi)容為當(dāng)前方法對應(yīng)名次的頻次。如果兩種方法的分類精度相同，本文采取的方法是并列排名。從表中可看出，在二分類問題中，DCMI方法排名第一的頻率最高，且沒有排名最低的情況，說明DCMI方法在二分類問題的特征選擇分類精度優(yōu)勢明顯，有較好的分類效果，DMI方法次之。在多分類問題中，DMI方法和DCMI方法的分類精度排名都排在前兩位，DCMI方法略好于DMI方法，說明DMI方法和DCMI方法好于其他方法，且效果穩(wěn)定。

Table 5 Accuracy of each method in binary classification表5 二分類問題各方法精度 %

Table 6 Accuracy of each method in multi-class classification表6 多分類問題各方法精度 %

Table 7 Rank frequency of each method in binary classification表7 二分類各方法排名頻數(shù)

Table 8 Rank frequency of each method in multi-class classification表8 多分類各方法排名頻數(shù)

（3）與文獻(xiàn)[24]中方法的比較

將DMI和DCMI方法與文獻(xiàn)[24]中的FFS（fast feature selection）方法進(jìn)行比較。分別選取FFS方法中二分類和多分類問題排名前五的方法與本文方法進(jìn)行了特征子集規(guī)模、分類精度的比較，以及選取FFS方法中不同維數(shù)凸包的特征選擇時間與本文方法進(jìn)行了比較。

將DMI、DCMI方法的所選特征比例與FFS方法在二分類和多分類問題精度排名前五方法進(jìn)行比較，結(jié)果如圖3和圖4所示。在二分類問題中，F(xiàn)FSF-3和FFS-3方法、FFSF-5和FFS-5方法的特征比例相同，為使數(shù)據(jù)展示更加清晰，故采用相同的線型；在多分類問題中，F(xiàn)FS-2和FFSF-2方法亦采用這種處理方式。在二分類問題和多分類問題中，DMI方法和DCMI方法的所選特征比例介于二維凸包和三維凸包的FFS方法之間，這三者特征比例差別較小，且選擇的特征子集規(guī)模較小。由此可見，DMI方法和DCMI方法的所選特征比例與FFS方法中凸包維數(shù)較小的方法相近。從圖中可明顯看出，隨著凸包維數(shù)的增加，F(xiàn)FS方法的所選特征比例會逐漸增加，且增加的幅度較大，而DMI方法和DCMI方法則不會出現(xiàn)該類問題，這兩種方法能夠保持較小的特征子集規(guī)模。

為清楚地表示二分類問題和多分類問題中FFS各方法和DMI方法、DCMI方法特征選擇結(jié)果之間的分類精度差異，將比較結(jié)果描述為箱線圖，如圖5和圖6所示。圖中符號“+”表示當(dāng)前方法在不同數(shù)據(jù)上的平均分類精度，箱中橫線表示中值，線端表示當(dāng)前方法的最值，箱端表示上、下四分位數(shù)。從圖中可看出，在二分類問題中，各方法在不同數(shù)據(jù)集上所能達(dá)到的最大分類精度相差較小，DMI方法和DCMI方法的平均分類精度均好于FFS方法，且DCMI方法優(yōu)勢明顯，具體表現(xiàn)為：（1）均值和中值均優(yōu)于其他方法，說明DCMI方法在多數(shù)數(shù)據(jù)集上的分類精度較好，且不受異常值影響；（2）在分類精度最差的數(shù)據(jù)集上表現(xiàn)明顯優(yōu)于其他方法。在多分類問題中，DMI方法和DCMI方法的平均分類精度略遜色于FFS方法中效果最好的方法，但這個差距并不明顯；DMI方法的表現(xiàn)不穩(wěn)定，受數(shù)據(jù)集的影響較大；DCMI方法可達(dá)到與其他方法相近的精度，且中值大于其他方法，說明在多數(shù)數(shù)據(jù)上有較好的分類結(jié)果。由此說明，本文提出的方法在二分類數(shù)據(jù)的特征選擇問題中有較明顯的優(yōu)勢。

Fig.3 Feature ratio of FFS&DMI in binary classification圖3 FFS和DMI方法二分類方法特征比例

Fig.4 Feature ratio of FFS&DMI in multi-class classification圖4 FFS和DMI方法多分類方法特征比例

Fig.5 Accuracy of FFS&DMI in binary classification圖5 FFS和DMI方法二分類問題分類精度比較

Fig.6 Accuracy of FFS&DMI in multi-class classification圖6 FFS和DMI方法多分類問題分類精度比較

FFS方法的優(yōu)勢就是特征選擇的時間較短，因此本文也比較了在特征選擇時間上二者的差異。由于在二分類問題和多分類問題中該特性有相似的表現(xiàn)，故本文只比較了二分類問題中FFS方法在2、3、5、8維凸包上的特征選擇時間與DMI、DCMI方法的特征選擇時間，如圖7所示。因時間差別較大，故圖中采用以10為底數(shù)的對數(shù)坐標(biāo)軸。從圖中明顯看出，F(xiàn)FS方法在各維數(shù)的凸包中的特征選擇時間均明顯少于DMI方法和DCMI方法。

Fig.7 Time cost of FFS&DMI in binary classification圖7 FFS和DMI方法二分類方法特征選擇時間

綜上所述，DMI方法和DCMI方法能達(dá)到較好分類精度，且能選擇更少的特征個數(shù)，這在后期簡化分類器計算中有較大的應(yīng)用價值。然而這兩種方法也存在現(xiàn)有互信息方法共有的缺點(diǎn)，即特征選擇過程中時間代價較大。因此，這也是本文今后需改進(jìn)的方向。

4 總結(jié)

綜合考慮特征選擇過程中特征組合變化對樣本的影響，本文提出了一種動態(tài)互信息特征選擇方法，將該方法與分類器結(jié)合，最終給出特征選擇的特征子集和特征子集對應(yīng)的特征分類精度。此外，考慮到特征選擇過程中已選特征對待選特征的影響，本文提出了動態(tài)條件互信息特征選擇方法，優(yōu)先考慮待選特征是否在已選特征的影響下，為數(shù)據(jù)帶來了新的數(shù)據(jù)信息。實驗結(jié)果表明，這兩種方法明顯好于已有的互信息特征選擇方法，且DCMI方法在特征子集的分類精度和特征子集的規(guī)模上較好于DMI方法。

因互信息特征選擇方法在特征選擇中會花費(fèi)較多的時間代價，故優(yōu)化算法以提高特征選擇效率將是未來工作的重要內(nèi)容。