基于聚類的W i-Fi與移動智能終端商場室內定位

周明，王曉峰

（上海海事大學信息工程學院，上海201306）

0 引言

在互聯網爆炸的時代，人們對位置信息的關注越來越多。基于位置的服務（Location Based Service,LBS）是指通過用戶當前定位信息，根據用戶需求為其提供相應的服務。LBS作為定位技術的核心，在導航、人員跟蹤、室外游戲、物流等諸多方面得到了應用，它能夠根據移動對象的位置信息提供個性化服務[1]。室外定位系統主要有四大衛星導航系統，分別為美國的GPS、俄羅斯的GLONASS系統、中國的北斗系統、歐盟的Galileo系統[2]。當今社會主流的室外定位技術之一是全球定位系統（Global Position System,GPS），其通過衛星獲取地理位置信息[3]。GPS擁有建設和運行時間長，技術成熟，性能穩定可靠，定位精度高，適應能力強，應用廣泛等優點，可以較好地滿足戶外定位需求，然而在封閉的室內，由于布局復雜和障礙物對信號的干擾嚴重等緣由，GPS通常不被使用在室內定位[4]；室內的定位技術有：①室內部署紅外線設備來定位的方法[5]；②室內部署超聲波設備來定位的設計方案[6]；③室內部署射頻設備來定位的方案[7-8]；④室內部署UWB設備來定位的方案[9-10]。雖然以上方法能得到較高的精度，但在實施前需要安裝昂貴的設備和定位前需要采集必需的位置信息，這就使得這幾種方法得不到普及[5]。

隨著Wi-Fi技術的成熟和無線網的普及，基于Wi-Fi的室內定位技術不斷成為研究熱點。Wi-Fi信號能被用于定位的特征有ID、強度、傳播時間、接受角度等。其中，基于Wi-Fi信號的接受強度指示（Re?ceived Signal Strength Indication）的應用尤為廣泛。根據采用的算法各異，定位模型可分為兩種：基于信號傳播模型的定位和基于位置指紋識別算法的定位[11]。

基于信號傳播模型的定位是對無線網的傳播信道進行建模，這種定位方式難度較大，因為需要用數學模型去擬合障礙物難以模擬的特征。基于位置指紋識別的定位方法通過提取指紋數據庫中的模式特征，與信號傳播模型不同，通過構建RSSI信息與位置信息之間的函數關系，降低定位的復雜度。

本文在基于位置指紋識別的定位算法研究傳統的K近鄰（K Nearest,KNN）方法在Wi-Fi定位中的應用，提出基于簇和KNN相結合的室內定位算法，并將兩者的定位效果進行比較。

1 定位算法

1.1 傳統指紋搜索算法

指紋算法是在復雜的室內環境下，針對特征參數有變動性而進行匹配的一種識別技術。該算法的實現分為離線階段和在線階段這兩個過程，如圖1所示。離線階段的主要內容是將訓練集數據按照映射關系存儲到數據庫中，在數據庫存儲著m×n的指紋庫矩陣，其存儲方式如表1，其中RSSij（i=1,2...,n;j=1,2,...,m）表示第j個APs在第i個檢測點的RSS值，其目的是為了讓在線階段更好地根據數據庫匹配數據。在線階段的目標是對未知位置的用戶進行位置估計，其做法是將該用戶的特征信息（在本文是RSS值），根據特定的匹配算法，在數據庫中搜尋特征與之最相似的特征點，然后將其歸于該類中。特定的匹配算法主要有K近鄰（K-Nearest Neighbor,KNN）、決策樹和支持向量機等算法。

機器學習算法之一的KNN算法，因其簡易且方便而被經常使用，其原理是通過計算未知類別樣本的特征信息與K個最相似的參考點，然后將未知類別的樣本歸于這K個最相似的點中，出現類別個數最多的那一類。

傳統定位匹配KNN算法過程如下：

（1）輸入要估計位置的數據r，計算其與各個訓練數據ri之間的相似度，其公式如下：

rij表示第j個Wi-Fi源到第i個點的信號強度；

（2）按照相似度大小順序進行排序；

（3）選取相似度最大的的K個已知類別的數據點；

（4）計算前K個點各類別點出現的次數；

（5）將未知類別點的預測類別定位前K個點中，出現頻率最高的類別[12]。

圖1 基于傳統指紋搜索算法的室內定位流程圖

該傳統的定位算法有一個必要的過程，就是在每執行一次KNN算法時，都需要遍歷數據庫中所有的APs，當然在匹配少數據量時，其匹配速度還可以接受，然而在匹配大量數據量時，要找出K個相似度最大的值，系統的時效性不容樂觀了。為解決這個系統時效性問題，本文將引入指紋簇的所搜方法，在保證室內定位的準確率情況下，能夠減少算法在匹配時搜索的數量，減少估計時間和計算量。

1.2 本文簇類指紋定位算法

（1）按經緯度聚類的指紋定位算法

本文簇類指紋定位算法的目標是在保證定位的準確率情況下，減少搜索的數據量，減少估計的時間和計算量，圖2是簇類指紋定位算法的流程圖。其工作模式和傳統定位算法的工作模式相同，也包含離線階段和在線階段，然而優勢之處是將訓練數據按使用K-means算法聚成簇后存儲在數據庫中。離線階段中，使用K-means方法把數據集分成不同簇，并把每個簇包含位置的無線網特征存儲在數據庫中。在線定位數據匹配時，先對數據進行簇匹配，然后進行指紋定位匹配。在線階段將未知位置的數據，使用分級的搜尋模式，先用KNN算法將其歸于簇類中，確定簇類，然后在簇類中使用傳統的指紋定位算法，將其所在的位置估計出來。

Means聚類方法：

K-means算法是機器學習中的無監督分類算法，它是根據距離來確定類別分類的，距離越大，其相似性越低，距離越小，其相似性越高。

具體如下：

輸入：k=97,data[n];

①隨機選擇97個初始中心點，例如c[0]=data[0],…c[k-1]=data[k-1];

②對于 data[0]….data[n]，分別與 c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i;

③對于所有標記為i點，重新計算中心坐標c[i]，n為該類所有實例數目

④重復②③，直到所有c[i]值的變化小于給定閾值或達到指定迭代次數。

簇類KNN算法實現：

①輸入要估計點r的經緯度值（W,S），計算其與各個訓練數據ri之間的相似度，其公式（3）如下：

W表示地球的經度值，S表示地球的緯度值，Wi表示第i個點的經度值，Si表示第i個點的緯度值；

②按照相似度大小順序進行排序；

③選取相似度最大的K個已知類別的數據點；

④計算前K個點各類別點出現的次數；

⑤將未知類別點的預測類別定位前K個點中，出現頻率最高的簇中[12]。

圖2 基于簇方法的定位流程圖

本方法雖然能夠在很大程度上減少定位時搜索的數量，提高系統的時效性，但是由于在按經緯度聚類時會出現歸類錯誤，導致在線定位階段出現無法定位的數據，從而降低定位的準確度。所以，就提高聚類的準確度，需要有所研究，下文提出根據無線網進行聚類。

（2）按無線網聚類的指紋定位算法

依據無線網發射器的識別碼具有唯一性的特性，本文提出一種根據無線網識別碼來聚類的方法，然后再使用上文的定位法進行定位。圖3是根據無線網識別碼分簇圖。而整個定位算法工作模式和基于KNN聚類的指紋定位算法的工作模式相同，也包含離線階段和在線階段，相對于基于K-means聚類的指紋定位算法的優勢在于按照無線網的識別碼來將數據進行簇類聚類，這樣可以提高聚類的正確率，然后將訓練數據按簇存儲在數據庫中，在數據匹配時，也是先按照無線網識別碼對數據進行簇匹配，然后進行指紋定位匹配。離線階段中，把數據集根據不同商場為簇來分開，并把每個簇包含位置的無線網特征存儲在數據庫中，呈現出一種分級存儲格式。在線階段將未知位置的數據，使用分級的搜尋模式，先根據無線網識別碼將其歸于簇類中，確定簇類，然后在簇類中使用KNN指紋定位算法，將其所在的位置預測出來。通過以上這種做法，可以極大地減少了遍歷數據庫中的數據個數，較少的計算量，達到可靠地系統時效性。

圖3 按識別碼分簇圖

理論分析本方法具有更好的聚類效果，能夠為在線定位提更高的數據匹配環境。

2 實驗與結果分析

2.1 數據清洗

本實驗數據來至阿里競賽數據集，97個不同的商場和54個店鋪類型在某月份的客戶發生交易行為的實際記錄，數據集包含兩部分，其中一部分是店鋪與商場的對應關系，記為U，擁有的字段如下：商場id，店鋪id，店鋪經緯度，店鋪類型，和消費金額，另一部分數據集是發生交易數據集，記為C，含有的字段如下：店鋪id，發生交易的時間，發生交易時的地球經緯度數值，發生交易時的Wi-Fi信號強度數值，用戶id。在數據集中，需刪除無意義的字段，如消費金額和用戶id。由于在智能終端（手機）定位時，定位往往會發生不準確的，偏離真實地點很遠的點，以及流動熱點的Wi-Fi情況，所以數據不能直接使用，需要對數據進行數據清洗，具體處理如下：

數據存儲方式轉換，原始的CSV格式的文件不好清洗，所以利用Navicat for MySQL把CSV格式的數據存到MySQL數據庫中。

數據處理，對數據做以下處理：

（1）由于智能終端性能等多方面因素，經緯度定位有偏離真實的數據，本數據的范圍是國內，把所有點映射到地圖上，可以確定把緯度高于50度和低于20度的數據清洗過濾，把經度低于100度高于130度的數據清洗過濾。

（2）將偏離點，單個點和聚類點數目個數聚集較少的點清洗過濾。

（3）如今的智能終端擁有開啟手機熱點的功能，這種熱點將會極大地影響精度的計算，取交易時Wi-Fi標識碼的交集，清洗過濾臨時的熱點Wi-Fi，將穩定的Wi-Fi標識碼作為店鋪的最終評判Wi-Fi。

（4）確定穩定Wi-Fi后，若某個數據Wi-Fi中沒有相對應的Wi-Fi識別碼，則將該Wi-Fi強度置0。

（5）把清洗好的數據集合理拆分，第二部分的數據集隨機分成1/3和2/3，數據集的1/3為測試集,記為C1，數據集的2/3訓練集，記為C2。

2.2 實驗結果與分析

為了驗證本文提出的簇類算法的系統時效性，將傳統算法和本文提出的兩種算法進行試驗對比，將清洗好的實驗數據輸入上三種方法進行實驗，得到實驗結果如圖4和表2展示，圖4中紅虛線代表傳統指紋算法的實驗結果圖，綠線為本文算法的實驗結果圖，rate為實驗的準確率，K_num是KNN的K值，K=1,2,3,4,5,6,7，表2為三種方法在線定位一次所需要的時間和在數據庫中搜索的數目比例。從圖中可知，傳統的指紋搜索方法準確率比本文提出的第一種方法的方法要好些，但兩者相差較小，但從表2中可知，本文提出的第一種方法在線階段所花費的時間比傳統方法的少了60%左右，搜索的數目也只占全部數據集的一部分，系統的時效性提高，計算量明顯減少；傳統方法相比較于本文提出的第三種方法，準確率兩者幾乎同等，但是在搜索時間和搜索數目上，本文第二種方法具有明顯的優勢，定位時間更短，搜索數目減少了59%左右。從實驗結果可知本文方法的理論與實踐皆優于傳統方法。

圖4 三種算法的實驗結果圖K_num是KNN的K取值，K=1,2,3,4,5,6,7，rate為實驗的準確率

表2 傳統方法與本文方法的定位耗時以及搜索數目

由圖3折線看出，當K=5時，本文的定位準確率達到最大，為此取K=5時，將數據集按1:2的比例隨機分配，繼續用本文方法對數據做4次實驗，得到四次結果，繪制圖5，count_num_k=3表示第三次實驗。從圖5中可知，這四次實驗的結果相對穩定，且第二種方法的準確度比第一種高些。

圖5 K=5的本文方法4次實驗結果

3 結語

本文通過介紹傳統指紋定位算法的介紹，剖析其算法原理，指出其系統時效性不足的問題，并針對問題提出本文的兩種簇指紋定位方法，將原始數據集按分級搜索，減少數據計算量，減少在線定位的時間，讓系統時效性更好，同時還保證定位的準確性。最后通過實驗來驗證所提方法的可行性，實驗結果得出：本文方法能夠減少算法在匹配時搜索的數量，減少估計時間和計算量，讓系統時效性讓人更能接受。