基于ELM特征映射的kNN算法

盧誠波，林銀河，梅 穎

(麗水學院工學院，麗水323000)

?

基于ELM特征映射的kNN算法

盧誠波，林銀河，梅 穎

(麗水學院工學院，麗水323000)

研究了基于ELM特征映射的kNN算法，利用ELM特征映射，將原始數(shù)據(jù)映射到這種高維特征空間當中，使得數(shù)據(jù)間變得更加線性可分，即數(shù)據(jù)結(jié)構(gòu)會變得簡單，因此，在利用kNN算法進行分類時，利用ELM特征空間中對應的特征數(shù)據(jù)代替原始空間中的數(shù)據(jù)進行分類將會取得更好的分類效果.最后，來自MNIST和UCI中的幾個數(shù)據(jù)集的仿真實驗進一步驗證了該算法的優(yōu)良性能.

超限學習機；k最近鄰算法；特征空間；分類

由Cover和Hart提出的k最近鄰(k-Nearest Neighbor，kNN)算法[1]是最著名的模式識別和統(tǒng)計學方法之一.kNN算法的核心思想是如果一個樣本的k個最鄰近的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性.該方法在確定分類決策上只依據(jù)最鄰近的一個或者幾個樣本的主要分類來決定新數(shù)據(jù)的類別，因此被稱為最近鄰算法.kNN算法在類別決策時，只與極少量的相鄰樣本有關(guān).由于kNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別，因此對于類域的交叉或重疊較多的待分樣本集來說，kNN算法較其他方法更為適合.kNN算法思路簡單，易于實現(xiàn)，因此在模式識別、文本分類、圖形圖像等領域被經(jīng)常使用.

kNN算法需解決的問題主要有：1)近鄰數(shù)k的取值問題，k值選取的合理與否直接關(guān)系到算法的結(jié)果，因此，一些研究者開始研究k值的選取方法以取代個人的經(jīng)驗選擇[2-3]；2)如何根據(jù)實際問題選擇更合適的相似度函數(shù)[4-5]；3)kNN算法在對屬性較多即維數(shù)較高的訓練樣本進行分類時，由于計算量大而使其效率降低，效果不是很理想，因此涌現(xiàn)了一些針對性的解決方案[6-7]；4)如何對原始數(shù)據(jù)進行預處理，例如使線性不可分的樣本轉(zhuǎn)化為線性可分，從而更利于kNN算法進行分類.

本文主要的思想是利用ELM特征映射算法將低維輸入空間中復雜線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得kNN算法在高維特征空間中的分類精確度得到進一步提高.

下面首先簡單介紹ELM算法.

1 ELM算法

ELM算法是一種被稱為“超限學習機(Extreme Learning Machine，ELM)”的單隱層前饋神經(jīng)網(wǎng)絡學習算法的簡稱[8-9]，基本思想如下：

對于輸入向量x∈n,具有個隱層節(jié)點的單隱層前饋神經(jīng)網(wǎng)絡的輸出值可表示為：

其中：wi∈n是連接第i個隱層節(jié)點的輸入權(quán)值;βi∈m是連接第i個隱層節(jié)點的輸出權(quán)值;bi是第i個隱層節(jié)點的偏置；G(wi,bi,x)為第i個隱層節(jié)點的輸出，激勵函數(shù)G可以是任意有界的非常量連續(xù)函數(shù)，大部分非線性分段連續(xù)函數(shù)都可以用來當作激勵函數(shù)[8]，常用的激勵函數(shù)如Gaussian函數(shù)、Sigmoidal函數(shù)、Sine函數(shù)等.

設分別有N個輸入模式向量x1,x2,…,xN(其中xi∈)和N個對應的期望輸出向量t1,t2,…,tN(其中ti∈m)，這N個輸入模式向量的實際輸出向量o1,o2,…,oN(其中oi∈m)表示為：

Hβ=O,

(1)

其中：

(2)

令O=T, 這里T=[t1,t2,…,tN]T, 則式(1)可寫為：

Hβ=T,

(3)

通過解(3)式的方程，即可得到輸出權(quán)矩陣

β=H+T,

其中H+為矩陣H的Moor-Penrose廣義逆.

在ELM算法中，輸入權(quán)和偏置為隨機給定，輸出權(quán)通過最小二乘法計算得到，整個訓練過程一次完成，不需要迭代.由于ELM算法與已知的一些算法相比，訓練速度要快得多，且具有更好的泛化性，并且人為干預少，因此被廣泛地應用，特別是在各種分類和回歸問題中[10-14].

圖1為一個輸入權(quán)和隱層偏置為隨機數(shù)的單隱層前饋神經(jīng)網(wǎng)絡(Single-hidden Layer Feedforward Neural Network, SLFN).

2 ELM特征空間中的kNN算法

由于通過非線性轉(zhuǎn)化，數(shù)據(jù)在高維特征空間中將會變得更加線性可分，數(shù)據(jù)結(jié)構(gòu)變得相對簡單，也就更易于分類，因此，一些核方法開始被用來作特征映射，如支持向量機(Support Vector Machine，SVM)，通過一個非線性映射，把樣本空間映射到一個高維乃至無窮維的特征空間中(Hilbert空間)，使得在原來的樣本空間中非線性可分的問題轉(zhuǎn)化為在特征空間中的線性可分的問題．ELM不僅在學習速度上要比傳統(tǒng)的SVM快得多，而且在許多時候擴展性和泛化性都要好于SVM[9]，文獻[11]證明了SVM的最大分離邊際與ELM的輸出權(quán)最小范數(shù)實際上是一致的，相比下，ELM的優(yōu)化限制條件卻更少.文獻[15]將ELM核應用于SVM中，使分類器取得了更好的性能，這是因為ELM有泛逼近能力和分類能力[8-9]，使其可以逼近任何連續(xù)目標函數(shù)，以及能對任何不相交區(qū)域進行正確分類.因此，通過ELM特征映射，原始數(shù)據(jù)的可分性能在高維特征空間中進一步增大，許多情況下，即使將原始數(shù)據(jù)通過ELM特征映射到同維的空間中，也能使數(shù)據(jù)變得線性可分.同時，與SVM核映射不同，ELM特征映射是一種顯示映射方法，更加簡單.此外，在ELM的實施過程中發(fā)現(xiàn)，當隱層節(jié)點的個數(shù)，即特征空間的維數(shù)為1000時(也可以為更小的數(shù))，對于各種長度的訓練數(shù)據(jù)，ELM基本上能取得令人滿意的結(jié)果[9]，這使得ELM映射生成的特征空間維數(shù)不至于過高，從而能夠避免kNN算法的“維數(shù)災難”，在提高原始數(shù)據(jù)的線性可分性和控制特征空間維數(shù)之間找到了一個很好的平衡點.

下面概括ELM特征空間上的kNN算法：

Step 1 對于N個需要進行分類的原始數(shù)據(jù)(包括訓練數(shù)據(jù)與測試數(shù)據(jù)){x1,x2,…,xN}(xi∈n),取定隱層節(jié)點個數(shù)為；

Step 2 生成隨機數(shù)輸入權(quán)向量wi∈n和偏置bi∈；

Step 3 選擇激勵函數(shù)，如Sigmoidal函數(shù)；

Step 4 利用ELM特征映射將xi映射為h(xi)=G(wi,bi,x)；

Step 5 利用kNN算法對h(xi)i=1,2,…,N進行分類.

Step 6 若h(xi)屬于第j類，則原始樣本xi屬于第j類.

3 仿真實驗

在本節(jié)中，我們將作kNN算法在樣本數(shù)據(jù)的原始空間進行分類和在ELM特征空間進行分類的精確率比較.

所用的數(shù)據(jù)集分別為MNIST手寫體數(shù)字數(shù)據(jù)庫[16]和來自UCI機器學習庫[17]的Wisconsin乳癌數(shù)據(jù)集、精子活力數(shù)據(jù)集、小麥種子數(shù)據(jù)集、Bupa肝臟疾病數(shù)據(jù)集.

使用的仿真軟件為：Matlab R2013a, 近鄰分類器采用Matlab模式識別工具箱中的knnclassify函數(shù)，k值取3，其他參數(shù)取默認值.

該實驗的環(huán)境為：Window 7 64bit操作系統(tǒng)，Intel Core i5-3570 3.40GHz，8GB內(nèi)存.

除MNIST數(shù)據(jù)庫外，實驗中其余數(shù)據(jù)集采用5-折交叉驗證，其中4份作為訓練數(shù)據(jù)集，另外1份作為測試數(shù)據(jù)集，輪流讓其中的1份作為測試樣本，其余4份作為訓練樣本，實驗結(jié)果取平均值.

首先進行手寫體數(shù)字識別.實驗數(shù)據(jù)來自MNIST手寫體數(shù)字數(shù)據(jù)庫，該數(shù)據(jù)庫有60 000個訓練樣本和10 000個測試樣本.

MNIST手寫體數(shù)字數(shù)據(jù)庫由0到9之間的手寫體數(shù)字構(gòu)成,每個數(shù)字構(gòu)成一幅28像素×28像素的灰度圖，灰度值取值范圍為0(黑)到255(白).為了進行無偏實驗，訓練樣本和測試樣本都隨機取自訓練集和測試集，訓練樣本每次取800個，測試樣本每次取200個，重復10次，實驗結(jié)果取平均值.圖3是一個手寫體數(shù)字的樣本集.

為了得到樣本數(shù)據(jù)，每個數(shù)字的圖像(如圖4(a))被均勻地分割成14行乘以14列，即每幅數(shù)字圖被分割成196幅小圖，見圖4(b).

利用式(4)計算每幅小圖的平均灰度值：

(4)

其中：(pl,q)i,j是第lq幅小圖的第ij個灰度值；r(=2)與c(=2)分別是像素行數(shù)與列數(shù).

因此，圖4(b)中的手寫體數(shù)字可表示為式(5)中的數(shù)據(jù)向量：

x=[x1,1,x1,2,…,x1,14,x2,1,x2,2,…,x2,14,…,x14,1,x14,2,…,x14,14].

(5)

同樣地，對Wisconsin乳癌數(shù)據(jù)庫、精子活力數(shù)據(jù)庫、小麥種子數(shù)據(jù)庫、Bupa肝臟疾病數(shù)據(jù)庫做上述處理.實驗數(shù)據(jù)集描述見表1.實驗結(jié)果如圖5～圖9所示.

表1 實驗數(shù)據(jù)集細節(jié)

從圖5～圖9可以看出，kNN算法在ELM特征空間中可以取得比在原始數(shù)據(jù)空間中更高的分類精確率，且隨著隱層節(jié)點個數(shù)的增加，分類精確率將逐漸提高.同時實驗表明，基本上隱層節(jié)點個數(shù)在200至400之間kNN算法能取得較為理想的分類精確率，從而使得kNN算法在ELM特征空間上能夠避免因維數(shù)過大所帶來的“災難”.

4 結(jié) 語

本文提出了一種在ELM特征空間中實行kNN分類算法的思想，利用ELM核將待分類的原始數(shù)據(jù)映射到特征空間中，使其在特征空間中被進一步分離，從而提高kNN算法的分類精確率，理論分析與實驗結(jié)果表明，我們的算法是有效的.

[1] COVER T M, HART P E.Nearest neighbor pattern classification [J].IEEETransactionsonInformationTheory,1967，13(1)：21-27.

[2] XIE Z P, HSU W,LIU Z T,etal. SNNB：A selective neighborhood based naive Bayes for lazy learning [C]∥Advances in Knowledge Discovery and Data Mining.Volume 2336 of the series Lecture Notes in Computer Science.Berlin-Heidelberg：Springer-Verlag，2002：104-114.

[3] JIANG L X, ZHANG H, CAI Z H.Dynamic k-nearest-neighbor naive Bayes with attribute weighted [M]∥Fuzzy Systems and Knowledge Discovery.German：Springer Press, 2006：365-368.

[4] LEE L H, WAN C H, RAJKUMAR R,etal. An enhanced support vector machine classification framework by using Euclidean distance function for text document categorization [J].AppliedIntelligence,2012,37(1)：80-99.

[5] PAREDES R, GIROLAMI M. On the use of diagonal and class-dependent weighted distances for the probabilistic k-nearest neighbor [C]∥Pattern Recognition and Image Analysis.Volume 6669 of the series Lecture Notes in Computer Science.Berlin-Heidelberg：Springer-Verlag，2011：265-272.

[6] CHANDRASEKHAR A P, RANI T S. Storage and retrieval of large data sets：Dimensionality reduction and nearest neighbour search [M]∥Contemporary Computing.Volume 306 of the series Communications in Computer and Information Science. Berlin-Heidelberg：Springer-Verlag，2012：262-272.

[8] HUANG G B, WANG D H, LAN Y. Extreme learning machines：A survey [J].InternationalJournalofMachineLearningandCybernetics,2011,2(2)：107-122.

[9] HUANG G B, DING X J, ZHANG RUI,etal. Extreme learning machine for regression and multiclass classification [J].IEEETransactionsonSystems,Man,andCybernetics—PartB：Cybernetics,2012,42(2)：513-529.

[10] HUANG G B, DING X J,ZHOU H M. Optimization method based extreme learning machine for classification [J].Neurocomputing,2010,74(1-3)：155-163.

[11] LU H J, AN C L, ZHENG E H,etal.Dissimilarity based ensemble of extreme learning machine for gene expression data classification [J].Neurocomputing,2014,128(3)：22-30.

[12] TIAN H X, MENG B.A new modeling method based on Bagging ELM for day-ahead electricity price prediction [C]∥2010 IEEE Fifth International Conference on Bio-Inspired Computing：Theories and Applications(BIC-TA).Changsha, China：IEEE，2010：1076-1079.

[13] LIU N, WANG H.Ensemble based extreme learning machine [J].IEEESignalProcessingLetters,2010,17(8)：754-757.

[14] HE Q, JIN X, DU C Y,etal. Clustering in extreme learning machine feature space [J].Neurocomputing,2014,128(2)：88-95.

[15] LIU Q G, HE Q, SHI Z Z. Extreme support vector machine classifier [C]∥Advances in Knowledge Discovery and Data Mining.Volume 5012 of the series Lecture Notes in Computer Science.Berlin-Heidelberg：Springer-Verlag，2008：222-233.

[16] MNIST數(shù)據(jù)庫[DB/OL].http：∥yann.lecun.com/exdb/mnist/.

[17] UCI機器學習庫[DB/OL].http：∥archive.ics.uci.edu/ml/datasets.html.

kNN Based on Extreme Learning Machine Feature Mapping

LU Chengbo, LIN Yinhe, MEI Ying

(Faculty of Engineering, Lishui University, Lishui 323000， China)

In view of the good properties of the ELM feature mapping, thekNN algorithm using ELM feature mapping techniques is studied. Through the ELM feature mapping, the original data will become more linear separable in the transformed high dimensional feature space, that is, data structure becomes much simpler. Thus, it can get more satisfactory results for classification using the feature data replace of the original data. Simulation experiments on MNIST and UCI data set show the excellent performance of our method.

extreme learning machine(ELM);k-nearest neighbor(kNN); feature space; classification

0427-7104(2016)05-0570-06

2015-03-20

國家自然科學基金(61373057，11171137)；浙江省自然科學基金(LY13A010008)

盧誠波(1977—)，男，博士，副教授；梅 穎(1977—)，女，碩士，副教授，通訊聯(lián)系人，E-mail：mymeiying@tom.com.

TP181;TP311

A