基于XGBoost的客戶所在店鋪WiFi定位技術研究

(1.上海交通大學 模具CAD國家工程研究中心，上海 200030;2.東莞市橫瀝模具科技產業發展有限公司，廣東 東莞 523460)

0 引言

隨著移動互聯網計算平臺的迅速普及，根據不同的場景實時精確地推送相關信息，已經成為一項增強用戶體驗友好度并提升商業信息服務水平的有效策略。此應用對面向移動大數據的推薦算法提出了精度更高且具可操作性的要求，在恰當的時間和地點向用戶提供最具針對性的服務，是諸多通訊與互聯網企業智能化拓展的新目標。

隨著城市功能的發展，室內場景日趨復雜，商業場所對于定位及監控相關需求也逐漸深入。如大型超市可以基于客戶定位信息提供引流導購營銷服務。醫療機構可以快速調用相關醫療資源，同時對特殊病患進行定位監護，以提高患者就醫及醫務人員診療效率。在通訊技術覆蓋日益全面的情況下，室內定位諸多行業均展現出了廣闊的應用前景。目前，室內定位技術如WiFi、藍牙、RFID、紅外等得到了廣泛的研究與開發，為眾多室內定位應用提供了諸多行之有效的位置服務方案，成為智能城市的有效組成與標準配置。

1 基于WiFi信號的移動定位

通過手機等移動設備攜帶的信息精確定位用戶位置信息是室內智能應用中關鍵的一環，WiFi信號獲取、大數據分析以及數據挖掘是當前完成此項功能的有效途徑之一。

在真實商業場景測試實驗中，手機等移動端在室內復雜環境中經常存在定位信號模糊、環境信息不全、店鋪數據缺失、不同店鋪空間距離太近等諸多挑戰[1]，因此很難精準地確定移動中的用戶所在商鋪。隨著WiFi在室內環境中的廣泛部署，以及智能移動設備的普及，使得WiFi具有作為主要定位介質的技術成為可能[2]。

室內環境的復雜性導致信號被遮擋或者產生多徑效應，引起的接受誤差是影響定位效果的主要原因。另外信號接收端和發射端的硬件差異和穩定性也會造成定位誤差。所以在進行室內定位的時候，必須考慮到上述因素的影響[3]。

基于WiFi的室內定位技術主要包括幾何特征法、鄰近信息法和場景分析法。幾何特征法將信號強度轉換為距離，再使用幾何原理進行定位。當信號穩定，傳播時不受到干擾時可以達到較好的定位效果，但室內應用環境的復雜和信號的波動影響了它的定位精度。鄰近信息法利用信號作用范圍來確定參考點，但只能判斷定位點是否在參考點的附件，定位精度不高。場景分析法利用待測點的可測量特征來進行定位，有效利用了各類位置信息，可以在復雜室內環境中取得理想的定位精度，擁有較好的實用價值，因此被廣泛的研究和應用[4]。場景分析法首先要收集大量的位置信息構建“指紋庫”，在定位時系統會將測量所處位置的“指紋”和“指紋庫”的數據進行信息匹配，即可獲取待測點的位置[5]。現在較為主流的一類匹配方式是通過歐氏距離或馬氏距離，在指紋庫中選出距離最小的位置信息，被稱為確定性方法。這種方法受信號穩定性影響大，定位精度低。另一種是通過在此類方法基礎上加入一些先進的機器學習算法來改進這些問題，比如SVM[6]或模糊邏輯[7]等。

總體而言，由于實現難度適中、成本相對較低、定位精度較高及穩定性好等優點，基于位置指紋的WiFi室內定位技術已經成為目前研究的熱點方法之一。本文針對位置指紋進行了深入的分析，提出了一種基于XGBoost算法的位置指紋法，通過XGBoost學習器對采集到的真實店鋪和用戶交易數據進行離線訓練，建立位置指紋庫，然后根據用戶信息進行實時定位。實驗證明，XGBoost算法具有較好的分類能力，相對傳統的最近鄰算法，本文提出的方法取得了較高的WiFi信號定位精度。

2 位置指紋法基本原理

2.1 定位基本階段

位置指紋指的是某個位置與可測量物理刺激相關物理量之間的關系，把實際環境中的位置和某種“指紋”聯系起來，一個位置對應一個獨特的指紋。基于位置指紋法的定位可以分為離線訓練和在線定位兩個階段[8]。

1)離線訓練階段建立位置指紋庫，首先確定區域中一系列的測試參考點，然后在各個參考點采集足夠數量的AP信號樣本，對這些樣本進行篩選加工(通常去除異常值后使用取均值)作為此參考點的AP信號特征參數，并且在位置指紋數據庫中進行記錄，即為位置指紋地圖。

2)在線定位階段在測得某處的信號特征參數后，依據實時測得的信號數據與位置指紋數據庫中記錄進行匹配，獲得位置信息，進而實現定位。

2.2 最近鄰算法

隨著對于位置指紋法的定位技術研究的深入，匹配算法中最早在RADAR定位系統中提出最近鄰算法(NN, Nearest Neighbor)[9]是一種最基本的確定性匹配算法。最近鄰算法根據向量間的極大似然理論，它通過計算實測信號強度和含有信號強度以及位置信息的數據庫中樣本的相似度，來評估該接收信號強度可能的位置[10]。這種算法會在指紋數據庫中搜索與實測信號信息最匹配的數據點，取該樣本的位置作為定位估計值。

對于空間環境十分復雜的室內情況，并非所有的位置指紋都可靠，更復雜的指紋庫可能還包括了RSSI (Received Signal Strength Index)的標準差信息，或者賦予每個AP不同的權值，這樣需要使用加權的歐氏距離，如對整個指紋加一個權值，或者對指紋的系列特征分別加權值[11]。Brunato M和Battiti R提出了一個權值設計方式[12]，可使加權K近鄰算法的定位精度比K近鄰算法有一定的性能提升。但這種匹配算法計算過程復雜，工作量大，不適用于實時精確定位。目前部分商用WiFi接收器可以提供信道相關信息，利用該信息建立指紋庫進行定位，可以有效地提高定位精度。本文在前述特征研究的基礎上，針對位置指紋法中學習及分類方案進行了深入分析比較，采用基于XGBoost算法的WiFi指紋定位法。

3 基于XGBoost的位置指紋法

3.1 XGBoost算法

Boosting分類器屬于集成學習算法，它采用了加法模型，其基本思想是把成百上千個分類準確率較低的弱分類器組合形成一個準確率較高的強分類器。以決策樹為基本分類器的Boosting方法稱為提升樹(Boosting Tree)，該模型不斷迭代，每次迭代生成一棵新的提升樹，在每步生成合理的提升樹是Boosting分類器的關鍵[13]。

提升樹可以定義為一種使用前向分布算法的決策樹加法模型。首先定義初始提升樹f0(x)=0，而第m步的模型定義為：

fm(x)=fm-1(x)+T(x;Θm)

(1)

其中:fm-1(x)為當前模型，通過極小化風險來確定下一棵決策樹的參數Θm：

(2)

若損失函數為平方或指數函數時，每步優化都較為簡單，但對一般損失函數進行優化則比較困難。針對這一問題，Freidman提出了梯度提升(Gradient Boosting)算法[14]。

它用了當前模型損失函數負梯度的值作為提升樹算法的殘差近似值，使每一棵樹的迭代都會降低整體的損失，T(x;Θm) 的擬合目標值如下：

(3)

通過損失函數負梯度的擬合來優化損失函數，朝著最小化給定目標函數的方向逼近。在參數合理設置下，需要生成一定數量的樹才能達到預期準確率，另外在數據集龐大且較復雜的時候，Gradient Boosting算法的計算量巨大。

XGBoost[15]是Gradient Boosting算法的快速實現，能充分利用CPU的多線程進行并行計算，并通過使用損失函數的二階泰勒展開對算法加以改進以提高精度。XGBoost的基礎學習器包括常用的樹模型或線性模型，可以進行分類和回歸的預測，采用了深度學習中的dropout技術[16]在訓練的過程中隨機采用數據和特征防止過擬合，具有可擴展性、不易過擬合等特點，并能分布式處理高維稀疏特征。另外XGBoost算法在訓練之前，預先對數據進行排序，然后保存為block結構，后面的迭代中重復地使用這個結構，從而極大減小了計算量。XGBoost有多種實現，本文采用XGBoost算法的Python版本進行分類建模與計算。

3.2 基于XGBoost的定位算法

改進的基于XGBoost算法的位置指紋法同樣分為2個階段，離線訓練階段和在線定位階段。在訓練階段，首先將數據對象進行預處理使數據標準化，然后利用XGBoost算法對標準化數據進行分類，根據分類的結果調整XGBoost算法的輸入參數，獲得最優的多分類模型。在定位階段，對每一個新測數據進行標準化，然后輸入訓練好的多分類模型，運用XGBoost算法進行分類。本方法詳細的算法流程圖包括三個階段：數據采集，訓練和定位結果顯示，如圖1所示。

圖1 基于XGBoost的定位算法

使用XGBoost算法作為位置指紋法的匹配算法，由于采用了Boosting的方法相比于KNN較大的提升了準確度，同時使用訓練好的模型能進行即時精確定位。

通過XGBoost算法對位置和WiFi信號數據之間的映射關系進行離線學習，構建高精度指紋庫。同時為了獲取更好的定位效果，將位置離散化，對商場不同位置使用商鋪ID作為唯一標識，指紋庫如表1所示。

表1 WiFi信號指紋庫

表1中Yi為第i個樣本所在位置離散后的唯一標識ID，APj為整個定位區域內第j個AP，Xij為第i個樣本所在位置接受到APj信號的強度值，無信號的AP用默認值填充。

XGBoost算法通過構建多棵決策樹來構建指紋庫，其思想是通過位置離散化將定位問題轉化為多分類問題，每個位置對應一種類別。然后對樣本進行訓練，將每個決策樹的結果融合得到最終的分類結果。利用XGBoost算法構建指紋庫的步驟如下：

1)選取某一位置作為采樣點，采集WiFi信號數據作為一個樣本的全部特征。對特征進行列采樣，利用貪婪算法根據“損失函數最小”原則來尋找最優分裂點，將使損失函數值最小的WiFi特征及該特征下的信號強度值作為本次分裂的分裂點。

2)為了防止構建的指紋庫模型過于復雜，出現過擬合現象，即該模型對訓練數據可以獲得較高的定位準確率，而在線定位時準確率率低，需要對結點的每次分裂進行限制。只有當增益大于閾值的時候才進行分裂，同時當一棵樹到達最大深度停止繼續分裂。

3)在生成決策樹時，使用Gradient Boosting算法促使預測結果不斷逼近真實結果。通過多棵決策樹的學習，完成離線訓練。在定位階段，首先對每一個新測WiFi數據進行標準化，然后輸入訓練好的多分類模型，應用XGBoost算法進行定位。

4 基于XGBoost的定位實驗及分析

4.1 測試數據構成

本文所有數據均來自阿里天池比賽的商場中精確定位用戶所在店鋪賽題的真實采集數據集。當用戶使用移動支付方式付費時，后臺采集了此時手機的狀態(用戶ID、時間、GPS定位、WiFi信號強度及連接)和被掃碼的商店的信息(商店ID、商場ID、商店消費水平、商店位置)。采集到的具體信息如下圖表2和表3所示。

表2 用戶在店鋪內交易表

表3 店鋪商場信息表

商場中精確定位用戶所在店鋪數據庫提供的2017年8月份各類交易信息，一共包含1138015條數據。為了保證數據集在時間上可能出現的周期性，本文將8月1日至24日的數據作為訓練集，剩余7天作為測試集驗證算法效果，表4展示數據集的基本信息。

表4 數據量

選取用戶在店鋪內交易表和店鋪商場信息表中商場ID為m_7168的部分數據的經緯度信息，使用QGIS桌面地理信息系統對數據進行可視化，可視化效果如圖2。黑色三角形是不同店鋪的真實經緯度定位，而彩色圓點為商場交易發生時收集到的手機定位的經緯度定位，相同顏色的圓點則為同一個店鋪。

圖2 商場m_7168的經緯度定位可視化

圖2采用的是GPS經緯識別。雖然GPS在室外定位中取得了極大的成功，但由于室內環境復雜，存在各種遮擋信號的障礙物，導致GPS接收機難以接收到足夠強度的衛星信號，引起較大的定位偏差。圖2也反映了在商場內手機GPS定位結果與真實經緯度存在較大偏差。另外，GPS信號存在異常值，且不同商店的GPS重疊嚴重，呈現出聚集狀態，其中有些聚集的數據甚至可以呈現出商場清晰輪廓。這說明在室內定位中，GPS定位只能作為輔助提供一些定位信息。

4.2 數據處理

首先對原始數據進行預處理以滿足XGBoost算法的輸入要求。此外為了避免臨近商場的影響提高定位精度，減少預測模型的復雜度，我們分別對每個商場各自訓練一個預測模型。數據處理主要分為幾個步驟。

1)提取訓練集中每個商場中所有WiFi的ID作為特征，為了避免個人移動熱點的影響，剔除出現次數少于10的WiFi的ID。

2)提取訓練集中每條數據的WiFi信息，將出現的WiFi強度作為對應的WiFi的特征值，一般WiFi的信號強度范圍是[-90，-30]dBm，我們對特征向量中的缺失值使用-999來填充，為此確保搜到的WiFi的重要性。

3)以訓練集中每條數據的shop_id作為類標簽，優化目標是降低多分類錯誤率。

4.3 模型訓練

將預處理后的數據輸入到XGBoost模型中進行訓練，為了既不影響模型的收斂速度，又有較好的定位準確率，采用的模型參數如表5所示。訓練樣本由WiFi強度值和shop_id標簽組成，通過WiFi強度值去訓練一棵決策樹，將葉子節點的結果分類到樣本的標簽上。雖然參數對決策樹的樹深做了限制，存在分類錯誤的情況，但由于XGBoost模型采用了Boosting的集成學習方法，模型會將分類的誤差作為下一輪決策樹的擬合值。eta參數相當于學習速率，在進行完一次迭代后，會將葉子節點的權重乘上該系數，其目的主要是為了削弱每棵樹的影響，讓后面訓練的決策樹有更大的學習空間。通過多輪的迭代，XGBoost訓練的目標函數的分類結果將始終逼近真實的標簽，從而提高WiFi的定位精度。

表5 XGBoost模型參數

4.4 實驗結果

對比其他WiFi定位算法，定位的準確率是重要的性能指標，也就是預測的shop_id是否和標準答案的shop_id相等，準確率等于預測正確的樣本總數除以總樣本數。在本文中，總樣本為測試集8月25日至8月31日的數據，其中的shop_id列為標準答案，其他列均可用于預測shop_id。

對基于KNN和基于XGBoost模型的位置指紋法的準確率進行比較可知，在相同的樣本個數(288510)時，根據WiFi強度信息，基于XGBoost算法的定位準確率(87.82%)明顯高于傳統的基于KNN的算法(79.43%)。

XGBoost算法的優越性還體現在它的可擴展性，它能將其他含有較低信息量的特征利用起來，進一步組合提高定位的準確率，如表6所示。

表6 使用經緯度和WiFi特征的預測結果

由表6可知，雖然僅使用經緯度特征定位存在較大偏差，準確率只有66.52%，但是可以在WiFi強度特征的基礎上加入經緯度特征，進一步提高定位的準確性。

由以上結果可以看出，改進后的基于XGBoost算法的位置指紋法相比于傳統的基于最近鄰算法的位置指紋法有著巨大的提升。同時XGBoost算法還可通過特征工程進一步挖掘數據價值，提高定位的準確率。在離線訓練階段，XGBoost可以自動利用CPU的多線程進行并行，有著良好的訓練速度。在線定位階段，算法的時間復雜度為O(1)，平均每條數據所需的預測時間為0.23 ms(Intel i5-6400 CPU)，基本可以忽略，因此本文基于XGBoost算法的位置指紋法可以實現實時室內定位功能。

5 結束語

針對室內復雜環境和WiFi信號強度的變化特點，本文提出了一種基于XGBoost算法的位置指紋法。在離線學習階段，我們訓練集數據訓練預測模型。在線定位階段，我們將測試集的WiFi信息，輸入預測模型，進行實時定位。實驗結果表明，該方法相對傳統的基于最近鄰算法的位置指紋法，具有可靠性強、精度高等優點，可以應用于復雜室內環境的實時定位。

由于室內空間復雜的信道環境和空間拓撲關系，給室內定位帶來很大的挑戰，單一的定位源終究存在一定的局限。目前室內定位技術的發展趨勢包含如下三個方面：探索新的定位源，形成高精度高可用定位技術；異源異構定位源的高效融合；基于GIS的語義約束定位和語義認知協同定位。這將是本文后續工作的重點研究方向。