基于ELM特征映射的kNN算法

卢诚波，林银河，梅 颖

(丽水学院工学院，丽水323000)



基于ELM特征映射的kNN算法

卢诚波，林银河，梅 颖

(丽水学院工学院，丽水323000)

研究了基于ELM特征映射的kNN算法，利用ELM特征映射，将原始数据映射到这种高维特征空间当中，使得数据间变得更加线性可分，即数据结构会变得简单，因此，在利用kNN算法进行分类时，利用ELM特征空间中对应的特征数据代替原始空间中的数据进行分类将会取得更好的分类效果.最后，来自MNIST和UCI中的几个数据集的仿真实验进一步验证了该算法的优良性能.

超限学习机；k最近邻算法；特征空间；分类

由Cover和Hart提出的k最近邻(k-Nearest Neighbor，kNN)算法[1]是最著名的模式识别和统计学方法之一.kNN算法的核心思想是如果一个样本的k个最邻近的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性.该方法在确定分类决策上只依据最邻近的一个或者几个样本的主要分类来决定新数据的类别，因此被称为最近邻算法.kNN算法在类别决策时，只与极少量的相邻样本有关.由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别，因此对于类域的交叉或重叠较多的待分样本集来说，kNN算法较其他方法更为适合.kNN算法思路简单，易于实现，因此在模式识别、文本分类、图形图像等领域被经常使用.

kNN算法需解决的问题主要有：1)近邻数k的取值问题，k值选取的合理与否直接关系到算法的结果，因此，一些研究者开始研究k值的选取方法以取代个人的经验选择[2-3]；2)如何根据实际问题选择更合适的相似度函数[4-5]；3)kNN算法在对属性较多即维数较高的训练样本进行分类时，由于计算量大而使其效率降低，效果不是很理想，因此涌现了一些针对性的解决方案[6-7]；4)如何对原始数据进行预处理，例如使线性不可分的样本转化为线性可分，从而更利于kNN算法进行分类.

本文主要的思想是利用ELM特征映射算法将低维输入空间中复杂线性不可分的样本转化为高维特征空间使其线性可分，从而使得kNN算法在高维特征空间中的分类精确度得到进一步提高.

下面首先简单介绍ELM算法.

1 ELM算法

ELM算法是一种被称为“超限学习机(Extreme Learning Machine，ELM)”的单隐层前馈神经网络学习算法的简称[8-9]，基本思想如下：

对于输入向量x∈n,具有个隐层节点的单隐层前馈神经网络的输出值可表示为：

其中：wi∈n是连接第i个隐层节点的输入权值;βi∈m是连接第i个隐层节点的输出权值;bi是第i个隐层节点的偏置；G(wi,bi,x)为第i个隐层节点的输出，激励函数G可以是任意有界的非常量连续函数，大部分非线性分段连续函数都可以用来当作激励函数[8]，常用的激励函数如Gaussian函数、Sigmoidal函数、Sine函数等.

设分别有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)式的方程，即可得到输出权矩阵

β=H+T,

其中H+为矩阵H的Moor-Penrose广义逆.

在ELM算法中，输入权和偏置为随机给定，输出权通过最小二乘法计算得到，整个训练过程一次完成，不需要迭代.由于ELM算法与已知的一些算法相比，训练速度要快得多，且具有更好的泛化性，并且人为干预少，因此被广泛地应用，特别是在各种分类和回归问题中[10-14].

图1为一个输入权和隐层偏置为随机数的单隐层前馈神经网络(Single-hidden Layer Feedforward Neural Network, SLFN).

2 ELM特征空间中的kNN算法

由于通过非线性转化，数据在高维特征空间中将会变得更加线性可分，数据结构变得相对简单，也就更易于分类，因此，一些核方法开始被用来作特征映射，如支持向量机(Support Vector Machine，SVM)，通过一个非线性映射，把样本空间映射到一个高维乃至无穷维的特征空间中(Hilbert空间)，使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题．ELM不仅在学习速度上要比传统的SVM快得多，而且在许多时候扩展性和泛化性都要好于SVM[9]，文献[11]证明了SVM的最大分离边际与ELM的输出权最小范数实际上是一致的，相比下，ELM的优化限制条件却更少.文献[15]将ELM核应用于SVM中，使分类器取得了更好的性能，这是因为ELM有泛逼近能力和分类能力[8-9]，使其可以逼近任何连续目标函数，以及能对任何不相交区域进行正确分类.因此，通过ELM特征映射，原始数据的可分性能在高维特征空间中进一步增大，许多情况下，即使将原始数据通过ELM特征映射到同维的空间中，也能使数据变得线性可分.同时，与SVM核映射不同，ELM特征映射是一种显示映射方法，更加简单.此外，在ELM的实施过程中发现，当隐层节点的个数，即特征空间的维数为1000时(也可以为更小的数)，对于各种长度的训练数据，ELM基本上能取得令人满意的结果[9]，这使得ELM映射生成的特征空间维数不至于过高，从而能够避免kNN算法的“维数灾难”，在提高原始数据的线性可分性和控制特征空间维数之间找到了一个很好的平衡点.

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

Step 1 对于N个需要进行分类的原始数据(包括训练数据与测试数据){x1,x2,…,xN}(xi∈n),取定隐层节点个数为；

Step 2 生成随机数输入权向量wi∈n和偏置bi∈；

Step 3 选择激励函数，如Sigmoidal函数；

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 仿真实验

在本节中，我们将作kNN算法在样本数据的原始空间进行分类和在ELM特征空间进行分类的精确率比较.

所用的数据集分别为MNIST手写体数字数据库[16]和来自UCI机器学习库[17]的Wisconsin乳癌数据集、精子活力数据集、小麦种子数据集、Bupa肝脏疾病数据集.

使用的仿真软件为：Matlab R2013a, 近邻分类器采用Matlab模式识别工具箱中的knnclassify函数，k值取3，其他参数取默认值.

该实验的环境为：Window 7 64bit操作系统，Intel Core i5-3570 3.40GHz，8GB内存.

除MNIST数据库外，实验中其余数据集采用5-折交叉验证，其中4份作为训练数据集，另外1份作为测试数据集，轮流让其中的1份作为测试样本，其余4份作为训练样本，实验结果取平均值.

首先进行手写体数字识别.实验数据来自MNIST手写体数字数据库，该数据库有60 000个训练样本和10 000个测试样本.

MNIST手写体数字数据库由0到9之间的手写体数字构成,每个数字构成一幅28像素×28像素的灰度图，灰度值取值范围为0(黑)到255(白).为了进行无偏实验，训练样本和测试样本都随机取自训练集和测试集，训练样本每次取800个，测试样本每次取200个，重复10次，实验结果取平均值.图3是一个手写体数字的样本集.

为了得到样本数据，每个数字的图像(如图4(a))被均匀地分割成14行乘以14列，即每幅数字图被分割成196幅小图，见图4(b).

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

(4)

其中：(pl,q)i,j是第lq幅小图的第ij个灰度值；r(=2)与c(=2)分别是像素行数与列数.

因此，图4(b)中的手写体数字可表示为式(5)中的数据向量：

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

(5)

同样地，对Wisconsin乳癌数据库、精子活力数据库、小麦种子数据库、Bupa肝脏疾病数据库做上述处理.实验数据集描述见表1.实验结果如图5～图9所示.

表1 实验数据集细节

从图5～图9可以看出，kNN算法在ELM特征空间中可以取得比在原始数据空间中更高的分类精确率，且随着隐层节点个数的增加，分类精确率将逐渐提高.同时实验表明，基本上隐层节点个数在200至400之间kNN算法能取得较为理想的分类精确率，从而使得kNN算法在ELM特征空间上能够避免因维数过大所带来的“灾难”.

4 结 语

本文提出了一种在ELM特征空间中实行kNN分类算法的思想，利用ELM核将待分类的原始数据映射到特征空间中，使其在特征空间中被进一步分离，从而提高kNN算法的分类精确率，理论分析与实验结果表明，我们的算法是有效的.

[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数据库[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—)，女，硕士，副教授，通讯联系人，E-mail：mymeiying@tom.com.

TP181;TP311

A