物聯(lián)網(wǎng)用戶的時空特征挖掘算法

于海寧，方 舟，馬 超

(1.哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)與信息安全研究中心，黑龍江 哈爾濱 150001；2.黑龍江省網(wǎng)絡(luò)空間研究中心，黑龍江 哈爾濱 150001；3.哈爾濱理工大學(xué) 軟件與微電子學(xué)院，黑龍江 哈爾濱 150040)

0 引言

隨著網(wǎng)絡(luò)技術(shù)、信息技術(shù)的發(fā)展，物聯(lián)網(wǎng)受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。物聯(lián)網(wǎng)成為連接物理世界與虛擬世界的紐帶，并逐步描繪出萬物互聯(lián)的愿景[1]。研究機(jī)構(gòu)Gartner公布的最新報告顯示，2016年全球的網(wǎng)絡(luò)設(shè)備數(shù)量將達(dá)到64億，較2015年增長了30%，預(yù)計(jì)2020年，網(wǎng)絡(luò)設(shè)備的數(shù)量會增長至208億。網(wǎng)絡(luò)規(guī)模迅猛擴(kuò)張的同時也制造了海量的多模態(tài)數(shù)據(jù)。市場調(diào)研機(jī)構(gòu)IDC預(yù)計(jì)，未來全球數(shù)據(jù)總量年增長率將維持在50%左右，預(yù)計(jì)2020年，全球數(shù)據(jù)總量將達(dá)到40 ZB，我國數(shù)據(jù)量將達(dá)到8.6 ZB，占全球的21%左右。在物聯(lián)網(wǎng)環(huán)境下,用戶由傳統(tǒng)的數(shù)據(jù)消費(fèi)者變?yōu)閿?shù)據(jù)生產(chǎn)者。面對海量的用戶數(shù)據(jù)，物聯(lián)網(wǎng)服務(wù)商亟須解決“信息過載，知識匱乏”的問題，為用戶提供個性化、智能化的物聯(lián)網(wǎng)服務(wù)。物聯(lián)網(wǎng)用戶特征是物聯(lián)網(wǎng)個性化應(yīng)用設(shè)計(jì)的基礎(chǔ)依據(jù)之一。物聯(lián)網(wǎng)應(yīng)用往往涉及用戶的時空特性，用戶的時空運(yùn)動模式是時空特性最直接的表現(xiàn).運(yùn)動模式能夠體現(xiàn)出用戶興趣愛好、活動規(guī)律、經(jīng)驗(yàn)等特征，如何發(fā)現(xiàn)時間敏感、空間敏感的用戶特征，以支持物聯(lián)網(wǎng)個性化應(yīng)用，這是急需解決的關(guān)鍵問題。針對該問題，本文提出物聯(lián)網(wǎng)用戶的時空特征挖掘算法，從用戶的GPS軌跡中發(fā)現(xiàn)其隱藏的時空運(yùn)動模式，該方法的創(chuàng)新點(diǎn)概括如下：①提出用戶全球定位系統(tǒng)(Global Positioning System, GPS)軌跡預(yù)處理方法，在綜合考慮GPS點(diǎn)的時間和空間特性的基礎(chǔ)上，挖掘隱藏的熱點(diǎn)區(qū)域序列；②提出熱點(diǎn)區(qū)域序列的異步周期序列模式挖掘模型，刻畫那些頻繁的且呈現(xiàn)出異步周期性的熱點(diǎn)區(qū)域序列；③提出一種基于模式增長的多最小支持度的異步周期的序列模式挖掘算法，發(fā)現(xiàn)異步周期的序列模式，即用戶的時空運(yùn)動特征；④采用真實(shí)和仿真的數(shù)據(jù)集對所提方法進(jìn)行驗(yàn)證與評估。

1 相關(guān)工作

目前已有許多研究關(guān)注從用戶GPS軌跡中挖掘用戶時空運(yùn)動模式[2]，如，軌跡模式挖掘[3-4]、移動對象的位置預(yù)測[5-7]、基于位置的行為識別[8-9]。挖掘GPS軌跡中隱藏的行為模式前，需要對GPS軌跡進(jìn)行處理，發(fā)現(xiàn)對用戶有意義的熱點(diǎn)區(qū)域。上述文獻(xiàn)采用GPS點(diǎn)的密度聚類算法獲取熱點(diǎn)區(qū)域,這些方法只考慮了用戶在空間域內(nèi)頻繁出現(xiàn)的位置，而忽視了用戶在時間域內(nèi)頻繁出現(xiàn)的位置。文獻(xiàn)[10]在空間域和時間域內(nèi)檢測用戶頻繁出現(xiàn)的位置，提出基于停留點(diǎn)的熱點(diǎn)區(qū)域挖掘方法，但該方法忽視了那些用戶沒有停留的，卻具有特殊意義的位置。

通過序列模式挖掘算法和周期模式挖掘算法能夠發(fā)現(xiàn)熱點(diǎn)區(qū)域中隱藏的用戶時空運(yùn)動模式，傳統(tǒng)的序列模式挖掘模型用于發(fā)現(xiàn)序列數(shù)據(jù)庫中所有頻繁的序列模式，其目標(biāo)數(shù)據(jù)庫如表1所示。表中：{a,b,c,d,e,f}是所有項(xiàng)的集合，表示一個序列，例如a(abc)(ac)d(cf)，其中()表示一個項(xiàng)集，如(abc)。時空序列挖掘模型用于發(fā)現(xiàn)時空序列數(shù)據(jù)庫中所有頻繁的時空序列模式，其目標(biāo)數(shù)據(jù)庫如表2所示，表中下標(biāo)t表示項(xiàng)集關(guān)聯(lián)的時間戳。周期模式挖掘模型用于發(fā)現(xiàn)時間序列數(shù)據(jù)庫中所有周期模式，其目標(biāo)數(shù)據(jù)庫如表3所示。

按照這3個挖掘模型，可以將序列的時間屬性劃分為兩個層次：①用于標(biāo)注項(xiàng)集的細(xì)粒度時間屬性，如表4中序列項(xiàng)集的下標(biāo)ti；②用于標(biāo)注序列的粗粒度時間屬性，如表4中序列的時間槽tidi。細(xì)粒度時間屬性是對粗粒度時間屬性的進(jìn)一步劃分。序列挖掘模型僅利用細(xì)粒度時間屬性排序項(xiàng)集，且不關(guān)注序列的粗粒度時間屬性。時空序列挖掘模型將細(xì)粒度時間屬性引入挖掘算法，它以標(biāo)注相似性作為判斷序列相同的依據(jù)，能夠容忍項(xiàng)集時間標(biāo)注的誤差。上述兩個序列挖掘模型均忽視了序列的粗粒度時間屬性，即它們只關(guān)注序列的頻繁性，但忽視了序列在數(shù)據(jù)庫中的分布周期性特征。周期模式挖掘模型雖然能夠以細(xì)粒度時間屬性為標(biāo)準(zhǔn)發(fā)現(xiàn)周期模式，并依此推算出粗粒度時間屬性的周期模式，但它對項(xiàng)集的標(biāo)注要求過于苛刻(細(xì)粒度時間屬性必須被劃分為等間隔的時間段)，且無法容忍頻繁的項(xiàng)集標(biāo)注的時間誤差。此外，對于稀疏的時間序列數(shù)據(jù)庫，周期模式挖掘模型可能產(chǎn)生大量稀疏且無意義的周期模式。因此，現(xiàn)有模型只關(guān)注了序列發(fā)生的頻繁性，而忽視了序列分布的周期性。

表1 符號序列數(shù)據(jù)庫

表2 時空序列數(shù)據(jù)庫

表3 時間序列數(shù)據(jù)庫

表4 粗細(xì)粒度時間標(biāo)注的序列數(shù)據(jù)庫

傳統(tǒng)的序列挖掘算法是在序列數(shù)據(jù)庫中發(fā)現(xiàn)頻繁的序列模式，如PrefixSpan[11]、SPADE[12]等。文獻(xiàn)[11]對傳統(tǒng)的序列挖掘算法進(jìn)行了詳細(xì)的敘述。時空序列挖掘算法本質(zhì)上是一類特殊序列挖掘算法，它需要考慮序列的時間標(biāo)注和空間位置的誤差。文獻(xiàn)[13]提出了基于PrefixSpan的時空序列挖掘算法，在該算法中，時空序列中的時間標(biāo)注不僅用于位置或狀態(tài)的排序，還直接參與序列模式的挖掘。當(dāng)序列模式變得較長時，該算法的復(fù)雜度急劇升高。

周期模式挖掘算法是在時間序列數(shù)據(jù)庫中發(fā)現(xiàn)周期性重復(fù)出現(xiàn)的周期模式.周期模式按照不同特征可以分為以下類型：

(1)完全周期模式挖掘和部分周期模式挖掘 完全周期模式[14]描述了時間序列中的全局的周期性，部分周期模式[15]描述了時間序列中某些局部的周期性。部分周期模式相比于完全周期模式更為松散，也更符合真實(shí)的情況。完全周期模式的挖掘算法在信號分析領(lǐng)域中得到了廣泛的研究，快速傅里葉變換和小波分析經(jīng)常被用來發(fā)現(xiàn)時間序列中的完全周期模式。文獻(xiàn)[16]提出一個基于向下封閉屬性的部分周期模式挖掘算法，通過建立命中模式樹來分離部分周期模式，提高挖掘效率。文獻(xiàn)[17]提出了基于卷積的部分周期挖掘算法，采用基于改進(jìn)的快速傅立葉變換來挖掘部分周期模式。文獻(xiàn)[18]將時間序列劃分為密區(qū)間，挖掘分布于各密區(qū)間上的同步部分周期模式。

(2)同步周期模式和異步周期模式的挖掘 同步周期模式[15]是指如果某周期模式在時間槽ti處發(fā)生，則該周期模式以后發(fā)生的時間槽一定是ti+period×n(n>0)，其中：period是該周期模式的周期長度，不在這些固定時間槽發(fā)生的周期模式被視為不相關(guān)模式。異步周期模式[16]是指如果某周期模式在時間槽ti處發(fā)生，則該周期模式以后發(fā)生的時間槽不再限定只發(fā)生在ti+period×n(n>0)，該周期模式可能隨機(jī)出現(xiàn)在其他時間槽處。同步周期模式是異步周期模式的一個特例，異步周期模式更符合真實(shí)的情況。文獻(xiàn)[16，19]提出一個最長子串識別(Longest Subsequence Identification, LSI)的異步周期模式挖掘算法，試圖發(fā)現(xiàn)一個允許“噪聲”的最長的周期序列，該算法可能會遺漏非最長異步周期序列。針對該缺陷，文獻(xiàn)[20]提出一個基于哈希表和枚舉的改進(jìn)算法SMCA，該算法改進(jìn)了LSI算法的缺陷。文獻(xiàn)[21]提出一個改進(jìn)的頻繁模式樹結(jié)構(gòu)，用于挖掘呈現(xiàn)出周期性的頻繁項(xiàng)集，文獻(xiàn)[22]擴(kuò)展了該算法，使其支持多個最小支持度的周期性的頻繁項(xiàng)集的挖掘。

用戶的GPS軌跡往往具有稀疏性，上述周期挖掘算法無法有效地發(fā)現(xiàn)隱藏的周期模式。雖然上述序列模式挖掘算法能夠應(yīng)對軌跡稀疏性，但它只關(guān)注序列的頻繁性，而忽視了序列分布的周期性。目前，針對稀疏的GPS軌跡，還沒有同時關(guān)注序列模式頻繁性與周期性的挖掘模型與算法，從而導(dǎo)致無法全面、準(zhǔn)確地發(fā)現(xiàn)用戶的時空特征。

2 GPS軌跡的預(yù)處理方法

用戶GPS軌跡的預(yù)處理方法綜合考慮了GPS點(diǎn)的時間和空間特性從GPS軌跡挖掘出隱藏的熱點(diǎn)區(qū)域，并將GPS軌跡轉(zhuǎn)化為熱點(diǎn)區(qū)域序列。該方法由去噪、停留點(diǎn)和切換點(diǎn)檢測、停留點(diǎn)和切換點(diǎn)聚類、停留點(diǎn)和切換點(diǎn)替換4部分構(gòu)成，如圖1所示。

由于GPS系統(tǒng)自身精度的限制，以及天氣和建筑物對GPS信號的影響，原始GPS軌跡中可能存在離群點(diǎn)。原始的GPS軌跡首先需要進(jìn)行過濾去噪處理，刪除軌跡中的離群點(diǎn)。離群點(diǎn)的檢測主要依據(jù)GPS軌跡點(diǎn)的速度和加速度。GPS軌跡的交通模式是指用戶運(yùn)動所使用的交通工具，如步行、跑步、自行車、汽車和地鐵等，識別常見的交通模式能夠有效地豐富GPS軌跡所包含的信息。

一條GPS軌跡Traj是由一組GPS點(diǎn)構(gòu)成的隊(duì)列，每個GPS點(diǎn)pi包含了緯度pi.latitude、經(jīng)度pi.longitude和時間戳pi.time。軌跡表示為Traj=p1→p2→…→pn，其中：n為中的GPS點(diǎn)的數(shù)量，pi.time

停留點(diǎn)代表用戶逗留或徘徊一段時間的地理位置，例如，用戶進(jìn)入屏蔽GPS信號的區(qū)域，并逗留一段時間后離開該區(qū)域(如圖2a); 用戶在一定的地理區(qū)域內(nèi)徘徊(如圖2b); 用戶圍繞地標(biāo)移動(如圖2c)。一個停留點(diǎn)s被視為由一組連續(xù)的GPS點(diǎn)確定的虛擬位置P={pm,pm+1,…,pn}，其中，?m

s.startTime=pn.time，s.endTime=pm.time。

其中：latitude表示停留點(diǎn)的緯度，longitude表示停留點(diǎn)的經(jīng)度，startTime表示停留點(diǎn)的起始時間，endTime表示停留點(diǎn)的結(jié)束時間。

切換點(diǎn)是指用戶交通模式變化的地理位置，例如，用戶基本沒有停滯直接變化交通模式(如圖2d); 切換用戶經(jīng)過停滯后變化交通模式(如圖2e)。一個交通模式切換點(diǎn)s被視為由兩個連續(xù)的GPS點(diǎn)確定的虛擬位置P={p1,p2}，雖然交通模式的變化是瞬時的，但是為了更加準(zhǔn)確地表示交通模式變化的過程，可以引入時間鹽值ΔTsalt。交通模式切換點(diǎn)s表示為一個四元組s=(latitude,longitude,startTime,endTime)，其中：

s.latitude=(p1.latitude+p2.latitude)/2，

s.longitude=(p1.longitude+p2.longitude)/2，

s.startTime=p1.time-ΔTsalt，

s.endTime=p2.time+ΔTsalt。

其中：latitude表示切換點(diǎn)的緯度，longitude表示切換點(diǎn)的經(jīng)度，startTime表示切換點(diǎn)的起始時間，endTime表示切換點(diǎn)的結(jié)束時間。對于未標(biāo)注交通模式的GPS軌跡，采用文獻(xiàn)[23]提出的方法識別其交通模式。

算法1StayPointMiner(sequencegps,θd,θt)

輸入：GPS軌跡sequencegps，距離閾值θd和時間閾值θt；

輸出：停留點(diǎn)與切換點(diǎn)集合S。

1.i=0;gpsNum=|sequencegps|;

2.tm=pi.transMode; //初始的交通模式

3.WHILE(i

4. Stm=Ф; //交通模式切換點(diǎn)集合

5. FOR(j=i;j

6. IF(pj.transMode≠tm)THEN//交通模式變化

7. s.latitude=(pj-1.latitude+pj.latitude)/2;

8. s.longitude=(pj-1.longitude+pj.longitude)/2;

9. s.startTime=pj-1.time-ΔTsalt; //ΔTsalt鹽值

10. s.endTime=pj.time+ΔTsalt;

11. Stm.insert(s);

12. tm=pj.transMode;

13. dis=Distance(pi,pj);

14. IF(dis>θd)THEN

15. ΔT=pj.Time-pi.Time;

16. IF(ΔT>θt)THEN

19. s.startTime=pi.time;

20. s.endTime=pj.time;

21. S.insert(s);

22. ELSE S.insert(Stm)

23. i=j;break;

24. ENDFOR

25.ENDWHILE

26.return S;

GPS軌跡可以表示為停留點(diǎn)和切換點(diǎn)的序列，這個序列被稱為位置軌跡，表示為

其中Δti=Si+1.startTime-Si.endTime。為消除不同位置軌跡的坐標(biāo)偏差，需要對停留點(diǎn)和切換點(diǎn)進(jìn)行聚類。將位置軌跡替換為熱點(diǎn)區(qū)域序列，表示為

其中：Ci是Si所歸屬的熱點(diǎn)區(qū)域，Δti與Loc中的相同。熱點(diǎn)區(qū)域序列將作為后續(xù)序列模式挖掘算法的輸入序列。

3 異步周期的序列模式挖掘模型

3.1 相關(guān)概念定義

在討論異步周期的序列模式挖掘算法之前，首先給出一些基本概念的定義。

假設(shè)I={i1,i2,…,in}是所有項(xiàng)的集合，項(xiàng)集是項(xiàng)的非空子集。序列是項(xiàng)集的有序列表，表示為s=s1,s2,…,sl>，其中：sj是一個項(xiàng)集，它也被稱為s的一個元素，記為sj=(x1,x2,…，xm)，其中xk是一個項(xiàng)。為簡化表達(dá)，如果一個元素由單獨(dú)的項(xiàng)構(gòu)成，則省略元素的括號，如元素“(x)”表示為“x”。一個項(xiàng)最多在序列的一個元素中出現(xiàn)一次，但在序列的不同元素中可多次出現(xiàn)。不失一般性，假設(shè)元素中的項(xiàng)按照字典順序排序，序列中項(xiàng)目的數(shù)目為序列的長度，長度為l的序列被稱為l序列。

異步周期的序列模式挖掘的目標(biāo)數(shù)據(jù)庫為時間標(biāo)注的符號序列數(shù)據(jù)庫(temporal symbolic sequence database)，它是一個元組的集合，TDB={t0,t1,…,t|TDB|-1}，其中：|TDB|是元組的數(shù)量，ti是元組(tid,s)，s表示一個序列，tid表示s發(fā)生的時間槽，如小時、天、周等。TDB的元組按照時間槽升序排序，且時間槽是等間距的。圖3給出了一個由23個元組構(gòu)成的時間的符號序列數(shù)據(jù)。

下面給出子序列和超序列、包含和發(fā)生、前綴、后綴、周期投影數(shù)據(jù)庫、前綴投影數(shù)據(jù)庫的定義。

定義1子序列和超序列。如果存在一組整數(shù)1≤j1

定義2包含和發(fā)生。給定一個序列α和TDB的一個元組t′=(tid′,s′)，t′包含α(或α在t′發(fā)生)，當(dāng)且僅當(dāng)α是s′的一個子序列。例如，如圖3所示，(ab)adf在第一個元組(0,a(abc)(ac)d(cf))中發(fā)生。

定義5周期投影數(shù)據(jù)庫。指定一個時間的符號序列數(shù)據(jù)庫TDB和一個預(yù)設(shè)參數(shù)最大周期max_per，max_per<<(tidf-tidl)，其中tidf和tidl分別是TDB的第一個和最后一個元組的時間標(biāo)識。元組(tidl+i*p,sl+i*p)(0≤i≤m)構(gòu)成了從時間槽l起始的、以p為周期的周期投影數(shù)據(jù)庫prjp,l(TDB)，其中：l

例如，如圖3所示，prj3,1(TDB)包括元組1:(bd)c(bc)(ad),4:bc(bc)(ad),7:c(bc)ab(abd),10:ac(abc)(ad),13:(ac)(abe)cb,16:(cef)a(ab)ddb,19:b(ac)(abd)。

定義6前綴投影數(shù)據(jù)庫。序列α以p為周期的包含片段L，是prjp,l(TDB)中連續(xù)包含α的元組所對應(yīng)的時間槽列表。序列α為時間的符號序列數(shù)據(jù)庫TDB中的一個異步周期的序列模式，則α的前綴投影數(shù)據(jù)庫為TDB中所有以α為前綴的序列關(guān)于α的后綴構(gòu)成的子數(shù)據(jù)庫記為S|α。

下面給出異步周期的序列挖掘模型的相關(guān)概念定義。

定義7包含片段。序列α以p為周期的包含片段L，是prjp,l(TDB)中連續(xù)包含α的元組所對應(yīng)的時間槽列表。包含片段L由四元組(α,p,rep,begin)表示，其中：α是目標(biāo)序列，p是周期，rep是α的重復(fù)發(fā)生次數(shù)(L的重復(fù)計(jì)數(shù))，begin是α重復(fù)發(fā)生的起始位置(L的起始位置)。若在prjp,l(TDB)中，L兩個方向上的相鄰序列都不包含α，則L被稱為最大的包含片段.

如圖3所示，最大包含片段L2記為(a(ab),3,5,7)，它表示a(ab)從tid7起始以3為周期重復(fù)發(fā)生了5次，發(fā)生的tid分別是7,10,13,16,19。相似地，L1記為(a(ab),3,3,0)，L3記為(a(ab),3,3,14)，它們同樣是a(ab)周期為3的最大包含片段。

定義8有效的包含片段。一個最大包含片段L=(α,p,rep,begin)是有效的，當(dāng)且僅當(dāng)L的重復(fù)計(jì)數(shù)不小于預(yù)設(shè)的最小重復(fù)計(jì)數(shù)min_rep，即L.rep≥min_rep。

如圖3所示，假設(shè)min_rep=3，則最大包含片段L1，L2，L3是a(ab)關(guān)于周期3的有效的包含片段，因?yàn)長1，L2，L3的重復(fù)計(jì)數(shù)分別為3、5和3，它們不小于3。

定義9包含片段的間隔。給出兩個包含片段L和L′(L.begin

如圖3所示，L1和L2之間的距離為1(7-6)，L1和L3之間的距離為8(14-6)，L2和L3之間的距離為-5(14-19)。因此，(L1,L2)和(L1,L3)不相交，而(L2,L3)是相交的。

定義10含片段的隊(duì)列。包含片段的隊(duì)列是由滿足以下條件的一組包含片段組成的序列：

(1)包含片段來自相同時間的符號序列數(shù)據(jù)庫，并且是關(guān)于同一序列的相同周期的；

(2)包含片段是有效的；

(3)包含片段按照起始時間槽升序排列；

(4)任意兩個連續(xù)的包含片段是不相交的。

在圖3所示的時間的符號數(shù)據(jù)庫中，若預(yù)設(shè)min_rep=3，max_dis=3，min_sup=6，則(L1→L2)和(L1→L3)是a(ab)的周期為3的有效的包含片段隊(duì)列。

3.2 同步周期的序列模式挖掘模型

3.3 異步周期的序列模式挖掘模型

在許多應(yīng)用中，序列的周期性往往不是完美和精確的，序列的周期段之間可能存在噪聲的干擾。同步周期的序列模式挖掘只能識別“序列缺失”的噪聲，而無法識別“序列偏移”的噪聲。噪聲插入引起的序列偏移會導(dǎo)致許多有價值的序列模式無法被發(fā)現(xiàn)?！跋到y(tǒng)行為”經(jīng)常在一段時間內(nèi)重復(fù)發(fā)生，然后可能改變或消失，這導(dǎo)致序列模式可能在數(shù)據(jù)庫的局部呈現(xiàn)出周期性。

針對上述問題，本文提出了異步周期的序列模式挖掘模型，發(fā)現(xiàn)時間的符號序列數(shù)據(jù)庫中某些時間范圍內(nèi)呈現(xiàn)出周期性的序列模式，并能夠容忍一定程度的噪聲干擾。該模型的核心思想簡述如下：判斷一個序列是否是潛在的異步周期的序列模式，首先，該序列需要在某些時間范圍內(nèi)連續(xù)發(fā)生，這反映了序列具有顯著的周期性的趨勢；然后，檢查這些序列周期性連續(xù)發(fā)生的時間范圍之間的時間間隔，確定這些時間間隔是“隨機(jī)噪聲”還是“系統(tǒng)行為的改變”；最后，在允許噪聲的前提下，序列周期性連續(xù)發(fā)生的時間范圍被連接為最大的序列周期發(fā)生的時間范圍。具體地，異步周期的序列模式及其挖掘模型定義如下：

定義12異步周期的序列模式。序列α是時間的符號數(shù)據(jù)庫TDB的一個異步周期的序列模式，如果在TDB中至少存在一個關(guān)于α的有效的包含片段隊(duì)列，該隊(duì)列關(guān)聯(lián)的周期是異步周期的序列模式α的一個周期。不難發(fā)現(xiàn)，一個異步周期的序列模式可能具有多個周期，而每個周期也可能對應(yīng)了多個有效的包含片段隊(duì)列。

定義13異步周期的序列模式挖掘模型。在指定最小支持度、最大間隔系數(shù)、最小重復(fù)計(jì)數(shù)和最大周期的前提下，異步周期的序列模式挖掘就是發(fā)現(xiàn)時間的符號數(shù)據(jù)庫中所有異步周期的序列模式及其對應(yīng)的有效包含片段隊(duì)列。

4 AP-PrefixspanM挖掘算法

如果使用單一最小支持度進(jìn)行挖掘，則隱含假設(shè)所有項(xiàng)目具有相同的性質(zhì)和相似的出現(xiàn)頻率。該隱含假設(shè)與實(shí)際情景相違背，導(dǎo)致含有稀少但重要項(xiàng)目的序列模式被遺漏。一個完善的異步周期的序列模式挖掘算法應(yīng)該支持多個最小支持度，即用戶可以為每個項(xiàng)目指定一個最小支持度，不同的序列根據(jù)其所包含項(xiàng)目的不同需要滿足不同的最小支持度。多最小支持度不僅能夠避免由于單一最小支持度設(shè)置過低所產(chǎn)生的大量無意義的模式，還能夠?qū)邢∩夙?xiàng)目的模式進(jìn)行挖掘.

為了按照多個最小支持度進(jìn)行異步周期的序列模式的挖掘，本文提出一個基于模式增長的多最小支持度挖掘算法AP-PrefixspanM(Asynchronous Periodic Prex-projected sequential patterns with Multiple minimum item supports)挖掘算法。

4.1 算法的參數(shù)關(guān)系

令MinIS(i)表示第i個項(xiàng)目的最小支持度值，序列模式P的最小支持度是P所有項(xiàng)目中最低的最小支持度值，設(shè)P中項(xiàng)目的集合為i1,i2,…,ik，則P的最小支持度為

min_sup(P)=min(MinIS(i1),

MinIS(i2),…,MinIS(ik))。

令MinREP(i)表示第i個項(xiàng)目的最小重復(fù)計(jì)數(shù)值，P的最小重復(fù)計(jì)數(shù)是P所有項(xiàng)目中最低的最小重復(fù)計(jì)數(shù)，即

min_rep(P)=min(MinREP(i1),

MinREP(i2),…,MinREP(ik))。

令MaxDis(i)表示第i個項(xiàng)目的最大干擾間隔系數(shù)，P的最大干擾間隔系數(shù)是P中所有項(xiàng)目中最高的最大干擾間隔系數(shù)，即

max_dis(P)=max(MaxDIS(i1),

MaxDIS(i2),…,MaxDIS(ik))。

為減少用戶設(shè)置的工作量，又不失一般性，假設(shè)項(xiàng)目的最小重復(fù)計(jì)數(shù)、最大干擾間隔系數(shù)與最小支持度之間存在函數(shù)關(guān)系。具體地，第i個項(xiàng)目的最小重復(fù)計(jì)數(shù)MinREP(i)與最小支持度MinIS(i)之間呈線性遞增關(guān)系：

MinREP(i)=λ×MinIS(i)，0<λ≤1。

第i個項(xiàng)目的最大周期間隔系數(shù)MaxDis(i)與最小支持度MinIS(i)之間呈指數(shù)遞減關(guān)系：

其中：η是預(yù)設(shè)的干擾間隔常數(shù)，max(MinIS)是MinIS中最大的最小支持度。

若MinIS(i1)≤MinIS(i2)≤…≤MinIS(ik)，則MinREP(i1)≤MinREP(i2)≤…≤MinREP(ik)，MaxDIS(i1)≥MaxDIS(i2)≥…≥MaxDIS(ik)。

4.2 算法的主要思想和步驟

為了大幅壓縮異步周期的序列模式挖掘的搜索空間，單一最小支持度的異步周期的序列模式挖掘模型利用向下封閉屬性。

性質(zhì)1向下封閉屬性(Downward Closure Property)。如果序列α是一個異步周期的序列模式，且其有效的包含片段隊(duì)列集合為QSet，則任何α的非空子序列也是異步周期的序列模式，且該子序列的有效的包含片段隊(duì)列的集合是QSet的超集。

當(dāng)使用多個最小支持度進(jìn)行異步周期的序列模式挖掘時，一個異步周期的序列模式的最小支持度可能小于其子序列的最小支持度，因此，無法直接應(yīng)用向下封閉屬性剪枝搜索空間。

AP-PrefixspanM算法的主要思想是采用分治策略，將異步周期的序列模式挖掘問題逐級地分解為互不相交的更小的異步周期的序列模式挖掘的子問題，先深遞歸地挖掘相應(yīng)的子數(shù)據(jù)庫即可以解決子問題。算法的數(shù)據(jù)庫劃分框架如圖4所示，包括兩種劃分方式：①利用向下封閉屬性剪枝搜索空間，在第1層根據(jù)最小支持度向量將數(shù)據(jù)庫拆分為一系列子數(shù)據(jù)庫；②從模式增長的方式產(chǎn)生異步周期的序列模式，在第2層以下的層次按照前綴遞歸產(chǎn)生前綴投影數(shù)據(jù)庫。

AP-PrefixspanM算法首先根據(jù)最小支持度向量拆分?jǐn)?shù)據(jù)庫，產(chǎn)生一系列以單一最小支持度進(jìn)行挖掘的子數(shù)據(jù)庫。其中每次拆分都以一個頻繁項(xiàng)目為基準(zhǔn)，該頻繁項(xiàng)目稱為關(guān)鍵項(xiàng)目，挖掘該子數(shù)據(jù)所采用的單一最小支持度為該關(guān)鍵項(xiàng)目的最小支持度，挖掘這些子數(shù)據(jù)能夠利用向下封閉屬性剪枝搜索空間。具體的數(shù)據(jù)拆分步驟描述如下(具體算法如算法2所示)：

步驟1掃描一遍目標(biāo)數(shù)據(jù)庫TDB，獲取每個真實(shí)支持度至少為MinIS(xi)的項(xiàng)目xi，這樣的xi被稱為頻繁項(xiàng)目，將頻繁項(xiàng)目按照其MinIS(xi)升序排列，獲得列表list=x1,x2,…,xn，(xi≤xi+1)。

步驟2異步周期的序列模式的完全集可以劃分為以下n個互不相交的子集(允許子集為空)：

(1)包含x1的序列模式；

(2)包含x2，但不包含x1的序列模式；

……

(i)包含xi，但不包含{x1,x2,…,xi-1}的序列模式；

……

(n)只包含xn的序列模式。

按上述n個子集將TDB拆分為以下n個子數(shù)據(jù)庫，分別挖掘這些子數(shù)據(jù)庫即可以獲得上述n個異步周期的序列模式子集。

(1)TDB1(關(guān)鍵項(xiàng)目x1)，刪除元組中非頻繁的項(xiàng)目，刪除不包含x1的元組；

(2)TDB2(關(guān)鍵項(xiàng)目x2)，刪除元組中非頻繁的項(xiàng)目和x1，刪除不包含x2的元組；

……

(i)TDBi(關(guān)鍵項(xiàng)目xi)，刪除元組中非頻繁的項(xiàng)目和{x1,x2,…,xi-1}，刪除不包含xi的元組；

……

(n)TDBn(關(guān)鍵項(xiàng)目xn)，刪除元組中除xn以外的所有項(xiàng)目，刪除不包含xn的元組。

針對拆分后的子數(shù)據(jù)庫TDBi，算法以MinIS(xi)作為最小支持度進(jìn)行異步周期的序列模式挖掘。挖掘TDBi中異步周期的序列模式的問題可以分解為一系列互不相交的子問題：

(2)設(shè)α是一個長度為l的異步周期的序列模式，{β1,β2,…,βo}是所有以α為前綴、長度為l+1的異步周期的序列模式集。除α本身以外，以α為前綴的異步周期的序列模式的完全集可以劃分為k個互不相交的子集，第k個子集(1≤k≤o)是以βk為前綴的異步周期的序列模式子集，如圖5所示。

基于上述分析，異步周期的序列模式的挖掘問題可以進(jìn)行遞歸劃分，即每個異步周期的序列模式子集合可以進(jìn)一步劃分，進(jìn)而構(gòu)成一個分治框架。為了挖掘異步周期的序列模式的子集，可以構(gòu)造相應(yīng)的前綴投影數(shù)據(jù)庫，并先深遞歸地挖掘每個前綴投影數(shù)據(jù)庫。針對每個子數(shù)據(jù)庫TDBi具體的挖掘步驟描述如下(具體如算法2中函數(shù)1所示)：

步驟1生成參數(shù)。以MinIS(xi)作為最小支持度，并生成相應(yīng)的最小重復(fù)計(jì)數(shù)MinREP(xi)和最大干擾間隔系數(shù)MaxDIS(xi)。

步驟2發(fā)現(xiàn)長度為1的序列模式。掃描數(shù)據(jù)庫一次，生成所有長度為1的異步周期的序列模式，并將長度為1的異步周期序列模式擴(kuò)展到當(dāng)前前綴之后，獲得長度加1的序列模式。

步驟3劃分搜索空間。將異步周期的序列模式完全集劃分上述長度加1的序列模式為前綴的序列模式子集。

步驟4發(fā)現(xiàn)異步周期的序列模式的子集。分別構(gòu)建相應(yīng)的前綴投影數(shù)據(jù)庫，遞歸地挖掘出每個異步周期的序列模式的子集。具體地，在相應(yīng)的前綴投影數(shù)據(jù)庫中重復(fù)上述步驟，直到不能產(chǎn)生長度為1的異步周期的序列模式為止。在上述挖掘過程中，只有那些包含關(guān)鍵項(xiàng)目的異步周期的序列模式添加到挖掘結(jié)果中，其他模式在完成挖掘后被刪除。

4.3 算法的實(shí)現(xiàn)

AP-PrefixspanM算法的偽碼如算法2所示。首先，根據(jù)最小支持度向量MinIS生成最小重復(fù)計(jì)數(shù)向量MinREP和最大干擾間隔系數(shù)向量MaxDIS(如算法2中步驟1和步驟2所示)。然后，掃描目標(biāo)數(shù)據(jù)TDB一次，找出所有真實(shí)支持度至少為MinIS(xi)的頻繁項(xiàng)目xi，它是潛在長度為1的異步周期的序列模式(如算法2中步驟4所示)，按照最小支持度向量MinIS升序排序頻繁項(xiàng)目，獲得隊(duì)列SPF1(如算法2中步驟5所示)。最后，根據(jù)SPF1，獲取|SPF1|個拆分后的子數(shù)據(jù)庫。針對每個子數(shù)據(jù)庫，調(diào)用MAPPrefixSpan函數(shù)進(jìn)行異步周期的序列模式的挖掘(如算法2中步驟6～步驟10所示)。

算法2AP-PrefixspanM(TDB,MinIS,max_per)。

輸入:目標(biāo)數(shù)據(jù)庫TDB,最小支持度向量MinIS和最大周期max_per；

輸出:所有異步周期的序列模式及有效的包含片段隊(duì)列。

1.MinREP←generateREP(MinIS);

2.MaxDIS←generateDIS(MinIS);

3.L←init_pass(M,TDB);

4.PF1←{〈l〉|l∈L,l.count≥MinIS(l)};

5.SPF1←sort(PF1,ASCEND);

9. MAPPrefixSpan(null,SUB_TDB〈xi〉,〈xi〉,MinIS(xi),MaxREP(xi),MaxDIS(xi));

ENDFOR

函數(shù)1MAPPrefixSpan(prefix,DB,c_item,min_sup,min_rep,max_per,max_dis)。

輸入：前綴prefix，時間標(biāo)識的符號序列數(shù)據(jù)庫TDB，關(guān)鍵項(xiàng)目c_item，最小支持度min_sup，最小重復(fù)計(jì)數(shù)min_rep，最大周期max_per，最大干擾間隔系數(shù)max_dis

2.FOR each tuple t in DB DO

3. IF〈x〉∈t.s,x∈L THEN

4. hash_item[x].count++;hash_item[x].tid←t∪t.tid.tid;

5. IF〈{perfix.litemset,x}〉or〈_x〉∈t.s,x∈L THEN

6. //prefix.litemset是前綴的最后一個項(xiàng)集

7. hash_item[_x].count++;hash_item[_x].tid←t.tid;;

8.ENDFOR

9.FOR each key c in hash_item DO

10. IF hash_item[c].count

11.ENDFOR

12.FOR each key c in hash_item DO

13. ASPDetector(c,hash_item[c],c_item,prefix,min_sup,min_rep,max_per,max_dis);

14. IF c can be extended to prefix THEN

15. newprefix←extend(c,prefix);

16. DB|c←Projectdatabase(c,DB);

17. IF prefix not contain c_item THEN

18. delete tuples in DB|cwhich not contain c_item;

19. IF min_sup≤|DB|c|THEN

20. AP-PrefixspanM(newprefix,DB|c,c_item, min_sup,min_rep,max_per,max_dis);

21.ENDFOR

MAPPrefixSpan函數(shù)通過深度優(yōu)先搜索方式查找所有異步周期的序列模式，其偽碼如函數(shù)1所示。首先，定義一個哈希表hash_itemitem_id,(count,tids)記錄每個頻繁項(xiàng)目的發(fā)生次數(shù)及相應(yīng)的時間槽(如函數(shù)1中步驟1所示)。其中：item_id是哈希表的鍵，二元組(count,tids)是鍵值，count代表item_id的發(fā)生次數(shù)，tids代表item_id發(fā)生的時間槽隊(duì)列。每個項(xiàng)目x都有兩種可能的方式擴(kuò)展到前綴，獲得新的序列模式：①將x加入前綴的最后一個項(xiàng)集，此時，x對應(yīng)的item_id表示為“_x”；②將x獨(dú)立地加入前綴，此時，x對應(yīng)的item_id表示為“x”。掃描投影數(shù)據(jù)庫TDB，通過哈希表hash_item記錄每個項(xiàng)目在兩種擴(kuò)展方式下的發(fā)生次數(shù)及相應(yīng)的時間戳隊(duì)列(如函數(shù)1中步驟2～步驟8所示)。刪除hash_item中發(fā)生次數(shù)小于min_sup的項(xiàng)目(如函數(shù)1中步驟9～步驟11所示)。此時，hash_item中的頻繁項(xiàng)目可能擴(kuò)展到當(dāng)前前綴產(chǎn)生新的異步周期的序列模式。針對每個項(xiàng)目，通過ASPDetector函數(shù)進(jìn)一步判斷頻繁項(xiàng)目擴(kuò)展到前綴的可能性和產(chǎn)生新模式的可能性，如果可以產(chǎn)生新模式，則生成新模式所有有效的包含片段隊(duì)列集合(如函數(shù)1中步驟13所示)。若頻繁項(xiàng)目能擴(kuò)展到前綴，則生成擴(kuò)展后的前綴(如函數(shù)1中步驟15所示)。同時，調(diào)用Projectdatabase函數(shù)產(chǎn)生當(dāng)前項(xiàng)目的前綴投影數(shù)據(jù)庫DB|c，若前綴不包含c_item，則刪除DB|c中不包含關(guān)鍵項(xiàng)目c_item的元組(如函數(shù)1中步驟16～18所示)。若過濾后的DB|c中元組數(shù)量不小于min_sup，則遞歸調(diào)用MAPPrefixSpan函數(shù)，在更小的前綴投影數(shù)據(jù)庫上繼續(xù)查找可以擴(kuò)展到前綴的項(xiàng)目，發(fā)現(xiàn)逐漸增長的異步周期的序列模式(如函數(shù)1中步驟19～步驟20所示)。在上述遞歸過程中，所有異步周期的序列模式及其有效的包含片段隊(duì)列將被發(fā)現(xiàn)。

ASPDetector函數(shù)判斷能否將當(dāng)前項(xiàng)目擴(kuò)展到前綴，進(jìn)而獲得新的增長的異步周期的序列模式(簡稱新模式)，并發(fā)現(xiàn)新模式的有效的包含片段隊(duì)列。模式增長的判斷由3個階段構(gòu)成：①潛在周期探測階段(Potential Period Detection， PPD)；②有效的包含片段探測階段(Valid Segment Detection，VSD)；③有效的包含片段合并階段(Valid Se gment Mergence，VSM)。

(1)PPD階段(如函數(shù)2中步驟3～步驟9所示)負(fù)責(zé)探測新模式所有可能的周期 哈希表hash_periodp,count用于記錄周期的出現(xiàn)次數(shù)，其中鍵值count初始化為1。掃描參數(shù)occur的時間槽隊(duì)列，以隊(duì)列的首個時間槽起始，建立一個長度為最大周期max_per的滑動窗口，分別計(jì)算窗口內(nèi)第一個時間槽與它之后的時間槽之間的時間間隔。在時間槽隊(duì)列的任一時間槽tidi處，計(jì)算tidi和tidj之間的間隔pij=|tidi-tidj|，其中i+1≤j≤min(max_per-i,|occur|)，若pij≤max_per，則hash_period對應(yīng)周期pij的計(jì)數(shù)加1(如函數(shù)2中步驟4和步驟5所示)；否則，停止計(jì)算，將窗口滑動到tidi之前的時間槽tidi+1處，重復(fù)上述計(jì)算過程，產(chǎn)生以pi(1≤pi≤max_per)為周期的新模式的必要條件是周期pi出現(xiàn)的次數(shù)不小于min_rep，即hash_period[pi]≥min_rep。

(2)VSD階段負(fù)責(zé)發(fā)現(xiàn)新模式的所有有效的包含片段 首先，對于每個潛在的周期pi定義一個哈希表hash_segmentpos,(rep,last)來記錄模式的包含片段(如函數(shù)2中步驟10所示)。其中：鍵pos表示模式的偏移量，鍵值(rep,last)記錄包含片段的重復(fù)計(jì)數(shù)和最新時間槽。在時間槽隊(duì)列的任一時間槽tidi處，tidj-hash_segment[posi].last(posi=tidi%pi)表示偏移量為posi時兩次同步發(fā)生的時間間隔。若tidi-hash_segment[posi].last=pi，則這兩次發(fā)生在同一包含片段中是同步連續(xù)的。hash_segment[posi].rep記錄了包含片段的重復(fù)計(jì)數(shù)，當(dāng)hash_segment[posi].rep≥min_rep時，當(dāng)前偏移量為posi的包含片段被認(rèn)為是有效的。具體地，對于每一個周期pi，算法需要掃描一遍時間槽隊(duì)列，針對隊(duì)列中的每個時間槽tidi，計(jì)算偏移量posi=tidj%pi(如函數(shù)2中步驟13所示)，若tidj-hash_segment[posi].last=pi，意味著當(dāng)前包含片段增長，hash_segment[posi].rep加1，并更新hash_segment[posi].last為tidi(如函數(shù)2中步驟15和步驟16所示)，而后繼續(xù)處理下一個時間槽；否則，意味著當(dāng)前包含片段中斷，此時，若hash_segment[posi].rep≥min_rep，意味著當(dāng)前中斷的包含片段是有效的，它以四元組的形式記錄在vs_set中(如函數(shù)2中步驟18～步驟20所示)。該包含片段中斷后，hash_segment[posi].rep重置為1，hash_segment[posi].last更新為tidi(如函數(shù)2中步驟21和步驟22所示)。當(dāng)時間槽隊(duì)列檢驗(yàn)完畢后，再檢查一遍hash_segment，判斷是否存在有效的包含片段(如函數(shù)2中步驟24～步驟27所示)。將所有以pi為周期的有效包含片段按照起始時間槽升序排序(如函數(shù)2中步驟28所示)。針對每個包含片段調(diào)用MergeSeg函數(shù)合并包含片段，生成所有以pi為周期、當(dāng)前包含片段起始的有效的包含片段的隊(duì)列(如函數(shù)2中步驟29～步驟31所示)，并輸出模式中包含關(guān)鍵項(xiàng)目的有效包含片段隊(duì)列。

(3)VSM階段負(fù)責(zé)生成有效的包含片段隊(duì)列MergeSeg函數(shù)采用深度優(yōu)先的枚舉方式將所有可能合并的包含片段組合成隊(duì)列。分別產(chǎn)生不同包含片段起始的片段隊(duì)列，對于每個包含片段，算法采用分治策略，每次查找能夠與起始片段直接合并的片段，分別以這些片段為起始片段遞歸地查找能直接合并的片段，重復(fù)該過程直至沒有可以繼續(xù)合并的片段。具體地，如果起始片段的重復(fù)計(jì)數(shù)不小于min_sup，則輸出該片段(如函數(shù)2中步驟29和步驟30所示)。針對任一起始片段，掃描一遍svs_set，發(fā)現(xiàn)可以直接合并的片段集合(如函數(shù)3中步驟2～步驟7所示)。對于集合中的片段，遞歸地調(diào)用MergeSeg函數(shù)(如函數(shù)3中步驟14所示)，每次遞歸產(chǎn)生更小的片段集合(如函數(shù)3中步驟11所示)，并可能合并出更長的片段隊(duì)列(如函數(shù)3中步驟9所示)。在合并過程中一旦發(fā)現(xiàn)隊(duì)列中片段重復(fù)計(jì)數(shù)的和不小于min_sup，且模式含有關(guān)鍵項(xiàng)目，則輸出該片段隊(duì)列(如函數(shù)3中步驟12和步驟13所示)。

函數(shù)2ASPDetector(fitem,occur,c_item,prefix,min_sup,min_rep,max_per,max_dis)。

輸入:頻繁項(xiàng)目fitem，時間槽列表occur，關(guān)鍵項(xiàng)目c_item，前綴prefix，最小支持度min_sup，最小重復(fù)計(jì)數(shù)min_rep，最大周期max_per，最大干擾間隔系數(shù)max_dis。

2.FOR each tidiin occur.tids DO

3. FOR each tidjin occur.tids,i

4. IF(|tidj-tidi|)≤max_per THEN

5. hash_period[tidj-tidi].count++;

6. ELSE break;

7. ENDFOR

8.ENDFOR

9.FOR each key pithat hash_period[pi]≥min_rep DO

11. vs_set(patten,period,rep,start)←;

12. FOR each tidiin occur.tids DO

13. posi←tidimod pi;

14. IF(tidi-hash_segment[posi].last)==piTHEN

15. hash_segment[posi].rep++;

16. hash_segment[posi].last←tidi;

17. continue;

18. IF hash_segment[posi].rep≥min_rep THEN

19. pattern←extend(prefix,fitem);

20. vs_set←vs_set∪(pattern,pi,hash_segment[posi].rep,hash_segment[posi].last

-pi*(hash_segment[posi].rep-1));

21. hash_list[posi].rep←1;

22. hash_list[posi].last←tidi;

23.ENDFOR

24.FOR each key posithat hash_list[posi]≥min_rep DO

25. pattern←extend(prefix,fitem);

26. vs_set←vs_set∪(pattern,pi,hash_list[posi].rep,

27. ENDFOR

28. svs_set←sort(vs_set);

29. FOR each vsiin svs_set DO

30. IF(vsi.rep≥min_sup)&&(c_item∈pattern)THEN

31. Output(vsi);

32. MergeSeg(vsi,svs_set,vsi.rep,min_sup,max_dis);

33. ENDFOR

函數(shù)3MergeSeg(prefix_segs,svs_set,prefix_sum,min_sup,max_dis)。

輸入：前綴片段prefix_segs，包含片段集合svs_set，前綴片段重復(fù)次數(shù)prefix_sum，最小支持度min_sup，最大干擾間隔系數(shù)max_dis。

2.FOR each vsiin svs_set i>1 DO

3. tail←vs1.start+vs1.period*(vs1.rep-1);

4. IF((vsi.start-tail)>max_dis*p)THEN break;

5. ELSE IF(tail>vsi.start)THEN continue;

6. ELSE VSQ←VSQ∪vsi;

7.ENDFOR

8.FOR each vsiin VSQ DO

9. newprefix_segs←prefix_segs∪vsi;

10. newprefix_sum←prefix_sum+vsi.rep;

11. newsvs_set←svs_set delete segments before vsi;

12. IF(newprefix_sum≥min_sup)&&(c_item∈pattern)THEN

13. Output(newprefix_segs);

14. MergeSeg(newprefix_segs,newsvs_set,prefix_sum,min_sup,max_dis);

15.ENDFOR

5 實(shí)驗(yàn)分析

本文實(shí)驗(yàn)所用數(shù)據(jù)集是微軟亞洲研究院的Geolife數(shù)據(jù)集中4位用戶3年(2007年4月～2010年12月)的GPS軌跡數(shù)據(jù)。數(shù)據(jù)集中的一條GPS軌跡是由一組按照時間升序排列的GPS點(diǎn)所組成的序列，每個GPS點(diǎn)記錄了經(jīng)度、維度、海拔高度、日期和時間。在數(shù)據(jù)集中，用戶120記錄了2135條GPS軌跡，用戶141記錄了1 343條GPS軌跡，用戶060記錄了723條GPS軌跡，用戶060記錄了621條GPS軌跡。本文對這4位用戶的GPS軌跡的距離長度和時間長度進(jìn)行了統(tǒng)計(jì)，如圖6所示，時間長度的統(tǒng)計(jì)結(jié)果如圖7所示。統(tǒng)計(jì)結(jié)果顯示，用戶每天往往只記錄幾個小時的GPS軌跡，且多數(shù)GPS軌跡的時間長度分布在1～2小時之間，較為稀疏，GPS軌跡的距離長度由時間長度和運(yùn)動模式共同決定。

GPS軌跡的轉(zhuǎn)化步驟包括去噪、停留點(diǎn)和切換點(diǎn)檢測、停留點(diǎn)和切換聚類、停留點(diǎn)和切換點(diǎn)替換4個步驟。在去噪過程中，設(shè)置速度和加速度的上限閾值分別設(shè)置為35 m/s和10 m/s2。在停留點(diǎn)的檢測算法中，時間閾值被設(shè)置為15 min，距離閾值被設(shè)置為150 m，即若用戶在150 m的距離內(nèi)徘徊15 min以上，則會產(chǎn)生一個停留點(diǎn)。本文利用OPTICS算法對用戶的停留點(diǎn)和切換點(diǎn)進(jìn)行聚類，其中，ε鄰域最小點(diǎn)數(shù)MinPts參數(shù)設(shè)置為4，可達(dá)距離的閾值設(shè)置為150 m。按照本文提出的GPS軌跡預(yù)處理方法對4位用戶的GPS軌跡進(jìn)行處理，轉(zhuǎn)化后的統(tǒng)計(jì)結(jié)果如表5所示。

表5 用戶GPS軌跡預(yù)處理統(tǒng)計(jì)結(jié)果

利用AP-PrefixspanM算法分別對用戶141的熱點(diǎn)區(qū)域序列進(jìn)行異步周期的序列模式挖掘。圖8給出了在不同最小支持度條件下，異步周期的序列模式的長度分布。當(dāng)最小支持度為1%時，產(chǎn)生了大量的無意義的序列模式，此后，隨著最小支持度的增大，序列模式的數(shù)量急劇減少。當(dāng)最小支持度為4%時，只存在3個長度為1的模式。長度為1的序列模式數(shù)量最多，這是因?yàn)橛脩鬐PS軌跡的時間長度較短，不足以生成較長的序列模式。圖9給出了不同最小支持度條件下，序列模式的周期長度分布。當(dāng)最小支持度不小于2%時，多數(shù)序列模式的周期長度分布在1～14天之間。圖10給出了在不同最小支持度條件下，有效的包含片段隊(duì)列的長度分布，有效的包含片段隊(duì)列的長度是指它所含有的有效包含片段數(shù)量。當(dāng)最小支持度不小于2%時，多數(shù)有效的包含片段隊(duì)列的長度分布在1～3之間。

考慮到用戶真實(shí)GPS軌跡的稀疏性，為進(jìn)一步驗(yàn)證異步周期的序列模式挖掘算法的有效性和穩(wěn)定性，本文依據(jù)文獻(xiàn)[16]設(shè)計(jì)實(shí)現(xiàn)了一個仿真數(shù)據(jù)的生成算法，如算法3所示。首先，算法產(chǎn)生C個可能的異步周期的序列模式，其周期由期望為P的正態(tài)分布生成，模式的項(xiàng)目集數(shù)由期望為T的正態(tài)分布生成，項(xiàng)目集的平均項(xiàng)目數(shù)由期望為I的正態(tài)分布生成，項(xiàng)目出現(xiàn)的概率按照高頻(High)、中頻(Medium)和低頻(Low)3個等級分布，模式的起始位置由期望為N/5的均勻分布決定。然后，針對每一個異步周期的序列模式，產(chǎn)生一組包含片段直至到達(dá)末尾時間槽，并將該模式按照這組包含片段插入到相應(yīng)的時間槽，其中，包含片段的重復(fù)計(jì)數(shù)由期望為R的正態(tài)分布產(chǎn)生。最后，掃描一遍所有的時間槽，如果時間槽中序列為空或較短，則向序列中補(bǔ)充一些項(xiàng)目，項(xiàng)目總數(shù)由期望為T×I的泊松分布產(chǎn)生。

算法3.DataGenerator(N,S,High,Medium,Low,C,P,T,I,R,D)

輸入：參數(shù)及其含義如表5所示。

輸出：仿真數(shù)據(jù)集。

1. FOR i=1 to C do

2. p.period=GaussianDist(P,MAXPER);

3. p.pattern=GenPattern(p.period,T,I,High,Medium,Low);

4. position=UniformDist(N/5);

5. WHILE(1)DO

6. p.local=GeometricDist(R,MAX=N/P);

7. IF(N-position

8. FOR j=1 to p.local DO

9. position+=p.period;

10. insert p.pattern into TIDS[position];

11. ENDFOR

12. p.disturbance=p.period*GeometricDist(D,MAXDIS);

13. postion+=p.disturbance;

14. ENDWHILE

15.ENDFOR

16.FOR i=1 to N DO

17. t=PoissonDist(I,MAX=N);

18. k=t-|TIDS[i]|;

19. random generatek symbols with TIDS[i];

20.ENDFOR

利用仿真數(shù)據(jù)集生成算法得到一個仿真數(shù)據(jù)集，算法參數(shù)值如表6所示。利用AP-PrefixspanM算法對仿真數(shù)據(jù)集進(jìn)行異步周期的序列模式挖掘，算法的最大周期max_per為20，系數(shù)λ和η分別為0.2和10.

表6 仿真數(shù)據(jù)集生成算法參數(shù)設(shè)置

圖11給出了不同最小支持度條件下，異步周期序列模式的長度分布。實(shí)驗(yàn)結(jié)果顯示，隨著最小支持度的減小，序列模式的數(shù)量逐漸增大。當(dāng)將高頻、中頻項(xiàng)目的最小支持度設(shè)置很高(5%)，低頻項(xiàng)目的最小支持度設(shè)置很低(1%)時，出現(xiàn)了大量長度為1或2的序列模式，表明即使只關(guān)注低頻項(xiàng)目，如果最小支持度過低，也會出現(xiàn)大量無意義的序列模式。在其他最小支持度條件下，隨著序列模式長度的增加，序列模式數(shù)量激增，當(dāng)序列模式長度為5時，序列模式數(shù)量達(dá)到最大值，之后隨序列模式長度增加遞減。項(xiàng)目總數(shù)較少導(dǎo)致了長度短的序列模式數(shù)量較少。隨著模式增長，越來越多的項(xiàng)目能夠擴(kuò)展到短模式，導(dǎo)致了模式數(shù)量的激增。隨著模式長度的增加，可擴(kuò)展的項(xiàng)目減少，導(dǎo)致了模式數(shù)量的減少。當(dāng)高中低頻項(xiàng)目的最小支持度分別為4%、3%和2%時，序列模式數(shù)量略高于最小支持度為4%時的序列模式數(shù)量，這說明AP-PrefixspanM算法能夠有效地挖掘出含有稀少項(xiàng)目的異步周期的序列模式，同時避免了產(chǎn)生大量無意義的模式。

圖12給出了不同最小支持度條件下，異步周期序列模式周期長度的分布。實(shí)驗(yàn)結(jié)果顯示，當(dāng)高中低頻項(xiàng)目最小支持度分別為5%、5%和1%時，周期長度呈現(xiàn)出混亂的狀態(tài)，這表明挖掘結(jié)果中存在著大量無意義的序列模式。在其他最小支持度條件下，挖掘出的異步周期的序列模式的周期長度幾乎都是5，這與數(shù)據(jù)集生成算法的預(yù)設(shè)參數(shù)P=5相符合。

圖13給出了在不同的最小支持度條件下，有效的包含片段隊(duì)列的長度分布。實(shí)驗(yàn)結(jié)果顯示，除高中低頻項(xiàng)目最小支持度分別為5%、5%和1%外，在其他最小支持度條件下，有效的包含片段隊(duì)列的長度多數(shù)為3或4。雖然數(shù)據(jù)集生成算法的預(yù)設(shè)參數(shù)R=25，即包含片段的平均重復(fù)計(jì)數(shù)25，但序列模式的獨(dú)立插入和序列的隨機(jī)補(bǔ)充導(dǎo)致許多較短序列模式的包含片段的重復(fù)計(jì)數(shù)大于25，從而使得有效的包含片段隊(duì)列的長度多數(shù)為3或4。

上述實(shí)驗(yàn)結(jié)果證明了AP-PrefixspanM算法能夠穩(wěn)定、有效地用于異步周期的序列模式的挖掘。

5 結(jié)束語

物聯(lián)網(wǎng)應(yīng)用往往涉及用戶的時空特性，用戶的運(yùn)動模式是時空特性最直接的表現(xiàn)。用戶運(yùn)動模式往往呈現(xiàn)出不完美的規(guī)律性，即有序的規(guī)律中摻雜著無序的干擾噪聲。這些不完美的模式揭示了用戶的興趣偏好、行為模式和生活規(guī)律等諸多特征。用戶時空特征為制定個性化物聯(lián)網(wǎng)應(yīng)用提供了決策依據(jù)?；诖耍疚奶岢隽宋锫?lián)網(wǎng)用戶的時空特征挖掘算法，從GPS軌跡中發(fā)現(xiàn)隱藏的用戶運(yùn)動模式，。具體而言，提出了：①GPS軌跡的轉(zhuǎn)化方法，將 GPS 軌跡轉(zhuǎn)化為熱點(diǎn)區(qū)域序列;②異步周期的序列模式挖掘模型，用于發(fā)現(xiàn)時間標(biāo)注的符號序列數(shù)據(jù)庫中頻繁出現(xiàn)的且呈現(xiàn)出異步周期性的序列模式，并識別出它們發(fā)生的時間范圍;③基于模式增長的多最小支持度的異步周期的序列模式挖掘算法，采用分治的策略，將異步周期的序列模式挖掘問題逐級地分解為互不相交的更小的異步周期的序列模式挖掘的子問題，在相應(yīng)的子數(shù)據(jù)庫上進(jìn)行異步周期的序列模式挖掘。實(shí)驗(yàn)結(jié)果證明了該算法的有效性和準(zhǔn)確性。未來將在時空特征挖掘算法中引入地圖的語義信息，進(jìn)而更加全面、準(zhǔn)確地獲取物聯(lián)網(wǎng)用戶的時空特征。