基于GBDT的Wi-Fi室內(nèi)定位算法研究

劉付杰，馮 濤*，高秀敏

（1.杭州電子科技大學(xué)電子信息學(xué)院，杭州 310000；2.上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海 200000）

室內(nèi)定位技術(shù)是近些年研究的一個(gè)熱點(diǎn)。常見(jiàn)的全球定位系統(tǒng)GPS在戶外擁有非常好的定位效果，但是卻無(wú)法應(yīng)用于室內(nèi)。戶外的定位系統(tǒng)的可接受誤差在幾十米，而室內(nèi)定位的預(yù)期誤差則遠(yuǎn)遠(yuǎn)小于這個(gè)值，通常在幾米范圍之內(nèi)，甚至更小。當(dāng)前Wi-Fi指紋是用于室內(nèi)定位的一種流行方法，該方法建立將RSS向量回歸映射到水平坐標(biāo)上的模型。KNN和 RandomForest算法常被用于基于指紋的室內(nèi)定位中。但是由于墻壁的反射以及終端接入點(diǎn)位置環(huán)境的隨機(jī)性都可能引起信號(hào)強(qiáng)度的變化，這些變化意味著變量之間的高度非線性交互作用，基于決策樹(shù)的方法恰能很好地處理這種交互作用。考慮到這一點(diǎn)，本文決定將GBDT算法用于Wi-Fi指紋定位中，并測(cè)試它是否能夠改進(jìn)RandomForest算法獲得的定位結(jié)果。根據(jù)現(xiàn)有已知信息，該算法還未被用在室內(nèi)定位任務(wù)中。該算法將通過(guò)真實(shí)數(shù)據(jù)進(jìn)行定位測(cè)試，并與典型的室內(nèi)指紋定位算法KNN和RandomForest進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明：在有限的AP集中，GBDT算法擁有比KNN和RandomForest更好的定位結(jié)果，具有一定的研究意義。

1 GBDT算法介紹

1.1 GBDT算法原理

GBDT是一種以Gradient Boosting框架結(jié)合決策樹(shù)作為基學(xué)習(xí)器而構(gòu)成的可用于回歸和分類的機(jī)器學(xué)習(xí)算法。GBDT算法采用了一種貪心策略[1]，每次只訓(xùn)練一個(gè)基學(xué)習(xí)器，在訓(xùn)練基學(xué)習(xí)器的過(guò)程中，一種常用的方法叫做擬合殘差。假設(shè)算法模型發(fā)F（x；P）表示如下[2]：

式（1）中β表示每個(gè)基學(xué)習(xí)器模型的權(quán)重；α表示每個(gè)基學(xué)習(xí)器模型的參數(shù)，模型參數(shù)可用如下公式表示：

式（2）表示對(duì)于M個(gè)樣本點(diǎn)（xi，yi），計(jì)算其在模型F（x；P）下的損失函數(shù)，最優(yōu)解P可以使得損失函數(shù)最小。寫成梯度下降形式的表示如下：

式（3）計(jì)算的參數(shù)βn，αn，用于確保模型Fn（x）的方向是前一個(gè)模型Fn-1（x）損失函數(shù)下降最快的方向。對(duì)于每一個(gè)數(shù)據(jù)點(diǎn)xi，都可以得到一個(gè)gn（xi），最終可以得到一個(gè)完整的梯度下降方向：

為了確保Fn（x）能夠在gn（x）的方向上，可以使用最小二乘法優(yōu)化上面的公式得到：

計(jì)算得到αn的值后，可以計(jì)算得到βn，公式如下

最終合并的算法模型為：

上述介紹了GBDT算法的基本原理及框架，在后面的實(shí)驗(yàn)試驗(yàn)證中就將使用基于這一框架的算法模型。

2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

2.1 數(shù)據(jù)采集與處理

室內(nèi)定位的Wi-Fi指紋識(shí)別方法需要依靠測(cè)量的AP信號(hào)強(qiáng)度（RSS）建立的模型，定位過(guò)程中根據(jù)當(dāng)前接受AP信號(hào)強(qiáng)度結(jié)合建立的模型來(lái)確定當(dāng)前位置。為了確保實(shí)驗(yàn)數(shù)據(jù)的真實(shí)可靠以及最接近實(shí)際的工程應(yīng)用，實(shí)驗(yàn)數(shù)據(jù)選擇了某商場(chǎng)中的一個(gè)區(qū)域進(jìn)行采集。該區(qū)域?yàn)橐粋€(gè)長(zhǎng)12m，寬9.6m，高3m的長(zhǎng)方體，實(shí)驗(yàn)采集的AP信號(hào)強(qiáng)度數(shù)據(jù)全部來(lái)源于周邊商鋪提供的免費(fèi)AP熱點(diǎn)，AP熱點(diǎn)的位置分布是未知的。實(shí)驗(yàn)環(huán)境中人員的移動(dòng)，周圍建筑的不規(guī)性以及AP熱點(diǎn)位置的無(wú)規(guī)律性，都使得實(shí)驗(yàn)具有高度的泛化能力，更容易在實(shí)際工程中進(jìn)行應(yīng)用。

AP信號(hào)的收集使用的是型號(hào)為L(zhǎng)eMax2的手機(jī)作為無(wú)線終端硬件，使用自己編寫的軟件對(duì)周圍的13個(gè)AP信號(hào)進(jìn)行采集。測(cè)試區(qū)域被劃分為80個(gè)1.2×1.2m的小正方形塊，共得到了99個(gè)采集點(diǎn)，考慮到Wi-Fi信號(hào)的易變性，每個(gè)點(diǎn)都采集了300組數(shù)據(jù)，其中79個(gè)點(diǎn)采集的23700組數(shù)據(jù)將作為訓(xùn)練集用于模型的學(xué)習(xí)，剩余的20個(gè)點(diǎn)采集的6000組數(shù)據(jù)作為測(cè)試集用于對(duì)模型性能進(jìn)行測(cè)試評(píng)估。這里的每一條數(shù)據(jù)都由13個(gè)AP信號(hào)強(qiáng)度值和一個(gè)水平坐標(biāo)組成，存放形式如｛[rss1，rss2，…，rss13][x，y]｝，rssi（i∈[1，13]）表示在坐標(biāo)點(diǎn)（x，y）測(cè)得的第i個(gè)AP的信號(hào)強(qiáng)度值。

數(shù)據(jù)采集完成后，統(tǒng)計(jì)數(shù)據(jù)時(shí)發(fā)現(xiàn)每一個(gè)采集點(diǎn)所采集的AP信號(hào)數(shù)據(jù)都存在一定程度的缺失，周圍環(huán)境的短暫變化以及某些AP信號(hào)在傳播過(guò)程中過(guò)多衰減都會(huì)引起采集過(guò)程中信號(hào)強(qiáng)度值的丟失，采集點(diǎn)AP信號(hào)強(qiáng)度弱是導(dǎo)致數(shù)據(jù)缺失的主要原因，統(tǒng)計(jì)數(shù)據(jù)得到信號(hào)強(qiáng)度的變化區(qū)間是[-93，-30]，因此決定對(duì)缺失值采用補(bǔ)值處理，將數(shù)據(jù)集中的缺失值統(tǒng)一取值-100dbm。

2.2 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)數(shù)據(jù)在前面已經(jīng)做了說(shuō)明，23700組數(shù)據(jù)作為訓(xùn)練集，6000組數(shù)據(jù)作為測(cè)試集。下面將使用這些數(shù)據(jù)對(duì)KNN、Random-Forest以及上述的GBDT算法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中會(huì)使用控制變量法測(cè)試AP熱點(diǎn)個(gè)數(shù)對(duì)三種算法最終定位結(jié)果的影響。文章將使用平均定位結(jié)果，以及80%位定位結(jié)果來(lái)比較三種算法在指紋定位任務(wù)中的優(yōu)劣，仿真中使用的編程語(yǔ)言為Python3.6。

2.3 結(jié)果分析

首先，重復(fù)了KNN和RandomForest算法，并結(jié)合工程調(diào)參經(jīng)驗(yàn)，使KNN和RandomForest在采集的數(shù)據(jù)集中達(dá)到最優(yōu)定位結(jié)果。根據(jù)上面描述的GBDT算法模型，并對(duì)GBDT模型進(jìn)行了參數(shù)調(diào)優(yōu)。當(dāng)KNN、RandomForest和GBDT在除AP個(gè)數(shù)參數(shù)外，其他參數(shù)固定的情況下，三種算法定位誤差的均值和80%位值分別都隨著AP個(gè)數(shù)的增加而降低，即AP個(gè)數(shù)越多，定位結(jié)果越好，但是當(dāng)AP個(gè)數(shù)等于13時(shí)，三種算法的定位結(jié)果都比AP個(gè)數(shù)等于11時(shí)要差，以前面的結(jié)論相悖，在仔細(xì)分析了數(shù)據(jù)集之后，發(fā)現(xiàn)第13個(gè)AP采集數(shù)據(jù)的缺失值的個(gè)數(shù)要遠(yuǎn)遠(yuǎn)多于其他AP缺失值的個(gè)數(shù)。為了探究缺失值數(shù)量對(duì)定位結(jié)果的影響，決定選取一個(gè)缺失值只有7%的AP信號(hào)，通過(guò)增加其缺失值數(shù)量觀察定位誤差均值的變化，結(jié)果表明，當(dāng)AP缺失值占比超過(guò)30%時(shí)，對(duì)定位結(jié)果產(chǎn)生較大影響。即信號(hào)質(zhì)量差的AP并不會(huì)減小定位誤差，并且還會(huì)起得相反的作用。因此，可以總結(jié)為有限的AP集中，AP數(shù)量的增加可以減小定位誤差。這里的有限AP集包含的是AP信號(hào)缺失值占比不超過(guò)30%的AP。

三種算法在各自最優(yōu)參數(shù)下20個(gè)點(diǎn)的定位誤差的均值分別為KNN：2.299m、RF：2.15m和GBDT：1.8m，結(jié)果可以分析出，GBDT算法的定位結(jié)果在大多數(shù)情況下都要優(yōu)于KNN和Random-Forest算法，并且在三種算法定位結(jié)果都在各自最優(yōu)的情況下，GBDT定位誤差的均值1.89m分別比KNN的2.30m和Random-Forest的2.17m減小了17%和13%，GBDT定位誤差的80%位值能有效地控制在2.8m之內(nèi)，分別比KNN的3.4m和Random-Forest的3.1m的減小了18%和10%。

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

本文提出將GBDT算法應(yīng)用于室內(nèi)定位中，并且與KNN和RandomForest算法進(jìn)行了相比。結(jié)果表明，在有限的AP集中，GBDT算法能夠比KNN和RandomForest算法明顯的減小室內(nèi)定位的誤差，具有一定的研究?jī)r(jià)值。后續(xù)將把該算法用于實(shí)際的工程中，探索其在工程中的應(yīng)用價(jià)值。