改进的核极限学习机定位算法

杨晋生,郭雪亮,陈为刚

(天津大学 微电子学院，天津 300072)

0 引 言

近年来，随着神经网络的发展越来越成熟，神经网络被广泛应用于人工控制、图像分析、智能预测等各个领域。由于神经网络具有抗干扰能力强、非线性映射能力强、自学习能力强等优点，许多学者将神经网络应用在无线定位领域。例如：径向基(radial basis function,RBF)、反向传播(back propagation,BP)、支持向量机[3](support vector machine,SVM)、极限学习机[4](extreme learning machine,ELM)等神经网络都被应用到了无线定位中。神经网络定位主要分为2部分：训练和预测。训练阶段，主要是将样本数据输入到神经网络中进行训练，得到预测模型；预测阶段，主要是将预测数据输入预测模型中得到预测结果。其中，样本数据主要由测量点到各个接收点的信号强度(received signal strength, RSS)[5]和测量点的位置坐标组成。

ELM是由Huang等提出的一种新的神经网络算法，相较于其他神经网络算法，ELM神经网络具有泛化能力强和学习速度快的优点。因此，被广泛应用在室内无线定位领域。基于ELM神经网络的定位方法主要分为2类：①利用ELM的分类特性，针对预测区域建立指纹数据库，通过指纹匹配的方式得到定位结果。文献[4-7]中的做法就是先建立指纹数据库，然后用ELM神经网络对指纹进行匹配。然而，这种建立指纹库的方法存在一个严重的缺点，就是没有充分考虑到信号强度受噪声的干扰导致指纹与位置坐标不是唯一对应的问题。为此，文献[8]采用序贯极限学习机对指纹数据库进行不定时的更新，这一做法在一定程度上避免了噪声的干扰，但是仍然对指纹的不唯一性考虑不足，定位精度不高；②利用ELM的强大的泛化能力，进行非线性拟合，进而估计出位置。文献[9-12]先利用训练样本建立预测模型，然后通过这一预测模型进行定位，虽然在获取RSS信息时进行了降低噪声干扰的处理，但是效果不明显，定位结果受噪声干扰大，定位精度不高。文献[12]采取对同一位置进行多次测量的方法，有效降低了噪声对定位结果的干扰，但是这一方法导致了训练样本增多，使网络训练时间变长。

针对在同一位置测得的数据受噪声干扰可能有多组，不是唯一不变的，导致定位误差较大，以及目前神经网络无线定位算法参数设置复杂、训练耗时较长的问题。本文提出来一种改进的核极限学习机(kernel extreme learning machine, KELM)定位算法。算法具有以下优点。

1)算法定位精度高。对同一位置进行多次测量得到受噪声干扰的样本数据，充分考虑了噪声对定位结果的干扰。

2)定位速度快。一方面是由于以样本子空间中心为训练集，达到了降维的效果；另一方面由于本文改进了KELM算法，提高了算法的计算速度。

1 核极限学习机

由于RELM算法需要设置的参数较少，训练速度快，泛化能力强，因此，选用KELM。

KELM是由黄广斌[13-14]等提出的一种新的单层前馈神经网络算法。RELM具有训练速度快，预测精度高的优点[15]。

对于N个任意不同的样本(xi,ti)，其中，xi=[xi1,xi2,…,xin]T∈Rn，ti=[ti1,ti2,…,tim]T∈Rm，R为实数集；对于具有L个隐层神经元数的单层前馈神经网络，网络的输出表示为

(1)

(1)式中，xj=[xj1,xj2,…,xjn]T∈Rn为输入样本；wi=[wi1,wi2,…win]T∈Rn为输入层到隐藏层的权重；wi·xj为wi和xj的内积，βi=[βi1,βi2,…,βim]T为隐层到输出层的权重；bi为第i个隐层神经元的偏置；h(·)为隐层神经元的激励函数；tj为第j个样本的输出。(1)式可以写成矩阵相乘的形式，即

Hβ=T

(2)

对(2)式求最小二乘法得到

(3)

(4)

(4)式中：C为惩罚系数；ξj为实际输出与理论输出的差，ξj=[ξj1,…,ξjm]；αj为Lagrange乘子，αj=[αj1,…,αjm]，h(xj)=[h(w1·xj+b1),…，h(wL·xj+b1)]为矩阵H的行向量。

(4)式由KKT条件得

(5)

(5)式中：α=[α1,α2,…,αN]T；ξ=[ξ1,ξ2,…,ξN]T。

由(5)式得

(6)

求解(6)式得

(7)

定义核矩阵表达式如下：Ω=HHT,K(xi,xj)=h(xi)×h(xj)，代入(5)式得

(8)

将(8)式代入(2)式得

(9)

由此得到核极限学习机的输出权值为

(10)

2 本文算法

2.1 样本子空间降维

为了充分考虑噪声对样本的干扰，本文采取对同一个位置进行多次测量的方法得到样本数据，然后将这些对应同一位置的数据划分为一个样本子空间，之后用该样本子空间的特征代替原来的样本数据，这样不仅充分考虑了噪声对样本数据的干扰，同时也起到了降低样本维度的效果。本文已考虑不同的干扰源可能引起样本数据聚集出不同的簇，如图1所示，圆Ai表示在任意一个位置测得样本数据，圆B1，B2，B3代表受不同干扰影响形成的簇。本文提出了一种样本子空间降维算法(sample subspace dimension reduction, SSDR)，算法以样本子空间的中心和该子空间的簇的中心与该子空间的中心的余弦相似度来代替原来的训练数据。

图1 样本子空间Fig.1 Sample subspace

假设在一个周围有M个固定信号接收点的场景中，对N(M≪N)个位置进行训练样本采集，且针对同一个位置测量k次，那么得到的样本集可以用N×k行M列的矩阵表示。

根据位置将这些样本划分为N个不同的样本子空间，在求各个子空间的中心时，考虑到这些子空间属于高维子空间，一般的低维空间求聚类中心的方法不再适用。因此，本文利用子空间投影的方法来求高维子空间的聚类中心，先将子空间中的点投影到各个平面上，再用k-means聚类得到平面上的聚类中心，再由各个平面中心坐标得到子空间中心坐标为Oi。

同理，求得任意一个样本子空间中划分出的m(m

算法1SSDR降维算法。

输入：样本矩阵S=[x1,x2,…,xN]T。其中，xi=[xi1,xi2,…,xiM]，N为样本总数，M为固定信号接收点数，即样本特征数。

输出：降维之后的样本矩阵S′。

1)将样本按测量位置分为N子矩阵，即N个M维子空间。

2)Fori=1,2,…,N

从S中划分出子矩阵Ai,i=1,2,…,N。

3)Forj=2,3,…,M

①取特征1与特征j构成矩阵将样本投影到平面上得Pj←[Ai(:,1),Ai(:,j)]；

②利用k-means求平面上聚类中心oij←kmeans(Pj,1)；

③同理得到Ai子空间的m(m

4)End For

5)得到Ai聚类中心Oi←[oi1,oi2(:,2),…,oiM(:,2)]；

8)End For

2.2 改进核极限学习机算法

提出一种改进的核极限学习机(improved kernel extreme learning machine，IMP-KELM)。由于核极限学习机算法的核矩阵Ω的大小与输入样本数N正相关。在N较大的情况下，计算核Ω会花费较长的时间，为了降低计算复杂度，本文采用计算Ω的近似矩阵h的方法来降低计算复杂度。

考虑到矩阵ΩN×N是根据输入样本计算得来的，所以可以通过减少参与计算的样本数量来达到降低计算复杂度的目的。又因为输入的样本对算法的贡献度不同，本文根据主向量分析法(principal component analysis，PCA)，以样本为特征，得到样本的贡献度。取贡献度较大的n个样本组成样本矩阵Xn×M。

最后，将hN×N=GGT，代入(8)式再根据Woodbury公式得到网络输出权重矩阵为

(11)

算法具体实现过程如下。

算法2改进的KELM算法。

输入：训练样本(xi,yi)，其中，xi=[xi1,xi2,…,xiM]T∈RM，ti=[ti1,ti2]T∈R2，N为样本总数，M为固定信号接收点数，即样本特征数。

输出：最终定位预测模型。

1)利用主向量分析法，以样本个数为特征，得到样本的贡献度。取前n个贡献度大的样本构成矩阵Xn×M；

2)加载KELM训练模型；

3)IF 选择RBF核函数，则

求得ΩN×n；

4)End IF

7)得到最终预测模型。

2.3 改进的核极限学习机定位算法

本文以SSDR-IMP-KELM表示该定位算法。首先，根据样本子空间降维算法对样本进行降维，得到以子空间特征组成的新的样本；然后，将这些新的样本数据输入到核极限学习机中训练神经网络，得到预测模型；最后，用得到的预测模型进行位置估计，达到定位目的。算法具体实现过程如下。

算法3改进核极限学习机定位算法。

输入：样本(xi,yi)，其中，xi=[xi1,xi2,…,xiM]T∈RM，ti=[ti1,ti2]T∈R2，N为样本总数，M为固定信号接收点数，即样本特征数。

输出：定位预测结果，即预测位置的坐标。

1)取样本的特征信息组成矩阵S←[x1,x2,…,xN]T；

5)测试样本输入到预测模型；

6)T′←H·β得到预测位置坐标。

算法流程图如图2所示。

图2 定位算法流程图Fig.2 Flow chart of positioning algorithm

2.4 计算复杂度分析

本文算法的计算复杂度主要由2部分组成：SSDR降维算法的计算复杂度、改进的KELM算法的计算复杂度。参照文献[15]计算复杂度的方法，统计加、减、乘、除的运算总次数来度量算法的计算复杂度。遵循以下2个原则。

1)矩阵的加、减、乘和求逆计算的计算统计。

若矩阵A∈Rm×n，B∈Rm×n，C∈Rn×l，D∈Rn×n则A±B的计算复杂度为mn，AC为2mnl-ml；D-1为n3。

2)消减原则。

只保留最高次幂项且忽略每一项前的系数。

依据以上原则统计实现SSDR降维算法的运算总次数，得到计算复杂度为ο((Nk)2NM(M-1)/2)。

同理，改进的KEM的计算复杂度为ο(Nn2+n3)。

改进的核极限学习机定位算法的复杂度主要由SSDR降维算法与改进的KELM算法的复杂度组成则计算复杂度为ο((Nk)2NM(M-1)/2+Nn2+n3)。

同理，未改进的KELM算法计算复杂度为ο((Nk)3)。其中，M,N,k代表含义与2.1节相同，n为2.2节样本经过PCA分析，得到的n个贡献度较大的样本。

3 实验与仿真

3.1 实测数据分析

为了使仿真实验与实际联系起来，本文首先对实际环境下得到的数据进行分析，并以此为依据进行仿真实验。实测数据来源于2016年8月29日，在天津市无线电管理委员会频谱资源监控中心，利用位于天津市南开区天津大学西侧的白堤路上的编号为UMS300-101487的监测站，对南开大学校园广播的信号强度进行连续3天的检测得到的数据。本文取每一天的上午一分钟和下午一分钟得到的测量统计图如图3所示。

图3中，在实际环境中，针对同一个点进行多次测量，得到的RSS值不是固定不变的，RSS值是变化的。同时，由于测得的数据是在一分钟内完成的，所以在实际应用中，可以利用较短的时间得到大量的RSS值。为了使仿真更符合实际，本文采用了以下仿真方法。

图3 室外实际测量某一信号RSS变化统计图Fig.3 Outdoor actual measurement of a signal RSS change statistics

3.2 场景仿真

应用MATLAB R2013b 在CPU型号为intel(R) Core(TM)i5-2450M，主频2.50 GHz，内存为4 GByte，Windows7 64位系统的环境下进行仿真实验。仿真一个2 000 m×2 000 m的室外环境，且周围有4个接收点，具体仿真场景如图4所示，利用信号路径损耗模型，根据参考点距离计算RSS值。

(12)

(12)式中：PL0为路径损耗系数，在本文中被设为-40 dBm；d0是与PL0对应的测量距离；d为到参考点的距离；α为路径损耗指数取2，X为由服从高斯分布、伽马分布和均匀分布的噪声组成。

图5为对某一点仿真得到的RSS统计图。在仿真场景范围内随机取200个点，对每个点进行100次的测量，得到仿真数据，从中随机选取100个点作为训练集，剩余100个点为测试集。

图4 仿真场景图Fig.4 Simulation scenario

图5 某一点仿真得到的RSS统计图Fig.5 RSS statistics obtained from a point simulation

3.3 实验涉及参数设置

1)算法1涉及的参数。在同一位置重复测量次数k，由3.2节知k=100；任意一个样本子空间中划分出m(m

2)算法2涉及的参数。选择贡献度大的前n个样本，n的选取通过多次实验得到，n=82；核极限学习机的核参数设为RBF核，如(13)式；惩罚参数C，设C∈{2-10,2-9,…,240,250}，进行网格搜索得到C=220；RBF核的参数μ，设μ∈{2-10,2-9,…,240,250}，网格搜索得到μ=210。

K(u,v)=exp[-(‖u-v‖2/μ)]

(13)

(13)式中，μ为核参数。

3)遗传算法优化的BP神经网络算法(GA-BP)。GA-BP用于与本文算法对比，网络参数设置为：隐层数3，隐层节点数取20(经过多次实验得到)，迭代次数设为1 000次。

4)RBF神经网络参数设置。RBF用于与本文算法对比，RBF神经网络网络参数设置为：隐层节点数70，迭代次数1 000次。

3.4 定位仿真实验

衡量性能的指标一般选取均方根误差(root mean square error ，RMSE)作为衡量测试性能的标准，如(14)式。

(14)

仿真结果如表1所示。表1中，Training-RMSE，Train-Time，Test-RMSE分别表示训练耗时(原始数据输入KELM到得出模型参数)、训练误差以及测试所得结果的均方根误差。

表1 仿真结果对比

表1中，KELM与改进后IMP-KELM相比，在训练时间方面，改进的KELM算法明显耗时较短，其他方面相差不大。因此，IMP-KELM算法是有效的。KELM与本文算法SSDR-IMP-KELM相比，在时间方面，训练耗时和测试耗时都要比本文算法用时长，训练耗时是本文算法SSDR-IMP-KELM的10倍左右；在误差方面，本文算法误差明显小于KELM算法，约为KELM误差的1/4。GA-BP算法和RBF算法与本文算法相比，训练耗时长，误差较大，误差是本文算法的4倍左右。

由2.4节知，KELM算法的时间复杂度为ο((N×k)3)，改进的KEM的计算复杂度为ο(Nkp2+p3)，SSDR-IMP-KELM算法复杂度为ο((Nk)2NM·(M-1)/2+Nn2+n3)。仿真实验中k=100，N=100，n=82，M=4，p=3000则ο((N×k)3)=ο(1012)，ο(Nkp2+p3)=ο(9.27×1010)，ο((Nk)2NM(M-1)/2+Nn2+n3)≈ο(6.0×1010)。

为了更直观地比较SSRD-IMP-KELM算法与其他算法的误差，本文给出了误差累计分布图，如图6所示。

图6 误差累计分布图Fig.6 Cumulative error distribution

从图6中可以看出，本文算法在误差为75 m时累计误差分布率接近100%，而KELM算法在误差为200 m时误差累计分布率刚刚达到76%。GA-BP与RBF算法在误差为200 m时误差累积分布率刚刚达到74%。由此可以看出，本文算法误差更小，且分布较为集中。

4 结 论

本文针对目前神经网络无线定位耗时较长，且定位结果易受噪声干扰的问题提出了一种改进的核极限学习机的定位算法。因为测量RSS数据时易受各种噪声的干扰导致定位精度不高，本文采用以样本子空间特征代替原来样本的方法处理数据，这样既提高了定位精度又降低了样本数据维度，提高了定位速度。为了进一步提高定位速度本文提出了一种改进的核极限学习机，利用改进的核极限学习机学习降维之后的样本，得到定位预测模型。仿真实验验证了本文算法具有定位速度快，定位精度高的优点。

参考文献：

[1] 毛永毅,李明远,张宝军. 基于RBF神经网络的蜂窝无线定位算法[J]. 系统工程与电子技术,2008(09):1798-1800.

MAO Yongyi, LI Mingyuan, ZHANG Baojun. Cellular location algorithm based on the RBF neural network[J]. Journal of Systems Engineering and Electronics, 2008(09):1798-1800.

[2] 张会清,石晓伟,邓贵华,等. 基于BP神经网络和泰勒级数的室内定位算法研究[J]. 电子学报,2012,40(9):1876-1879.

ZHANG Huiqing, SHI Xiaowei, DENG Guihua, et al. Research on Indoor Location Technology Based on Back Propagation Neural Network and Taylor Series [J]. Chinese Journal of Electronics, 2012，40(9): 1876-1879.

[3] CHOU K C, CAI Y D. Using functional domain composition and support vector machines for prediction of protein subcellular location[J]. Journal of Biological Chemistry, 2002, 277(48): 45765-45769.

[4] ZOU H, HUANG B, LU X, et al. A robust indoor positioning system based on the procrustes analysis and weighted extreme learning machine[J]. IEEE Transactions on Wireless Communications, 2016, 15(2): 1252-1266.

[5] 夏英,王磊,刘兆宏.基于无线局域网接收信号强度分析的混合室内定位方法[J].重庆邮电大学学报:自然科学版, 2012, 24(2):217-221.

XIA Ying, WANG Lei, LIU Zhaohong. Hybrid indoor positioning method based on WLAN RSS analysis[J]. Journal of Chongqing University of Posts and Telecommunications : Natural Science Edition, 2012, 24(2):217-221.

[6] DWIYASA F, LIM M H, ONG Y S, et al. Extreme learning machine for indoor location fingerprinting[J]. Multidimensional Systems and Signal Processing, 2017, 28(3): 867-883.

[7] XIAO W, LIU P, SOH W S, et al. Extreme learning machine for wireless indoor localization[C]//Proceedings of the 11th international conference on Information Processing in Sensor Networks. 2012 ACM/IEEE 11th International Conference on. Beijing, China: IEEE Press, 2012: 101-102.

[8] ZOU H, JIANG H, LU X, et al. An online sequential extreme learning machine approach to WiFi based indoor positioning[C]//Internet of Things(WF-loT). 2014 IEEE Press, World Forum on. Seoul, South Korea: IEEE Press, 2014:111-116.

[9] LIU J, CHEN Y, LIU M, et al. SELM: semi-supervised ELM with application in sparse calibrated location estimation[J]. Neurocomputing, 2011, 74(16): 2566-2572.

[10] LU X, LONG Y, ZOU H, et al. Robust extreme learning machine for regression problems with its application to wifi based indoor positioning system[C]//Machine Learning for Signal Processing(MLSP). 2014 IEEE International Workshop on. Reims, France: IEEE Press, 2014:1-6.

[11] XIAO W, LIU P, SOH W S, et al. Large scale wireless indoor localization by clustering and Extreme Learning Machine[C]//Information Fusion(FUSION). 2012 15th International Conference on. Singapore, Singapore: IEEE Press, 2012:1609-1614.

[12] LU X, ZOU H, ZHOU H, et al. Robust extreme learning machine with its application to indoor positioning[J]. IEEE Transactions on Cybernetics, 2016, 46(1): 194-205.

[13] HUANG G B, ZHU Q Y, Siew C K. Extreme learning machine: a new learning scheme of feedforward neural networks[C]//Neural Networks, 2004. Proceedings. 2004 IEEE International Joint Conference on. Budapest, Hungary: IEEE Press, 2005: 985-990.

[14] HUANG G B, ZHOU H, DING X, et al. Extreme learning machine for regression and multiclass classification[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2012, 42(2): 513-529.

[15] HUANG G B, CHEN L, SIEW C K. Universal approximation using incremental constructive feed-forward networks with random hidden nodes[J]. IEEE Transactions on Neural Networks, 2006, 17(4): 879-892.

[16] 文成林,吕冰,葛泉波.一种基于分布式滤波的数据融合算法[J].电子学报,2004,32(8):1264-1267.

WEN Chenglin, LU Bing, GE Quanbo. A Data Fusion Algorithm Based on Filtering Step by Step[J]. Chinese Journal of Electronics, 2004, 32 (8): 1264-1267.