李斌 張金煥 封靖川

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

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

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

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

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

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

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

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

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

1.1 KNN（K 鄰近法）算法

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

1.2 WKNN算法

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

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

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

2方法

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

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

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

2.2 XGBoost再分類

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

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

2.3 定位階段算法

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

輸入：RSS指紋庫(kù) ？？ = {？？1，？？2，...，？？？？，...，？？？？}，測(cè)試集RSS信息T = {？？1，？？2，...，？？？？，...，？？w}。

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

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

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

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

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

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

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

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

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

3實(shí)驗(yàn)與評(píng)價(jià)

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

本實(shí)驗(yàn)的數(shù)據(jù)集來(lái)源是來(lái)自阿里天池大數(shù)據(jù)平臺(tái)，數(shù)據(jù)集采集了兩個(gè)月20多個(gè)商場(chǎng)，平均每個(gè)商場(chǎng)近90個(gè)商鋪的RSS指紋數(shù)據(jù)，實(shí)驗(yàn)選取4個(gè)商場(chǎng)的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

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

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

3.3 實(shí)驗(yàn)結(jié)果比較評(píng)估

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

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

[2]銳，鐘榜，朱祖禮，馬樂(lè)，姚金飛.室內(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