最優互信息特征分析論文

導語：最優互信息特征分析論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要本文提出一種新的多層神經網絡的特征提取的方法。基于所提出的每個特征的評價函數值,此方法能夠給出所有特征的排序。該方法在人造數據集和真實數據集上進行了實驗。實驗結果表明OMI能夠準確地高效地在各種數據集上鑒別出最優特征集。

關鍵詞特征選取;特征排序;神經網絡;多層神經網絡

1引言

隨著信息科學技術的快速發展,在工業界和學術界有著更復雜和更大的多變量建模問題。研究人員發現當不相關和冗余的特征向量剔除之后,模式識別技術的性能將顯著的提高。由此,特征提取成為了數據預處理和數據挖掘技術的重要的步驟之一。具體來講,特征提取有助于在線計算,加強系統的可讀性,以及提高系統的預測性能。

一般來講,特征選擇有兩大步驟:計算評價函數值和特征子集搜尋[1]。評價函數要能反映出特征向量與數據類信息的匹配度信息,以及分類器性能變化的信息。而就特征子集搜尋來講,為了避免繁冗的無遺漏搜尋,一些被大多數學者認可的搜尋方法被廣泛采用,例如:前向選擇,后向刪除,雙向搜尋等等[2]。與完全搜尋和隨即搜尋相比,這三種順序的搜尋方法都能簡單而快速的執行。

在構造輸入數據和輸出數據的復雜映射方面,由于多層神經網絡(MLP)的卓越性能,因而MLP被廣泛的采用。本文采用MLP來作為分類器,來展示各種特征選取方法在各個數據集上的分類性能。

2最優互信息

根據Shannon信息理論,一個隨機變量C的不確定性可以由熵H(C)來估計。對于兩個隨機變量X和C,條件熵可以估計當變量X已知時,變量C的不確定性。而互信息可以估計變量C和變量X的相互依賴性。從而,H(C),和三者有如下的關系[3]:

,等價于

(1)

訓練分類模型的目的是最小化已知訓練數據與類屬性數據的不確定性。若比較大,則意味著訓練數據集X所包含的信息能夠有效地預測它們的類屬性;相反地,若比較小,則意味著訓練數據集X所包含的信息不能夠有效地預測它們的類屬性。所以,訓練分類器的過程應該找一組分類器參數Θ,而盡可能增大互信息。

而對于特征選取而言,其目的是從特征全集中選取一特征子集使得互信息盡可能的大以致于特征子集F能夠有效地預測訓練數據的類屬性。也就是說,共有個F從而即可得到,我們可以選擇最大的所對應的F來作為最優的特征集來代表特征全集X。

然而,以上的描述只是考慮到了特征子集F與類屬性C有最大的相關性,F未必成為最優的特征集。例如若F中每個的特征與屬性C有最大的相關性時,它們當中有可能含有極大線性或非線性相關的特征甚至重復的特征。所以我們應該剔除掉這些冗余的特征,使得處理后的F成為新的最優的特征集。

即最小化。

因此,最大相關性和最小冗余性應同時考慮在一起。我們定義一個算子Θ將D和S結合起來來最大化Θ,從而可以同時優化D和S:

(2)

在實際中,我們可以采取前向遞增的搜尋方法,并根據(2)來找到最優的特征向量集。假設我們已經有了(m-1)個特征集Fm-1。現在的任務是要選取mth特征從。這一過程可以通過最大化Θ()來實現。也即優化下式:

(3)

其中,。

3OMI特征提取算法

通過以上分析,我們將OMI特征提取算法,表述為如下過程:

初始化:將F設為空集,X為包含所有特征的全集。

(1)計算與類屬性的互信息:對每一個特征,計算。

(2)選取第一個特征:選擇特征f,對應最大的互信息值;并且設置。

(3)遞歸計算:選擇特征f,對應最大的OMI評價函數,即:

(4)如果,回到第2步,否則F即為最終所有特征向量的排序。

需要指出的是,通過計算特征向量與類屬性的互信息值,來導出每個特征向量相關性的排序,在理論上是可以證明的。另外,OMI評價函數可以避免估算多變量的的密度函數來求互信息。例如:計算和,意味著需要先計算和。而這兩項在高維數據集的實例中,無法有效地準確地估計。而OMI中,只需計算和,意味著只需先計算和即可。通常這兩項可以用ParzenWindow,Histogram等常用的低維密度函數估計的方法來估計。

4其它特征提取算法

當今,特征提取的方法可以總體分為兩大類:過濾式和嵌入式。過濾式是指特征提取的算法與分類器的訓練算法無關;而嵌入式是指特征提取的算法與分類器的訓練算法直接相關。一般而言,過濾式的方法容易執行而且運行效率高,然而嵌入式的方法選出的特征向量更可靠但是計算量非常大。本文提出的OMI方法,在特征向量選取和排序時并未用到任何分類器的訓練算法,所以OMI屬于過濾式的特征選取方法。但是在后文的實驗部分可以看到OMI選取的特征向量比有代表性的嵌入式特征選取方法還要好。

當今有代表性的過濾式方法為FisherScore[4]。FisherScore方法通過式(4)來估計每個特征向量對不同類屬性的區分能力,從而得出所有特征的排序。

(4)

其中和分別是特征向量在第一類的均值和方差,而和分別是特征向量在第二類的均值和方差。從式(4)可以看到每個特征向量的重要性只是由均值和方差的比值來衡量。所以在高維的數據集中,其特征選取的效果并不可靠。

而有代表性的嵌入式方法有:Leave-one-out[5],Maximumoutputinformation[6]。Leave-one-out是在每刪除一個特征向量時,計算一次validation數據集上的分類器錯誤率變化。若其錯誤率變化相對較大,這可推斷此特征向量相對重要;反之相對不重要。由此,也可得出所有特征向量的排序。而最近新提出的MaximumOutputInformation方法與MLP神經網絡分類器相結合,通過計算輸出信息在神經網絡輸入層各個節點的權值的大小來選出一個最不重要的特征向量。將其剔除后再依次重復以上過程剔除每一個特征向量。最先剔除的為最不重要的特征向量,最后剔除的為最重要的特征向量。從而也可得出所有特征向量的排序。值得注意的是,這兩種嵌入式的特征選取的方法在遞歸計算各個特征向量的重要程度是都必須重新訓練分類器,所以嵌入式的特征選取方法計算效率普遍很低。

5實驗結果

5.1人造數據集

本文選取兩個被廣泛采用的人造數據集Monk和Weston數據集來展現OMI特征提取算法能夠有效地可靠地對所有特征向量進行排序。關于兩個數據集的介紹見表1。本文所有數據集的分類器采用3層MLP神經網絡。其內部節點的數目由5-foldcrossvalidation的方法來確定。

表1數據集介紹

數據集名稱MonkWeston

訓練集樣本個數432200

測試集樣本個數1249800

特征向量個數610

MLP二層節點個數56

Monk1數據集可以從UCI網站公共數據庫下載得到(archive.ics.uci.edu/ml/)。已知6個特征向量與類屬性的關系:當(f1=f2)或者(f5=1)時,樣本屬于第一類,反之屬于第二類。由此可見這個數據集只需選擇特征向量1,2,5即可。表2列出了所有特征向量的重要程度降序的排序。其Top1-Top6特征向量作為輸入,相應的測試樣本集的分類錯誤率在圖1中給出。

表2Monk數據集特征向量排序

215346

圖1Monk測試集錯誤率

我們按照Weston[5]的方法生成了Weston數據集。此數據集共有10,000個樣本,每個樣本包含10個特征向量。其中只有f1,f2是與類屬性相關的,其它的特征向量全部都是服從N(0,20)的隨機噪聲。而f1,f2分別服從和分布。在第一類中,,。而在第二類中,,。兩類中的。因而這個數據集只需選擇特征向量1,2即可。為了避免神經網絡初始值等不確定因素的影響,此實驗共運行30次。圖2中給出了Top1-Top10特征向量作為輸入,其30次平均的測試集分類錯誤率。表3列出了所有特征向量的重要程度最終的降序的排序。

表3Weston數據集特征向量排序

12107845396

圖2Weston平均測試集錯誤率

由此可見,OMI能有效地可靠地并準確地對所有特征向量進行排序。

5.2真實數據集

MOI特征向量選取方法在三個真實數據集Heart,Ionosphere和Waveform+noise上進行測試。關于三個數據集的介紹見表4。

表4數據集介紹

數據集名稱HeartIonosphereWaveformnoise

訓練集樣本個數170200400

測試集樣本個數1001514600

特征向量個數133440

MLP二層節點個數1263

第3部分所介紹FisherScore,Leave-one-out,MaximumOutputInformation與OMI按各自的特征向量排序,而后Top1-TopN特征向量作為輸入,其30次平均的測試集分類錯誤率在圖3-圖5中給出。同樣為了避免神經網絡初始值等不確定因素的影響,所有的方法在三個數據集上分別運行30次。

圖3Heart平均測試集錯誤率

圖4Ionosphere平均測試集錯誤率

圖5Waveformnoise平均測試集錯誤率

由圖5所示,OMI的方法得出特征向量排序要好于其它三個方法。盡管從上圖可知OMI在某些Top特征向量的錯誤率要低于其它三個方法,但是通過t-test的分析可以得出四種方法在這些Top特征向量的錯誤率均值可近似看作是相等的。換句話說,這三個數據集的結果均表明MOI的選出的Top特征向量不差于其它三種特征選取方法選出的Top特征向量。

就運行速度而言,FisherScore最快,OMI次之,而Leave-one-out,MaximumOutputInformation由于嵌入式方法的特性,它們必須在排完一個特征向量后,重新訓練MLP神經網絡,所以,運行時間大幅增加。

6結論

本文描述了一種基于互信息理論的特征向量選取的方法。由于具有足夠的信息理論支持,這一新的特征向量排序的評價標準式主要有兩種顯著的優越性。首先,它可以最優地或接近最優地選出用戶所需求的特征向量集。其次,這個特征向量集估計可以以集成化的方式有效進行。這第二個特性在高維數據集中尤為重要,因為它不需要任何人工的干預或調整。

而我們的逐次增加的特征向量選取方案,避免了多變量密度估計。由于其過濾式特征向量選取的本質,此方法可以與所有的分類器算法相結合,來執行各種模式識別。

在人造數據集和真實數據集的結果比較,表明OMI特征選取方法能夠顯著的提高分類精度降低運行時間。例如在神經網絡中,復雜的神經網絡結構使得在高維數據集變得無法有效地執行。而OMI特征選取可以有效地剔除高維數據集中不相關或冗余的特征向量。這將大大提高神經網絡算法的性能。

參考文獻

[1]A.L.BlumandP.Langley,“SelectionofRelevantFeaturesandExamplesinMachineLearning,”ArtificalIntelligence,vol.97,pp.245–271,1997

[2]Vapnik,V.N.,StatisticalLearningTheory.NewYork:Wiley

[3]T.M.CoverandJ.A.Thomas,ElementsofInformationtheory.NewYork:Wiley,1991

[4]Guyon.I.,andAndre.E.,“Anintroductiontovariableandfeatureselection,”JournalofMachineLearningResearch,vol.3,1157-1182

[5]Weston,J.,Mukherjee,S.,Chapelle,O.,Pontil,M.,Poggio,T.,andVapnik,V.N,“FeatureselectionforSVMs”,AdvancesinNeuralInformationProcessingSystems.,vol.13,pp.668–674

[6]V.Sindhwani,S.Rakshit,D.Deodhare,J.C.Principle,andP.Niyogi,“FeatureselectioninMLPsandSVMsbasedonmaximumoutputinformation,”IEEETrans.NeuralNetworks,vol.15,no.4,pp.937–948,July.2004