基于空間鄰近搜索的移動軌跡相對時間模式挖掘方法

張海濤，周 歡，張國楠

(1.南京郵電大學 地理與生物信息學院，南京 210023； 2.南京郵電大學 通信與信息工程學院，南京 210003；3.南京郵電大學 計算機學院、軟件學院、網(wǎng)絡空間安全學院，南京 210023)(*通信作者電子郵箱zhouhuan8899@qq.com)

0 引言

隨著定位技術與移動通信技術的快速發(fā)展，基于位置服務(Location Based Service, LBS)的應用產(chǎn)生了大量具有時空特性的移動軌跡數(shù)據(jù)。挖掘移動軌跡數(shù)據(jù)從中發(fā)現(xiàn)隱含、有用的移動軌跡序列模式[1-2]，對于分析、預測人類或動物的相關行為習慣具有重要的參考價值。在生態(tài)學中，分析動物的運動路線，可以幫助我們更好地理解它們的行為習慣，當一些動物的運動模式突然改變時，有可能預示即將發(fā)生某些地質災難(例如，地震、海嘯等)[3]。在城市智能交通系統(tǒng)中，從大量車輛、行人的運動軌跡數(shù)據(jù)中發(fā)現(xiàn)頻繁的移動軌跡序列模式，可以輔助交通規(guī)劃、交通疏導等[4]。在商業(yè)應用領域，從記錄人們?nèi)粘３鲂行袨榱晳T的運動軌跡數(shù)據(jù)中，挖掘移動軌跡序列模式并與商業(yè)管理系統(tǒng)中客戶信息關聯(lián)，可以實現(xiàn)位置場景感知的商品推薦、目標客戶定向廣告投送等[5]。

傳統(tǒng)的序列模式數(shù)據(jù)挖掘方法包括：Apriori All[6-8]、頻繁模式樹(Frequent Pattern tree, FP-tree)[9]、PrefixSpan[10]、SPADE(Sequential PAttern Discovery using Equivalence classes)[11]等，由于在項集和序列模式的挖掘中沒有考慮到移動軌跡數(shù)據(jù)的時空特性，不能直接應用于移動軌跡序列模式的挖掘。目前，出現(xiàn)了一些改進傳統(tǒng)序列模式挖掘方法，可以實現(xiàn)移動軌跡序列模式挖掘。典型的方法主要包括：Cao等[12]提出的一種通過查找不同對象之間相似移動軌跡，發(fā)現(xiàn)頻繁的移動軌跡序列模式的方法；Shaw等[13]提出的一種基于Apriori算法對移動軌跡數(shù)據(jù)進行頻繁模式挖掘的方法；Pasquier 等[14]提出的一種在歸屬樹森林中挖掘頻繁模式的方法；Gatuha 等[15]提出的采用局部廣度優(yōu)先搜索的并行頻繁模式挖掘算法；Khoshahval等[16]提出的使用關聯(lián)規(guī)則從軌跡數(shù)據(jù)發(fā)現(xiàn)頻繁模式的方法。

但是文獻[12-16]存在共性問題：移動軌跡序列模式挖掘方法的執(zhí)行效率太低。分析主要原因為：沒有考慮到在實際應用中產(chǎn)生的移動軌跡數(shù)據(jù)具有時空鄰近特性，直接使用所有頻繁項集進行排列組合來生成候選移動軌跡序列模式，會造成候選的移動軌跡序列模式的數(shù)量急劇增多，大幅增加方法執(zhí)行的系統(tǒng)資源開銷。為此，本文提出一種基于空間鄰近搜索的移動軌跡相對時間模式挖掘方法。

1 基本概念

1.1 移動軌跡

記錄用戶的連續(xù)運動的位置的有序列表，定義為TID=((p1,t1),(p2,t2),…,(pn,tn))(t1

1.2 時空格空間

對于一個包含移動軌跡數(shù)據(jù)集的離散時空域，其中R2表示2維幾何空間,pi表示移動軌跡點的空間位置,T表示1維時間,ti表示具體的時間點，其對應的時空格(Space-Time Cell，STC)空間為：

STC=(DR2,DT);

其中：DR2是基于時空格的2維幾何空間，DT是基于時空格的時間域，每個(Cell(col,row),periodk)稱為一個時空格，Cell(col,row)表示時空格的幾何空間跨度也稱空間格，col、row表示時空格在幾何空間平面劃分中所處的列號、行號，periodk(s,t)表示時空格的時間跨度也稱時間段，j是編號，s、t表示時間域劃分中起、止時間，period_count、col_count、row_count分別是根據(jù)用戶指定的時空分辨率而設定的時段劃分數(shù)、幾何空間劃分的列數(shù)、行數(shù)。

2 移動軌跡序列模式挖掘方法

本章定義相關概念，然后設計模式挖掘方法，最后通過實例分析分析方法實現(xiàn)流程。

2.1 基本定義

定義1 時空格序列(Sequence of Space-Time Cells, SeSTC)：對于一條移動軌跡TID=((p1,t1),(p2,t2),…,(pn,tn))(t1

TID直接匹配到STC時空格序列定義為：

其中ID表示時空格序列的編號。

依據(jù)移動軌跡數(shù)據(jù)的特性,以及后續(xù)數(shù)據(jù)分析的需要，本文對時空格序列進行如下條件限定：

2.2 方法設計

本文提出的基于空間鄰近搜索的移動軌跡相對時間模式挖掘方法包含3個步驟：處理移動軌跡數(shù)據(jù)、獲取長度為2的頻繁相對時間模式、對長度為2的頻繁相對時間模式進行模式增長，獲取長度為3,4,…的頻繁相對時間模式，對應的實現(xiàn)算法分別是DataPre()、BasicRelTimePattern()、Pattern-growth()。算法1～3給出了對應的偽代碼。

算法1 DataPre()。

輸入 移動軌跡數(shù)據(jù)rawdata；

輸出 時空格序列集合SeSTCs，頻繁空間網(wǎng)格集合FSCells。

1)rawSeSTCs= ToRawSeSTCs(rawdata);

2)SeSTCs=splitSeSTCs(rawSeSTCs);

3)FSCells=getFrequentCells(SeSTCs);

算法1代碼第1)行，讀取移動軌跡數(shù)據(jù)進行時空離散化得到初始時空格序列; 代碼第2)行根據(jù)空間鄰近規(guī)則、用戶設置的時段鄰近閾值，對初始時空格序列進行拆分得到新的時空格序列; 代碼第3)行遍歷時空格序列得到所有頻繁空間網(wǎng)格的集合。

算法2 BasicRelTimePattern()。

輸入 時空格序列集合SeSTCs，頻繁空間網(wǎng)格集合FSCells；

輸出 鄰接表集合adjLists，長度為2的頻繁相對時間模式IvP2。

1)

forFSCellinFSCells

2)

listCell=formAdjList(FSCell);

3)

adjLists.add(FSCell,listCell);

4)

IvP1=FSCell.cellToIvP();

5)

candiIvPs2.add(IvP1.getNextLengthIvps(adjLists));

6)

end for

7)

forcandiIvP2incandiIvPs2

8)

If (support(SeSTCs,candiIvP2))

9)

IvPs2.add(candiIvp2);

10)

end for

算法2代碼第1)～6)行，遍歷頻繁空間網(wǎng)格, 為每個頻繁空間網(wǎng)格構建鄰接表，并添加到鄰接表集合中; 將每個頻繁空間網(wǎng)格轉變成長度為1的頻繁相對時間模式；通過getNextLengthIvPs()方法得到對應的長度為2的候選相對時間模式。代碼第7)～10)行，遍歷候選相對時間模式，計算在時空格序列集合SeSTCs中的模式支持度，滿足支持度閾值的候選相對時間模式添加到長度為2的頻繁相對時間模式集合中。

算法3 Pattern-growth()。

輸入 長度為n的頻繁相對時間模式集合IvPsn，鄰接表集合adjLists；

輸出 長度為n+1的頻繁相對時間模式IvPsn+1。

1)

forIvPninIvPsn

2)candiIvPsn+1.add(IvP.getNextLengthIvP(adjLists));

3) end for

4)

forcandiIvPn+1incandiIvPsn+1

5)

If(support(SeSTCs,candiIvPn+1))

6)

IvPsn+1.add(candiIvP);

7)

end for

算法3代碼第1)～3)行，遍歷長度為n的頻繁相對時間模式，通過getNextLengthIvP()方法獲取對應的長度為n+1的候選相對時間模式。代碼第4)～7)行，遍歷長度為n+1的候選相對時間模式，計算在時空格序列集合SeSTCs中的模式支持度，滿足支持度閾值的候選相對時間模式添加到長度為n+1的頻繁相對時間模式集合中。

2.3 算法復雜度分析

本文方法包含3個步驟，但本文方法與傳統(tǒng)方法的本質區(qū)別在于模式增長的方式上。本文方法采用空間鄰近搜索的方式進行模式增長，而傳統(tǒng)方法采用全排列組合的方式進行模式增長, 因此，只分析模式增長算法的時間、空間復雜度。同時，為了簡化計算的復雜度分析的對比過程，不考慮模式支持度計算對于算法執(zhí)行過程的影響，即假定所有的增長模式都滿足支持度閾值的限定條件。首先分析兩端點情況，然后得到一般情況的復雜度分析對比，結果如下：

1)假定存在n個頻繁空間網(wǎng)格，且n個頻繁空間網(wǎng)格全部相鄰。本文方法與傳統(tǒng)方法進行單次模式增長的時間復雜度T(n)都為O(n)，空間復雜度S(n)都為O(n), 即在最差的情況下，所有的頻繁空間網(wǎng)格全部相鄰，本文方法與傳統(tǒng)方法的時間復雜度、空間復雜度相同。

2)假定存在n個頻繁空間網(wǎng)格，且n個頻繁空間網(wǎng)格全部不相鄰。本文方法與傳統(tǒng)方法進行單次模式增長的時間復雜度T(n)分別為O(1)、O(n)，空間復雜度S(n)分別為O(1)、O(n), 即在最優(yōu)的情況下，所有頻繁空間網(wǎng)格全部不相鄰，本文方法的時間復雜度、空間復雜度為常數(shù)O(1)，遠小于傳統(tǒng)方法的復雜度O(n)。

3)假定存在n個頻繁空間網(wǎng)格，其中m(1≤m≤n)個頻繁空間網(wǎng)格相鄰。本文方法與傳統(tǒng)方法進行單次模式增長的時間復雜度T(n)分別為O(m)、O(n)，空間復雜度S(n)分別為O(m)、O(n)。

2.4 實例分析

下面結合一個示例，介紹方法執(zhí)行的基本過程。表1是一個移動軌跡數(shù)據(jù)庫，包含8條移動軌跡。設定頻繁空間網(wǎng)格、頻繁相對時間模式的最小支持度閾值都為35%，時段鄰近閾值為3。

表1 移動軌跡數(shù)據(jù)庫

1)對軌跡數(shù)據(jù)進行時空離散化得到時空格序列，結果如表2所示。

表2 時空格序列

2)剔除時空格序列中重復時空格，并根據(jù)空間格鄰近以及用戶指定的時段鄰近閾值，對時空格序列進行拆分，形成新的時空格序列，結果如表3所示。

表3 新的時空格序列

3)對比表3中的數(shù)據(jù)與設定的空間網(wǎng)格最小支持度閾值得到頻繁空間網(wǎng)格，結果如表4所示。

表4 頻繁空間網(wǎng)格

4)根據(jù)空間鄰近規(guī)則組合表4的頻繁空間網(wǎng)格。因為設置的時段鄰近閾值為3，時間間隔可能為1、2、3，從而得到長度為2的候選相對時間模式。計算候選相對時間模式的支持度，剔除無效的候選相對時間模式，得到長度為2的頻繁相對時間模式，結果如表5所示。

表5 長度為2的頻繁相對時間模式的支持度和時間間隔

5)表5中的頻繁相對時間模式，對照表4，尋找與頻繁相對時間模式最后一個空間網(wǎng)格鄰近且沒有在該頻繁相對時間模式中出現(xiàn)過的空間網(wǎng)格添加到該頻繁相對時間模式的末尾，并且時間間隔可能為1、2、3，得到長度為3的候選相對時間模式。計算候選相對時間模式支持度，剔除無效的候選相對時間模式，得到長度為3的頻繁相對時間模式，結果如表6所示。

表6 長度為3的頻繁相對時間模式的支持度和時間間隔

6)表6中的頻繁相對時間模式，對照表4，尋找與頻繁相對時間模式最后一個空間網(wǎng)格鄰近且沒有在該頻繁相對時間模式中出現(xiàn)過的空間網(wǎng)格添加到頻繁相對時間模式的末尾，并且時間間隔可能為1、2、3，得到長度為4的候選相對時間模式。計算候選相對時間模式支持度，沒有任何一個候選相對時間模式支持度達到閾值。

3 實驗結果與分析

本文采用2 612輛出租車上的全球定位系統(tǒng)(Global Positioning System, GPS)軌跡數(shù)據(jù)作為基礎數(shù)據(jù)，經(jīng)過時空離散化、圖幅網(wǎng)格化，模擬生成時空格序列數(shù)據(jù)為實驗數(shù)據(jù)[17]。通過在引言部分對傳統(tǒng)方法[12-16]的分析，本文方法與傳統(tǒng)方法的本質區(qū)別在于模式增長時采用了空間鄰近搜索的策略。

為突出本文提出的基于空間鄰近搜索的相對時間模式挖掘方法性能優(yōu)勢，與傳統(tǒng)的方法進行實驗對比。性能的對比主要采用兩個度量指標：運行時間和占用最大內(nèi)存。為保證算法性能對比的高效性與有效性，采用本文方法的整體框架，設計了一種只改變其中獲取候選相對時間模式的方式，即對頻繁空間網(wǎng)格進行排列組合的方式的對比方法。該對比方法一方面代表了傳統(tǒng)的典型方法[12-16]，另一方面由于采用與本文方法除去模式增長本質不同外的設計框架，可以保證性能對比的公平性。在后續(xù)的實驗對比部分中，簡稱本文方法為空間鄰近方法，實驗對比方法為非空間鄰近方法。兩種方法執(zhí)行模式挖掘時設定的頻繁空間網(wǎng)格支持度閾值、頻繁相對時間模式支持度閾值均分別為3%、0.03%，時段鄰近閾值均為3。頻繁空間網(wǎng)格支持度閾值、頻繁相對時間模式支持度閾值、時段鄰近閾值用戶可以自行設定，頻繁空間網(wǎng)格支持度閾值越大，頻繁相對時間模式支持度閾值越大，運行時間越短、占用最大內(nèi)存越小；時段鄰近閾值越大，運行時間越長、占用最大內(nèi)存越大。本文設定頻繁空間網(wǎng)格支持度閾值、頻繁相對時間模式支持度閾值分別為3%、0.03%，時段鄰近閾值為3，程序運行時間、占用最大內(nèi)存可以滿足對比實驗的需要。

3.1 穩(wěn)定性對比

實驗模擬生成了10個批次的時空格序列數(shù)據(jù)，基本信息如表7所示。其中，10個批次的數(shù)據(jù)包含的時空格序列數(shù)量基本接近，以對比測試方法性能的穩(wěn)定性。

表7 10批次時空格序列數(shù)據(jù)

實驗結果如圖1、2所示。圖1是對比兩種方法在運算各個批次數(shù)據(jù)時所需要的運行時間, 從批次1到批次10，空間鄰近方法的運行時間一直小于非空間鄰近方法的運行時間。根據(jù)圖1數(shù)據(jù)計算，空間鄰近方法、非空間鄰近方法運行時間的標準差σ分別為689、3 020，表明在運行時間方面，空間鄰近方法有更好的穩(wěn)定性。圖2是對比兩種方法在運算各個批次數(shù)據(jù)時占用最大內(nèi)存。可以看出：運算批次3、5、6的實驗數(shù)據(jù)時，空間鄰近方法和非空間鄰近方法在占用最大內(nèi)存性能方面基本相近。對于其他批次數(shù)據(jù)，空間鄰近方法均小于非空間鄰近方法。根據(jù)圖2數(shù)據(jù)計算，空間鄰近方法、非空間鄰近方法占用最大內(nèi)存的標準差σ分別為28、18，表明在占用最大內(nèi)存方面，兩種方法的穩(wěn)定性差距不大。

圖1 10批次數(shù)據(jù)運行時間對比

圖2 10批次數(shù)據(jù)運行占用最大內(nèi)存對比

實驗結果表明空間鄰近方法運行時間更短，占用最大內(nèi)存更小，在運行時間方面比非空間鄰近方法具有更好的穩(wěn)定性，在占用最大內(nèi)存方面兩者的穩(wěn)定性差距不大。

3.2 可擴展性對比

為進一步檢驗方法的可擴展性，本文將表7中的10個批次數(shù)據(jù)進行增量合并，生成時空格序列數(shù)據(jù)近似倍增的實驗數(shù)據(jù)，如表8所示。

表8 增量10批次的時空格序列數(shù)據(jù)

實驗結果如圖3、4所示。圖3是對比兩種方法在運算每個批次數(shù)據(jù)時所需要的運行時間, 可以看出：除批次2數(shù)據(jù)兩種方法的運行時間相同外，空間鄰近方法所需要的運行時間均小于非空間鄰近方法，而且隨著數(shù)據(jù)量的增大，運行時間的差距越來越大。

圖3 增量10批次數(shù)據(jù)運行時間對比

圖4是對比兩種方法在運算各個批次數(shù)據(jù)時占用最大內(nèi)存, 可以看出：在運行批次2、4、7、8、9、10的數(shù)據(jù)時，兩種方法占用最大內(nèi)存相近。而在運行批次1、3、5、6的數(shù)據(jù)時，空間鄰近方法占用最大內(nèi)存均小于非空間鄰近方法。

圖4 增量10批次數(shù)據(jù)運行占用最大內(nèi)存對比

實驗結果表明，隨著數(shù)據(jù)量的增大，空間鄰近方法所需要的運行時間一直較小，且和非空間鄰近方法的差距會越來越大，說明針對增量數(shù)據(jù)，空間鄰近方法在運行時間方面具有更好的可擴展性；空間鄰近方法占用最大內(nèi)存和非空間鄰近方法差距不大，但也基本優(yōu)于非空間鄰近方法，說明針對增量數(shù)據(jù)，空間鄰近方法在占用最大內(nèi)存方面可擴展性稍優(yōu)于非空間鄰近方法。

4 結語

傳統(tǒng)的移動軌跡序列模式挖掘方法以及一些改進方法都存在一個共性問題：沒有考慮到在實際應用中產(chǎn)生的移動軌跡數(shù)據(jù)具有時空鄰近特性，直接使用所有頻繁項集進行排列組合，生成候選相對時間模式，這會造成候選相對時間模式的數(shù)量急劇增加, 因此運行效率低，占用資源多。為此，本文提出一種基于空間鄰近搜索的相對時間模式挖掘方法。實驗結果表明，本文方法具有運行時間短、占用最大內(nèi)存小的優(yōu)點，且方法在運行時間方面具有更好的穩(wěn)定性和可擴展性，在占用最大內(nèi)存方面兩者的穩(wěn)定性與可擴展性基本相近。