一種基于流形正則化的半監督指紋定位算法

朱順濤，盧先領,于丹石

(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，訓練時間和測試時間的比較?？芍琈R-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.