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

呂彥,林耀進,陳祥焰,李瓏珠,王晨曦

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

0 引言

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

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

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

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

1 鄰域粗糙集

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

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

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

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

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

其中

NDS的正域和負域分別定義為

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

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

B1?B2?…?C，

則有

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

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

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

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

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

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

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

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

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

2.1 鄰域粗糙集的擴展

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

定義7 給定一個鄰域決策系統(tǒng)NDS=〈U,C,D〉,x∈U的鄰域為

δ′(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)

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

(4)

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

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

(5)

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

(6)

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

(7)

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

2.2 DJNB算法

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

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

2.3 三種在線評估準則

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

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

(8)

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

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

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

(9)

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

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

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

(10)

2.4 OFS-JNB算法

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

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

OFS-JNB算法輸入:NDS=,t時刻到達的特征ft,t-1時刻已選的特征子集S輸出:t所選的特征子集S'1. 初始化特征子集S'=?;2. 在t時刻流進的特征ft;3. 計算屬性ft的依賴度γ'ft (D);4. ifγ'ft (D)<1|S|∑fi∈Sγ'fi (D)5. discard ft;6. else7. 計算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)]有新特征流進特征空間,返回特征子集S'。

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

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

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

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

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

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

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

3.2 結(jié)果分析

為了進一步驗證OFS-JNB算法的有效性,實驗采用OSFS、Fast-OSFS、SAOLA、α-investing[15]和OFS-Density作為對比算法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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