何 洋, 吳 飛, 賀成成, 朱 海, 毛萬葵

(1.上海工程技術大學 電子電氣工程學院,上海 201620;2.上海華測導航技術股份有限公司,上海 201702)

0 引 言

由于衛(wèi)星信號[1]在室內環(huán)境受到鋼筋水泥等建筑掩體的遮擋等影響嚴重,所以,基于電磁信號的室內定位研究開始受到廣泛關注。

Wi-Fi在日常生活環(huán)境中大多實現全覆蓋,已經成為目前室內定位技術研究的熱點之一[2]。其中被廣泛關注的是基于電磁指紋庫的定位方法,利用Wi-Fi電磁信號在空間中的傳播與分布規(guī)律,建立特征數據庫作為定位基礎[3]。文獻[4]提出在固定的區(qū)域范圍內,定位階段根據被搜索到的接收信號強度(received signal strength,RSS)數值的大小進行排序,篩除較小的值降低了計算量,再用K-means算法得到位置信息,但是K-means算法在定位數據集差異較大時,在誤差消除階段容易陷入局部最優(yōu),因此無法得到廣泛的運用。文獻[5～9]均是基于K-means算法進行室內定位,所以依然存在K-means算法固有的中心點k選取難和對異常值敏感等缺點,導致最終定位精度受到很大的影響。同時,文獻[10,11]提出基于密度峰值聚類(density peak clustering,DPC)算法融合網格查尋算法來獲取類中心,一定程度上解決了因為聚類中心個數k值選取不當從而導致定位結果不理想的情況,但網格搜索效率較低且依然從數據的局部分布考慮,并未用到數據之間的關聯性,不適用于帶有位置特性的定位數據。

本文結合K-NN算法,合理處置了離群點歸屬問題,并且利用關聯系數解決了定位精度不高的缺陷。

1 基于Wi-Fi指紋庫定位方法

基于Wi-Fi電磁指紋庫的室內定位方法,主要分為離線階段和在線階段。離線階段,通過對定位區(qū)域進行網格劃分,采集RSS信號,創(chuàng)建標準化電磁指紋庫,并且結合實際位置信息作為定位標簽,對采集數據進行聚類處理[12]。在線階段,對于進入定位區(qū)域內的用戶采集到的電磁指紋信息和指紋庫數據進行映射匹配,從而實現室內用戶定位[13～17]。

2 DPC算法

DPC算法基于兩種假設:1)與周圍點相比聚類中心的密度最高；2)聚類中心與其他高密度區(qū)域之間有較大的距離。

假設待處理定位指紋庫數據為X,規(guī)模為M×N,數據集中任意數據xi,該點的分布情況可由局部密度ρi和與其他高密度區(qū)域相對距離δi描述。

局部密度定義

(1)

式中φ(x)為分段函數,dij為數據點xi到數據點xj之間的距離,dc為截斷距離,ρi可理解為在距離dij內數據點xi的個數。由于式(1)存在統計誤差,所以文獻[3]提出式(2)來表示局部密度

(2)

并給出截斷距離dc的選擇標準是每個樣本點的鄰居樣本點的平均個數是數據集樣本點的1 %～2 %[3]。

相對距離定義

(3)

圖1 DPC算法

3 改進DPC算法

為了解決傳統DPC算法面對大范圍定位數據集,無法以較好識別度區(qū)分電磁指紋數據的聚類中心,改進后的DPC算法和之前只關注局部密度不同,本文從數據分布的整體考慮,引入關聯系數來評判各數據點對當前點密度的影響。常用的做法是在高斯核函數中加入關聯系數來計算局部密度,建立數據樣本的全局性關系,然后再進行聚類中心的計算。并且結合K-NN的思想,針對聚類中心以外的離群點,根據K-NN的分布信息采用統計概率分配的方式對離群點進行處理。算法的具體實現步驟如下:

1)獲取每個樣本點xi的局部密度ρi:

改進后的DPC算法,從定位數據的整體分布考慮,密度的計算公式為

(4)

式中r為關聯系數,表示密度函數與樣本點之間的關聯程度,r值越大則表示其余樣本點離xi距離越近,對其密度ρi貢獻程度越大,σ取數據樣本的2 %[3]。

2)與傳統密度峰值算法相同,利用式(3)計算數據點xi和其他高密度區(qū)域之間的相對距離。

3)經過步驟(1)和步驟(2)的計算可以得到局部密度值ρi和相對距離δi,再由決策圖γ=ρ×δ,統計前M個最大的值,選取統計值M作為局部聚類中心。

4)根據步驟(3)選取的聚類中心,規(guī)定各聚類中心鄰域內的點為中心點Xcore,其余點稱為離群點,Xcore定義為

(5)

式中ε變量為鄰域分隔閾值,o為類中心,um為局部類Cm中各點與類中心o的平均距離,定義為

(6)

為了將離群點正確分類,需要結合K-NN思想做進一步的處理。

5)通過計算每個離群點屬于相關局部類Cm的概率進行分配。首先需要計算樣本點xi和xj之間的相似度Sij

(7)

(8)

K-IDPC算法實現如下:

Input:數據集X。

Output:類別標簽labels。

Initial:

關聯系數r=1,近鄰個數k=4。

Main:

Do:

利用式(3)和式(4)計算相對距離δi和局部密度ρi；

通過決策圖γ得到聚類中心；

根據式(5)和式(6)得到中心點數組:Xcore=[xcore1,xcore2,…,xcorem]和離群點數組X’core=[x’core1,x’core2,…,x’coreN-m]；

依據式(8)并結合K近鄰算法計算每個離群點所屬類的概率值,存入概率矩陣Pk×M；

選取max(P[index])對應的數據點x0歸為類I[o]；

更新Pk×M,P,I；

While:

P中所有值均為零

輸出聚類結果

改進后的DPC算法,思路簡單,沒有復雜的公式計算。算法首先引入關聯系數,從定位數據集樣本分布整體考慮,更好地界定聚類中心,使得聚類過程更加穩(wěn)定。同時結合K-NN思想針對離群點依統計概率進行所屬歸類,提高了算法針對密度不均的定位數據處理能力。

考慮計算機的實際運算過程,K-IDPC算法和傳統的聚類算法一樣,在執(zhí)行運算過程是需要將數據一次性讀入內存單元,無疑對運行設備的內存有較為嚴苛的要求。但是在實際定位場景中,每天都存在很大的數據流量,僅憑單獨的聚類算法很難處理大規(guī)模的定位數據,所以在上述優(yōu)化后的K-IDPC聚類方法的基礎上繼續(xù)優(yōu)化,融合數據切割的思想,使得算法能夠適應大規(guī)模的定位數據。

基于數據切割的K-IDPC算法,即將大數據集合理劃分為若干小數據塊,然后提取、合并每個數據塊的特征元素,得到全局特征量,再對原大規(guī)模定位數據聚類。即假定大小為n的數據集D,將其分割為m個數據塊,并滿足

D1∪D2∪D3…∪Dm=D,Di≠?

(9)

Od=max(f(n1),f(n2),…,f(nm))

(10)

由于n>ni,且f(n)′>0,所以Od(n)

經由分析可知,大數據集被切割后能夠減小計算開銷,但是顯然需要進行合理的劃分。切割的過大,分割后的數據塊在特征提取時會耗費更大的計算開銷。同理,切割過細,那么在特征元素合并階段也會造成極大的開銷,所以,需要找到合適的切割點。數據塊切割大小與聚類耗時如圖2所示。

圖2 不同數據規(guī)模下聚類時間與數據塊大小關系

采用數據規(guī)模分別為1×103,1×104,1×105和1×106,從上圖可以看到,針對不同規(guī)模的數據集的切割,其聚類時間和數據塊大小的肘點值在50～80之間,所以，在數據切割時可以以此規(guī)則為參考對數據塊進行劃分。

4 實驗驗證與分析

4.1 實驗設計

本次實驗共采集783個Wi-Fi電磁信號組成指紋庫數據,每個無線接入點(access point,AP)連續(xù)采集100組數據,采樣時間間隔為1 s,以1.2 m×1.2 m為指紋庫網格劃分基準。其中實驗所在走廊的平面圖按比例如圖3所示。

圖3 實驗區(qū)域平面圖

為了便于對定位效果進行更好的分析,引入用于評判的誤差函數

(11)

式中 (xtrue,ytrue)為真實位置,(xi,yi)為所測得的位置坐標,根據均方誤差求得誤差函數MSE。

4.2 實驗分析

本實驗通過本文提出的改進算法和經典的K-means、DBSCAN和DPC聚類算法進行有效對比。相關實驗參數如表1所示。

表1 實驗算法參數

為了更好分析上述算法對于實際應用中的效果,對獲得的實驗數據進行去噪、缺失值等預處理。實驗表明相比于傳統的K-means、DBSCAN和DPC算法,所提出的K-IDPC算法對于不同區(qū)域的定位準確率有明顯的提高。

如圖4定位誤差分析,改進后的K-IDPC算法相比于DPC算法,加入了關聯系數,從定位數據全局分布考慮,更好利用定位數據集的位置關聯信息,同時結合K-NN思想,合理處理定位數據離群點,增強了定位精度。其中DPC算法和K-means算法相比,融合決策圖解決了聚類中心選擇問題,定位效果優(yōu)于K-means算法,且與DBSCAN對比,其類中心點的選取效果更好。實驗得到K-IDPC算法約91.2 %的定位誤差可以控制在1.5 m左右。其他三種算法,1.5 m內定位誤差概率分別48 %,57 %和66 %,明顯改進后的算法定位效果最優(yōu)。

圖4 定位誤差分析

從不同定位區(qū)域的準確率去衡量上述4種算法的性能。表2為在不同定位區(qū)域內不同算法各自的準確率,K-IDPC算法針對4個不同區(qū)域的定位指紋數據,引入關聯系數,聚類中心的界定清晰合理,最高可達到97 %的定位準確率,相比于其他三種定位算法有了很大程度上的提高。

表2 不同定位區(qū)域的準確率

在定位的時效性上,本文在改進后的K-IDPC算法的基礎上進一步優(yōu)化,使用數據切割的方法,先提取每個小數據塊的特征元素,再對這些特征元素進行聚類分析,降低了聚類算法的計算復雜度。從圖5不同區(qū)域定位時間對比圖可以看到,改進后的K-IDPC算法平均定位時間均在15.5 s,由圖可知K-IDPC算法定位時效性最佳。

圖5 不同區(qū)域定位時間對比

5 結 論

經過上述理論研究和4.2節(jié)實驗分析,在實際定位場景運用中,K-IDPC算法在定位效果上明顯優(yōu)于同類相關算法。引入關聯系數和K-NN思想,充分利用了定位數據集的全局信息,并且合理處置了離群點,大幅的提高了室內定位的精度。同時從定位時效性考量,運用數據切割的方法,將龐大的定位數據集合理分割,降低了計算開銷,從宏觀上來看削減了定位時間。所以,可以很好地運用到實際室內定位場景。