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

徐龍陽(yáng)

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 概述

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

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

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

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

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

2.1KNN算法

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

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

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

KNN算法理論簡(jiǎn)單，K值對(duì)KNN算法定位性能影響很大，大部分優(yōu)化的KNN算法都是對(duì)K值進(jìn)行優(yōu)化。因?yàn)樗惴ㄐ枰闅v數(shù)據(jù)庫(kù)里所有樣本數(shù)據(jù)，因此對(duì)于數(shù)據(jù)量過(guò)大的數(shù)據(jù)庫(kù)使用KNN算法會(huì)有較大的計(jì)算量。endprint

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

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

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

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

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

2.3 支持向量機(jī)方法

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

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

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

2.4 決策樹方法

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

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

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

2.5 貝葉斯方法

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

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

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

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

3 定位方法的比較分析

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

（1） 提高定位精度

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

通過(guò)對(duì)基于機(jī)器學(xué)習(xí)的室內(nèi)定位方法學(xué)習(xí)研究，未來(lái)有一些值得深入研究的熱點(diǎn)問(wèn)題。

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

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

參考文獻(xiàn)：

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

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

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

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

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

[6] 朱宇佳， 鄧中亮， 劉文龍，等. 基于支持向量機(jī)多分類的室內(nèi)定位系統(tǒng)[J].計(jì)算機(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].中國(guó)科技論文，2015（20）：2377-2381.

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