基于聚類的W i-Fi與移動(dòng)智能終端商場(chǎng)室內(nèi)定位

周明，王曉峰

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0 引言

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

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

基于信號(hào)傳播模型的定位是對(duì)無(wú)線網(wǎng)的傳播信道進(jìn)行建模，這種定位方式難度較大，因?yàn)樾枰脭?shù)學(xué)模型去擬合障礙物難以模擬的特征?；谖恢弥讣y識(shí)別的定位方法通過(guò)提取指紋數(shù)據(jù)庫(kù)中的模式特征，與信號(hào)傳播模型不同，通過(guò)構(gòu)建RSSI信息與位置信息之間的函數(shù)關(guān)系，降低定位的復(fù)雜度。

本文在基于位置指紋識(shí)別的定位算法研究傳統(tǒng)的K近鄰（K Nearest,KNN）方法在Wi-Fi定位中的應(yīng)用，提出基于簇和KNN相結(jié)合的室內(nèi)定位算法，并將兩者的定位效果進(jìn)行比較。

1 定位算法

1.1 傳統(tǒng)指紋搜索算法

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

機(jī)器學(xué)習(xí)算法之一的KNN算法，因其簡(jiǎn)易且方便而被經(jīng)常使用，其原理是通過(guò)計(jì)算未知類別樣本的特征信息與K個(gè)最相似的參考點(diǎn)，然后將未知類別的樣本歸于這K個(gè)最相似的點(diǎn)中，出現(xiàn)類別個(gè)數(shù)最多的那一類。

傳統(tǒng)定位匹配KNN算法過(guò)程如下：

（1）輸入要估計(jì)位置的數(shù)據(jù)r，計(jì)算其與各個(gè)訓(xùn)練數(shù)據(jù)ri之間的相似度，其公式如下：

rij表示第j個(gè)Wi-Fi源到第i個(gè)點(diǎn)的信號(hào)強(qiáng)度；

（2）按照相似度大小順序進(jìn)行排序；

（3）選取相似度最大的的K個(gè)已知類別的數(shù)據(jù)點(diǎn)；

（4）計(jì)算前K個(gè)點(diǎn)各類別點(diǎn)出現(xiàn)的次數(shù)；

（5）將未知類別點(diǎn)的預(yù)測(cè)類別定位前K個(gè)點(diǎn)中，出現(xiàn)頻率最高的類別[12]。

圖1 基于傳統(tǒng)指紋搜索算法的室內(nèi)定位流程圖

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

1.2 本文簇類指紋定位算法

（1）按經(jīng)緯度聚類的指紋定位算法

本文簇類指紋定位算法的目標(biāo)是在保證定位的準(zhǔn)確率情況下，減少搜索的數(shù)據(jù)量，減少估計(jì)的時(shí)間和計(jì)算量，圖2是簇類指紋定位算法的流程圖。其工作模式和傳統(tǒng)定位算法的工作模式相同，也包含離線階段和在線階段，然而優(yōu)勢(shì)之處是將訓(xùn)練數(shù)據(jù)按使用K-means算法聚成簇后存儲(chǔ)在數(shù)據(jù)庫(kù)中。離線階段中，使用K-means方法把數(shù)據(jù)集分成不同簇，并把每個(gè)簇包含位置的無(wú)線網(wǎng)特征存儲(chǔ)在數(shù)據(jù)庫(kù)中。在線定位數(shù)據(jù)匹配時(shí)，先對(duì)數(shù)據(jù)進(jìn)行簇匹配，然后進(jìn)行指紋定位匹配。在線階段將未知位置的數(shù)據(jù)，使用分級(jí)的搜尋模式，先用KNN算法將其歸于簇類中，確定簇類，然后在簇類中使用傳統(tǒng)的指紋定位算法，將其所在的位置估計(jì)出來(lái)。

Means聚類方法：

K-means算法是機(jī)器學(xué)習(xí)中的無(wú)監(jiān)督分類算法，它是根據(jù)距離來(lái)確定類別分類的，距離越大，其相似性越低，距離越小，其相似性越高。

具體如下：

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

①隨機(jī)選擇97個(gè)初始中心點(diǎn)，例如c[0]=data[0],…c[k-1]=data[k-1];

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

③對(duì)于所有標(biāo)記為i點(diǎn)，重新計(jì)算中心坐標(biāo)c[i]，n為該類所有實(shí)例數(shù)目

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

簇類KNN算法實(shí)現(xiàn)：

①輸入要估計(jì)點(diǎn)r的經(jīng)緯度值（W,S），計(jì)算其與各個(gè)訓(xùn)練數(shù)據(jù)ri之間的相似度，其公式（3）如下：

W表示地球的經(jīng)度值，S表示地球的緯度值，Wi表示第i個(gè)點(diǎn)的經(jīng)度值，Si表示第i個(gè)點(diǎn)的緯度值；

②按照相似度大小順序進(jìn)行排序；

③選取相似度最大的K個(gè)已知類別的數(shù)據(jù)點(diǎn)；

④計(jì)算前K個(gè)點(diǎn)各類別點(diǎn)出現(xiàn)的次數(shù)；

⑤將未知類別點(diǎn)的預(yù)測(cè)類別定位前K個(gè)點(diǎn)中，出現(xiàn)頻率最高的簇中[12]。

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

本方法雖然能夠在很大程度上減少定位時(shí)搜索的數(shù)量，提高系統(tǒng)的時(shí)效性，但是由于在按經(jīng)緯度聚類時(shí)會(huì)出現(xiàn)歸類錯(cuò)誤，導(dǎo)致在線定位階段出現(xiàn)無(wú)法定位的數(shù)據(jù)，從而降低定位的準(zhǔn)確度。所以，就提高聚類的準(zhǔn)確度，需要有所研究，下文提出根據(jù)無(wú)線網(wǎng)進(jìn)行聚類。

（2）按無(wú)線網(wǎng)聚類的指紋定位算法

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

圖3 按識(shí)別碼分簇圖

理論分析本方法具有更好的聚類效果，能夠?yàn)樵诰€定位提更高的數(shù)據(jù)匹配環(huán)境。

2 實(shí)驗(yàn)與結(jié)果分析

2.1 數(shù)據(jù)清洗

本實(shí)驗(yàn)數(shù)據(jù)來(lái)至阿里競(jìng)賽數(shù)據(jù)集，97個(gè)不同的商場(chǎng)和54個(gè)店鋪類型在某月份的客戶發(fā)生交易行為的實(shí)際記錄，數(shù)據(jù)集包含兩部分，其中一部分是店鋪與商場(chǎng)的對(duì)應(yīng)關(guān)系，記為U，擁有的字段如下：商場(chǎng)id，店鋪id，店鋪經(jīng)緯度，店鋪類型，和消費(fèi)金額，另一部分?jǐn)?shù)據(jù)集是發(fā)生交易數(shù)據(jù)集，記為C，含有的字段如下：店鋪id，發(fā)生交易的時(shí)間，發(fā)生交易時(shí)的地球經(jīng)緯度數(shù)值，發(fā)生交易時(shí)的Wi-Fi信號(hào)強(qiáng)度數(shù)值，用戶id。在數(shù)據(jù)集中，需刪除無(wú)意義的字段，如消費(fèi)金額和用戶id。由于在智能終端（手機(jī)）定位時(shí)，定位往往會(huì)發(fā)生不準(zhǔn)確的，偏離真實(shí)地點(diǎn)很遠(yuǎn)的點(diǎn)，以及流動(dòng)熱點(diǎn)的Wi-Fi情況，所以數(shù)據(jù)不能直接使用，需要對(duì)數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，具體處理如下：

數(shù)據(jù)存儲(chǔ)方式轉(zhuǎn)換，原始的CSV格式的文件不好清洗，所以利用Navicat for MySQL把CSV格式的數(shù)據(jù)存到MySQL數(shù)據(jù)庫(kù)中。

數(shù)據(jù)處理，對(duì)數(shù)據(jù)做以下處理：

（1）由于智能終端性能等多方面因素，經(jīng)緯度定位有偏離真實(shí)的數(shù)據(jù)，本數(shù)據(jù)的范圍是國(guó)內(nèi)，把所有點(diǎn)映射到地圖上，可以確定把緯度高于50度和低于20度的數(shù)據(jù)清洗過(guò)濾，把經(jīng)度低于100度高于130度的數(shù)據(jù)清洗過(guò)濾。

（2）將偏離點(diǎn)，單個(gè)點(diǎn)和聚類點(diǎn)數(shù)目個(gè)數(shù)聚集較少的點(diǎn)清洗過(guò)濾。

（3）如今的智能終端擁有開啟手機(jī)熱點(diǎn)的功能，這種熱點(diǎn)將會(huì)極大地影響精度的計(jì)算，取交易時(shí)Wi-Fi標(biāo)識(shí)碼的交集，清洗過(guò)濾臨時(shí)的熱點(diǎn)Wi-Fi，將穩(wěn)定的Wi-Fi標(biāo)識(shí)碼作為店鋪的最終評(píng)判Wi-Fi。

（4）確定穩(wěn)定Wi-Fi后，若某個(gè)數(shù)據(jù)Wi-Fi中沒有相對(duì)應(yīng)的Wi-Fi識(shí)別碼，則將該Wi-Fi強(qiáng)度置0。

（5）把清洗好的數(shù)據(jù)集合理拆分，第二部分的數(shù)據(jù)集隨機(jī)分成1/3和2/3，數(shù)據(jù)集的1/3為測(cè)試集,記為C1，數(shù)據(jù)集的2/3訓(xùn)練集，記為C2。

2.2 實(shí)驗(yàn)結(jié)果與分析

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

圖4 三種算法的實(shí)驗(yàn)結(jié)果圖K_num是KNN的K取值，K=1,2,3,4,5,6,7，rate為實(shí)驗(yàn)的準(zhǔn)確率

表2 傳統(tǒng)方法與本文方法的定位耗時(shí)以及搜索數(shù)目

由圖3折線看出，當(dāng)K=5時(shí)，本文的定位準(zhǔn)確率達(dá)到最大，為此取K=5時(shí)，將數(shù)據(jù)集按1:2的比例隨機(jī)分配，繼續(xù)用本文方法對(duì)數(shù)據(jù)做4次實(shí)驗(yàn)，得到四次結(jié)果，繪制圖5，count_num_k=3表示第三次實(shí)驗(yàn)。從圖5中可知，這四次實(shí)驗(yàn)的結(jié)果相對(duì)穩(wěn)定，且第二種方法的準(zhǔn)確度比第一種高些。

圖5 K=5的本文方法4次實(shí)驗(yàn)結(jié)果

3 結(jié)語(yǔ)

本文通過(guò)介紹傳統(tǒng)指紋定位算法的介紹，剖析其算法原理，指出其系統(tǒng)時(shí)效性不足的問題，并針對(duì)問題提出本文的兩種簇指紋定位方法，將原始數(shù)據(jù)集按分級(jí)搜索，減少數(shù)據(jù)計(jì)算量，減少在線定位的時(shí)間，讓系統(tǒng)時(shí)效性更好，同時(shí)還保證定位的準(zhǔn)確性。最后通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證所提方法的可行性，實(shí)驗(yàn)結(jié)果得出：本文方法能夠減少算法在匹配時(shí)搜索的數(shù)量，減少估計(jì)時(shí)間和計(jì)算量，讓系統(tǒng)時(shí)效性讓人更能接受。