特征選擇方法中三種度量的比較研究

宋智超　康健　孫廣路　何勇軍

摘要：不同類型數據中特征與類別以及特征與特征之間存在一定的線性和非線性相關性。針對基于不同度量的特征選擇方法在不同類型數據集上選取的特征存在明顯差別的問題，本文選擇線性相關系數、對稱不確定性和互信息三種常用的線性或非線性度量，將它們應用于基于相關性的快速特征選擇方法中，對它們在基因微陣列和圖像數據上的特征選擇效果進行實驗驗證和比較。實驗結果表明，基于相關性的快速特征選擇方法使用線性相關系數在基因數據集上選取的特征集往往具有較好分類準確率，使用互信息在圖像數據集上選取的特征集的分類效果較好，使用對稱不確定性在兩種類型數據上選取特征的分類效果較為穩定。

關鍵詞：特征選擇；線性相關系數；對稱不確定性；互信息；基于相關性的快速特征選擇方法

DOI：10.15938/j.jhust.2018.01.020

中圖分類號： TM391.1

文獻標志碼： A

文章編號： 1007-2683（2018）01-0111-06

Abstract：It has been known that either linear correlation or nonlinear correlation might exist between featuretofeature and featuretoclass in datasets. In this paper， we study the differences of selected feature subset when different kinds of measures are applied with same feature selection method in different kinds of datasets. Three representative linear or nonlinear measures， linear correlation coefficient， symmetrical uncertainty， and mutual information are selected. By combining them with the fast correlationbased filter （FCBF） feature selection method， we make the comparison of selected feature subset from 8 gene microarray and image datasets. Experimental results indicate that the feature subsets selected by linear correlation coefficient based FCBF obtain better classification accuracy in gene microarray datasets than in image datasets， while mutual information and symmetrical uncertainty based FCBF tend to obtain better results in image datasets. Moreover， symmetrical uncertainty based FCBF is more robust in all datasets.

Keywords：feature selection；linear correlation coefficient；symmetrical uncertainty；mutual Information；fast correlationbased filter

0引言

數據挖掘方法能夠從數據中獲取到潛在的有效信息，在金融預測、模式識別等多個領域得到了廣泛應用。隨著互聯網和生物信息學技術的不斷進步，數據朝著更大規模的方向發展，并帶來了“維度災難”等問題[1]。解決上述問題的有效方法之一是降低數據集中特征的維數。特征選擇作為數據挖掘和機器學習中的重要研究內容，其通過刪除數據集中的無關和冗余特征，達到有效的降低特征維數，提高分類的準確率和效率的目的，并且具有去噪、防止機器學習模型過擬合的作用[2]。

現有的特征選擇方法主要可以分為過濾方法、封裝方法和嵌入方法[3]。封裝方法使用預先選定的機器學習方法作為評價特征集優劣的準則，存在時間復雜度高的問題。嵌入方法則將特征選擇和機器學習算法的訓練過程相結合。過濾方法不依賴特定的機器學習方法，具有運行效率高的特點，適用于解決高維數據中的特征選擇問題。本文主要針對過濾方法進行研究。

搜索策略和度量的選取是過濾方法的兩個重要研究內容。學者們提出了基于一致性、基于距離、基于信息論等多種度量，并據此提出了多種評價函數[4-6]。當前研究者們重點關注特征選擇方法的設計，實驗常用數據集主要有基因生物數據、圖像數據和文本數據等[7]。據作者調研，目前尚無針對不同度量在不同類型數據上可能存在的效果差異性的研究。本文選取常用的三種度量——線性相關系數、對稱不確定性和互信息，并結合經典的特征選擇方法，對這3種度量應用到不同類型數據集上的效果進行研究。

基于相關性的快速特征選擇方法是一種經典的特征選擇方法，其在多種數據集上都具有較好的效果，并且對于高維數據具有較快的運行效率。本文將上述不同的度量應用于基于相關性的快速特征選擇方法中，通過實驗驗證對不同度量在基因生物數據和圖像數據上效果的差異，并對度量和數據類型之間的關系進行研究。

本文第二節為相關工作，對目前影響較大的特征選擇方法和度量的應用進行介紹；第三節描述特征選擇中的3種度量和基于相關性的快速特征選擇方法；第四節是實驗數據集和實驗結果，第五節為總結。

1相關工作

變量間的相關關系在機器學習和模式識別領域得到了廣泛的研究。研究者們提出了多種度量對變量間的相關性進行挖掘，目前而言，變量之間的相關關系主要分為線性相關和非線性相關兩類。早期的特征選擇方法一般應用馬氏距離、相關系數等線性度量[8]。文[9]使用相關系數、Wilcoxon秩和檢驗兩種度量對基因數據中的特征關系進行挖掘。文[10]提出了最小乘方錯誤和最大信息壓縮指數兩種線性度量并應用于無監督的特征選擇方法中，取得了較好的效果。然而，現實世界中的數據并不總是滿足線性關系，對數據間線性關系的假設并不完備[11]。針對這種情況，學者們提出了多種非線性相關的度量，其中基于信息論的度量被認為是最有前景的度量，信息增益[12]、互信息[13]、歸一化互信息[14]和條件互信息[15]等被應用到特征選擇中，取得了不錯的效果。

基于上述度量可以構建特征選擇方法進行最優特征子集的選取。早期的特征選擇方法只考慮特征與類別之間的相關性，如信息增益、Relief[16]和ReliefF[17]等。隨著特征維數的增加，該類方法的時間復雜度呈線性增長并且能夠適用于高維數據的特征選擇。但是由于沒有考慮冗余特征的影響，該類方法選取特征子集的分類效果往往不理想。

冗余特征的存在不僅增加了機器學習模型的時間復雜度，而且對最后的分類任務有干擾作用，也應該被去除。基于相關性的特征選擇[18]、最小冗余最大相關[19]等方法可以對冗余特征進行處理，然而其使用的貪心序列搜索、最優搜索等搜索策略的時間復雜度為O（n2），使得這些方法很難應用到高維數據的特征選擇中。

針對上述問題，馬爾科夫毯首次被Koller等人應用到特征選擇中，取得了很好的效果[20]。隨后的學者們對馬爾科夫毯方法進行了廣泛的研究[7，11，21]。其中，論文[11]提出一種基于相關性的快速特征選擇方法，并對特征選擇中的基本問題進行了定義。后續研究者在此基礎上進行改進并應用到不同的特征選擇任務中[7，22]。從算法效率和選取的特征子集的分類效果兩方面來看，基于相關性的快速特征選擇方法具有一定的優勢。

2特征選擇中的度量和方法

3實驗結果與分析

3.1實驗設置

為了驗證本文提出的3種度量在基因和圖像數據上選取特征的分類效果是否存在差異，選取8個數據集進行實驗研究。由于對選取的數據集無法事先得知最優特征子集，同時為了增強實驗的說服性、避免實驗結果的偏置，在不同數據集上應用本文提出的3種特征選擇方法FSCC、FSSU和FSMI分別選取10，20，30，40維特征，對3種不同特征選擇方法選取特征差異性進行比較。由于對數據集我們沒有先驗知識，當前特征選擇工作一般使用分類器的準確率對最終選取的特征集優劣進行評價。本文使用常用的樸素貝葉斯（Nave Bayes， NB）和支持向量機（Support Vector Machine， SVM）分類器，統一使用10fold交叉驗證得到3種特征選擇方法選取不同維數特征的分類準確率。

實驗中將數據隨機均等分成2份，1份為訓練集，1份為測試集，使用本文提出的3種特征選方法從訓練集中選取預先設定維數的特征，然后根據選取的特征子集重新構造測試集，并應用NB和SVM分類器，采用10折交叉驗證得到不同特征選擇方法選取的特征集在測試集上的分類準確率。為了使得最后的實驗結果更具統計意義，重復上述實驗過程10次，并對10次實驗的結果取平均值得到最終的分類準確率。

3.2數據集

實驗中使用基因和圖像兩類數據集，對3種度量的效果進行實驗分析。每類數據選取四個不同的數據集，有二分類也有多分類數據集，特征維數從280維到19993維，具體數據信息如表1所示。

3.3實驗處理和結果

本文算法1為兩階段特征選擇方法，算法第一階段通過對FSCC、FSSU和FSMI3種方法設定不同的閾值θ，選取預期維數的特征。表2為3種特征選擇方法分別選取不同維數特征在NB分類器上的實驗結果。表3為3種特征選擇方法選取的特征在SVM分類器上的實驗結果。

圖1和圖2為3種特征選擇方法選取不同維數特征在NB和SVM兩個分類器上的準確率均值。從表2和圖1中實驗結果來看，FSCC在SMKCAN、TOX171和Leukemia 3個基因類型數據集上的分類準確率最高，而在四個圖像類型數據上的分類準確率較FSSU和FSMI方法有明顯的差距。在Arrhythmia數據集上與FSMI分類準確率相近。FSMI在4個圖像數據上的分類效果最好，但在四個基因類型的數據集上的分類效果較差。FSSU在Arrhythmia數據上的分類效果最好，在TOX171數據集上的分類準確率最差，在其余的六個數據集上的效果與分類效果最好的方法效果相近。因此，從最終的分類結果來看，FSMI效果最好，并且其更適合處理圖像類型數據。而FSCC更適合處理基因數據，并且FSCC在圖像數據上的分類效果明顯差于FSMI和FSSU方法。盡管FSSU方法只在Arrhythmia數據上的分類準確率最高，但是從所有八個數據集上的分類準確率來看，FSSU選取的特征在不同數據集上的分類效果更加穩定。

圖2和表3中在SVM分類器上的實驗結果與圖1和表2中實驗結果類似，FSCC方法仍然在SMKCAN、TOX171和Leukemia 3個基因數據上的分類準確率最高，FSSU在Arrhythmia、PIE10P和PIX10P 3個數據集上的效果最好，FSMI在其他兩個圖像數據上的效果最好。

由上述實驗結果可得，線性相關系數適合基因類型數據的特征選擇工作，而在圖像類型數據上選取特征的分類準確率較差。互信息和對稱不確定性更適合處理圖像類型的數據，對稱不確定性在兩種類型的數據上選取特征的分類效果較為穩定。

4結語

本文選取基因和圖像兩種特征選擇常用類型數據集，對特征選擇常用的3種度量——線性相關系數、對稱不確定性和互信息在不同數據集上的效果進行研究。為了加快特征選擇的效率，同時保證選取特征的分類效果，將3種度量應用到基于相關性的快速特征選擇方法中，并提出FSCC、FSSU和FSMI 3種不同的特征選擇方法。使用樸素貝葉斯和SVM兩種分類器評價3種不同特征選擇方法選取的特征。在選取的8個數據集上的實驗表明，線性相關系數更適合于處理基因類型數據，選擇的特征能夠取得較好的分類效果，而在圖像數據集上的效果較差；互信息在圖像類型數據上的效果較在基因類型數據上更為突出。對稱不確定性在兩種類型的數據上的效果較為穩定，且效果較好。

參 考 文 獻：

[1]CHANDRASHEKAR G， SAHIN F. A Survey on Feature Selection Methods[J]. Computers & Electrical Engineering， 2014， 40（1）： 16-28.

[2]DESSI N， PES B. Similarity of Feature Selection Methods： An Empirical Study Across Data Intensive Classification Tasks[J]. Expert Systems with Applications， 2015， 42（10）： 4632-4642.

[3]ZHAO Z， LIU H. Searching for Interacting Features[C]// Proceedings of the 20th International Joint Conference on Artificial Intelligence. Hyderabad， India， 2007：1156-1161.

[4]DASH M， LIU H，MOTODA H. Consistency Based Feature Selection[C]// PacificAsia Conference on Knowledge Discovery and Data Mining， Current Issues and New Applications. SpringerVerlag， 2000：98-109.

[5]ZHANG J G， DENG H W. Gene Selection for Classification of Microarray Data Based on the Bayes Error[J]. BMC bioinformatics， 2007， 8（1）： 370.

[6]SOTOCA J M， PLA F. Supervised Feature Selection by Clustering Using Conditional Mutual Informationbased Distances[J]. Pattern Recognition， 2010， 43（6）： 2068-2081.

[7]SONG Q， NI J， WANG G. A Fast Clusteringbased Feature Subset Selection Algorithm for Highdimensional Data[J].IEEE Transactions on Knowledge and Data Engineering， 2013， 25（1）： 1-14.

[8]GUYON I， ELISSEEFF A. An Introduction to Variable and Feature Selection[J]. The Journal of Machine Learning Research， 2003， 3： 1157-1182.

[9]謝娟英， 高紅超. 基于統計相關性與 Kmeans 的區分基因子集選擇算法[J]. 軟件學報， 2014， 25（9）： 2050-2075.

[10]MITRA P， MURTHY C A， PAL S K. Unsupervised Feature Selection Using Feature Similarity[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24（3）： 301-312.

[11]YU L， LIU H. Efficient Feature Selection Via Analysis of Relevance and Redundancy[J]. The Journal of Machine Learning Research， 2004（5）： 1205-1224.

[12]PEREIRA R B， PLASTINO A， ZADROZNY B， et al. Information Gain Feature Selection for MultiLabel Classification[J]. Journal of Information and Data Management， 2015， 6（1）： 48.

[13]HOQUE N， BHATTACHARYYA D K， KALITA J K. MIFSND： A Mutual Informationbased Feature Selection Method[J]. Expert Systems with Applications， 2014， 41（14）： 6371-6385.

[14]LEE S， PARK Y T，dAuriol B J. A Novel Feature Selection Method Based on Normalized Mutual Information[J]. Applied Intelligence， 2012， 37（1）： 100-120.

[15]FLEURET F. Fast Binary Feature Selection with Conditional Mutual Information[J]. The Journal of Machine Learning Research， 2004， 5： 1531-1555.

[16]KIRA K， RENDELL L A. The Feature Selection Problem： Traditional Methods and a New Algorithm[C]// Tenth National Conference on Artificial Intelligence. AAAI Press， 1992：129-134.

[17]KONONENKO I. Estimating Attributes： Analysis and Extensions of RELIEF[C]// European Conference on Machine Learning on Machine Learning. SpringerVerlag New York， Inc.， 1994：356-361.

[18]HALL M A. Correlationbased Feature Selection for Discrete and Numeric Class Machine Learning[C]// Seventeenth International Conference on Machine Learning. Morgan Kaufmann， 2000：359-366.

[19]DING C， PENG H. Minimum Redundancy Feature Selection from Microarray Gene Expression Data[J]. Journal of bioinformatics and computational biology， 2005， 3（2）： 185-205.

[20]KOLLER D. Toward Optimal Feature Selection[C]// Proceedings of 13th International Conference on Machine Learning. Morgan Kaufmann， 2000：284-292.

[21]崔自峰， 徐寶文， 張衛豐，等. 一種近似Markov Blanket最優特征選擇算法[J]. 計算機學報， 2007， 30（12）：2074-2081.

[22]W Xindong， Y Kui， D Wei， et al. Online Feature Selection with Streaming Features[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2013， 35（5）：1178-1192.

（編輯：關毅）