室內(nèi)位置軌跡的聚類與可視化

袁德寶，王炳靈，閆 瑜，周士強，梁 晨

(中國礦業(yè)大學(xué)(北京)地球科學(xué)與測繪工程學(xué)院，北京 100083)

如今，無線射頻識別技術(shù)、藍(lán)牙、無線局域網(wǎng)絡(luò)等定位技術(shù)極速發(fā)展，滿足室內(nèi)位置高精度定位的要求，因而常用于室內(nèi)定位[1]。

軌跡數(shù)據(jù)是人類移動行為的表征，能夠映射出人的出行模式和社會屬性等信息。如何有效挖掘軌跡數(shù)據(jù)蘊藏的人類活動規(guī)律一直是研究的熱點。通過軌跡聚類發(fā)現(xiàn)行為相似的類簇，從而探究群體的移動模式是軌跡挖掘和深度應(yīng)用常見的方法之一[2]。

室內(nèi)移動對象軌跡數(shù)據(jù)分析采用相關(guān)算法對預(yù)處理后的對象軌跡數(shù)據(jù)進(jìn)行聚類，提取對象軌跡數(shù)據(jù)中的相似性和異常性，有助于發(fā)現(xiàn)用戶感興趣的區(qū)域，完成用戶個性化推薦服務(wù)[3]。室內(nèi)移動對象軌跡數(shù)據(jù)分析也能夠發(fā)掘物體移動方式的空間散布和時間特征，對于認(rèn)識運動的形成機制，預(yù)測運動的未來發(fā)展具有重要的意義。

目前，許多著名的聚類算法如K-means、BIRCH、DBCSAN(density-based spatial clustering of applications with noise)、OPTICS、STING等[4]已被用于軌跡聚類。文獻(xiàn)[5]首次將時間依賴關(guān)系引入軌跡分析中。文獻(xiàn)[6]用場表達(dá)軌跡，通過格網(wǎng)內(nèi)的軌跡密度劃分出活躍區(qū)域。文獻(xiàn)[5]對軌跡分段并將速度等要素引入軌跡段間的相似度計算。文獻(xiàn)[7]用矢量線表達(dá)完整軌跡，通過歷史數(shù)據(jù)建立回歸模型，計算軌跡和模型間的相似性，進(jìn)而聚類得到移動模式。文獻(xiàn)[8]提出了路網(wǎng)空間下的基于密度的軌跡聚類方法。本文利用DBSCAN算法對某商場大廈的室內(nèi)軌跡數(shù)據(jù)進(jìn)行聚類分析，得到關(guān)于進(jìn)入商場大廈的人員的習(xí)慣特征分析，同時對軌跡數(shù)據(jù)進(jìn)行熱度圖可視化展示，以驗證聚類分析結(jié)果。

1 基于DBSCAN聚類方法的室內(nèi)軌跡分析

1.1 DBSCAN聚類算法

1996年，Martin Ester等提出了一種基于密度的空間聚類算法DBSCAN。該算法將具有高密度的區(qū)域劃分為簇，并在具有噪聲的數(shù)據(jù)中聚類成簇。DBSCAN算法以空間兩點間的直線距離和最小點數(shù)為標(biāo)準(zhǔn)進(jìn)行聚類的二維空間聚類方法，它可以通過計算點的密度將集合中的點分為核心點、邊界點和噪聲點，當(dāng)二維空間中點密度超過一定閾值時，就認(rèn)為這些點是一個集簇。在此基礎(chǔ)上，對所有點進(jìn)行空間聚類。

如圖1所示，假定領(lǐng)域密度閾值(MinPts)為6，R為圖中圓半徑長度。則根據(jù)定義，圖上點C在R鄰域內(nèi)共有7個鄰點，大于MinPts，為核心點；點B在R鄰域內(nèi)共有5個鄰點，小于MinPts，不是核心點，但其在核心點C的鄰域范圍內(nèi)，是邊界點；點N在R鄰域內(nèi)的鄰點數(shù)為0，因此不是核心點，同時也不在核心點的鄰域范圍內(nèi)，屬于噪聲點。其中，對象p的R領(lǐng)域是以對象p為中心、R為半徑的空間，參數(shù)R>0，是用戶指定每個對象的領(lǐng)域半徑值；MinPts為對象R領(lǐng)域的對象數(shù)量；核心點為在領(lǐng)域半徑R內(nèi)含有超過MinPts數(shù)目的點；邊界點為落在核心點的鄰域內(nèi)，且領(lǐng)域半徑R內(nèi)點的數(shù)量小于MinPts；噪音點定義為既不是核心點也不是邊界點的點。聚類算法具體流程如圖2所示。

1.2 聚類分析內(nèi)容

1.2.1 數(shù)據(jù)采集

本文的數(shù)據(jù)源為某商場采集的1 d內(nèi)基于手機WiFi信息的室內(nèi)位置數(shù)據(jù)。對這些數(shù)據(jù)進(jìn)行預(yù)處理，剔除由于手機WiFi信號的不穩(wěn)定導(dǎo)致位置冗余的數(shù)據(jù)及邏輯上明顯的錯誤數(shù)據(jù)，選用質(zhì)量優(yōu)良的有效軌跡454條。另外，本文使用的樓層數(shù)據(jù)共10層，其中地上8層，地下2層。

1.2.2 軌跡聚類分析

用戶的停留點是用戶軌跡最重要的特征之一，它隱含了豐富的空間結(jié)構(gòu)信息和行為規(guī)律信息。對室內(nèi)人員的停留點加以分析挖掘，能夠得到極具價值的室內(nèi)人員行為特征規(guī)律。本文選擇DBSCAN算法作為提取軌跡停留點的基礎(chǔ)算法。圖3是對軌跡數(shù)據(jù)聚類后的結(jié)果。

1.2.3 聚類結(jié)果分析

1.2.3.1 DBSCAN聚類算法的結(jié)果分析

本文將DBSCAN聚類算法應(yīng)用到室內(nèi)人員軌跡分析中，對質(zhì)量優(yōu)良的454條有效軌跡提取的各樓層商鋪進(jìn)行聚類。圖4僅展示了部分軌跡路徑，箭頭表示軌跡的方向。圖中圓點表示軌跡聚類中心，聚類中心是由聚類效果圖與樓層圖層的對比及軌跡路徑圖獲得的。

1.2.3.2 個人行為特征提取

通過對個人軌跡信息進(jìn)行整理、數(shù)理統(tǒng)計，并結(jié)合人們的生活行為規(guī)律和商場店鋪的性質(zhì)，能夠得到個體的行為特征規(guī)律。如對MAC地址為E84E844118D4的客戶軌跡信息進(jìn)行統(tǒng)計發(fā)現(xiàn)，該客戶在9:01—13:52時間段，軌跡信號一直停留在商場6層的港麗餐廳，由此可以推斷該人員是港麗餐廳的服務(wù)人員。對MAC地址為E88D28E33487的客戶軌跡位置統(tǒng)計整理，表1為該客戶在15:38—16:25時間段經(jīng)過的店鋪，由此可知該客戶為女性，且消費水平處于較高程度。

表1 E88D28E33487客戶途徑商店

1.2.3.3 群體行為特征提取

運用DBSCAN算法，對選用質(zhì)量優(yōu)良的454條有效軌跡提取的各樓層位置信息進(jìn)行批量分析，本文針對室內(nèi)人員感興趣的幾個區(qū)域，對部分停留點信息進(jìn)行數(shù)理統(tǒng)計與歸納，整理結(jié)果如表2和圖5所示。

表2 各樓層熱點區(qū)域出現(xiàn)頻數(shù)

根據(jù)表2與圖5中展示的統(tǒng)計數(shù)據(jù)信息，得到該商場室內(nèi)人員群體行為特征規(guī)律如下：

(1) 商場6層的聚類中心較多，且6層大部分商鋪屬性為餐廳、甜點等類型。由此判斷相比其他消費方面，人們對于吃飯方面的關(guān)注與消費是很高的。

(2) 地下2層人員來往程度較高，其中地下2層聚類中心有發(fā)型店和服裝店，判斷人員對于自己的容貌方面也是比較重視的。另外也反映出，這幾處發(fā)型店與服裝店服務(wù)態(tài)度及消費價格是公道合理的。

(3) 商場5層的聚類中心有手機廣場和中國移動營業(yè)廳，說明客戶購買手機、置辦或更換手機套餐服務(wù)的頻率是較高的。

(4) 商場8層比其他樓層人員來往得少，盡管也有較多的餐廳服務(wù)店，推斷可能由于樓層太高或商店不出名等原因，人員更喜歡去方便、好評度高的地方就餐。

2 軌跡可視化展示

2.1 熱度圖

熱度圖是以特殊高亮的形式顯示訪客熱衷的頁面區(qū)域和訪客所在的地理區(qū)，以顯示不可點擊區(qū)域發(fā)生的事。通過熱度圖可以簡單地聚合大量數(shù)據(jù)，并使用一種漸進(jìn)的色帶表現(xiàn)，效果一般優(yōu)于離散點的直接顯示，可以很直觀地展現(xiàn)空間數(shù)據(jù)的疏密程度或頻率高低。

熱度圖是通過ArcGIS API for JavaScript實現(xiàn)的，其中，需要采用的數(shù)據(jù)是ArcGIS對某樓層圖層的地圖發(fā)布服務(wù)和漁網(wǎng)圖采集到的該樓層各商店軌跡坐標(biāo)信息數(shù)據(jù)。ArcGIS API for JavaScript首先定義一個map底圖，引用樓層圖層地圖發(fā)布服務(wù)的URL地址，實現(xiàn)樓層數(shù)據(jù)在瀏覽器中的表達(dá)；然后定義一個heatmap，其中heatmap的data數(shù)據(jù)需要覆蓋店鋪且能代表店鋪位置的漁網(wǎng)網(wǎng)格中心點坐標(biāo)作為熱點中心，漁網(wǎng)圖采集的軌跡信息數(shù)目作為熱點中心的count值；加載以后，在瀏覽器實現(xiàn)map與heatmap的疊加，展示熱度圖。

2.2 熱度圖展示

熱度圖通過多個熱點中心(覆蓋店鋪且能代表店鋪位置的漁網(wǎng)網(wǎng)格中心點)的顏色深淺來展現(xiàn)室內(nèi)人員軌跡的密度情況，可以反映哪些商鋪吸引了大多數(shù)訪客的注意，直觀地表達(dá)各樓層商店的人員軌跡密集情況，結(jié)合日常生活中人們的生活規(guī)律與興趣及店鋪相應(yīng)的屬性信息推測店鋪的銷售情況，獲得個人、群體行為特征，為市場調(diào)查、研究等領(lǐng)域提供參考的依據(jù)。圖6為實現(xiàn)的熱度圖展示。

3 結(jié) 語

本文基于當(dāng)前已有的軌跡研究服務(wù)成果，利用DBSCAN聚類算法實現(xiàn)軌跡數(shù)據(jù)的聚類，并對聚類結(jié)果進(jìn)行分析，得到群體行為特征信息；同時對室內(nèi)位置信息進(jìn)行熱度圖展示，進(jìn)一步驗證聚類結(jié)果。然而，由于DBSCAN算法自身的缺陷和本文數(shù)據(jù)預(yù)處理的不確定性，導(dǎo)致聚類結(jié)果與真實情況存在偏差，DBSCAN聚類只是考慮點與點之間的空間關(guān)系，而沒有考慮點與點之間的時間關(guān)系,但在實際情況中，空間上相鄰的點在時間上不一定相鄰。如何獲取更高質(zhì)量的用戶軌跡數(shù)據(jù)，并對其進(jìn)行更加有效的處理分析，將是下一步的研究方向。