基于加權(quán)K近鄰的特征選擇方法

李雙杰，張開(kāi)翔，王士棟，王淑琴

（天津師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，天津 300387）

在當(dāng)今大數(shù)據(jù)時(shí)代，很多應(yīng)用中數(shù)據(jù)集的維度很高，尤其在DNA 微序列分析、圖像處理、模式識(shí)別和文本分類等領(lǐng)域，數(shù)據(jù)具有極高的維度[1-3]，然而，在分類任務(wù)中，過(guò)高維度造成的“維度詛咒”現(xiàn)象會(huì)導(dǎo)致過(guò)擬合，從而降低學(xué)習(xí)模型的泛化能力[4]，而且許多特征都是不相關(guān)或者冗余特征，它們?cè)诜诸悓W(xué)習(xí)過(guò)程中毫無(wú)用處.特征選擇是機(jī)器學(xué)習(xí)的一個(gè)重要的數(shù)據(jù)預(yù)處理過(guò)程[5-6]， 其目標(biāo)就是剔除不相關(guān)和冗余特征，以減少學(xué)習(xí)維度，并在可接受的時(shí)間內(nèi)獲得高準(zhǔn)確率，同時(shí)降低訓(xùn)練模型所用的時(shí)間和存儲(chǔ)空間[7].

在過(guò)去幾年里，各種各樣的特征選擇算法被相繼提出[8].根據(jù)分類器是否獨(dú)立，特征選擇方法可以分為Filter、Wrapper 和 Embedded 3 類.由于在選擇候選特征子集時(shí)，F(xiàn)ilter 方法與分類器相分離[9-11]，因此Filter方法相對(duì)簡(jiǎn)單，時(shí)間復(fù)雜度較低，可以和多種分類器結(jié)合.Wrapper 方法通常以分類器的性能作為候選特征子集的評(píng)價(jià)準(zhǔn)則[12]， 因此它具有較好的分類性能，但其計(jì)算開(kāi)銷通常比Filter 方法大很多.Embedded 方法結(jié)合了Filter 方法和Wrapper 方法的優(yōu)點(diǎn)，在學(xué)習(xí)算法訓(xùn)練過(guò)程中可以自動(dòng)進(jìn)行特征選擇[13]，因此它通常優(yōu)于Filter 方法和Wrapper 方法.

在模式識(shí)別中，K 近鄰算法經(jīng)常用于分類和回歸任務(wù)[14-15].K 近鄰的優(yōu)勢(shì)是算法簡(jiǎn)單且對(duì)異常值不敏感.近年來(lái)，它也被用于特征選擇方法的研究.文獻(xiàn)[16]提出了一種基于KNN 的加權(quán)策略（MKNN）方法，它使用傳統(tǒng)的信息增益作為特征選擇方法，MKNN 作為分析基因表達(dá)數(shù)據(jù)的分類器，該方法根據(jù)數(shù)據(jù)集中每一類別中樣本到該類中心點(diǎn)的距離對(duì)樣本進(jìn)行加權(quán)，從而使K 個(gè)近鄰樣本對(duì)判定測(cè)試樣本類別的貢獻(xiàn)不同，但該方法在計(jì)算距離時(shí)沒(méi)有考慮特征的重要性.文獻(xiàn)[17]將KNN 作為一個(gè)基本單元集成到特征選擇框架中，用以評(píng)價(jià)候選特征子集的優(yōu)劣，該方法通過(guò)隨機(jī)選擇多個(gè)特征子集，用KNN 評(píng)價(jià)特征子集的分類準(zhǔn)確率，最后將相應(yīng)準(zhǔn)確率的平均值作為特征的支持度，支持度越高表示特征與類別的相關(guān)性越大， 該方法將KNN 視為一個(gè)黑盒子， 沒(méi)有對(duì)KNN 算法展開(kāi)研究.在對(duì)測(cè)試樣本的類別進(jìn)行判定時(shí)，一方面，應(yīng)依據(jù)其K 個(gè)近鄰樣本與其距離的大小不同來(lái)決定每個(gè)近鄰樣本對(duì)類別的貢獻(xiàn)，距離越小的貢獻(xiàn)也應(yīng)越大；另一方面，由于每個(gè)特征對(duì)樣本類別的重要程度是不同的，所以在計(jì)算樣本間距離時(shí)，還應(yīng)考慮每個(gè)特征的重要程度.為此，本文提出了一種基于加權(quán)K 近鄰的特征選擇算法，該算法在計(jì)算樣本類別時(shí)既考慮每個(gè)特征的重要程度，又考慮近鄰樣本的距離，并使用遺傳算法搜索最優(yōu)特征權(quán)重向量，最后按最優(yōu)特征權(quán)重向量對(duì)所有特征降序排序，依次選出對(duì)應(yīng)的前N 個(gè)特征組成特征子集，并用分類器評(píng)價(jià)其質(zhì)量，本文方法屬于Filter 方法.使用6 個(gè)真實(shí)數(shù)據(jù)集，將本文方法與現(xiàn)有的 3 種特征選擇方法 MIFS[18]、DISR[19]和 CIFE[20]進(jìn)行比較， 并使用 K 近鄰（KNN）、隨機(jī)森林（random forest）、樸素貝葉斯（NB）、決策樹(shù)（decision tree）和支持向量機(jī)（SVM）5 種分類器對(duì)每個(gè)方法所選擇的特征進(jìn)行分類預(yù)測(cè)，實(shí)驗(yàn)結(jié)果表明本文方法具有較好的分類性能.

1 基于加權(quán)K近鄰的特征選擇方法

本文提出的基于加權(quán)K 近鄰的特征選擇方法，簡(jiǎn)記為 WKNNFS（feature selection based on weighted K-nearest neighbors）.首先初始化一個(gè)種群，種群中每個(gè)個(gè)體代表一個(gè)特征權(quán)重向量；然后用加權(quán)K 近鄰預(yù)測(cè)樣本類別，并設(shè)計(jì)合適的適應(yīng)度函數(shù)；最后用遺傳算法搜索最優(yōu)特征權(quán)重向量.

1.1 相關(guān)定義

對(duì)于分類任務(wù)，測(cè)試樣本的類別由K 個(gè)近鄰?fù)镀睕Q定，將測(cè)試樣本歸為票數(shù)最多的類別.對(duì)于回歸任務(wù)，測(cè)試樣本的類別由K 個(gè)近鄰的目標(biāo)值的算術(shù)平均值決定.以下若無(wú)特殊說(shuō)明均為處理回歸任務(wù).給定一個(gè)回歸問(wèn)題 D=（F，X，Y）， F={f1， f2，…， fm}為特征集合， X={x1，x2，…，xn}為包含 n 個(gè)樣本的數(shù)據(jù)集，xi=（xi1，xi2，…，xim）（1≤i≤n）為樣本 xi的觀測(cè)值， Y={y1，y2，…，yn}為目標(biāo)變量集合，則測(cè)試樣本 xi的預(yù)測(cè)值Pi為

其中：K 為KNN 中選擇的近鄰個(gè)數(shù)；yj為K 個(gè)近鄰樣本的目標(biāo)變量.

定義一個(gè)特征權(quán)重向量 wf=（wf1，wf2，…，wfm）， 則對(duì)特征加權(quán)后的樣本觀測(cè)值用Hadamard 積表示為

使用特征加權(quán)后樣本xi與xj的歐幾里得距離為

傳統(tǒng)的K 近鄰方法中，訓(xùn)練集中用于預(yù)測(cè)測(cè)試樣本類別的K 個(gè)近鄰樣本的貢獻(xiàn)是相同的，這忽略了不同近鄰樣本的重要性的大小，距離越小，它們屬于同一類別的可能性越大，也就越重要.因此，可以對(duì)K個(gè)近鄰的貢獻(xiàn)進(jìn)行加權(quán)，距離越小的近鄰分配的權(quán)重越大.距離加權(quán)函數(shù)w 應(yīng)滿足以下性質(zhì)：

（1）w（d）為一個(gè)單調(diào)遞減函數(shù).

（2） w（0） =1.

（3）w（∞）=0.

本文采用的距離加權(quán)函數(shù)為

考慮特征加權(quán)與距離加權(quán)后測(cè)試樣本xi的預(yù)測(cè)值Pi（wf）定義為

損失函數(shù)用預(yù)測(cè)值Pi（wf）與目標(biāo)函數(shù)的真實(shí)值yi的差表示，定義損失函數(shù)為

成本函數(shù)用所有訓(xùn)練樣本損失函數(shù)的平均值表示，成本函數(shù)值越小說(shuō)明整體的預(yù)測(cè)誤差越小.成本函數(shù)定義為

1.2 遺傳算法

采用遺傳算法搜索最優(yōu)特征權(quán)重向量.

（1）初始化種群：使用（0，1）中的實(shí)數(shù)隨機(jī)初始化含有m 位基因的個(gè)體，每個(gè)個(gè)體代表一個(gè)特征權(quán)重向量.

（2）適應(yīng)度函數(shù)：個(gè)體t 的適應(yīng)度函數(shù)定義為

其中Max 是給定的使Ft（wf）≥0 的正整數(shù).

（3）選擇算子： 使用輪盤(pán)賭選擇（也稱為比例選擇方法）[21]作為選擇算子.

（4）交叉算子： 因?yàn)楸疚氖褂玫氖菍?shí)數(shù)編碼方式，因此采用算術(shù)交叉算子，使下一代盡可能地遺傳上一代中優(yōu)秀個(gè)體的性狀.先根據(jù)概率隨機(jī)選擇一對(duì)父代個(gè)體P1、P2作為雙親，然后進(jìn)行如下隨機(jī)線性組合產(chǎn)生 2 個(gè)新的子代個(gè)體

其中：α、β 為（0，1）中的隨機(jī)數(shù)，個(gè)體基因的取值范圍為[Gmin， Gmax].如果（1 - α）·P1+ β·P2的值小于 Gmin（或大于Gmax）， 則P1′的值為Gmin（或Gmax）， P2′的值同理可得.

（5）變異算子：變異算子采用高斯變異，這種操作方式能重點(diǎn)搜索原個(gè)體附近的某個(gè)局部區(qū)域.高斯變異使用符合均值為μ、方差為σ2的正態(tài)分布的一個(gè)隨機(jī)數(shù)Q 來(lái)替換原來(lái)的基因值.Q 的計(jì)算公式為

其中： ri是在[0，1]范圍內(nèi)均勻分布的隨機(jī)數(shù)， μ 和 σ的計(jì)算公式為

1.3 WKNNFS特征選擇方法

對(duì)于回歸問(wèn)題D=（F，X，Y），首先，用實(shí)數(shù)編碼方式初始化一個(gè)種群， 種群中每個(gè)個(gè)體為一個(gè)權(quán)重向量；然后，對(duì)于當(dāng)前代的每個(gè)個(gè)體t，用基于K 近鄰的方法計(jì)算訓(xùn)練集中每個(gè)樣本的預(yù)測(cè)值Pi（wf）及該個(gè)體對(duì)應(yīng)的適應(yīng)度函數(shù)值Ft（wf），為了更好地找到全局最優(yōu)解，將當(dāng)前代最大的適應(yīng)度函數(shù)值和對(duì)應(yīng)個(gè)體保存到Results 中；最后，分別執(zhí)行選擇、交叉、變異3 個(gè)遺傳算子產(chǎn)生新的種群，并重復(fù)上述操作直到滿足終止條件，即達(dá)到給定的迭代次數(shù).

迭代操作結(jié)束后，將Results 中的適應(yīng)度函數(shù)值降序排序，獲得適應(yīng)度值最高的個(gè)體，則可得到最優(yōu)特征權(quán)重向量，再對(duì)最優(yōu)特征權(quán)重降序排序，即可得到對(duì)應(yīng)特征分類能力的降序序列.

WKNNFS 特征選擇方法的具體流程如下：

2 實(shí)驗(yàn)與性能分析

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

為驗(yàn)證WKNNFS 算法的正確性和有效性， 在6個(gè)數(shù)據(jù)集 Q_green、hcc-data2、Sonar、clean1、Prostate 和brain 上進(jìn)行實(shí)驗(yàn)，前4 個(gè)數(shù)據(jù)集下載自UCI 機(jī)器學(xué)習(xí)庫(kù)[22]，后2 個(gè)數(shù)據(jù)集下載自學(xué)習(xí)網(wǎng)站http：//ligarto.org/.實(shí)驗(yàn)中對(duì)這些數(shù)據(jù)均做了歸一化處理，所用數(shù)據(jù)集的具體描述見(jiàn)表1.

表1 數(shù)據(jù)集Tab.1 Datasets

2.2 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

使用PyCharm 集成開(kāi)發(fā)環(huán)境，對(duì)每個(gè)數(shù)據(jù)集進(jìn)行十重交叉檢驗(yàn).在以上6 個(gè)數(shù)據(jù)集上，將WKNNFS 與現(xiàn)有的3 種特征選擇方法MIFS、DISR 和CIFE 進(jìn)行比較，并使用K 近鄰、隨機(jī)森林、樸素貝葉斯、決策樹(shù)和支持向量機(jī)5 種分類器對(duì)每個(gè)方法所選擇的特征進(jìn)行分類預(yù)測(cè).實(shí)驗(yàn)中初始化種群包含80 個(gè)個(gè)體，迭代次數(shù)為260 次，交叉概率為0.8，變異概率為0.08.

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

實(shí)驗(yàn)所用數(shù)據(jù)集中部分是不平衡數(shù)據(jù)集，所以本文采用F1-measuer 指標(biāo)來(lái)衡量分類性能.F1-measure指標(biāo)綜合了精確度（precision）和召回率（recall），其定義為實(shí)驗(yàn)結(jié)果見(jiàn)圖1，圖中，橫坐標(biāo)表示選取前N 個(gè)特征，縱坐標(biāo)為選取前N 個(gè)特征后5 個(gè)分類器進(jìn)行分類預(yù)測(cè)得到的F1 的平均值.

由圖1 可見(jiàn)，WKNNFS 與其他3 種方法相比，不僅獲得的分類性能最高， 而且在多數(shù)情況下最快獲得了最高分類性能.在數(shù)據(jù)集Q_green、hcc-data2 和Sonar 上（圖1（a）～（c））， WKNNFS 相比另外 3 種方法能夠很快達(dá)到最高分類性能.在數(shù)據(jù)集clean1 上（圖1（d））， 當(dāng)選取前 N（N=1，2，…，20）個(gè)特征時(shí)， 4 種方法的分類性能相近，但隨著特征數(shù)的增加，WKNNFS的性能明顯優(yōu)于另外3 種方法.在數(shù)據(jù)集Prostate 和brain 上（圖1（e）～（f））， WKNNFS 達(dá)到最高分類性能的過(guò)程較慢， 這可能是因?yàn)檫@2 個(gè)數(shù)據(jù)集的維度較高.由圖1（a）和（b）可見(jiàn)， 4 種方法的分類性能達(dá)到最高后， 再增加所選特征數(shù)， 分類性能反而呈下降趨勢(shì)，這表明特征數(shù)過(guò)高可能會(huì)降低模型的分類性能.

表2 給出了在6 個(gè)數(shù)據(jù)集上4 種方法獲得的最高分類性能（F1）及其對(duì)應(yīng)的特征數(shù)（m）.每個(gè)數(shù)據(jù)集上的最高分類性能用粗體表示.

由表2 可見(jiàn)，在6 個(gè)數(shù)據(jù)集上WKNNFS 達(dá)到的最高分類性能均高于其他方法.當(dāng)達(dá)到最高分類性能時(shí)，WKNNFS 在所有數(shù)據(jù)集上都優(yōu)于CIFE 方法，即達(dá)到最高分類性能時(shí)選取的特征數(shù)較少.WKNNFS 與另外2 種方法相比，當(dāng)達(dá)到最高分類性能時(shí)，在4 個(gè)數(shù)據(jù)集（hcc-data2、Sonar、Prostate 和 brain）上選取的特征數(shù)較少，在數(shù)據(jù)集Q_green 上選取的特征數(shù)相差不大，而在數(shù)據(jù)集clean1 上選取的特征數(shù)較多，這可能是因?yàn)檫z傳算法在搜索最優(yōu)特征權(quán)重向量過(guò)程中陷入局部最優(yōu)， 而后又跳出局部最優(yōu)（由圖1（d）WKNNFS 的分類性能曲線可見(jiàn)，在N =13 和N =35附近曲線下降）.

圖1 4 種方法在不同數(shù)據(jù)集上F1 的平均值Fig.1 Mean of F1 on different datasets of 4 methods

表2 在6 個(gè)數(shù)據(jù)集上4 種方法的最高分類性能（F1）及對(duì)應(yīng)的特征數(shù)（m）Tab.2 Highest classification performances and the number of features selected of 4 methods on 6 datasets

3 結(jié)語(yǔ)

特征選擇是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域常用的降維技術(shù).本文提出了基于加權(quán)K 近鄰的特征選擇方法，同時(shí)使用遺傳算法搜索最優(yōu)特征權(quán)重向量，在6個(gè)真實(shí)數(shù)據(jù)集上與其他3 個(gè)特征選擇方法進(jìn)行比較實(shí)驗(yàn)，結(jié)果表明，WKNNFS 獲得的分類性能最高，且能較快獲得最高分類性能.在未來(lái)的工作中可以嘗試其他距離公式或遺傳算子， 以進(jìn)一步提高分類準(zhǔn)確率，降低預(yù)測(cè)誤差.