利用鄰域信息交互的在線流特征選擇算法

李瓏珠，林耀進(jìn)，呂 彥，盧 舜，王晨曦

1.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州363000

2.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建 漳州363000

在圖像分類[1]、醫(yī)學(xué)診斷[2]和生物基因?qū)W[3]等領(lǐng)域，數(shù)據(jù)的特征空間往往呈現(xiàn)高維性，特征選擇是機(jī)器學(xué)習(xí)領(lǐng)域中一種有效的數(shù)據(jù)預(yù)處理技術(shù)。隨著Web2.0及各種智能終端的快速發(fā)展，數(shù)據(jù)的特征空間不再是一個(gè)靜態(tài)固定的，而是動(dòng)態(tài)的甚至是未知的[4]。因此，已有特征選擇算法無(wú)法解決實(shí)時(shí)產(chǎn)生的數(shù)據(jù)，需構(gòu)建一類新的特征選擇方法來(lái)處理數(shù)據(jù)特征呈現(xiàn)序列達(dá)到的特性[5]。于是，在線流特征選擇算法因其能有效處理動(dòng)態(tài)流特征而受到了廣泛的關(guān)注[5-7]。

流特征是指樣本空間固定不變，而特征空間是動(dòng)態(tài)未知的且特征逐個(gè)獲取[4]。例如，從高分辨率的行星圖像進(jìn)行火星隕石坑檢測(cè)[5]中，可以為遠(yuǎn)距離測(cè)量行星表面的相對(duì)年齡提供唯一的解決方案，而且從行星圖像中生成并儲(chǔ)存數(shù)以萬(wàn)計(jì)的圖像特征來(lái)幾乎覆蓋火星表面的全范圍是不可行的，因此圖像特征需提取時(shí)立即進(jìn)行在線選擇。目前，流特征選擇面臨的主要問(wèn)題有：（1）特征維度可能隨著時(shí)間的推移而增加，甚至可能擴(kuò)展到無(wú)限大。（2）在單位時(shí)間內(nèi)特征逐個(gè)流入，且要求特征在達(dá)到時(shí)能夠被實(shí)時(shí)處理。根據(jù)樣本的語(yǔ)義信息，在線流特征選擇算法可以分為單標(biāo)記在線流特征選擇算法和多標(biāo)記在線流特征選擇算法。單標(biāo)記在線流特征選擇算法包括流向特征選擇算法（Streamwise Feature Selection，α-investing）[6]，在線流特征選擇算法（Online Streaming Feature Selection，OSFS）[7]，可擴(kuò)展和準(zhǔn)確的在線流特征選擇算法（Scalable and Accurate Online Selection Approach，SAOLA）[8]等。此外，Zhou等人[9-10]提出了一種專門處理類別不平衡數(shù)據(jù)的在線特征選擇算法（Online Feature Selection for high-dimensional classimbalanced Data，K-OFSD）和一種基于鄰域粗糙集的在線流特征選擇算法（A New Online Feature Selection Method Using Neighborhood Rough Set，OFS-A3M）。在Zhou等人的基礎(chǔ)上，Chen等人[11]提出了基于鄰域粗糙集的高維類不平衡數(shù)據(jù)在線流特征選擇算法（Online Streaming Feature Selection for High-Dimensional and Class-Imbalanced Data Based on Neighborhood Rough Set，OFS），提出三種在線策略處理高維不平衡數(shù)據(jù)。Bai等人[12]還將流特征選擇與層次分類結(jié)合，提出了基于鄰域粗糙集的大規(guī)模層次分類在線流特征選擇算法（Large-Scale Hierarchical Classification Online Streaming Feature Selection Based on Neighborhood Rough Set，OHFS）。

多標(biāo)記在線流特征選擇算法主要包括流標(biāo)記下的多標(biāo)記流特征選擇算法（Multi-Label Feature Selection with Streaming Labels，MLFSL）[13]，基于模糊互信息的多標(biāo)記流特征選擇（Streaming Feature Selection for Multi-label Learning Based on Fuzzy Mutual Information，MUCO）[14]，以及基于鄰域粗糙集的多標(biāo)記流特征選擇算法（Online Multi-label streaming feature selection based on Neighborhood Rough Set，OMNRS）[15]等。此外，Liu等人[16]通過(guò)設(shè)計(jì)類間鑒別和類內(nèi)近鄰識(shí)別選擇新到標(biāo)簽的類屬屬性進(jìn)行多標(biāo)記流特征選擇（Feature Selection for multi-label learning with Streaming Label，F(xiàn)SSL）。

然而，已有在線流特征選擇算法僅考慮特征與標(biāo)記間的相關(guān)性，忽略單個(gè)特征之間的局部交互作用，特別是多個(gè)特征聯(lián)合時(shí)的全局交互作用，易損失一些具有弱交互性但強(qiáng)區(qū)分能力的特征。特征交互是指那些特征與類標(biāo)記單獨(dú)計(jì)算相關(guān)性時(shí)，表現(xiàn)為無(wú)關(guān)或極弱相關(guān)，但當(dāng)與其他特征聯(lián)合時(shí)，會(huì)與類標(biāo)記呈極大的相關(guān)性[17]?；诖?，本文提出基于鄰域信息交互的在線流特征選擇算法（Online streaming feature selection using Neighborhood Information Interaction，NII）。該算法主要分為兩個(gè)階段：（1）在線交互特征選擇階段，即在定義特征強(qiáng)交互、弱交互和不相關(guān)三種概念基礎(chǔ)上，將新到特征直接與整個(gè)已選特征子集和類標(biāo)簽進(jìn)行交互判斷以選擇強(qiáng)交互特征；（2）在線冗余特征剔除階段，即針對(duì)弱交互特征采用成對(duì)比較機(jī)制評(píng)估與已選特征的冗余度，剔除冗余特征以得到強(qiáng)區(qū)分能力的特征子集。最后，在10個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明本文所提算法具有較好的分類性能。

1 鄰域熵與鄰域互信息

本章將解釋鄰域熵與鄰域互信息相關(guān)概念。

定義1[18]設(shè)U={x1,x2,…,xn}為論域，C={a1,a2,…,am}為描述樣本的條件屬性，D為決策屬性，則稱NDS=U,C,D為鄰域決策系統(tǒng)。

定義2[18]?xi,xj,xk∈U，都存在唯一確定的實(shí)函數(shù)Δ與之對(duì)應(yīng)，且Δ滿足：

（1）Δ(xi,xj)≥0當(dāng)且僅當(dāng)xi=xj,Δ(xi,xj)=0。

（2）Δ(xi,xj)=Δ(xj,xi)。

（3）Δ(xi,xk)≤Δ(xi,xj)+Δ(xj,xk)。則稱Δ是U上的距離函數(shù)，U,Δ是度量空間。

定義3[18]設(shè)U,Δ為非空度量空間，x∈U，δ≥0，稱點(diǎn)集δ(x)是樣本x以δ大小為半徑的鄰域信息粒。

定義4[18]給定鄰域決策系統(tǒng)NDS=U,C,D，A?C，NA表示A的鄰域關(guān)系。若δA(xi)表示xi在A下得到的鄰域，那么xi不確定性可表示為：

于是，A的鄰域熵可表示為：

定義5[18]設(shè)A,B?C，則xi在A?B上的鄰域可表示為δA?B(xi)，因此，A和B鄰域聯(lián)合熵為：

當(dāng)B為決策屬性D時(shí)，此時(shí)

令δD(xi)=Dxi，則特征子集與類標(biāo)簽的聯(lián)合熵定義為：

定義6[18]設(shè)A,B?C，則B相對(duì)A的鄰域條件熵為：

定義7[18]設(shè)A,B?C，A和B的鄰域互信息定義為：

定義8[19]設(shè)A,B?C，A和B的對(duì)稱不確定性為：

2 基于鄰域信息交互的在線流特征選擇算法

本章將在線流特征選擇分為在線交互特征選擇和在線冗余特征剔除兩階段。首先給出特征交互的定義，并定義了強(qiáng)交互特征、弱交互特征和不相關(guān)特征等三個(gè)概念以選擇具有重要性和交互性的特征。然后，利用成對(duì)比較在線移除冗余特征，以獲得一個(gè)最具區(qū)分能力的特征子集。

2.1 在線交互特征選擇

定義9[20]給定一個(gè)在線流特征鄰域決策系統(tǒng)NDST=U,C,D,T，其中，U為非空有限樣本集合，C為條件特征集合，D為決策屬性，T為時(shí)間序列。St-1為在t-1時(shí)刻的已選特征子集，?fi∈St-1，ft為t時(shí)刻新到達(dá)的特征。若

則稱ft與fi交互。

定義9只衡量了新到達(dá)特征ft與已選子集中單個(gè)特征的相關(guān)性。但實(shí)際上特征不一定只與單個(gè)特征相關(guān)，也可能與多個(gè)特征相關(guān)。在線特征選擇過(guò)程中，只考慮新到特征與單個(gè)特征的交互性會(huì)遺漏重要特征?；诖耍疚奶岢鲋苯佑?jì)算新到特征ft與整個(gè)已選子集St-1的交互度。

定義10給定在線流特征鄰域決策系統(tǒng)NDST=U,C,D,T，C為條件特征集合，D為決策屬性，St-1為在t-1時(shí)刻的已選特征子集，ft為t時(shí)刻新到達(dá)的特征。則ft與St-1的交互度可定義為：

基于此，提出三種特征交互定理，分別為：強(qiáng)交互特征、弱交互特征和不相關(guān)特征。

定理1（強(qiáng)交互特征）給定在線流特征鄰域決策系統(tǒng)NDST=U,C,D,T，若F(ft);St-1;D>1，則ft是強(qiáng)交互特征，將其選入候選子集中。

證明 由定義9可知

∵NMIδ(ft,fi;D)>NMIδ(ft;D)+NMIδ(fi;D)

∴若ft與St-1交互，則

即

定理2（弱交互特征）給定在線流特征鄰域決策系統(tǒng)NDST=U,C,D,T，若0

證明 如定理1所示。

定理3（不相關(guān)特征）給定在線流特征鄰域決策系統(tǒng)NDST=U,C,D,T，若F(ft);St-1;D=0，則ft是不相關(guān)特征。

證明 如定理1所示。

2.2 在線冗余特征剔除

基于上述分析，若新到特征為弱交互特征，則需進(jìn)一步與已選特征進(jìn)行冗余性分析。公式（12）用于判斷新到特征ft能否加入已選子集St-1以及能否剔除冗余特征：

其中，λ為閾值。當(dāng)且僅當(dāng)S(ft,fi,D)>λ時(shí)才可將原子集中的特征剔除。當(dāng)0

2.3 基于鄰域信息交互的在線流特征選擇算法

根據(jù)在線交互特征選擇和在線冗余分析兩階段，可提出基于鄰域信息交互的在線流特征選擇算法，算法步驟如下：

算法1基于鄰域信息交互的在線流特征選擇算法

輸入：在線流特征鄰域決策系統(tǒng)NDST=U,C,D,T，去冗余閾值λ，在t-1時(shí)刻，當(dāng)前已選特征子集St-1，已選特征fi

在算法1中，設(shè)論域U中的特征個(gè)數(shù)為|C|，在線交互特征選擇階段的時(shí)間復(fù)雜度為O(|C|)，在線冗余特征剔除階段的時(shí)間復(fù)雜度會(huì)隨當(dāng)前已選子集St-1規(guī)模的擴(kuò)大而增加。假設(shè)當(dāng)前已選子集St-1中的元素個(gè)數(shù)為，則NII的時(shí)間復(fù)雜度為

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

3.1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)指標(biāo)

為驗(yàn)證提出算法的有效性，實(shí)驗(yàn)選取10個(gè)不同類型數(shù)據(jù)集，既有普通數(shù)據(jù)集，又有高維小樣本數(shù)據(jù)集。包括6個(gè)DNA微陣列數(shù)據(jù)集（SRBCT、BREAST、CAR、GENE3、GENE10和LUNG4）以及4個(gè)普通UCI數(shù)據(jù)集。數(shù)據(jù)的樣本數(shù)量從62到20 000，特征個(gè)數(shù)從17到9 217，類別從2類到26類。表1給出所用數(shù)據(jù)集的相關(guān)描述信息。

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental datasets

本實(shí)驗(yàn)中采用KNN(K=3)和線性支持向量機(jī)（LSVM）這兩個(gè)基分類器對(duì)已選的特征子集進(jìn)行分類精度的評(píng)價(jià)，在實(shí)驗(yàn)中使用10折交叉驗(yàn)證。對(duì)于自適應(yīng)鄰域半徑δ，本算法借鑒文獻(xiàn)[21]中的鄰域半徑來(lái)確定論域U每個(gè)樣本的鄰域大小。實(shí)驗(yàn)平臺(tái)統(tǒng)一采用Matlab R2016a，并且所有的實(shí)驗(yàn)都是在同一臺(tái)Inter?i5，2.9 GHz，4 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行。

3.2 冗余判斷參數(shù)λ分析

為分析冗余判斷閾值λ的取值對(duì)NII的影響，本節(jié)選擇λ=0,0.01,0.02,0.03,0.04,0.05，分析λ在不同取值下對(duì)BREAST、SONAR、GENE10和LUNG4數(shù)據(jù)集分類精度的影響，結(jié)果分別如圖1和圖2所示。

圖1 不同λ在KNN分類器上的性能對(duì)比Fig.1 Predictive accuracy using KNN on different λ

圖2 不同λ在LSVM分類器上的性能對(duì)比Fig.2 Predictive accuracy using LSVM on different λ

由圖1可知，當(dāng)使用KNN分類器時(shí)，4個(gè)數(shù)據(jù)集的預(yù)測(cè)精度都隨λ值的增大而增大，并在λ=0.05時(shí)達(dá)到最大值。表明當(dāng)λ=0.05時(shí)，4個(gè)數(shù)據(jù)集能獲得最佳的分類精度。由圖2可知，當(dāng)使用LSVM分類器時(shí)，BREAST和SONAR數(shù)據(jù)集的分類性能在λ=0.05時(shí)有較為明顯的提升。GENE10和LUNG4數(shù)據(jù)集在λ=0.02后整體趨勢(shì)比較平穩(wěn)，但總體還是呈上升狀態(tài)?？偠灾?，當(dāng)λ=0.05時(shí)，NII在4個(gè)數(shù)據(jù)集上相較于λ=0,0.01,0.02,0.03,0.04，還是取得整體最優(yōu)的情況。

接著分析4個(gè)數(shù)據(jù)集在不同λ下運(yùn)行10次得到的平均運(yùn)行時(shí)間，結(jié)果由表2所示。由表2可知，λ對(duì)SONAR和LUNG4數(shù)據(jù)集的運(yùn)行時(shí)間幾乎沒(méi)有影響。GENE4數(shù)據(jù)集隨λ的增大，運(yùn)行時(shí)間的增幅比較平緩。BREAST數(shù)據(jù)集的運(yùn)行時(shí)間的波動(dòng)也不大。

綜上所述，結(jié)合不同分類器的評(píng)價(jià)結(jié)果，得出NII在λ=0.05時(shí)，表現(xiàn)最佳。因此在以下實(shí)驗(yàn)中，在線冗余分析階段的閾值將采用λ=0.05。那是因?yàn)樵谌哂嗵卣魈蕹A段，參數(shù)λ用于判斷候選特征與已選特征的冗余度，當(dāng)λ取值過(guò)小時(shí)，重要特征會(huì)被誤刪；當(dāng)λ取值過(guò)大時(shí)，冗余特征會(huì)選入。實(shí)驗(yàn)分析，隨著λ取值逐漸增大，算法分類性能逐步提高，達(dá)到某個(gè)分類性能后會(huì)保持穩(wěn)定，然后逐步下降，但運(yùn)行時(shí)間和選擇特征數(shù)量不斷上升。因此，從時(shí)間性能、分類性能和所選特征數(shù)量等因素考慮，選擇λ=0.05作為最優(yōu)值。

3.3 與在線流特征選擇算法對(duì)比

為評(píng)價(jià)NII的有效性，將選擇4種目前較為流行的在線流特征選擇算法與本研究提出的算法進(jìn)行比較：可擴(kuò)展和準(zhǔn)確的在線流特征選擇算法（SAOLA）[8]、在線流特征選擇算法（OSFS）[7]、高維類非平衡數(shù)據(jù)的在線特征選擇算法（K-OFSD）[9]，以及基于鄰域粗糙集的在線流特征選擇算法（OFS-A3M）[10]。其中，SAOLA和OSFS算法中的顯著性水平參數(shù)α均設(shè)置成α=0.01，K-OFSD算法中的K值設(shè)置參考文獻(xiàn)[9]。

表3 、表4分別表示5種算法分別在KNN(K=3)和LSVM分類器上的預(yù)測(cè)精度，表中加粗字體表示該數(shù)據(jù)集的最高分類精度。表5和表6分別記錄5種算法在10個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間和所選子集大小，加粗字體表示該數(shù)據(jù)集的最短運(yùn)行時(shí)間和最小特征子集數(shù)。

表3 5種算法在KNN分類器上的預(yù)測(cè)精度Table 3 Predictive accuracy of five algorithms on KNN classifier

表4 5種算法在LSVM分類器上的預(yù)測(cè)精度Table 4 Predictive accuracy of five algorithms on LSVM classifier

表5 5種算法在10個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間Table 5 Running time of five algorithms on ten datasets s

表6 5種算法在10個(gè)數(shù)據(jù)集上的所選特征個(gè)數(shù)Table 6 Number of selected features of five algorithms on ten datasets

（1）NII vs.SAOLA。由表3可知，在KNN分類器下，NII在10數(shù)據(jù)集上的預(yù)測(cè)精度都優(yōu)于SAOLA。在LSVM分類器上，10個(gè)數(shù)據(jù)集上也有8個(gè)數(shù)據(jù)集的精度優(yōu)于SAOLA。觀察表6可知，在保證預(yù)測(cè)精度的前提下，NII在大部分?jǐn)?shù)據(jù)集上選擇交互特征的數(shù)量遠(yuǎn)小于SAOLA。因?yàn)镾AOLA算法采用兩兩比較的方法在線計(jì)算特征間的相關(guān)性可降低時(shí)間復(fù)雜度，NII算法以所有特征子集為條件計(jì)算特征間的相關(guān)性，并在冗余階段再采用成對(duì)比較方法剔除冗余特征，會(huì)造成時(shí)間復(fù)雜度比較高。然而，NII算法在線交互階段選擇強(qiáng)交互特征，在線冗余分析階段選擇弱交互特征使得分類精度較高。

（2）NII vs.OSFS。由表3和表4可知，在KNN和LSVM分類器上，NII幾乎在所有的數(shù)據(jù)集上取得更高的預(yù)測(cè)精度。由于OSFS在大部分?jǐn)?shù)據(jù)集上選擇最少的特征，所以運(yùn)行時(shí)間較短。但過(guò)少的特征不能保證分類性能，表明在選擇過(guò)程中誤刪了重要特征。

（3）NII vs.K-OFSD。由表3和表4可知，在KNN和LSVM分類器上，NII在10個(gè)數(shù)據(jù)集中至少有7個(gè)精度高于K-OFSD。但由表6可知，K-OFSD選擇子集大小不穩(wěn)定，如CAR數(shù)據(jù)集選擇96個(gè)，而WAVEFORM數(shù)據(jù)集只選擇了1個(gè)特征，最終導(dǎo)致K-OFSD選擇最多的特征。在運(yùn)行時(shí)間上，K-OFSD略微遜色于NII。

（4）NII vs.OFS-A3M。由表3可知，在KNN分類器上，10個(gè)數(shù)據(jù)集中的7個(gè)取得較優(yōu)的性能。由表4可知，在LSVM分類器上，10個(gè)數(shù)據(jù)集中有9個(gè)數(shù)據(jù)集的預(yù)測(cè)精度優(yōu)于OFS-A3M算法。OFS-A3M雖選擇較少的特征，但運(yùn)行時(shí)間遠(yuǎn)大于NII，特別是在LETTER數(shù)據(jù)集上，說(shuō)明OFS-A3M不能很好地處理大樣本數(shù)據(jù)集。

綜上所述，在KNN和LSVM分類器上，NII均能選出具有強(qiáng)區(qū)分能力的特征子集。相較于其他4個(gè)對(duì)比算法，NII能在運(yùn)行時(shí)間和所選子集大小合理的情況下，獲得最好的分類性能。

接下來(lái)為更直觀地比較NII與其他算法之間的差異，采用盒形圖對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

圖3 和圖4為NII與4種對(duì)比算法在KNN和LSVM分類器上的預(yù)測(cè)精度對(duì)比。由圖3和圖4可知，就平均預(yù)測(cè)精度而言，NII與SAOLA算法相當(dāng)，但明顯優(yōu)于其他3個(gè)對(duì)比算法?？紤]整體穩(wěn)定性，NII比4個(gè)對(duì)比算法都要穩(wěn)定。

圖3 5種算法在KNN分類器上的預(yù)測(cè)精度對(duì)比Fig.3 Comparison of predictive accuracy of five algorithms on KNN classifier

圖4 5種算法在LSVM分類器上的預(yù)測(cè)精度對(duì)比Fig.4 Comparison of predictive accuracy of five algorithms on LSVM classifier

綜上所述，NII算法整體上優(yōu)于4種流特征選擇算法，而且更加穩(wěn)定。

4 結(jié)束語(yǔ)

大部分在線流特征選擇算法只關(guān)注特征與類標(biāo)簽之間的相關(guān)性，而忽視特征與特征之間交互性的問(wèn)題，本文提出基于鄰域信息交互的在線流特征選擇算法，該算法通過(guò)計(jì)算新到達(dá)的特征與整個(gè)已選特征子集的交互性，選擇強(qiáng)交互的特征加入已選子集中，對(duì)弱交互的特征再進(jìn)行成對(duì)冗余判斷，以獲得具有強(qiáng)分類能力的特征子集。大量的實(shí)驗(yàn)結(jié)果表明了所提算法的有效性。由于本文并未考慮特征間的因果關(guān)系，因此未來(lái)的工作將進(jìn)一步考慮具有因果關(guān)系的在線交互特征選擇。