一种基于流形正则化的半监督指纹定位算法

朱顺涛，卢先领,于丹石

(1. 江南大学“轻工过程先进控制”教育部重点实验室，江苏 无锡 214100； 2. 江南大学物联网工程学院，江苏 无锡 214100)

近年来，随着人们对于室内位置服务的需求日益迫切，室内定位技术受到广泛关注[1-3]。其中基于WLAN的室内指纹定位方位法凭借易部署、精度高、非视距等优点，逐步成为室内定位技术中研究的热点[4-5]。该方法主要分为离线训练和在线定位两个阶段[6]。离线训练阶段的主要工作是在每个参考点处采集一定数量的接收信号强度(received signal strength，RSS)信息，构建位置指纹数据库，并利用机器学习算法构建定位模型；在线定位阶段则根据待定位点处测得的RSS及离线阶段训练好的定位模型进行位置估计。

国内外学者提出几种典型的室内指纹定位算法。文献[7]提出一种改进的神经网络(improved neural network，INN)指纹定位算法，该算法结合神经网络初始参数设置与均方误差之间的相关性，来训练获得RSS指纹和位置坐标之间复杂的映射关系；文献[8]提出一种基于支持向量回归(support vector regression，SVR)的室内定位算法，该算法利用支持向量回归得到位置预测模型，提高定位精度的同时降低了对存储容量及计算能力的要求。文献[9]将极限学习机(extreme learning machine，ELM)运用到位置指纹定位算法中，凭借ELM随机特征映射的特点获得极快的学习速度，减少了离线学习时间；另外，ELM有着紧密的网络结构，能有效克服环境变化以及RSS时变性对定位精度的影响。传统指纹定位算法离线阶段都需要采集大量带有位置标签的训练数据来确保定位精度，这一过程将会耗费大量的人力物力，而大量无标签的指纹数据则可以通过定位区域中的移动终端轻松采集[10]。因此，充分利用带标签和无标签数据的半监督指纹算法有利于降低室内指纹定位算法对带标签位置数据的需求[11]。

针对传统指纹定位算法采集带标签训练数据成本高的问题，本文提出一种基于流形正则化的半监督指纹定位算法。

1 极限学习机

极限学习机(extreme learning machine，ELM)[12]是由Huang等提出的一种单隐含层前馈神经网络算法。该算法摒弃了梯度下降算法的迭代调整策略，通过随机产生隐含层的输入权值和偏移量来计算相应的输出权值矩阵，在保证学习精度的前提下比传统的学习算法速度更快。ELM的基本网络结构如图1所示。

图1 ELM算法的网络结构

对于任意N个训练样本集{(xj,tj)}j=1,2,…,N，ELM回归模型为

(1)

式中，ωi是连接输入节点和第i个隐含层节点之间的权值；bi是第i个隐含层节点的偏移量；g()是激活函数；βi是第i个隐含层节点输出权值；L是隐含层节点个数。将式(1)写成矩阵形式为

Hβ=T

(2)

式中，隐含层输出矩阵、位置输出矩阵及输出权值矩阵分别为

(3)

T=[t1t2…tN]T,β=[β1β2…βL]T

(4)

ELM模型通过最小化训练误差函数及输出权值矩阵的模，来计算隐含层的输出权值矩阵，从而完成相应模型的构建。ELM的目标函数可表示为[13]

(5)

式中，e是误差向量；C是训练误差惩罚系数矩阵。

2 流形正则化极限学习机

2.1 流形正则化框架

流形正则化(manifold regularization，MR)是一种通过构建无向有权图及图拉普拉斯算子来进行半监督学习的方法[14]，其通过整合流行正则化方法从而将那些未标记样本用于模型的训练。该方法建立在流形假设基础之上，流形假设可概括为：假设所有样本处于一个很小的局部邻域，那么它们就应该具有相近的标记[15]。用数学语言表达如下：如果x1和x2在同一个局部邻域内，那么x1的条件概率P(y|x1)和x2的条件概率P(y|x2)也应该相近。

给定一个训练样本集，其中包括l个标记样本{(xi,ti)}(i=1,2,…,l)和u个未标记样本{xi}(i=1,2,…,u)，流形正则化框架的最小化成本函数Lm为

(6)

式中，Wij为样本点xi和xj之间的边权值矩阵，计算方式如下

(7)

式中，KNN(xj)表示xj的最近邻点集合。由于条件概率不容易求得，可将式(6)简化为

(8)

根据图谱理论，式(8)能进一步写为如下形式

(9)

2.2 流形正则化框架和极限学习机的融合算法

本节将流形正则化和极限学习机相结合，提出一种基于流形正则化的半监督指纹定位算法(manifold regularization extreme learning machine，MR-ELM)，充分利用大量无标签数据，减少采集带标签数据的工作量，同时继承了极限学习机无需迭代、模型执行高效的优点。

具体过程是将式(9)表示的流形结构作为惩罚项来约束式(5)中的ELM目标函数，则MR-ELM算法的目标函数表现形式为

(10)

(11)

式中，L表示在带标签数据和无标签数据空间中建立的图拉普拉斯算子；F表示经模型运算后的输出矩阵；L是隐含层节点个数；no是输出层节点个数。

当利用K近邻方法构建邻接图时，权重矩阵计算如式(7)所示，该方法虽然减少了计算量，便于实现，但是节点的位置预测更偏向于它邻居节点的位置，从而降低了预测精度。为了解决这个问题，引入高斯核函数进行权重矩阵计算[16]，从而更好地反映样本空间的流形，提高预测精度，公式如下

(12)

将式(10)约束因子代入目标函数，则MR-ELM目标函数的矩阵形式可简写为

(13)

将式(13)对β求导，并令其等于0，得

(14)

当带标签数据的个数大于隐含层节点的个数时

β=(IL+HTCH+λHTLH)-1HTCY

(15)

当带标签数据的个数小于隐含层节点的个数时

β=HT(Il+u+CHHT+λLHHT)-1CY

(16)

式中，I是单位矩阵；惩罚矩阵C=diag(1,1,…,0,0)。通过求解β得到训练好的MR-ELM定位模型。

3 仿真结果分析

本文通过计算机模拟简化场景下的射线跟踪，生成仿真环境下的指纹数据库(数据来源：https:∥github.com/jiangqideng/codeInBlogs/tree/master/IP_raytracing)。该指纹库的覆盖范围为20 m×15 m的矩形区域，有6个AP节点。试验收集30 000条训练数据和10 000条测试数据，其中训练数据包括带标签数据和无标签数据。指纹数据库中的数据形式见表1，接收信号强度作为输入特征向量，位置坐标作为输出特征向量。系统的运行软件环境为Matlab 2012b，硬件环境为Core i3、3.7 GHz、8 GB内存的PC机。

表1 部分训练数据 dBm

图2 误差距离定义

如图3所示，随着带标签训练数据个数的增加，4种算法的平均定位误差逐渐下降并趋于稳定，这是由于带标签训练数据中所包含的信息改善了学习的性能，提高了定位精度。当带标签训练个数达到12 000时，MR-ELM算法的平均定位误差在1.5 m左右，相比于INN、SVR和ELM算法，分别降低了31.70%、24.90%和10.84%。

图3 各算法平均定位误差比较

假设误差距离为2 m，在不同带标签数据个数的情况下，对4种算法的定位准确率进行统计。如图4所示，MR-ELM算法的定位准确率高于其他3种算法，尤其是当带标签训练数据的个数小于12 000的稀疏状态时。当N=3000时，MR-ELM的定位准确率与INN、SVR、ELM算法相比，分别提高了33.52%、4.67%和16.56%。

图4 各算法定位准确率比较图

图5反映了带标签训练数据个数与训练时间之间的关系，可以看出随着带标签训练数据的不断增加，INN、SVR算法所需的训练时间增长较快，而ELM和MR-ELM两种算法的训练时间仅小幅增加。MR-ELM算法的训练时间略高于ELM算法，这是因为其在处理带标签训练数据的同时，还需处理无标签数据。表2为4种算法在带标签数据个数为3000，训练时间和测试时间的比较。可知，MR-ELM算法所需的训练时间和测试时间分别为2.50和0.05 s，符合实际定位要求。

图5 各算法离线阶段训练时间比较图

s

为了验证MR-ELM算法在带标签训练数据稀疏情况下定位效果的稳定性，试验将带标签训练个数和距离误差作为条件，对各算法的定位准确率进行了统计。试验结果如图6所示，MR-ELM算法在N=100、3000、6000、9000的4种带标签训练数据较少的情况，定位的准确率更高，且随着带标签训练数据的减少，MR-ELM算法的定位准确率的波动性远小于其他3种算法。

4 结 语

本文提出了一种基于流形正则化的半监督指纹定位算法。该算法首先以流形假设为依据，利用批量输入的带标签数据与无标签数据之间的相似度构建图拉普拉斯算子；然后与极限学习机算法相结合，通过随机特征映射建立隐含层；最后在流形正则化框架下，求解隐含层和输出层之间的权值矩阵，从而建立接收信号强度与位置之间的映射关系，即位置估计模型。仿真结果表明，与INN、SVR、ELM 3种算法相比，该算法的训练和测试时间较短，且在带标签训练数据稀疏的前提下仍能保持较高的准确率与稳定性。

图6 不同带标签训练数据和距离误差情况下定位准确率比较

随着时间的推移、室内环境的改变，在参考点处接收到的指纹信号将会发生变化，导致定位模型精度的降低，今后的研究重点是进一步提高定位模型对动态环境的适应能力。

[1] DENG Zhongliang,YU Yanpei,YUAN Xie，et al.Situation and Development Tendency of Indoor Positioning[J].China Communication，2013，10(3): 42-55.

[2] 靳超，邱冬炜.基于WiFi信号室内定位技术的研究[J].测绘通报，2017(5): 21-25.

[3] 毕京学，甄杰，汪云甲,等.高斯函数定权的改进KNN室内定位方法[J].测绘通报，2017(6):9-12.

[4] HE S，CHAN S H G.Wi-Fi Fingerprint-based Indoor Positioning: Recent Advances and Comparisons[J].IEEE Communications Surveys & Tutorials，2016，18(1):466-490.

[5] 崔斌，赵西安.一种基于传播模型和位置指纹的混合室内定位方法[J].测绘通报，2015(6): 35-43.

[6] XIA S，LIU Y，Yuan G，et al.Indoor Fingerprint Positioning Based on Wi-Fi: An Overview[J].International Journal of Geo-Information，2017，6(5):135.

[7] MOK E，CHEUNG B K S.An Improved Neural Network Training Algorithm for Wi-Fi Fingerprinting Positioning[J].ISPRS International Journal of Geo-Information，2013，2(3):854-868.

[8] SHI K，CHEN H S，ZHANG R T.Indoor Location Method Based on Support Vector Regression in 802.11 Wireless Rnvironments[J].Journal of Software，2014，25(11): 2636-2651.

[9] DWIYASA F，LIM M H，ONG Y S，et al.Extreme Learning Machine for Indoor Location Fingerprinting[J].Multidimensional Systems & Signal Processing，2017，28(3):867-883.

[10] 向铭.基于半监督学习的室内WLAN支持向量回归定位算法[D].重庆：重庆邮电大学，2016.

[11] PULKKINEN T，ROOS T，MYLLYMKI P.Semi-supervised Learning for WLAN Positioning[C]∥Proceedings of the 21th International Conference on Artificial Neural Networks and Machine Learning.Espoo:Springer-Verlag，2011.

[12] 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,2012,42(2):513-529.

[13] 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.

[14] NIYOGI P，Manifold Regularization and Semi-supervised Learning：Some Theoretical Analyses [J].Journal of Machine Learning Research，2013，14(1): 1229-1250.

[15] BELKIN M，NIYOGI P，SINDHWANI V.Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples[J].Journal of Machine Learning Research，2006，7(1): 2399-2434.

[16] 陶新民，曹盼东，宋少宇，等.基于半监督高斯混合模型核的支持向量机分类算法[J].信息与控制，2013,42(1)：18-26.