基于GPS軌跡的周期模式發(fā)現(xiàn)

李海

（江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 211003）

智能手機(jī)和穿戴設(shè)備的興起使得GPS軌跡記錄的采集越來越方便，也為軌跡數(shù)據(jù)挖掘研究帶來了極大的便利。由于人類活動(dòng)是有著某些顯著的且相對固定的移動(dòng)模式[1]，所以周期模式的挖掘不僅為移動(dòng)數(shù)據(jù)的壓縮提供了幫助[2-3]同時(shí)還可以用來預(yù)測該對象未來的移動(dòng)方向[4]及發(fā)現(xiàn)移動(dòng)對象的異常行為。然而，從GPS記錄中發(fā)現(xiàn)用戶的周期模式是一件非常有挑戰(zhàn)的事情。其中有兩個(gè)主要問題需要解決：如何有效預(yù)處理GPS數(shù)據(jù)和如何從時(shí)間序列的發(fā)現(xiàn)周期模式。

已經(jīng)有很多人針對周期模式發(fā)現(xiàn)這個(gè)問題進(jìn)行了研究，但是他們很少考慮到GPS數(shù)據(jù)特殊性：數(shù)據(jù)不是完全正確、采樣頻率的不確定、數(shù)據(jù)的不完整等。2010年，Li提出將傅里葉變換和自相關(guān)系數(shù)結(jié)合尋找周期模式[5]，該方法的不足之處在于采樣頻率過低和數(shù)據(jù)不完整的情況下，很少能找到周期模式。由于用戶的GPS設(shè)備不一定是隨時(shí)都處于工作狀態(tài)以及面臨大量用戶數(shù)據(jù)的時(shí)候，采樣點(diǎn)過密，會(huì)產(chǎn)生大量的數(shù)據(jù)冗余，所以文中主要研究如何處理低采樣的情況。

針對GPS數(shù)據(jù)的特殊性，文中提出一種周期模式的發(fā)現(xiàn)方法GMPF（GPSMulti-Periodic Find），可以有效處理數(shù)據(jù)稀疏和不完整的問題?；镜乃惴ㄋ悸罚菏紫葘PS記錄進(jìn)行預(yù)處理并聚類得到需要的興趣點(diǎn)，然后對興趣點(diǎn)進(jìn)行采樣得到多個(gè)二進(jìn)制的序列，最后采用基于概率的周期發(fā)現(xiàn)算法，從二值序列中發(fā)現(xiàn)每個(gè)興趣點(diǎn)的周期模式。

1 GMPF算法框架

GPS記錄是由一系列 GPS點(diǎn)構(gòu)成的[6]，表示為 P={p1，p2，…，pn}，每個(gè)GPS點(diǎn)數(shù)據(jù)由經(jīng)度，緯度和時(shí)間戳構(gòu)成，pi∈P且pi=（Lat，Lngt，t）。

定義1（GPS軌跡）：GPS軌跡可以看成是關(guān)于GPS點(diǎn)的時(shí)間序列。Tra={p0，p1，…，pn}，?0≤i≤n，pi+1·t>pi·t，其中pi（0≤i≤n）是 GPS 采樣點(diǎn)。

定義 2（停留點(diǎn)）：一個(gè)停留點(diǎn)表示一個(gè)區(qū)域范圍（θd表示區(qū)域半徑）用戶停留的時(shí)間超過了設(shè)定的時(shí)間閾值θt。停留點(diǎn)就是符合以下定義的GPS點(diǎn)的集合P=其中，?mθd且 pn·t-pm·t>θt。 基于上面的介紹給出停留點(diǎn) S 的符號化定義，s=（x，y，ta，

表示當(dāng)前停留點(diǎn)的中心坐標(biāo)，代表這個(gè)停留點(diǎn)的位置，ta表示停留點(diǎn)起始時(shí)間點(diǎn)，tl表示停留點(diǎn)的結(jié)束的時(shí)間點(diǎn)。

定義3（行為的周期模式）：一個(gè)行為的周期模式可以表示成，oi表示第 i個(gè)興趣點(diǎn)，Ti=（lengthi，tai，tli），其中 tai≤tli且lengthi>0，其中l(wèi)engthi表示周期時(shí)間長度。

從上面的定義，文中提出一個(gè)兩步驟的周期發(fā)現(xiàn)算法GMPF（GPSMulti-Periodic Find）。

算法1：GMPF（多周期模式發(fā)現(xiàn)）

輸入：一個(gè)GPS移動(dòng)序列LOC=loc1loc2…locn

輸出：一系列興趣點(diǎn)的周期模式

1：/*階段1：檢測GPS中興趣點(diǎn)*/

2：Find stay spots S={s1，s2，…，sn}； //找到所有的停留點(diǎn)

3：O=ClusterStayPoint（S）；//通過聚類停留點(diǎn)，得到興趣點(diǎn)

4：/*階段2：檢測每個(gè)興趣點(diǎn)的周期模式*/

5:for each oi∈O do

6:P=MinePeriodPattern （oi）；//對每個(gè)興趣點(diǎn)進(jìn)行周期模式挖掘

7:constructPeriodPatternOutput （P）；//構(gòu)造周期模式輸出結(jié)果

算法1描述了GMPF的基本的框架。在第一個(gè)階段主要是找到所有的興趣點(diǎn)（2-3行），然后對每一個(gè)興趣點(diǎn)進(jìn)行周期模式挖掘并輸出相應(yīng)的結(jié)果（5-7行）。

2 興趣點(diǎn)發(fā)現(xiàn)

本文主要是處理兩類停留點(diǎn)，第一類停留點(diǎn)就是一個(gè)人進(jìn)入了某個(gè)區(qū)域，然后在這個(gè)區(qū)域徘徊的時(shí)間超過了一個(gè)閾值；第二類情形就是一個(gè)人GPS記錄保持停止?fàn)顟B(tài)的時(shí)長超過了某個(gè)閾值。

興趣點(diǎn)發(fā)現(xiàn)是對上一步得到的停留點(diǎn)集合進(jìn)行聚類分析，得到其中被訪問次數(shù)較高的區(qū)域。文中提出一個(gè)依賴于閾值假定的聚類方法，其思想類似于DBSCAN，但是不需求去計(jì)算鄰域，而是去掃描已經(jīng)存在簇，當(dāng)數(shù)據(jù)的密度比較高的時(shí)候，效率會(huì)遠(yuǎn)高于DBSCAN，在最壞的情況下也要比DBSCAN的時(shí)間復(fù)雜度要小。由于本文主要挖掘GPS序列中的周期模式，一般來說存在大量周期模式的數(shù)據(jù)中必然存在大量的高密度數(shù)據(jù)簇。

首先從停留點(diǎn)集合中抽出一個(gè)未處理的點(diǎn)，然后遍歷當(dāng)前所有的簇的集合，檢測該點(diǎn)是否屬于某個(gè)簇，如果存在這樣的簇的話，則更新簇的中心。否則認(rèn)為這個(gè)點(diǎn)是一個(gè)新的簇。最后檢測每個(gè)簇的計(jì)數(shù)是否滿足最小計(jì)數(shù)的要求。

3 周期模式挖掘

3.1 移動(dòng)序列二值化

現(xiàn)在得到了一系列的興趣點(diǎn)，下面主要是針對每一個(gè)興趣點(diǎn)進(jìn)行挖掘，找出其中潛在的周期模式。以其中的一個(gè)興趣點(diǎn)為例，首先對整個(gè)移動(dòng)序列進(jìn)行采樣，將這個(gè)移動(dòng)序列轉(zhuǎn)換成一個(gè)二進(jìn)制序列 B=b1，b2，…，bn，當(dāng)這個(gè)移動(dòng)對象在時(shí)間點(diǎn)i的時(shí)候在這個(gè)興趣點(diǎn)區(qū)域內(nèi)，則bi=1，否則 bi=0。

3.2 二進(jìn)制序列周期挖掘模型

定義4（周期序列）在一個(gè)序列X=x（t），0

定義 5 （周期分布向量）定義向量 p=[p0，p1，…，pT-1]∈[0，1]是一個(gè)長度為 T的周期分布向量，x（t）是獨(dú)立且服從pmod（t，T）伯努利分布，則 X=x（t）就是一個(gè)服從周期向量分布 p的二值序列。

定義 6：假設(shè) X 是一個(gè)二值序列，定義 S+={t:x（t）=1}，S-={t:x（t）=0}。 It表示[0:T-1]的冪集，其中 T 表示一個(gè)候選周期。對于任何?I∈It，定義 S+I={t∈S+:FT（t）∈I}，S-I={t∈S-:FT（t）∈I}，其中 FT（t）=mod（t，T），進(jìn)一步用比率形式表示 μx+（I，T）=

定理1：對于一個(gè)長度為n且服從周期向量分布P的二

現(xiàn)在介紹基于定理1的周期發(fā)現(xiàn)方法，對于任意的I∈IT，Δx（I，T）=μx+（I，T）-μx-（I，T）。 當(dāng) T 是本序列的周期，則滿足下面的條件 γ（T）=Δ（I，T），顯然 0≤γx（T）≤1。 當(dāng)序列 X完全符合以T為周期的時(shí)間序列，則γ（T）=1。但是這些只能說明在什么情況下的T是符合要求的，下面還要介紹如何才能找到這個(gè)周期T。

可以得到：

3.3 周期模式挖掘算法

經(jīng)過3.1節(jié)的移動(dòng)序列二值化以后，就可以把得到序列看成是一個(gè)服從某個(gè)周期向量分布的序列。在3.2節(jié)中已經(jīng)介紹了文中尋找潛在周期T的方法，就是計(jì)算每一個(gè)周期T的可能性，然后取概率最大的一個(gè)，具體的步驟如下：

1）設(shè)定一個(gè)最大周期Tmax

2）從區(qū)間[1，Tmax]中按序取出一個(gè)值，賦值給T0

3）用公式（1）和（2）計(jì)算T0是目標(biāo)序列周期的概率

4）重復(fù)第二步，直到完全遍歷

5）取計(jì)算得到的最大P對應(yīng)的T0，這就是當(dāng)前序列的周期

假設(shè)一個(gè)最大可能的周期Tmax，然后通過公式計(jì)遍歷計(jì)算[1，Tmax]，取P最大的那個(gè)T，作為本條序列的周期。

4 實(shí)驗(yàn)及結(jié)果分析

本實(shí)驗(yàn)的運(yùn)行環(huán)境是 Windows 7操作系統(tǒng)，算法的編寫使用 Python語言。主要開發(fā)軟件環(huán)境包括：1）Spyder作為實(shí)驗(yàn)算法實(shí)現(xiàn)和性能測試程序的開發(fā)環(huán)境；2）MySQL作為數(shù)據(jù)庫存儲(chǔ)平臺(tái)。本文使用的數(shù)據(jù)集是微軟亞洲研究院Geolife項(xiàng)目所采集到的數(shù)據(jù)。

算法驗(yàn)證1：為了驗(yàn)證文中的對興趣點(diǎn)的聚類算法的有效性，本文在geolife的編號為0的用戶的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，同時(shí)將實(shí)驗(yàn)的結(jié)果同Yu文章中使用的聚類方法DBSCAN得到的結(jié)果進(jìn)行比較。

GPS記錄點(diǎn)總數(shù)是173 870，通過停留點(diǎn)分析，得到 823個(gè)停留點(diǎn)。然后通過對停留點(diǎn)分別使用DBSCAN和本文的興趣點(diǎn)聚類算法進(jìn)行聚類。實(shí)驗(yàn)結(jié)果如圖1和圖2所示。

圖1 DBSCAN聚類結(jié)果Fig.1 Result of DBSCAN cluster

圖2本文方法聚類結(jié)果Fig.2 Result of our cluster method

由于DBSCAN密度可達(dá)是直接密度可達(dá)的傳遞閉包，并且這種關(guān)系是非對稱的，使其對數(shù)據(jù)集的密度極為敏感。如圖1所示，數(shù)據(jù)被聚類成2個(gè)簇，其中簇1中包含了764個(gè)點(diǎn)，簇2中包含了23個(gè)點(diǎn)。如圖2所示，文中提出的算法將數(shù)據(jù)劃分成了5個(gè)簇，所包含點(diǎn)的個(gè)數(shù)分別為110，294，118，15，17，50。結(jié)合本GPS數(shù)據(jù)的特點(diǎn)，人們?nèi)粘Ｉ畹囊苿?dòng)軌跡數(shù)據(jù)，可以看出本文的算法更符合現(xiàn)實(shí)特點(diǎn)。

算法驗(yàn)證2：二值化序列的周期挖掘算法驗(yàn)證比較，為了驗(yàn)證本文周期挖掘算法在低采樣情況下的有效性，將文獻(xiàn)中[5]提出的FFT集合自相關(guān)系數(shù)，以及文獻(xiàn)[7]中提出的幾種二進(jìn)制序列周期發(fā)現(xiàn)方法和本文的周期挖掘算法進(jìn)行比較。圖3，4，5分別是本文的方法自相關(guān)系數(shù)結(jié)合傅里葉算法、傅里葉結(jié)合直方圖算法在不同采樣率情況下的實(shí)驗(yàn)結(jié)果。

由圖3~5所示，可以發(fā)現(xiàn)在高采樣的情況下，3種算法都是表現(xiàn)良好，但是當(dāng)降低采樣頻率后，后3種方法就不能得到正確的周期了。由此可以看出本文提出的周期算法對低采樣的情況有較好的表現(xiàn)。

實(shí)驗(yàn)驗(yàn)證3：在geolife的編號為0的用戶的數(shù)據(jù)集上，綜合驗(yàn)證本文的算法。在實(shí)驗(yàn)1中得到了5個(gè)興趣點(diǎn)，由于后兩個(gè)興趣點(diǎn)的密度較小，所以只選用前3個(gè)興趣點(diǎn)進(jìn)行驗(yàn)證，假設(shè)這三興趣點(diǎn)分別是公司、家、健身館。最后的得到的實(shí)驗(yàn)結(jié)果如表1。

圖3本文方法Fig.3 Our method

從表中可以看出該用戶的周期模式分別是一天和一周為單位的，符合日常的行為習(xí)慣。

5 結(jié) 論

圖4自相關(guān)系數(shù)結(jié)合傅里葉算法Fig.4 Autocorrelation coefficient combined with Fourier algorithm

圖5傅里葉結(jié)合直方圖算法Fig.5 Fourier combined histogram algorithm

表1 用戶的周期模式檢測結(jié)果Tab.1 Result of Person periodic pattern

本文針對移動(dòng)對象的周期性問題，提出了一個(gè)GMPF算法，主要有兩個(gè)部分構(gòu)成。第一個(gè)部分找到興趣點(diǎn)，不同的興趣點(diǎn)在時(shí)間上是可以重疊的，這個(gè)也就解決了同時(shí)存在多個(gè)周期模式的問題。第二部分主要是挖掘周期模式，由于GPS[8]數(shù)據(jù)采樣頻率的不確定性，采用基于概率統(tǒng)計(jì)的方法來尋找周期。實(shí)驗(yàn)結(jié)果表明本文的方法在數(shù)據(jù)非常稀疏的情況下，也可以取得較好的表現(xiàn)。本文提出的算法框架在最壞情況下的時(shí)間復(fù)雜度是O（n*n），這個(gè)還可以進(jìn)一步的改進(jìn)與提高，也是將來研究的一個(gè)方向。

[1]Gonzalez MC，Hidalgo C A，Barabasi A L.Understanding individualhumanmobilitypatterns[J].Nature，2008，453（7196）:779-782.

[2]Cao H，Mamoulis N，Cheung D W.Discovery of periodic patterns in spatiotemporal sequences[J].IEEE Transactions on Knowledge and Data Engineering，2007，19（4）:453-467.

[3]Xia Y，Tu Y，Atallah M，et al.Reducing Data Redundancy in Location-Based Services[C]//Geosensor，2006.InProcs.of 2nd International Conference on Geosensor Networks，2006:30-35.

[4]Jeung H，Liu Q，Shen H T，et al.A hybrid prediction model for moving objects[C]//IEEE 24th International Conference on.IEEE，2008:70-79.

[5]Li Z，Ding B，Han J，et al.Mining periodic behaviors for moving objects[C]//Proceedings of the 16th ACMSIGKDD international conference on Knowledge discovery and data mining.ACM，2010:1099-1108.

[6]Zheng Y，Zhang L，Xie X，et al.Mining interesting locations and travel sequences from GPS trajectories[C]//Proceedings of the 18th international conference on World wide web.ACM，2009:791-800.

[7]Junier I，Hérisson J，Képès F.Periodic pattern detection in sparse booleansequences[J].Algorithms for Molecular Biology，2010（5）:31.

[8]雷娟，劉文霞.GPS數(shù)據(jù)采集分析器設(shè)計(jì) [J].電子科技，2013（5）:30-33.LEI Juan，LIU Wenxia.Design of a GPS data acquisition analyzer[J].Electronic Science and Technology，2013（5）:30-33.