基于半监督极限学习机的增量式定位算法*

朱顺涛,卢先领

(江南大学物联网工程学院,江苏 无锡 214122)

项目来源:江苏省产学研联合创新资金前瞻性联合研究项目(BY2014023-31);江苏省“六大人才高峰”项目(WLW-007)

2017-04-26修改日期2017-06-13

基于半监督极限学习机的增量式定位算法*

朱顺涛,卢先领*

(江南大学物联网工程学院,江苏 无锡 214122)

针对目前室内指纹定位算法存在实时性差、对动态环境适应性不足的问题,提出一种新的基于半监督极限学习机的定位算法。该算法首先通过半监督极限学习机建立初始化位置估计模型,然后利用新增的半标记数据对原定位模型进行动态调整,最后为新增训练数据分配合适惩罚权重,使模型具有时效机制。仿真结果表明,该定位算法在保证定位实时性的同时提高了对动态环境的适应性。

无线传感器网络;指纹定位;增量式学习;半监督学习;极限学习机

随着近年智能设备的兴起以及人们对精确定位服务的需求,室内定位技术成为人们研究和关注的焦点[1]。其中,基于WLAN的室内指纹定位技术以其易部署、精度高、非视距等优点,逐步成为室内定位技术中研究的热点[2]。该技术原理是利用机器学习算法,学习目标点的接收信号强度RSSI(Received Signal Strength Indication)和物理位置之间的非线性映射关系,从而推断出待测点位置[3]。

目前国内外无线传感器网络室内定位技术取得了显著的成果,指纹定位技术和基于RSSI的定位技术备受关注[4]。Dwiyasa等人将极限学习机ELM(Extreme Learning Machine)运用到位置指纹定位算法中[5],凭借ELM随机特征映射的特点获得极快的学习速度,从而减少离线学习时间;另外,ELM有着紧密的网络结构,有效克服环境变化以及RSSI时变性对定位精度的影响,但其缺点在于采用监督学习的方式,使得离线阶段收集带标签训练数据的成本较高。Li等人提出基于协同训练的半监督极限学习机,降低了训练成本[6],但是学习过程中重复循环训练会造成学习速度降低和累计误差增加的后果。Liu等人提出基于流形正则化的半监督极限学习机SELM(Semi-supervised Extreme Learning Machine)来进行室内位置估计,确保在带标签数据稀疏的情况下仍然有着理想的定位精度[7],缺点是模型过于固定及实时性较差。Kaemarungsi等人指出随着时间的推移,RSSI指纹信号的波动会造成位置估计模型定位精度的下降[8]。Yang等人将增量学习方法与极限学习机相结合,在每次循环反馈中对新加入的样本进行在线连续学习[9],提高了对环境的适应性,但由于其未考虑增量数据的实效性,所以定位模型的准确性和鲁棒性有待进一步提高。Gu等人提出带约束项的在线指纹定位算法,通过引入L2约束项,提高模型长时间定位的泛化能力[10],但也没有考虑增量数据的时效机制。Pan等人在无线定位问题中采用了增量式学习框架,并且能够实时接收新增的半标记数据,对定位预测模型进行在线更新[11],与传统方法相比,减少标定工作量且提高了定位准确率。

针对传统室内指纹定位算法实时性差、对动态环境适应性不足的问题,提出一种基于半监督极限学习机的增量式定位算法IS-ELM(Incremental Semi-supervised Extreme Learning Machine)。首先利用SELM对带标签数据及无标签数据共同进行训练,从而建立初始化非线性位置估计模型;然后利用分块矩阵的运算法则,使半标记的增量训练数据能够对模型参数进行动态调整,提高定位模型的实时性和对动态环境的适应性;最后为新增训练数据分配合适惩罚权重,使模型具有时效机制。

1 SELM定位模型

在指纹定位的离线阶段,需要收集大量带有位置信息的标签数据来训练定位模型,这将耗费大量的人力和时间[12]。而半监督极限学习机是在Huang提出的ELM基础上,通过引入图拉普拉斯正则化,从而对带标签训练数据和无标签训练数据一起进行半监督学习[13]。该模型充分利用大量易获得的无标签数据,从而降低了采集带标签数据的成本。

对于N个训练数据{xj,tj}j=1,2,…,N,隐含层节点个数为L,ELM回归模型[14]可表示为

(1)

式中:wi是连接输入节点和第i个隐含层节点之间的权值向量,bi是第i个隐含层节点的偏移量,g(.)是激活函数,βi是第i个隐含层节点输出权值向量。根据KKT理论[15],构建ELM模型就等同于求解如下优化问题

ε(β)=min‖Hβ-T‖2+μ‖β‖2

(2)

(3)

T=[t1,t2,…,tN]T,β=[β1,β2,…,βL]T

(4)

式中:ε(β)为关于β的优化函数,H为隐含层输出矩阵,β为隐含层输出权值矩阵,T为输出目标矩阵,μ为正则化参数。

SELM定位模型则是在ELM模型基础上,利用Belkin提出的半监督图理论[16],寻找一个平滑函数

(5)

进一步写成矩阵形式

s(f)=fTLf

(6)

ε(β)=min‖JHβ-T‖2+λ(Hβ)TLHβ+μ‖β‖2

(7)

使用拉格朗日乘子法求解输出权值矩阵解

(8)

β=[μI+HT(J+λL)H]-1HTJT

(9)

当式(9)中参数λ=0时,意味着不考虑无标签训练数据,此时ELM模型就相当于SELM模型的一种特殊形式。

2 改进的SELM定位算法

本节针对大量半标记训练数据进行批量学习时,巨大的计算量会导致模型定位实时性差和对动态环境适应性不足的问题,提出一种基于SELM的增量式定位算法。该算法的主要思想是,首先将训练数据转化为数据流的形式输入,然后对传统的SELM模型的模型参数进行优化,使得增量数据的贡献直接体现在对现有模型进行修正,最后为新增数据赋予惩罚权重,从而使得位置估计模型更好地适应环境的动态变化。

2.1 SELM的增量式改进

Bing等人指出SELM模型需要在经验风险、结构风险及模型复杂度之间取得平衡[17],其输出权值矩阵如式(9)所示,令

K=μI+HT(J+λL)H

(10)

则SELM模型的输出权值矩阵

β=K-1HTJT

(11)

(12)

(13)

(14)

(15)

(16)

式中:J1为增量数据集的转换矩阵,L为增量数据集的图拉普拉斯矩阵,I为单位矩阵,D、Q为两个数据集之间的图拉普拉斯算子。

根据半监督学习优化理论[18],最小化模型复杂度仅为一个辅助条件来改善模型光滑度,所以在直接计算图拉普拉斯矩阵的时候,图拉普拉斯算子D、Q将被忽视,最后的联合图拉氏矩阵为并且将联合图拉氏矩阵及式(13)代入式(15)中,得K1的迭代形式:

(17)

为了寻找SELM模型参数β(1)和β(0)之间的增量关系,并推测出增量数据对模型的贡献,对下式进行重写

(18)

根据上式所得,β(1)能被写为

(19)

(20)

IS-ELM的输出权值矩阵记为

(21)

综上所述,已存在的模型及经过增量学习的模型的权值输出矩阵分别表示为β和β*,二者之间的关系为β*=β+Δβ,其中,Δβ为增量数据对于模型的改变量,记为

(22)

2.2IS-ELM实效性改进

(23)

新加入的惩罚权重ω可以作为增量数据对原有模型的影响程度,从而相对减小了过时训练数据对位置估计模型的干扰。

惩罚权重ω是一个常量,其取值需要通过实验来获得。如仅对于式(23)进行一次性权重修正,定位模型不足以趋于稳定。为此本文采用牛顿迭代法的方式获得IS-ELM模型参数最终解,即对式(23)进行迭代计算,直至前后模型参数之差|β(k+1)-β(k)|<ε时(ε是初始化阈值)停止迭代;否则令β(k)=β(k+1),继续迭代到最大迭代次数T为止。最终IS-ELM模型输出权值矩阵参数β(out)=β(k+1),从而完成位置估计模型的训练。

综上所述,本文提出的IS-ELM定位算法的流程如图1所示,具体定位步骤如下:①从实际环境中采集带标签训练数据和无标签训练数据,共同构成初始训练数据集;②设置定位模型的系统参数,如激活函数g(x),隐含层节点个数L,正则化参数μ、λ,惩罚权重ω;③随机分配隐含层节点的输入权值矩阵W=[w1,w2,…,wL]T和偏移b=[b1,b2,…,bL]T;④计算初始化的隐含层输出矩阵H0、图拉普拉斯矩阵L、输出权值矩阵β(0);⑤当在线阶段有新的增量数据输入时,计算新的图拉普拉斯矩阵L以及迭代后的模型参数β(k+1);⑥给原有模型参数分配惩罚权重ω,设定最大迭代次数T,利用牛顿迭代法的方式对最终输出的模型参数进行更新调整,得到最终的模型参数β(out);⑦输入测试数据到定位模型中,进行位置估计。

图1 本文算法流程图

3 实验仿真及分析

本文利用计算机模拟简化室内场景下的射线跟踪,生成仿真环境下指纹数据库(数据来源:https://github.com/jiangqideng/codeInBlogs/tree/master/IP_raytracing)。系统的运行软件环境为MATLAB 2012b,硬件环境为Core i3、3.7 GHz、8 GB内存的PC机。该指纹库的覆盖范围为20 m×15 m,包括6个AP节点,选用ITU所定义的室内传播模型[19]来构建路径损耗与距离之间的关系,其表达式如下

PL(d)=PL0-10αlog(d)+Xσ

(24)

式中:PL0是路径损耗系数,Xσ是均值为零的随机噪声,σ是路径衰减指数。构建完成的指纹数据库如表1所示,其中包括10 000组离线训练数据、20 000组增量训练数据以及30组在线测试数据。在训练数据中25%为带标签数据,其余为不带标签数据。实验采用SELM和一次权重增量极限学习机WOSELM(Weighted Online Sequential Extreme Learning Machine)算法作为比较算法,并采用均方根误RMSE差(Root Mean Square Error)和不同误差距离下的定位精度作为度量标准,对3种算法的位置估计能力进行比较。

表1 部分训练数据(信号强度单位:dBm)

图2 不同惩罚权重下IS-ELM的定位误差

表2 不同算法实时性比较

为确保算法之间进行公平比较,IS-ELM、WOS-ELM和SELM 3种算法的隐含层节点个数都取500,激活函数选用hardlim函数。另外惩罚权重ω是IS-ELM算法的一个重要参数,该值的选取由测试结果来确定。图2显示了惩罚权重与定位误差之间的关系曲线,由图可知,令惩罚权重为5时,测试误差取最小值,故选择ω=5作为惩罚权重经验值。图3显示了当ω=5时的IS-ELM定位算法的收敛性能,当经过60次左右的迭代后的模型参数之差|β(k+1)-β(k)|趋于稳定,算法即可收敛,所以最大迭代次数T取60。

图3 IS-ELM算法的收敛性随迭代次数的变化

为了测试算法在定位实时性方面的表现,本文将在线校准数据分为4个数据块,然后对初始定位模型进行调整。由表2可知,IS-ELM、WOSELM、SELM 3种算法平均每次增量学习所需的训练时间分别为0.89 s、0.70 s、3.78 s。IS-ELM定位算法与传统SELM算法相比,平均训练时间减少了2.89 s,提高了定位的实时性;与WOSELM算法相比,训练时间增加了0.19 s,这是因为IS-ELM采用牛顿迭代法来计算模型参数,提高了模型的时间复杂度,但依然能够满足实际定位的需求。3种算法所需测试时间分别为0.28 s、0.29 s、0.26 s,比较接近。

3种定位算法在不同距离误差下的定位精度比较如图4所示。当距离误差为1.50 m时,IS-ELM、WOS-ELM、SELM的平均定位精度概率分别为65%、57%、53%。IS-ELM算法相对于SELM算法,定位精度提高了12%,这主要是因为IS-ELM算法对于新增数据的增量式学习功能,使得模型能够适应室内环境的动态变化;相对于WOS-ELM算法,定位精度提高了8%,这得益于IS-ELM算法的实效性改进。

图4 不同误差距离下算法定位精度比较

为了进一步验证IS-ELM算法对动态环境的适应能力,我们改变射线跟踪模型的参数σ,来产生3个不同的时间段内的指纹数据。在每个时间段内采集5 000组增量训练数据以及30组在线测试数据,每组测试点进行50次实验。

图5～图7分别显示了IS-ELM、WOSELM、SELM 3种定位算法在不同时间段内的平均定位误差。从图5可以看出,在时间段1内,SELM和WOS-ELM算法的平均定位误差分别为2.51 m和1.85 m,而IS-ELM算法的平均定位误差仅为1.63 m;从图6可以看出,当环境再次发生变化时,SELM和WOS-ELM算法的平均定位误差与前一时间段相比,分别提高了1.23 m和0.67 m,而IS-ELM算法仅提高0.21 m;从图7可以看出,当环境发生第3次变化时,其他两种算法的定位误差仍然在不断增大,而IS-ELM的平均定位误差可以保持在1.85 m左右,对环境的适应性最好。

图5 不同算法在时间段1内定位误差比较概率

图6 不同算法在时间段2内定位误差比较概率

图7 不同算法在时间段3内定位误差比较概率

图8 各算法在不同时间段内的RMSE变化

图8显示了IS-ELM、WOSELM、SELM 3种算法在不同时间段内的RMSE变化图。时间段0代表模型初始化阶段,此时3种算法的RMSE比较接近。但随着时间的推移,室内环境发生动态变化,IS-ELM凭借本文提出的更新机制,RMSE变化幅度最小,定位的稳定性最好。

4 结论

室内定位系统面临长时间运行定位精度下降的问题,这是因为环境的不断变化使得指纹信号受到严重的干扰。为了解决这个问题,本文提出一种基于半监督学习的增量式指纹定位算法。该算法利用新增的半标记数据来更新旧的位置估计模型,并为增量数据分配惩罚权重,在保证定位实时性的前提下,改善了传统指纹定位算法对动态环境的适应性。下一步工作将计划部署实际的室内定位环境,将基于IS-ELM算法运用于现实的室内定位系统之中,并在提高定位的精度和效率方面做进一步的研究。

[1] 杨增瑞,段其昌,毛明轩,等. 基于磁场指纹辅助的手机室内定位系统[J]. 传感技术学报,2016,29(9):1441-1448.

[2] Kaemarungsi K,Krishnamurthy P.Analysis of WLAN’s Received Signal Strength Indication for Indoor Location Fingerprinting[J]. Pervasive and Mobile Computing,2012,8(2):292-316.

[3] Chen B,Liu R,Chen Y,et al. WiFi Fingerprint Basedself-Adaptive Indoor Localization in the Dynamic Environment[J]. Chinese Journal of Sensors and Actuators,2015,28(5):729-738.

[4] 章晓强,方飞,应可珍,等. 一种基于插值的室内指纹定位系统设计与实现[J]. 传感技术学报,2017,30(4):596-602.

[5] Dwiyasa F,Lim M H.Extreme Learning Machine for Active RFID Location Classification[M]. Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems-Volume 2. Springer International Publishing,2015:657-670.

[6] Li K,Zhang J,Xu H,et al. A Semi-Supervised Extreme Learning Machine Method Based on Co-Training[J]. Journal of Computational Information Systems,2013,9(1):207-214.

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

[8] Kaemarungsi K,Krishnamurthy P. Analysis of WLAN’s Received Signal Strength Indication for Indoor Location Fingerprinting[J]. Pervasive and Mobile Computing,2012,8(2):292-316.

[9] Yang Z,Zhang P,Chen L. RFID-Enabled Indoor Positioning Method for a Real-Time Manufacturing Execution System Using OS-ELM[J]. Neurocomputing,2016,174(PA):121-133.

[10] Gu Y,Liu J,Chen Y,et al. Constraint Online Sequential Extreme Learning Machine for Lifelong Indoor Localization System[C]//International JointConference on Neural Networks.IEEE,2014. 732-738.

[11] Pan J J,Pan S J,Yin J,et al. Tracking Mobile Users in Wireless Networks via Semi-Supervised Colocalization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,34(3):587-600.

[12] 张勇,支小莉. 基于半监督学习的室内定位算法[J]. 计算机工程,2010,36(17):277-279.

[13] Huang G,Song S,Gupta J N D,et al. Semi-Supervised and Unsupervised Extreme Learning Machines[J]. IEEE Transactions on Cybernetics,2014,44(12):2405-2417.

[14] Huang G B,Zhu Q Y,Siew C K.Extreme Learning Machine Theory and Applications[J]. Neurocomputing,2006,70(1-3):489-501.

[15] 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 A Publication of the IEEE Systems Man and Cybernetics Society,2012,42(42):513-29.

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

[17] Bing L,Xia S X,Meng F R,et al. Manifold Regularized Extreme Learning Machine[J]. Neural Computing and Applications,2016,27(2):255-269.

[18] Liu S L,Feng L,Wang H B,et al. Extend Semi-Supervised ELM and a Frame Work[J]. Neural Computing and Applications,2016,27(1):205-213.

[19] Chrysikos T,Georgopoulos G,Kotsopoulos S. Site-Specific Validation of ITU Indoor Path Loss Model at 2.4 GHz[C]//World of Wireless,Mobile and Multimedia Networks and Workshops,2009:1-6.

AnIncrementalLocalizationAlgorithmBasedonSemi-SupervisedExtremeLearningMachine*

ZHUShuntao,LUXianling*

(School of Internet of Things Engineering,Jiangnan University,Wuxi Jiangsu 214122,China)

Due to present indoor fingerprint-based localization algorithms perform poorly in real-time and cannot adapt quickly in a dynamic environment,a new localization algorithm based on semi-supervised extreme learning machine is proposed.Firstly,a location estimation model is initialized with the semi-supervised extreme learning machine.Subsequently,the initial model is incrementally adaptively adjusted by incorporating the new semi-labeled training dataset.Finally,an appropriate penalty weight is assigned to the incremental dataset to render the model dynamic.Simulation results show that the proposed algorithm improves the model’s environment adaptability while ensuring its real-time localization capability.

wireless sensor network;fingerprint-based localization;incremental learning;semi-supervised learning;extreme learning machine

TP393.1

A

1004-1699(2017)10-1554-06

10.3969/j.issn.1004-1699.2017.10.017

朱顺涛(1993-),男,江苏宜兴市人,硕士研究生,主要研究领域为室内定位、机器学习,6151904012@vip.jiangnan.edu.cn;

卢先领(1972-),男,汉族,江苏无锡市人,博士,教授,硕士生导师,主要研究领域为室内定位、无线传感网,jnluxl@jiangnan.edu.cn。