基于過濾-精煉策略的用戶特定時間段移動軌跡特征提取①

楊東山, 張曉濱

?

基于過濾-精煉策略的用戶特定時間段移動軌跡特征提取①

楊東山, 張曉濱

(西安工程大學計算機科學學院, 西安 710048)

發現移動用戶在特定時間段的軌跡特征是實現用戶個性化推薦服務的關鍵之一. 采用過濾--精煉策略, 研究了如何從單用戶的大量軌跡數據中發現其在較長時間內的特定時間段的興趣點. 在過濾階段, 將用戶連續若干天中同一特定時間段內的軌跡數據進行基于密度的聚類, 從而得到用戶在這些天中每天的該特定時間段的停留點. 在精煉階段, 對所有的停留點再一次聚類, 進而得到用戶在這些天中該特定時間段的興趣點. 最后, 通過實驗驗證了該方法的有效性.

軌跡; 聚類; 停留點; 興趣點

移動設備的廣泛使用和GPS技術的迅猛發展使得海量的時空數據因運而生. 這些數據給人們的生活和學者的科研帶來了新的機遇與挑戰. 通過對用戶的海量的時空數據分析, 我們可以得到用戶在日常生活中感興趣的地點, 從而在許多基于位置的服務中更好地為用戶推薦貼心的個性化服務[1,2]. 而如何高效準確地從海量的時空數據中得到用戶感興趣的地點是研究用戶移動行為的可預見性和獨一性[3,4]進而實現用戶個性化推薦的關鍵問題之一[5,6]. 該問題已經引起了眾多學者的關注和思考.

Palma等人[7]基于改進的DBSCAN算法提出了一種根據用戶移動速度的快慢來識別用戶停留點的算法. 該算法將傳統的DBSCAN算法中的鄰域改為基于路程的Eps-linear-neighborhood, 結合時間MinTime, 對空間數據進行聚類, 所得到的簇作為該用戶的停留點. 此外, 該算法還給出了聚類時所需半徑的計算方法. Zhao Xiuli等人[8]在Palma等人的基礎上對聚類時所需半徑的計算方法做了改進. Zhao等人[8]認為聚類時所需的半徑計算方法應該根據用戶移動的速度快慢分為兩種情況, 而不是Palma等人所認為的只有一種情況. Jose Antonio M.R.Rocha等人[9]提出了一種根據方向變化來識別停留點的方法并且成功地應用于識別漁船的停留點. 上述文獻只是對移動對象的單條軌跡進行了分析, 從而發現一些具有重要意義的位置[10]. 而實際生活中, 用戶某一天的活動規律并不能代表該用戶長期以來一直遵循這條活動規律. 例如: 某用戶有一天去某個商店購物, 然而在接下來的3個月沒有再去該商店購物. 此外, 許多研究旨在找出大量移動對象在一個較長時間段內的相似行為, 用來指導決策[11]. 然而這些方法取決于多個移動對象, 只能用于對熱門區域的分析, 如: 預測到某條路線交通狀況[12,13].

日常生活中, 由于移動通訊網絡使用傳統工作模式(如: 短信服務、廣播服務)[14], 用戶總會隨時隨地收到大量的垃圾信息, 而不是在相應的時間段和相應的地點得到自己感興趣的信息. 這樣, 一方面致使自己所關心的信息被淹沒, 另一方面容易引起用戶對該服務強烈的厭惡和不滿. 因此, 如何從單用戶已有的移動軌跡數據中得到其在特定時間段的興趣點成為解決上述問題的關鍵. 目前, 雖然學者們就如何分析時空數據已經提出了許多改進的基于密度的聚類方法, 但是只采用其中一種算法難以發掘出用戶在較長時間內(如: 3個月)的同一特定時間段(如: 每天的8:00~10:00)的興趣點. 為此, 本文采用過濾--精煉策略, 分兩個階段運用基于密度的聚類, 較好地解決了該問題. 在過濾階段, 對某用戶的連續若干天中的同一特定時間段的軌跡數據聚類, 從而得出該用戶在每一天的該特定時段內的停留點. 在精煉階段, 對這些停留點聚類, 進而得到該用戶在該特定時間段的興趣點.

1 問題描述

定義1 (GPS軌跡). GPS軌跡是由一組連續的GPS點組成的有序序列, 可表示為={(1,1,1),..., (x,y,t)}. 其中(x,y,t)表示用戶的第個GPS點. 在(x,y,t)中,x、y分別表示在時刻用戶的經度和緯度.

定義2 (停留點). 在某段GPS軌跡中, 如果用戶在該段GPS軌跡的子軌跡={(x,y,t),...,(x,y,t)}中的速度, 則為停留點. 其中,為閾值. 由此, 可得出的總路程不能超過閾值, 且該段子軌跡的持續時間.

在實際生活中, 定位系統以恒定的、短暫的時間間隔(通常為2-5秒)采集移動用戶的GPS數據, 所采集數據的位置屬性精度可以達到1m. 通過聚類所獲取的停留點中任意兩個相鄰時間的GPS點之間的距離非常小, 即所包含的GPS點在二維坐標下不僅是密集的, 而且具有一定形狀. 因此, 為了便于計算, 通過計算中、的平均值以獲得的中心位置坐標, 從而將壓縮, 以減少計算量.

圖1 某用戶連續三天8:00~10:00的停留點

定義3 (移動點). 在某段GPS軌跡中, 如果出現下列情況, 則視為移動點: (1)兩個時間相鄰的停留點之間所夾著的那段連續的GPS軌跡點; (2)GPS軌跡的起始點和第一個停留點之間所夾著的那段連續的GPS軌跡點; (3)GPS軌跡的終止點和最后一個停留點之間所夾著的那段連續的GPS軌跡點; (4)如果整條GPS軌跡沒有一個停留點, 則這條GPS軌跡中所有的點都是移動點.

定義4 (興趣點). 將集合{11,12,...,1k;21,22,...,2m;...;T1,T2,...,T’}中的停留點聚類, 所形成的每一個簇代表用戶在這連續的若干天內同一特定時間段經常訪問的地點, 即用戶在該特定時間段的興趣點. 其中, (11,12,...,1k)表示在第一天中用戶在該特定時間段共有個停留點. 類似的, (T1,T2,...,T’)表示在第天中用戶在該特定時間段共有個停留點.

2 特定時間段軌跡特征提取

與其它聚類方法相比, 基于密度的聚類可以發現任意形狀的簇. 這更符合用戶造訪某地的實際情況. 然而, 只采用一種現有的基于密度的聚類算法難以準確地從單用戶的大量軌跡數據中發現其較長時間內同一特定時間段的興趣點. CB-SMoT[7]算法只適合提取用戶單條移動軌跡的停留點. 而ST-DBSCAN[15]算法在處理單條移動軌跡時, 由于無法在時間維度得到適合的半徑, 所以不能發現用戶單條移動軌跡的停留點, 但是它可以對多條移動軌跡進行聚類分析. 綜上, 本文采用過濾--精煉策略, 分為兩個階段(過濾階段和精煉階段)來有效地解決上述問題. 在過濾階段, 從某用戶連續若干天中同一特定時間段的GPS數據中過濾掉用戶每一天該特定時段的移動點, 進而篩選出每一天該特定時段的停留點. 在精煉階段, 從壓縮后的所有停留點中提取出用戶在這些天該特定時間段的興趣點.

2.1 獲取停留點

用戶在運動時, 當其速度在某地變小時, 說明該用戶在此地有停留, 對此地周圍的景物感興趣. 反之, 當用戶的速度變大時, 說明該用戶正忙著趕路, 無暇顧及周圍的景物. 因此, 當用戶一條GPS軌跡中的某一段子軌跡的總路程不能超過閾值, 且該段子軌跡的持續時間大于等于閾值Δ時, 則該段子軌跡被認為是該用戶的停留點.

根據上述理論, 本文在獲取停留點時, 采用Eps-linear-neighborhood鄰域, 即: 在某段子軌跡中, 點的鄰域為

2.2 獲取興趣點

將上一小節所得的所有停留點壓縮, 然后對其聚類, 從而得到用戶在這些天該特定時間段的興趣點. 本次聚類需要三個參數, 它們分別是、、. 其中,用來判斷某一停留點在經緯度維度是否屬于另一停留點的鄰域; 而用來判斷某一停留點在時間維度是否屬于另一停留點的鄰域.、的計算公式如下:

(4)

3 實驗與分析

本文采用微軟(亞洲研究所)對外公開的GeoLife數據集作為實驗數據集. 隨機選取1名用戶A的連續3個月中每天8:00~10:00的GPS數據作為研究對象.

由于在實際生活中人們造訪某地時的速度是在一定范圍內的, 所以在獲取用戶停留點時所需的參數對所有用戶具有通用性. 因此, 本文在獲取用戶停留點時, 根據已有的文獻和先驗知識, 選取了具有通用性的實驗所需的參數. 由于每個用戶的生活習慣不同, 他們在特定時間段內的停留點個數、停留時間的長短不同, 而這些都會直接地對獲取用戶興趣點造成影響, 因此在獲取某用戶興趣點時, 需要尋求適合該用戶的最佳參數, 而不是一概而論. 為此, 本文通過實驗得到適合用戶A在獲取興趣點時所需的最佳參數, 進而驗證了所提出的方法的有效性.

圖2 用戶A某天8:00~10:00的軌跡

圖3 用戶A某天8:00~10:00的停留點

(a)MinPts=2

(b)MinPts=3

(c)MinPts=4

(d)MinPts=5

圖4 用戶A在不同參數下聚類的平均值

使用上述最佳參數組合, 對已經得到的用戶A所有停留點聚類, 得到如圖5所示的結果. 從圖5中可以看出來, 該用戶在這90天中這一時間段內的興趣點共有8個.

圖5 用戶A90天8:00~10:00經常停留的地點

4 結語

本文采用過濾—精煉策略, 運用基于密度的聚類對單用戶在特定時間段的移動軌跡數據進行分析, 從而得到該用戶在指定時間段的興趣點. 這為實現基于位置的個性化推薦服務提供了扎實的基礎. 在實際應用中, 服務商可以根據用戶在特定時間段所處的位置為其提供更準確的個性化推薦服務.

1 宋國杰,唐世渭,楊冬青,等.一種無線通信環境中的用戶移動模式的挖掘算法.軟件學報,2002,13(8):1465–1471.

2 孟祥武,胡勛,王立才,等.移動推薦系統及其應用.軟件學報,2013,24(1):91–108.

3 郭遲,劉經南,方媛,等.位置大數據的價值提取與協同挖掘方法.軟件學報,2014,25(4):713–730.

4 Song C, Qu Z, Blumm N, et al. Limits of predictability in human mobility. Science, 2010, 327(5968): 1018–1021.

5 劉樹棟,孟祥武.一種基于移動用戶位置的網絡服務推薦方法.軟件學報,2014,25(11):2556–2574.

6 劉樹棟,孟祥武.基于位置的社會化網絡推薦系統.計算機學報,2015,38(2):322–336.

7 Palma T, Bogorny V, Kuijpers B, et al. A clustering-based approach for discovering interesting places in trajectories. Proc. of the 2008 ACM Symp. on Applied Computing. New York. ACM. 2008. 863–868.

8 Zhao XL, Xu WX. A clustering-based approach for discovering interesting places in a single trajectory. 2009 Second International Conference on Intelligent Computation Technology and Automation. New York. IEEE. 2009. 429–432.

9 Rocha JAMR, Times VC, Oliveira G, et al. DB-SMOT: A direction-based spatio-temporal clusteringmethod. IEEE Conference of Intelligent Systems. New York. IEEE. 2010. 114–119.

10 劉大有,陳慧靈,齊紅,等.時空數據挖掘研究進展.計算機研究與發展,2013,50(2):225–239.

11 劉奎恩,肖俊超,治明,等.軌跡數據庫中熱門區域的發現.軟件學報,2013,24(8):1816–1835.

12 喬少杰,金琨,韓楠,等.一種基于高斯混合模型的軌跡預測算法.軟件學報,2015,26(5):1048–1063.

13 李國徽,鐘細亞.一種基于固定網格的移動對象運動軌跡索引模型.計算機研究與發展,2006,43(5):828–833.

14 孟祥武,王凡,史艷翠,等.移動用戶需求獲取技術及其應用.軟件學報,2014,25(3):439–456.

15 Birant D, Kut A. ST-DBSCAN: An algorithm for clustering spatial-temporal data. Data & Knowledge Engineering, 2007, 60(1): 208–221.

Feature Extraction for Users’ Trajectories in a Period Based on Filter-Refinement Strategy

YANG Dong-Shan, ZHANG Xiao-Bin

(School of Computer Science, Xi’an Polytechnic University, Xi’an 710048, China)

Finding features of users’ trajectories in a period of time is one of the key point to realize user’s personalized recommendation service. In this paper, how to find the interests in a period from the large amount of user’s trajectories is presented with a filter-refinement strategy. In the filter step, the user’s trajectories in the same period for several certain days are clustered based on density to obtain the user’s stops; in the refinement step, the stops are clustered to obtain the user’s interests. Finally, experiments show the effectiveness of this work.

trajectories; clustering; stop and move; interest

陜西省教育廳科學研究計劃(14JK1307);陜西省自然科學基金(2015JQ5157);西安工程大學研究生創新基金(CX201630)

2016-04-07;收到修改稿時間:2016-05-16

[10.15888/j.cnki.csa.005525]