基于Minibatch-kMeans和XGBoost算法的大型場所WLAN室內(nèi)定位的方法

李斌 張金煥 封靖川

摘要：基于RSS的WLAN指紋定位算法，針對大型場所的室內(nèi)定位數(shù)據(jù)維數(shù)高，計算量大，定位精度不高的問題，本文提出一種基于先聚類再分類的方法.本文用Minibatch-kMeans先聚類分區(qū)定位，然后采用XGBoost分類算法在子區(qū)域精確定位，解決了大型場所室內(nèi)定位數(shù)據(jù)維數(shù)高，運算速度慢的問題，并提高了定位的精度。本文提出的算法具有很大的應(yīng)用價值和應(yīng)用前景。

關(guān)鍵詞：WLAN室內(nèi)定位; Minibatch-kMeans;XGBoost;數(shù)據(jù)降維

中圖分類號：TP212? ? 文獻標(biāo)識碼：A? 文章編號：1007-9416（2018）10-0000-00

越來越多的移動互聯(lián)網(wǎng)應(yīng)用希望可以獲得用戶的位置信息來對用戶提供更智能更精確的服務(wù)，目前相當(dāng)成熟的GPS技術(shù)僅僅限于用于室外。基于802.1lb/g/n協(xié)議的無線局域網(wǎng)被廣泛部署于全世界不用環(huán)境，如商場、寫字樓、機場大廳等，幾乎覆蓋了絕大多數(shù)人類活動的室內(nèi)環(huán)境。因此基于WiFi信號的室內(nèi)定位成為目前十分熱門和前景廣闊的研究方向。目前基于WiFi信號的定位定位方法中，大致可以分為幾何測距法和位置指紋法。由于位置指紋法無需提前獲取無線WiFi接入點的位置和定位精度高，因此成為目前更熱門的定位方法。

但是在實際應(yīng)用過程中，特別是針對于大型場所，位置指紋法仍然存在如下兩個挑戰(zhàn)：

（1）需要參考的AP（無線WiFi接入點）越來越多，如某大型商場可以檢測到10000個AP，因此位置指紋庫數(shù)據(jù)維數(shù)高，導(dǎo)致計算和存儲開銷十分巨大。

（2）如何研發(fā)出性能更好的匹配算法，取得更高的定位準(zhǔn)確率。因此，為了解決這兩個挑戰(zhàn)，本文提出一種基于結(jié)合MiniBatch-kMeans聚類和XGBoost分類算法的定位算法。

1 國內(nèi)外研究現(xiàn)狀

常用的指紋定位匹配算法有神經(jīng)網(wǎng)絡(luò)法、KNN法，加權(quán)K近鄰法等。這些算法都是基于RSS進行指紋的匹配或映射得到最終的定位位置。

1.1 KNN（K 鄰近法）算法

在KNN相似度匹配時，選取歐式距離最小的前K個點，將K個點的幾何質(zhì)心作為定位位置的估計。2000年微軟研究院P.Bahl等人提出RADAR定位系統(tǒng)就是應(yīng)用的KNN算法。

1.2 WKNN算法

WKNN法是KNN法的進一步改進，與KNN匹配算法相比.最大的不同在于選擇出歐式距離最小的前K個點后，按照每個參考點對定位點的貢獻程度，給每個參考點一個權(quán)值，最后將K個點加權(quán)質(zhì)心作為定位的估計位置。

1.3 深度學(xué)習(xí)法

深度學(xué)習(xí)的概念源于人工神經(jīng)網(wǎng)絡(luò)的研究。含多隱層的多層感知器就是一種深度學(xué)習(xí)結(jié)構(gòu)。深度學(xué)習(xí)通過組合低層特征形成更加抽象的高層表示屬性類別或特征，以發(fā)現(xiàn)數(shù)據(jù)的分布式特征表示。Gibran Felix等人應(yīng)用深度學(xué)習(xí)的方法來處理復(fù)雜環(huán)境中室內(nèi)定位的問題， 提高了算法的泛化能力，得到了較高的準(zhǔn)確率。

2方法

2.1 MiniBatch-kMeans先聚類分區(qū)

本文采用Mini-BatchKMeans聚類算法法來對數(shù)據(jù)進行分區(qū)降維處理。我們發(fā)現(xiàn)很多大型場所內(nèi)的一定區(qū)域范圍內(nèi)，只需部分AP即可實現(xiàn)定位，大部分AP在該區(qū)域內(nèi)獲取不到RSS信息，所以我們可以先對大型場所進行分區(qū)，剔除對該區(qū)域無用的AP，從而達到降維的效果。本文采用Mini-BatchKMeans的方法進行自動聚類分區(qū)。

算法在兩個主要步驟之間迭代。第一步，從數(shù)據(jù)集中隨機抽取b個樣本，形成一個小批量，然后將這些分配給最近的質(zhì)心。在第二步中，質(zhì)心被更新。與K-Means相反，這是在每個樣本的基礎(chǔ)上完成的。對于小批量中的每個樣品，指定的質(zhì)心通過將樣品的流動平均值和先前分配給該質(zhì)心的所有樣品進行更新。這具有降低質(zhì)心隨時間變化的速率的效果。執(zhí)行這些步驟直到達到收斂或預(yù)定次數(shù)的迭代。

2.2 XGBoost再分類

完成了聚類算法區(qū)域劃分后，就可以對于每個子區(qū)域用分類方法進行訓(xùn)練。運用XGBoost作為我們的分類器。XGBoost是一個端到端的可擴展算法系統(tǒng)，XGBoost就是基于GDBT，并對GDBT做了如下改進：（1）損失函數(shù)從平方損失推廣到二階可導(dǎo)的損失。GDBT擬合殘差可以逼近到真值，是因為使用了平方損失作為損失函數(shù)。XGBoost的方法是，將損失函數(shù)做泰勒展開到第二階，使用前兩階作為改進的殘差。（2）加入了正則化項在決策樹中，模型復(fù)雜度體現(xiàn)在樹的深度上。XGBoost使用了一種替代指標(biāo)，即葉子節(jié)點的個數(shù)來表示模型的復(fù)雜度。并通過正則化來限制模型的復(fù)雜度。（3）支持列抽樣。列抽樣是指，訓(xùn)練每棵樹時，是從特征抽取一部分來訓(xùn)練這棵樹，而不是使用所有特征。

XGBoost分類過程如下：步驟1：導(dǎo)入RSS訓(xùn)練數(shù)據(jù)進行訓(xùn)練，根據(jù)訓(xùn)練數(shù)據(jù)的特點，設(shè)置模型初始參數(shù)設(shè)置如：迭代數(shù)次、樹的最大深度、損失函數(shù)等。步驟2：用訓(xùn)練數(shù)據(jù)訓(xùn)練好的 XGBoost 模型，導(dǎo)入測試集，計算出測試集的結(jié)果。步驟3：統(tǒng)計測試集數(shù)據(jù)預(yù)測結(jié)果，若預(yù)測結(jié)果不理想，對XGBoost參數(shù)調(diào)整，重復(fù)1步，第2步，直到達到一定的預(yù)測準(zhǔn)確率。

2.3 定位階段算法

XGBoost模型訓(xùn)練好后，就對數(shù)據(jù)進行預(yù)測運算，先進行聚類分區(qū)預(yù)測，得到分區(qū)后，在該區(qū)域內(nèi)做XGBoost再分類預(yù)測，最終得到預(yù)測結(jié)果，定位預(yù)測階段的算法流程如下：

輸入：RSS指紋庫 ？？ = {？？1，？？2，...，？？？？，...，？？？？}，測試集RSS信息T = {？？1，？？2，...，？？？？，...，？？w}。

輸出：測試集預(yù)測結(jié)果

（1）For k=mink->maxk do? ?#枚舉區(qū)域個數(shù);

（2）MiniBatchKmeans（聚類個數(shù)=K，訓(xùn)練集T） #聚類訓(xùn)練;

（3）為每個區(qū)域建立RSS指紋庫;

（4）MiniBatchKmeans .Predict（T）? #聚類預(yù)測每條測試集所屬區(qū)域;

（5）XGboost.predict（Ti）#預(yù)測測試集位置結(jié)果;

（6）統(tǒng)計準(zhǔn)確率，比較每次的預(yù)測率，特征維數(shù)，運算時間找到最佳K的取值。

2.4 定位技術(shù)總流程

綜上所述，本文室內(nèi)方法分為離線訓(xùn)練階段和在線定位階段，定位技術(shù)與方法的總流程如圖1所示。

3實驗與評價

3.1實驗環(huán)境和數(shù)據(jù)

本實驗的數(shù)據(jù)集來源是來自阿里天池大數(shù)據(jù)平臺，數(shù)據(jù)集采集了兩個月20多個商場，平均每個商場近90個商鋪的RSS指紋數(shù)據(jù)，實驗選取4個商場的數(shù)據(jù)進行實驗。

3.2 數(shù)據(jù)預(yù)處理

（1）去除無用AP：由于數(shù)據(jù)集存在大量的移動熱點，我們通過篩選出現(xiàn)頻率大于5次并且出現(xiàn)天數(shù)大于一天的AP作為我們參考的AP。（2）歸一化處理：由于收集到的RSS數(shù)據(jù)分布在[-110，0]之間，不利于聚類和分類算法的收斂，我們對WiFi信號數(shù)據(jù)進行歸一化處理。

3.3 實驗結(jié)果比較評估

我們對不分區(qū)和分區(qū)方法在特征維數(shù)、定位準(zhǔn)確率、運行時間三方面進行比較，如表1。

我們發(fā)現(xiàn)分區(qū)算法在很大程度上降低了數(shù)據(jù)維數(shù)，縮短了運行的時間，并且仍然能保持較高的準(zhǔn)確率。將分類算法和KNN、神經(jīng)網(wǎng)絡(luò)算法進行比較，如表2所示我們發(fā)現(xiàn)我們的算法準(zhǔn)確率都在其他算法之上。

4結(jié)語

本文針對基于RSS的WLAN室內(nèi)定位在大型場所中的問題與挑戰(zhàn)，提出了先聚類分區(qū)再分類定位的方法，在分區(qū)階段使用Minibatch-kMeans聚類算法對數(shù)據(jù)進行了有效的降維，節(jié)省了約90%的運算時間;在分類定位階段首次使用XGBoost算法進行計算，并和KNN、神經(jīng)網(wǎng)絡(luò)算法進行比較，XGBoost算法在準(zhǔn)確率上有更優(yōu)的表現(xiàn)。

參考文獻

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

[2]銳，鐘榜，朱祖禮，馬樂，姚金飛.室內(nèi)定位技術(shù)及應(yīng)用綜述[J].電子科技，2014，27（03）：154-157.

[3]Chen T， He T， Benesty M. Xgboost： extreme gradient boosting[J]. R package version 0.4-2，2015： 1-4.

WLAN Indoor Localization Method with Minibatch-KMeans and XGBoost

LI Bin，ZHANG Jin-huan，F(xiàn)ENH Jing-chuan

（Central South University， Changsha Hunan? 410000）

Abstract：Based on the WLAN fingerprint localization algorithm ， this paper proposes a method based on pre-cluster classification algorithm ， which is implemented by Minibatch-KMeans clustering and XGBoost classification algorithm. It solve the problem of large-scale data dimension ，problem of slow operation speed and improved positioning accuracy. The algorithm proposed in this paper has great application value and prospects.

Key words：WLAN fingerprint localization;Minibatch-KMeans;XGBoost;Dimensionality reduction