基于K 近鄰和粒子群優(yōu)化的特征選擇算法

鐘昌康

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識(shí)別和信號(hào)處理等許多領(lǐng)域中，經(jīng)常需要處理包含大量特征的數(shù)據(jù)集。在這種情況下，對(duì)數(shù)據(jù)進(jìn)行降維預(yù)處理能大大提升學(xué)習(xí)算法的訓(xùn)練速度和性能。特征選擇是數(shù)據(jù)降維領(lǐng)域中的重要方法。特征選擇是從給定數(shù)據(jù)的原始特征集中選擇特征子集的過(guò)程，通過(guò)特征選擇算法選出的特征子集應(yīng)該能盡量的表示原始特征集的特性。特征選擇的重要性在于減小特征集合的大小并減少學(xué)習(xí)算法的搜索空間。在模式分類器的設(shè)計(jì)中，特征選擇可以提高分類精度和并加快模型訓(xùn)練速度。

特征選擇過(guò)程包含兩個(gè)基本步驟：①評(píng)估特征或特征子集的優(yōu)劣；②在特征空間搜索最優(yōu)特征子集[1]。目前已經(jīng)有許多基于統(tǒng)計(jì)學(xué)和數(shù)學(xué)特征的評(píng)估措施以及搜索技術(shù)用于特征選擇領(lǐng)域。特征選擇領(lǐng)域?qū)W者們已經(jīng)開(kāi)發(fā)了許多有效的特征選擇算法，其中包括評(píng)估函數(shù)和搜索策略的各種組合。但是，統(tǒng)計(jì)方法的計(jì)算復(fù)雜度會(huì)隨特征維度的增加而成指數(shù)增加。所以在現(xiàn)實(shí)應(yīng)用中，統(tǒng)計(jì)方法不太適用。近年來(lái)，諸如人工神經(jīng)網(wǎng)絡(luò)、模糊集和粗糙集之類的軟計(jì)算工具被廣泛用于特征子集的評(píng)估，而遺傳算法、粒子群優(yōu)化等進(jìn)化算法因?yàn)榫哂辛己玫娜炙阉髂芰Χ蛔C明對(duì)于搜索最優(yōu)特征子集的問(wèn)題是有效的。

特征選擇算法分為三種類型：①過(guò)濾器方法；②包裝器方法；③嵌入式或混合方法。在濾波方法中，特征子集的優(yōu)劣是通過(guò)某些基于數(shù)據(jù)集的指標(biāo)來(lái)評(píng)估的，整個(gè)評(píng)估過(guò)程不涉及任何的學(xué)習(xí)算法。濾波方法往往需要較少的計(jì)算資源，但這種方法沒(méi)有考慮特征對(duì)于最終的學(xué)習(xí)任務(wù)的影響，并且特征之間的相互作用可能會(huì)被忽視。包裝器方法將學(xué)習(xí)算法的精度作為評(píng)估特征子集的指標(biāo)。包裝器方法選擇與分類算法相關(guān)的特征，能得到更高的分類準(zhǔn)確率，但是由于每次評(píng)估特征子集時(shí)都需要訓(xùn)練分類器，因此包裝器方法的計(jì)算量通常很大。嵌入式特征選擇算法嵌入在學(xué)習(xí)算法當(dāng)中，當(dāng)分類算法訓(xùn)練過(guò)程結(jié)束就可以得到特征子集。

在本文中，我們將K 近鄰算法和粒子群算法結(jié)合，提出了一個(gè)基于K 近鄰和離散粒子群優(yōu)化的特征選擇算法，K 近鄰算法用于評(píng)估特征子集的優(yōu)劣，擁有良好全局搜索能力的群體智能算法粒子群算法將用于在特征空間中搜索最優(yōu)特征子集，本文所提算法在5 個(gè)UCI 數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)過(guò)后表明能有效降低數(shù)據(jù)維度并提高分類精度。

1 預(yù)備知識(shí)

1.1 粒子群優(yōu)化算法

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法[2]是Kennedy 和Eberhart 受人工生命研究結(jié)果的啟發(fā)、通過(guò)模擬鳥群覓食過(guò)程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機(jī)搜索算法。粒子群算法在對(duì)動(dòng)物集群活動(dòng)行為觀察基礎(chǔ)上，利用群體中的個(gè)體對(duì)信息的共享使整個(gè)群體的運(yùn)動(dòng)在問(wèn)題求解空間中產(chǎn)生從無(wú)序到有序的演化過(guò)程，從而獲得最優(yōu)解。

在粒子群算法中，鳥被抽象為一個(gè)個(gè)的粒子，每一個(gè)粒子有自己的位置和速度，對(duì)于一個(gè)N 維優(yōu)化問(wèn)題，若粒子群的規(guī)模為M，則粒子i,( 0 ＜i ≤M )在N 維空間的位置表示為Xi=(x1,x2,x3,…,xN)，飛行速度表示為矢量Vi=( v1,v2,v3,…,vN)。每個(gè)粒子都有一個(gè)由目標(biāo)函數(shù)決定的適應(yīng)值，并且知道自己到目前為止發(fā)現(xiàn)的最好位置（pbest）和現(xiàn)在的位置Xi。這個(gè)可以看作是粒子自己的飛行經(jīng)驗(yàn)。除此之外，每個(gè)粒子還知道到目前為止整個(gè)群體中所有粒子發(fā)現(xiàn)的最好位置（gbest）（gbest 是pbest 中的最好值），這個(gè)可以看作是粒子同伴的經(jīng)驗(yàn)。粒子就是通過(guò)自己的經(jīng)驗(yàn)和同伴中最好的經(jīng)驗(yàn)來(lái)決定下一步的運(yùn)動(dòng)[6]。

粒子按照以下公式進(jìn)行速度和位置的更新：

其中? 叫做慣性因子，反映了粒子的運(yùn)動(dòng)習(xí)慣，代表粒子有維持自己先前速度的趨勢(shì)，當(dāng)? 較大時(shí)，算法的全局搜索能力較強(qiáng)，局部搜索能力較弱[4]。當(dāng)? 較小時(shí)，算法的全局搜索能力較弱，局部搜索能力較強(qiáng)。其中c1 和c2 為學(xué)習(xí)因子，也稱加速常數(shù)，代表了粒子向自己的最優(yōu)經(jīng)驗(yàn)學(xué)習(xí)和向所有粒子的最優(yōu)學(xué)習(xí)的趨勢(shì)，通過(guò)調(diào)整c1 和c2 可以平衡算法的探索和挖掘能力。第二部分為粒子的認(rèn)知部分，反映了粒子對(duì)自身歷史經(jīng)驗(yàn)的記憶，代表粒子有向自身歷史最佳位置逼近的趨勢(shì)；第三部分為社會(huì)部分，反映了粒子間協(xié)同合作與知識(shí)共享的群體歷史經(jīng)驗(yàn)，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢(shì)。rand（）是在0 到1 之間的兩個(gè)隨機(jī)數(shù)。

1.2 K近鄰算法

K 近鄰學(xué)習(xí)[3]是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中一種常見(jiàn)的監(jiān)督學(xué)習(xí)方法，其工作機(jī)制非常簡(jiǎn)單。在給定訓(xùn)練樣本后，基于某種度量找出訓(xùn)練集與測(cè)試集中最接近的K 個(gè)樣本，即所謂的K 個(gè)鄰居來(lái)預(yù)測(cè)樣本類別。度量通常使用標(biāo)準(zhǔn)歐氏距離，其公式如下：

K 近鄰的算法描述為：

（1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離；

（2）按照距離的遞增關(guān)系進(jìn)行排序；

（3）選取距離最小的K 個(gè)點(diǎn)；

（4）確定前K 個(gè)點(diǎn)所在類別的出現(xiàn)頻率；

（5）返回前K 個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類。

2 基于K近鄰和粒子群優(yōu)化的特征選擇算法

我們可以將PSO 的思想用于最佳特征選擇問(wèn)題。考慮一個(gè)充滿特征子集的大型特征空間。每個(gè)特征子集都可以看作是此類空間中的一個(gè)點(diǎn)或位置。如果數(shù)據(jù)集總共有N 個(gè)特征，則將有2N個(gè)特征子集，每個(gè)子集包含的特征數(shù)量和特征互不相同。最佳特征子集是特征數(shù)目最小，并且能使得基于該特征集訓(xùn)練出的分類器分類質(zhì)量最高。現(xiàn)在我們將一個(gè)粒子群放入這個(gè)特征空間，每個(gè)粒子占據(jù)一個(gè)位置。粒子在此空間中飛行，它們的目標(biāo)是飛行到最佳位置。隨著時(shí)間的流逝，他們會(huì)改變自己的位置，彼此交流，并在本地最佳和群體最佳位置附近搜尋。最終，他們應(yīng)該集中在良好的，也有可能是最佳的位置上。粒子群的這種探索能力可以使其具備執(zhí)行特征選擇和發(fā)現(xiàn)最佳特征子集的能力。由于特征選擇是一個(gè)離散優(yōu)化問(wèn)題，所以在使用PSO 進(jìn)行特征選擇時(shí)，我們需要調(diào)整PSO 中的一些更新公式。

（1）粒子表示

我們將粒子的位置表示為長(zhǎng)度為N 的0,1 向量，其中N 是特征的總數(shù)。每一位代表一個(gè)特征，值“1”表示選擇了相應(yīng)的特征，而“0”代表對(duì)應(yīng)位置的特征沒(méi)有被選擇。每個(gè)粒子的位置都代表一個(gè)特征子集。初始化時(shí)，每個(gè)粒子的位置應(yīng)該在（0,1）之間。

其中xi=1 代表第i 個(gè)特征被選擇，否則代表第i個(gè)特征沒(méi)有被選擇。例如，X=(1,0,1,1,0)代表第一個(gè)、第三個(gè)、第四個(gè)特征被選擇。

（2）位置更新

粒子按照如下公式進(jìn)行位置更新：

其中r3是屬于（0,1）區(qū)間的一個(gè)隨機(jī)數(shù)，當(dāng)粒子的速度更新經(jīng)過(guò)指數(shù)函數(shù)處理后，粒子的速度大小就位于（0,1）之間，然后通過(guò)生成隨機(jī)數(shù)r3來(lái)決定粒子的下一步更新是變?yōu)? 還是0[5]。

（3）適應(yīng)度函數(shù)

為了平衡分類精度和特征數(shù)目，我們將適應(yīng)度函數(shù)定義為如下公式：

其中γR( D )在特征子集R 上訓(xùn)練出的分類器D 的分類精度，| R |是選擇出來(lái)的特征子集包含的特征的數(shù)目，|C |是原始特征集合中特征總數(shù)。α 和β 是用來(lái)調(diào)節(jié)分類精度和特征數(shù)目?jī)蓚€(gè)目標(biāo)函數(shù)比重的重要參數(shù)，α ∈( 0,1) 且β=1-α。

公式（4）代表分類質(zhì)量和特征子集長(zhǎng)度對(duì)于特征選擇任務(wù)具有不同的意義。在本文的實(shí)驗(yàn)中，我們假設(shè)分類質(zhì)量比子集長(zhǎng)度更重要，并設(shè)置α=0.9，β=0.1，α 的值較大可以使得選出的特征子集能最大程度的代表原始特征集合。每個(gè)特征子集都通過(guò)這個(gè)適應(yīng)度函數(shù)進(jìn)行評(píng)估，適應(yīng)度函數(shù)值越大代表特征子集越優(yōu)。

算法整體流程如圖1 所示。

3 實(shí)驗(yàn)

為了驗(yàn)證本文所提出的算法的優(yōu)越性，我們從UCI 選取了5 個(gè)常用的數(shù)據(jù)集進(jìn)行算法實(shí)驗(yàn)，表1 給出了這些數(shù)據(jù)集的簡(jiǎn)要概括信息。這些數(shù)據(jù)集的特征數(shù)目從9 到60 不等，而且這些數(shù)據(jù)集的樣例數(shù)目也大小不一，從而能夠很好地檢驗(yàn)算法的在處理特征選擇問(wèn)題上的搜索能力。所有實(shí)驗(yàn)是在處理器為Intel Core i5-2320 3.00GHz 運(yùn)行內(nèi)存為6GB 的PC 上完成，最大迭代次數(shù)被設(shè)置為100，群體的數(shù)目被設(shè)置成10，慣性因子ω=0.5，c1=c2=2。適應(yīng)度函數(shù)中的α和β被分別設(shè)置為0.99 和0.1。另外，所有統(tǒng)計(jì)結(jié)果是在獨(dú)立運(yùn)行30 次之后得到的，問(wèn)題的維度和所對(duì)應(yīng)數(shù)據(jù)集的特征數(shù)目是相等的。對(duì)于每個(gè)數(shù)據(jù)集，我們將其分為訓(xùn)練集和測(cè)試集，80%作為訓(xùn)練集，20%作為測(cè)試集。KNN（k=5）被用來(lái)作為分類器用來(lái)評(píng)估所選出的特征子集的好壞。

圖1 算法整體框架

表1 使用數(shù)據(jù)集

從表2 的結(jié)果可以看出，通過(guò)使用PSO 對(duì)特征進(jìn)行選擇之后分類精度相比于使用全部特征訓(xùn)練的KNN有很大的提升，通過(guò)圖2 我們可以看出特征選擇并不意味著特征越少越好，從圖2 的第三個(gè)小圖我們可以看到，當(dāng)算法在處理HeartEW 這個(gè)數(shù)據(jù)集的時(shí)候，最后選擇的特征數(shù)目為9，而不是一開(kāi)始算法就達(dá)到的5 個(gè)特征，這是因?yàn)檫m應(yīng)度函數(shù)平衡了特征數(shù)目和分類精度兩個(gè)目標(biāo)，所以算法會(huì)在最終迭代結(jié)束時(shí)用較少的特征爭(zhēng)取得到更高的分類精度。而且由圖2 中的第一個(gè)小圖我們可以看出，特征選擇可以在減少特征的同時(shí)得到更高的分類精度，當(dāng)算法在處理Breastcancer 這個(gè)數(shù)據(jù)集的時(shí)候，在第十九次迭代的時(shí)候，算法選擇的特征由8 個(gè)降低到了7 個(gè)，但是分類器的準(zhǔn)確率卻從96.5%提升到了97.1%。綜上所述，通過(guò)特征選擇可以有效降低數(shù)據(jù)維度，提高算法性能。

表2 實(shí)驗(yàn)結(jié)果

圖2 基于K近鄰和粒子群優(yōu)化的特征選擇算法的特征選擇過(guò)程圖

4 結(jié)語(yǔ)

在本文中，我們以粒子群優(yōu)化為搜索算法，以K 近鄰算法作為評(píng)估方法，提出了一種包裝器式的特征選擇方法，該方法以分類精度和特征子集的大小的綜合評(píng)判作為評(píng)估函數(shù)，將兩個(gè)目標(biāo)函數(shù)統(tǒng)一在一個(gè)目標(biāo)函數(shù)里。在將粒子群用于特征選擇之前，需要一些離散化算法來(lái)離散化數(shù)據(jù)。我們?cè)? 個(gè)UCI 基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)表明，該算法可以有效降低特征數(shù)量并提高分類器分類精度，與使用全部特征訓(xùn)練的K 近鄰算法相比，分類準(zhǔn)確率也有較大提升。未來(lái)工作可以使用更廣泛的數(shù)據(jù)集檢查算法的效率，使用不同的分類器對(duì)所選特征子集進(jìn)行分類的準(zhǔn)確性，采用不同的評(píng)估方法和搜索算法的組合。