方濱興，劉 威

（哈爾濱工業(yè)大學計算機網(wǎng)絡與信息安全研究中心 哈爾濱150001）

1 引言

在現(xiàn)在的生活里智能手機越來越普及，智能手機以其強大的功能正在逐漸改變人們上網(wǎng)的方式。此外幾乎每個人都有手機，并且大部分時間都會將手機帶在身邊，用戶可以很方便地通過智能手機的GPS功能獲取用戶當前的位置信息。這些位置信息能夠幫助用戶獲得周圍的信息并且引導用戶到達感興趣的地方,同時還可以將這些位置信息分享給好友。

最近幾年，越來越多的公司和組織提供關于GPS數(shù)據(jù)的服務。對于一些簡單的服務，網(wǎng)絡公司通過向用戶提供位于用戶附近的用戶列表，幫助用戶認識更多的朋友；或者用戶可以直接將自己的位置信息分享給其他人。當然也有一些復雜的服務。人們的運動軌跡往往能夠反映他們的興趣愛好，比如經常去體育館或者籃球場的人可以判定為喜歡做運動；而對于那些經常在自然景觀附近徘徊的人們，可以認為喜歡旅行。因此，可以認為具有相似的運動軌跡數(shù)據(jù)的人們具有相同的興趣?；谶@項服務，可以實現(xiàn)好友推薦功能?？梢詫⒕哂邢嗤瑦酆玫娜送扑]給用戶，這樣用戶就可以很容易地找到志同道合的朋友。另外，還可以從GPS數(shù)據(jù)中挖掘出運動模式[1]。運動模式是描述人們行為的重要屬性，通常運動模式包括步行、自行車、公交車、小汽車等。有了運動模式這個概念，可以把GPS數(shù)據(jù)劃分為不同的運動模式，然后根據(jù)用戶的需要向用戶提供更好的建議。比如系統(tǒng)可以通過對運動模式為小汽車的GPS數(shù)據(jù)進行挖掘，如果用戶想開車到某個地方，這時系統(tǒng)可以根據(jù)挖掘出來的結果向用戶提供一條合理的行車路線。另外通過對運動模式的挖掘，可以發(fā)現(xiàn)其他人都采用什么方式到達同一個地點，幫助用戶做出更好的選擇。

通過智能手機以及其他能夠提供GPS功能的設備，可以收集海量的GPS數(shù)據(jù)。然而，大多數(shù)情況下，應用并不能直接地使用這些數(shù)據(jù)。這是因為GPS數(shù)據(jù)的數(shù)據(jù)量非常巨大，而且一個GPS孤點對于應用來說并沒有太多的意義，因此需要從中挖掘出頻繁周期模式。通過分析周期模式，可以發(fā)現(xiàn)人的運動以及生活規(guī)律。而且周期模式可以看作用戶運動軌跡的壓縮，可以用它們替換原始數(shù)據(jù)節(jié)省空間。此外，在收集GPS數(shù)據(jù)的同時，會不可避免地引入噪聲，因此應該在挖掘之前進行預處理去除噪聲。

在本文中，設計實現(xiàn)了一個基于GPS軌跡發(fā)現(xiàn)用戶生活規(guī)律的系統(tǒng)。系統(tǒng)可以被劃分為以下幾個模塊。

·GPS數(shù)據(jù)記錄模塊：利用智能手機實時地感知用戶位置信息，產生GPS軌跡，并定時地將軌跡提交給后臺周期挖掘服務，因為手機不可能一直在前端運行記錄程序，否則會影響用戶手機的其他應用，所以GPS數(shù)據(jù)記錄模塊應該能夠在后臺運行。

·通信模塊：負責智能手機與后臺服務器之間的通信。

·預處理模塊：后臺接收到手機發(fā)來的軌跡數(shù)據(jù)，由預處理模塊進行預處理，預處理模塊主要包括去噪以及挖掘停留點兩方面內容。

·挖掘模塊：通過對停留點序列進行挖掘獲得頻繁周期模式，最后挖掘出來的模式是異步的[2，3]。這里異步的概念指的是周期模式并不一定是連續(xù)發(fā)生的。也就是說容許一定程度的噪聲，這樣更符合實際情況。

·服務模塊：根據(jù)獲得的周期模式提供服務。這方面內容不是討論的重點，所以主要服務就是向用戶提供挖掘出來的周期模式。系統(tǒng)的模塊如圖1所示。

圖1 系統(tǒng)的模塊

GPS數(shù)據(jù)記錄模塊將記錄的GPS軌跡發(fā)送到通信模塊，通信模塊再將軌跡數(shù)據(jù)發(fā)送到后臺服務器，軌跡序列經過預處理模塊處理之后，就會得到停留點序列。系統(tǒng)的挖掘模塊通過對停留點序列進行挖掘，最后獲得異步頻繁周期模式。挖掘出來的周期模式可以通過通信模塊發(fā)送到智能手機。

2 系統(tǒng)設計與實現(xiàn)

下面介紹系統(tǒng)中GPS數(shù)據(jù)記錄模塊、預處理模塊、挖掘模塊的設計以及具體實現(xiàn)。

2.1 GPS數(shù)據(jù)記錄模塊

由于智能手機的強大功能，可以很簡單地記錄GPS數(shù)據(jù)，但是仍有很多問題需要解決。GPS數(shù)據(jù)記錄模塊實際上就是運行在智能手機的應用程序。當模塊開始運行的時候，應該首先檢查GPS功能是否可用，如果不可用，應該提醒用戶打開GPS，否則模塊將無法正常工作。此外應該保證手機在運行GPS數(shù)據(jù)記錄模塊時不影響手機的其他應用，否則會嚴重影響系統(tǒng)的用戶體驗。所以GPS數(shù)據(jù)記錄模塊應該能在后臺運行，當然在后臺運行并不代表會失去對模塊的控制，必要的時候，仍能夠恢復到前端進行操作。Android開發(fā)中activity生命周期和service生命周期[4,5]能夠幫助實現(xiàn)這個功能。在模塊開始記錄數(shù)據(jù)過程中，按照5 s的時間間隔記錄GPS數(shù)據(jù)，并且將數(shù)據(jù)保存在data.xml中。這些數(shù)據(jù)應該按照表1的格式進行保存。之后按照固定的時間周期將這些數(shù)據(jù)發(fā)送到服務器。

表1 收集的GPS數(shù)據(jù)的格式

2.2 預處理模塊

預處理模塊的主要功能是去噪以及挖掘獲取停留點序列。因此，將預處理模塊劃分為兩個部分：去噪模塊以及停留點挖掘模塊。

2.2.1 去噪模塊

由于GPS系統(tǒng)本身精確度的限制，收集到的GPS數(shù)據(jù)會包含很多離群點。這些離群點大部分是因為GPS信號偏移導致的，尤其是在室內，信號偏移的概率是很高的；就算用戶在戶外，仍然有可能接收到偏移的信號。因此對GPS數(shù)據(jù)進行過濾是很重要的。這里將介紹兩種過濾器，具體如下。

（1）速度過濾器

用戶的移動速度是有一定區(qū)間范圍的。這里認為，對于一個用戶來說合理的速度為0~120 km/h。速度過濾器計算用戶在兩個連續(xù)GPS點之間的速度，如果速度沒有處于這個合理的范圍，就會判定該點是離群點，并將這個點去除掉。這些離群點通常就是信號偏移造成的。

（2）加速度過濾器

速度過濾器是計算兩個連續(xù)GPS點之間的速度，而加速度過濾器是利用這些計算出來的速度，計算3個連續(xù)的位置點之間的加速度。同樣的，個人運動的加速度也有一定的合理范圍。這里認為，合理的加速度應該小于15 m/s2，如果檢測到不合理的加速度，加速度過濾器將過濾掉后一個位置點。GPS接收器接收到漂移數(shù)據(jù)，也會造成異常的運動加速度。

2.2.2 停留點挖掘模塊

停留點通常與用戶的行為關聯(lián)。如果用戶停留在球場，他很有可能是在打籃球；如果用戶長時間停留在建筑物中，那很有可能代表用戶生活或者工作在這里。一些算法僅僅考慮空間信息，并且停留點被定義為包含GPS點大于臨界值的區(qū)域，也就是說停留點包含的GPS點多于其他區(qū)域。這個算法存在錯誤和偏差，因為很有可能會把一些毫不關聯(lián)的點包括進來，用戶僅僅可能是經常路過這里。而且很有可能會漏掉一些停留點，因為如果在室內，GPS是接收不到衛(wèi)星信號的，但是這個建筑物很有可能是與用戶行為相聯(lián)系的停留點。因此，不僅需要考慮空間信息，還需要考慮時間信息。主要關注的是停留時間超過一定臨界值的物理區(qū)域。用這個物理區(qū)域的中心來表示它，也就是停留點。

停留點的挖掘依賴兩個參數(shù)，一是時間臨界值Tthresh，一是空間臨界值Dthresh，P={pm,pm+1,…,pn}是GPS點序列的一組連續(xù)的 GPS 點。對于坌i，其中 m

使用式（1）計算停留點的緯度，式（2）計算停留點的經度，式（3）計算進入停留點的時間，式（4）計算離開停留點的時間。

通常地，這些停留點會出現(xiàn)在兩種情形中。一種是連續(xù)兩個GPS點的間隔時間超過時間臨界值的情形。這種情形大多發(fā)生在用戶進入建筑物內時，因為室內沒有GPS信號，所以看上去就好像用戶這段時間一直保持不動。另一種情形是用戶徘徊在一個小區(qū)域的時間超過了時間的臨界值。這種情形一般發(fā)生在用戶被周圍的風景所吸引或者在戶外參加打籃球等活動。和GPS數(shù)據(jù)相比，停留點包含更多的語義。

之后，還需要對停留點進行聚類，因為不同時間用戶徘徊在同一地點計算出來的停留點會有偏差，結果并不完全一樣，因此需要把實際上位于同一地點的停留點進行聚類，并用聚類后的結果表示停留點，得到新的序列。

這里將預處理模塊運行在后臺服務器，隨著智能手機的計算能力越來越強，也可以將預處理模塊放在手機上進行處理，這樣可以大大減少與服務器通信的開銷。

2.3 挖掘模塊

發(fā)送到后臺的GPS軌跡序列經過預處理模塊處理之后，就會得到停留點序列。系統(tǒng)的挖掘模塊對停留點序列進行挖掘，最后獲得異步頻繁周期模式。異步周期模式可以用來反映用戶的生活規(guī)律。模式P={p1,p2,…,pl}是一個周期長度為 L的模式，其中每一個元素 pi哿E∪*，pi≠覫(1≤i≤L),E代表事件集，這里采用的事件集就是挖掘出來的停留點聚類后的集合。*代表一個任意事件的集合，能夠符合任意事件的要求。D0=d1,d2,…,dl是時序性數(shù)據(jù)集D中的連續(xù)子序列，對于周期模式P={p1,p2,…,pl}，當pi哿di或pi=*，(1≤i≤L)，稱 P 符合 D。

這里引入 3 個變量 min_rep、max_dis和 total_rep[4，5]描述頻繁周期模式。min_rep代表模式連續(xù)發(fā)生的最小次數(shù)。如果有一個連續(xù)的D=D1,D2,…,Dj,對于坌i，其中1

挖掘模塊總共分為如下4個階段：

·挖掘單事件模式；

·挖掘多事件模式；

·挖掘復雜模式；

·挖掘異步周期模式。

前3個階挖掘出來的模式對應顯著分割對應的模式，第4個階段挖掘出來的模式對應顯著子序列對應的模式。

2.3.1 挖掘單事件模式

模式P={p1,p2,…,pl}是一個周期長度為L的模式，其中一個元素p1哿E，其余的pi為*，稱這樣的模式為單一模式。其中p1是一個集合，當p1只包含一個事件，稱該模式為單事件模式，如果p1包含多個事件，稱其為多事件模式。這個階段就是挖掘出所有的單事件模式。

在挖掘之前，應該對序列進行一步處理，將其轉換為垂直格式，這樣處理之后挖掘會更加高效[6]，處理后的結果如表2所示，之后挖掘單事件模式，只需考慮該事件發(fā)生時間的序列。

表2 序列的垂直格式

挖掘單事件模塊可以分為兩個階段：第一個階段就是利用滑動窗口找到所有可能的周期；第二個階段就是基于散列驗證所有可能的周期并得到單事件模式。所謂滑動窗口就是每一次只考慮落入固定窗口的點。設定一個參數(shù)Lmax代表最長可能的周期，這樣將不會考慮大于Lmax的周期。因此，需要將滑動窗口的長度設為Lmax。對于每一個時間點，僅僅考慮落入以該點為起始的滑動窗口的時間點，并分別計算時間間隔，這樣隨著滑動窗口向前滑動，就能統(tǒng)計每個時間間隔發(fā)生的次數(shù)。

對于第二階段，首先檢查第一階段統(tǒng)計的結果，找到發(fā)生次數(shù)大于min_rep的時間間隔作為該事件可能的周期，這樣做可以縮小查找范圍，提高查找效率。這里還利用了一個比較重要的數(shù)據(jù)結構Seg，這個數(shù)據(jù)結構包含兩個參數(shù)：rep和last,分別代表一個可能周期的重復次數(shù)和上一個周期發(fā)生的時間點。給定可能的周期p，定義一個結構體數(shù)組Seg[p]。將任意的時間點通過散列算法映射到Seg[p]中的某一項，這里使用的散列算法是除留余數(shù)法：取時間點t被p除后的余數(shù)為散列地址。通過這種散列就可以找到所有的周期模式，比如Seg[1]代表起點除以周期p等于1的周期模式，因此結構體數(shù)組Seg[p]就包含起點從0到p-1所有可能的情況。在進行遍歷的過程中，對于一個時間點t，首先將其映射到Seg[t%p]，并將時間點與Seg[t%p].last相減，并將 Seg[t%p].last的值設為 t，如果結果等于p,則將Seg[t%p].rep加1并繼續(xù)遍歷。如果不等于p,則比較Seg[t%p].rep是否大于min_rep，如果大于則代表是顯著分割并輸出結果，最后將Seg[t%p].rep設為1并繼續(xù)遍歷。遍歷結束后最后統(tǒng)計一下Seg[p]，找出剩余的顯著分割。挖掘出來的顯著分割應該具有標準化的格式：（segment,rep,p,start），其中 segment代表包含的事件集，rep代表這個顯著分割重復發(fā)生的次數(shù)，p代表周期，start代表顯著分割的起始位置。

2.3.2 挖掘多事件模式

這個階段接收的輸入為上一個階段的輸出，也就是挖掘出來的單事件模式。通過定義知道多事件模式實際上由單事件模式構成，因此這個階段需要做的工作就是按照定義合并單事件模式。這里引入偏移的概念。合并具有相同周期以及相同偏移的顯著分割。通過式（5）計算偏移。合并后的模式重復發(fā)生次數(shù)通過式（6）得到。如果重復發(fā)生次數(shù)大于min_rep，那么合并就是合理的。

合并的過程實際上就是一個深度優(yōu)先遍歷的過程。盡管深度優(yōu)先匹配效率很低，時間復雜度呈指數(shù)增長，但是可以在合并之前對單事件模式按照start進行排序，這樣遍歷不會太深就會結束，從而大大提高了效率。

2.3.3 挖掘復雜模式

模式P={p1,p2,…,pl}是一個周期長度為L的模式，其中至少兩個元素pi,pj哿E，其余的p為*，稱這樣的模式為復雜模式。這個階段接收的輸入為前兩個階段輸出的并集，因此這個階段所需要做的工作就是將前兩個階段挖掘出來的單一模式合并為復雜模式。

合并的過程，仍需利用偏移這個概念。將具有不同偏移但是周期相同的顯著分割進行合并。復雜模式可能是（A,*,B,C）、(B,C,A,*)或者(C,A,*,B)中的一種,但是并不是說可以任意選擇一個，如果任意選擇一個，那么可能造成重復的問題。這里采用具有最大的重復次數(shù)模式來代表合并后的復雜模式，具體來說就是選擇結束位置最小的元素作為模式的第一個元素，結束位置可以通過式（7）得到。可以通過式（8）得到合并后的復雜模式重復發(fā)生的次數(shù)。

挖掘復雜模式和挖掘多事件模式在實現(xiàn)上很相似，所以可以將其合并到一起。

2.3.4 挖掘異步周期模式

這個階段的輸入是前3個階段輸出的結果，這一階段所需要做的工作就是將前3個階段得到的顯著分割合并為顯著子序列。合并的過程需要判斷兩個相鄰的顯著分割之間的雜訊長度是否小于max_dis，如果小于max_dis，則將兩個顯著分割合并為一個子序列。通過遞歸，將所有可以合并的顯著分割合并。最后驗證所有的子序列對應模式重復發(fā)生次數(shù)是否大于total_rep，如果成立，則該子序列為顯著子序列，其對應的模式就是要挖掘的異步周期模式。

2.3.5 相關算法比較

這里將挖掘模塊的挖掘算法和LSI[3]算法進行比較。LSI算法可以分為兩個階段，LSI的第一階段用來挖掘異步的單事件模式，按照時間順序可以分為3個部分執(zhí)行：模式確認（A）、模式生長（B）、模式擴展（C），其中 A 和 B 兩個部分的功能與第2.3.1節(jié)所提到的挖掘單事件模式的功能類似，C部分的功能和第2.3.4節(jié)所提到的挖掘異步周期模式的功能類似。LSI的第二個階段用于計算異步的復雜周期模式，可以大致地看作第2.3.3節(jié)所提到的挖掘復雜模式的功能。和挖掘模塊的挖掘算法相比，LSI中沒有第

2.3.2節(jié)的內容。

對于挖掘單事件模式，LSI第一階段的A和B部分的時間復雜度為k×M×Lmax。這里k可以通過min_rep+max_dis+Lmax獲得[3]，M是數(shù)據(jù)的大小，M=D×T，D 代表時間點個數(shù)，T代表每個時間點事件個數(shù)。而根據(jù)第2.3.1節(jié)的分析，單事件挖掘模塊的時間復雜度為M×Lmax。LSI的第二個階段采用分層搜索的方法來挖掘復雜模式，即通過周期相同較短的復雜模式構造更長的復雜模式。這個算法掃描數(shù)據(jù)集的次數(shù)約等于候選個數(shù)，所以在分割個數(shù)不是特別高的情況下，第2.3.3節(jié)提供的算法擁有更好的表現(xiàn)。

3 仿真實驗

實驗可以分為兩個部分,第一個部分主要就是驗證系統(tǒng)各個模塊的輸出是否符合當初設計的要求，而對于第二個部分，要驗證不同的輸入對系統(tǒng)的影響。

設定 min_rep為 5，max_dis為 3，total_rep為 30。通過對整個系統(tǒng)進行測試，證明系統(tǒng)能夠正常地收集GPS數(shù)據(jù)并且將數(shù)據(jù)發(fā)送到服務器。根據(jù)收集來的GPS數(shù)據(jù)，能夠挖掘出關聯(lián)地點。最后能夠通過挖掘模塊挖掘出異步周期模式。結果如圖2所示。

圖2 挖掘的結果

因為GPS數(shù)據(jù)并不能按照要求進行構造，所以對于第二部分，需要根據(jù)不同實驗的需求測試數(shù)據(jù)。在構造數(shù)據(jù)的過程中，首先組合出C個可能的顯著模式候選，每個顯著模式候選的周期長度服從正態(tài)分布；起始位置服從均勻分布。之后就要將這些顯著模式候選放進每一個時間點內，而每一個模式所形成的劃分及劃分之間的雜訊由幾何分布決定。按照這樣的原則，產生所有顯著的劃分，直到時間軸的最末點，以形成一條顯著的時間序列。另外，將顯著模式插入時間點后，需要檢查每個時間點發(fā)生的事件數(shù)至少服從泊松分布。

因為滑動窗口的原因，對于輸入數(shù)據(jù)集的每一個時間點，都必須進行循序的檢查，也就是說，系統(tǒng)在尋找重復發(fā)生模式的時候，時間軸上的每一個時間點都不能夠被忽略，所以輸入的資料集長度越長，系統(tǒng)尋找周期性模式的時間也應該跟著增加，如圖3所示，當min_rep=15、Lmax=20時，時序性數(shù)據(jù)集長度對挖掘單事件模式運行的影響。圖3中實線代表提出算法的結果，虛線代表LSI（A+B）的結果。通過觀察可知處理相同的數(shù)據(jù)，提出的算法性能更好。

圖3 數(shù)據(jù)集長度對單事件模式挖掘的影響

因為挖掘多事件模式和挖掘復雜模式的過程非常相似，所以在這里只討論挖掘復雜模式的過程。其時間復雜度和顯著分割的數(shù)目相關，模式的平均長度對顯著分割數(shù)目的影響是呈指數(shù)增長的，但是通過圖4看出，運行時間并不是隨模式平均長度指數(shù)增長，而是近似于線性增長，這是因為之前將數(shù)據(jù)集按照start進行排序，這樣沒有重疊部分的顯著分割之間的比較能夠得到避免。

圖4 模式平均長度對復雜模式挖掘的影響

4 結束語

本文提出的基于GPS軌跡發(fā)現(xiàn)用戶的生活規(guī)律的系統(tǒng)共分為3個模塊：第1個模塊為GPS數(shù)據(jù)記錄模塊，利用GPS提供定位信息，從精度上保證了挖掘異步周期模式的可行性；第2個模塊為預處理模塊，用于過濾GPS漂移點與停留點的挖掘；第3個模塊挖掘模塊，是整個系統(tǒng)的核心，對挖掘出來的停留點t點進行異步周期模式挖掘。在挖掘算法方面，采用的是一個4階段算法，包括挖掘單事件模式、挖掘多事件模式、挖掘復雜模式以及挖掘異步周期模式。在整個挖掘過程中，系統(tǒng)利用 min_rep、max_dis、total_rep這3個參數(shù)作為判斷異步周期模式的約束條件。

根據(jù)實驗的結果，系統(tǒng)是穩(wěn)定而高效的。但是在未來的研究和開發(fā)中，這個系統(tǒng)還有很大的拓展和應用空間，比如提供根據(jù)挖掘的周期模式對用戶行為進行預測，并且利用推測出的用戶的行為對用戶進行推薦等基于位置的服務。

1 Liu B.Web Data Mining,2nd Edition.Germany:Springer,2006

2 Felker D.Android Application Development for Dummies.Indiana:Wiley Publishing,2011

3 Yang J,Yu P S,Wang W.Mining asynchronous periodic patterns in time series data.IEEE Transanctions on Knowledge and DataEng,2003,15(3):613~628

4 Wang W,Yang J,Yu P S.Mining patterns in long sequential datawith noise.ACMSIGKDDExplorations Newsletter,2003,2(2):28~33

5 Yang J,Yu P S,Wang W.Meta-patterns:revealing hidden periodic patterns. International Conference on Knowledge Discovering and Data Mining,San Jose,California,USA,2001

6 Zaki M J.Spade:an efficient algorithm for mining frequent sequences.Machine Learning,2001,42(2):31~60

7 Li Q,Zheng Y,Chen Y.Understand transportation mode based on GPS data for Web applications.ACM Transactions on the Web(TWEB),2010,4(1)：247~256

8 Meier R.Professional Android 2 Application Development.Indiana:Wiley

Publishing,2010