通信學(xué)論文-基于最優(yōu)互信息的特征選取.doc

通信學(xué)論文-基于最優(yōu)互信息的特征選取摘要本文提出一種新的多層神經(jīng)網(wǎng)絡(luò)的特征提取的方法?；谒岢龅拿總€(gè)特征的評(píng)價(jià)函數(shù)值，此方法能夠給出所有特征的排序。該方法在人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明OMI能夠準(zhǔn)確地高效地在各種數(shù)據(jù)集上鑒別出最優(yōu)特征集。關(guān)鍵詞特征選??；特征排序；神經(jīng)網(wǎng)絡(luò)；多層神經(jīng)網(wǎng)絡(luò)1引言隨著信息科學(xué)技術(shù)的快速發(fā)展，在工業(yè)界和學(xué)術(shù)界有著更復(fù)雜和更大的多變量建模問題。研究人員發(fā)現(xiàn)當(dāng)不相關(guān)和冗余的特征向量剔除之后，模式識(shí)別技術(shù)的性能將顯著的提高。由此，特征提取成為了數(shù)據(jù)預(yù)處理和數(shù)據(jù)挖掘技術(shù)的重要的步驟之一。具體來講，特征提取有助于在線計(jì)算，加強(qiáng)系統(tǒng)的可讀性，以及提高系統(tǒng)的預(yù)測(cè)性能。一般來講，特征選擇有兩大步驟：計(jì)算評(píng)價(jià)函數(shù)值和特征子集搜尋1。評(píng)價(jià)函數(shù)要能反映出特征向量與數(shù)據(jù)類信息的匹配度信息，以及分類器性能變化的信息。而就特征子集搜尋來講，為了避免繁冗的無遺漏搜尋，一些被大多數(shù)學(xué)者認(rèn)可的搜尋方法被廣泛采用，例如：前向選擇，后向刪除，雙向搜尋等等2。與完全搜尋和隨即搜尋相比，這三種順序的搜尋方法都能簡單而快速的執(zhí)行。在構(gòu)造輸入數(shù)據(jù)和輸出數(shù)據(jù)的復(fù)雜映射方面，由于多層神經(jīng)網(wǎng)絡(luò)(MLP)的卓越性能，因而MLP被廣泛的采用。本文采用MLP來作為分類器，來展示各種特征選取方法在各個(gè)數(shù)據(jù)集上的分類性能。2最優(yōu)互信息根據(jù)Shannon信息理論，一個(gè)隨機(jī)變量C的不確定性可以由熵H（C）來估計(jì)。對(duì)于兩個(gè)隨機(jī)變量X和C，條件熵可以估計(jì)當(dāng)變量X已知時(shí)，變量C的不確定性。而互信息可以估計(jì)變量C和變量X的相互依賴性。從而，H（C），和三者有如下的關(guān)系3：，等價(jià)于(1)訓(xùn)練分類模型的目的是最小化已知訓(xùn)練數(shù)據(jù)與類屬性數(shù)據(jù)的不確定性。若比較大，則意味著訓(xùn)練數(shù)據(jù)集X所包含的信息能夠有效地預(yù)測(cè)它們的類屬性；相反地，若比較小，則意味著訓(xùn)練數(shù)據(jù)集X所包含的信息不能夠有效地預(yù)測(cè)它們的類屬性。所以，訓(xùn)練分類器的過程應(yīng)該找一組分類器參數(shù)，而盡可能增大互信息。而對(duì)于特征選取而言，其目的是從特征全集中選取一特征子集使得互信息盡可能的大以致于特征子集F能夠有效地預(yù)測(cè)訓(xùn)練數(shù)據(jù)的類屬性。也就是說，共有個(gè)F從而即可得到，我們可以選擇最大的所對(duì)應(yīng)的F來作為最優(yōu)的特征集來代表特征全集X。然而，以上的描述只是考慮到了特征子集F與類屬性C有最大的相關(guān)性，F(xiàn)未必成為最優(yōu)的特征集。例如若F中每個(gè)的特征與屬性C有最大的相關(guān)性時(shí)，它們當(dāng)中有可能含有極大線性或非線性相關(guān)的特征甚至重復(fù)的特征。所以我們應(yīng)該剔除掉這些冗余的特征，使得處理后的F成為新的最優(yōu)的特征集。即最小化。因此，最大相關(guān)性和最小冗余性應(yīng)同時(shí)考慮在一起。我們定義一個(gè)算子將D和S結(jié)合起來來最大化，從而可以同時(shí)優(yōu)化D和S：(2)在實(shí)際中，我們可以采取前向遞增的搜尋方法，并根據(jù)(2)來找到最優(yōu)的特征向量集。假設(shè)我們已經(jīng)有了(m-1)個(gè)特征集Fm-1?，F(xiàn)在的任務(wù)是要選取mth特征從。這一過程可以通過最大化()來實(shí)現(xiàn)。也即優(yōu)化下式：(3)其中，。3OMI特征提取算法通過以上分析，我們將OMI特征提取算法，表述為如下過程：初始化：將F設(shè)為空集，X為包含所有特征的全集。(1)計(jì)算與類屬性的互信息：對(duì)每一個(gè)特征，計(jì)算。(2)選取第一個(gè)特征：選擇特征f，對(duì)應(yīng)最大的互信息值；并且設(shè)置。(3)遞歸計(jì)算：選擇特征f，對(duì)應(yīng)最大的OMI評(píng)價(jià)函數(shù)，即：(4)如果，回到第2步，否則F即為最終所有特征向量的排序。需要指出的是，通過計(jì)算特征向量與類屬性的互信息值，來導(dǎo)出每個(gè)特征向量相關(guān)性的排序，在理論上是可以證明的。另外，OMI評(píng)價(jià)函數(shù)可以避免估算多變量的的密度函數(shù)來求互信息。例如：計(jì)算和，意味著需要先計(jì)算和。而這兩項(xiàng)在高維數(shù)據(jù)集的實(shí)例中，無法有效地準(zhǔn)確地估計(jì)。而OMI中，只需計(jì)算和，意味著只需先計(jì)算和即可。通常這兩項(xiàng)可以用ParzenWindow，Histogram等常用的低維密度函數(shù)估計(jì)的方法來估計(jì)。4其它特征提取算法當(dāng)今，特征提取的方法可以總體分為兩大類：過濾式和嵌入式。過濾式是指特征提取的算法與分類器的訓(xùn)練算法無關(guān)；而嵌入式是指特征提取的算法與分類器的訓(xùn)練算法直接相關(guān)。一般而言，過濾式的方法容易執(zhí)行而且運(yùn)行效率高，然而嵌入式的方法選出的特征向量更可靠但是計(jì)算量非常大。本文提出的OMI方法，在特征向量選取和排序時(shí)并未用到任何分類器的訓(xùn)練算法，所以O(shè)MI屬于過濾式的特征選取方法。但是在后文的實(shí)驗(yàn)部分可以看到OMI選取的特征向量比有代表性的嵌入式特征選取方法還要好。當(dāng)今有代表性的過濾式方法為FisherScore4。FisherScore方法通過式(4)來估計(jì)每個(gè)特征向量對(duì)不同類屬性的區(qū)分能力，從而得出所有特征的排序。(4)其中和分別是特征向量在第一類的均值和方差，而和分別是特征向量在第二類的均值和方差。從式(4)可以看到每個(gè)特征向量的重要性只是由均值和方差的比值來衡量。所以在高維的數(shù)據(jù)集中，其特征選取的效果并不可靠。而有代表性的嵌入式方法有：Leave-one-out5，Maximumoutputinformation6。Leave-one-out是在每刪除一個(gè)特征向量時(shí)，計(jì)算一次validation數(shù)據(jù)集上的分類器錯(cuò)誤率變化。若其錯(cuò)誤率變化相對(duì)較大，這可推斷此特征向量相對(duì)重要；反之相對(duì)不重要。由此，也可得出所有特征向量的排序。而最近新提出的MaximumOutputInformation方法與MLP神經(jīng)網(wǎng)絡(luò)分類器相結(jié)合，通過計(jì)算輸出信息在神經(jīng)網(wǎng)絡(luò)輸入層各個(gè)節(jié)點(diǎn)的權(quán)值的大小來選出一個(gè)最不重要的特征向量。將其剔除后再依次重復(fù)以上過程剔除每一個(gè)特征向量。最先剔除的為最不重要的特征向量，最后剔除的為最重要的特征向量。從而也可得出所有特征向量的排序。值得注意的是，這兩種嵌入式的特征選取的方法在遞歸計(jì)算各個(gè)特征向量的重要程度是都必須重新訓(xùn)練分類器，所以嵌入式的特征選取方法計(jì)算效率普遍很低。5實(shí)驗(yàn)結(jié)果5.1人造數(shù)據(jù)集本文選取兩個(gè)被廣泛采用的人造數(shù)據(jù)集Monk和Weston數(shù)據(jù)集來展現(xiàn)OMI特征提取算法能夠有效地可靠地對(duì)所有特征向量進(jìn)行排序。關(guān)于兩個(gè)數(shù)據(jù)集的介紹見表1。本文所有數(shù)據(jù)集的分類器采用3層MLP神經(jīng)網(wǎng)絡(luò)。其內(nèi)部節(jié)點(diǎn)的數(shù)目由5-foldcrossvalidation的方法來確定。表1數(shù)據(jù)集介紹數(shù)據(jù)集名稱MonkWeston訓(xùn)練集樣本個(gè)數(shù)432200測(cè)試集樣本個(gè)數(shù)1249800特征向量個(gè)數(shù)610MLP二層節(jié)點(diǎn)個(gè)數(shù)56Monk1數(shù)據(jù)集可以從UCI網(wǎng)站公共數(shù)據(jù)庫下載得到(http：//ml/)。已知6個(gè)特征向量與類屬性的關(guān)系：當(dāng)（f1=f2）或者（f5=1）時(shí)，樣本屬于第一類，反之屬于第二類。由此可見這個(gè)數(shù)據(jù)集只需選擇特征向量1，2，5即可。表2列出了所有特征向量的重要程度降序的排序。其Top1-Top6特征向量作為輸入，相應(yīng)的測(cè)試樣本集的分類錯(cuò)誤率在圖1中給出。表2Monk數(shù)據(jù)集特征向量排序215346圖1Monk測(cè)試集錯(cuò)誤率我們按照Weston5的方法生成了Weston數(shù)據(jù)集。此數(shù)據(jù)集共有10，000個(gè)樣本，每個(gè)樣本包含10個(gè)特征向量。其中只有f1,f2是與類屬性相關(guān)的，其它的特征向量全部都是服從N（0，20）的隨機(jī)噪聲。而f1,f2分別服從和分布。在第一類中，。而在第二類中，。兩類中的。因而這個(gè)數(shù)據(jù)集只需選擇特征向量1，2即可。為了避免神經(jīng)網(wǎng)絡(luò)初始值等不確定因素的影響，此實(shí)驗(yàn)共運(yùn)行30次。圖2中給出了Top1-Top10特征向量作為輸入，其30次平均的測(cè)試集分類錯(cuò)誤率。表3列出了所有特征向量的重要程度最終的降序的排序。表3Weston數(shù)據(jù)集特征向量排序12107845396圖2Weston平均測(cè)試集錯(cuò)誤率由此可見，OMI能有效地可靠地并準(zhǔn)確地對(duì)所有特征向量進(jìn)行排序。5.2真實(shí)數(shù)據(jù)集MOI特征向量選取方法在三個(gè)真實(shí)數(shù)據(jù)集Heart，Ionosphere和Waveform+noise上進(jìn)行測(cè)試。關(guān)于三個(gè)數(shù)據(jù)集的介紹見表4。表4數(shù)據(jù)集介紹數(shù)據(jù)集名稱HeartIonosphereWaveformnoise訓(xùn)練集樣本個(gè)數(shù)170200400測(cè)試集樣本個(gè)數(shù)1001514600特征向量個(gè)數(shù)133440MLP二層節(jié)點(diǎn)個(gè)數(shù)1263第3部分所介紹FisherScore，Leave-one-out，MaximumOutputInformation與OMI按各自的特征向量排序，而后Top1-TopN特征向量作為輸入，其30次平均的測(cè)試集分類錯(cuò)誤率在圖3-圖5中給出。同樣為了避免神經(jīng)網(wǎng)絡(luò)初始值等不確定因素的影響，所有的方法在三個(gè)數(shù)據(jù)集上分別運(yùn)行30次。圖3Heart平均測(cè)試集錯(cuò)誤率圖4Ionosphere平均測(cè)試集錯(cuò)誤率圖5Waveformnoise平均測(cè)試集錯(cuò)誤率由圖5所示，OMI的方法得出特征向量排序要好于其它三個(gè)方法。盡管從上圖可知OMI在某些Top特征向量的錯(cuò)誤率要低于其它三個(gè)方法，但是通過t-test的分析可以得出四種方法在這些Top特征向量的錯(cuò)誤率均值可近似看作是相等的。換句話說，這三個(gè)數(shù)據(jù)集的結(jié)果均表明MOI的選出的Top特征向量不差于其它三種特征選取方法選出的Top特征向量。就運(yùn)行速度而言，F(xiàn)isherScore最快，OMI次之，而Leave-one-out，MaximumOutputInformation由于嵌入式方法的特性，它們必須在排完一個(gè)特征向量后，重新訓(xùn)練MLP神經(jīng)網(wǎng)絡(luò)，所以，運(yùn)行時(shí)間大幅增加。6結(jié)論本文描述了一種基于互信息理論的特征向量選取的方法。由于具有足夠的信息理論支持，這一新的特征向量排序的評(píng)價(jià)標(biāo)準(zhǔn)式主要有兩種顯著的優(yōu)越性。首先，它可以最優(yōu)地或接近最優(yōu)地選出用戶所需求的特征向量集。其次，這個(gè)特征向量集估計(jì)可以以集成化的方式有效進(jìn)行。這第二個(gè)特性在高維數(shù)據(jù)集中尤為重要，因?yàn)樗恍枰魏稳斯さ母深A(yù)或調(diào)整。而我們的逐次增加的特征向量選取方案，避免了多變量密度估計(jì)。由于其過濾式特征向量選取的本質(zhì)，此方法可以與所有的分類器算法相結(jié)合，來執(zhí)行各種模式識(shí)別。在人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的結(jié)果比較，表明OMI特征選取方法能夠顯著的提高分類精度降低運(yùn)行時(shí)間。例如在神經(jīng)網(wǎng)絡(luò)中，復(fù)雜的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)使得在高維數(shù)據(jù)集變得無法有效地執(zhí)行。而OMI特征選取可以有效地剔除高維數(shù)據(jù)集中不相關(guān)或冗余的特征向量。這將大大提高神經(jīng)網(wǎng)絡(luò)算法的性能。參考文獻(xiàn)1A.L.BlumandP.Langley，“SelectionofRelevantFeaturesandExamplesinMachineLearning，”ArtificalIntelligence，vol.97，pp.245271，19972Vapnik，V.N.，StatisticalLearningTheory.NewYork：Wiley3T.M.CoverandJ.A.Thomas，ElementsofInformationtheory.NewYork：Wiley，19914Guyon.I.，andAndre.E.，“Anintroductiontovariableandfeatureselection，”JournalofMachineLearningResearch，vol.3，1157-11825Weston，J.，Mukherjee，S.，Chapelle，O.，Pontil，M.，Poggio，T.，andVapnik，V.N，“FeatureselectionforS