特征選擇方法中特征相關(guān)性的稀疏表示系數(shù)測度

特征選擇方法中特征相關(guān)性的稀疏表示系數(shù)測度

1特征-類別相關(guān)性測度作為一種重要的方法，資源選擇方法被廣泛應(yīng)用于各種高維小樣本數(shù)據(jù)的分類（基因表達(dá)數(shù)據(jù)、文本數(shù)據(jù)等）。特征選擇方法通常分為三種類型：菲塞爾方法、堆棧方法和消息方法。菲爾法簡單快速，不像分類器那么快。它在高維小樣本數(shù)據(jù)中得到了廣泛應(yīng)用。資源相關(guān)測量是基于特征相關(guān)測量特征或特征集的相關(guān)性。不同的資源相關(guān)測量和選擇資源相關(guān)的性質(zhì)。因此，對菲爾法和資源選擇的研究具有重要意義。近年來,各種各樣的特征相關(guān)性測度已被提出,按照功能可將它們分為特征-類別相關(guān)性測度和特征-特征相關(guān)性測度.特征-類別相關(guān)性測度專門用來評價特征對分類的重要性,常見的這類測度有T-檢驗,F-檢驗,Fisher′sRatio和ROC曲線等.它們通常假設(shè)特征所代表的樣本是有類別的,通過特征對樣本類別的區(qū)分能力來評價特征的重要性.特征-特征相關(guān)性測度通?；谛畔⒄摶蛱卣髯陨淼慕y(tǒng)計特性來評價兩個特征的相關(guān)程度,這類測度包括互信息,對稱不確定性(SymmetricalUncertainty,SU)和皮爾森相關(guān)系數(shù)(PearsonCorrelationCoefficient,PCC)等.特征-特征相關(guān)性測度也可用于評價特征的特征-類別相關(guān)性.這兩類測度的特點為假設(shè)所考察特征與其它特征是相互獨立的,測度值通常僅反映單個特征與類別,兩個特征之間的相關(guān)性,沒有反映其它特征對它們的影響.信號的稀疏表示近年來受到越來越多的關(guān)注和研究.它的基本假設(shè)是任何目標(biāo)信號都是稀疏的,只要找到合適的域就可用這個域中少量的基信號線性表示它.揭示基信號對于表示目標(biāo)信號重要與否的量稱為稀疏表示系數(shù)(SparseRepresentationCoefficient,SRC).本文提出用SRC評估特征的相關(guān)性,它與已有特征相關(guān)性測度的不同之處在于其值本身反映的就是一個特征在其它特征影響下與目標(biāo)的相關(guān)性,其中目標(biāo)可以是含類別信息的變量也可以是某個特征.為驗證SRC作為一種特征相關(guān)性測度的有效性,我們在10組典型的高維小樣本數(shù)據(jù)上對比分別以SRC,SU和PCC作為相關(guān)性測度的特征選擇方法選擇的特征集的分類能力.此外也對比以SRC為相關(guān)性測度的特征選擇方法與ReliefF方法選擇的特征集的分類能力.實驗結(jié)果表明SRC作為一種特征相關(guān)性測度是有效的.2基礎(chǔ)學(xué)習(xí)2.1稀疏表示問題設(shè)φi∈RN,i=1,2,…,M為N×1維的基信號(原子),Φ=[φ1,φ2,…,φM]為M個基信號構(gòu)成的矩陣,稱為字典,其中M≥N,β為M×1的系數(shù)向量,s為N×1的目標(biāo)信號.稀疏表示的基本問題為在Φ中選擇盡可能少的原子使得Φβ=s成立,即希望找到一個β,使得Φβ=s成立的同時,其中非0元素的個數(shù)盡可能的少.β中的元素被稱為稀疏表示系數(shù).目前求解稀疏表示問題的典型模型有基于‖β‖0最小的匹配追蹤,基于‖β‖1最小的基追蹤和基于‖β‖2最小的框架模型等.這3類模型中,基追蹤模型既可保證β的稀疏性,又可求得全局最優(yōu)解,本文使用它求解稀疏表示問題,其數(shù)學(xué)描述如下:min‖β‖1,s.t.Φβ=s.(1)式(1)是一個1范數(shù)極小化問題,它與線性規(guī)劃問題有著密切的聯(lián)系.令A(yù)=[Φ,-Φ]?b=s?c=Τ?x=[u,v]Τ?β=u-v.式(1)可轉(zhuǎn)換為標(biāo)準(zhǔn)線性規(guī)劃問題:mincTx,s.t.Ax=b,x≥0.(2)這樣任何用于求解線性規(guī)劃的方法均可求解式(1).目前常見的方法有基于內(nèi)點法的MOSEK和L1-magic及基于根求解的SPGL1等.考慮到效率問題,本文使用SPGL1方法,它的時間復(fù)雜度為O(Mlog2M).由于式(1)和式(2)的轉(zhuǎn)換關(guān)系,基追蹤是全局尋優(yōu)的,它在尋找盡可能少的原子逼近s的過程中,會考慮原子間的相互影響,以尋求最優(yōu)的原子組合.這使得βi(i=1,2,…,M)反映的是在其它原子的影響下,第i個原子對于s的重要程度,也即在其它原子的影響下,原子i與s的相關(guān)程度.2.2基于熵定義的非線性相關(guān)測度PCC是一種線性相關(guān)系數(shù),它反映兩個變量間的線性相關(guān)程度.設(shè)X,Y為隨機變量,PCC(X,Y)定義如下:ΡCC(X,Y)=∑i(xi-—xi)(yi-—yi)√∑i(xi-—xi)2√∑i(yi-—yi)2,其中,—xi?—yi分別是X,Y的均值.PCC(X,Y)的取值在-1～1之間.當(dāng)PCC(X,Y)為-1或1時,表示兩個變量完全相關(guān);當(dāng)PCC(X,Y)為0時,表示兩個變量線性無關(guān).SU是一種基于熵定義的非線性相關(guān)測度,它可揭示兩個變量間非線性的相關(guān)程度.隨機變量X的熵:Η(X)=-∑iΡ(xi)log2Ρ(xi).在觀測到隨機變量Y后,X的熵定義為H(XY)=-∑jΡ(yj)∑iΡ(xiyj)log2P(xiyj),其中,P(xi)是X=xi的概率,P(xiyi)是Y=yi的條件下,X=xi的概率.觀測到Y(jié)后,X的熵減小的量稱為信息增益,即IG(XY)=H(X)-H(XY).SU是一種規(guī)范化的信息增益:SU(X,Y)=2[ΙG(X|Y)Η(X)+Η(Y)].不難看出,SU(X,Y)∈.當(dāng)SU(X,Y)為1時,表示兩個變量完全相關(guān);當(dāng)SU(X,Y)為0時,表示兩個變量相互獨立.PCC與SU共同特點:只測度兩個變量之間的相關(guān)性,忽略其它變量對它們的影響.3稀疏表示目標(biāo)特征的求解xi=[f1,f2,…,fM]T∈RM,yi∈{1,2,…,k},k為樣本集的類別數(shù).令X=[x1,x2,…,xN]T,Y=[y1,y2,…,yN]T.由2.1節(jié)的相關(guān)理論可知,將樣本x中的特征當(dāng)作原子,如果將X當(dāng)作字典并用它取代Φ,用一個含類別信息的變量取代s,然后求解式(1),相應(yīng)的SRC反映各個特征對于稀疏表示類別變量的重要性.如果將X中的某個特征當(dāng)作目標(biāo)特征并用它取代s,將由剩余特征組成的數(shù)據(jù)當(dāng)作字典并取代Φ,然后求解式(1),則相應(yīng)的SRC反映剩余的各個特征對于稀疏表示目標(biāo)特征的重要性.3.1特征分類相關(guān)分析由于類標(biāo)僅是標(biāo)記樣本類屬的標(biāo)記,其取值可以在保證正確標(biāo)記樣本類屬的情況下任意改變,將類標(biāo)作為目標(biāo)信號,會導(dǎo)致特征的相關(guān)性隨著類標(biāo)取值的改變而改變.本文將間隔最大化判別分析(MarginMaximizingDiscriminantAnalysis,MMDA)在X上提取的第一個分量作為目標(biāo)信號.由于MMDA提取的第一個分量是數(shù)據(jù)在其最優(yōu)分類面的法方向上的投影,它不僅不會隨著類標(biāo)取值的改變而改變,而且其中兩類樣本的區(qū)分性也是最好的.本文中,MMDA的核函數(shù)采用線性核函數(shù),由于它只適合處理兩類問題,對于多類問題,采用One-vs-all策略.SRC評估特征分類相關(guān)性的方法如下.對于兩類問題:設(shè)P為MMDA在X上提取的第一個分量,揭示特征對于稀疏表示類別變量重要性的SRC向量α可通過求解下式獲得,即min‖α‖1,s.t.Xα=P.在求得α后,特征fj,j=1,2,…,M對應(yīng)的特征-類別相關(guān)性定義為SRC(fj,y)=|αj|.對于k(k>2)類問題:設(shè)Pi為第i(i=1,2,…,k)個二分類問題中MMDA在X上提取的第一個分量.第i(i=1,2,…,k)個二分類問題對應(yīng)的SRC向量αi可通過求解下式獲得,即min‖αi‖1,s.t.Xαi=Pi.在求得所有k個二分類問題對應(yīng)的SRC向量后,特征fj,j=1,2,…,M對應(yīng)的特征-類別相關(guān)性:SRC(fj,y)=k∑i=1|αij|,j=1,2,?,Μ.3.2特征fi類設(shè)特征fi,i∈{1,2,…,M}為目標(biāo)特征,由所有樣本中第i個特征構(gòu)成的向量記為Fi=[X1,i,X2,i,…,XN,i]T.由除fi以外其它特征構(gòu)成的樣本記為xji=[f1,f2,?,fi-1,fi+1,?,fΜ]Τ?j∈{1,2,?,Ν}?相應(yīng)的樣本集記為X′i=[x1i,x2i,…,xΝi]T.其它特征稀疏表示fi的系數(shù)可通過求解下式得到,即min‖αfi‖1,s.t.X′iαfi=Fi.在得到與每個特征對應(yīng)的αfi后,將各個αfi中的元素取絕對值得?αfi,i=1,2,?,Μ.令W=[?αf1,?αf2,?,?αfΜ].W(i,j)反映特征fi對于稀疏表示特征fj的重要性,W(j,i)則反映特征fj對于稀疏表示特征fi的重要性.由于W(i,j)與W(j,i)不一定相等,我們將fi和fj的特征-特征相關(guān)性定義為SRC(fi,fj)=W(i,j)+W(j,i)2.3.3評估特征相關(guān)性的時間復(fù)雜度稀疏表示問題通常假設(shè):字典Φ是超完備冗余的(即Φ中原子的個數(shù)遠(yuǎn)大于原子的維數(shù)),且僅用Φ中少量的原子即可表示目標(biāo).因此SRC適合測度高維小樣本數(shù)據(jù)中特征的相關(guān)性.理論上來講,SRC與現(xiàn)有的特征相關(guān)性測度的不同之處主要體現(xiàn)在以下方面.1)通過求解優(yōu)化問題來評估特征的相關(guān)性,一次性地解得所有特征-特征之間的相關(guān)性和特征-類別相關(guān)性,而不像傳統(tǒng)方法那樣,要分別求兩兩特征之間的相關(guān)性和每個特征與類別之間的相關(guān)性.2)所獲得的特征-特征/特征-類別相關(guān)性,是在考慮到特征之間/特征及類別之間整體關(guān)系情況下的線性表示系數(shù).顯然,這種相關(guān)性,不僅僅反映孤立的兩個特征之間的相關(guān)性和孤立的每個特征與類別之間的相關(guān)性,同時也反映其它特征對這種相關(guān)性的影響.從而這種相關(guān)性更加全面地反映特征之間/特征與類別之間的關(guān)系.這是目前常用的特征相關(guān)性測度所不具備的.3)它的計算無需樣本的統(tǒng)計分布,而傳統(tǒng)特征相關(guān)性測度(如SU和互信息等)的計算則建立在數(shù)據(jù)的統(tǒng)計分布基礎(chǔ)上的,其精度往往受到樣本數(shù)目不足的影響.由于SRC評估特征的相關(guān)性需要求解稀疏表示問題,這使得它評估特征相關(guān)性的時間復(fù)雜度大于目前常用的特征相關(guān)性測度.在特征數(shù)為M的情況下,SRC評估特征相關(guān)性的時間復(fù)雜度為O(Mlog2M),而常用的特征相關(guān)性測度評價特征的時間復(fù)雜度大多為O(M).3.4基于src的特征選擇方法目前特征選擇方法使用特征相關(guān)性測度的方式分為兩種:1)基于特征相關(guān)性測度構(gòu)建目標(biāo)函數(shù)以評價特征子集的相關(guān)性和冗余性,并通過某種搜索策略(如遺傳算法等)選擇一個使目標(biāo)函數(shù)最優(yōu)的特征子集;2)首先用特征相關(guān)性測度評估每個特征的特征-類別相關(guān)性并選擇前K個相關(guān)特征,然后根據(jù)以特征相關(guān)性測度定義的近似MarkovBlanket移除所選特征集中的冗余特征.基于第一種方式的特征選擇方法需要搜索特征子集構(gòu)成的空間,在特征個數(shù)較多時,它的計算量非常大,同時也容易使選擇的特征過于擬合訓(xùn)練數(shù)據(jù).本文側(cè)重于在高維小樣本數(shù)據(jù)中選擇特征,為此采用第二種方式,即首先通過SRC評估每個特征的特征-類別相關(guān)性并選擇相關(guān)特征,然后使用由SRC定義的近似MarkovBlanket移除冗余特征,其中由SRC定義的近似MarkovBlanket:特征fi是特征fj的近似MarkovBlanket,那么SRC(fi,y)≥SRC(fj,y)且SRC(fi,fj)≥SRC(fj,y).基于SRC的特征選擇方法(記為FS_SRC)的步驟如下.輸入樣本集S,閾值K輸出特征序列Qstep1相關(guān)分析.step1.1對每個特征fi,i=1,2,…,M,用SRC(fi,y)評估其分類相關(guān)性.step1.2按照分類相關(guān)性從大到小的順序排列特征.step1.3取前K個特征,并將他們依次加入到Q中.step2冗余分析.step2.1令i=1,L為Q中特征的個數(shù).step2.2對每個fj,j=i+1,i+2,…,L,如果SRC(fi,fj)≥SRC(fj,y),則將fj從Q中移去并L=L-1.step2.3如果i<L,i=i+1,轉(zhuǎn)到step2.2.4實驗結(jié)果和分析為驗證SRC的有效性,首先分別用FS_SRC,以SU和PCC為相關(guān)性測度的特征選擇方法及ReliefF在10組高維小樣本數(shù)據(jù)(3組UCI數(shù)據(jù),6組基因表達(dá)數(shù)據(jù)和單核苷酸多態(tài)性(SingleNucleotidePolymophism,SNP)數(shù)據(jù))上選擇特征,然后對比4種方法所選特征集的分類性能.以SU和PCC為相關(guān)性測度的特征選擇方法的流程和FS_SRC一致,只是由SU和PCC分別替換SRC評估特征的相關(guān)性,下面將它們分別記為FS_SU和FS_PCC.為使獲得的實驗結(jié)果較客觀,隨機將數(shù)據(jù)拆分為10份,其中9份用于特征選擇和構(gòu)造分類器,1份用于測試分類器的識別能力.此拆分過程重復(fù)20次,最終識別性能定義為20次拆分中測試正確率的平均值.分類器采用SVM、最近鄰分類器(NN)和樸素貝葉斯分類器(NaiveBayesClassifier,NBC),其中SVM的核函數(shù)采用線性核函數(shù),參數(shù)C的值設(shè)為1.實驗中,所有程序均由Matlab語言實現(xiàn),運行的軟件環(huán)境是WindowsXP系統(tǒng)下的Matlab7.6.0,硬件環(huán)境是CPU為XeonE5504,內(nèi)存為6GB的HP工作站.4.1k值及特征集選擇規(guī)律實驗使用3組的UCI數(shù)據(jù)為Dorothea,Dexter,Arcene.Dorothea是藥物發(fā)現(xiàn)數(shù)據(jù),Dexter是文本數(shù)據(jù),Arcene是光譜數(shù)據(jù).6組基因表達(dá)數(shù)據(jù)是前列腺癌,白血病,肺癌,淋巴瘤,小圓藍(lán)細(xì)胞瘤和腦癌.它們的信息如表1所示.在FS_SRC中,K的取值決定相關(guān)分析階段選擇多少個特征,同時也決定后續(xù)冗余分析的規(guī)模.因此,先確定K的取值是非常必要的.參照文獻(xiàn)判斷選擇相關(guān)特征個數(shù)的方法,首先用SRC評估數(shù)據(jù)中每個特征的特征-類別相關(guān)性并按照相關(guān)性從大到小的順序排列特征,然后取前K,1≤K≤250大相關(guān)特征訓(xùn)練SVM分類器并考察SVM識別性能的變化情況.相關(guān)實驗結(jié)果如圖1所示.由圖1可知,Dexter、Arcene和腦癌數(shù)據(jù)對應(yīng)的識別率曲線隨著K值的增加變化較大.當(dāng)K的取值在200附近時,這3組數(shù)據(jù)對應(yīng)的識別率曲線才趨于平穩(wěn).而其它數(shù)據(jù)對應(yīng)的識別率曲線在K接近于100時就已趨于平穩(wěn).綜合考慮各組數(shù)據(jù)的情況,我們將K的值設(shè)定為220.在K的取值確定后,我們用4種方法在UCI及基因表達(dá)數(shù)據(jù)上分別進(jìn)行特征選擇.表2記錄它們選擇的特征集分別在SVM,NN和NBC上分類性能的情況,其中括號里的數(shù)字為識別率的標(biāo)準(zhǔn)差.從識別率的角度看,在表2中,FS_SRC在Dorothea、Arcene、前列腺癌、白血病、淋巴瘤和腦癌數(shù)據(jù)上選擇的特征集在3種分類器上均獲得最高的識別率.FS_SU在肺癌數(shù)據(jù)上選擇的特征集在SVM和NN上獲得最高的識別率,在小圓藍(lán)細(xì)胞瘤數(shù)據(jù)上選擇的特征集在NBC上也獲得最好的識別性能.FS_PC在Arcene和肺癌數(shù)據(jù)上選擇的特征集在NBC上獲得最好的識別性能.ReliefF方法選擇的特征集在3種分類器上的識別率性能均低于FS_SRC.總體來講,FS_SRC在大多數(shù)數(shù)據(jù)上獲得的識別率性能高于其它方法.從識別率的標(biāo)準(zhǔn)差的角度看,在FS_SU選擇的特征集獲得最高識別率時,所獲得識別率的標(biāo)準(zhǔn)差基本上是最小的.在相同情況下(即同一組數(shù)據(jù),同一個分類器),4種方法相比,與FS_SRC對應(yīng)的標(biāo)準(zhǔn)差不是最小的,就是處于中間位置.這表明在4種方法中,FS_SU選擇的特征集在3種分類器上的識別率性能的波動性較小,即相對來講,FS_SRC選擇的特征集的分類性能更穩(wěn)定.綜上所述,FS_SRC選擇的特征集在大多數(shù)數(shù)據(jù)上獲得更高的識別率,且識別率性能更穩(wěn)定.4.2snp集的篩選SNP是單個核苷酸變異所引起的多態(tài)性,它決定生物個體的差異.本文使用的SNP數(shù)據(jù)來自國際人類基因組單體型圖計劃第二階段單體型數(shù)據(jù)的Consensus版本(可從/downloads/phasing/2006-07_phaseII/下載).包含210個樣本:45個漢族人,45個日本人,60個歐洲人和60個非洲人.每個樣本由3535418個SNP表示.由于SNP數(shù)目巨大,超出硬件的處理能力,實驗中分兩步選擇SNP.首先用修正的T-檢驗預(yù)選10萬個SNP.再由預(yù)選SNP構(gòu)成的數(shù)據(jù)上分別用4種方法選擇SNP.所選SNP集在兩種分類器上的識別率結(jié)果如表3所示.由表3可知FS_SRC選擇的SNP集在3種分類器上的分類性能是最高的也是最穩(wěn)定的.與UCI及基因表達(dá)數(shù)據(jù)相比,SNP數(shù)據(jù)的一個特點是其中四類人的可分性我們是了解的,即我們可以很容易地將歐洲人,非洲人和亞洲人(漢族人+日本人)區(qū)分開來,但