張海濤，周 歡，張國(guó)楠

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

0 引言

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

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

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

1 基本概念

1.1 移動(dòng)軌跡

記錄用戶的連續(xù)運(yùn)動(dòng)的位置的有序列表，定義為T(mén)ID=((p1,t1),(p2,t2),…,(pn,tn))(t1

1.2 時(shí)空格空間

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

STC=(DR2,DT);

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

2 移動(dòng)軌跡序列模式挖掘方法

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

2.1 基本定義

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

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

其中ID表示時(shí)空格序列的編號(hào)。

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

2.2 方法設(shè)計(jì)

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

算法1 DataPre()。

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

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

1)rawSeSTCs= ToRawSeSTCs(rawdata);

2)SeSTCs=splitSeSTCs(rawSeSTCs);

3)FSCells=getFrequentCells(SeSTCs);

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

算法2 BasicRelTimePattern()。

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

輸出 鄰接表集合adjLists，長(zhǎng)度為2的頻繁相對(duì)時(shí)間模式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)格, 為每個(gè)頻繁空間網(wǎng)格構(gòu)建鄰接表，并添加到鄰接表集合中; 將每個(gè)頻繁空間網(wǎng)格轉(zhuǎn)變成長(zhǎng)度為1的頻繁相對(duì)時(shí)間模式；通過(guò)getNextLengthIvPs()方法得到對(duì)應(yīng)的長(zhǎng)度為2的候選相對(duì)時(shí)間模式。代碼第7)～10)行，遍歷候選相對(duì)時(shí)間模式，計(jì)算在時(shí)空格序列集合SeSTCs中的模式支持度，滿足支持度閾值的候選相對(duì)時(shí)間模式添加到長(zhǎng)度為2的頻繁相對(duì)時(shí)間模式集合中。

算法3 Pattern-growth()。

輸入 長(zhǎng)度為n的頻繁相對(duì)時(shí)間模式集合IvPsn，鄰接表集合adjLists；

輸出 長(zhǎng)度為n+1的頻繁相對(duì)時(shí)間模式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)行，遍歷長(zhǎng)度為n的頻繁相對(duì)時(shí)間模式，通過(guò)getNextLengthIvP()方法獲取對(duì)應(yīng)的長(zhǎng)度為n+1的候選相對(duì)時(shí)間模式。代碼第4)～7)行，遍歷長(zhǎng)度為n+1的候選相對(duì)時(shí)間模式，計(jì)算在時(shí)空格序列集合SeSTCs中的模式支持度，滿足支持度閾值的候選相對(duì)時(shí)間模式添加到長(zhǎng)度為n+1的頻繁相對(duì)時(shí)間模式集合中。

2.3 算法復(fù)雜度分析

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

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

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

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

2.4 實(shí)例分析

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

表1 移動(dòng)軌跡數(shù)據(jù)庫(kù)

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

表2 時(shí)空格序列

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

表3 新的時(shí)空格序列

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

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

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

表5 長(zhǎng)度為2的頻繁相對(duì)時(shí)間模式的支持度和時(shí)間間隔

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

表6 長(zhǎng)度為3的頻繁相對(duì)時(shí)間模式的支持度和時(shí)間間隔

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

3.1 穩(wěn)定性對(duì)比

實(shí)驗(yàn)?zāi)M生成了10個(gè)批次的時(shí)空格序列數(shù)據(jù)，基本信息如表7所示。其中，10個(gè)批次的數(shù)據(jù)包含的時(shí)空格序列數(shù)量基本接近，以對(duì)比測(cè)試方法性能的穩(wěn)定性。

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

實(shí)驗(yàn)結(jié)果如圖1、2所示。圖1是對(duì)比兩種方法在運(yùn)算各個(gè)批次數(shù)據(jù)時(shí)所需要的運(yùn)行時(shí)間, 從批次1到批次10，空間鄰近方法的運(yùn)行時(shí)間一直小于非空間鄰近方法的運(yùn)行時(shí)間。根據(jù)圖1數(shù)據(jù)計(jì)算，空間鄰近方法、非空間鄰近方法運(yùn)行時(shí)間的標(biāo)準(zhǔn)差σ分別為689、3 020，表明在運(yùn)行時(shí)間方面，空間鄰近方法有更好的穩(wěn)定性。圖2是對(duì)比兩種方法在運(yùn)算各個(gè)批次數(shù)據(jù)時(shí)占用最大內(nèi)存?？梢钥闯觯哼\(yùn)算批次3、5、6的實(shí)驗(yàn)數(shù)據(jù)時(shí)，空間鄰近方法和非空間鄰近方法在占用最大內(nèi)存性能方面基本相近。對(duì)于其他批次數(shù)據(jù)，空間鄰近方法均小于非空間鄰近方法。根據(jù)圖2數(shù)據(jù)計(jì)算，空間鄰近方法、非空間鄰近方法占用最大內(nèi)存的標(biāo)準(zhǔn)差σ分別為28、18，表明在占用最大內(nèi)存方面，兩種方法的穩(wěn)定性差距不大。

圖1 10批次數(shù)據(jù)運(yùn)行時(shí)間對(duì)比

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

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

3.2 可擴(kuò)展性對(duì)比

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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