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

李瓏珠，林耀進，呂 彥，盧 舜，王晨曦

1.閩南師范大學 計算機學院，福建 漳州363000

2.數(shù)據(jù)科學與智能應用福建省高等學校重點實驗室，福建 漳州363000

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

流特征是指樣本空間固定不變，而特征空間是動態(tài)未知的且特征逐個獲取[4]。例如，從高分辨率的行星圖像進行火星隕石坑檢測[5]中，可以為遠距離測量行星表面的相對年齡提供唯一的解決方案，而且從行星圖像中生成并儲存數(shù)以萬計的圖像特征來幾乎覆蓋火星表面的全范圍是不可行的，因此圖像特征需提取時立即進行在線選擇。目前，流特征選擇面臨的主要問題有：（1）特征維度可能隨著時間的推移而增加，甚至可能擴展到無限大。（2）在單位時間內特征逐個流入，且要求特征在達到時能夠被實時處理。根據(jù)樣本的語義信息，在線流特征選擇算法可以分為單標記在線流特征選擇算法和多標記在線流特征選擇算法。單標記在線流特征選擇算法包括流向特征選擇算法（Streamwise Feature Selection，α-investing）[6]，在線流特征選擇算法（Online Streaming Feature Selection，OSFS）[7]，可擴展和準確的在線流特征選擇算法（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等人的基礎上，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]還將流特征選擇與層次分類結合，提出了基于鄰域粗糙集的大規(guī)模層次分類在線流特征選擇算法（Large-Scale Hierarchical Classification Online Streaming Feature Selection Based on Neighborhood Rough Set，OHFS）。

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

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

1 鄰域熵與鄰域互信息

本章將解釋鄰域熵與鄰域互信息相關概念。

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

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

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

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

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

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

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

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

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

當B為決策屬性D時，此時

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

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

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

定義8[19]設A,B?C，A和B的對稱不確定性為：

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

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

2.1 在線交互特征選擇

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

則稱ft與fi交互。

定義9只衡量了新到達特征ft與已選子集中單個特征的相關性。但實際上特征不一定只與單個特征相關，也可能與多個特征相關。在線特征選擇過程中，只考慮新到特征與單個特征的交互性會遺漏重要特征。基于此，本文提出直接計算新到特征ft與整個已選子集St-1的交互度。

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

基于此，提出三種特征交互定理，分別為：強交互特征、弱交互特征和不相關特征。

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

證明 由定義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（不相關特征）給定在線流特征鄰域決策系統(tǒng)NDST=U,C,D,T，若F(ft);St-1;D=0，則ft是不相關特征。

證明 如定理1所示。

2.2 在線冗余特征剔除

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

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

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

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

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

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

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

3 實驗及結果分析

3.1 實驗數(shù)據(jù)及評價指標

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

表1 實驗數(shù)據(jù)集Table 1 Experimental datasets

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

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

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

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

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

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

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

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

3.3 與在線流特征選擇算法對比

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

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

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

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

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

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

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

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

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

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

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

接下來為更直觀地比較NII與其他算法之間的差異，采用盒形圖對實驗結果進行分析。

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

圖3 5種算法在KNN分類器上的預測精度對比Fig.3 Comparison of predictive accuracy of five algorithms on KNN classifier

圖4 5種算法在LSVM分類器上的預測精度對比Fig.4 Comparison of predictive accuracy of five algorithms on LSVM classifier

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

4 結束語

大部分在線流特征選擇算法只關注特征與類標簽之間的相關性，而忽視特征與特征之間交互性的問題，本文提出基于鄰域信息交互的在線流特征選擇算法，該算法通過計算新到達的特征與整個已選特征子集的交互性，選擇強交互的特征加入已選子集中，對弱交互的特征再進行成對冗余判斷，以獲得具有強分類能力的特征子集。大量的實驗結果表明了所提算法的有效性。由于本文并未考慮特征間的因果關系，因此未來的工作將進一步考慮具有因果關系的在線交互特征選擇。