基于機器學(xué)習(xí)的室內(nèi)定位方法綜述

徐龍陽

摘要：針對現(xiàn)有的室內(nèi)定位方法存在高成本、低精度、魯棒性低等問題。一些學(xué)者嘗試將機器學(xué)習(xí)（Machine Learning，ML）引入室內(nèi)定位中，用機器學(xué)習(xí)思想解決上述問題，旨在提高定位方法的性能。文章首先詳細(xì)綜述了五種基于K-最近鄰、人工神經(jīng)網(wǎng)絡(luò)、支持向量機、決策樹以及貝葉斯的定位方法，然后對這些方法的定位性能進行了比較分析，結(jié)果表明合適的機器學(xué)習(xí)算法能夠提高定位精度、增強系統(tǒng)魯棒性和降低成本，最后總結(jié)了基于機器學(xué)習(xí)的室內(nèi)定位方法未來的一些研究熱點問題。

關(guān)鍵詞：室內(nèi)定位；機器學(xué)習(xí)；神經(jīng)網(wǎng)絡(luò)

中圖分類號：TP391 文獻標(biāo)識碼：A 文章編號：1009-3044（2018）01-0217-03

Abstract：In some indoor positioning methods that there are existing some problems of a high cost， low accuracy and low robustness. Some scholars try to introduce Machine Learning （ML） into indoor positioning， and use machine learning to solve the problems mentioned above， aiming at improving the performance of positioning method. Firstly， the five kinds of localization methods Based on k-NN， ANN，SVM， decision tree and Bayesian are summarized. Then the positioning performance of these methods is compared and analyzed. The results show that the appropriate machine learning algorithm can improve the positioning accuracy， enhance the robustness of the system and reduce the cost. Finally， some research hotspots in the future of the indoor learning method Based on machine learning are summarized.

Key words： Indoor positioning； machine learning； neural network

1 概述

隨著人類社會快速發(fā)展，在高度城市化的現(xiàn)代社會，人們對空間位置信息的需求不斷提高，定位技術(shù)也越來越多受到人們的重視[1]。尤其是近些年，基于GPS定位系統(tǒng)、移動互聯(lián)網(wǎng)、智能手機等技術(shù)提供的位置信息服務(wù)，給人們?nèi)粘Ｉ顜順O大的便利。人們可以利用其提供的位置服務(wù)來進行打車、叫外賣、尋找銀行甚至交友等。除此之外，在一些大型商場、工廠、醫(yī)院、寫字樓以及地下煤礦等復(fù)雜的室內(nèi)環(huán)境下的位置信息需求也很迫切。但由于在室內(nèi)環(huán)境下無法有效感測到衛(wèi)星信號，因此GPS定位系統(tǒng)并不能提供足夠精度的位置信息來滿足人們在該環(huán)境下的定位需求[2]。基于此，一些國內(nèi)外學(xué)者對解決室內(nèi)環(huán)境下的定位問題做了廣泛而深入的研究。

目前，現(xiàn)有的室內(nèi)定位方法主要有基于測距和非測距定位兩大類，基于測距定位具體的方法有到達(dá)時間TOA ，到達(dá)時間差TDOA，到達(dá)角AOA等。基于非測距定位主要有接受信號強度指示RSSI，一般又分為距離路徑衰減模型法和位置指紋匹配法 。根據(jù)在室內(nèi)定位中采用的介質(zhì)不同，主要有移動傳感器 、可見光、紅外線、射頻識別RFID 、超寬帶 、Zigbee 、無線局域網(wǎng)WLAN以及無線傳感器網(wǎng)WSN等多種室內(nèi)定位技術(shù)。這些技術(shù)有些需要專門設(shè)備，成本較大，難以大規(guī)模推廣應(yīng)用。有些易受環(huán)境、信號等干擾影響定位效果。因此，如何低成本高精度普適性好地實現(xiàn)復(fù)雜的室內(nèi)環(huán)境下的定位，已成為當(dāng)前室內(nèi)定位技術(shù)中的研究熱點、難點之一。

近些年，一些學(xué)者將機器學(xué)習(xí)引入室內(nèi)定位中，利用機器學(xué)習(xí)思想來解決室內(nèi)定位問題。本文首先詳細(xì)綜述了五種基于機器學(xué)習(xí)的定位方法，然后對定位方法的定位性能進行比較分析，最后總結(jié)了基于機器學(xué)習(xí)的定位方法未來的一些研究熱點問題。

2 主要的機器學(xué)習(xí)定位方法

本節(jié)五種主要的算法分別是K-最近鄰、人工神經(jīng)網(wǎng)絡(luò)、支持向量機、決策樹以及貝葉斯等。

2.1KNN算法

K最近鄰算法KNN是一種簡單成熟的分類技術(shù)。通過計算距離的度量作為相似性度量。常用于指紋匹配階段，在定位時利用KNN算法計算目標(biāo)值與指紋庫里的樣本值之間的歐式距離，按距離大小進行排序，選取前K個最小距離的參考點，然后以這K個參考點的平均位置作為目標(biāo)估計的位置。

利用KNN算法作為指紋匹配算法，定位精度受選取的K值影響較大，K值太大太小都會造成較大誤差，因此優(yōu)化K值提高定位效果如Liu Chunyan等人[3]的幾何聚類指紋庫的約束加權(quán)KNN定位模型。

加權(quán)k最近鄰算法Weighted-KNN是一種改進的KNN算法，一般根據(jù)K個參考點與樣本點之間距離大小賦予不同的權(quán)值，距離越近權(quán)值越大。定位時將加權(quán)后的幾何質(zhì)心作為目標(biāo)估計的位置。WKNN算法可以通過調(diào)整權(quán)值來優(yōu)化分類結(jié)果，所以在性能上優(yōu)于傳統(tǒng)的KNN算法。

KNN算法理論簡單，K值對KNN算法定位性能影響很大，大部分優(yōu)化的KNN算法都是對K值進行優(yōu)化。因為算法需要遍歷數(shù)據(jù)庫里所有樣本數(shù)據(jù)，因此對于數(shù)據(jù)量過大的數(shù)據(jù)庫使用KNN算法會有較大的計算量。endprint

2.2 人工神經(jīng)網(wǎng)絡(luò)方法

人工神經(jīng)網(wǎng)絡(luò)ANN是一種模仿人腦神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)進行學(xué)習(xí)、處理問題的網(wǎng)絡(luò)模型。

傳統(tǒng)的基于RSSI的距離路徑衰減模型定位方法依賴于模型參數(shù)的選取，這些參數(shù)沒有統(tǒng)一標(biāo)準(zhǔn)化的準(zhǔn)則來度量，只能靠擬合或人工經(jīng)驗去估計，不準(zhǔn)確的估計會大大影響模型的性能。因此，張會清等人[4]通過訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)擬合模型參數(shù)A和n，A為收發(fā)距離為1m的路徑損耗值，n為路徑衰減系數(shù)，避免了傳統(tǒng)的復(fù)雜擬合或經(jīng)驗估計。

在位置指紋匹配法中，劉侃等人[5]采用四層的深度神經(jīng)網(wǎng)絡(luò)進行RSSI指紋定位。通過堆疊去躁自編碼器對網(wǎng)絡(luò)結(jié)構(gòu)進行預(yù)訓(xùn)練，并用反向傳播進行全局微調(diào)。自動地從具有波動性的無線信號里提取特征并進行線性變換計算目標(biāo)的位置坐標(biāo)。該方法實現(xiàn)較高的定位準(zhǔn)確率和增強了系統(tǒng)魯棒性。

利用人工神經(jīng)網(wǎng)絡(luò)模型定位，能適應(yīng)噪聲數(shù)據(jù)訓(xùn)練，具有較強的非線性映射能力和良好的數(shù)據(jù)擬合能力。通過網(wǎng)絡(luò)的學(xué)習(xí)能力能減少指紋構(gòu)建更新成本和自適應(yīng)環(huán)境變化。但前期需要大量數(shù)據(jù)訓(xùn)練網(wǎng)絡(luò)模型來調(diào)整其權(quán)值、閾值等參數(shù)，增加了訓(xùn)練成本。

2.3 支持向量機方法

支持向量機SVM是一種通過搜尋最大邊緣超平面來確定最優(yōu)決策邊界的分類回歸算法。通過核函數(shù)將非線性問題映射到高維特征空間中進行線性分類。并用松弛系數(shù)或懲罰系數(shù)來調(diào)整分類結(jié)果。因此，在解決高維、非線性分類問題有優(yōu)勢。可以將SVM良好的分類、回歸能力應(yīng)用到室內(nèi)定位。

利用SVM分類模型定位，將定位問題看作是分類問題。前期通過數(shù)據(jù)訓(xùn)練分類模型，然后將目標(biāo)樣本數(shù)據(jù)輸入訓(xùn)練好的分類模型，對應(yīng)輸出一個最優(yōu)分類結(jié)果，再利用具體的估計方法得出目標(biāo)的位置。在位置指紋定位法中，朱宇佳等人[6]將指紋匹配過程設(shè)計成多分類問題。根據(jù)室內(nèi)建筑結(jié)構(gòu)，劃分合適的網(wǎng)格區(qū)域。每個網(wǎng)格代表一個類別，然后用各個網(wǎng)格接受到的RSSI值和信標(biāo)節(jié)點編號信息訓(xùn)練SVM分類模型。

據(jù)上述介紹，基于SVM定位方法，憑借SVM出色的分類回歸能力，可以很好地解決多分類，高維、非線性分類問題。但也帶來較大的分類計算成本，且訓(xùn)練過程時間較長。

2.4 決策樹方法

決策樹（Decision Tree）是一個以樹結(jié)構(gòu)形式構(gòu)建的分類模型。用決策樹算法進行室內(nèi)定位先利用訓(xùn)練的數(shù)據(jù)，構(gòu)造一顆決策樹模型。再通過該模型對輸入的數(shù)據(jù)特征判別進行分類，依據(jù)分類結(jié)果確定目標(biāo)的位置。

行人航跡推算PDR的定位系統(tǒng)，常需要外部定位系統(tǒng)來保持精度和初始化。該算法存在傳感器漂移導(dǎo)致的累積誤差。因此，針對降低計算復(fù)雜度，減少累積誤差等問題。Liao J K等人[7]在室內(nèi)地圖信息輔助下引入低復(fù)雜度的模糊決策樹以減少對硬件設(shè)備依賴提高系統(tǒng)的準(zhǔn)確性和穩(wěn)定性。通過移動步長、候選區(qū)域選擇、方向估計三部分來構(gòu)造模糊決策樹中的三個內(nèi)部節(jié)點進行特征判別定位。為進一步提高模糊決策樹定位精度。

通過決策樹算法進行定位，分類準(zhǔn)確率較高，自上而下的建樹分類過程具有較好的可視化效果，易于理解。利用決策樹分類模型不需要太多訓(xùn)練數(shù)據(jù)，算法計算成本較低，能耗較少，適合應(yīng)用到對能耗有限制要求的定位系統(tǒng)中。但當(dāng)建樹過深，分支過多易發(fā)生過擬合問題和最優(yōu)化問題。

2.5 貝葉斯方法

貝葉斯分類（Bayesian）算法是一種基于概率統(tǒng)計學(xué)知識的分類算法。樸素貝葉斯分類（Naive Bayes）是基于貝葉斯定理和假設(shè)特征條件相互獨立的分類方法。

在基于RSSI的距離路徑衰減模型法中，由于室內(nèi)環(huán)境復(fù)雜導(dǎo)致同一參考點RSSI值分布不同，因此可以多次測量RSSI值，從中選取優(yōu)質(zhì)的值作為采集的數(shù)據(jù)，從而減少噪聲的RSSI值使用。如Liu Huan等人[8]基于貝葉斯概率模型提出一種優(yōu)化RSSI的無線傳感網(wǎng)絡(luò)定位系統(tǒng)。通過多次測量RSSI值并把測量的RSSI值看成符合正態(tài)分布概率事件。利用貝葉斯概率模型只篩選出現(xiàn)“大概率事件”的RSSI值，再利用三邊測量技術(shù)和最小二乘法來估計未知節(jié)點的位置。該方法通過篩選出優(yōu)質(zhì)RSSI值，降低了平均定位誤差。

在位置指紋定位中，利用貝葉斯算法進行定位在離線階段將在每個參考點采集的無線信號特征值作為指紋數(shù)據(jù)，計算每個參考點的指紋數(shù)據(jù)概率分布并存儲，即已知位置的指紋概率分布的先驗概率。在線階段利用存儲的先驗概率計算目標(biāo)指紋在各個參考點的后驗概率，選取最大的后驗概率所在的參考點位置作為目標(biāo)指紋的估計位置。

基于貝葉斯分類算法定位具有處理多分類問題的優(yōu)勢，因為計算量大不適用于大規(guī)模數(shù)據(jù)庫。樸素貝葉斯算法易于實現(xiàn)，但它是建立在條件相互獨立假設(shè)基礎(chǔ)上的，實際應(yīng)用中特征之間不可能絕對的獨立，因此影響了實際的定位效果。

3 定位方法的比較分析

本節(jié)對上文詳細(xì)介紹的一些基于機器學(xué)習(xí)的室內(nèi)定位方法進行比較分析，從精度、準(zhǔn)確度、成本、魯棒性以及優(yōu)缺點等方面給出比較結(jié)果。經(jīng)過分析總結(jié)，在室內(nèi)定位中使用的機器學(xué)習(xí)主要有提高定位精度、增強系統(tǒng)魯棒性以及降低系統(tǒng)成本等三大優(yōu)點。

（1） 提高定位精度

通過使用的機器學(xué)習(xí)算法可以在三個方面來提高定位精度。具體如下：

1） 優(yōu)化模型參數(shù)：通過優(yōu)化模型參數(shù)，提高模型定位精度。Zhang等人通過訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)擬合模型參數(shù)A和n，達(dá)到優(yōu)化參數(shù)的目的[4]。

2） 抗環(huán)境變化：利用一些算法的學(xué)習(xí)能力、提取有效特征的能力來適應(yīng)環(huán)境變化。降低誤差：通過一些回歸模型來估計校正測量、匹配誤差來提高精度。

3） 數(shù)據(jù)預(yù)處理：通過對數(shù)據(jù)進行除噪、除冗余來提高精度。如利用貝葉斯概率模型篩選出優(yōu)質(zhì)的RSSI值[8]。

（2） 增強系統(tǒng)魯棒性

基于無線信號的室內(nèi)定位方法易受到環(huán)境變化、信號干擾、衰減以及非視距等因素影響。利用合適的機器學(xué)習(xí)算法能有效降低這些變化影響。可以通過一些神經(jīng)網(wǎng)絡(luò)模型的在線學(xué)習(xí)、更新能力不斷調(diào)整模型參數(shù)適應(yīng)環(huán)境的變化，增強系統(tǒng)魯棒性。endprint

（3） 降低系統(tǒng)成本

降低成本主要表現(xiàn)在通過使用一些機器學(xué)習(xí)算法來降低指紋庫構(gòu)建更新、計算分類以及能耗等三個方面成本。具體如下：

1） 指紋庫構(gòu)建：在指紋定位中，通過一些算法自學(xué)習(xí)能力構(gòu)建、更新指紋庫來降低建造維護成本。

2） 減少計算分類成本：通過定位區(qū)域劃分若干子區(qū)域進行粗定位等來減少分類和計算成本[6]。

3） 降低能耗：可以選擇一些低計算復(fù)雜度、低能耗的算法來節(jié)省能耗，如決策樹[7]。

4 結(jié)束語

本文主要對五種基于機器學(xué)習(xí)算法的定位方法進行綜述并對其定位性能進行歸納比較。最后總結(jié)出使用合適的機器學(xué)習(xí)算法具有提高定位精度，增強系統(tǒng)魯棒性以及降低系統(tǒng)成本等優(yōu)點。目前，室內(nèi)定位技術(shù)仍有一些問題沒有得到令人滿意的解決。

通過對基于機器學(xué)習(xí)的室內(nèi)定位方法學(xué)習(xí)研究，未來有一些值得深入研究的熱點問題。

1） 指紋庫構(gòu)建、更新。傳統(tǒng)的指紋庫構(gòu)建、更新成本較大，嚴(yán)重影響指紋定位方法的推廣應(yīng)用。因此，國內(nèi)外一些學(xué)者提出一種基于CrowdSensing的定位方法[9]。該方法無需專門人員采集指紋數(shù)據(jù)就可建庫。這是一種利用群智感知的思想并結(jié)合機器學(xué)習(xí)與數(shù)據(jù)挖掘技術(shù)來完成指紋庫構(gòu)建與更新。

2） 設(shè)備異質(zhì)性。在指紋采集階段，使用不同的硬件設(shè)備在同一參考點采集到的指紋地圖是不同的。一種解決方法是通過使用其他比較穩(wěn)健的位置特征如RSSI的信號強度差異SSD作為位置指紋，然而該方法增加了指紋的維度和計算復(fù)雜度。如果從減少校準(zhǔn)成本和降低計算復(fù)雜度角度出發(fā)，嘗試?yán)脵C器學(xué)習(xí)解決設(shè)備異質(zhì)性問題是個不錯的選擇。

參考文獻：

[1] 鄧中亮. 室內(nèi)外無線定位與導(dǎo)航[M].北京郵電大學(xué)出版社，2013.

[2] 席瑞， 李玉軍， 侯孟書. 室內(nèi)定位方法綜述[J]. 計算機科學(xué)，2016，43（4）：1-6.

[3] 劉春燕， 王堅. 基于幾何聚類指紋庫的約束KNN室內(nèi)定位模型[J]. 武漢大學(xué)學(xué)報：信息科學(xué)版，2014， 39（11）：1287-1292.

[4] 張會清， 石曉偉， 鄧貴華，等. 基于BP神經(jīng)網(wǎng)絡(luò)和泰勒級數(shù)的室內(nèi)定位算法研究[J].電子學(xué)報，2012， 40（9）：1876-1879.

[5] 劉侃， 張偉， 張偉東，等. 一種基于深度神經(jīng)網(wǎng)絡(luò)的無線定位方法[J].計算機工程，2016，42（7）：82-85.

[6] 朱宇佳， 鄧中亮， 劉文龍，等. 基于支持向量機多分類的室內(nèi)定位系統(tǒng)[J].計算機科學(xué)， 2012，39（4）：32-35.

[7] Liao J K， Chiang K W， Tsai G J， et al. A low complexity map-aided Fuzzy Decision Tree for pedestrian indoor/outdoor navigation using smartphone[C]// International Conference on Indoor Positioning and Indoor Navigation. 2016：1-8.

[8] 劉歡，黃麗，楊曉，等.一種貝葉斯優(yōu)化RSSI和ILS的室內(nèi)定位算法[J].中國科技論文，2015（20）：2377-2381.

[9] 吳陳沭.基于群智感知的無線室內(nèi)定位[D].清華大學(xué)，2015.endprint