改進的ReliefF在ICP特征選擇中的應(yīng)用*

張光普 周從華 張 婷

（1.江蘇大學計算機科學與通信工程學院 鎮(zhèn)江 212013）（2.無錫市婦幼保健院 無錫 214002）

1 引言

特征選擇是人們在機器學習任務(wù)中，一個重要的“數(shù)據(jù)預(yù)處理”過程。數(shù)據(jù)和特征決定了機器學習的上限，而模型和算法只是逼近這個上限而已［1］。通過特征選擇，可以將數(shù)據(jù)集中的冗余數(shù)據(jù)以及相關(guān)性較小的數(shù)據(jù)清除，在確保特征集合包含所有重要特征的情況下，降低數(shù)據(jù)集的維度，從而提高學習器的效率和精度［2～3］。

特征選擇已經(jīng)成為醫(yī)學數(shù)據(jù)預(yù)處理中不可缺少的部分［4～6］。特征選擇算法主要有過濾式（Filter）方法和包裹式（Wrapper）方法和嵌入式（Embedded）方法三種。包裹式特征選擇方法直接將最終所使用的分類算法或模型的性能作為特征子集的評價標準，在特征選擇過程中需多次訓練學習器，所以算法計算復(fù)雜度高，計算開銷會比過濾式特征選擇方法大得多，對于樣本數(shù)少高維度的醫(yī)學數(shù)據(jù)并不適用。與包裹式特征選擇算法需要綁定后續(xù)的學習器不同，過濾式特征選擇方法通過數(shù)據(jù)特征的內(nèi)在屬性來評價特征的差異性，根據(jù)差異性評分對特征進行排序，選擇合適的特征用于學習器的學習，選擇過程中不考慮學習器對特征的影響［7～8］。

妊娠期肝內(nèi)膽汁淤積癥（Intrahepatic Cholestasis of Pregnancy，ICP）是妊娠期嚴重危害母嬰的并發(fā)癥，其發(fā)病率最高可以達12%［9～10］。原始的ICP數(shù)據(jù)集中含有大量的生物標志物信息，特征間通常會存在相關(guān)性，以及在ICP數(shù)據(jù)的采集過程中，由于設(shè)備和人為因素，數(shù)據(jù)集中往往會存在較大的冗余和噪聲，由于ICP患者們存在多種妊娠結(jié)局，并且不同妊娠結(jié)局間的人數(shù)差異較大，使數(shù)據(jù)集存在一定的不平衡性。

本文針對ICP數(shù)據(jù)的冗余性及數(shù)據(jù)不平衡的問題，在ReliefF算法的基礎(chǔ)上進行改進，提出了一種新的特征選擇算法SC-ReliefF算法，并應(yīng)用到ICP特征選擇當中篩選出對患病影響最大的特征子集。一方面，設(shè)計了新的樣本選擇方法，改進后的樣本選擇方法根據(jù)每個樣本與類中心的歐式距離，均勻地從各個類別中各自選擇n個樣本用來累計權(quán)值，從而使ReliefF算法可以更好地應(yīng)用于非平衡數(shù)據(jù)當中。另一方面，ReliefF算法去除冗余特征的能力較低，新的算法通過引入調(diào)整的余弦相似度用來度量特征向量之間的相關(guān)性，有效地去除ICP數(shù)據(jù)中的冗余特征。SC-ReliefF算法從樣本的選擇上和去冗余特征兩個方面對ReliefF算法進行了改進，使ReliefF算法適用于非平衡數(shù)據(jù)，同時有效去除原始數(shù)據(jù)集中的冗余特征。

2 ReliefF特征選擇算法概述

Relief（Relevant Features）算 法被Kira和Rendell在1992年提出，用于解決二分類問題，是一種高效的過濾式特征選擇算法［11～12］。算法的核心思想是表現(xiàn)好的特征將有利于分類，反之，表現(xiàn)差的特征會對分類產(chǎn)生不利影響。該方法通過比較樣本在某個特征上的猜中近鄰與猜錯近鄰的距離大小，來確定該特征對分類是否有利，同時賦予該特征一個權(quán)重。最后，指定一個閾值，剔除權(quán)重小于閾值的特征即可。

設(shè)樣本集T=｛（x1，y1），（x2，y2），…，（xn，yn）｝，每個樣本中存在k個特征，xi=｛xi1，xi2，…，xik｝，兩個樣本xa和xb在特征j上的距離表示為

若特征j為離散型，

若特征j為連續(xù)型，

由于Relief算法只能處理二分類問題，Kononenko在1994年對Relief算法進行了改進，得到ReliefF算法，改進后的算法可以處理多分類問題。

假設(shè)數(shù)據(jù)集T=｛（x1，y1），（x2，y2），…，（xn，yn）｝，T中包含n個樣本以及m（m＞2）個樣本種類m（m＞2）個，隨機從數(shù)據(jù)集中選取樣本xi，若樣本屬于第k類（1≤k≤m），與Relief算法類似，ReliefF算法首先在第k類樣本中找到d個xi的最近鄰樣本，并將其放入集合N，記為猜中近鄰集合，然后在除k類之外的每一個類別的樣本中分別找出d個xi的最近鄰樣本，并將其放入集合M（l）記作（l=1,2,…,m;l≠k），記為，猜錯近鄰集合。則xi與猜中近鄰在特征j上的距離表示為

則xi與猜錯近鄰在特征j上的距離表示為

其中pl=nl/n，表示第l類樣本在數(shù)據(jù)集T中所占的比例。M（l）h表示第l類樣本中第h個樣本。

則特征j的權(quán)重Wj計算公式為

通過分析式（3）～（5）可以得出，ReliefF算法通過計算樣本xi的d個猜中近鄰與其異類l中的距離xi最近的d個樣本在特征j上的平均距離，并將平均距離進行加權(quán)平均，即可得到樣本xi與l類在特征j上的距離。最后在xi的所有異類上進行此操作得出xi與異類樣本在特征j上的距離差異。由此評價該特征區(qū)分類別的能力。

3 對ReliefF算法的改進

3.1 樣本的選擇

ReliefF算法采用隨機的方式從訓練樣本中重復(fù)選取m個樣本，由于m一般遠遠小于樣本量，這就要求所選擇的m個樣本盡量均勻地分布在每個類別的樣本空間中，從而使m個樣本能夠更加有效地評估各個特征的權(quán)重。但在實際的ICP數(shù)據(jù)集中，ICP患者們有多種可能的妊娠結(jié)局，患者在各個ICP妊娠結(jié)局上的分布存在較大差異，若果采用這種隨機選取樣本點的方式，這必然會導(dǎo)致［13］：

1）特征的權(quán)重會向樣本數(shù)量多的類別傾斜。

2）隨機挑選所帶來的另一個問題是算法的不穩(wěn)定性。

針對上述兩個問題，本文對ReliefF中的樣本選擇方法進行了如下改進得到SRelifF算法。

在抽取樣本的時候，將從每個類別的樣本中個抽取m個樣本，避免隨機采樣時，少數(shù)類樣本被選擇幾率過小的情況。

1）首先通過式（6）計算樣本k類樣本中心：

其中，classk代表k類樣本的集合，nk表示k類樣本的個數(shù)。

2）通過式（7）計算每個k類樣本距離樣本中心的距離：

3）將k類中每個樣本按照與樣本中心距離大小從小到大排序，按照間隔Δd=nk/m等間隔地選取m個樣本作為特征權(quán)重累積樣本，放入集合Dk。

結(jié)合上述樣本選擇方法對ReliefF算法改進得到SReliefF算法，改進之后的樣本選擇方法一方面可以保證均勻地從各個類別樣本中選擇相同數(shù)目的樣本進行特征權(quán)重的累積計算，一定程度上避免了ICP數(shù)據(jù)集的不平衡性對ReliefF算法帶來的影響。另一方面，由于樣本不是隨機選擇的，那么只要樣本集合沒有發(fā)生變化，選擇的樣本都是固定的，所以每次運行ReliefF算法得到的特征權(quán)重是穩(wěn)定的，從而提高了算法的穩(wěn)定性。

3.2 特征之間的相似性

SReliefF雖然能夠用于非平衡數(shù)據(jù)集的特征選擇，但仍然存在著以下問題：SReliefF算法并沒有考慮到特征之間的相關(guān)性，這不可避免地會造成選擇之后的特征子集存在一定的冗余性。本文引入余弦相似度作為特征相似性的度量進一步在特征子集中剔除冗余特征［14］。

余弦相似度通過測量兩個矢量之間角度的余弦來測量兩個矢量之間的相似性［18］。

余弦相似度的計算如式（8）所示：

其中，A和B為向量，余弦相似度s（A，B）衡量了兩個向量之間的相關(guān)性程度，其值越大代表兩個向量之間的相關(guān)性越強。將特征向量表示為Fi和Fj，利用余弦相似度作為特征相似性度量，得向量Fi和Fj的相似度：

根據(jù)式（9）推得Fi與特征集合F之間的冗余度：

式（10）中，||F代表特征集合F中所包含的特征總數(shù)，F(xiàn)j為特征集合F中的特征，結(jié)合式（10）和式（9）得特征集合F的冗余度計算式：

SC-ReliefF算法的基本思想是：首先利用SReliefF算法剔除相關(guān)性較小的特征得到特征子集F，然后通過特征集合評價函數(shù)進一步在特征子集F中進行去冗余操作，最終得到Fend。得到特征集合的評分函數(shù)：

SC-ReliefF算法主要步驟：首先通過SReliefF算法得到特征集合相應(yīng)的權(quán)重向量，并對向量中的各個權(quán)重分量從大到小排序，按照設(shè)定的閾值對特征集合進行初步篩選。然后進行特征子集搜索，搜索方式為序列向前搜索：每次移除特征集合中權(quán)重最小的特征，通過評分函數(shù)計算刪除該特征后特征集合的評分，并與原特征集合評分進行比較。SC-ReliefF的具體步驟如表1所示。

表1 SC-ReliefF算法

其中，fi代表權(quán)重排序第i位的特征。此外，算法在序列向前搜索過程中加入評分因子η，表示在刪除第i位特征后，評分至少提升η才能將該特征刪除并放入候選集合，否則保留該特征，繼續(xù)搜索特征集合。

SC-ReliefF算法根據(jù)特征權(quán)重和冗余度度量共同構(gòu)建了特征集合的評價函數(shù)，使用序列向前搜索的方式進行子集的搜索與生成，從整體角度對特征子集進行評價，且加入評分因子，控制特征子集規(guī)模，可以分析不同規(guī)模的特征子集的優(yōu)劣。最后，本文通過實驗驗證了SC-ReliefF算法在不會降低分類算法性能的基礎(chǔ)上，可以去除冗余特征，得到規(guī)模較小且有效的特征子集。

4 實驗分析

4.1 實驗信息

本次實驗數(shù)據(jù)由無錫市婦幼保健院提供，包含400名患者和300正常人的相關(guān)數(shù)據(jù)，根據(jù)患者的妊娠結(jié)局可分為胎兒窘迫、新生兒窒息、早產(chǎn)、羊水污染四種。

本實驗采用精度（Acc）、宏差準率（macro-P）、宏查全率（macro-R）以及相應(yīng)的宏F1（macro-F1）作為分類算法的性能度量方式。

4.2 實驗結(jié)果及分析

本實驗使用ReliefF、mRMR、RS-ReliefF［15］特征選擇算法以及本文提出的SC-ReliefF算法對ICP數(shù)據(jù)集進行特征選擇，然后利用BP-NN、SVM進行分類。實驗使用十折交叉驗證法，本實驗通過比較在分類器取得最佳精度的條件下，特征選擇算法選擇的特征子集規(guī)模以及學習器的其他性能，驗證SC-ReliefF算法的有效性。

本節(jié)實驗選取四種特征選擇算法所選取的不同規(guī)模的特征子集，子集范圍從10%～100%，并利用BP-NN、SVM分類器，利用十折交叉驗證算法在不同子集規(guī)模下分類器的分類性能。圖1和2為四種特征選擇算法選擇不同規(guī)模特征子集在BP-NN和SVM分類器上的平均分類精度。

圖1 四種算法在BP-NN上的對比

圖2 四種算法在SVM上的對比

由圖1可知，在BP-NN上，所提算法SC-ReliefF在50%～60%的特征選擇比例下平均準確度可達0.8，然后隨著特征子集規(guī)模逐漸增加，算法準確度逐漸下降。而相對于原始的ReliefF算法，算法直到選取70%～80%的子集規(guī)模時，且精確度最高只有0.78；RS-ReliefF是另一種最ReliefF改進的特征選擇算法，在選取規(guī)模在60%～70%時，最高平均精度可達0.78；mRMR特征選擇算法在選取規(guī)模為60%～70%之間時，最高分類精度可達0.79。在SVM分類器上也有類似規(guī)律，算法性能明顯優(yōu)于對比算法，在50%～60%區(qū)間內(nèi)有較大提升。結(jié)合四種特征選擇算法在兩種分類器上的表現(xiàn)，說明本文所提出的算法能有效去除冗余特征，使得算法在較小的特征規(guī)模下，盡可能取得優(yōu)秀的性能。

本文在取四種特征選擇算法在取得最佳平均分類精度的情況下，綜合其他分類指標進行進一步對比，如表2所示。

表2 四種算法性能參數(shù)對比

由表2可知，本文所提的SC-ReliefF算法相較于傳統(tǒng)的ReliefF算法，所選擇的特征子集在兩種分類器算法上的性能均有明顯提高。此外在與RS-ReliefF和mRMR兩種ICP特征選擇算法相比，改進后的算法在多數(shù)情況下有著更好的性能。實驗結(jié)果說明，本文提出的SC-ReliefF算法可以選擇出較小規(guī)模的特征子集，且對學習器性能有略微提高，證明了SC-ReliefF算法在ICP特征選擇中的有效性。

5 結(jié)語

本文針對ICP數(shù)據(jù)集普遍存在的高冗余和非平衡性的特點，對傳統(tǒng)的ReliefF特征選擇算法進行適應(yīng)性改進。改進了ReliefF算法的樣本選擇算法，通過類內(nèi)平均距離均勻地從各個類別選擇樣本，一定程度上消除非平衡性帶來的影響。隨后在此基礎(chǔ)上，以余弦相似度作為特征冗余的度量進一步去除冗余特征，提出了一種結(jié)合余弦相似度的ReliefF的特征選擇算法——SC-ReliefF算法并用于ICP特征選擇中。實驗結(jié)果表明，SC-ReliefF算法能夠在提升學習器整體性能情況下，選擇出規(guī)模更小的ICP特征子集，從而提升學習器的效率。本文后續(xù)工作將集中于如何更好地衡量特征間的冗余度以及提升學習器的分類精度兩個方向上。