面向移動(dòng)時(shí)空軌跡數(shù)據(jù)的頻繁閉合模式挖掘*

王　亮，汪　梅，郭鑫穎，秦學(xué)斌

(西安科技大學(xué) 電氣與控制工程學(xué)院，陜西 西安 710054)

?

面向移動(dòng)時(shí)空軌跡數(shù)據(jù)的頻繁閉合模式挖掘*

王亮，汪梅，郭鑫穎，秦學(xué)斌

(西安科技大學(xué) 電氣與控制工程學(xué)院，陜西 西安 710054)

移動(dòng)泛在感知設(shè)備的廣泛普及為移動(dòng)軌跡數(shù)據(jù)的大規(guī)模采集、存儲(chǔ)與分析開拓了廣闊的空間。通過對(duì)用戶的移動(dòng)軌跡數(shù)據(jù)進(jìn)行分析挖掘，發(fā)現(xiàn)其中所蘊(yùn)含的有價(jià)值的行為模式與特征，對(duì)于基于位置的服務(wù)(Location-based Service，LBS)，城市交通管理，精準(zhǔn)廣告營銷等領(lǐng)域均具有重要的價(jià)值。文中針對(duì)移動(dòng)軌跡頻繁模式規(guī)模過大、信息冗余問題定義了頻繁閉合移動(dòng)軌跡模式，以經(jīng)典閉合序列模式挖掘算法為基礎(chǔ)提出了適應(yīng)于移動(dòng)軌跡數(shù)據(jù)的頻繁閉合模式CloseTraj算法，分別通過對(duì)仿真數(shù)據(jù)與真實(shí)數(shù)據(jù)的實(shí)驗(yàn)測(cè)試，結(jié)果顯示文中所提出的CloseTraj算法對(duì)于頻繁閉合移動(dòng)軌跡模式挖掘問題具有較強(qiáng)的適用性，同時(shí)在運(yùn)行效率方面具有顯著優(yōu)勢(shì)。

移動(dòng)軌跡；數(shù)據(jù)挖掘；頻繁閉合模式

0　引　言

隨著移動(dòng)通信與定位技術(shù)的不斷發(fā)展，通過攜帶便攜式設(shè)備對(duì)移動(dòng)軌跡數(shù)據(jù)進(jìn)行采集、傳輸與存儲(chǔ)成為可能。利用數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等相關(guān)技術(shù)對(duì)所收集的移動(dòng)軌跡數(shù)據(jù)進(jìn)行挖掘與分析，進(jìn)而從中發(fā)現(xiàn)有價(jià)值的信息與知識(shí)，對(duì)于理解移動(dòng)行為模式、揭示移動(dòng)行為規(guī)律、預(yù)測(cè)移動(dòng)行為趨勢(shì)均具有十分重要的價(jià)值與意義。此外，在應(yīng)用方面，所發(fā)現(xiàn)的價(jià)值信息可以為基于位置的服務(wù)、城市公共管理、移動(dòng)社交網(wǎng)絡(luò)、精準(zhǔn)廣告營銷等領(lǐng)域提供決策依據(jù)。

然而，移動(dòng)軌跡數(shù)據(jù)由于其中所蘊(yùn)含的時(shí)間-空間交叉演化關(guān)系以及背景知識(shí)約束(城市路網(wǎng)，區(qū)域功能定位等方面)，同時(shí)移動(dòng)軌跡背后所隱含的是移動(dòng)者的行為特征，也即“人的特征”，這種“以人為中心”的場(chǎng)景對(duì)于行為特征的提取與行為模式的挖掘分析帶來了極大的挑戰(zhàn)。作為時(shí)間連續(xù)的行為序列數(shù)據(jù)，頻繁模式集中易出現(xiàn)多個(gè)挖掘模式多項(xiàng)集重合、冗余的現(xiàn)象，而現(xiàn)實(shí)社會(huì)中同一社區(qū)群組相近移動(dòng)行為特征的普遍存在更是在一定程度上凸顯了這一問題，為此，文中定義了面向移動(dòng)軌跡的頻繁閉合模式，在序列數(shù)據(jù)頻繁閉合模式挖掘的經(jīng)典算法的基礎(chǔ)上，提出了適應(yīng)于移動(dòng)軌跡數(shù)據(jù)的頻繁閉合模式挖掘算法CloseTraj算法，在對(duì)移動(dòng)軌跡數(shù)據(jù)進(jìn)行模式挖掘時(shí)最大程度的縮減所挖掘的模式規(guī)模，從而使行為模式挖掘過程所產(chǎn)生的模式集合在包含相同信息的前提下，規(guī)模得到最大程度的約簡。

與文中相關(guān)的研究工作主要有以下2類：①頻繁閉合模式；②移動(dòng)軌跡模式挖掘。在頻繁閉合模式挖掘方面，針對(duì)項(xiàng)目集數(shù)據(jù)，Pasquier等于1999年首次提出了頻繁閉合項(xiàng)集挖掘問題[1]。 Pei等利用壓縮頻繁模式樹FP-Tree結(jié)構(gòu)，提出了CLOSET算法以挖掘頻繁閉合項(xiàng)集。Zaki與Hsiao等提出了CHARM算法以挖掘頻繁閉合模式[2]。針對(duì)序列數(shù)據(jù)的模式挖掘問題，Yan等提出了CloSpan算法以挖掘頻繁閉合序列模式，CloSpan算法利用剪枝策略與非頻繁序列剔除策略，通過對(duì)投影數(shù)據(jù)庫的搜索，將所挖掘的頻繁閉合序列模式存儲(chǔ)在晶格結(jié)構(gòu)中[3]。Han等學(xué)者提出了兩方向搜索投影數(shù)據(jù)庫的BIDE算法以有效提升閉合模式挖掘的效率[4]。

在移動(dòng)軌跡模式挖掘方面，F(xiàn).Giannotti等學(xué)者在文獻(xiàn)中定義了一種稱之為T-Patterns的帶時(shí)間注釋的移動(dòng)軌跡序列模式。同時(shí)其提出了熱點(diǎn)空間區(qū)域ROI(Region of Interesting)以表示移動(dòng)對(duì)象頻繁訪問的一類空間區(qū)域。通過分別以靜態(tài)和動(dòng)態(tài)的方式檢測(cè)發(fā)現(xiàn)熱點(diǎn)空間區(qū)域，利用類PrefixSpan 算法對(duì)頻繁時(shí)間注釋移動(dòng)軌跡模式進(jìn)行抽取與挖掘[5]。臺(tái)灣地區(qū)Anthony J.T.Lee 等學(xué)者在中提出了一種基于圖的頻繁時(shí)空軌跡模式挖掘算法GBM。通過構(gòu)建Mapping 圖和軌跡信息List，GBM 算法以深度優(yōu)先搜索策略對(duì)Mapping圖進(jìn)行遍歷搜索以發(fā)現(xiàn)頻繁軌跡模式集合[6]。然而，GBM 算法中所使用的移動(dòng)軌跡數(shù)據(jù)集合是一種簡單的離散相鄰單元序列數(shù)據(jù)，因而無需對(duì)連續(xù)空間域進(jìn)行離散化劃分或是近似處理。新墨西哥州立大學(xué)的曹惠萍等學(xué)者提出了以移動(dòng)軌跡分段簡化方法解決頻繁時(shí)空序列模式挖掘問題[7]。在文獻(xiàn)[7]中，原始移動(dòng)軌跡被轉(zhuǎn)換為分割線段表示的序列數(shù)據(jù)集合，進(jìn)而以基于距離的方法提取頻繁軌跡線段，以及采用改進(jìn)的類Apriori算法與substring tree的結(jié)構(gòu)進(jìn)行頻繁模式挖掘。Chung等學(xué)者在文獻(xiàn)[8]中使用基于Apriori的挖掘算法以發(fā)現(xiàn)移動(dòng)軌跡序列數(shù)據(jù)中的頻繁移動(dòng)模式。Arthur.A.Shaw等在中基于Apriori算法對(duì)以二維空間坐標(biāo)表示的移動(dòng)軌跡數(shù)據(jù)的頻繁模式進(jìn)行了挖掘分析研究[9]。

1　時(shí)空移動(dòng)軌跡頻繁模式

移動(dòng)軌跡數(shù)據(jù)可以表示為如下所示的四元組形式：，其中表示移動(dòng)對(duì)象的空間位置信息，Ti表示與空間位置信息相對(duì)應(yīng)的時(shí)間信息，而Oi表示時(shí)間空間信息以外的其它相關(guān)屬性，比如狀態(tài)，方向，移動(dòng)方式(步行、乘車)等。移動(dòng)軌跡數(shù)據(jù)反映的是移動(dòng)用戶在移動(dòng)過程中的連續(xù)信息片段，通過對(duì)這些信息片段集合的挖掘分析，在個(gè)體層面上可以得到具體用戶的移動(dòng)行為模式特征，比如早晨從家出發(fā)，搭乘公共交通工具經(jīng)過固定的線路到達(dá)單位，下午沿相同路線回家或是外出就餐、娛樂等等；而在群體層面上可以得到較大規(guī)模用戶的共同行為模式，在此基礎(chǔ)之上可以研究人群在城市不同區(qū)域之間的流動(dòng)規(guī)律，市民出行的交通路線選擇等等。

對(duì)于移動(dòng)軌跡數(shù)據(jù)頻繁模式的定義為移動(dòng)軌跡頻繁模式具有如下形式：

→.

且其支持度大于預(yù)先給定的最小支持度閾值。頻繁移動(dòng)模式反映的是移動(dòng)用戶群體在移動(dòng)行為上具有相同的特征或是規(guī)律，其表征的是移動(dòng)用戶在上一時(shí)刻位于位置，而在下一時(shí)刻位于位置，也即移動(dòng)用戶存在從位置向位置移動(dòng)的大概率意義上的規(guī)律。頻繁移動(dòng)軌跡是移動(dòng)軌跡數(shù)據(jù)集中所有支持度大于最小支持度閾值的模式，頻繁軌跡模式的任意子集同樣也是頻繁模式，可以說在頻繁移動(dòng)軌跡模式中存在著較多的冗余信息，即有的模式為其它模式的超集，而有的模式是其他模式的子集。頻繁模式的這一特點(diǎn)限制了頻繁模式挖掘算法的效率。

假設(shè)通過移動(dòng)模式的挖掘之后，產(chǎn)生了2個(gè)不同的移動(dòng)模式，分別為模式(1)→，以及模式(2)→→，且假設(shè)模式(1)與模式(2)具有相同的支持度，則模式(2)完全包含模式(1)。因此通過移動(dòng)頻繁模式挖掘，最終所得到的移動(dòng)模式集合中，如何得到信息量最全面，而數(shù)據(jù)規(guī)模最小的移動(dòng)模式集合是需要考慮的一個(gè)問題。

2　閉合頻繁移動(dòng)軌跡模式挖掘

基于Pasquier等于1999年所提出的頻繁閉合項(xiàng)目集的概念，定義了頻繁閉合移動(dòng)軌跡模式。

定義3：頻繁移動(dòng)模式Tpi屬于頻繁閉合移動(dòng)模式，其必須滿足如下條件，即在頻繁移動(dòng)模式集合中不存在這樣的一個(gè)模式Tpj，使Tpj與Tpi具有相同的支持度值，且Tpj為Tpi的超集。即在所獲取的頻繁移動(dòng)軌跡模式集中，不存在任一模式Tpj，滿足Tpj?Tpi，且support(Tpj)≥support(Tpj)。

與頻繁閉合項(xiàng)目集的性質(zhì)相似，頻繁閉合移動(dòng)軌跡模式集合僅僅是頻繁移動(dòng)軌跡模式集的一個(gè)有限子集，但其包含了所有頻繁項(xiàng)目集的完整信息。根據(jù)頻繁閉合移動(dòng)軌跡模式集可以產(chǎn)生頻繁移動(dòng)軌跡模式全集，然而在數(shù)量上頻繁閉合移動(dòng)軌跡模式集合較頻繁移動(dòng)軌跡模式集有了顯著的減少，有效減緩了挖掘過程的運(yùn)算代價(jià)。

文中以頻繁閉合序列模式挖掘經(jīng)典算法CloSpan為基礎(chǔ)，以FP-Tree表示模式支持度，通過對(duì)移動(dòng)數(shù)據(jù)庫的深度優(yōu)先搜索以挖掘頻繁閉合移動(dòng)軌跡模式，設(shè)計(jì)并實(shí)現(xiàn)了適應(yīng)于移動(dòng)軌跡數(shù)據(jù)的頻繁閉合移動(dòng)軌跡模式挖掘算法CloseTraj算法，CloseTraj算法的偽代碼如下所示：

算法:頻繁閉合移動(dòng)軌跡模式挖掘算法CloseTraj輸入:移動(dòng)軌跡數(shù)據(jù)庫D;用戶自定義最小支持度閾值σ,用戶設(shè)定的空間區(qū)域范圍大小ε;輸出:頻繁閉合移動(dòng)軌跡模式集合S1.基于空間聚類的移動(dòng)軌跡數(shù)據(jù)轉(zhuǎn)化f(x,y,ε);2.計(jì)算聚類空間集合中的元素頻繁度并移除非頻繁聚類空間項(xiàng);3.以長度為1的頻繁聚類空間集合構(gòu)建晶格結(jié)構(gòu)LS;4.對(duì)于每一個(gè)晶格集合LS中的元素ls5.搜索以ls為前綴的投影數(shù)據(jù)庫Dls,同時(shí)擴(kuò)展生成新的頻繁模式;6.剔除非閉合頻繁移動(dòng)軌跡模式;7.更新頻繁模式晶格結(jié)構(gòu)LS.

如圖1所示為頻繁閉合模式挖掘的基本流程：首先對(duì)GPS移動(dòng)軌跡數(shù)據(jù)進(jìn)行數(shù)據(jù)的預(yù)處理過程，包括針對(duì)冗余數(shù)據(jù)的基于速度比較的合并約簡、缺失數(shù)據(jù)的線性插值以及噪聲數(shù)據(jù)的卡爾曼濾波剔除等，經(jīng)過數(shù)據(jù)清洗過程之后生成分段語義軌跡數(shù)據(jù)集合，進(jìn)而對(duì)所覆蓋的空間區(qū)域進(jìn)行近鄰聚類操作以實(shí)現(xiàn)對(duì)連續(xù)空間區(qū)域的離散化處理過程，最后實(shí)現(xiàn)對(duì)閉合頻繁模式的挖掘過程。需要注意的是，在空間區(qū)域聚類部分，基于空間語義近鄰函數(shù)以及移動(dòng)軌跡數(shù)據(jù)的空間分布點(diǎn)密度進(jìn)行連續(xù)空間區(qū)域的聚類處理，定義空間語義近鄰函數(shù)為f(x,y,ε)，其中x和y表示空間坐標(biāo)軸的橫坐標(biāo)與縱坐標(biāo)，也即經(jīng)緯度信息，ε為用戶設(shè)定的空間區(qū)域范圍大小，該參數(shù)的大小表征語義軌跡中空間粒度的粗細(xì)程度。

圖1　移動(dòng)軌跡數(shù)據(jù)頻繁閉合模式挖掘流程Fig.1　Closed pattern mining process of mobile trajectory data

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

實(shí)驗(yàn)運(yùn)行環(huán)境的CPU為Intel(R)Core(TM)i3-311M @2.40 GHz，內(nèi)存為4.00 GB，操作系統(tǒng)為Win7，所有的實(shí)驗(yàn)采用C++實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)分別采用仿真數(shù)據(jù)與真實(shí)數(shù)據(jù)，其中仿真數(shù)據(jù)為隨機(jī)移動(dòng)軌跡數(shù)據(jù)與自定義頻繁移動(dòng)軌跡數(shù)據(jù)的合成數(shù)據(jù)集，其中隨機(jī)軌跡數(shù)據(jù)的產(chǎn)生如下：假設(shè)移動(dòng)個(gè)體初始隨機(jī)定位于某一空間位置，其次以某一隨機(jī)概率向其近鄰的若干個(gè)網(wǎng)格遷移或是繼續(xù)停留在當(dāng)前所處的移動(dòng)網(wǎng)格單元之內(nèi)，軌跡的長度服從Poisson 分布規(guī)律，軌跡平均長度從12到20不等，數(shù)據(jù)規(guī)模為12 M，相應(yīng)的實(shí)驗(yàn)結(jié)果如圖2～圖4所示。真實(shí)數(shù)據(jù)為雅典某學(xué)校校車GPS軌跡數(shù)據(jù)，數(shù)據(jù)集規(guī)模為352 M，相應(yīng)的實(shí)驗(yàn)結(jié)果如圖5所示。

對(duì)上述算法進(jìn)行仿真數(shù)據(jù)測(cè)試試驗(yàn)，第一個(gè)實(shí)驗(yàn)為移動(dòng)軌跡數(shù)據(jù)的空間聚類實(shí)驗(yàn)，即基于空間近鄰函數(shù)關(guān)系的連續(xù)空間離散化聚類，ε參數(shù)在隨機(jī)數(shù)據(jù)集與真實(shí)GPS數(shù)據(jù)集中的值分別設(shè)置為2個(gè)單位與125 m，最終的聚類結(jié)果如圖2所示為64個(gè)互不重合的空間區(qū)域，圖示為64個(gè)離散空間區(qū)域之間基于移動(dòng)軌跡數(shù)據(jù)的關(guān)聯(lián)矩陣可視化結(jié)果，所獲取的關(guān)聯(lián)矩陣中元素mi,j表示實(shí)驗(yàn)數(shù)據(jù)中從離散區(qū)域i到j(luò)的軌跡個(gè)數(shù)。第二個(gè)實(shí)驗(yàn)為ColseTray算法的效率測(cè)試，即不同最小支持度閾值下算法的運(yùn)行時(shí)間測(cè)試。第三個(gè)實(shí)驗(yàn)為ColseTray算法的擴(kuò)展性測(cè)試，具體為平均軌跡長度下算法的運(yùn)行時(shí)間測(cè)試。

圖2　移動(dòng)軌跡空間近鄰聚類結(jié)果圖示Fig.2　Neighbor clustering result of mobile trajectory spatial

圖3所示為分別基于不同的搜索方式：深度優(yōu)先搜索與廣度優(yōu)先搜索實(shí)現(xiàn)的頻繁閉合移動(dòng)軌跡模式挖掘效率實(shí)驗(yàn)，深度優(yōu)先搜索算法為CloseTraj算法，其中最小支持度分別為0.5%到1%之間均勻取值，從圖中可以看出，隨著支持度的不斷增大，2種算法的時(shí)間消耗呈指數(shù)規(guī)律遞減，同時(shí)與廣度優(yōu)先搜索相比較，采用深度優(yōu)先搜索方式的CloseTraj算法其運(yùn)行時(shí)間更短。

圖3　2種不同搜索方式下的算法運(yùn)行時(shí)間Fig.3　Algorithm running time of two different search methods

圖4 所示為不同移動(dòng)軌跡平均長度在最小支持度分別為0.5%，0.6%以及0.7%下的算法運(yùn)行時(shí)間結(jié)果圖示。由圖可以看出，隨著移動(dòng)軌跡平均長度的不斷增加，其算法運(yùn)行時(shí)間呈線性增長趨勢(shì)；且相同平均長度的移動(dòng)軌跡在最小支持度越小的條件下其運(yùn)行時(shí)間越長，增長越快。

圖4　不同平均移動(dòng)軌跡長度下的算法運(yùn)行效率Fig.4　Algorithm running efficiency of different average length mobile trajectories

此外，利用CloseTraj算法對(duì)雅典市真實(shí)車輛GPS移動(dòng)軌跡數(shù)據(jù)進(jìn)行了閉合頻繁移動(dòng)模式挖掘?qū)嶒?yàn)測(cè)試，如圖5所示為所挖掘的閉合頻繁模式集合中的一個(gè)模式Google Earth可視化結(jié)果，圖中紅色的氣泡圖標(biāo)表示的是所在的空間位置，由圖中可見，該閉合模式長度為3，方向從下向上移動(dòng)。

圖5　頻繁閉合移動(dòng)軌跡模式的Google Earth圖示Fig.5　Google Earth picture of frequent closed mobile trajectory patterns

4　結(jié)　論

文中針對(duì)移動(dòng)軌跡數(shù)據(jù)的頻繁閉合模式挖掘問題展開研究，利用深度優(yōu)先搜索方式，基于經(jīng)典序列數(shù)據(jù)的頻繁閉合模式挖掘算法提出了適用于上述問題的CloseTraj算法，分別進(jìn)行了基于仿真數(shù)據(jù)與真實(shí)數(shù)據(jù)的算法運(yùn)行實(shí)驗(yàn)。在算法運(yùn)行效率方面，實(shí)驗(yàn)結(jié)果顯示隨著支持度的不斷增大，算法運(yùn)行時(shí)間呈指數(shù)規(guī)律遞減；在時(shí)間可擴(kuò)展性方面，隨著移動(dòng)軌跡平均長度的增加，算法運(yùn)行時(shí)間呈線性增長趨勢(shì)，即所提出的算法在效率性及可擴(kuò)展性方面均具有較好的性能。

References

[1]Pasquier N，Bastide Y，Taouil R，et al.Discovering frequent closed itemsets for association rules[C]//Database Theory-ICDT’99.Springer Berlin Heidelberg，1999：398-416.

[2]Zaki M J，Hsiao C J.CHARM：An efficient algorithm for closed itemset mining[C]//SDM，2002(2)：457-473.

[3]Yan X，Han J，Afshar R.CloSpan：Mining closed sequential patterns in large datasets[C]//In SDM，2003：166-177.

[4]Wang J，Han J.BIDE：Efficient mining of frequent closed sequences[C]//Data Engineering，2004.Proceedings.20th International Conference on.IEEE，2004.

[5]Fosca Giannotti，M.Nanni，F(xiàn).Pinelli，D.Pedreschi，Trajectory pattern mining[C]//In：Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Scan Jose，California，USA，2007.

[6]Anthony J T Lee，Yi-An Chen，Weng-Chong IP.Mining frequent trajectory patterns in spatial-temporal database[J].Information Sciences，2009，179(13)：2 218-2 231.

[7]Huiping Cao，Nikos Mamoulis，David W.Cheung，Mining frequent spatio-temporal sequential patterns[C]//In：Proceedings of the Fifth IEEE International Conference on Data Mining，ICDM，2005.

[8]Jae Du Chung，Oh Hyun Paek，Jun Wook Lee，et al.Temporal pattern mining of moving objects for location-based service[C]//In：Proceedings of the 13th International Conference on Database and Expert Systems Applications，331-340.

[9]Arthur A Shaw，Gopalan N P.Frequent pattern mining of trajectory coordinates using apriori Algorithm[J].International Journal of Computer Application，2011,22(9)：1-7.

Frequent closed patterns mining for mobile trajectory data

WANG Liang，WANG Mei，Guo Xin-ying，QIN Xue-bin

(CollegeofElectricalandControlEngineering,Xi’anUniversityofScienceandTechnology,Xi’an710054,China)

Thankstothewidespreadpopularityofmobileubiquitoussensingdevices,theacquisition,storageandanalysisoflarge-scalemobiletrajectorydatahavebroadprospectsfortechnologyapplications.Bythemeansofanalysisandminingforusers’mobiletrajectoryhistory,wediscovermeaningfulbehaviorpatternsandcharacteristicsbehindtherecordedtrajectories.Theabove-mentioneddiscoveredknowledgeisofgreatvalueforlocation-basedservices,urbantrafficmanagement,targetadvertisingandmanyotherareas.Inthispaper,aimedattheover-sizedissueandinformationredundancyprobleminfrequentmovementtrajectorypatterns,aconceptionoffrequentclosemovingtrajectorypatternisproposed.Moreover,basedonclassicalclosedsequentialpatternminingalgorithm,afrequentclosepatternapproach,namelyCloseTrajalgorithm,isdevisedundertheconditionofmovingtrajectorydata.Basedonthesimulationandrealdataset,thecorrespondingresultsshowthatourproposedCloseTrajalgorithmhasstrongadaptabilitytotheaforementionedproblemwithsignificantadvantagesintermsofoperationalefficiency.

mobiletrajectory；datamining；frequentclosedpattern

10.13800/j.cnki.xakjdxxb.2016.0419

1672-9315(2016)04-0573-04

2016-04-20責(zé)任編輯：劉潔

國家自然科學(xué)基金(61402360)

王亮(1984-),男,陜西寶雞人，博士,E-mail:liangwang0123@gmail.com

TP 311

A