賈若然　劉曙光　孫啟龍

(中國科學院重慶綠色智能技術研究院　重慶　400714)

?

基于位置軌跡數據的用戶相似性分析

賈若然劉曙光孫啟龍

(中國科學院重慶綠色智能技術研究院重慶400714)

隨著獲取位置信息越來越方便,實時記錄用戶的移動軌跡成為可能,但是對用戶軌跡數據的分析一直停留在軌跡聚類上,而對通過用戶的位置軌跡信息分析用戶的相似性的研究則較少。為此,提出了分層級多粒度,在不同的鄰域半徑下密度聚類的方法;改進了傳統(tǒng)的聚類算法,探索根據用戶的移動軌跡分析用戶之間的相似性度量方法。該方法在不同粒度下觀察用戶訪問各個興趣區(qū)域的時長,進而利用向量空間模型(VSM)計算用戶在各個粒度下的相似性,最終以不同權重疊加各粒度下的用戶相似性值,得出用戶在地理空間行為上的相似性?；谡鎸嵱脩魯祿膶嶒灲Y果表明,該方法能有效識別出訪問地理位置相似的用戶。

聚類; 軌跡; 數據挖掘; 用戶相似性

Class NumberTP393

1　引言

隨著移動通信技術、無線網絡技術、全球定位系統(tǒng)(GPS)、Wi-Fi和藍牙室內定位技術的快速發(fā)展以及智能設備的普及率越來越高,人們獲取移動對象的位置信息變得越來越方便[1～2]。智能設備如智能手機、車載GPS、Pad等設備,能夠輕松方便地獲取移動對象的位置信息,并將帶有時間標記的位置信息上傳到服務器。個體移動追蹤數據逐漸有可獲得性[3～4]。通過對一個人的物理移動軌跡進行長期的追蹤,可以分析總結出該個體在地理空間上移動的特征。對于大規(guī)模用戶的移動軌跡進行分析可以分析用戶的行為規(guī)律,用戶之間的相似性。近年來隨著室內定位技術的快速發(fā)展填補了GPS定位在室內信號丟失引起的室內位置信息缺失的空白,獲取移動對象的方法和途徑變得多樣和便捷。分析和挖掘這些帶有時間標記的位置信息組成的時空數據具有重要的意義[5～7]。例如商場和會展中心可以通過室內定位技術獲取消費者的移動軌跡,通過相關性分析可以對消費者進行分類和相似性分析等處理,為精準營銷和智能推薦提供指導。隨著移動位置信息數據的快速增長,如何從浩如煙海的時空數據中提取有用信息吸引了越來越多研究人員的關注[8～9]。

當前對于用戶的移動數據的處理主要集中要軌跡聚類的處理上[10～11],主要是對用戶的移動軌跡數據進行聚類分類,但是并不能發(fā)現用戶之間的相似度。針對于用戶的位置信息進行處理分析計算用戶相似性的研究則較少。袁華等[12]提出了基于GPS軌跡數據的用戶興趣點以及頻繁路徑的挖掘研究,首先將GPS軌跡劃分為成組的線段集,然后運用聚類方法將地理上相似的端點進行聚類以檢測用戶的個性化興趣點。微軟亞洲研究院的鄭宇研究員,提出了一種新的概念:個人生活方式(Individual Life Pattern)挖掘[13],通過從基于GPS的歷史位置數據中發(fā)現個體的生活方式和生活規(guī)律,該研究給出了時間粒度、重要區(qū)域、序列模式、時刻和時間的相關定義,并給出了生活方式的形式化表示(LP normal form),用來描述哪種生活規(guī)則可以從歷史數據中提取出來,通過開發(fā)生活方式挖掘框架(LP mine framework)從GPS元數據中檢索和發(fā)現個體的行為和生活方式,LP-Mine由兩個階段表示:建模和挖掘。其中建模階段是對元數據進行描述作為挖掘的輸入;而挖掘階段,則是分析和發(fā)現個體的行為和生活方式。該研究給出了離散移動對象軌跡數據挖掘的相關概念、思路和流程,但是并沒有給出具體的實現方法。袁書寒等[14]提出了針對位置服務社交網絡用戶行為相似性分析,主要針對位置服務社交網絡的簽到數據作為用戶興趣點,進一步通過聚類得到不同粒度下的興趣區(qū)域,通過分析用戶有多少個興趣區(qū)域構成一個用戶訪問位置矩陣,可用余弦相似性方法計算用戶間的相似性。但是該方法在對興趣聚類時還是采用的傳統(tǒng)的DBSCAN聚類算法并沒有考慮到用戶行為特點和DBSCAN聚類會在密度較大時的擴展性,也沒有考慮到時間維度,會使之前的多粒度分析失去準確性。

本文首先根據活動半徑和停留時間作為標準,根據用戶的移動軌跡數據提取每個用戶的興趣點,然后通過劃分層次和粒度,改進傳統(tǒng)的基于密度的聚類算法使之能夠適用于興趣區(qū)域的發(fā)掘,在不同粒度上對興趣點進行聚類得到興趣區(qū)域,并得到用戶對于該興趣區(qū)域的興趣度,即用戶在該興趣區(qū)域興趣點的停留時間總和。在得到興趣區(qū)域和每個用戶對應的興趣度之后,就可以得到用戶和興趣區(qū)域之間的相似性矩陣。通過相似性矩陣就可以得出在每個粒度下用戶之間的相似性。對于不同的粒度賦予不同的權重:對于粒度小的興趣區(qū)域,屬于一個興趣區(qū)域則說明用戶之間相似性則較大,所以應該權重較大;而對于大粒度下得到的相似度則對應較小的權重。將各個粒度下的相似度進行相加求和即可求出用戶之間最終的相似度。

2　用戶相似性分析

在實際的軌跡數據中,用戶的軌跡是以經緯度和時間戳為主要數據的信息,如果將數據展示在地圖上則可以展示用戶的移動特征。如果用戶A去過X地點并停留了30min,則可以定義A對X地點感興趣;如果A對W,X,Y,Z地區(qū)都感興趣,而用戶B對X,Y,Z地點感興趣,則說明用戶A和用戶B具有較高的相似性。因此可以根據以上經驗得出興趣點的特點:在某個區(qū)域范圍內停留時間超過一個經驗閾值,則可以認為用戶對該區(qū)域感興趣,該區(qū)域的采樣點的經緯度的平均值即興趣點的坐標。

用戶具有兩個很接近的興趣點,則可以視為用戶具有相同的興趣點,以此為基礎則可以分析用戶之間的相似度。

2.1用戶興趣點和興趣區(qū)域

用戶軌跡是時刻都在記錄的,但是不是所有的記錄點都是對分析用戶相似性有作用的,需要從用戶的位置記錄點中提取用戶的興趣點。

定義1興趣點(Point of Interest,POI)可能并不是用戶軌跡上的點,是對于軌跡記錄點進行聚類后得到的代表點。以e為鄰域MinDistance為空間距離閾值,MinTime為時間間隔閾值進行DBSCAN[15]聚類,對于興趣點提取的聚類不僅要考慮地理空間上的相似度,還要考慮時間維度。最終聚類完成得到若干個簇,將屬于一個簇的點的經緯度進行求平均值得到興趣點的坐標。

定義2興趣度(Interest Degree):該簇的最后一個點的時間戳減去第一個點的時間戳;即該興趣點逗留時間。

因為在某個地理區(qū)域附近,可能有很多不同的興趣點,尤其熱門的大部分用戶常去的地區(qū)。因此用戶訪問相近的地理位置但是不一定具有相同坐標的興趣點,如果僅通過判斷用戶是具有相同的興趣點來計算用戶間相似性不現實的。因此,本文提出利用劃分層次和粒度的密度聚類方法將相近的興趣點在不同的ε鄰域下聚類,根據用戶訪問的各個聚類區(qū)域的時間作為感興趣程度,度量用戶相似性。利用密度聚類的方法,可以聚集用戶經常訪問的POI,但是不適用于密度聚類算法。原因有兩點:第一,傳統(tǒng)的密度聚類算法會將少數用戶才訪問的興趣點作為噪聲點過濾點,這是不合理的。因為對于計算用戶相似性而言,不僅僅是尋找共性還有尋找個性,為個性化推薦提供數據,這些密度低的興趣點也應該保留作為一個興趣區(qū)域。第二,傳統(tǒng)的密度聚類算法會不斷地將鄰域內直接可達的元素吸收進來,不斷擴大。會不利于分粒度相似性分析的實現和降低相似度的準確性。

圖1　用戶興趣點

因此本文對傳統(tǒng)的DBSCAN算法進行了改進,提出了DBSCPOI(Density-Based Spatial Clustering of POI)。主要改進點包括兩個方面:一是當該點的ε鄰域包含的興趣點數目少于MinPts時,并不是將該點作為噪聲過濾掉,而是將該點ε鄰域內也作為一個興趣區(qū)域;二是核心點的擴大方式,傳統(tǒng)的DBSCAN算法是判斷核心點的ε鄰域中的點是否為核心點,如果是則將領域中點的ε鄰域點吸收進來,以此循環(huán)至簇不再增加。本文為了限制簇的擴大,針對核心點ε鄰域點的領域點只吸收核心點進入該簇,并非全部吸收進來。根據上面描述,DBSCPOI算法的流程如下:

1) 根據興趣點的密度和粒度確定聚類半徑ε和核心點閾值MinPts。

2) 遍歷興趣點,判斷該點ε鄰域包含的興趣點個數是否超過MinPts,如果不滿足則該區(qū)域是一個感興趣用戶較少的區(qū)域,該點以及ε鄰域內的點作為一個興趣區(qū)域。

3) 如果滿足核心點的要求則以該點為中心首先將自己ε鄰域內的對象吸收進來,然后再將該對象ε鄰域中的核心點吸收進來,迭代過程反復進行直到已有的簇不再增長且沒有新簇出現為止。

Algorithm:DBSCPOI

Input:1.a Point Of Interest setP={p1,p2,p3,…,pn}

2.ε

3. MinPts

Output:a set of clustersC={C1,C2,C3,…,Cn}

Algorithm:

/*Step1*/

1. Set clusterId = 0;

2. Mark all segments as unclassified

3. For eachpi∈P

4 IfNi>MinPts andpiis unclustered

5. Markpias cluster core

6. clusterId++

7. Assign clusterId toNi

8. InsertNi-piinto the queue Q

9. ExpandCluster (Q, clusterId, P)

10. Else

11. clusterId++

12. Assign clusterId toNi

/*Step2*/

13. ExpandCluster (Q, clusterId, P)

14. while(Q ≠ ∮)

15. Let M be the first point in Q;

16. Get M’sNm

17. for each P inNm

18. IfNp≥Minpts then

19. Insert P to the Q

20. Assign clusterId to P

21. Remove M

Ni為pi的ε鄰域包含的興趣點集合,Nm為點m的ε鄰域包含的興趣點集合。經過聚類處理后,每個興趣點都屬于一個興趣區(qū)域了,一個用戶對于指定的興趣區(qū)域的興趣度等于用戶位于該興趣興趣點的興趣度的總和。

2.2用戶相似度計算方法

本文采用向量空間模型(Vector Space Model)來計算用戶相似性。將每個用戶的興趣區(qū)域表示為向量R=[r1,r2,…,rn],為了體現用戶訪問相同興趣區(qū)域的時間越長表示對該區(qū)域越感興趣,設定ri為用戶訪問第i個興趣區(qū)域的時長。則所有用戶訪問的興趣區(qū)域構成一個用戶-興趣區(qū)域矩陣Vnm,在這個矩陣的基礎上可以使用余弦相似性計算方法得到用戶間的相似性。

定義3用戶相似性計算矩陣:

(1)

式中m為用戶數量,n為在特定鄰域ε下聚類得到的興趣區(qū)域數量,Vij為第i個用戶對第j個興趣區(qū)域的興趣度。把用戶訪訪問過的位置看作n維位置空間上的向量,用向量間的余弦值計算用戶間的相似性。設用戶A和用戶B表示為向量UA和UB,則用戶A和用戶B之間的相似性為

(2)

‖UA‖‖UB‖由于對興趣點在不同鄰域ε進行多粒度聚類,因此在得到了用戶在不用粒度下的相似性后,下一步需要計算用戶總體的相似性。則跨粒度的用戶相似性為

(3)

(4)

式中H表示劃分的粒度總層次數目;Simi為第i層上的用戶相似性;βi為第i層的相似性權重,用戶在越小的粒度層次上相似,權重越大。

3　實驗分析

3.1實驗數據集

為了對本文提出的方法進行充分驗證,采用了真實的用戶軌跡信息進行實驗。本文使用的數據集為微軟亞洲研究院在北京城區(qū)采集的GPS軌跡數據,簡稱Geo Life。軌跡的元數據存在文本文件中,該數據以2s～5s或5m～10m的采樣率對165個用戶進行了超過兩年時間的跟蹤。采樣數據包含9559個文件,數據總量約1.46GB。本文的相關實驗僅選取北京城區(qū)(坐標為:北緯39°26＇～41°03＇,東經115°25＇～118°30＇)之間的軌跡參與計算。實驗選取用戶ID,軌跡ID,經緯度,采樣時間等信息參與分析。首先對Geo Life數據進行降噪、清洗、重構等預處理,生成具有標準結構的軌跡數據存儲在數據庫MySQL中。為了能充分全面地驗證本文方法,選取了30個移動對象的軌跡參與數據分析,在這些數據中,共包括采樣點個數為475,412。

3.2方法實施

首先通過對每個用戶的軌跡數據使用DBSCAN算法進行興趣點提取,將所有的興趣點加上用戶標識和興趣度后加入興趣點集合中,等待下一步的分層次多粒度興趣區(qū)域劃分。通過對30個用戶的軌跡進行興趣點提取后共提取出1354個興趣點。

本文采用考慮了興趣度的DBSCPOI算法對興趣點進行聚類,因為DBSCPOI算法是基于密度的聚類算法,需要人工干預聚類的聚類鄰域半徑ε和該鄰域內最少興趣點數MinPts。為了獲得更好的效果,實驗中首先計算出平均興趣點密度,即平均每平方公里的興趣點數目,最終確定劃分為三個層次的聚類參數。由于鄰域面積是以增長,因此鄰域內的最少興趣點數目也以平方增長,各層次的權重βi=2i。經過實驗驗證,上述參數設置方法能夠找出相似的用戶,說明表1的各層聚類參數是合理的。

表1　各粒度下的聚類參數

實驗中首先依次遍歷所有用戶的軌跡,提取出用戶的興趣點集合。隨后分粒度進行興趣點的聚類,得出興趣區(qū)域,計算各個粒度下用戶之間的相似度,最終如式(3)所示按各層權重將不同粒度下的相似度相加即可得到最終用戶之間的相似度。

3.3實驗結果分析

本文采用查準率和查全率來評估用戶相似性計算模型的效果。在實驗中使用了30名用戶的軌跡數據,并計算他們兩兩相似性,為每個用戶尋找到與之最相似的用戶,然后比較用戶與和他最相似用戶的興趣區(qū)域。如果用戶與之最相似用戶訪問相同的興趣區(qū)域越多,說明算法準確度越高。設f(u)為用戶在第i層的ROI集合,在第i層上的查準率為

(5)

那么兩個用戶在所有粒度下的準確率為

(6)

(7)式中ur是選擇出的和用戶U相似度最高的用戶,H表示總的層次數目,βi表示第i層的相似性權重。

而計算查全率的公式為

(8)

(9)

(10)

將本文的方法得到的查全率和查準率,與不劃分層次的方法以及不考慮停留時間(興趣度)采用Jaccard系數的方法進行對比,得到結果如圖2所示,本文所采用方法查準率要比不劃分層次和使用Jaccard系數的方法都要高,在查全率方面也要比Jaccard系數的方法要有優(yōu)勢。表明了分層次多粒度方法和加入興趣度屬性的必要性。

圖2　實驗效果

4　結語

本文基于真實的用戶移動軌跡數據,首先提取出用戶的興趣點,在此基礎上提出分層次多粒度聚類的方法,并改進了傳統(tǒng)的密度聚類算法。該方法在各種鄰域范圍下對用戶興趣點聚類,考察用戶對各聚類區(qū)域的興趣度,并利用向量空間模型計算余弦相似性的方法度量用戶行為軌跡上的相似性。通過統(tǒng)計分析查找出的相似用戶及其訪問的地理位置,運用計算查準率和查全率表明了本方法的有效性。

[1] 陳繼東,孟小峰,賴彩鳳.基于道路網絡的對象聚類[J].軟件學報,2007,18(2):332-344.

CHEN Jidong, MENG Xiaofeng, LAI Caifeng. Clustering objects in a road network[J]. Journal of Software,2007,18(2):332-344.

[2] 龔璽,裴韜,孫嘉,等.時空軌跡聚類方法研究進展[J].地理科學進展,2011,30(5):522-534.

GONG Xi, PEI Tao, SUN Jia, et al. Review of the Research Progresses in Trajectory Clustering Methods[J]. Progress in Geography,2011,30(5):522-534.

[3] Zhang Q, Tse W T, Wan X, et al. Remaining useful life estimation for mechanical systems based on similarity of phase space trajectory[J]. Expert Systems with Applications,2015,42(5):2353-2360.

[4] Kim Y C, Chang J W. A New Similar Trajectory Search Algorithm Based on Spatio-Temporal Similarity Measure for Moving Objects in Road Networks[J]. Ieice Transactions on Information & Systems,2009,92-D(2):327-331.

[5] Lu E, Lee W, Tseng V. A Framework for Personal Mobile Commerce Pattern Mining and Prediction[J]. IEEE Transactions on Knowledge and Data Engineering,2012,24(5):769-782.

[6] 孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學報,2008,19(1):48-61.

SUN Jigui, LIU Jie, ZHAO Lianyu. Clustering algorithms research[J]. Journal of Software,2008,19(19):48-61.

[7] 夏英,溫海平,張旭.基于軌跡聚類的熱點路徑分析方法[J].重慶郵電大學學報:自然科學版,2011,23(5):602-606.

XIA Ying, WEN Haiping, ZHANG Xu. Hot route analysis method based on trajectory clustering[J]. Journal of Chongqing University of Posts and Telecommunications,2011,23(5):602-606.

[8] Gudmundsson J, Valladares N. A GPU Approach to Subtrajectory Clustering Using the Fréchet Distance[J]. IEEE Transactions on Parallel & Distributed Systems,2012,26(4):259-268.

[9] Roubens M. Fuzzy clustering algorithms and their cluster validity[J]. European Journal of Operational Research,1982,10(3):294-301.

[10] NANNI M, PEDRESCHI D. Time-focused density-based clustering of trajectories of moving objects[J]. Journal of Intelligent Information Systems,2006,27(3):267-289.

[11] 張延玲,劉金鵬,姜保慶.移動對象子軌跡分割與聚類算法[J].計算機工程與應用,2009,45(10):65-68.

ZHANG Yanling, LIU Jinpeng, JIANG Baoqing. Partition and clustering for sub-trajectories of moving objects[J]. Computer Engineering and Applications,2009,45(10):65-68.

[12] 袁華,錢宇,楊銳.基于GPS軌跡的用戶興趣點及頻繁路徑挖掘研究[J].系統(tǒng)工程理論與實踐,2015(5):1276-1282.

YUAN Hua,, QIAN Yu, YANG Rui. Research on Gps_Trajectory-Based Personanlizatino Poi and Path Mining[J]. Systems Engineering-Theory & Practice,2015(5):1276-1282.

[13] Chen Z. Mining individual behavior pattern based on significant locations and spatial trajectories[C]//Pervasive Computing and Communications Workshops(PERCOM Workshops), 2012 IEEE International Conference on. IEEE,2012:540-541.

[14] 袁書寒,陳維斌,傅順開.位置服務社交網絡用戶行為相似性分析[J].計算機應用,2012,32(2):322-325.

YUAN Shuhan, CHEN Weibin, FU Shunkai. User behavior similarity analysis of location based social network[J]. Journal of Computer Applications,2012,32(2):322-325.

[15] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial database with noise[C]//KDD-96: Proceedings of the 2nd International Conference on Knowledge Discovering and DataMining. Portland, Oregon: [s.n.],1996:226-231.

User Similarity Analysis Based on Location Trajectory Data

JIA RuoranLIU ShuguangSUN Qilong

(Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing400714)

As location information becomes more convenient, real-time record the user’s movement becomes possible, but analysis of the data on the user trajectory stay on trajectory clusters, and analyzing information of user similarity by the user’s trajecctory research is less. This paper presents a hierarchical multi-granularity: under different neighborhood radius density clustering algorithm. The raditional clustering algorithm is improved by explore according to user’s mobile trajectory analysis of the similarity between users. The method under different granularity computes user’s stay time of each interested area, and then uses the vector space model (VSM) computing users at each particle size, Eventually stacking weights in different granularity of user’s similarity, the similarity is gotten between the user behavior in geographical space. Experimental results based on real user data show that this method can effectively identify similar user access user’s trajectory.

clustering, trajectory, data mining, user similarity

2016年2月11日,

2016年3月30日

賈若然,男,碩士研究生,研究方向:時空數據分析。劉曙光,男,碩士,高級工程師,副研究員,研究方向:消費者洞察時空數據分析。孫啟龍,男,碩士,助理研究員,研究方向:高性能計算。

TP393

10.3969/j.issn.1672-9722.2016.08.026