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

宋智超　康健　孫廣路　何勇軍

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

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

DOI：10.15938/j.jhust.2018.01.020

中圖分類號： TM391.1

文獻(xiàn)標(biāo)志碼： 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引言

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

現(xiàn)有的特征選擇方法主要可以分為過濾方法、封裝方法和嵌入方法[3]。封裝方法使用預(yù)先選定的機(jī)器學(xué)習(xí)方法作為評價(jià)特征集優(yōu)劣的準(zhǔn)則，存在時(shí)間復(fù)雜度高的問題。嵌入方法則將特征選擇和機(jī)器學(xué)習(xí)算法的訓(xùn)練過程相結(jié)合。過濾方法不依賴特定的機(jī)器學(xué)習(xí)方法，具有運(yùn)行效率高的特點(diǎn)，適用于解決高維數(shù)據(jù)中的特征選擇問題。本文主要針對過濾方法進(jìn)行研究。

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

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

本文第二節(jié)為相關(guān)工作，對目前影響較大的特征選擇方法和度量的應(yīng)用進(jìn)行介紹；第三節(jié)描述特征選擇中的3種度量和基于相關(guān)性的快速特征選擇方法；第四節(jié)是實(shí)驗(yàn)數(shù)據(jù)集和實(shí)驗(yàn)結(jié)果，第五節(jié)為總結(jié)。

1相關(guān)工作

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

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

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

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

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

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

3.1實(shí)驗(yàn)設(shè)置

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

實(shí)驗(yàn)中將數(shù)據(jù)隨機(jī)均等分成2份，1份為訓(xùn)練集，1份為測試集，使用本文提出的3種特征選方法從訓(xùn)練集中選取預(yù)先設(shè)定維數(shù)的特征，然后根據(jù)選取的特征子集重新構(gòu)造測試集，并應(yīng)用NB和SVM分類器，采用10折交叉驗(yàn)證得到不同特征選擇方法選取的特征集在測試集上的分類準(zhǔn)確率。為了使得最后的實(shí)驗(yàn)結(jié)果更具統(tǒng)計(jì)意義，重復(fù)上述實(shí)驗(yàn)過程10次，并對10次實(shí)驗(yàn)的結(jié)果取平均值得到最終的分類準(zhǔn)確率。

3.2數(shù)據(jù)集

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

3.3實(shí)驗(yàn)處理和結(jié)果

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

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

圖2和表3中在SVM分類器上的實(shí)驗(yàn)結(jié)果與圖1和表2中實(shí)驗(yàn)結(jié)果類似，F(xiàn)SCC方法仍然在SMKCAN、TOX171和Leukemia 3個基因數(shù)據(jù)上的分類準(zhǔn)確率最高，F(xiàn)SSU在Arrhythmia、PIE10P和PIX10P 3個數(shù)據(jù)集上的效果最好，F(xiàn)SMI在其他兩個圖像數(shù)據(jù)上的效果最好。

由上述實(shí)驗(yàn)結(jié)果可得，線性相關(guān)系數(shù)適合基因類型數(shù)據(jù)的特征選擇工作，而在圖像類型數(shù)據(jù)上選取特征的分類準(zhǔn)確率較差。互信息和對稱不確定性更適合處理圖像類型的數(shù)據(jù)，對稱不確定性在兩種類型的數(shù)據(jù)上選取特征的分類效果較為穩(wěn)定。

4結(jié)語

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

參 考 文 獻(xiàn)：

[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]謝娟英， 高紅超. 基于統(tǒng)計(jì)相關(guān)性與 Kmeans 的區(qū)分基因子集選擇算法[J]. 軟件學(xué)報(bào)， 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]崔自峰， 徐寶文， 張衛(wèi)豐，等. 一種近似Markov Blanket最優(yōu)特征選擇算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 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.

（編輯：關(guān)毅）