毛萬葵， 吳 飛， 張玉金， 章裕潤

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620)

0 引 言

隨著無線局域網(wǎng)(WiFi)技術(shù)的成熟，在一些大型的室內(nèi)場所(比如：大型超市、室內(nèi)商場、地下車庫等)已實現(xiàn)WiFi全覆蓋，基于WiFi的室內(nèi)定位技術(shù)，逐漸成為室內(nèi)定位服務(wù)的主要技術(shù)之一[1～3]。

但傳統(tǒng)的室內(nèi)定位技術(shù)主要還是集中在二維平面上的定位，而現(xiàn)在隨著發(fā)展，對于二維平面的室內(nèi)定位信息已經(jīng)無法滿足人們的需求，人們開始越來越關(guān)注基于樓層的三維空間上的定位服務(wù)，例如商場廣告推送、立交高架交通導(dǎo)航、緊急情況下的人員樓層定位等。雖然基于樓層的室內(nèi)定位服務(wù)，具有很好的市場應(yīng)用價值，但目前卻極少有研究者愿意關(guān)注這方面的研究。文獻(xiàn)[4]提出了一種基于WiFi指紋定位的樓層定位方法，該方法需要借助氣壓計、加速度計等硬件設(shè)備獲取定位目標(biāo)的海拔高度輔助定位。文獻(xiàn)[3]提出的基于快速部署的室內(nèi)多樓層定位算法，可以根據(jù)實際的需要對設(shè)備進(jìn)行部署安裝，對不同樓層的WiFi信號進(jìn)行差分計算，實現(xiàn)對樓層的定位。無法進(jìn)行大范圍的推廣。文獻(xiàn)[6,7]都是基于K均值聚類(K-means)算法的室內(nèi)定位樓層判別算法，增加了樓層定位的復(fù)雜度。文獻(xiàn)[8]基于室內(nèi)地圖環(huán)境信息的多樓層WiFi定位技術(shù)，在離線階段建立地圖環(huán)境信息，并且對指紋數(shù)據(jù)進(jìn)行聚類，在線階段采用設(shè)置閾值的方法對樓層進(jìn)行判斷，結(jié)合地圖模型和機器學(xué)習(xí)的方法算出位置，增加了系統(tǒng)在離線階段指紋數(shù)據(jù)庫建立的復(fù)雜度。

本文通過結(jié)合密度分層的思想，對傳統(tǒng)的層次聚類算法進(jìn)行改進(jìn)，并利用數(shù)據(jù)切分的方法，將離線階段的指紋數(shù)據(jù)進(jìn)行切分，變成若干較小數(shù)據(jù)集的聚類，這樣不僅提高了樓層識別的準(zhǔn)確度，而且降低了樓層定位的計算復(fù)雜度。

1 基于WiFi的樓層判別方法

基于WiFi的樓層定位判別方法主要是由離線階段和在線階段組成。離線階段，通過對定位區(qū)域網(wǎng)格劃分、設(shè)置采樣點、接收信號強度(received signal strength,RSS)采集、生成標(biāo)準(zhǔn)化的指紋數(shù)據(jù)庫。然后結(jié)合具體的樓層指紋信息，對終端接收信號進(jìn)行聚類，生成樓層指紋數(shù)據(jù)。在線階段，將用戶實時采集的指紋信息，與指紋數(shù)據(jù)庫進(jìn)行映射，最后定位出真實樓層信息。樓層定位方案如圖1所示。

圖1 樓層定位方案圖

2 層次聚類算法

層次聚類(hierarchical clustering,HC)算法是比較實用的一種聚類算法，可以將其分為兩大類：凝聚聚類和分裂聚類[9]。

HC算法主要是根據(jù)兩個不同類之間的矩陣相似度進(jìn)行計算。相似度的計算方式有很多不同的解法。

1)最短距離法：通過計算類中兩點之間的距離，然后將最短的兩點之間距離作為類的距離

dA,B=min{d(xa-xb)}

(1)

式中dA,B為類A和B類之間的歐氏距離，xa和xb分別是對應(yīng)兩個類中的樣本采樣點。

2)最長距離法：和最短距離法比較類似，但是不同的是將最長的兩點之間的聚類作為類的距離

dA,B=max{d(xa-xb)}

(2)

3)平均距離法：是計算兩個類中所有兩點之間距離，將距離的平均值當(dāng)作類之間的距離

dA,B=avg{d(xa-xb)}

(3)

層次聚類算法雖然計算簡單、聚類效果好，但是需要計算相似矩陣。時間復(fù)雜度較大，為O(n2·logn)，其中，n為數(shù)據(jù)集大小。普通的HC算法對離群點比較敏感，聚類的精度也比較容易受其影響[10～12]。

3 改進(jìn)的層次聚類算法

為了減小數(shù)據(jù)中的離群點對聚類結(jié)果的影響，改進(jìn)的算法通過隨機刪除密度較小的樣本點，只對剩下來的數(shù)據(jù)進(jìn)行層次聚類。常用的做法是選取原始數(shù)據(jù)中的8 %～12 %左右的數(shù)據(jù)進(jìn)行剔除[13]。因為密度較大的數(shù)據(jù)點都分布在類的中心部位，而這些點分類都是比較容易的。而且為了避免對一些整體密度都比較小的類造成誤判，改進(jìn)算法特意將密度較小的點單獨篩選出來劃分為一層，然后再分層進(jìn)行聚類計算。

算法的具體實現(xiàn)步驟如下：

1)計算每個數(shù)據(jù)點的密度值

密度值是依據(jù)某個區(qū)域內(nèi)所有點的數(shù)目的總和，設(shè)數(shù)據(jù)集為D，密度ρi的計算公式為

(4)

式中x的取值服從二項分布。lij為點i和點j之間的直線距離，d為截斷距離。

2)選擇偏離點

選出偏離點后，從整體數(shù)據(jù)中對偏離點進(jìn)行剔除，剩下的數(shù)據(jù)組成新的數(shù)據(jù)集P

(5)

式中ρ0為初始截斷密度值，可以初始設(shè)定一個值，然后根據(jù)公式就可以求出密度小于截斷密度的點的個數(shù)n即為偏離點的數(shù)據(jù)集大小。

3)將數(shù)據(jù)集P中的數(shù)據(jù)按密度從小大排列，提取出最大的1/4數(shù)據(jù)，重新組成數(shù)據(jù)集T，對數(shù)據(jù)集T進(jìn)行層次聚類，類別數(shù)記為K。

4)同樣地，從數(shù)據(jù)集P中選出最小的1/4數(shù)據(jù)，組成一個新的數(shù)據(jù)集S。對數(shù)據(jù)集S聚類，類別數(shù)記為K。

5)經(jīng)過步驟(3)和步驟(4)處理后，P中還有部分?jǐn)?shù)據(jù)，這部分的數(shù)據(jù)密度是介于T和S之間，記為H。這里將H中的每個數(shù)據(jù)點都視為一個單獨的類，然后結(jié)合步驟(3)和步驟(4)的聚類結(jié)果，對聚類結(jié)果進(jìn)行合并，使得最終聚類的數(shù)目為K/2。

6)將偏離點與P中的類進(jìn)行比較，分別劃分到不同的類中，最終實現(xiàn)對數(shù)據(jù)集D的聚類。

基于密度的改進(jìn)HC算法，計算簡單，沒有復(fù)雜的公式推導(dǎo)。算法初始階段就對偏離點進(jìn)行剔除，減少了偏離數(shù)據(jù)對聚類結(jié)果的干擾，使得聚類的過程更加的穩(wěn)定。同時，改進(jìn)的HC算法將數(shù)據(jù)集進(jìn)行劃分，分別在不同密度層進(jìn)行聚類，提高了算法對密度不均勻數(shù)據(jù)的處理能力。

但改進(jìn)后的算法和傳統(tǒng)聚類算法一樣，要將所有數(shù)據(jù)一次性讀入計算機內(nèi)存，使得算法對內(nèi)存的要求較高，這樣復(fù)雜的計算導(dǎo)致該算法無法在大規(guī)模的數(shù)據(jù)集上進(jìn)行很好的應(yīng)用。但是生活中，每天的定位數(shù)據(jù)都是非常龐大的，僅僅依靠密度的聚類方法很難快速的對大規(guī)模數(shù)據(jù)進(jìn)行處理。所以本文在上一小節(jié)基于密度的聚類方法的基礎(chǔ)上繼續(xù)進(jìn)行改進(jìn)，加入數(shù)據(jù)切分的思想，使得算法能夠處理大規(guī)模的定位數(shù)據(jù)。

基于數(shù)據(jù)切分思想的HC算法，是將大的數(shù)據(jù)集切分成不同的小的數(shù)據(jù)塊。然后通過合并每個數(shù)據(jù)塊的特征元素，得到全局特征，再對原始數(shù)據(jù)依次聚類[14]。假設(shè)初始數(shù)據(jù)集D的大小為n，將D切分成m個數(shù)據(jù)塊{D1,D2,…,Dm}，但是要滿足如下公式

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

(6)

Td(n)=max(f(n1),f(n2),…,f(nm))

(7)

因為n>ni，而且f(n)'>0,所以Td(n)

通過上面的分析知道，數(shù)據(jù)塊被切分后可以節(jié)省系統(tǒng)的計算開銷，但每個數(shù)據(jù)塊切分大小的不同也會影響計算效率。切分的太粗，導(dǎo)致在子數(shù)據(jù)集中的特征提取耗費更多的時間;切分的太細(xì)，系統(tǒng)在全局特征合并的時候，反而會增大時間開銷。所以,需要找一個平衡點，使得算法的效率達(dá)到最大化。

圖2中所示的實驗中數(shù)據(jù)集的大小分別為0.3×103,1×104,1×105,1×106，分類的類別數(shù)分別是2,3,6,6。從圖中可以看出，不同的切分大小與聚類時間之間都存在一個極值點，極點的范圍主要分布在50～80之間。說明數(shù)據(jù)集的大小和類別數(shù)對聚類時間的影響不大，所以,可以按照這樣的規(guī)律進(jìn)行數(shù)據(jù)塊大小的切分。

圖2 數(shù)據(jù)塊切分與聚類時間關(guān)系

如圖3是為了說明數(shù)據(jù)被切分后對最終聚類結(jié)果的影響，從圖中數(shù)據(jù)被切分成不同的大小后，其對應(yīng)的聚類結(jié)果都沒有太明顯的波動。綜合以上說明改進(jìn)算法對數(shù)據(jù)進(jìn)行切分是合理有效的。

圖3 數(shù)據(jù)塊大小與聚類F值關(guān)系

4 仿真與驗證

4.1 實驗環(huán)境

本文通過實驗來驗證樓層定位方法準(zhǔn)確度和效率的提高，選擇的實驗環(huán)境為本校實訓(xùn)樓1號樓，共有4層樓，每層樓的構(gòu)造基本相同，整棟樓經(jīng)過統(tǒng)計記錄共有68個無線訪問節(jié)點(access point,AP)，實驗用的信號采集設(shè)備為聯(lián)想(Lenovo)天逸310筆記本，通過內(nèi)置無線網(wǎng)卡和自主開發(fā)的信號采集軟件進(jìn)行信號采集。

實驗共選取了812個指紋采樣點，每個指紋采樣點處連續(xù)采集120組數(shù)據(jù)，時間間隔為1 s，以1.5 m×1.5 m作為采樣間隔，其中,以3樓為例指紋采樣點的平面分布如圖4所示。

圖4 實驗區(qū)指紋采樣點平面

為了將定位效果更好的量化，定義一個用來判斷誤差的函數(shù)為

(8)

式中 (xi,yi)為實際物理位置，(x'i,y'i)為測估算位置坐標(biāo)。

4.2 實驗結(jié)果分析

表1為實驗設(shè)定的相關(guān)參數(shù)。

表1 改進(jìn)HC算法實驗參數(shù)

如圖5(a)所示為各個算法在不同樓層上的平均定位誤差，其中經(jīng)典的CURE和ROCK算法要比傳統(tǒng)的K-means算法在定位誤差上要好一些，但是改進(jìn)的層次聚類算法的樓層定位誤差要明顯小于前面三種算法，誤差均值在1.212 m左右，比其他三種算法的平均誤差降低了54.7 %,48.16 %,48.78 %。

表2所示為不同算法的樓層識別率，改進(jìn)HC聚類算法因為采用了密度分層的方法降低了異常值對聚類結(jié)果的影響，增大了樓層間的聚類差異性，提高了樓層識別率，準(zhǔn)確均值可以達(dá)到95.25 %。

表2 不同算法樓層識別率

如圖5(b)所示為不同算法的樓層定位時間對比圖?？梢钥闯鰝鹘y(tǒng)的K-means的聚類所花時間最長，CURE和ROCK次之，改進(jìn)的HC算法聚類時間最短，平均值為16.2 s。綜合以上所述，可以說明本文提出的改進(jìn)的HC算法在樓層判別率和樓層定位效果上都要好于傳統(tǒng)K-means、CURE和ROCK聚類算法。

圖5 不同算法的平均定位誤差與定位時間

5 結(jié) 論

通過密度分層的思想對定位數(shù)據(jù)進(jìn)行敏感數(shù)據(jù)剔除、密度大小分層，對不同密度層分別進(jìn)行不同的層次聚類，解決了普通聚類算法對異常值敏感的缺陷，提高了終端的定位效果。同時為了降低日益增長的大規(guī)模定位數(shù)據(jù)帶來的計算復(fù)雜度高的問題，結(jié)合了數(shù)據(jù)切分的思想。離線階段時將定位數(shù)據(jù)進(jìn)行切分，將數(shù)據(jù)集進(jìn)行細(xì)化，降低了計算時間復(fù)雜度，節(jié)省了樓層判別的時間。從實驗結(jié)果上來看，與基本的聚類算法相比，改進(jìn)的HC算法無論在樓層定位效率，還是樓層判別準(zhǔn)確度上都有提高。