丁建立 劉濤 王家亮 曹衛(wèi)東

關(guān)鍵詞： K近鄰分類算法; 極端學(xué)習(xí)機(jī); 特征映射; 粒子群算法; 混合算法; 線性不可分

中圖分類號(hào)： TN911.1?34; TP181 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2019）05?0152?05

KNN classification algorithm based on PSO?ELM feature mapping

DING Jianli1， 2， LIU Tao1， WANG Jialiang1， 2， CAO Weidong1， 2

（1. College of Computer Science and Technology， Civil Aviation University of China， Tianjin 300300， China;

2. Tianjin Key Lab for Advanced Signal Processing， Civil Aviation University of China， Tianjin 300300， China）

Abstract： The K?nearest neighbor （KNN） classification algorithm based on PSO?ELM （particle swarm optimization?extreme learning machine） feature mapping is proposed because the traditional ELM algorithm and KNN classification algorithm have some shortcomings in classification process. The input?layer weight and hidden?layer neuron of ELM algorithm are used to perform the nonlinear mapping for the input sample. The PSO algorithm is used to find a group of optimal ELM mapping parameters， and then the mapped feature sample is input into KNN algorithm， which can improve the ability to deal with the linear impartibility problem. The experimental results of several data sets show that the proposed algorithm has higher classification accuracy than improved KNN algorithm and improved ELM algorithm.

Keywords： K?nearest neighbor classification algorithm; extreme learning machine; feature mapping; particle swarm optimization algorithm; hybrid algorithm; linear impartibility

0 ?引 ?言

K近鄰分類算法[1?2]（K?Nearest Neighbor，KNN）是一種簡單的分類算法，在數(shù)據(jù)挖掘等領(lǐng)域有著廣泛的應(yīng)用。作為一種有監(jiān)督的學(xué)習(xí)算法，使用投票機(jī)制確定未知樣本的類別，即給定一組有類別屬性的數(shù)據(jù)作為訓(xùn)練樣本，當(dāng)有新的未知類別樣本到來時(shí)，首先找到[K]個(gè)與未知樣本最為接近的訓(xùn)練樣本，在[K]個(gè)與未知樣本最接近的訓(xùn)練樣本標(biāo)簽中，出現(xiàn)次數(shù)最多的標(biāo)簽就是未知樣本所屬的類別標(biāo)簽。

從KNN算法的原理[3]可以總結(jié)出，該算法有兩個(gè)關(guān)鍵因素需要考慮，即[K]值的設(shè)定和距離度量。[K]值的選取對(duì)于該算法分類的正確率有著重要作用。如果[K]值太小，則分類結(jié)果容易受到噪聲樣本影響;如果[K]值太大，樣本數(shù)較少，類別會(huì)受到影響。其次是距離度量，常用的距離度量方法如歐氏距離和余弦距離等，不同距離度量的選擇對(duì)于分類結(jié)果也產(chǎn)生了很大的影響。

極端學(xué)習(xí)機(jī)算法[4?7]（Extreme Learning Machine，ELM）是由Huang等提出來的一種單隱層前向反饋神經(jīng)網(wǎng)絡(luò)（Single Hidden Layer Feed Forward Neural Networks，SLFN）。該算法與一般的SLFN算法相比，可以隨意地選擇隱層神經(jīng)元數(shù)目和激活函數(shù)類型，構(gòu)造不同的網(wǎng)絡(luò)結(jié)構(gòu)，隱層偏差和輸入層權(quán)值可以隨機(jī)產(chǎn)生，再利用輸出層期望使用最小二乘法計(jì)算輸出層權(quán)值。該算法具有計(jì)算速度快、泛化能力好等優(yōu)點(diǎn)，避免了傳統(tǒng)神經(jīng)網(wǎng)絡(luò)使用梯度算法計(jì)算時(shí)間長，容易陷入局部最優(yōu)解的問題。目前在系統(tǒng)辨識(shí)、模式識(shí)別、函數(shù)逼近等方面具有廣泛的應(yīng)用。由于輸入層權(quán)值和隱層偏差是隨機(jī)生成的，該算法通常需要數(shù)目較多的神經(jīng)元才能保證有較好的泛化能力和穩(wěn)定性。同時(shí)由于輸出層權(quán)值矩陣由隱含層輸出矩陣的廣義Moore?Pennose逆矩陣求出，當(dāng)隱含層節(jié)點(diǎn)數(shù)目過多時(shí)容易出現(xiàn)過擬合現(xiàn)象，降低ELM的泛化能力。對(duì)待線性不可分的樣本[8?10]，使用常用的歐氏距離和余弦距離來計(jì)算樣本相似程度進(jìn)行分類可能會(huì)導(dǎo)致效果很不理想。KNN算法在處理線性不可分問題時(shí)，可能會(huì)得到很差的分類效果。為了解決這類問題，可以將樣本進(jìn)行特征映射，從低維特征空間映射到高維特征空間中，從而將線性不可分問題轉(zhuǎn)化為線性可分問題，再使用傳統(tǒng)的距離算法計(jì)算樣本間的距離，從而提高分類正確率。

文獻(xiàn)[11]提出ELM K?means算法，使用ELM算法進(jìn)行特征映射，再將映射后的樣本特征指標(biāo)輸入到聚類算法中，取得了良好的效果。隨后文獻(xiàn)[12]又提出基于ELM特征映射的KNN算法。上述算法在利用ELM做特征映射時(shí)都存在穩(wěn)定性較差，需要大量神經(jīng)元即需要映射的維度極高等缺點(diǎn)。

針對(duì)ELM?KNN存在的問題，本文提出使用PSO?ELM特征映射的KNN算法。該算法利用ELM的輸入層權(quán)值和隱層對(duì)輸入樣本進(jìn)行特征映射，并運(yùn)用PSO算法尋找一組最優(yōu)的ELM輸入層權(quán)值和隱層偏差，再將映射后的樣本特征指標(biāo)輸入到KNN算法中，提高處理分類問題的能力。

1 ?ELM?KNN算法

設(shè)輸入樣本數(shù)據(jù)為[n]維向量[x=[x1，x2，…，xn]T]，通過一個(gè)ELM的輸入權(quán)值和隱層神經(jīng)元將[x]映射到一個(gè)[N]維的ELM特征空間（即隱層特征空間，[N]為隱層節(jié)點(diǎn)個(gè)數(shù)，也是新特征空間的維度），[x]在特征空間中對(duì)應(yīng)的特征向量為：

[h（x）=[h1（x），h2（x），…，hN（x）]T=[G（ω1*x+b1），G（ω2*x+b2），…，G（ωN*x+bN）]T] （1）

式中：[Gωi*x+bi]為隱層節(jié)點(diǎn)的輸出，[ωi]為連接[n]個(gè)輸入節(jié)點(diǎn)和第[i]個(gè)隱層節(jié)點(diǎn)的[N]維權(quán)重向量;[bi]為第[i]個(gè)隱層節(jié)點(diǎn)的偏差。由于[ωi]和[bii=1，2，…，N]是隨機(jī)生成的，無需計(jì)算和調(diào)整，在特征映射過程中只需要人為調(diào)整隱層節(jié)點(diǎn)個(gè)數(shù)，再將映射后的樣本[h（x）]作為新的特征樣本輸入到KNN算法中，計(jì)算待分類樣本所屬的類別。

由于隱藏偏差和輸入層權(quán)值隨機(jī)生成導(dǎo)致ELM?KNN在計(jì)算時(shí)往往需要映射到一千維以上才能保證較高的分類和穩(wěn)定性。這導(dǎo)致算法實(shí)用性較差，往往需要計(jì)算很多次才能得到理想的結(jié)果。

2 ?粒子群算法

粒子群算法[13]（Particle Swarm Optimization，PSO）是一種模仿鳥類捕食行為的智能優(yōu)化算法。在算法初始階段隨機(jī)生成一組隨機(jī)解，然后通過一定規(guī)律迭代地尋找最優(yōu)解。不同于遺傳算法使用交叉以及變異尋找最優(yōu)解，該算法的迭代策略是解空間朝著最優(yōu)一組解空間的方向進(jìn)行更新。同現(xiàn)行的其他智能優(yōu)化算法相比，該算法具有收斂速度快，不易陷入局部最優(yōu)解，算法簡單，參數(shù)設(shè)置少等特點(diǎn)。目前PSO算法已廣泛應(yīng)用到如函數(shù)優(yōu)化、參數(shù)估計(jì)、模型改進(jìn)、模糊系統(tǒng)控制等眾多領(lǐng)域。

在PSO中，每一個(gè)粒子代表空間中的一點(diǎn)，其對(duì)應(yīng)的空間坐標(biāo)代表該問題的一組解，記為[Xi=xi1，xi2，…，xiD]，可以利用適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度，同時(shí)每個(gè)粒子還有一個(gè)速度屬性[Vi=vi1，vi2，…，viD]，用來決定它們的方向和距離。粒子之間通過共享最優(yōu)粒子的信息在解空間中搜索最優(yōu)解。

粒子群首先計(jì)算每個(gè)粒子的適應(yīng)度fitness，選擇適應(yīng)度最優(yōu)的點(diǎn)，讓其他所有點(diǎn)朝著最優(yōu)點(diǎn)移動(dòng)，以此迭代尋找最優(yōu)解。在每次迭代過程中，粒子先朝著當(dāng)前最優(yōu)解更新速度，然后更新當(dāng)前位置。

粒子更新速度的公式為：

[vid=vid+c1?rand（pid-xid）+c2?rand（pgd-xid）] ?（2）

粒子更新位置的公式為：

[xid=xid+vid] （3）

式中：[Pi=pi1，pi2，…，piD]，表示第[i]個(gè)粒子的局部最優(yōu)解，即第[i]個(gè)粒子每次迭代到目前為止經(jīng)歷過的最佳點(diǎn);[Pg=pg1，pg2，…，pgD]，表示所有粒子群的最優(yōu)解，即目前為止粒子群所搜索到的適應(yīng)度最優(yōu)的解;[c1]和[c2]是學(xué)習(xí)因子，為大于零的常數(shù);[rand]表示在[0，1]生成隨機(jī)數(shù)。

3 ?基于PSO?ELM特征映射的KNN算法

為了改進(jìn)ELM?KNN算法的不足，本文提出一種基于PSO?ELM特征映射的KNN算法。該算法利用PSO尋優(yōu)策略代替ELM算法輸入層權(quán)值和隱層偏差隨機(jī)生成的過程。利用優(yōu)化后的ELM輸入層和隱層激活函數(shù)對(duì)樣本進(jìn)行特征映射，再將映射后的特征樣本輸入到KNN算法中進(jìn)行分類。

從ELM算法角度，本文算法有以下幾個(gè)方面的改進(jìn)：

1） 本文算法利用PSO尋優(yōu)策略代替了ELM算法輸出層權(quán)值和隱層偏差隨機(jī)生成的過程，避免了該算法輸出層權(quán)值和隱層偏差隨機(jī)生成導(dǎo)致的消耗神經(jīng)元數(shù)目過多、結(jié)果穩(wěn)定性差等缺點(diǎn)。

2） ELM算法輸出層的權(quán)值是利用最小二乘法計(jì)算得到的，ELM算法在對(duì)樣本進(jìn)行特征映射以后只是將映射后的特征樣本進(jìn)行加權(quán)求和，從而計(jì)算每個(gè)樣本的類別。利用KNN算法的投票機(jī)制代替這一過程，從而可以有效避免其容易出現(xiàn)的過擬合問題。

3） 從KNN算法的角度，對(duì)于傳統(tǒng)KNN算法的距離度量的不足進(jìn)行了改進(jìn)。利用PSO?ELM進(jìn)行特征映射提高了該算法處理線性不可分問題的能力。另外，特征映射的使用還能夠起到消除冗余信息，提取特征信息的作用。

具體算法如下：

對(duì)于給定[n]維輸入樣本[x=[x1，x2，…，xn]T]，首先利用粒子群算法隨機(jī)生成一組輸入層權(quán)值[ωi]和隱藏偏差[bi]，通過具有[N]個(gè)隱層神經(jīng)元、激活函數(shù)為[G（x）]的ELM對(duì)樣本進(jìn)行特征映射后的特征向量為：

[h（x）=[h1（x），h2（x），…，hN（x）]T=[G（ω1*x+b1），G（ω2*x+b2），…，G（ωN*x+bN）]T]

式中：[Gωi*x+bi]為隱層節(jié)點(diǎn)的輸出，[ωi]為連接[n]個(gè)輸入節(jié)點(diǎn)和第[i]個(gè)隱層節(jié)點(diǎn)的[N]維權(quán)重向量;[bi]為第[i]個(gè)隱層節(jié)點(diǎn)的偏差。常用的激勵(lì)函數(shù)有Hardlim函數(shù)、Sigmoid函數(shù)、Sine函數(shù)等。

ELM特征映射示意圖如圖1所示。

再將特征變化后的[h（x）]輸入到KNN算法中，計(jì)算樣本分類的正確率。分類正確率計(jì)算方法如下：

[正確率=分類正確樣本數(shù)樣本總數(shù)×100%] （4）

將分類正確率作為適應(yīng)度fitness返回給粒子群算法，作為每一個(gè)粒子的適應(yīng)度。通過PSO多次迭代，獲得使分類正確率最高的一組輸入層權(quán)值[ωi]和隱層偏差[bi]。

算法步驟如下：

1） 隨機(jī)生成粒子群，每一個(gè)粒子群的位置坐標(biāo)代表ELM輸入層權(quán)值[ωi]和隱層偏差[bi];

2） 依次選擇各個(gè)粒子，利用式（1）對(duì)輸入樣本[xi] 做特征映射得到[h（x）]，將[h（x）]作為新的樣本輸入到KNN中，并計(jì)算分類正確率作為對(duì)應(yīng)粒子的適應(yīng)度;

3） 根據(jù)適應(yīng)度更新每一個(gè)粒子的局部最優(yōu)解[Pi]和全局最優(yōu)解[Pg];

4） 根據(jù)式（2）和式（3）更新每一個(gè)粒子的速度和位置;

5） 判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到最大迭代次數(shù)，則輸出最優(yōu)的粒子位置即最優(yōu)的輸入層權(quán)值[ωi]和隱藏[bi]以及分類正確率，否則返回步驟2）。

4 ?計(jì)算機(jī)仿真結(jié)果與分析

實(shí)驗(yàn)環(huán)境為2.5 GHz CPU的Matlab 2015b。為了方便對(duì)比和討論，設(shè)定PSO算法的迭代次數(shù)為20次[14]（在不同輸入數(shù)據(jù)維度和隱層神經(jīng)元節(jié)點(diǎn)的情況下，粒子群算法在20次之前就能很好地收斂到一個(gè)穩(wěn)定的狀態(tài)，因此設(shè)定最大的迭代次數(shù)為20次），種群個(gè)體數(shù)為200，慣性權(quán)重[ω]為0.798，學(xué)習(xí)因子[c1]，[c2]為1.496 1。本文算法中統(tǒng)一使用的距離度量為歐氏距離，激活函數(shù)為Sigmoid函數(shù)。

仿真所使用的數(shù)據(jù)來源于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫[9]的鳶尾花數(shù)據(jù)集（iris），糖尿病數(shù)據(jù)集（diabetes），乳腺癌數(shù)據(jù)集（breast disease），葡萄酒數(shù)據(jù)集（wine）。上述數(shù)據(jù)集被廣泛應(yīng)用于機(jī)器學(xué)習(xí)算法的測試。為了使算法更具有普遍性，使用十折交叉驗(yàn)證的方式進(jìn)行計(jì)算，最后保留所有結(jié)果的平均值。數(shù)據(jù)的屬性描述如表1所示。

PSO?ELM?KNN算法、ELM算法以及PSO?ELM算法的分類正確率如表3所示。設(shè)定神經(jīng)元個(gè)數(shù)為5個(gè)，[K]的個(gè)數(shù)為5。

以breast disease為例，計(jì)算PSO?ELM?KNN算法和ELM?KNN算法在不同神經(jīng)元個(gè)數(shù)的情況下運(yùn)行10次的分類正確率以及分類正確率方差變化情況，如圖2，圖3所示。

通過表2可以發(fā)現(xiàn)，PSO?ELM?KNN算法分類正確率明顯高于KNN算法以及ELM?KNN算法。在選取不同[K]值時(shí)，KNN和ELM?KNN算法分類正確率會(huì)產(chǎn)生一定的影響，而本文算法在[K]大于5時(shí)，正確率基本保持不變，不會(huì)隨著[K]的變化而對(duì)正確率產(chǎn)生影響。在表3的4個(gè)數(shù)據(jù)集中，PSO?ELM?KNN分類正確率明顯高于ELM算法和PSO?ELM算法。通過圖2，圖3可以發(fā)現(xiàn)，隨著特征空間維度的增加，ELM?KNN算法的分類正確率不斷增加，達(dá)到400維度以上時(shí)其分類正確率趨于一個(gè)穩(wěn)定的值。而PSO?ELM?KNN算法在特征空間維度很小時(shí)就能達(dá)到很高的分類正確率。

通過以上結(jié)果分析，可得到以下結(jié)論：

1） 本文算法的分類精確度高于其他算法。在多個(gè)數(shù)據(jù)集下實(shí)驗(yàn)得到的結(jié)果均顯示PSO?ELM?KNN算法分類正確率高于KNN算法、ELM算法以及以上算法的組合。

2） 本文算法避免了[K]的確定過程。對(duì)于KNN算法以及ELM?KNN算法在不同數(shù)據(jù)集下，選取不同[K]值會(huì)產(chǎn)生不同的影響。針對(duì)[K]值選取往往需要多次實(shí)驗(yàn)，確定合適的[K]值。本文算法通過特征非線性映射，避免了[K]值變化產(chǎn)生的影響。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，[K]值很小時(shí)即能達(dá)到很好的效果。

3） 本文算法需要映射的特征空間維度不需要太大，即需要的神經(jīng)元個(gè)數(shù)較少。由于輸入層權(quán)值和隱層偏差隨機(jī)生成，ELM算法和ELM?KNN算法需要1 000個(gè)左右的神經(jīng)元才能達(dá)到較高的穩(wěn)定性和分類正確率。而PSO?ELM?KNN算法在維度為10時(shí)就能到達(dá)到很好的分類精確度以及穩(wěn)定性，極大地降低了分類的時(shí)間復(fù)雜度。

5 ?結(jié) ?語

本文提出PSO?ELM特征映射的KNN算法，并與ELM算法、KNN算法以及ELM?KNN算法的改進(jìn)進(jìn)行對(duì)比。該算法改善了ELM算法對(duì)樣本進(jìn)行特征非線性映射時(shí)的不足，以及[K]值和神經(jīng)元個(gè)數(shù)選擇的問題，提高了處理非線性問題分類正確率和算法的實(shí)用性。

參考文獻(xiàn)

[1] 張昊，陶然，李志勇，等.基于KNN算法及禁忌搜索算法的特征選擇方法在入侵檢測中的應(yīng)用研究[J].電子學(xué)報(bào)，2009，37（7）：1628?1632.

ZHANG Hao， TAO Ran， LI Zhiyong， et al. A research and application of feature selection based on KNN and Tabu search algorithm in the intrusion detection [J]. Acta electronica Sinica， 2009， 37（7）： 1628?1632.

[2] 周英，卓金武，卞月青.大數(shù)據(jù)挖掘[M].北京：機(jī)械工業(yè)出版社，2016.

ZHOU Ying， ZHUO Jinwu， BIAN Yueqing. Big data mining [M]. Beijing： China Machine Press， 2016.

[3] GUO G， WANG H， BELL D， et al. KNN model?based approach in classification [C]// 2003 International Conference on the Move to Meaningful Internet Systems. [S.l.]： Springer， 2003： 986?996.

[4] HUANG G B， ZHU Q Y， SIEW C K. Extreme learning machine： theory and applications [J]. Neurocomputing， 2006， 70（1/3）： 489?501.

[5] HUANG G B， ZHOU H， DING X， et al. Extreme learning machine for regression and multiclass classification [J]. IEEE transactions on systems， man & cybernetics， 2012， 42（2）： 513?529.

[6] 李彬，李貽斌.基于ELM學(xué)習(xí)算法的混沌時(shí)間序列預(yù)測[J].天津大學(xué)學(xué)報(bào)，2011，44（8）：701?704.

LI Bin， LI Yibin. Chaotic time series prediction based on ELM learning algorithm [J]. Journal of Tianjin University， 2011， 44（8）： 701?704.

[7] MART?NEZ J M， ESCANDELL?MONTERO P， SORIA OLIVAS E， et al. Regularized extreme leaning machine for regression problems [J]. Neurocomputing， 2011， 74（17）： 3716?3721.

[8] YU K， LIANG J， ZHANG X. Kernel nearest neighbor algorithm [J]. Neural processing letters， 2002， 15（2）： 147?156.

[9] SHAWE?TAYLOR J， CRISTIANINI N. Kernel method for pattern analysis [M]. New York： Cambridge University Press， 2004.

[10] CAMASTRA F， VERRI A. A novel kernel method for cluste?ring [J]. IEEE transactions on pattern analysis and machine intelligence， 2005， 27（5）： 245?250.

[11] ALSHAMIRI A K， SURAMPUDI B R， SINGH A. A novel ELM K?Means algorithm for clustering [C]// 2014 International Conference on Swarm， Evolutionary， and Memetic Compu?ting. Switzerland： Springer， 2015： 212?222.

[12] 盧誠波，林銀河，梅穎.基于ELM特征映射的KNN算法[J].復(fù)旦學(xué)報(bào)（自然科學(xué)版），2016，55（5）：570?575.

LU Chengbo， LIN Yinhe， MEI Ying. KNN based on extreme learning machine feature mapping [J]. Journal of Fudan University （natural science）， 2016， 55（5）： 570?575.

[13] SARASWATHI S. ICGA?PSO?ELM approach for accurate multiclass cancer classification resulting in reduced gene sets in which genes encoding secreted proteins are highly represented [J]. IEEE/ACM transactions on computational biology and bioinformatics， 2011， 8（2）： 452?463.

[14] UCI. UCI machine learning database [DB/OL]. [2012?04?23]. http：//archive.ics.uci.edu/ml/datasets.html.