基于機器學習的室內定位方法綜述

徐龍陽

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

關鍵詞：室內定位；機器學習；神經網絡

中圖分類號：TP391 文獻標識碼：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 概述

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

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

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

2 主要的機器學習定位方法

本節五種主要的算法分別是K-最近鄰、人工神經網絡、支持向量機、決策樹以及貝葉斯等。

2.1KNN算法

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

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

加權k最近鄰算法Weighted-KNN是一種改進的KNN算法，一般根據K個參考點與樣本點之間距離大小賦予不同的權值，距離越近權值越大。定位時將加權后的幾何質心作為目標估計的位置。WKNN算法可以通過調整權值來優化分類結果，所以在性能上優于傳統的KNN算法。

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

2.2 人工神經網絡方法

人工神經網絡ANN是一種模仿人腦神經網絡結構進行學習、處理問題的網絡模型。

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

在位置指紋匹配法中，劉侃等人[5]采用四層的深度神經網絡進行RSSI指紋定位。通過堆疊去躁自編碼器對網絡結構進行預訓練，并用反向傳播進行全局微調。自動地從具有波動性的無線信號里提取特征并進行線性變換計算目標的位置坐標。該方法實現較高的定位準確率和增強了系統魯棒性。

利用人工神經網絡模型定位，能適應噪聲數據訓練，具有較強的非線性映射能力和良好的數據擬合能力。通過網絡的學習能力能減少指紋構建更新成本和自適應環境變化。但前期需要大量數據訓練網絡模型來調整其權值、閾值等參數，增加了訓練成本。

2.3 支持向量機方法

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

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

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

2.4 決策樹方法

決策樹（Decision Tree）是一個以樹結構形式構建的分類模型。用決策樹算法進行室內定位先利用訓練的數據，構造一顆決策樹模型。再通過該模型對輸入的數據特征判別進行分類，依據分類結果確定目標的位置。

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

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

2.5 貝葉斯方法

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

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

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

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

3 定位方法的比較分析

本節對上文詳細介紹的一些基于機器學習的室內定位方法進行比較分析，從精度、準確度、成本、魯棒性以及優缺點等方面給出比較結果。經過分析總結，在室內定位中使用的機器學習主要有提高定位精度、增強系統魯棒性以及降低系統成本等三大優點。

（1） 提高定位精度

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

1） 優化模型參數：通過優化模型參數，提高模型定位精度。Zhang等人通過訓練BP神經網絡擬合模型參數A和n，達到優化參數的目的[4]。

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

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

（2） 增強系統魯棒性

基于無線信號的室內定位方法易受到環境變化、信號干擾、衰減以及非視距等因素影響。利用合適的機器學習算法能有效降低這些變化影響。可以通過一些神經網絡模型的在線學習、更新能力不斷調整模型參數適應環境的變化，增強系統魯棒性。endprint

（3） 降低系統成本

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

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

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

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

4 結束語

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

通過對基于機器學習的室內定位方法學習研究，未來有一些值得深入研究的熱點問題。

1） 指紋庫構建、更新。傳統的指紋庫構建、更新成本較大，嚴重影響指紋定位方法的推廣應用。因此，國內外一些學者提出一種基于CrowdSensing的定位方法[9]。該方法無需專門人員采集指紋數據就可建庫。這是一種利用群智感知的思想并結合機器學習與數據挖掘技術來完成指紋庫構建與更新。

2） 設備異質性。在指紋采集階段，使用不同的硬件設備在同一參考點采集到的指紋地圖是不同的。一種解決方法是通過使用其他比較穩健的位置特征如RSSI的信號強度差異SSD作為位置指紋，然而該方法增加了指紋的維度和計算復雜度。如果從減少校準成本和降低計算復雜度角度出發，嘗試利用機器學習解決設備異質性問題是個不錯的選擇。

參考文獻：

[1] 鄧中亮. 室內外無線定位與導航[M].北京郵電大學出版社，2013.

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

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

[4] 張會清， 石曉偉， 鄧貴華，等. 基于BP神經網絡和泰勒級數的室內定位算法研究[J].電子學報，2012， 40（9）：1876-1879.

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

[6] 朱宇佳， 鄧中亮， 劉文龍，等. 基于支持向量機多分類的室內定位系統[J].計算機科學， 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] 劉歡，黃麗，楊曉，等.一種貝葉斯優化RSSI和ILS的室內定位算法[J].中國科技論文，2015（20）：2377-2381.

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