基于抗噪聲鄰域粗糙集的在線流特征選擇算法

曾藝祥,林耀進(jìn),李育林,王晨曦

(閩南師范大學(xué) 計(jì)算機(jī)學(xué)院,福建 漳州 363000) (數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室,福建 漳州 363000)

1 引 言

開放動(dòng)態(tài)環(huán)境下機(jī)器學(xué)習(xí)常常面臨著數(shù)據(jù)的維數(shù)災(zāi)難問題,特征選擇作為降低特征維度的預(yù)處理技術(shù)得到了廣泛的應(yīng)用.特征選擇[1-3]是指在原始高維特征空間中,不損失信息的情況下,選擇一個(gè)最優(yōu)的特征子集,降低數(shù)據(jù)的特征維度,從而提高機(jī)器學(xué)習(xí)性能.傳統(tǒng)的特征方法假設(shè)特征空間是固定的、大小已知的.然而,在一些應(yīng)用場(chǎng)景當(dāng)中,特征往往是動(dòng)態(tài)生成并隨時(shí)間的推移逐漸流入特征空間.例如,在環(huán)境監(jiān)測(cè)當(dāng)中,一些新的傳感器會(huì)被逐步部署,從而帶來了新的數(shù)據(jù)特征[4];在入侵檢測(cè)當(dāng)中,系統(tǒng)會(huì)實(shí)時(shí)檢測(cè)不同數(shù)據(jù)包從而產(chǎn)生新的特征[5].為解決在線流特征空間維數(shù)災(zāi)難問題,許多在線流特征選擇算法被提出來[6-10].

目前,在線流特征選擇算法按照特征的流入方式可以分為單特征在線流特征選擇和組特征在線流特征選擇.單特征在線流特征選擇是指在每個(gè)時(shí)刻僅有一個(gè)新的特征生成并且流入特征空間,從當(dāng)前的特征空間中選擇最優(yōu)的特征子集.為此,PerKins等人[6]提出基于梯度的快速啟發(fā)式搜索方法(Grafting)來發(fā)現(xiàn)最可能改善現(xiàn)有模型的特征子集.Wu等人[7]提出基于馬爾科夫毯的在線相關(guān)性分析和在線冗余度分析,并設(shè)計(jì)了在線流特征選擇算法(OSFS,Online Streaming Feature Selection)和快速在線流特征選擇算法(Fast-OSFS,Faster Online Streaming Feature Selection).Zhou等人[8]提出基于動(dòng)態(tài)調(diào)整閾值α的特征選擇方法α-Investing,該方法通過動(dòng)態(tài)調(diào)整閾值控制特征的選擇.與此類似,在鄰域粗糙集的基礎(chǔ)上,為了避免對(duì)鄰域大小的選擇問題,Zhou等人[9]設(shè)計(jì)了密度鄰域關(guān)系,提出了新的在線流特征選擇方法 (OFS-Density,A Novel Online Streaming Feature Selection Method).為了提高計(jì)算的效率,Yu等人[10]利用互信息計(jì)算相關(guān)性特征和冗余性特征,設(shè)計(jì)了可拓展性的在線流特征選擇算法(SAOLA,Scalable and Accurate Online Approach for Feature Selection).

然而,上述流特征選擇算法不能夠適用于多標(biāo)記學(xué)習(xí)問題.基于此,Lin等人[11]利用模糊互信息評(píng)估多標(biāo)記特征的質(zhì)量,并設(shè)計(jì)多標(biāo)記在線流特征選擇方法(MSFS,Streaming Feature Selection for Multilabel Learing based on Fuzzy Mutual Information).Liu 等人[12]在鄰域粗糙集中引入最大近鄰的鄰域關(guān)系,計(jì)算每個(gè)特征對(duì)標(biāo)記的依賴度,提出了基于鄰域粗糙集的多標(biāo)記在線流特征選擇算法(OM-NRS,Online Muti-label Streaming Feature Selection based on Neighborhood Rough Set).

在線組特征流假設(shè)在一個(gè)時(shí)間戳上生成一組特征,且特征以組的形式流入特征空間.Li等人[13]基于互信息和條件互信息設(shè)計(jì)了組內(nèi)特征選擇和組間特征選擇兩個(gè)階段,并提出了組特征流特征選擇方法(GFSSF,Group Feature Selection with Streaming Features).與GFSSF算法不同,Wang 等人[14]利用譜特征選擇進(jìn)行組內(nèi)選擇,利用Lasso回歸在不同組間選擇最終子集,提出在線組特征選擇(OGFS,Online Group Feature Selection).在SAOLA的基礎(chǔ)上,Yu 等人[9]通過計(jì)算每個(gè)特征的與標(biāo)簽的互信息,將其拓展到在線組特征選擇(Group-SAOLA).

鄰域粗糙集由于不需要先驗(yàn)知識(shí)且能夠描述特征與決策之間的一致性,在特征選擇得到廣泛的應(yīng)用[15].然而,數(shù)據(jù)中不可避免會(huì)存在噪聲,在噪聲的影響下鄰域粗糙集進(jìn)行計(jì)算特征與標(biāo)記之間的依賴度會(huì)存在偏差.基于此,本文提出了基于抗噪聲鄰域粗糙集在線流特征選擇方法(OFS-A,Oline Feature Selection Based on Anti-noise Neighborhood Rough Set).OFS-A算法通過計(jì)算異類樣本對(duì)同類樣本的區(qū)分能力,以避免噪聲的影響,提出了新的鄰域關(guān)系,重新定義了鄰域粗糙集的下近似和依賴度的計(jì)算方法,用于衡量每個(gè)特征對(duì)樣本的區(qū)分能力;考慮到特征對(duì)不同類別提供的信息不同,結(jié)合已選特征子集類別正域的大小,提出新的在線相關(guān)性分析和在線冗余性分析方法.實(shí)驗(yàn)結(jié)果顯示,所提出的算法在8個(gè)常用的數(shù)據(jù)集上所選的特征子集,在平均精度和平均排名都取得最優(yōu)的效果.

2 鄰域粗糙集

本節(jié)內(nèi)容介紹領(lǐng)域粗糙集的相關(guān)知識(shí)及2種鄰域關(guān)系.

定義1[16].給定一個(gè)非空有限的樣本集合U={x1,x2,…,xm},非空有限的條件屬性集合C={f1,f2,…,fn}和決策屬性集合D.如果C是生成U的一族鄰域關(guān)系,則稱NDS=為一個(gè)鄰域決策系統(tǒng).

定義2[16].給定一個(gè)非空有限的樣本集合U,設(shè)Δ表示一個(gè)距離度量函數(shù),且對(duì)于?xi,xj,xk∈U距離度量函數(shù)Δ應(yīng)滿足以下的性質(zhì):

1)非負(fù)性:Δ(xi,xj)≥0,當(dāng)且僅當(dāng)xi=xj,等號(hào)成立;

2)自反性:Δ(xi,xj)=Δ(xj,xi);

3)三角不等式:Δ(xi,xj)≤Δ(xi,xk)+Δ(xk,xj).

距離度量函數(shù)Δ常用P范數(shù)進(jìn)行表示:

(1)

其中,f(x,a)表示樣本x在屬性a上值.

定義3[16].給定鄰域決策系統(tǒng)NDS=和距離度量函數(shù)Δ,δ為非負(fù)實(shí)數(shù),對(duì)于?x∈U,δ鄰域定義為:

δ(x)={xj|xj∈U,Δ(x,xj)≤δ,δ>0}

(2)

定義4[17].給定鄰域決策系統(tǒng)NDS=和距離度量函數(shù)Δ,k為正整數(shù),對(duì)于?x∈U,k最近鄰域定義為:

K(x)={xj|xj∈MINk(Δ(x,xj)),xj∈U,xj≠x}

(3)

其中,MINk(Δ(x,xj))表示與x最近的k個(gè)樣本.

定義5[16].給定NDS=,D將U劃分為N個(gè)等價(jià)類:X1,X2,…,XN，B?C生成U上的鄰域關(guān)系RB,則決策D關(guān)于B的下近似和上近似分別為:

(4)

其中:

鄰域決策系統(tǒng)正域定義為:

(5)

定義6[16].給定鄰域決策系統(tǒng)NDS=,特征子集B?C,條件特征子集B相對(duì)于決策屬性的依賴度定義為:

(6)

其中,CARD(X)表示集合X的基數(shù).

3 基于抗噪聲鄰域粗糙集的在線流特征選擇方法

在本節(jié)中,首先介紹在線流特征選擇的定義;然后,提出了一種抗噪聲的鄰域關(guān)系,重新定義的鄰域粗糙集下近似和依賴度的計(jì)算方法;最后,考慮到特征對(duì)不同類別提供的信息不同,設(shè)計(jì)一種在線相關(guān)性分析和冗余度分析的評(píng)估準(zhǔn)則.

3.1 問題描述

給定一個(gè)在線鄰域決策系統(tǒng)ONDS=,定義一個(gè)在線流特征選擇問題如下:給定論域U和決策屬性D的條件下,在時(shí)間t流入一個(gè)新的特征ft,選擇一個(gè)與決策屬性D高相關(guān),且與已選的特征子集St?C低冗余的特征子集.

3.2 抗噪聲的鄰域關(guān)系

傳統(tǒng)鄰域粗糙集使用δ鄰域或者k最近鄰域,要求鄰域樣本保持一致性,使得鄰域粗糙集下近似對(duì)噪聲樣本特別敏感,造成特征的依賴度計(jì)算存在偏差.

如圖1所示,類別1上使用的δ鄰域,類別2上使用k最近鄰域(k=4),可發(fā)現(xiàn)在噪聲樣本存在條件下,很難保證噪聲點(diǎn)周圍樣本鄰域的一致性.因此本文設(shè)計(jì)了新的鄰域關(guān)系,如定義7所示.

圖1 含噪聲數(shù)據(jù)樣本分布示意圖Fig.1 Sample distribution with noise data

定義7.給定在線鄰域決策系統(tǒng)ONDS=和度量函數(shù)Δ,對(duì)特征子集S?C,?x∈U,稱x在特征集合S下的抗噪聲的(ANN,Anit-noise Neighborhood)鄰域?yàn)?

(7)

其中:

NTi(x) 表示樣本空間中與x最近的第i個(gè)同類樣本,NMi(x)表示樣本空間中與x最近的第i個(gè)異類樣本.

1)當(dāng)ddiffk-dsamek≤0時(shí),表示特征子集S不能夠?qū)最近k個(gè)同類與最近k個(gè)異類區(qū)分.

2)當(dāng)ddiffk-dsamek>0時(shí),表示該特征子集S能夠?qū)最近k個(gè)同類與最近k個(gè)異類進(jìn)行區(qū)分.

區(qū)別于傳統(tǒng)的鄰域關(guān)系,抗噪聲鄰域關(guān)系考慮了最近k個(gè)異類與最近k個(gè)同類對(duì)樣本x的區(qū)分能力.如果k個(gè)最近異類能夠正確區(qū)分k個(gè)最近同類,則樣本x屬于正域.由此,在一定程度上避免噪聲的影響.

(8)

基于抗噪聲鄰域關(guān)系下鄰域決策系統(tǒng)的正域定義為:

(9)

定義9.給定在線鄰域決策系統(tǒng)ONDS=,特征子集B?C,基于抗噪聲鄰域關(guān)系下的特征依賴度定義為:

(10)

其中CARD表示集合元素的基數(shù).

3.3 在線相關(guān)性分析

設(shè)t時(shí)刻已選的特征子集St={f1,f2,…,fp},特征ft以流的形式到達(dá).對(duì)于已選的特征子集St,基于抗噪聲鄰域關(guān)系的平均依賴度為:

(11)

對(duì)于特征ft,基于抗噪聲鄰域關(guān)系的依賴度為:

(12)

對(duì)于t時(shí)刻所選的特征子集St,應(yīng)使St與決策屬性具有高相關(guān)性.

∴MeanSt

對(duì)于t時(shí)刻新到達(dá)的特征ft,由定理1可知,當(dāng)ft的依賴度大于已選特征子集的依賴度時(shí),ft的加入能夠使得平均依賴度增大;由定義10可知,當(dāng)存在ft在類別Xi的正域大于已選特征子集在類別Xi的正域時(shí),特征ft與類別Xi具有高相關(guān)性.

綜合以上定義和定理,當(dāng)t時(shí)刻新到達(dá)的特征ft滿足以下條件:

(13)

則稱特征ft為決策屬性的相關(guān)特征.否則,該特征為決策屬性的不相關(guān)特征,丟棄特征ft.

3.4 在線冗余度分析

在線相關(guān)性分析所選擇的特征可能存在某些特征之間相互冗余.例如,兩個(gè)特征對(duì)決策屬性都是相關(guān)的,但是兩個(gè)特征提供的信息一致,造成特征冗余.為了剔除這些冗余特征,需要進(jìn)行在線冗余度分析.

定義11.給定在線鄰域決策系統(tǒng)ONDS=,對(duì)于已選的特征子集St?C,?fi∈St滿足以下條件:

(14)

則稱特征fi為冗余特征.

經(jīng)過在線冗余度分析,剔除掉冗余的特征子集,選擇一個(gè)較優(yōu)的特征集合.結(jié)合在線相關(guān)性分析,可以得到一個(gè)新的在線特征選擇算法.

3.5 算法步驟

算法.OFS-A

輸入:NDS=,鄰域參數(shù)k

輸出:t時(shí)刻已選的特征子集St-1

1.Repeat

2. 在t時(shí)刻流入一個(gè)新的特征ft

3. /*在線相關(guān)性分析*/

6. 返回到步驟2;

7.ENDIF

9.St=St-1∪ft;

11. /*在線冗余度分析*/

12.St=St-1∪ft;

13. 隨機(jī)打亂已選子集St的順序;

14.FOREACHf′inSt

17.ENDIF

18.ENDFOR

19.ENDIF

20. 直到?jīng)]有新的特征流入,返回St.

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

4.1 實(shí)驗(yàn)設(shè)置

表1中展示了本文所使用的數(shù)據(jù)集相關(guān)信息,包括WARPAR10P、COLON、CAR、GENE2、GENE4、SRBCT、LEUKEMIA、GLIOMA等8個(gè)數(shù)據(jù)集.其中COLON和LEUKEMIA為2類別數(shù)據(jù)集,其余6個(gè)數(shù)據(jù)集為多類別數(shù)據(jù)集.實(shí)驗(yàn)按照每次處理一個(gè)特征的方式,模擬特征的流入.實(shí)驗(yàn)環(huán)境為Windows sever 2012操作系統(tǒng)、MATLAB R2016b.實(shí)驗(yàn)采用10折交叉驗(yàn)證的方法,用9/10的數(shù)據(jù)作為訓(xùn)練集,1/10的數(shù)據(jù)作為測(cè)試集.實(shí)驗(yàn)方法所使用的分類器包括線性支持向量機(jī)(LSVM)、分類回歸決策樹(CART)、k-最近鄰KNN(k=3),用于評(píng)估選定特征子集的好壞.

表1 數(shù)據(jù)集的描述Table1 Description of datasets

為了驗(yàn)證所提出的算法的有效性,實(shí)驗(yàn)選擇了當(dāng)前比較有代表性的在線流特征選擇算法,包括OFS_Density[8]、OSFS[6]、α-investing[7]、Fast-OSFS[6]、SAOLA[9].其中OFS_Denstiy的參數(shù)λ設(shè)置為0.05,OSFS、Fast-OSFS、SAOLA的顯著

性水平參數(shù)α設(shè)置為0.01,α-investing的參數(shù)按照文獻(xiàn)實(shí)驗(yàn)取α= 0.5.

4.2 參數(shù)k分析

為了分析參數(shù)k對(duì)算法的影響,本節(jié)選擇k=1,2,3,4,5,針對(duì)3個(gè)不同數(shù)據(jù)集上的性能表現(xiàn)和篩選的特征子集的大小,選擇最適合的參數(shù).

圖2～圖4分別描述了k取不同值時(shí),在3個(gè)數(shù)據(jù)集上不同分類器的性能比較.圖5描述了k取不同值時(shí),在3個(gè)數(shù)據(jù)集上選擇的特征子集大小的比較.

當(dāng)使用LSVM作為分類器時(shí),由圖1可以看出,不同k取值對(duì)算法在COLON和SRBCT數(shù)據(jù)集上性能表現(xiàn)影響不大.GLOMIA數(shù)據(jù)集在k=4時(shí)候表現(xiàn)最好,當(dāng)k=1時(shí),算法在3個(gè)數(shù)據(jù)集的表現(xiàn)都很好.

當(dāng)使用KNN作為分類器時(shí),COLON和GLOMIA數(shù)據(jù)集在k=4的表現(xiàn)略好于k=5和k=1,明顯優(yōu)于其他的取值.在SRBCT數(shù)據(jù)集上,k的取值對(duì)其性能表現(xiàn)影響不大.

當(dāng)使用CART作為分類器時(shí),SRBCT數(shù)據(jù)集在k=2時(shí)表現(xiàn)較好,COLON在k=1,3,4,5表現(xiàn)較好,在k=2時(shí)表現(xiàn)較差.對(duì)于GLOMIA在k=5時(shí)表現(xiàn)較差,k=1,2,3,4表現(xiàn)較好.

對(duì)于選擇的特征子集大小,由圖5可以看出,在3個(gè)數(shù)據(jù)集上,當(dāng)k=4時(shí),所選擇的特征子集都是最少的.

綜合以上分析,k=1和k=2時(shí),分類器的不同對(duì)精度的影響比較大,所選的特征子集也比較大;當(dāng)k=4時(shí),3個(gè)數(shù)據(jù)集的表現(xiàn)都能高于平均水平且選擇的特征比較少.因此,在本文后面的實(shí)驗(yàn)當(dāng)中,k的取值為4.

4.3 有效性分析

在本節(jié)當(dāng)中,為了分析OFS-A 算法的有效性,分別用OFS-A與其他對(duì)比算法所選的特征子集在3個(gè)不同分類器上的分類精度進(jìn)行對(duì)比.除此之外,利用盒形圖進(jìn)一步分析各個(gè)算法的整體表現(xiàn).

表2～表4分別描述了OFS-A算法與對(duì)比算法在8不同數(shù)據(jù)集上所選擇的特征子集在LSVM、KNN(k=3)、CART分類器預(yù)測(cè)精度,其中加粗表示在所有算法當(dāng)中表現(xiàn)最優(yōu).圖6～圖8分別描述了不同算法的預(yù)測(cè)精度在盒形圖上的對(duì)比.

表2 6種算法在LSVM分類器上分類精度的比較Table 2 Comparison of prediction accuracy on LSVM with 6 different methods

表3 6種算法在KNN分類器上預(yù)測(cè)精度的比較Table 3 Comparison of prediction accuracy on KNN with 6 different methods

表4 6種算法在CART分類器上分類精度的比較Table 4 Comparison of prediction accuracy on CART with 6 different methods

從圖6～圖8中,可以得出以下的結(jié)論:1) OFS-A算法在箱型圖的上四分位與下四分位所夾的部分都是最小的,表明OFS-A算法對(duì)比其他算法有更加穩(wěn)定的性能;2)從各個(gè)算法箱型圖的中位線來看,OFS-A算法在LSVM和KNN分類器上都能明顯高于其他算法,在CART分類器上,OFS-A算法略優(yōu)于OFS_Density算法,但明顯優(yōu)于其他算法.3)對(duì)于分類器的不同,OFS-A算法在KNN分類器上性能表現(xiàn)最優(yōu).

從表2～表4中,可以得出以下的結(jié)論:1) 在類別數(shù)目比較多的數(shù)據(jù)集當(dāng)中,如WARPAR10P、CAR、GENE2、GENE4,OFS-A算法在3個(gè)不同的分類器當(dāng)中,效果明顯優(yōu)于其他算法;2)其他類別數(shù)目比較少的數(shù)據(jù)集當(dāng)中,如COLON、LEUKEMIA等,OFS-A算法表現(xiàn)平均水平之上;3)從平均精度與平均排名中可以看出,OFS-A在各個(gè)數(shù)據(jù)集上的平均表現(xiàn)都是最優(yōu).在LSVM、KNN、CART分類器上,平均精度相對(duì)次優(yōu)算法提高了19%、25.4%、18.5%.

4.4 不同算法的所選的特征子集的比較

在本節(jié)當(dāng)中,利用OFS-A算法與對(duì)比算法在各個(gè)數(shù)據(jù)集上選擇的特征子集大小進(jìn)行比較.

表5描述了不同算法在各個(gè)數(shù)據(jù)集上所選的特征子集的大小,其中加粗表示在所有對(duì)比的算法中選擇的特征數(shù)最少,下劃線表示在所有對(duì)比的算法中選擇的特征數(shù)目次少.從表5可看出,OFS-A算法所選擇特征子集的平均大小僅次于α-investing和SAOLA.在CAR、GENE2、GENE4等數(shù)據(jù)集當(dāng)中,OFS-A算法所選特征子集大小在對(duì)比算法當(dāng)中都是最大;在其他數(shù)據(jù)集當(dāng)中,OFS-A算法得到的特征子集處于平均水平;對(duì)比算法OSFS和Fast-OSFS所選特征子集比較少,但是從表2-表4來看,兩個(gè)算法選擇出來的特征子集在分類器上的性能表現(xiàn)沒有OFS-A算法優(yōu).

表5 6種算法所選的特征子集大小的比較Table 5 Comparison of selected feature size of 6 different methods

OFS-A算法選擇的特征子集比較大的原因在于:該算法使用的在線相關(guān)性分析,能夠充分挖掘出有用的特征信息.相較于其它在線流特征選擇算法,OFS-A算法能夠選擇出更多的有用的特征,所以最終得到的特征子集比較大.

5 總 結(jié)

對(duì)于在線流特征選擇任務(wù),提出基于抗噪聲鄰域的在線流特征選擇方法.首先,為解決噪聲的影響,計(jì)算異類樣本對(duì)同類樣本的區(qū)分能力,設(shè)計(jì)了抗噪聲的鄰域關(guān)系;其次,提出了新的相關(guān)性和冗余性評(píng)估準(zhǔn)則.最后,在8個(gè)數(shù)據(jù)集上實(shí)驗(yàn)顯示,該算法能夠提取更有用的特征子集,提高了分類算法的精度,性能更加穩(wěn)定.