馬 忱，姜高霞，王文劍

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

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

1 引言

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

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

相較于其他兩種特征選擇方法，過(guò)濾器式特征選擇方法不僅能達(dá)到多數(shù)分類器的分類精度[6]，而且計(jì)算復(fù)雜度較低。這種優(yōu)勢(shì)在處理大規(guī)模數(shù)據(jù)或在線數(shù)據(jù)等時(shí)表現(xiàn)明顯。通常情況下，過(guò)濾器方法主要有相關(guān)性度量、距離度量、信息度量[7]和一致性度量[8]等。由于信息度量是借助信息理論中互信息的概念來(lái)量化特征間的不確定性程度，故不要求預(yù)先假定數(shù)據(jù)分布是已知的，可以解決變量間的非線性關(guān)系，從整體的角度來(lái)評(píng)估特征間的相關(guān)性，剔除無(wú)關(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)的特征選擇方法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

從學(xué)習(xí)算法的角度對(duì)數(shù)據(jù)進(jìn)行分析，可將樣本分為已識(shí)別樣本和未識(shí)別樣本兩類。將已排序的特征依次加入特征子集，每加入一個(gè)新的特征，則重新使用分類器學(xué)習(xí)并分類，將可以識(shí)別的樣本從樣本集合中去除，達(dá)到相應(yīng)的停止條件則輸出最終的特征子集。本文所用的停止條件為：所有的樣本都能被正確識(shí)別或特征子集的個(gè)數(shù)已達(dá)到用戶定義的最大值δ。這意味著當(dāng)樣本集中所有樣本都能被已選的特征子集所識(shí)別，特征選擇過(guò)程將結(jié)束；或達(dá)到了特征子集所能容納特征的最大數(shù)目時(shí)，仍有部分樣本未能識(shí)別，但已超出了用戶定義的最大分類特征數(shù)，則忽略未能識(shí)別的樣本，輸出當(dāng)前特征子集；其他情況出現(xiàn)時(shí)，則繼續(xù)執(zhí)行特征選擇過(guò)程。通常情況下，函數(shù)型數(shù)據(jù)的特征子集的特征個(gè)數(shù)不超過(guò)10個(gè)，因此本文在后續(xù)實(shí)驗(yàn)中設(shè)置特征子集中特征個(gè)數(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）計(jì)算每個(gè)特征與類別之間的互信息，并將特征按照互信息值的大小降序排列，得到排序特征矩陣M。

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

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

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

通過(guò)計(jì)算每個(gè)已選特征對(duì)當(dāng)前待選特征的量化影響值，選出其中的最大值Jmax，將當(dāng)前最大值Jmax與初始最大值Imax進(jìn)行比較，如果Jmax＞Imax，則說(shuō)明待選特征在已選特征的影響下，依然帶來(lái)了較多的信息量，因此將當(dāng)前待選特征Ak加入已選特征子集，并將Imax的值更新為Jmax；反之，如果Jmax≤Imax，則說(shuō)明在已選特征的影響下，待選特征不能提供更多的信息量，則認(rèn)為當(dāng)前待選特征是冗余的或不能帶來(lái)新的信息量的，故不將當(dāng)前特征加入到已選特征子集中。每次特征子集發(fā)生變化后，都將當(dāng)前的特征子集在分類器中重新進(jìn)行學(xué)習(xí)和分類，將可以正確分類的樣本從樣本集合中去除，直到所有的樣本都被正確識(shí)別或達(dá)到用戶定義的特征子集的最大個(gè)數(shù)δ，則停止特征選擇過(guò)程。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）計(jì)算每個(gè)特征與類別之間的互信息，并將特征按照互信息值的大小降序排列，得到排序特征矩陣M。

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

（4）依次向特征子集E′中加入候選特征子集中的特征，并計(jì)算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 時(shí)間復(fù)雜度分析

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)數(shù)據(jù)采集自UCR時(shí)序分類數(shù)據(jù)集（http：//www.cs.ucr.edu/～eamonn/time_series_data/），其中二分類數(shù)據(jù)13組（序號(hào)為1～13），多分類數(shù)據(jù)10組（序號(hào)為14～23），由于采集到的數(shù)據(jù)為離散數(shù)據(jù)，因此首先將數(shù)據(jù)經(jīng)過(guò)B樣條基擬合，轉(zhuǎn)換為函數(shù)型數(shù)據(jù)，再計(jì)算出函數(shù)型數(shù)據(jù)的特征矩陣。實(shí)驗(yàn)數(shù)據(jù)詳見(jiàn)表1。數(shù)據(jù)的平滑、擬合以及實(shí)驗(yàn)部分均在Matlab環(huán)境下實(shí)現(xiàn)，所用計(jì)算機(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í)驗(yàn)數(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ī)模和分類精度的對(duì)比，并將上述結(jié)果與不進(jìn)行特征選擇而直接進(jìn)行分類（空白對(duì)照FD）的結(jié)果進(jìn)行了比較。此外，文獻(xiàn)[24]提出了一種面向函數(shù)型數(shù)據(jù)的快速特征選擇方法，本文與此方法也進(jìn)行了對(duì)比，說(shuō)明本文方法的有效性。

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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ù)目

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

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

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

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

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

（2）分類效果的比較

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

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

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

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

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

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方法中二分類和多分類問(wèn)題排名前五的方法與本文方法進(jìn)行了特征子集規(guī)模、分類精度的比較，以及選取FFS方法中不同維數(shù)凸包的特征選擇時(shí)間與本文方法進(jìn)行了比較。

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

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

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方法二分類問(wèn)題分類精度比較

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

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

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

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

4 總結(jié)

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

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