基于最大信息系數的ReliefF和支持向量機交互的自動特征選擇算法

葛倩，張光斌，張小鳳

（陜西師范大學 物理學與信息技術學院，西安 710119）

0 引言

在不同領域的數據挖掘過程中，產生了包含眾多特征的高維數據集，其中，冗余特征和不相關特征的存在不但會增加數據處理過程的復雜度，還在一定程度上降低了后續分類算法的準確率［1］。因此，對高維數據集進行預處理，減少冗余特征和不相關特征成為數據挖掘的重要研究內容。

作為數據降維的一種有效方式，特征選擇算法不僅可以篩選出數據的重要特征，規避維數災難造成的分類準確率低的問題，還可以降低計算的復雜度，提高分類模型的性能［2］。特征選擇算法主要分為過濾式（Filter）、包裝式（Wrapper）與嵌入式（Embedded）方法三類［3-6］。其中，包裝式特征選擇算法在特征選擇的過程中是以分類器的分類性能評價特征子集，如K近鄰算法、序列特征選擇（Sequential Feature Selection，SFS）等［7］。但包裝式特征選擇算法每次選擇特征時均要執行分類算法以判斷特征子集的優劣，因此算法的計算效率較低［8］。嵌入式特征選擇方法，是將特征選擇過程和學習模型的訓練過程在同一個優化過程中完成，并使用同一個目標函數來實現特征篩選，如正規化方法、決策樹算法等［9］。嵌入式特征選擇方法可以快速地選擇特征子集，但是目標函數的構造是一大難點［10］。過濾式特征選擇方法使用準則函數來評估特征相較于目標類的相關性或鑒別能力，因其克服了包裝式與嵌入式特征選擇方法計算復雜性高的缺點被廣泛用于數據的預處理［11-12］。常見的過濾式特征選擇方法主要有互信息（Mutual Information，MI）、相關系數、最大相關最小冗余（max-Relevance and Min-Redundancy，mRMR）算法、Relief 算法等［13］。其中，由Kira等［14］在1992 年提出的Relief 算法是一種高效的過濾式特征選擇算法，因其復雜性低、高效快速而適用于處理高維數據，該算法在二分類問題中顯示出較好的性能［15］。1994年，Kononenko［16］提出了擴展的Relief 算法，即ReliefF 算法，該算法不僅可以解決多分類問題，還可以解決數據缺失和存在噪聲的問題，已被廣泛應用于多個領域［17-18］；但是ReliefF 算法在應用中存在穩定性不足、特征權值波動較大的問題。為此，Wang等［19］提出在給定樣本時，根據局部樣本的平均偏差計算其權重的方法來提高特征選擇方法的穩定性。同時，改進已選取的近鄰樣本之間相關性的計算方法也可以用來提高ReliefF 算法的穩定性［20-22］。但是，目前所提出的大多數改進算法均忽略了近鄰樣本的選取方式對于算法穩定性的影響；此外，這些改進的ReliefF 算法由于缺乏與分類模型的交互，對于特征的選擇標準沒有明確的評價指標，從而在利用篩選出的特征子集進行后續的分類問題時可能會出現分類準確率較低的問題［23］。為了解決這一問題，趙玲等［24］提出利用支持向量機（Support Vector Machine，SVM）與特征選擇算法實現信息交互以自動尋找特征子集的方法；但是，由于每次實驗訓練集的隨機性，篩選的特征子集仍具有較大的隨機性，不具有泛化能力。

為了實現最優特征子集的自動篩選，緩解維數災難造成的分類準確率降低問題，本文提出一種可以篩選出穩定的特征子集且具有泛化能力的特征選擇算法。首先，對傳統ReliefF 算法的近鄰樣本選取方法進行改進，提出MICReliefF（Maximum Information Coefficient-ReliefF）算法，利用最大信息系數（Maximal Information Coefficient，MIC）［25］替代歐氏距離估計樣本之間差異，尋找同類與異類近鄰樣本；其次，將選擇的特征子集輸入到SVM 分類器，以SVM 的分類準確率作為評價指標，多次尋優，自動確定其最優特征子集，實現MICReliefF 算法與分類模型的交互優化，即MICReliefF-SVM自動特征選擇算法。利用UCI 多個公開數據集對MICReliefF-SVM 算法的性能進行了驗證，并且利用SVM 模型與極限學習 機（Extreme Learning Machine，ELM）對MICReliefF-SVM 自動特征選擇算法篩選的特征子集進行測試。

1 ReliefF算法

ReliefF 算法是一種具有低計算復雜度的過濾式特征選擇算法。首先，從總樣本D中隨機選取樣本R；然后，在數據中找出與樣本R屬同一類的k個最近鄰的樣本，記作Hj，與樣本R不在同一類中的k個最近鄰的樣本，記作M(C)j；最后，計算樣本中特征A的特征權重，公式如下：

其中：class(R)是隨機選取的樣本R所屬的類別；P(C)是類別C出現的概率；P(class(R)是隨機選取的樣本R所屬類別的概率；diff(A，R，Hj)和diff(A，R，M(C)j)分別表示兩樣本在特征A下的距離；m是抽樣次數。在ReliefF 算法中，近鄰樣本數通常設置為k=10［26］。

ReliefF 算法的偽代碼如下所示。

算法1 ReliefF 算法。

輸入 數據集D=，特征個數a，迭代次數m，近鄰樣本的個數k。

輸出 特征權重向量W。

ReliefF 算法的目標是通過多次評估隨機選取的樣本實例與同類近鄰樣本和異類近鄰樣本之間的類間距離和類內距離，計算每個特征的權重，挑選出權值高的特征，從而完成特征選擇的任務［27］。但是，ReliefF 算法在尋找近鄰樣本時，采用的是相似度度量，如果隨機抽取的樣本較少，將導致特征權值波動較大，進而影響特征排名。近鄰樣本的選取對于算法的穩定性具有較大的影響。在選擇近鄰樣本時，ReliefF算法通過使用歐氏距離來計算所有樣本與所隨機選取的樣本實例R的相似程度，以便從同類與不同類樣本中分別選擇k個距離最小，即相關性最大的樣本作為近鄰樣本。盡管歐氏距離已經成為評定兩個樣本之間相近程度的一種常見度量方式，但它普適于樣本的各個特征度量的標準比較統一的情形。對絕大部分真實數據集來說，樣本中每個特征的取值不是統一的標準，因而會導致近鄰樣本的選取極易被特征值較大的特征所影響，從而忽略了特征值較小的特征對于分類準確率的貢獻。

2 MICReliefF-SVM 自動特征選擇算法

為了提高ReliefF 算法的性能，本文使用最大信息系數（MIC）來代替歐氏距離求解樣本之間的相關性，即MICReliefF 算法。

MIC 是一種用來捕捉屬性間相關性的統計量［25］，能夠有效度量變量之間的復雜關系。

對于數據集D={U=ui，V=vi}，i=1，2，…，N，變量和變量的互信息可以表示為：

其中：p(u，v)是變量U、V的聯合概率密度；p(u)、p(v)分別是變量U、V的邊緣概率密度。

變量U和變量V的MIC 定義為：

其中：a、b是在x、y軸方向上劃分的格子個數，應滿足|a| ·|b| ＜B，B=N0.6，N是樣本數。

盡管ReliefF 算法能夠計算特征所占的權重，但由于缺乏與分類模型的交互，且對于特征子集的選擇標準沒有明確的評價指標，因此，ReliefF 算法本身無法去除冗余特征。在實際應用中，一般都是根據已有經驗設置權重閾值，大于閾值的特征被保留下來，而小于閾值的特征則被剔除，這樣就會導致不當的閾值選擇對分類結果產生不好影響。如果將MICReliefF 算法排序后的特征輸入到SVM 分類器，利用SVM模型的分類準確率來選擇特征子集，通過多次交互尋優，則可以自動確定其最優特征子集，即MICReliefF-SVM 自動特征選擇算法。算法的流程如圖1 所示。

3 實驗與結果分析

為了驗證MICReliefF-SVM 自動特征選擇算法的性能，使用UCI 公開數據庫中乳腺癌數據集WDBC、電離層數據集Ionosphere、馬腹絞痛數據集Horse Colic、蘑菇數據集Mushroom、帕金森數據集Parkinsons、聲納、地雷、巖石數據集Connectionist Bench 以及檢測是否有新分子的Musk 數據集共7 個常用于分類問題研究的數據集［28］對算法的特征選擇能力進行了測試。表1 為所選數據集的信息，以及每一次實驗時隨機選取的訓練集和測試集的個數。

表1 實驗數據集的信息Tab.1 Information of experimental datasets

實驗中分別采用ReliefF-SVM 算法和MICReliefF-SVM 算法對7 個數據集中的特征進行篩選，每次實驗采用隨機抽取的方式將每個數據集的總樣本劃分成60%的訓練集與40%的測試集，利用訓練集對SVM 模型進行訓練，選出分類準確率最高的特征子集，并將其應用到測試集進行測試。為了能選擇出穩定的最優特征子集，重復實驗過程500次，統計500次實驗中測試集出現的最優特征子集及其出現的次數，最后把500 次實驗中出現次數最多的最優特征子集作為最終的最優特征子集，篩選結果如表2 所示。從表2 中給出的篩選后的特征個數結果可知，與ReliefF-SVM 算法相比，在7 個UCI 數據集上MICReliefF-SVM 算法除對Connectionist Bench數據集篩選后保留相同的特征個數之外，在其他數據集上都篩除了更多的冗余特征，即能有效地減少樣本的特征維度。

表2 各算法的特征篩選結果比較Tab.2 Comparison of feature filtering results of different algorithms

為了驗證MICReliefF-SVM 算法所選特征子集的分類效果以及穩定性，利用SVM 與ELM 兩種分類模型，分別對表2篩選出的特征進行測試，即分別采用SVM 與ELM 兩種分類模型對利用MICReliefF-SVM 算法選取的特征子集、ReliefFSVM 算法選取的特征子集以及原始數據集中的全部特征進行分類。在SVM 分類器中，采用RBF（Radial Basis Function）核函數，核參數C=1，γ=100［11］；在ELM 分類器中，采用Sigmoid 核函數，隱層節點的個數設置為20［29］。每次實驗仍按照表1 所示的標準劃分訓練數據集與測試數據集，實驗100次，以平均準確率Acc（Accuracy）、平均敏感度Sen（Sensitivity）、平均特異性Spe（Specificity）、平均精準度Pre（Precision）以及平均F 值（F-measure）等作為評價指標。上述評價指標基于表3 混淆矩陣計算，其定義如下：

表3 混淆矩陣Tab.3 Confusion matrix

SVM 分類模型中各評價指標的平均值及其標準差如表4 所示。從表4 的數據可知：

表4 各特征選擇算法在SVM模型中評價指標的平均值與標準差比較Tab.4 Mean and standard deviation comparison of evaluation indexes among each feature selection algorithms in SVM model

1）在WDBC 數據集中，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的Accuracy、Sensitivity、F 值指標的平均值均優于采用原始數據集中的全部特征，且MICReliefF-SVM 算法結果整體最優。對于標準差而言，除Specificity外，Accuracy、Sensitivity、Precision、F 值的標準差均優于采用原始數據集中的全部特征。

2）在Ionosphere 數據集中，除Sensitivity 指標外，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的Accuracy、Specificity、Precision、F 值的平均值及其標準差均優于采用原始數據集中的全部特征，且MICReliefF-SVM 算法結果最優。

3）在Horse Colic數據集中，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的各指標的平均值及其標準差均優于采用原始數據集中的全部特征，且MICReliefF-SVM 算法結果最優。

4）在Mushroom 數據集中，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的Accuracy、Sensitivity、Specificity、Precision、F 值的平均值均優于采用原始數據集中的全部特征，其中，MICReliefF-SVM 算法選取的特征子集的Accuracy、Sensitivity、F 值指標結果優于ReliefFSVM 算法。對于標準差而言，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集與原始數據集在精確到小數后4 位時，標準差均為0。

5）在Parkinsons 數據集中，除Sensitivity 指標外，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的各指標的平均值均優于采用原始數據集中的全部特征，且MICReliefF-SVM 算法結果最優，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的各指標的標準差均優于采用原始數據集中的全部特征。

6）在Connectionist Bench 數據集中，利用MICReliefFSVM 算法選取的特征子集的各指標的平均值及其標準差均優于利用ReliefF-SVM 算法選取的特征子集以及采用原始數據集中的全部特征，除Sensitivity 指標的均值外，利用ReliefF-SVM 算法選取的特征子集各指標的平均值及其標準差均優于采用原始數據集中的全部特征。

7）在Musk 數據集中，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的Accuracy、Specificity、Precision、F 值指標的平均值均優于采用原始數據集中的全部特征，且MICReliefF-SVM 算法結果整體最優。對于標準差而言，MICReliefF-SVM 算法選取的特征子集的指標除Specificity 劣于ReliefF-SVM 算法外，Accuracy、Sensitivity、Precision、F 值的標準差均優于ReliefF-SVM 算法選取的特征子集和采用原始數據集中的全部特征。

ELM 分類模型中各評價指標的平均值及其標準差如表5 所示。

表5 各特征選擇算法在ELM模型中評價指標的平均值與標準差比較Tab.5 Mean and standard deviation comparison of evaluation indexes among each feature selection algorithms in ELM model

從表5 可知：

1）在WDBC 數據集中，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的各指標的平均值均優于采用原始數據集中的全部特征；其中，利用MICReliefFSVM 算法選取的特征子集的Accuracy、Sensitivity 以及F 值指標的平均值高于ReliefF-SVM 算法選取的特征子集。對于標準差而言，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的Sensitivity、Precision、F 值指標的標準差均優于采用原始數據集中的全部特征。

2）在Ionosphere 數據集中，除Sensitivity 指標外，利用MICReliefF-SVM 算法選取的特征子集的Accuracy、Specificity、Precision、F 值的平均值及其標準差均優于利用ReliefF-SVM 算法選取的特征子集以及采用原始數據集中的全部特征，且ReliefF-SVM 算法選取的特征子集各指標的平均值及其標準差均優于采用原始數據集中的全部特征。

3）在Horse Colic 數據集中，利用ReliefF-SVM算法與MICReliefF-SVM 算法選取的特征子集的各指標的平均值及其標準差均優于采用原始數據集中的全部特征，且MICReliefF-SVM 算法結果最優。

4）在Mushroom 數據集中，利用MICReliefF-SVM 算法選取的特征子集的Accuracy、Sensitivity、F 值的平均值均優于利用ReliefF-SVM 算法選取的特征子集與采用原始數據集中的全部特征，且ReliefF-SVM 算法選取的特征子集各指標的平均值均優于采用原始數據集中的全部特征；對于標準差而言，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的標準差整體優于采用原始數據集中的全部特征。

5）在Parkinsons、Connectionist Bench 和Musk 數據集中，利用ReliefF-SVM 算法與MICReliefF-SVM 算法選取的特征子集的各指標的平均值及其標準差均優于采用原始數據集中的全部特征，且MICReliefF-SVM 算法結果最優。

SVM 模型與ELM 模型的測試結果均證明，MICReliefFSVM 算法可以在減少樣本特征維度的同時，有效提高分類準確率，該算法不僅能夠自動選擇出分類準確率良好的特征子集，而且選取的特征子集具有一定的穩定性和泛化能力。

為了探究MICReliefF-SVM 算法的計算效率，本文統計了采用SVM 與ELM 兩種分類模型對MICReliefF-SVM 算法選取的特征子集、ReliefF-SVM 算法選取的特征子集以及原始數據集中的全部特征進行分類時100 次實驗的總運行時間，結果如表6 所示。

從表6 可以看出：在SVM 和ELM 兩種分類模型中，對MICReliefF-SVM 算法選取的特征子集、ReliefF-SVM 算法選取的特征子集進行分類的運算時間均短于對原始數據集中的全部特征進行分類的時間，其中MICReliefF-SVM 算法選取的特征子集的分類時間最短，即計算效率最高。說明本文提出的MICReliefF-SVM 算法可以有效地提高后續學習算法的計算效率，進一步說明了MICReliefF-SVM 算法的有效性。

表6 不同特征選擇算法在SVM模型和ELM模型中的運行時間比較 單位：sTab.6 Comparison of running time among different feature selection algorithms in SVM model and ELM model unit：s

為進一步驗證MICReliefF-SVM 算法的有效性，本文在7個數據集上分別利用SVM 與ELM 分類模型比較了MICReliefF-SVM 算法與MI、mRMR、支持向量機遞歸特征消除（Support Vector Machines-Recursive Feature Elimination，SVM-RFE）、相關性特征選擇（Correlation-based Feature Selection，CFS）、隨機森林（Random Forest，RF）、遺傳算法（Genetic Algorithm，GA）［30-33］六種經典的傳統特征選擇算法的分類準確率，每次實驗仍按照表1 所示的標準劃分訓練數據集與測試數據集，實驗100次，求其平均準確率作為評價標準。

各特征選擇算法在SVM 分類模型中的實驗結果如表7所示。從表7 中給出的結果可知：MICReliefF-SVM 算法除了在Mushroom 數據集上的準確率稍劣于RF 特征選擇算法外，在其他6 個數據集上的準確率均優于對比算法。各特征選擇算法在ELM 分類模型中的實驗結果如表8 所示。從表8中給出的結果可知：MICReliefF-SVM 算法除在Mushroom 數據集和Musk 數據集上的準確率劣于RF 特征選擇算法，在其他6 個數據集上的準確率均優于對比算法。因此，MICReliefF-SVM 算法所選特征子集的分類能力整體上要優于對比算法。

表7 不同特征選擇算法在SVM模型中的分類準確率對比Tab.7 Comparison of classification accuracy among different feature selection algorithms in SVM model

表8 不同特征選擇算法在ELM模型中的分類準確率對比Tab.8 Comparison of classification accuracy among different feature selection algorithms in ELM model

4 結語

本文提出了一種MICReliefF-SVM 交互的自動特征選擇算法，采用多個UCI 數據集對算法的有效性進行驗證。研究結果表明：

1）與ReliefF 算法相比，MICReliefF-SVM 算法在特征冗余的篩選上具有一定的優勢。利用SVM 與ELM 分類模型對UCI 多個公開數據集上的數據進行分類的對比實驗結果表明，MICReliefF-SVM 算法在減少樣本特征維度的同時，有效提高了分類準確率，且該算法可以實現分類準確率良好的特征子集的自動選擇，選取的特征子集具有一定的穩定性和泛化能力。

2）與經典MI、mRMR、SVM-RFE、CFS、RF 以及GA 特征選擇算法相比，MICReliefF-SVM 算法所選特征子集整體上具有更好的分類能力。

在未來的工作中，將會繼續對提高ReliefF 算法的穩定性以及該算法在處理高維特征數據方面的應用進行研究。