方濱興,劉 威
(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全研究中心 哈爾濱150001)
在現(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ī)。
下面介紹系統(tǒng)中GPS數(shù)據(jù)記錄模塊、預(yù)處理模塊、挖掘模塊的設(shè)計(jì)以及具體實(shí)現(xiàn)。
由于智能手機(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ù)的格式
預(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ù)器通信的開銷。
發(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)。
實(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)橥诰蚨嗍录J胶屯诰驈?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ù)雜模式挖掘的影響
本文提出的基于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