基于模糊鄰域判別指數的在線流組特征選擇

徐久成，孫元豪+，韓子欽

(1.河南師范大學 計算機與信息工程學院，河南 新鄉 453007；2.河南師范大學 智慧商務與物聯網技術河南省工程實驗室，河南 新鄉 453007)

0 引 言

特征選擇是一種常見的數據預處理技術[1，2]。傳統的特征選擇假定特征空間是不變的[3]，然而在實際情況中，特征往往隨著時間逐個或逐組地獲得，特征空間信息未知[4]。如何在流特征環境中進行高效的特征選擇具有重要的實際應用價值。

根據特征組的原始結構信息，在線流特征選擇可分為在線流單特征選擇和在線流組特征選擇[5，6]。在線流單特征選擇方法對特征單獨處理，忽略了特征流存在的組結構信息[7-10]。而對特征組執行特征選擇比單獨對特征執行特征選擇效果更好[11]。Yu等[12]提出一種可擴展的流特征選擇方法，可在群組和個體兩個層面對特征組進行有效選擇。Zhou等[5]考慮到流特征組內和組間的交互作用，并通過彈性網回歸模型中的懲罰函數將變量的系數進行調整，選擇有價值的變量，設計了一種新的群組流特征選擇方法。然而，現有的在線流特征選擇方法不能有效地處理模糊和不確定性環境下的任務。

近年來，基于模糊粗糙集的特征選擇方法在處理具有模糊性和不確定性的分類問題中得到了廣泛的應用[13-15]。Xu等[16]重新定義了模糊鄰域關系并將其引入到條件熵中，提出了一種新的模糊鄰域條件熵。Wang等[17]提出一種鄰域判別指數，與香農熵具有相似的性質，可反映特征子集的區分能力。但這些基于模糊粗糙集理論的方法不能解決流環境下的特征選擇問題。

因此，為了解決模糊性和不確定性背景下的流特征選擇問題，本文提出一種基于模糊鄰域判別指數的在線流組特征選擇方法，并通過與5種流行算法的對比實驗，論證了該方法的有效性。

1 基礎知識

設OGDS= 為在線流組決策系統。其中U={x1，x2，…，xm} 為樣本的論域集合，G={G1，G2，…，Gt} 為條件特征集合，t為時間序列，Gi={f1，f2，…，fn} 為G中的一組特征，D為決策特征集合，在t時刻特征組Gt流入特征空間，h為映射函數。

1.1 模糊鄰域熵

令A?G為U上的一個條件特征子集，則屬性A引出的一組模糊二元關系表示為RA，RA(x，y)=1-|xA-yA|，若RA同時滿足：①自反性：RA(x，y)=1，?x∈U；②對稱性：RA(x，y)=RA(y，x)，?x，y∈U。則稱RA為U上的一組模糊相似關系。

定義1[16]設λ為模糊鄰域半徑，則對于?x∈U，x關于A的參數化的模糊鄰域信息粒定義為

(1)

關于A的模糊鄰域熵定義為

(2)

定義2[16]假設D將樣本集合U劃分為l個等價類，U/D={D1，D2，…，Dl}，由D生成的模糊決策為FD={FD1T，FD2T，…，FDlT}，其中FDj為樣本決策的模糊等價類，則x在Dj上的隸屬度表示為

(3)

式中：j=1，2，…，l，|·|表示基數，|λA(x)∩Dj|表示樣本對λA(x)的隸屬度不大于Dj的個數。

1.2 鄰域判別指數

(4)

鄰域判別指數的計算基于鄰域相似關系的基數，具有與香農熵及其變體相似的性質，是一種度量特征子集區分能力的有效方法[18]。

1.3 Lasso模型

Lasso模型是彈性網策略的一種特殊形式，令X為數據矩陣，ê為投影向量，則決策類向量表示為Y=XTê，設γ為調節正則化數目的參數，Lasso方法通過最小化以下目標函數來選擇最佳的ê

(5)

2 模糊鄰域判別指數的不確定性度量

本節首先定義了模糊鄰域判別指數，然后提出了模糊鄰域互判別指數和模糊對稱不確定性的概念，在此基礎上擴展了一些不確定性度量方法。

2.1 模糊鄰域判別指數

定義4 給定OGDS= 為在線流組決策系統，其中U={x1，x2，…，xm}，設A?G，λA(x) 為x關于A的參數化的模糊鄰域粒，則關于A的模糊鄰域判別指數定義為

(6)

根據式(6)可知，模糊鄰域判別指數通過模糊鄰域粒的基數來計算，而式(2)中模糊鄰域熵通過累加模糊鄰域相似類的基數獲得。因此，模糊鄰域判別指數的計算復雜度略小于模糊鄰域熵。

性質1 若A?B，則FNDIλ(A)≤FNDIλ(B)。

證明：令 (xi，xj)∈λB(x)，可得RB(xi，xj)≤λ，由A?B可得RA(xi，xj)≤λ，因此 (xi，xj)∈λA(x)，由模糊鄰域粒的性質可知λB(x)?λA(x)，且|λB(x)|≤|λA(x)|。根據定義4可得FNDIλ(A)≤FNDIλ(B)。

性質1表明模糊鄰域判別指數的大小隨著特征組的增大單調遞增。

定義5 設A，B?G，則A和B的模糊鄰域互判別指數定義為

(7)

特別地，當B=D時，使用樣本生成的模糊決策FD來計算特征與決策類的模糊鄰域互判別指數，可以更充分地利用決策信息，進而更好地處理模糊性和不確定性數據。

模糊鄰域互判別指數的值越大，表明該特征與決策類越相關，該特征就越重要。

性質2

FNMDIλ(A；B)=

FNDIλ(A)+FNDIλ(B)-FNDIλ(A，B)

證明

FNDIλ(A)+FNDIλ(B)-FNDIλ(A，B)

定義6 設A，B?G，則A和B的模糊對稱不確定性定義為

(8)

模糊鄰域互判別指數和模糊對稱不確定性都可以用于評價相關特征的重要性，利用兩種度量標準有利于選擇更佳的特征子集，提升算法的性能。

2.2 基于不確定性度量的在線流組特征選擇

接下來將在線流組特征選擇分為組內特征選擇和組間特征選擇兩部分，并擴展了一些不確定性度量方法。首先計算特征的重要度在組內選擇具有強近似能力的特征流入特征空間，然后根據交互增益和對比度選擇具有交互作用的特征。

2.2.1 組內特征選擇

定義7 給定OGDS= 為一個在線流組決策系統，設A?Gt，a∈A，則特征a關于決策D的重要度定義為

Sig(a，A，D)=

FNMDIλ(A；D)-FNMDIλ(A-{a}；D)

(9)

定理1 若Sig(a，A，D)>0，則稱特征a是重要的，否則稱特征a是不重要的。

證明：當Sig(a，A，D)>0時，由式(9)可得FNMDIλ(A；D)>FNMDIλ(A-{a}；D)，這表明去掉特征a導致模糊鄰域互判別指數的值變小，特征組提供的近似能力變弱，因此特征a是重要的。顯然，當不滿足該條件時，特征a是不重要的。

通過將式(9)應用到組內特征選擇，可以遍歷特征組Gi中的所有特征，選擇重要的特征，并將選擇后的特征組S′t流入特征空間。

2.2.2 組間特征選擇

定義8 給定OGDS= 為一個在線流組決策系統，設f為S′t中的一個特征，St-1為t-1時刻已選擇的特征集合，則特征f關于St-1的交互增益定義為

IGλ(f，St-1)=FSUλ(f，St-1；D)-

FSUλ(f；D)-FSUλ(St-1；D)

(10)

定理2 若IGλ(f，St-1)>0，則特征f具有交互作用。

證明：當IGλ(f，St-1)>0時，由式(10)可得FSUλ(f，St-1；D)>FSUλ(f；D)+FSUλ(St-1；D)，這表明f和St-1在一起所提供的信息大于二者分開所提供信息之和，因此特征f具有交互作用。

如果特征f具有交互作用，那么需進一步對該特征進行分析。

定義9 給定OGDS= 為一個在線流組決策系統，設f1為S′t中有交互作用的特征，f2為St-1中的特征，則特征f2關于f1的對比度定義為

Cλ(f1，f2)=FSUλ(f1，D)-FSUλ(f2；D)

(11)

定理3 若Cλ(f1，f2)>0，則特征f1是重要的，特征f2是冗余的。

證明：定義9衡量了新到達特征與已選特征集合的相關性。當Cλ(f1，f2)>0時，由式(11)可得FSUλ(f1；D)>FSUλ(f2；D)，這表明特征f1所提供的信息是大于特征f2所提供的信息的，因此特征f1是重要的，特征f2是冗余的。

當沒有新特征流入時，使用Lasso方法對所有選定的特征進行重新評估，丟棄不相關的特征。

3 在線流組特征選擇算法

基于上述理論，本文提出了一種基于模糊鄰域判別指數的在線流組特征選擇(online group streaming feature selection based on fuzzy neighborhood discrimination index，OGSFS-FNDI) 算法。算法描述如下：

算法1：OGSFS-FNDI

輸入：OGDS=，模糊鄰域半徑λ，組規模g；

輸出：已選特征子集S.

(1)初始化:S=?;

(2)在t時刻流入新的特征組Gt;

(3)/*組內特征選擇*/

(4)fori=1 to|Gt|

(5) 計算fi的重要度Sig(fi,Gt,D);

(6) ifSig(fi,Gt,D)>0

(7) LetS′t=S′t∪{fi};

(8) end if

(9)end for

(10)/*組間特征選擇*/

(11)forj=1 to|S′t|

(12) 計算fj的交互增益IGλ(fj,St-1);

(13) ifIGλ(fj,St-1)>0

(14) fork=1 to|St-1|

(15) 計算fj和fk的對比度Cλ(fj,fk);

(16) ifCλ(fj,fk)>0

(17) LetS=S∪{fj};S=S-{fk};

(18) end if

(19) end for

(20) end if

(21)end for

(22)直到沒有Gt流入,使用Lasso選擇特征子集S;

(23)returnS.

在算法1中，OGSFS-FNDI算法的時間復雜度由步驟(11)的循環決定，設組內特征選擇階段選擇的特征個數為|S′t|，t-1時刻已選擇的特征個數為|St-1|，樣本個數為m。步驟(15)的時間復雜度在最壞情況下為O(m2)，因此，OGSFS-FNDI算法的時間復雜度在最壞情況下為O(m2×|S′t|×|St-1|)。顯然|S′t|和|St-1|的值遠小于特征維度|G|，可見OGSFS-FNDI算法選擇最佳特征子集的效率較高。

4 實驗及結果分析

為了驗證OGSFS-FNDI算法的有效性，實驗選取8個公共數據集，包括3個UCI數據集(Wpbc、Sonar、Heart)和5個DNA微陣列數據集(Colon、DLBCL、Lymphoma、Breast、MLL)。上述數據集可從http：//arc-hive.ics.uci.edu/ml/index.php和http：//csse.sz u.edu.cn/staff/zhuzx免費下載，表1給出相關數據集的詳細信息。

表1 數據集描述

本文實驗均在Windows 10 PC，Intel Core i5-3470 CPU@3.20 GHz，4.0 GB RAM環境下進行，并使用Matlab2016a實現和完成所有對比實驗。為了減少不同量綱對實驗結果的影響，通過以下公式對數據集進行歸一化

F(xi)=(xi-xmin)/(xmax-xmin)

(12)

經過預處理操作，數據被歸一化到[0，1]區間。借鑒文獻[5]中的實驗設置，本節選取KNN(k=3)和CART分類器對特征子集進行評估，并將分類準確率和選擇特征個數作為評價指標，分析了OGSFS-FNDI算法和對比算法在相關數據集上的分類性能。

本節采用十折交叉驗證以測試算法分類性能的準確性，每個數據集被隨機分成10份，輪流將其中9份作為訓練數據集，另外一份作為測試數據集，取10次分類準確率的平均值作為最終的結果。所有的對比算法都基于相同的設計方法。

4.1 參數分析

OGSFS-FNDI算法中有兩個參數，模糊鄰域半徑λ用于調節模糊鄰域的大小，組規模g用于控制在線流組特征選擇的特征組大小。為了分析兩個參數的取值對算法的影響，本節將λ的值設置為0.1到1，步長為0.1，并根據文獻[5]的組規模，將g的值設置為50、100、200、400、800，這個區間設置針對高維數據集是有效的，但是面對低維數據集時并不能發揮劃分特征組的作用，因此對于低維數據集將g的值設置為5、10、20、30、60，這更有利于模擬實際工作中特征流的組劃分情況。本節重點討論了不同參數對OGSFS-FNDI算法在分類準確率方面的影響，使用KNN和CART分類器得到的分類準確率隨參數變化的曲面圖大致相似，因此本文僅列出了使用KNN分類器的情況。

圖1呈現了所提算法在3個低維數據集上的分類準確率隨參數的變化曲面。由圖1可知，參數的變化會對不同的數據集產生不同程度的影響。對于Wpbc和Sonar數據集，當λ的值大于0.4時分類性能整體趨勢較為平穩，在大多數參數上均達到了較高的分類準確率，由于數據集的特征維度較低，此時g的值對其分類性能的影響并不明顯。而對于Heart數據集，分類性能隨著參數的變化呈現不規律性，但整體的分類準確率仍保持在一個穩定的區間內。

圖1 3個低維數據集在不同參數下分類準確率的變化曲面

圖2為OGSFS-FNDI算法在5個高維數據集上的分類準確率隨參數的變化曲面。觀測圖2，模糊鄰域半徑和組規模的大小在DNA微陣列數據集上更能呈現出規律性。對于Colon、DLBCL和Lymphoma數據集，算法的分類性能隨著參數變化的趨勢大致相同，隨著λ的增大分類準確率也呈現上升的狀態，尤其是當λ的值大于0.4時分類準確率具有明顯的提升，且隨著g的增大分類準確率同時也在增加。在Breast和MLL數據集上，當λ的值小于0.6時的分類準確率整體呈現較低的水平，在λ大于0.6且g的值較大時達到分類精度的最優值。這表明由于DNA微陣列數據集的特征維數較高，數據具有模糊性和不確定性，模糊鄰域判別指數作為一種有效的度量方法，可以有效地考慮到特征之間的相關性，而使用較大的模糊鄰域半徑和組規模往往可以充分利用特征組的分類信息，從而提高特征子集的強近似能力。

圖2 5個高維數據集在不同參數下分類準確率的變化曲面

總的來說，OGSFS-FNDI算法可以在大部分數據集上找到最優的參數以達到較高的分類準確率，但對于不同的數據集所適用的參數是不同的。

4.2 實驗對比分析

為了評價算法的有效性，本節選擇了目前較流行的5種算法與OGSFS-FNDI算法進行比較，其中包括兩種在線流組特征選擇算法(OGSFS-FI[5]、Group-SAOLA[12])，兩種在線流單特征選擇算法(SFS-FI[7]、K-OFSD[8])和一種基于模糊鄰域條件熵的特征選擇算法(FNCE[16])。對比算法的參數設置均與原論文描述一致，且下文呈現的數據均為算法所達到的最優值。接下來分析了算法在分類準確率和選擇特征個數方面的性能對比。

表2和表3分別呈現了對比算法在KNN和CART分類器上取得的分類準確率，加粗字體表示某一算法在該數據集上取得最佳分類準確率，最后一行列出了算法在所有數據集上的平均準確率。

表2 6種算法在KNN分類器上的分類準確率對比

表3 6種算法在CART分類器上的分類準確率對比

由表2和表3可見，基于KNN和CART分類器，OGSFS-FNDI算法在Wpbc、Sonar、Heart、Lymphoma數據集上的表現均優于其它5種對比算法，且在8個數據集上分類準確率的平均值均排名第一。盡管OGSFS-FI和Group-SAOLA算法都可以處理在線流組特征選擇問題，但其在兩個分類器上的分類準確率都低于本文所提算法。K-OFSD算法與本文所提算法在分類準確率方面保持在同一水平，且在處理DLBCL、MLL這類高維類不平衡數據集時該算法可以實現更高的分類準確率。SFS-FI算法具有最差的分類性能，且K-OFSD和SFS-FI算法僅能在單特征層面進行在線流特征選擇。FNCE算法整體的分類性能較差，且只能處理靜態的特征選擇。OGSFS-FNDI算法在高維數據集上的分類準確率明顯高于其它對比算法，這是因為該算法基于粗糙集理論進行推廣，在處理DNA微陣列數據集這類不確定性數據時有著明顯的優勢。同時，算法還考慮到了數據的模糊概念，使用參數化的模糊鄰域信息粒構建隸屬度函數，實驗結果表明該算法對具有模糊性和不確定性數據的處理有較好的效果。

為了更直觀地展示OGSFS-FNDI算法的有效性，本節繪制了盒型圖來描述對比算法的分類準確率之間的離散分布差異，圖3和圖4指出了所有算法在KNN和CART分類器上所獲得分類準確率的分布情況，盒型圖中間的橫線表示中位數，“+”表示離群的異常值。

圖3 6種算法在KNN分類器上的盒型圖對比

圖4 6種算法在CART分類器上的盒型圖對比

由圖3和圖4可知，OGSFS-FNDI算法在兩個分類器上分類準確率的平均性能(中位數)都是最強的。在KNN和CART分類器上，算法在上四分位數和下四分位數的多數集中在分類準確率較高的區間，且并未出現異常值。對比算法的分類準確率表現較差，中位線所在水平均明顯低于所提算法，且其分布并不穩定。Group-SAOLA和SFS-FI算法在整體上處于較低水平；OGSFS-FI和FNCE算法呈現的數值區間較大；而K-OFSD算法在CART分類器上出現了離群的異常值，這表明對比算法雖然在部分數據集上分類性能較好，但其表現并不穩定。由此可得，OGSFS-FNDI算法的分類性能和其它5種算法相比更為穩定。

表4描述了6種算法在8個數據集上選擇的特征個數。觀察表4發現，OGSFS-FNDI算法在8個數據集上能夠實現特征約簡的目的，但在所有的對比算法中表現并未達到最優。盡管Group-SAOLA和SFS-FI算法在選擇特征個數上體現了很大的優勢，但通過表2和表3可見其分類精度明顯低于其它算法，這表明在特征選擇過程中丟失了較為重要的特征信息。

表4 6種算法在8個數據集上選擇的特征個數

與OGSFS-FNDI算法相比，Group-SAOLA和SFS-FI算法的時間復雜度分別為O(|St-1|×|G|) 和O(m2)，盡管其表現較優，但結合實驗結果可知其分類準確率較低。此外，K-OFSD和FNCE算法的時間復雜度均為O(m2×|G|)，而OGSFS-FI算法的時間復雜度為O(k3+k2×|St-1|)，其中k為算法調用彈性網的次數，時間復雜度較高。根據實驗結果可知，OGSFS-FNDI算法最終選擇的特征子集很小，即所提算法在實際應用中的時間復雜度遠低于最壞情況。因此，與其它5種特征選擇算法相比，本文算法在時間復雜度上的表現較優。

綜上所述，本文所提的OGSFS-FNDI算法能夠在選擇較少特征個數的同時呈現出較優且穩定的分類性能。

5 結束語

針對大多數在線流組特征選擇方法無法處理模糊性和不確定性數據的問題，本文提出了一種基于模糊鄰域判別指數的在線流組特征選擇算法。該算法基于模糊鄰域判別指數擴展了相關的不確定性度量，同時使用組內特征選擇和組間特征選擇兩種策略，以在線的方式選擇能夠提高分類性能的特征。通過一系列實驗對比及分析，驗證了所提算法可以有效且穩定地選擇最佳特征子集。雖然OGSFS-FNDI算法在大部分數據集上達到更高的分類精度，但窮舉法尋找最佳參數的方式效率較低，因此未來的工作將重點研究自動尋找最優參數的在線流組特征選擇方法。