曾海亮， 林耀進*， 唐 莉， 王晨曦

(1.閩南師范大學 計算機學院, 漳州 363000) (2.數(shù)據(jù)科學與智能應用福建省高等學校重點實驗室, 漳州 363000)

在圖像識別、文本分類、生物信息學、基因微陣列分析等研究領域,數(shù)據(jù)呈現(xiàn)出高維小樣本特點,即特征空間呈現(xiàn)高維性,而樣本數(shù)量過少．另外,該類數(shù)據(jù)往往伴隨著屬性值稀疏、噪聲高、類別不平衡等問題．雖然特征空間較高的維數(shù)是獲得問題準確描述的有力保障,但存在著大量冗余、不相關(guān)和噪聲特征,易引發(fā)維數(shù)災難,在分類學習過程中出現(xiàn)過擬合．因此,對高維小樣本數(shù)據(jù)進行特征選擇具有重要意義．

在高維小樣本數(shù)據(jù)的特征選擇過程中,不僅要選擇出對分類學習性能有著極具提升作用的特征子集,而且應該注重特征選擇結(jié)果的穩(wěn)定性[1]．眾所周知,高維小樣本數(shù)據(jù)特征維數(shù)與樣本數(shù)比例不協(xié)調(diào)，使得數(shù)據(jù)本身具有較強的敏感性,即訓練樣本在微小擾動情況下會產(chǎn)生不同的特征選擇結(jié)果．為了同時兼具準確性和穩(wěn)定性,許多專家提出了不同高維小樣本數(shù)據(jù)的特征選擇算法．文獻[2]中提出一種基于迭代Lasso的信息基因選擇方法，以獲得基因數(shù)量少且分類能力較強的信息基因子集.文獻[3]中解決了計算開銷過大的問題，并在一定程度上解決了過擬合問題.從某種意義上講在線流特征選擇算法[4]、在線流標記特征選擇[5]也是處理高維數(shù)據(jù)的一種方式.文獻[6]中通過重構(gòu)鄰域粗糙集下近似算子，提出了基于特征和標記之間依賴關(guān)系的在線特征選擇模型.文獻[7]中定義一種新的具有自適應鄰域的鄰域粗糙集關(guān)系，并提出了一種基于這種關(guān)系的在線流特征選擇方法．

在高維小樣本數(shù)據(jù)中,樣本蘊含的豐富信息使得特征空間具有超高維性,如基因微陣列數(shù)據(jù)中,特征有種族、血型、生長等信息;文本文檔數(shù)據(jù)中,特征有樣式、字體、顏色等信息;圖像數(shù)據(jù)中,特征有位深、像素、飽和度等信息．這些豐富多樣的特征提供了觀察樣本的不同視圖,在基因數(shù)據(jù)中,代表種族視圖的若干屬性構(gòu)成種族特征子空間,代表血型視圖的若干屬性構(gòu)成血型特征子空間,代表生長視圖的若干屬性構(gòu)成生長特征子空間,這些視圖子空間構(gòu)成對基因數(shù)據(jù)的完整刻畫．因此,構(gòu)建多個特征子空間對高維小樣本數(shù)據(jù)進行分析不僅符合數(shù)據(jù)本身的特點,而且具有較好的準確率及魯棒性．

在高維小樣本數(shù)據(jù)的子空間[8]學習過程中,由于同一子空間的特征具有強相關(guān)性,而不同子空間的特征具有弱相關(guān)性．同時,子空間之間的差別構(gòu)成了研究對象屬性的多樣性．為此,文中引入了特征擾動策略,提出了高維小樣本數(shù)據(jù)的子空間學習算法．特征擾動策略是指在子空間學習過程中,通過判斷特征間的相關(guān)性尋出歸屬不同子空間的特征．其中,子空間特征個數(shù),即基數(shù),取與樣本個數(shù)相同，有利于化解高維小樣本數(shù)據(jù)的高維性，以及降低因特征維數(shù)與樣本數(shù)的比例不協(xié)調(diào)而引起的數(shù)據(jù)本身的敏感性．文中首先用鄰域粗糙集[9]計算各屬性重要度,選取屬性重要度最高的一個屬性作為基準屬性,接著選取和基準屬性相關(guān)性最大的前M個屬性構(gòu)成一個視圖子空間;然后,再從余下的屬性中選取屬性重要度最高的屬性作為基準屬性,重復上述步驟,直至構(gòu)造完所有子空間視圖．對各個子空間利用鄰域粗糙集進行特征選擇,集成各個子空間選擇的特征作為最終特征選擇結(jié)果．實驗結(jié)果證明所提模型能夠較好地改善高維小樣本數(shù)據(jù)的分類能力．

1 鄰域粗糙集相關(guān)知識

定義1[6]給定實數(shù)空間上的非空有限集合U={x1,x2,…,xm},對于U上的任意對象xi,定義其δ-鄰域為：

δ(xi)={x|x∈U,dist(x,xi)≤δ}

根據(jù)度量的性質(zhì),有:

(1)δ(xi)≠?,因為xi∈δ(xi)

(2)xj∈δ(xi)?xi∈δ(xj)

定義2[10]給定樣本集合U={x1,x2,…,xm},A為描述U的實數(shù)型特征集合,D為決策屬性．如果A生成論域上的一簇鄰域關(guān)系,則稱NDT=〈U,A,D〉為一個鄰域決策系統(tǒng)．

式中：

NBX={xi|δB(xi)?X,xi∈U}

定義3[10]給定一個鄰域決策系統(tǒng)NDT=〈U,A,D〉,B?A,定義決策屬性D對條件屬性B的依賴性為：

γB(D)=Card(NBD)/Card(U)

定義4[10]給定鄰域信息系統(tǒng)NDT=〈U,A,D〉,B?A,?a∈B,如果γB-a(D)<γB(D),稱a相對于B而言是必不可少的,否則,γB-a(D)=γB(D),稱a是多余的．如果?a∈B都是必不可少的,稱B是獨立的．如果γB-a(D)=γB(D),則表明從系統(tǒng)中去掉屬性a,系統(tǒng)的正域沒有發(fā)生改變,因此,各類的可區(qū)分性不變．

定義5[10]給定鄰域決策系統(tǒng)NDT=〈U,A,D〉,稱B?A是A的一個約簡,如果B滿足:

(1)?a∈B,γB-a(D)<γB(D)

(2)γB(D)=γA(D)

該定義的條件(1)要求在一個約簡中不存在多余的屬性,所有的屬性都應該是必不可少的;條件(2)要求約簡不能降低系統(tǒng)的區(qū)分能力,約簡應該與系統(tǒng)中全部條件屬性具有相同的分辨能力．

定義6[10]給定鄰域決策系統(tǒng)NDT=〈U,A,D〉,B?A,?a?B,屬性a的重要度定義為：

sig(a,B,D)=γB∪a(D)-γB(D)

2 利用特征擾動的高維小樣本數(shù)據(jù)子空間學習

為了降低高維小樣本數(shù)據(jù)中特征空間維數(shù)與樣本數(shù)之間極度不平衡帶來的分類學習過程中的過擬合,文中主要利用子空間學習方法來進行高維小樣本數(shù)據(jù)的特征選擇．首先,利用鄰域粗糙集方法依次度量各特征的重要度,選取特征重要度最高的一個特征作為基準特征,接著選取和基準特征最大相關(guān)的前M個特征構(gòu)成一個視圖子空間;其次,再從余下的特征中選取重要度最高的特征作為基準特征,重復上述步驟,直至構(gòu)造完所有視圖子空間；最后,對各個子空間利用鄰域粗糙集進行特征選擇,集成各個子空間的特征選擇結(jié)果作為最終特征選擇結(jié)果．

高維小樣本數(shù)據(jù)的特征維數(shù)遠遠大于樣本的個數(shù),導致傳統(tǒng)的分類學習方法失效．因此,通過學習多個特征子空間可避免過擬合現(xiàn)象,另外能有效地學習一組對樣本具有強判別能力的特征子集．為了構(gòu)建高維小樣本數(shù)據(jù)的多個子空間,給定訓練樣本U={x1,x2,…,xm},描述樣本的一組特征A={a1,a2,…,an},子空間屬性個數(shù)取m,則子空間個數(shù)定義為k=「n/m?．

給定k個子空間,為了保證子空間內(nèi)的屬性具有相關(guān)性,子空間之間的屬性表示描述樣本的不同視角．文中將定義基準屬性、基準屬性子空間等．

定義7給定鄰域決策系統(tǒng)NDT=〈U,A,D〉,?b∈A,稱屬性b為基準屬性,若屬性b滿足

定義8給定鄰域決策系統(tǒng)NDT=〈U,A,D〉,B?A，b為基準屬性,稱以基準屬性b為基準的屬性子空間B為基準屬性子空間,若?a∈A-b,屬性a滿足：

sig(a,b,D)≤β

式中,β為使基準屬性子空間里的屬性個數(shù)為m的參數(shù)值．

根據(jù)定義7、8,可以構(gòu)建以基準屬性b為核心的子空間,反應了子空間內(nèi)屬性之間存在強依賴,表明了該子空間刻畫了樣本集的某一固有屬性信息．另外,對于給定的高維小樣本數(shù)據(jù),可構(gòu)建k個基準屬性子空間，分別為S1={a11,a12,…,a1m},S2={a21,a22,…,a2m},…,Sk={ak1,ak2,…,akη},其中,a11,a21,…,ak1分別為基準屬性子空間S1,S2,…,Sk中的基準屬性．另外,基準屬性子空間Sk中η=n-m×?n/m」．

通過定義8可以獲得多個基準屬性子空間,這些基準屬性子空間從不同視角對樣本進行刻畫．但由于每個基準屬性子空間內(nèi)的屬性存在冗余,因此需對每個基準屬性子空間進行屬性選擇．

通過定義9,可獲得每個基準屬性空間的屬性約簡:

最后,集成基準屬性空間的屬性約簡結(jié)果即為最終選擇的屬性．具體模型見圖1.

眾所周知,通過每個基準屬性空間選擇冗余性較小的屬性,既可以保證得到在整個屬性空間上對決策屬性較重要的特征,又不會丟失對決策屬性相對次要卻關(guān)鍵的特征．

根據(jù)以上分析,利用特征擾動的高維小樣本數(shù)據(jù)子空間學習，該算法具體描述如下:

算法:利用特征擾動的高維小樣本數(shù)據(jù)子空間學習

輸入:NDT=〈U,A,D〉

輸出:約簡red

步驟：

(1) ?a∈A:計算鄰域關(guān)系Na

(2)k=「n/m?/*計算子空間數(shù)k*/

(3) ?→sel,?→sub

(4) fori=1,2,…,k-1 do

(5) ?b∈A-sel,sig(b,D)=γb(D)

(6)sig(b′,D)=maxsig(b,D)

(7)sel∪b′→sel,subi∪b′→subi

(8) forj=1,2,…,m-1 do

(9) ?a∈A-sel,sig(a,b,D)=γb∪a(D)-γb(D)

(10)sig(a′,b,D)=minsig(a,b,D)

(11)sel∪a′→sel,subi∪a′→subi

2017年，為了得到程立生的支持，使其孩子順利入學瓊臺師范學院附屬幼兒園，肖某于2017年7月份在酒店包廂送給程立生現(xiàn)金1萬元。

(12) end for

(13) end for

(14)A-sel→subk

/*余下的屬性生成一個子空間*/

(15) fori=1,2,…,kdo

(16) ?→redi/*初始化各子空間的已選特征*/

(17) ?a∈subi-redi/*此處定義γ?(D)=0*/

圖1 利用特征擾動的高維小樣本數(shù)據(jù)子空間學習Fig.1 Subspace learning of high dimensional small sample data using feature disturbance

(18)sig(a,redi,D)=γredi ∪a(D)-γredi(D)

(19)sig(a′,redi,D)=maxsig(a,redi,D)

(20) ifsig(a′,redi,D)>0 then

(21)redi∪a′→redi

(22) go to步驟(17)

(23) else

(24)red∪redi→red

(25) end if

(26) end for

(27) return red

分析該算法,可以看出其具有以下特點:

(1) 利用特征擾動劃分基準屬性子空間視圖,在基準屬性子空間視圖中計算特征的重要度．此方法簡單易行,計算復雜性較低,有效實現(xiàn)了對特征多樣性的綜合考慮．

(2) 通過計算特征空間重要度尋出基準屬性,選取與基準屬性高度相關(guān)的屬性構(gòu)建基準屬性子空間視圖,能有效增強特征選擇的靈活性．每一個基準屬性子空間視圖刻畫屬性空間某種含義,各基準屬性子空間相互獨立,合在一起構(gòu)成了對樣本空間的完整刻畫．可有效地識別出在整個條件屬性空間下與決策層性弱相關(guān)卻是隸屬對應基準屬性子空間內(nèi)與決策屬性強相關(guān)低冗余性的特征．

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

3.1 實驗數(shù)據(jù)

為了驗證SLFD算法的有效性,選取8個高維小樣本數(shù)據(jù)集進行實驗,其中數(shù)據(jù)集colon、leukemia、dlbcl、prostate、lung為二分類任務．數(shù)據(jù)集mll為三分類任務,數(shù)據(jù)集srbct為四分類任務,數(shù)據(jù)集car為十一分類任務,各數(shù)據(jù)集信息見表1．

表1 高維小樣本數(shù)據(jù)集

3.2 實驗設置

實驗全部運行在3.10 GHz處理器、4 GB內(nèi)存、Windows 7系統(tǒng)及Matlab 2013實驗平臺上．

為了驗證算法的有效性,實驗中分別與mRMR[11]、ICAP[12]、DISR[13]、MIFS[14]、CondRed[15]等經(jīng)典特征選擇算法，以及K-OFSD[6]、OFS-A3M[7]等在線特征選擇算法進行對比．參考基于鄰域?；痛植诒平臄?shù)值屬性約簡[10]中的鄰域閾值、鄰域粗糙集鄰域?；撝郸?0.1．基分類器采用RBF-SVM．實驗結(jié)果采用5折交叉驗證．由于mRMR、ICAP、DISR、MIFS、CondRed算法的特征選擇結(jié)果以特征排序,為了比較公平,其選擇的特征子集數(shù)量設置為SLFD得到的特征數(shù)．實驗結(jié)果的評價指標采用分類精度、查準率、查全率和F-Score．

3.3 實驗分析

表2～4分別給出了不同算法在數(shù)據(jù)集上平均查準率、平均查全率和平均F-Score值的結(jié)果．由表2可見：對平均查準率而言,在數(shù)據(jù)集prostate、lung、srbct、car上算法SLFD均優(yōu)于對比算法;在三分類數(shù)據(jù)集mll上算法mRMR、DISR、MIFS優(yōu)于SLFD;在數(shù)據(jù)集colon上算法mRMR和算法K-OFSD優(yōu)于SLFD;在數(shù)據(jù)集leukemia上算法OFS-A3M優(yōu)于SLFD;在數(shù)據(jù)集dlbcl上算法ICAP和算法OFS-A3M優(yōu)于子集法算法SLFD．

由表3可見：對平均查全率而言,在數(shù)據(jù)集prostate、lung、srbct、car上算法SLFD均優(yōu)于對比算法;在三分類數(shù)據(jù)集mll上算法mRMR、DISR、MIFS優(yōu)于SLFD;在數(shù)據(jù)集colon上算法K-OFSD優(yōu)于SLFD;在數(shù)據(jù)集leukemia上算法OFS-A3M與SLFD基本持平;在數(shù)據(jù)集dlbcl上算法ICAP和算法SLFD基本持平．

由表4可見：對平均F-Score值而言,算法SLFD在數(shù)據(jù)集prostate、lung、srbct、car上均優(yōu)于對比算法;在三分類數(shù)據(jù)集mll上算法mRMR、DISR、MIFS優(yōu)于SLFD;在數(shù)據(jù)集colon上算法K-OFSD優(yōu)于SLFD;在數(shù)據(jù)集leukemia上算法OFS-A3M與SLFD基本持平;在數(shù)據(jù)集dlbcl上算法ICAP和算法SLFD基本持平．

表2 平均查準率

表3 平均查全率

表4 平均F-Score值

表5給出了特征選擇后的平均分類精度和標準差,分類精度越高說明樣本分類越準確,標準差越小說明分類穩(wěn)定性越高,不難看出,在數(shù)據(jù)集dlbcl、prostate、lung、srbct、car上算法SLFD的平均分類精度均優(yōu)于對比算法；在數(shù)據(jù)集dlbcl、lung、srbct上,算法SLFD的平均標準差均小于對比算法；在數(shù)據(jù)集prostate上算法K-OFSD的平均標準差小于SLFD；在十一分類數(shù)據(jù)集car上,算法K-OFSD的平均標準差與算法SLFD持平;在三分類數(shù)據(jù)集mll上算法mRMR、DISR、MIFS的平均分類精度優(yōu)于SLFD,而在平均標準差方面,算法SLFD的平均標準差小于mRMR、DISR、MIFS,雖然算法SLFD的分類準確性不如算法mRMR、DISR、MIFS好,但其分類穩(wěn)定性較高;在數(shù)據(jù)集colon上子集法算法K-OFSD的平均分類精度優(yōu)于SLFD,而算法SLFD的平均標準差小于K-OFSD;在數(shù)據(jù)集leukemia上算法OFS-A3M的平均分類精度高于SLFD,并且平均標準差低于SLFD．

表5 平均分類精度和標準差

為了從整體上對比8種算法的分類性能隨著特征選擇的數(shù)目的變化情況．圖1～4給出了在二分類數(shù)據(jù)集lung、四分類數(shù)據(jù)集srbct上，8種算法分別以查準率、查全率、F-Score和分類精度作為評價指標時其分類性能伴隨著特征數(shù)目的變化情況．

圖1 查準率指標下各算法分類性能Fig.1 Classification performance based on precision

從平行坐標圖中可以直觀地觀察到,各個算法的查準率、查全率、F-Score都是隨著特征數(shù)目的增加而逐漸提高并趨于穩(wěn)定．對比算法mRMR、ICAP、DISR、MIFS、CondRed和算法K-OFSD、OFS-A3M,特征數(shù)目越多,算法SLFD的分類曲線浮動越小,穩(wěn)定性最好．實驗結(jié)果表明,利用特征擾動的高維小樣本數(shù)據(jù)子空間學習算法SLFD的分類性能以及魯棒性遠優(yōu)于對比算法．

圖2 查全率指標下各算法分類性能Fig.2 Classification performance based on recall

圖3 F-Score指標下各算法分類性能Fig.3 Classification performance based on F-Score

圖4 分類精度指標下各算法分類性能Fig.4 Classification performance based on accuracy

4 結(jié)論

(1) 數(shù)據(jù)擾動法并不適用于小樣本應用場景,如基因篩選、生物識別、癌癥檢測等,因為在小樣本數(shù)據(jù)上,采用數(shù)據(jù)擾動法易造成過擬合．函數(shù)擾動法對小樣本應用而言較為適用,其缺點在于難以根據(jù)數(shù)據(jù)集的特點選擇合適的特征選擇方法進行集成．

(2)特征擾動法并不存在以上問題.文中利用特征擾動對高維小樣本數(shù)據(jù)進行子空間學習,通過特征與特征的相關(guān)性尋出歸屬不同子空間視圖的特征,從而構(gòu)建多個具有差異性的子空間視圖,有助于化解高維小樣本數(shù)據(jù)的高維性和降低高維小樣本數(shù)據(jù)的敏感性．

(3)特征擾動法在高維小樣本領域極具意義和研究價值,未來將致力于研究高維小樣本數(shù)據(jù),分析特征高維性、分類魯棒性,進一步探索特征擾動的優(yōu)勢．