基于GPS數(shù)據(jù)的周期性行為挖掘*

方濱興，劉 威

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

1 引言

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

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

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

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

·GPS數(shù)據(jù)記錄模塊：利用智能手機(jī)實(shí)時(shí)地感知用戶位置信息，產(chǎn)生GPS軌跡，并定時(shí)地將軌跡提交給后臺(tái)周期挖掘服務(wù)，因?yàn)槭謾C(jī)不可能一直在前端運(yùn)行記錄程序，否則會(huì)影響用戶手機(jī)的其他應(yīng)用，所以GPS數(shù)據(jù)記錄模塊應(yīng)該能夠在后臺(tái)運(yùn)行。

·通信模塊：負(fù)責(zé)智能手機(jī)與后臺(tái)服務(wù)器之間的通信。

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

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

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

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

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

2 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

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

2.2 預(yù)處理模塊

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

2.2.1 去噪模塊

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

（1）速度過濾器

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

（2）加速度過濾器

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

2.2.2 停留點(diǎn)挖掘模塊

停留點(diǎn)通常與用戶的行為關(guān)聯(lián)。如果用戶停留在球場(chǎng)，他很有可能是在打籃球；如果用戶長(zhǎng)時(shí)間停留在建筑物中，那很有可能代表用戶生活或者工作在這里。一些算法僅僅考慮空間信息，并且停留點(diǎn)被定義為包含GPS點(diǎn)大于臨界值的區(qū)域，也就是說停留點(diǎn)包含的GPS點(diǎn)多于其他區(qū)域。這個(gè)算法存在錯(cuò)誤和偏差，因?yàn)楹苡锌赡軙?huì)把一些毫不關(guān)聯(lián)的點(diǎn)包括進(jìn)來，用戶僅僅可能是經(jīng)常路過這里。而且很有可能會(huì)漏掉一些停留點(diǎn)，因?yàn)槿绻谑覂?nèi)，GPS是接收不到衛(wèi)星信號(hào)的，但是這個(gè)建筑物很有可能是與用戶行為相聯(lián)系的停留點(diǎn)。因此，不僅需要考慮空間信息，還需要考慮時(shí)間信息。主要關(guān)注的是停留時(shí)間超過一定臨界值的物理區(qū)域。用這個(gè)物理區(qū)域的中心來表示它，也就是停留點(diǎn)。

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

使用式（1）計(jì)算停留點(diǎn)的緯度，式（2）計(jì)算停留點(diǎn)的經(jīng)度，式（3）計(jì)算進(jìn)入停留點(diǎn)的時(shí)間，式（4）計(jì)算離開停留點(diǎn)的時(shí)間。

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

之后，還需要對(duì)停留點(diǎn)進(jìn)行聚類，因?yàn)椴煌瑫r(shí)間用戶徘徊在同一地點(diǎn)計(jì)算出來的停留點(diǎn)會(huì)有偏差，結(jié)果并不完全一樣，因此需要把實(shí)際上位于同一地點(diǎn)的停留點(diǎn)進(jìn)行聚類，并用聚類后的結(jié)果表示停留點(diǎn)，得到新的序列。

這里將預(yù)處理模塊運(yùn)行在后臺(tái)服務(wù)器，隨著智能手機(jī)的計(jì)算能力越來越強(qiáng)，也可以將預(yù)處理模塊放在手機(jī)上進(jìn)行處理，這樣可以大大減少與服務(wù)器通信的開銷。

2.3 挖掘模塊

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

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

挖掘模塊總共分為如下4個(gè)階段：

·挖掘單事件模式；

·挖掘多事件模式；

·挖掘復(fù)雜模式；

·挖掘異步周期模式。

前3個(gè)階挖掘出來的模式對(duì)應(yīng)顯著分割對(duì)應(yīng)的模式，第4個(gè)階段挖掘出來的模式對(duì)應(yīng)顯著子序列對(duì)應(yīng)的模式。

2.3.1 挖掘單事件模式

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

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

表2 序列的垂直格式

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

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

2.3.2 挖掘多事件模式

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

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

2.3.3 挖掘復(fù)雜模式

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

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

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

2.3.4 挖掘異步周期模式

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

2.3.5 相關(guān)算法比較

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

2.3.2節(jié)的內(nèi)容。

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

3 仿真實(shí)驗(yàn)

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

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

圖2 挖掘的結(jié)果

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

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

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

因?yàn)橥诰蚨嗍录Ｊ胶屯诰驈?fù)雜模式的過程非常相似，所以在這里只討論挖掘復(fù)雜模式的過程。其時(shí)間復(fù)雜度和顯著分割的數(shù)目相關(guān)，模式的平均長(zhǎng)度對(duì)顯著分割數(shù)目的影響是呈指數(shù)增長(zhǎng)的，但是通過圖4看出，運(yùn)行時(shí)間并不是隨模式平均長(zhǎng)度指數(shù)增長(zhǎng)，而是近似于線性增長(zhǎng)，這是因?yàn)橹皩?shù)據(jù)集按照start進(jìn)行排序，這樣沒有重疊部分的顯著分割之間的比較能夠得到避免。

圖4 模式平均長(zhǎng)度對(duì)復(fù)雜模式挖掘的影響

4 結(jié)束語

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

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

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