張光普 周從華 張 婷

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

1 引言

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

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

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

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

2 ReliefF特征選擇算法概述

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

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

若特征j為離散型，

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

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

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

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

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

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

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

3 對(duì)ReliefF算法的改進(jìn)

3.1 樣本的選擇

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

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

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

針對(duì)上述兩個(gè)問(wèn)題，本文對(duì)ReliefF中的樣本選擇方法進(jìn)行了如下改進(jìn)得到SRelifF算法。

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

1）首先通過(guò)式（6）計(jì)算樣本k類樣本中心：

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

2）通過(guò)式（7）計(jì)算每個(gè)k類樣本距離樣本中心的距離：

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

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

3.2 特征之間的相似性

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

余弦相似度通過(guò)測(cè)量?jī)蓚€(gè)矢量之間角度的余弦來(lái)測(cè)量?jī)蓚€(gè)矢量之間的相似性［18］。

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

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

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

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

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

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

表1 SC-ReliefF算法

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

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

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)信息

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

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

4.2 實(shí)驗(yàn)結(jié)果及分析

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

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

圖1 四種算法在BP-NN上的對(duì)比

圖2 四種算法在SVM上的對(duì)比

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

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

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

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

5 結(jié)語(yǔ)

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