基于特征相關的譜特征選擇算法

胡敏杰，林耀進，楊紅和，鄭荔平，傅為

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

基于特征相關的譜特征選擇算法

胡敏杰，林耀進，楊紅和，鄭荔平，傅為

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

針對傳統的譜特征選擇算法只考慮單特征的重要性，將特征之間的統計相關性引入到傳統譜分析中，構造了基于特征相關的譜特征選擇模型。首先利用Laplacian Score找出最核心的一個特征作為已選特征，然后設計了新的特征組區分能力目標函數，采用前向貪心搜索策略依次評價候選特征，并選中使目標函數最小的候選特征加入到已選特征。該算法不僅考慮了特征重要性，而且充分考慮了特征之間的關聯性，最后在2個不同分類器和8個UCI數據集上的實驗結果表明：該算法不僅提高了特征子集的分類性能，而且獲得較高的分類精度下所需特征子集的數量較少。

特征選擇；譜特征選擇；譜圖理論；特征關聯；區分能力；索搜策略；拉普拉斯；分類精度

特征選擇是指在原始特征空間中選擇能讓給定任務的評價準則達到最優的特征子集的過程，是模式識別、機器學習等領域中數據預處理的關鍵步驟之一[1-3]。其主要目標是在不顯著降低分類精度和不顯著改變類分布情況下選擇一個重要特征子集并且移除不相關或不重要的特征，使留下的特征具有更強的分辨率[4]。其中評價準則是特征選擇算法中的關鍵步驟，國內外研究者已設計了多種評價準則，包括距離度量[5]、信息度量[6]和譜圖理論[7-8]等方法。由于基于譜圖理論的特征選擇模型的可理解性及其完備的數學理論，受到了廣泛的關注[8-9]。

根據數據是否帶有標記，基于譜圖理論的特征選擇可分為有監督特征選擇和無監督特征選擇[8-12]。無監督特征選擇算法在構造相似性矩陣時不考慮類信息，通常對給出的樣本值采用核函數構造相似性矩陣。有監督特征選擇算法將類信息引入相似性矩陣中，常根據類別個數來構造對應的相似性矩陣。利用譜圖理論進行特征選擇的主要思想是對鄰接圖Laplacian矩陣進行譜分解，其特征向量反映了樣本的類屬關系[11]?；谠撍枷耄琙hao等[8]設計了一個譜特征選擇框架，框架根據相似性矩陣是否考慮類標記信息分別應用于有監督和無監督算法，而選擇特征子集過程與具體學習器無關，利用特征對樣本分布的影響對特征進行排序。He等[10]結合譜圖理論和特征的局部保持能力提出了基于Laplacian 得分的特征選擇算法。Zhao[8]和He[10]等基于譜圖理論的特征選擇均僅考慮每個單獨的特征按一定的可分性或統計判據進行排隊以形成特征序列，并取靠前的特征子集進行學習。該策略僅在各個特征間統計獨立且類別正態分布時較優，但特征間具有這種關系僅僅是極少數[13]，實際上特征空間中特征之間存在較為緊密的關聯性。

針對已有的基于譜圖理論有監督特征選擇算法存在的上述問題，我們提出融合特征相關的譜特征選擇算法，在原始的整個特征空間中不僅考慮每一個特征的區分力，還考慮特征組的區分性能，迭代地尋找對保持數據的局部結構比上一組特征更強的特征組合。由此，提出了基于特征相關的譜特征選擇算法(spectral feature selection based on feature correlation，SPFC)。實驗結果表明，該算法不僅提高了特征選擇的分類性能，而且獲得了較高的分類精度下所需特征子集的數量較少。

1 譜特征選擇算法

譜特征選擇算法的主要理論是譜圖理論，本文研究的算法是以Laplacian Score特征選擇算法為基礎，因此本節只介紹圖Laplacian矩陣譜分析。

式中nk為類別為k的樣本個數。

令G為一無向有權圖，則鄰接矩陣Wij=Sij(1≤i,j≤m),且W為對稱矩陣。令度矩陣D為

由式(1)可以看出度矩陣D是一個對角矩陣，對角線上的每個元素是鄰接矩陣W每一行或每一列的和。度矩陣可以解釋為每個樣本周圍圍繞的其他樣本的密集度，度矩陣中的元素越大，意味著有更多的樣本靠近這個元素代表的樣本。

由鄰接矩陣和度矩陣得到相應的Laplacian矩陣L和正則化的Laplacian矩陣L

根據Laplacian矩陣的性質[5]，給出下面定義：

定義1 Laplacian矩陣的最小特征值為0，對應特征向量為單位向量

letI=[1 1 … 1]T,L*I=0

定義2 對于任意一個n維向量x(數據集中的特征列)，都滿足下式成立：

定義3 對于任意一個n維向量x(數據集中的特征列)，任意一個實數，都有(特征列中的每個元素減去一個相同的值得到的新特征列仍然保持結果不變)：

?x∈Rn,?t∈R,x-t*eTL(x-t*e)=xTLx

譜圖理論說明，Laplacian 矩陣的特征值與特征向量包含著數據集的樣本分布結構。譜特征選擇在選取有強識別度的特征時，以特征取值的分布是否與樣本分布的結構保持一致作為特征選擇的評價標準。例如在圖1中，每個圖形(三角和星)表示一個樣本，形狀不同意味樣本在同一特征上的取值不同，各圓形分別為類1和類2的區域，即同一區域內的樣本屬于同一類別。在圖1左側中屬于同一類的樣本在特征F1上取值近似相同，而不屬于同一類的樣本在特征F1上取值不同，因此特征F1對類1和類2就有很好的識別能力，此時稱特征F1的取值分布與樣本分布一致。在圖1右側中特征F2的取值分布則與樣本分布不一致，F2對類1和類2不具有很好的識別能力。因此在譜特征選擇算法中會選取F1而不選F2。

圖1 特征與樣本分布一致性示意圖Fig.1 The characteristics and the sample distribution consistency schematic diagram

而譜特征選擇算法將選擇那些與樣本分布結構一致的特征，即選擇那些使得式(2)取較小值的特征[7]：

式中：Fr表示第r個特征,fr是第r個特征向量，fri和frj表示第r個特征上的i,j1≤i,j≤m個樣本的取值，Vfr表示第r個特征fr的方差。

一個隨機變量x的方差定義為[7]：

式中：M是數據的流行結構，u表示x期望值，dP是一個概率度量。根據譜圖理論[7]，dP可以用對角矩陣D估計出來，因此特征fr的方差V(fr)為

Vfr=∑i(fri-ur)2Dii

式中ur表示第r個特征fr的期望值，定義為

∑i,jSij(fri-frj)2越小表示在樣本分布結構圖里近鄰的樣本在該特征上差異很小，即一個識別能力強的特征會使得Sij大而(fri-frj)小，因而式(2)趨小?！苅(fri-ur)2Dii越大表示該特征在各樣本上的取值方差越大，一個區分能力強的特征應該會賦予同類樣本近似的值而不同類樣本差異大的值，即具有較大方差的特征具有較強的識別能力。因此式(2)通過譜圖理論結合特征的局部信息保持能力和方差來進行特征選擇。

2 基于特征相關的譜特征選擇模型

傳統的譜特征選擇算法采用單獨最優特征組合的啟發式搜索策略，用式(2)對每個特征單獨度量其重要度，該策略并未考慮特征間的冗余度和交互性，因此需要考慮候選特征與已選特征之間的冗余性和交互性。本文在式(2)的基礎上定義了特征組的重要度公式如式(3)。為了度量每個候選特征對已選特征的貢獻程度，同時定義了式(4)來計算候選特征的重要度。模型思想是：首先利用傳統譜特征選擇算法選出使目標函數式(2)最好的一個特征，然后以這個特征為核心據點作為已選特征，依次逐個評價候選特征與已選特征的相關性，即依次根據目標函數(式(3))評價特征組合后的圖的保持能力，然后根據式(4)選出保持能力優于未組合時的最強一個特征，并將該特征加入到已選特征中形成新的組合，接著對余下候選特征進行下一輪的迭代。該算法不僅考慮了特征間的相關效應，而且通過式(4)避免了特征間的冗余。

定義特征組相關的目標函數為

在式(3)的基礎上通過式(4)評估候選特征中能提升已有特征子集的區分能力的特征，其目標函數定義為

式中：FU表示候選特征集合，fi∈FU，通過評估一個新的特征fi能否使得同類樣本距離小而不同類樣本距離大來衡量是否加入已選Fs。又在候選特征集合里可能有多個fi能提升已選子集的能力，由式(3)知新加入的fi使得φFS越小越好，因此在多個具有提升子集能力的候選特征中選擇使φFS∪fi-φFS最小的一個特征。

根據式(4)，可提出基于特征相關的譜特征選擇算法(SPFC)的偽代碼如算法1所示。

算法1 基于特征相關的譜特征選擇算法(SPFC)

輸入樣本集X，類標記Y；

輸出FS特征相關后的特征序列。

1)FS=?，FU=F1F2…Fn；

2)依據X、Y計算每兩個樣本間的相似度矩陣Sij(1≤i,j≤m);

3)依據相似度構建Laplacian圖G，并計算W、D、L;

4)根據傳統譜特征選擇算法求出最具有識別力的一個特征fi

FS=FS∪fi，FU=FU-{fi};

5)whileFU不為空

6)根據式(3)計算φFS;

7) fori=1 to length(FU)

ifφFS∪fi-φFS>0 then

L(j)=φFS∪fi-φFS;

j=j+1;

end if

8)end for

9)將L按升序排序

FS=FS∪fL(1)，FU=FU-{fL(1)};

10)end while

3 實驗設計與對比

3.1 實驗數據

為了進一步驗證SPFC算法的有效性，本文從UCI (http://www.ics.uci.edu)中選擇8個數據集，各數據集相應的描述信息見表1,在表1～3中australian_credit數據集簡寫為AC，VeteranLungCancer數據集簡寫為VE。

表1 實驗數據描述

3.2 實驗結果與分析

為了驗證SPFC算法的性能，實驗分為兩部分。第1組實驗與CFS[14]、ChiSquare[15]、FCBF[16]、Laplacian[10]、NRS[17]以及Relief[18]算法進行比較由特征子集誘導出來的分類精度。另一組實驗采用Friedman test[19]和Bonferroni-Dunn test[20]在統計上對比SPFC與其他算法在8個數據集上的實驗結果。由于ChiSquare、Laplacian、FCFS、Relief這4種算法得到的是一個特征序列，而CFS、FCBF、NRS 3種算法得到的是子集約簡，因此，ChiSquare、Fisher、FCFS、Relief這4種算法得到的特征序列取前k個特征作特征子集，其中k為 CFS、FCBF、NRS算法中得到的3個約簡子集數量的最小值。此外，NRS算法中的鄰域參數值δ為0.10。在實驗中，采用十折交叉驗證法進行評價特征子集的優劣，用KNN(K=10)、CART 2個不同的基分類器來評價分類精度。

實驗1 為了比較特征選擇后的分類精度，在表2～4中，分別采用KNN(K=10)、CART 這2個不同的基分類器進行特征子集分類精度的評價。此外，為了更加直觀地比較不同方法得到的特征子集的性能，表2、3中加粗的數值表示最高分類進度，下劃線表示精度次優，最后一行表示不同算法得到的特征子集的平均分類精度，最后一行中加下劃線的數值表示平均分類精度最高的值。另外，括號里面的數值表示數據的標準差，括號外面的數值表示分類精度。

表2 不同特征選擇算法在KNN分類器下的分類精度比較

表 3 不同特征選擇算法在CART分類器下的分類精度比較

結合表2、3的實驗結果可知：

1)從總體上看，SPFC算法相比CFS、ChiSquare、FCBF、Laplacian、NRS以及Relief算法在KNN、CART基分類器下表現穩定，且均獲得最高平均分類精度。相比考慮類信息的傳統譜特征選擇算法Laplacian, SPFC算法優于Laplacian。

2)相比ChiSquare、Laplacian、Relief這3種同樣獲得特征系列的算法，SPFC算法以相同的前k個特征在不同的基分類器下獲得的平均分精度明顯較高，相比子集約簡的算法CFS、FCBF、NRS，SPFC取它們子集約簡數量的最小值在兩個基分類器下分類精度明顯要高于NRS，在CART基分類器下SPFC的分類精度高于CFS、FCBF達兩個百分點以上，而在KNN基分類器下也顯著高于CFS、FCBF。

3)每一種算法均會在某一個分類器上某個數據集上獲得最高分類精度，但只有SPFC能在兩個基分類器上多個數據集上獲得最高分類精度。SPFC算法在數據集ICU、rice、zoo上性能提升更為明顯，在兩個分類器上均達到最高。而ICU為混合型數據，rice為連續型數據、zoo為離散型數據。說明SPFC可以處理多類型數據集，在大部分各類型數據集上SPFC均能達到較好的穩定表現。

實驗2 為了進一步研究比較SPFC算法與其他算法在兩個分類器下的分類性能是否明顯不同，我們采用Friedman test 和Bonferroni-Dunn在統計上進行驗證。 Friedman 統計值定義為

式中：k代表對比算法個數，N表示數據集個數，Ri表示第i個算法在8個數據集上的排序均值(見表4)。由表4結合式(5)算出KNN分類器下FF的值為2.18，cart分類器下FF的值為3.05，又當顯著性水平a=0.1時F(6,42)=1.87，因此在兩個分類器下都拒絕了零假設(所有算法性能相等)，這時還需要結合特定的post-hoc test來進一步分析各個算法性能的差異。本文采用顯著性水平為0.1的Bonferroni-Dunn test。在這里定義兩個算法的不同用下面的臨界差：

在Bonferroni-Dunn test里顯著性水平為0.1且7個算法對比時qα=2.394，因此CD=2.58(k=7,N=8)。如果兩個算法在所有數據集上的平均排序的差不低于臨界差CD，則認為它們有顯著性差異。圖2給出了在兩個分類器下SPFC算法與其他算法的比較，其中，每個子圖中最上行為臨界值，坐標軸畫出了各種算法的平均排序且最左(右)邊的平均排序最高(低)。用一根加粗的線連接性能沒有顯著差異的算法組。

從圖2可以直觀看出在KNN分類器下，SPEC算法顯著優于Relief算法，雖然與其他算法沒有顯著差別，但可以看出SPFC算法性能要高于其他算法；在CART分類器下SPFC算法性能顯著優于算法NRS、ChiSquare、Relief，而與算法Laplacain、CFS、FCBF性能相當，但性能相當的同一組里SPFC算法要遠遠優于算法Laplacain、CFS、FCBF。

表4 不同算法在兩個分類器下的排序均值表

(a) KNN分類器

(b) CART分類器 圖2 在KNN和CART分類器下SPEC與其他算法的比較Fig.2 SPEC compared with other algorithms Under the CART and KNN classifier

4 結論

本文針對傳統的譜特征選擇只考慮特征的單獨最優組合問題進行改進，提出基于譜圖理論的特征相關的特征選擇算法，本文研究發現：1)引入特征之間的統計相關性到譜特征選擇中，能有效地解決有用特征可能是冗余的問題；2)在公開的UCI數據集上的實驗結果表明,本文算法能夠選擇較少的特征，獲得較好的分類精度；3)由表2～4中的數據亦看出考慮特征間的相關性算法(SPEC)比不考慮特征間相關性算法(Laplacian)能顯著提高特征子集的分類性能。但由于本文實驗采用歐式距離統計特征間的相關性，而歐式距離對于高維特征的計算差值變化不大，因此對于高維特征間的相關性的設計有待進一步研究。

[1]LIN Yaojin, Li Jinjin, LIN Peirong, et al. Feature selection via neighborhood multi-granulation fusion[J]. Knowledge-based systems, 2014, 67： 162-168.

[2] MANORANJAN D, LIU Huan. Consistency-based search in feature selection[J]. Artificial intelligence, 2003,151(1): 155-176.

[3] ZHANG C, ARUN K, CHRISTOPHER R. Materialization optimizations for feature selection workloads[J]. ACM transactions on database systems, 2016, 41(1): 2.

[4]曹晉, 張莉, 李凡長. 一種基于支持向量數據描述的特征選擇算法[J]. 智能系統學報, 2015, 10(2): 215-220.

CAO Jin , ZHANG li, LI Fanchang . A feature selection algorithm based on support vector data description[J]. CAAI transactions on intelligent systems, 2015, 10(2): 215-220 .

[5]MANORANJAN D, LIU Huan. Feature selection for classification[J]. Intelligent data analysis, 1997, 1(3): 131-156.

[6]SUN Yujing, WANG Fei, WANG Bo, et al. Correlation feature selection and mutual information theory based quantitative research on meteorological impact factors of module temperature for solar photovoltaic systems[J]. Energies, 2016, 10(1): 7.

[7]CVETKOVIC D M, ROWLINSON P. Spectral graph theory[J]. Topics in algebraic graph theory, 2004: 88-112.

[8]ZHAO Zheng, LIU Huan. Spectral feature selection for supervised and unsupervised learning[C]//Proceedings of the 24th international conference on Machine learning. ACM, 2007: 1151-1157.

[9]ZHAO Zhou, HE Xiaofei, CAI Deng, et al. Graph regularized feature selection with data reconstruction[J]. IEEE transactions on knowledge and data engineering, 2016, 28(3): 689-700.

[10]HE Xiaofei, CAI Deng, NIYONGI P. Laplacian score for feature selection[M].Cambridge： MIT Press, MA, 2005, 17: 507-514.

[11]BELABBAS M A, WOLFE P J. Spectral method in machine learning and new strategies for very large datasets[J]. Proceedings of the national academy of sciences, 2009, 106(2): 369-374.

[12]WANG Xiaodong, ZHANG Xu, ZENG Zhiqiang, et al. Unsupervised spectral feature selection with l 1-norm graph[J]. Neurocomputing, 2016, 200: 47-54.

[13]邊肇祺,張學工.模式識別[M]. 2版. 北京: 清華大學出版社, 2000.

[14]HALL M A. Correlation-based feature selection for discrete and numeric class machine learning[C]//the 17thInternational Conference on Machine Learning. San Francisco: Morgan Kaufmann, 2000: 359-366.

[15]ANDREAS W, ANDREAS P. Attacks on stegan ographic systems[M]. Heidelberg, Berlin: Springer-Verlag, 2000: 61-76.

[16]YU Lei, LIU Huan. Efficient feature selection via analysis of relevance and redundancy[J]. Journal of machine learning research, 2004, 5(1): 1205-1224.

[17]HU Qinghua, YU Daren, LIU Jinfu, et al. Neighborhood rough set based heterogeneous feature subset selection[J]. Information sciences, 2008, 178 (18): 3577-3594.

[18]CRAMMER K, GILAD-BACHRACH R, NAVOT A. Margin analysis of the lvq algorithm[C]//Advances in Neural Information Processing Systems. 2002, 14: 462-469.

[19]FRIEDMAN M, A comparison of alternative tests of significance for the problem of m rankings[J]. The annals of mathematical statistics, 1940, 11(1): 86-92.

[20]DUNN O J.Multiple comparisons among means[J]. Journal of the american statistical association, 1961, 56(293): 52-64.

2017WorkshoponSARinBigDataEra:Models,MethodsandApplications

During the last decade a series of SAR satellites has been launched, including Chinese Gaofen-3, providing great amount of SAR data with varied modes to meet the varieties of applications. It becomes a challenge to retrieve information from these big data. The main objective of this workshop is to share models, methods and applications of SAR data exploration in the big data era.

The workshop includes different subjects, such as big SAR data modeling, large-scale intelligent SAR processing, SAR applications in big data frameworks. It will feature keynote presentations by distinguished researchers on this topics, most of them are IEEE GRSS members.

Website：http://www.radi.ac.cn/BIGSARDATA2017/

Spectralfeatureselectionbasedonfeaturecorrelation

HU Minjie, LIN Yaojin, YANG Honghe, ZHENG Liping, FU Wei

(School of Computer Science, Minnan Normal University, Zhangzhou 363000, China)

In the traditional spectrum feature selection algorithm, only the importance of single features are considered. In this paper, we introduce the statistical correlation between features into traditional spectrum analysis and construct a spectral feature selection model based on feature correlation. First, the proposed model utilizes the Laplacian Score to identify the most central feature as the selected feature, then designs a new feature group discernibility objective function, and applies the forward greedy search strategy to sequentially evaluate the candidate features. Then, the candidate feature with the minimum objective function is added to the selected features. The algorithm considers both the importance of feature as well as the correlations between features. We conducted experiments on two different classifiers and eight UCI datasets, the results of which show that the algorithm effectively improves the classification performance of the feature subset and also obtains a small number of feature subsets with high classification precision.

feature selection; spectral feature selection; spectral graph theory; feature relevance; discernibility; search strategy; Laplacian score;classification performance

2016-09-08.網絡出版日期2017-04-07.

國家自然科學基金項目(61303131,61379021);福建省高校新世紀優秀人才支持計劃;福建省教育廳科技項目(JA14192)

胡敏杰.E-mail:zzhuminjie@sina.com.

10.11992/tis.201609008

http://kns.cnki.net/kcms/detail/23.1538.tp.20170407.1758.016.html

TP18

A

1673-4785(2017)04-0519-07

中文引用格式：胡敏杰，林耀進，楊紅和,等.基于特征相關的譜特征選擇算法J.智能系統學報， 2017, 12(4): 519-525.

英文引用格式：HUMinjie,LINYaojin,YANGHonghe,etal.SpectralfeatureselectionbasedonfeaturecorrelationJ.CAAItransactionsonintelligentsystems, 2017, 12(4): 519-525.

胡敏杰，女，1979年生，講師，主要研究方向為數據挖掘。

林耀進，男,1980年生,主要研究方向為數據挖掘、粒計算。主持國家自然科學基金2項。發表學術論文60余篇。

楊紅和，男，1969生，高級實驗師，主要研究方向為數字校園。