呂彥,林耀進(jìn),陳祥焰,李瓏珠,王晨曦

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

0 引言

在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)分類任務(wù)中,特征選擇或?qū)傩约s簡是一種有效的數(shù)據(jù)預(yù)處理方法。其主要目的是減少冗余特征,簡化分類模型的復(fù)雜性,提高分類模型的泛化能力。目前,特征選擇廣泛應(yīng)用于醫(yī)療診斷[1]、欺詐檢測(cè)[2]、文本分類[3]和近似推理[4]等領(lǐng)域。傳統(tǒng)的特征選擇方法假設(shè)在進(jìn)行特征選擇前,整個(gè)特征空間是已知的。然而,在許多實(shí)際應(yīng)用中,并不是所有的特征都是可以提前獲取的。例如,在新浪微博中,熱門話題榜單每10 min就會(huì)變動(dòng)1次,當(dāng)1個(gè)新的熱門話題出現(xiàn)時(shí),它可能會(huì)帶有一組新的關(guān)鍵字,而其中一些新關(guān)鍵字可用于識(shí)別新熱門話題的關(guān)鍵特征[5]。在大數(shù)據(jù)時(shí)代,數(shù)據(jù)呈現(xiàn)高維海量特點(diǎn)及整體特征空間無法提前獲取的情況下,在線流特征選擇技術(shù)具有極其重要的實(shí)際應(yīng)用價(jià)值。

近年來,針對(duì)流環(huán)境下的在線特征選擇算法備受研究者的關(guān)注[6]。在線流特征選擇方法是按所有的備選特征動(dòng)態(tài)生成,即隨著時(shí)間的推移特點(diǎn)一個(gè)接一個(gè)流進(jìn)來。目前,在線流特征選擇算法可分為單標(biāo)記流特征和多標(biāo)記流特征選擇,一些代表性的單標(biāo)記在線流特征選擇算法被先后提出,其中Perkins和Theiler[7]提出分段梯度下降的在線特征選擇算法Grafting。Wu等[8]提出了一種在線流特征選擇的基本框架,并介紹了兩種可快速選擇強(qiáng)相關(guān)和非冗余特征的在線流特征選擇算法(Online Streaming Feature Selection,OSFS)和快速在線特征選擇算法(Faster Online Streaming Feature Selection,Fast-OSFS)。Yu等[5]提出采用在線成對(duì)比較方法處理高維數(shù)據(jù)的可伸縮性算法(Scalable and Accurate Online Feature Selection Approach,SAOLA)?？紤]傳統(tǒng)鄰域粗糙集方法都需要預(yù)先指定一些參數(shù),Zhou等[9]改進(jìn)鄰域粗糙集模型,設(shè)計(jì)了一種基于自適應(yīng)密度鄰域關(guān)系的在線流特征選擇新算法(A New Online Streaming Feature Selection Method Based on Adaptive Density Neighborhood Relation, OFS-Density)。

上述在線流特征選擇算法僅適用于處理單標(biāo)記數(shù)據(jù)問題。對(duì)于多標(biāo)記學(xué)習(xí),代表性的多標(biāo)記流特征選擇算法包括Lin等[10]采用模糊互信息來評(píng)估多標(biāo)簽學(xué)習(xí)中特征的質(zhì)量,并提出了一種多標(biāo)記流特征選擇算法(Multilabel Streaming Feature Selection,MSFS)用于處理特征空間完全已知或部分已知時(shí)的場(chǎng)景。Liu等[11]基于鄰域粗糙集提出了一種新穎的在線多標(biāo)記流特征選擇算法(Online Multi-label Streaming Feature Selection Based on Neighborhood Rough Set,OMNRS),用于選擇包含高度相關(guān)且非冗余特征的特征子集。

然而,上述基于鄰域粗糙集的流特征選擇算法在計(jì)算屬性依賴度時(shí),僅考慮條件屬性子集的正域中包含的信息,而忽視了邊界區(qū)域中包含的信息。與正域不同,邊界區(qū)域內(nèi)的樣本包含同類樣本與異類樣本,故而可將邊界樣本看作是含有噪聲的正域。因此降低邊界區(qū)域中噪聲樣本的影響,并將其與鄰域粗糙集中的依賴度結(jié)合使用,可以更好地限定特征子集之間的依存關(guān)系。由此,本文改進(jìn)了鄰域粗糙集模型依賴度的計(jì)算方法,提出了一種聯(lián)合鄰域邊界的在線流特征選擇算法(Joint Neighborhood Boundary for Online Streaming Feature Selection, OFS-JNB)。OFS-JNB根據(jù)“在線依賴度分析、在線重要度分析和在線冗余度分析”三大評(píng)估準(zhǔn)則,在線依次處理流進(jìn)特征空間的特征,從而所選特征子集與決策屬性表現(xiàn)出高依賴性、高重要度和低冗余性。最后,在具有不同應(yīng)用場(chǎng)景的8個(gè)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)證明,該算法所選出的特征子集,能夠有效提高分類效率。

1 鄰域粗糙集

定義1[12]給定一個(gè)非空有限樣本集合U={x1,x2,…,xn},C={a1,a2,…,am}作為描述論域U的實(shí)數(shù)型特征集合,如果C能生成該論域U上的一簇鄰域關(guān)系,D為決策屬性,則稱NDS=〈U,C,D〉為鄰域決策系統(tǒng)。

定義2[12]給定非空的有限樣本集合U={x1,x2,…,xn},對(duì)?xi∈U的鄰域δ(xi)可定義為

δ(xi)={xj|Δ(xi,xj)≤δ,xj∈U}。

xi的鄰域δ(xi)是以xi為中心，δ為半徑的球體。

定義3[12]給定鄰域決策系統(tǒng)NDS=〈U,C,D〉,D將U劃分為N個(gè)等價(jià)類{X1,X2,…,X},B?C生成U上的鄰域關(guān)系RB,則決策屬性D關(guān)于條件屬性子集B的下近似和上近似分別為

其中

NDS的正域和負(fù)域分別定義為

定義4[12]給定鄰域決策系統(tǒng)NDS=〈U,C,D〉,B?C,決策屬性D對(duì)于條件屬性子集B的依賴度為

由上式可知依賴度是單調(diào)遞增的,若

B1?B2?…?C，

則有

γB1(D)≤γB2(D)≤…≤γC(D)。

定義5[12]給定鄰域決策系統(tǒng)NDS=〈U,C,D〉,若B?C滿足以下條件,則B是C的一個(gè)約簡

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

2)γB(D)=γC(D)。

即約簡后的集合中,所有的屬性都應(yīng)該是必不可少的,且不存在冗余的屬性;同時(shí),屬性約簡是在不降低系統(tǒng)的區(qū)分能力下的約簡。

定義6[12]給定鄰域決策系統(tǒng)NDS=〈U,C,D〉,B?C,對(duì)?a?B,條件屬性a的重要度定義如下

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

2 聯(lián)合鄰域邊界的在線流特征選擇算法

本文重點(diǎn)研究了傳統(tǒng)基于鄰域粗糙集的在線特征選擇在計(jì)算條件屬性集合的依賴度時(shí),忽視了邊界區(qū)域中包含的信息的問題。首先對(duì)鄰域粗糙集理論進(jìn)行擴(kuò)展,介紹了一種計(jì)算條件屬性集合依賴度的新方法。并在此基礎(chǔ)上,提出了三種在線選擇特征的評(píng)估準(zhǔn)則,用于選擇與決策屬性依賴度高,同時(shí)特征間冗余度低的特征子集。

2.1 鄰域粗糙集的擴(kuò)展

傳統(tǒng)方法通過對(duì)不同類型數(shù)據(jù)設(shè)置不同的閾值,致使存在粒度選擇問題[11]。為了使所有實(shí)例粒度化,同時(shí)避免粒度選擇的問題,引入最大近鄰的方法來設(shè)置信息粒子的大小。同時(shí),傳統(tǒng)基于鄰域粗糙集的特征選擇算法僅利用條件屬性集合的正域來計(jì)算依賴度,而忽略了邊界區(qū)域的重要性。在大多數(shù)情況下,數(shù)據(jù)分布往往是不均勻的,上近似與下近似的集合大小差別較大,即邊界區(qū)域包含較多樣本。然而這些樣本中包含的大量有用信息被噪聲所影響,使得依賴度的計(jì)算有一定的不足。由此,本文引入邊界區(qū)域,對(duì)原始鄰域粗糙集理論進(jìn)行擴(kuò)展,提出一種計(jì)算屬性依賴度的新方法。

定義7 給定一個(gè)鄰域決策系統(tǒng)NDS=〈U,C,D〉,x∈U的鄰域?yàn)?/p>

δ′(x)={y|Δ(x,y)≤d(x),y∈U}，

(1)

其中

d(x)=max(d1(x),d2(x))，

d1(x)=Δ(x,NM(x))，

d2(x)=Δ(x,NH(x)),

其中,NH(x)是樣本x的最近同類樣本,NM(x)是樣本x的最近異類樣本。Δ(x,NM(x))與Δ(x,NH(x))分別表示樣本x到NM(x)和NH(x)的距離。

(2)

其中

NDS的正域和邊界分別定義為

(3)

相對(duì)正域posiBND的權(quán)重定義為

(4)

定義10 給定鄰域決策系統(tǒng)NDS=〈U,C,D〉,B?C。若使權(quán)重集合w={w1,w2,…,wN}的最大值大于0.5,則決策屬性D對(duì)于條件屬性子集B的依賴度為

s.t.wi≥0.5，wi=max(w)。

(5)

否則,決策屬性D對(duì)于條件屬性子集B的依賴度為

(6)

定義11 給定鄰域決策系統(tǒng)NDS=〈U,C,D〉,B?C,對(duì)?a?B,條件屬性a的重要度定義如下

(7)

基于公式(5)和公式(6),提出了一種聯(lián)合鄰域邊界的依賴度計(jì)算方法(Dependency of Joint Neighborhood Boundariy,DJNB)。

2.2 DJNB算法

DJNB算法輸入:NDS=,特征子集B?C,U/D={X1,X2,…,XN}輸出:特征子集B的依賴度γ'B (D)1. 計(jì)算樣本xi最近的同類樣本NH(xi);2. 計(jì)算樣本xi最近的異類樣本NM(xi);3. 計(jì)算鄰域半徑δ'(xi);4. 以間隔大小δ'(xi)為鄰域半徑劃分鄰域;5. 計(jì)算下近似R'BD、邊界BND'B (D);6. for each Xi in U7. 根據(jù)公式(3)計(jì)算posiBND;8. 根據(jù)公式(4)計(jì)算wi;9. end for10. if max(w)≥0.511. 根據(jù)公式(5)計(jì)算依賴度γ'B (D);12. else13. 根據(jù)公式(6)計(jì)算依賴度γ'B (D);14. end if15. Return γ'B (D)。

在DJNB算法中,返回的是特征子集B的依賴度。在DJNB算法中,步驟7-8是計(jì)算邊界區(qū)域相對(duì)于類別集合Xi的相對(duì)正域posiBND,并計(jì)算相對(duì)正域的權(quán)重wi。步驟10-14是計(jì)算依賴度。若權(quán)重集合w的最大值大于等于0.5,則意味著,邊界區(qū)域內(nèi)樣本與相應(yīng)類別集合內(nèi)的大部分樣本分布一致,則根據(jù)公式(5)計(jì)算條件屬性集合的依賴度。若權(quán)重集合w的最大值小于0.5,則根據(jù)公式(6)計(jì)算條件屬性集合的依賴度。若假設(shè)|U|是訓(xùn)練樣本的數(shù)目,那么算法的時(shí)間復(fù)雜度為O(|U|·log|U|)。

2.3 三種在線評(píng)估準(zhǔn)則

與傳統(tǒng)的特征選擇方法不同,基于特征流的在線特征選擇隨著時(shí)間的推移,逐個(gè)獲取特征,同時(shí)必須快速?zèng)Q定對(duì)在t時(shí)刻新到達(dá)的特征ft是保留還是丟棄[13]。由此,三種評(píng)估特征子集的準(zhǔn)則被提出。具體內(nèi)容如下:

1) 在線依賴度分析(Online dependence analysis)

(8)

使用“在線依賴度分析”準(zhǔn)則來選擇依賴度高的特征,同時(shí)依賴度低的特征將不做考慮,但是它所篩選的子集中存在冗余特征。

2) 在線重要度分析(Online importance analysis)

已知鄰域決策系統(tǒng)NDS=〈U,C,D〉,其中C={f1,f2,…,ft},特征ft相對(duì)于決策屬性D的重要度定義為

(9)

其中,ft為t時(shí)刻新到達(dá)的特征,S?C是當(dāng)前時(shí)刻下已選的特征子集。在線重要度分析可以有效地評(píng)估當(dāng)前特征ft的重要性,若特征ft的重要度大于0,則ft被認(rèn)為是對(duì)決策屬性有效的特征,此時(shí)應(yīng)該保留該特征,否則ft被認(rèn)為是一個(gè)沒有意義的特征,將不被考慮。

3) 在線冗余度分析(Online redundancy analysis)

給定鄰域決策系統(tǒng)NDS=〈U,C,D〉,其中條件屬性集合C={f1,f2,…,ft},S?C為已選特征子集,ft為t時(shí)刻新到達(dá)的新特征。若?S′∈S,滿足公式(10),則將ft添加到S′中,進(jìn)而取代特征子集S。

(10)

2.4 OFS-JNB算法

如果ft滿足“最大依賴度準(zhǔn)則”,步驟8判斷特征ft的重要性,若ft∪S的依賴度大于S的依賴度,則將特征ft添加進(jìn)特征子集S中。

步驟11至16是“在線冗余度分析”,用于檢查S中是否存在與ft是相互冗余的特征。步驟12-15,評(píng)估ft是否應(yīng)該被添加進(jìn)當(dāng)前已選特征子集S,如果?fi∈S滿足公式(10),則應(yīng)該將ft添加入S中,而將fi從已選特征子集S中刪除。

OFS-JNB算法輸入:NDS=,t時(shí)刻到達(dá)的特征ft,t-1時(shí)刻已選的特征子集S輸出:t所選的特征子集S'1. 初始化特征子集S'=?;2. 在t時(shí)刻流進(jìn)的特征ft;3. 計(jì)算屬性ft的依賴度γ'ft (D);4. ifγ'ft (D)<1|S|∑fi∈Sγ'fi (D)5. discard ft;6. else7. 計(jì)算ft的重要度sig'(ft,S,D);8. if sig'(ft,S,D)>09. S=S∪ft;10. else11. for each fi in S12. if γ'{S-fi}∪ft (D)≥γ'S (D)13. S=S-fi;14. S=S∪ft;15. end if16. end for17. end if18. end if19. S'=S;20. 直到?jīng)]有新特征流進(jìn)特征空間,返回特征子集S'。

由此,根據(jù)三種在線評(píng)估準(zhǔn)則的約束,我們能夠選擇出高依賴性、高重要度和低冗余度的特征子集。

2.5 時(shí)間復(fù)雜度分析

本文算法主要是選擇與決策屬性依賴度高,同時(shí)特征間冗余度低的特征子集。在t時(shí)刻,|S|是當(dāng)前已選特征子集中特征的個(gè)數(shù),D為決策屬性,U為論域。在最好的情況下,OFS-JNB算法通過“在線依賴度分析”準(zhǔn)則已經(jīng)可以獲得了一個(gè)好的特征子集,這一步驟的時(shí)間復(fù)雜度為O(|U|·log|U|)。然而OFS-JNB算法在很多情況下,并不能如此簡單就能獲得最好的特征子集,所以必須要通過“在線重要度分析”準(zhǔn)則和“在線冗余度分析”準(zhǔn)則進(jìn)一步篩選?！霸诰€重要度分析”和“在線冗余度分析”的時(shí)間復(fù)雜度取決于比較決策屬性分別對(duì)已選特征子集和候選特征子集的依賴度。所以,在最壞情況下,我們需要對(duì)每一個(gè)當(dāng)前時(shí)刻流進(jìn)來的特征進(jìn)行“在線冗余度分析”處理,其時(shí)間復(fù)雜度為O(|S|·|U|2·log|U|)。但在實(shí)際應(yīng)用情況下,“在線依賴度分析”準(zhǔn)則已刪去大多數(shù)特征,故該算法真實(shí)時(shí)間復(fù)雜度遠(yuǎn)小于O(|S|·|U|2·log|U|)。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)通過一次處理一個(gè)特征的方式來模擬特征流。實(shí)驗(yàn)中采用K-近鄰(K=3)、分類回歸樹(CART)和線性支持向量機(jī)(LSVM)三種分類器對(duì)選定的特征子集進(jìn)行評(píng)估[14]。另外,對(duì)每個(gè)數(shù)據(jù)集進(jìn)行10折交叉驗(yàn)證,9/10的數(shù)據(jù)樣本進(jìn)行訓(xùn)練,其余1/10數(shù)據(jù)進(jìn)行測(cè)試。實(shí)驗(yàn)平臺(tái)統(tǒng)一采用Matlab R2013b。本文將OFS-JNB算法在不同數(shù)據(jù)集上的分類精度和選擇特征的數(shù)量與最先進(jìn)的流特征選擇算法進(jìn)行對(duì)比。其中數(shù)據(jù)集包括AUTOVAL_B、CAR、GENE2、GENE4、GENE7、MLL、SRBCT、WARPAR10P(見表1)。

表1 數(shù)據(jù)集的描述

3.2 結(jié)果分析

為了進(jìn)一步驗(yàn)證OFS-JNB算法的有效性,實(shí)驗(yàn)采用OSFS、Fast-OSFS、SAOLA、α-investing[15]和OFS-Density作為對(duì)比算法。

OSFS、Fast-OSFS算法動(dòng)態(tài)選擇強(qiáng)相關(guān)和非冗余特征,包含兩個(gè)主要步驟:在線相關(guān)性分析(丟棄不相關(guān)特征)和在線冗余分析(消除冗余特征)[8]。為了解決從超高維數(shù)據(jù)中在線選擇特征的挑戰(zhàn),SAOLA通過對(duì)特征之間兩兩相關(guān)的界限進(jìn)行理論分析,采用了新穎的在線兩兩比較的技術(shù),并以在線的方式在一段時(shí)間內(nèi)保持一個(gè)簡單的模型。α-investing是一種基于流回歸的自適應(yīng)復(fù)雜度懲罰的流式特征選擇方法,它能夠動(dòng)態(tài)的調(diào)整閾值以減少添加新特征所產(chǎn)生的誤差[15]。OFS-Density算法利用周圍實(shí)例的密度信息提出了一種新的自適應(yīng)鄰域關(guān)系,通過使用模糊等式約束進(jìn)行冗余分析,從而選擇冗余度較低的特征。

OFS-JNB不需要預(yù)先設(shè)定任何閾值。OSFS、Fast-OSFS和SAOLA中顯著性水平參數(shù)α均設(shè)置為0.01,α-investing模型中參數(shù)α的設(shè)置與文獻(xiàn)[15]相同。OFS-Density模型中的參數(shù)λ設(shè)置為0.05。

表2 6種算法在KNN分類器上分類精度的對(duì)比

表3 6種算法在CART分類器上分類精度的對(duì)比

表4 6種算法在LSVM分類器上分類精度的對(duì)比

表5 6種算法在8個(gè)數(shù)據(jù)集上選擇特征的個(gè)數(shù)

表2-表4分別描述6種算法在KNN(K=3)、CART和LSVM分類器上的分類精度。表5為6種模型在8個(gè)數(shù)據(jù)集上選擇的特征數(shù)量。

基于KNN、CART和LSVM分類器,OFS-JNB算法在GENE2和MLL數(shù)據(jù)集上都優(yōu)于其他五種對(duì)比算法,同時(shí)上述其他四種對(duì)比算法在這兩個(gè)數(shù)據(jù)集上的分類精度都不高。

在GENE4數(shù)據(jù)集上,采用各類分類器對(duì)上述6種算法進(jìn)行評(píng)估時(shí),僅OFS-JNB算法在LSVM分類器上獲得了較高的預(yù)測(cè)精度,其余算法的預(yù)測(cè)精度均不理想。尤其是OFS-Density算法在各類分類器下預(yù)測(cè)精度均不足0.2。

由表5可知,OSFS在8個(gè)數(shù)據(jù)集上,均選擇了很少的特征,盡管在特征數(shù)量上OSFS算法具有非常大的優(yōu)勢(shì),但結(jié)合表2-表4可知,OSFS的分類精度也低于其他對(duì)比算法。無論是在哪個(gè)分類器下,OSFS、Fast-OSFS和SAOLA算法在數(shù)據(jù)集WARPAR10P上的都很低,只能達(dá)到0.3左右,其主要原因是該數(shù)據(jù)集非常稀疏,這四種算法只能選擇這些數(shù)據(jù)集的后幾個(gè)特征。

由表2-表5可見,SAOLA和α-investing在CAR數(shù)據(jù)集上所選特征子集中特征數(shù)量遠(yuǎn)多于其他對(duì)比算法,預(yù)測(cè)精度也高于其他對(duì)比算法,然而,其預(yù)測(cè)精度與對(duì)比算法的差異較小。SAOLA在數(shù)據(jù)集GENE7上所選特征個(gè)數(shù)遠(yuǎn)多于其他對(duì)比算法,而預(yù)測(cè)精度卻低于其他對(duì)比算法。由此可知,SAOLA和α-investing所選特征子集中存在較多冗余特征。

觀察表2-表5發(fā)現(xiàn),OFS-JNB算法所選特征個(gè)數(shù)與Fast-OSFS和OFS-Density保持在同一水平,在大多數(shù)數(shù)據(jù)集上均明顯小于SAOLA和α-investing。

為了更加直觀地對(duì)比6種算法在不同分類器上的分類性能,采用箱型圖對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析,結(jié)果見圖1、圖2和圖3。由圖可得如下結(jié)論:

在總體水平上,OFS-JNB算法在8個(gè)數(shù)據(jù)集上的3個(gè)分類器上預(yù)測(cè)精度的中位數(shù)(平均性能)都排在第一。

OFS-JNB算法在KNN、LSVM分類器下,上四分位數(shù)和下四分位數(shù)的分布較為緊密,且集中分布在較高的分類性能區(qū)域。在CART分類器下,雖然上四分位數(shù)和下四分位數(shù)分布較為松散,但都集中分布在較高的分類性能區(qū)域。

圖1 各算法在KNN分類器上的盒形圖對(duì)比Fig.1 Box plot comparison of algorithmswith KNN classifier

圖2 各算法在CART分類器上的盒形圖對(duì)比Fig.2 Box plot comparison of algorithmswith CART classifier

圖3 各算法在LSVM分類器上的盒形圖對(duì)比Fig.3 Box plot comparison of algorithmswith LSVM classifier

由此可得OFS-JNB算法預(yù)測(cè)精度優(yōu)于其他算法且更穩(wěn)定。

4 結(jié)論

在線流特征選擇作為一種以在線方式處理流特征的新方法,近年來備受關(guān)注,并在處理高維數(shù)據(jù)問題方面發(fā)揮了關(guān)鍵作用。然而,傳統(tǒng)基于鄰域粗糙集的在線流特征選擇方法在計(jì)算屬性依賴度時(shí),僅利用下近似來計(jì)算決策屬性對(duì)于條件屬性集合的依賴度,而忽視了邊界區(qū)域中存在的有用信息?；谏鲜銮闆r,本文提出聯(lián)合鄰域邊界的在線流特征選擇算法(OFS-JNB)。定義了一種計(jì)算屬性依賴度的新方法,使得邊界域中的信息得以利用。同時(shí),依據(jù)“在線依賴度分析,在線重要度分析和在線冗余度分析”三種評(píng)估準(zhǔn)則,選出高依賴度、高重要度且低冗余的特征子集。在8個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,OFS-JNB算法在預(yù)測(cè)精度上要優(yōu)于傳統(tǒng)的在線流特征選擇算法。今后,我們的工作將討論如何將該方法擴(kuò)展應(yīng)用于多標(biāo)簽數(shù)據(jù)集上。