宋智超　康健　孫廣路　何勇軍

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

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

DOI：10.15938/j.jhust.2018.01.020

中圖分類號(hào)： TM391.1

文獻(xiàn)標(biāo)志碼： A

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

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

搜索策略和度量的選取是過(guò)濾方法的兩個(gè)重要研究?jī)?nèi)容。學(xué)者們提出了基于一致性、基于距離、基于信息論等多種度量，并據(jù)此提出了多種評(píng)價(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)研，目前尚無(wú)針對(duì)不同度量在不同類型數(shù)據(jù)上可能存在的效果差異性的研究。本文選取常用的三種度量——線性相關(guān)系數(shù)、對(duì)稱不確定性和互信息，并結(jié)合經(jīng)典的特征選擇方法，對(duì)這3種度量應(yīng)用到不同類型數(shù)據(jù)集上的效果進(jìn)行研究。

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

本文第二節(jié)為相關(guān)工作，對(duì)目前影響較大的特征選擇方法和度量的應(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í)和模式識(shí)別領(lǐng)域得到了廣泛的研究。研究者們提出了多種度量對(duì)變量間的相關(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)兩種度量對(duì)基因數(shù)據(jù)中的特征關(guān)系進(jìn)行挖掘。文[10]提出了最小乘方錯(cuò)誤和最大信息壓縮指數(shù)兩種線性度量并應(yīng)用于無(wú)監(jiān)督的特征選擇方法中，取得了較好的效果。然而，現(xiàn)實(shí)世界中的數(shù)據(jù)并不總是滿足線性關(guān)系，對(duì)數(shù)據(jù)間線性關(guān)系的假設(shè)并不完備[11]。針對(duì)這種情況，學(xué)者們提出了多種非線性相關(guān)的度量，其中基于信息論的度量被認(rèn)為是最有前景的度量，信息增益[12]、互信息[13]、歸一化互信息[14]和條件互信息[15]等被應(yīng)用到特征選擇中，取得了不錯(cuò)的效果。

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

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

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

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

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

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

為了驗(yàn)證本文提出的3種度量在基因和圖像數(shù)據(jù)上選取特征的分類效果是否存在差異，選取8個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)研究。由于對(duì)選取的數(shù)據(jù)集無(wú)法事先得知最優(yōu)特征子集，同時(shí)為了增強(qiáng)實(shí)驗(yàn)的說(shuō)服性、避免實(shí)驗(yàn)結(jié)果的偏置，在不同數(shù)據(jù)集上應(yīng)用本文提出的3種特征選擇方法FSCC、FSSU和FSMI分別選取10，20，30，40維特征，對(duì)3種不同特征選擇方法選取特征差異性進(jìn)行比較。由于對(duì)數(shù)據(jù)集我們沒(méi)有先驗(yàn)知識(shí)，當(dāng)前特征選擇工作一般使用分類器的準(zhǔn)確率對(duì)最終選取的特征集優(yōu)劣進(jìn)行評(píng)價(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份為測(cè)試集，使用本文提出的3種特征選方法從訓(xùn)練集中選取預(yù)先設(shè)定維數(shù)的特征，然后根據(jù)選取的特征子集重新構(gòu)造測(cè)試集，并應(yīng)用NB和SVM分類器，采用10折交叉驗(yàn)證得到不同特征選擇方法選取的特征集在測(cè)試集上的分類準(zhǔn)確率。為了使得最后的實(shí)驗(yàn)結(jié)果更具統(tǒng)計(jì)意義，重復(fù)上述實(shí)驗(yàn)過(guò)程10次，并對(duì)10次實(shí)驗(yàn)的結(jié)果取平均值得到最終的分類準(zhǔn)確率。

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

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

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

本文算法1為兩階段特征選擇方法，算法第一階段通過(guò)對(duì)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兩個(gè)分類器上的準(zhǔn)確率均值。從表2和圖1中實(shí)驗(yàn)結(jié)果來(lái)看，F(xiàn)SCC在SMKCAN、TOX171和Leukemia 3個(gè)基因類型數(shù)據(jù)集上的分類準(zhǔn)確率最高，而在四個(gè)圖像類型數(shù)據(jù)上的分類準(zhǔn)確率較FSSU和FSMI方法有明顯的差距。在Arrhythmia數(shù)據(jù)集上與FSMI分類準(zhǔn)確率相近。FSMI在4個(gè)圖像數(shù)據(jù)上的分類效果最好，但在四個(gè)基因類型的數(shù)據(jù)集上的分類效果較差。FSSU在Arrhythmia數(shù)據(jù)上的分類效果最好，在TOX171數(shù)據(jù)集上的分類準(zhǔn)確率最差，在其余的六個(gè)數(shù)據(jù)集上的效果與分類效果最好的方法效果相近。因此，從最終的分類結(jié)果來(lái)看，F(xiàn)SMI效果最好，并且其更適合處理圖像類型數(shù)據(jù)。而FSCC更適合處理基因數(shù)據(jù)，并且FSCC在圖像數(shù)據(jù)上的分類效果明顯差于FSMI和FSSU方法。盡管FSSU方法只在Arrhythmia數(shù)據(jù)上的分類準(zhǔn)確率最高，但是從所有八個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率來(lái)看，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個(gè)基因數(shù)據(jù)上的分類準(zhǔn)確率最高，F(xiàn)SSU在Arrhythmia、PIE10P和PIX10P 3個(gè)數(shù)據(jù)集上的效果最好，F(xiàn)SMI在其他兩個(gè)圖像數(shù)據(jù)上的效果最好。

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

4結(jié)語(yǔ)

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