基于GBDT的Wi-Fi室內定位算法研究

劉付杰，馮 濤*，高秀敏

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

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

1 GBDT算法介紹

1.1 GBDT算法原理

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

式（1）中β表示每個基學習器模型的權重；α表示每個基學習器模型的參數，模型參數可用如下公式表示：

式（2）表示對于M個樣本點（xi，yi），計算其在模型F（x；P）下的損失函數，最優解P可以使得損失函數最小。寫成梯度下降形式的表示如下：

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

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

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

最終合并的算法模型為：

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

2 實驗設計與結果分析

2.1 數據采集與處理

室內定位的Wi-Fi指紋識別方法需要依靠測量的AP信號強度（RSS）建立的模型，定位過程中根據當前接受AP信號強度結合建立的模型來確定當前位置。為了確保實驗數據的真實可靠以及最接近實際的工程應用，實驗數據選擇了某商場中的一個區域進行采集。該區域為一個長12m，寬9.6m，高3m的長方體，實驗采集的AP信號強度數據全部來源于周邊商鋪提供的免費AP熱點，AP熱點的位置分布是未知的。實驗環境中人員的移動，周圍建筑的不規性以及AP熱點位置的無規律性，都使得實驗具有高度的泛化能力，更容易在實際工程中進行應用。

AP信號的收集使用的是型號為LeMax2的手機作為無線終端硬件，使用自己編寫的軟件對周圍的13個AP信號進行采集。測試區域被劃分為80個1.2×1.2m的小正方形塊，共得到了99個采集點，考慮到Wi-Fi信號的易變性，每個點都采集了300組數據，其中79個點采集的23700組數據將作為訓練集用于模型的學習，剩余的20個點采集的6000組數據作為測試集用于對模型性能進行測試評估。這里的每一條數據都由13個AP信號強度值和一個水平坐標組成，存放形式如｛[rss1，rss2，…，rss13][x，y]｝，rssi（i∈[1，13]）表示在坐標點（x，y）測得的第i個AP的信號強度值。

數據采集完成后，統計數據時發現每一個采集點所采集的AP信號數據都存在一定程度的缺失，周圍環境的短暫變化以及某些AP信號在傳播過程中過多衰減都會引起采集過程中信號強度值的丟失，采集點AP信號強度弱是導致數據缺失的主要原因，統計數據得到信號強度的變化區間是[-93，-30]，因此決定對缺失值采用補值處理，將數據集中的缺失值統一取值-100dbm。

2.2 實驗設計

實驗數據在前面已經做了說明，23700組數據作為訓練集，6000組數據作為測試集。下面將使用這些數據對KNN、Random-Forest以及上述的GBDT算法進行仿真實驗。實驗中會使用控制變量法測試AP熱點個數對三種算法最終定位結果的影響。文章將使用平均定位結果，以及80%位定位結果來比較三種算法在指紋定位任務中的優劣，仿真中使用的編程語言為Python3.6。

2.3 結果分析

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

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

3 結束語

本文提出將GBDT算法應用于室內定位中，并且與KNN和RandomForest算法進行了相比。結果表明，在有限的AP集中，GBDT算法能夠比KNN和RandomForest算法明顯的減小室內定位的誤差，具有一定的研究價值。后續將把該算法用于實際的工程中，探索其在工程中的應用價值。