基于半監督極限學習機的增量式定位算法*

朱順濤,盧先領

(江南大學物聯網工程學院,江蘇 無錫 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。