移動(dòng)目標(biāo)同現(xiàn)模式挖掘算法的研究?

周 濛 朱保平

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

從移動(dòng)目標(biāo)的時(shí)空軌跡數(shù)據(jù)中挖掘目標(biāo)的關(guān)聯(lián)關(guān)系是時(shí)空數(shù)據(jù)挖掘領(lǐng)域的重要研究?jī)?nèi)容之一，也是本文研究的主要內(nèi)容。大量的時(shí)空軌跡數(shù)據(jù)蘊(yùn)含著大量移動(dòng)目標(biāo)的行為規(guī)律。通常情況下，移動(dòng)目標(biāo)在某段時(shí)間范圍內(nèi)具備一定的規(guī)律，因此從時(shí)空軌跡數(shù)據(jù)集中挖掘目標(biāo)的關(guān)聯(lián)關(guān)系具有極高的研究?jī)r(jià)值。時(shí)空同現(xiàn)模式研究是時(shí)空數(shù)據(jù)挖掘研究的熱點(diǎn)之一。為了挖掘時(shí)空同現(xiàn)相關(guān)的模式，M.Celik 等提出混合群時(shí)空同現(xiàn)模式的概念并定義了時(shí)空興趣度［1］，并給出基于混合群的時(shí)空同現(xiàn)模式的挖掘方法及相關(guān)改進(jìn)算法［2～3］。

近些年來(lái)學(xué)術(shù)界在時(shí)空數(shù)據(jù)建模方面也取得了較大研究進(jìn)展。George等在空間網(wǎng)絡(luò)的基礎(chǔ)上，通過(guò)將時(shí)間序列作為圖中節(jié)點(diǎn)與邊的屬性，提出了一種比Kohler 等提出的利用時(shí)間拓展圖構(gòu)建一個(gè)隨時(shí)間動(dòng)態(tài)變化的空間網(wǎng)絡(luò)［4］更為有效的時(shí)間匯總圖建模方式［5］，解決重復(fù)建模問(wèn)題［6～7］。Y. Wan等定義了一種基于k-鄰近對(duì)象的空間同位模式［8～9］，探討了基于k-鄰近空間關(guān)系的同位模式及基于距離閾值的空間同位模式的區(qū)別和聯(lián)系，解決了基于距離閾值的空間同位模式算法中難以解決的對(duì)稀少空間特征對(duì)象的同位模式的發(fā)現(xiàn)，為基于k-鄰近對(duì)象的空間同位模式應(yīng)用于時(shí)空數(shù)據(jù)挖掘提供參考。龔健雅在空間數(shù)據(jù)庫(kù)中研究了分布式數(shù)據(jù)模型［10］，但是該模型不能夠直接應(yīng)用于時(shí)空數(shù)據(jù)庫(kù)中。本文針對(duì)現(xiàn)有時(shí)空數(shù)據(jù)建模及挖掘算法的計(jì)算瓶頸，給出粗細(xì)粒度結(jié)合的時(shí)空模型CFCMDCOP Graph，粗粒度層的構(gòu)建基于移動(dòng)目標(biāo)軌跡信息匹配及FT 過(guò)濾器篩選，代替了直接遍歷軌跡點(diǎn)集，通過(guò)減少計(jì)算對(duì)象來(lái)降低建模耗時(shí)；并提出基于連接的挖掘算法CFCMDCOP Graph Miner，挖掘中通過(guò)對(duì)粗粒度層移動(dòng)目標(biāo)間的引發(fā)序列計(jì)算，提前對(duì)不滿足引發(fā)閾值的移動(dòng)目標(biāo)組合進(jìn)行剪枝，細(xì)粒度層能夠快速挖掘多條軌跡之間的時(shí)間交集，并計(jì)算多軌跡間的時(shí)空鄰近頻繁度，減少挖掘過(guò)程中的冗余計(jì)算來(lái)提高算法挖掘效率。

2 關(guān)聯(lián)性挖掘主要公式及定義

本文提出了粗細(xì)粒度結(jié)合的混合時(shí)空模型（Coarse-fine-grained Combination Mixed-Drove Co-occurrence Pattern Graph，CFCMDCOP Graph）。粗粒度層存儲(chǔ)元素之間的時(shí)空引發(fā)關(guān)系，細(xì)粒度層存儲(chǔ)元素對(duì)應(yīng)的實(shí)例集間的時(shí)空鄰近狀態(tài)，通過(guò)訪問(wèn)CFCMDCOP Graph，能夠高效獲取挖掘時(shí)空引發(fā)同現(xiàn)模式過(guò)程中需要的信息，避免冗余計(jì)算，提高了計(jì)算效率。下面來(lái)介紹本文的CFCMDCOP Graph存儲(chǔ)模型。

定義1：粗粒度的引發(fā)關(guān)系網(wǎng)絡(luò)（Coarse-grained Initiation Relation Graph，CIRG）：描述時(shí)空引發(fā)同現(xiàn)模式中各元素對(duì)應(yīng)實(shí)例的出現(xiàn)情況及其引發(fā)關(guān)系。

N表示元素集，E表示有向邊集，兩個(gè)元素節(jié)點(diǎn)之間的邊是雙向的。fi為元素對(duì)的候選2 時(shí)空引發(fā)同現(xiàn)模式，edegi為fi對(duì)應(yīng)的引發(fā)序列，F(xiàn)T 為過(guò)濾規(guī)則，根據(jù)實(shí)際數(shù)據(jù)特性建立相應(yīng)的規(guī)則。

定義2：細(xì)粒度的時(shí)空聚合網(wǎng)絡(luò)（Fine-grained Spatiotemporal Aggregation Graph，F(xiàn)SAG）：描述實(shí)例對(duì)在有效時(shí)間槽下的時(shí)空鄰近狀態(tài)。

N 表示實(shí)例集，E 表示無(wú)向邊集，CR 為候選引發(fā)關(guān)系集，TF為時(shí)間框架，ci為鄰近實(shí)例對(duì)的集合，ei為鄰近實(shí)例對(duì)對(duì)應(yīng)的時(shí)空鄰近序列，edgei表示ci與ei的對(duì)應(yīng)關(guān)系。

定義3：CFCMDCOP Graph：描述時(shí)空引發(fā)同現(xiàn)模式中各元素對(duì)應(yīng)實(shí)例的出現(xiàn)情況及其引發(fā)關(guān)系、元素與實(shí)例的映射關(guān)系及實(shí)例對(duì)在有效時(shí)間槽下的時(shí)空鄰近狀態(tài)。

圖1 CFCMDCOP Graph

TF 表示時(shí)間框架，Nelement表示元素集，Nintance表示實(shí)例集，E 表示邊集，li表示類型與實(shí)例之間的連接，pk表示類型對(duì)與實(shí)例對(duì)集之間的連線，一個(gè)類型對(duì)對(duì)應(yīng)多個(gè)實(shí)例對(duì)集。

以上是對(duì)CFCMDCOP Graph 時(shí)空存儲(chǔ)模型的描述。CFCMDCOP Graph 時(shí)空存儲(chǔ)模型的細(xì)粒度時(shí)空聚合網(wǎng)絡(luò)是基于時(shí)間匯總圖的，并且在細(xì)粒度層的基礎(chǔ)上擴(kuò)展出了一層粗粒度層，用于模式挖掘時(shí)提前對(duì)非時(shí)空引發(fā)同現(xiàn)模式進(jìn)行剪枝。

定義4：時(shí)空引發(fā)同現(xiàn)模式。借鑒災(zāi)害關(guān)聯(lián)之間存在的關(guān)聯(lián)關(guān)系［11］、同現(xiàn)模式及時(shí)空興趣度定義［1，12～13］，基于移動(dòng)目標(biāo)的時(shí)空數(shù)據(jù)，認(rèn)為不同移動(dòng)目標(biāo)之間出現(xiàn)時(shí)間較早的移動(dòng)目標(biāo)有引發(fā)與其距離較近且出現(xiàn)時(shí)間較晚的移動(dòng)目標(biāo)的可能性［14］，由此定義元素之間的時(shí)空引發(fā)同現(xiàn)模式，給定：1）CFCMDCOP Graph 混合模型；2）時(shí)空引發(fā)閾值θI；3）過(guò)濾規(guī)則FT；4）鄰近距離R；5）引發(fā)時(shí)長(zhǎng)YFSC；6）空間頻繁閾值θPr；7）時(shí)空鄰近頻繁閾值θSPF。最終挖掘出滿足上述條件的移動(dòng)目標(biāo)組合，k 元時(shí)空引發(fā)同現(xiàn)模式的形式為P={C1→C2…→Ck}，該模式存在方向性。

實(shí)例名稱在時(shí)間框架下獲取到的相應(yīng)實(shí)例集描述一條軌跡。給出移動(dòng)目標(biāo)及其軌跡的相關(guān)定義。

定義5：移動(dòng)目標(biāo)軌跡定義：Tr=(mc，st，et，areas，D)，mc表示具體的移動(dòng)目標(biāo)軌跡名稱，st、et表示移動(dòng)目標(biāo)軌跡的首尾點(diǎn)對(duì)應(yīng)的時(shí)間，即出現(xiàn)與消失時(shí)間，areas 表示軌跡的經(jīng)過(guò)區(qū)域，D 表示組成軌跡的軌跡點(diǎn)集合，D={m t1，mt2，mt3，…，mtn} ，n ∈N+，n 為軌跡點(diǎn)的數(shù)量。

定義6：軌跡點(diǎn)mt=( )x，y，t ，其中x，y 表示移動(dòng)目標(biāo)所在的經(jīng)緯度坐標(biāo)，t 表示軌跡點(diǎn)對(duì)應(yīng)的時(shí)間戳。

定義7：時(shí)空鄰近狀態(tài)。元素的實(shí)例映射到時(shí)間框架下，可以描述出一條完整軌跡。時(shí)空鄰近狀態(tài)用于表征軌跡組合之間在交集時(shí)長(zhǎng)內(nèi)處于空間鄰近狀態(tài)的頻繁程度。描述如下：1）時(shí)空鄰近序列seq；2）時(shí)空鄰近頻繁閾值θSPF；3）包含n 個(gè)時(shí)間槽的時(shí)間框架TF。seq 由若干0、1、2 組成一組序列值，序列值中的2 表示該時(shí)間槽對(duì)軌跡組合而言是無(wú)效時(shí)間槽；序列值中1 表示單個(gè)時(shí)間槽下軌跡組合處于空間鄰近狀態(tài)，0 表示不處于空間鄰近狀態(tài)。序列中1的數(shù)量與n的比值為時(shí)空鄰近頻繁度SPF，如果大于θSPF，則稱軌跡組合處于時(shí)空鄰近狀態(tài)。

定義8：時(shí)空引發(fā)率，描述時(shí)空引發(fā)同現(xiàn)模式的引發(fā)程度。計(jì)算模式p 的時(shí)空引發(fā)率的公式如下：

如果時(shí)空引發(fā)同現(xiàn)模式p 的引發(fā)率大于引發(fā)閾值，那么模式p為時(shí)空引發(fā)同現(xiàn)模式。

2.1 移動(dòng)目標(biāo)關(guān)聯(lián)性挖掘建模

粗粒度的引發(fā)關(guān)系網(wǎng)絡(luò)層構(gòu)建基于移動(dòng)目標(biāo)軌跡的匹配，由于構(gòu)建出的移動(dòng)目標(biāo)軌跡數(shù)量遠(yuǎn)遠(yuǎn)少于軌跡點(diǎn)集的數(shù)量，由此降低了計(jì)算的數(shù)量級(jí)，減少了計(jì)算耗時(shí)；通過(guò)FT 過(guò)濾規(guī)則，得到候選2 元時(shí)空引發(fā)同現(xiàn)模式。同時(shí)，細(xì)粒度的時(shí)空聚合網(wǎng)絡(luò)層基于時(shí)間匯總圖的建模方式，避免了為每個(gè)時(shí)間槽的空間關(guān)系重復(fù)建模的問(wèn)題，并且本文基于有效時(shí)間段進(jìn)行算法建模，進(jìn)一步減少了關(guān)聯(lián)性模式算法建模的時(shí)間與空間消耗。

粗粒度的移動(dòng)目標(biāo)引發(fā)關(guān)系網(wǎng)絡(luò)的構(gòu)建流程如下。

1）初始化提取軌跡點(diǎn)的特征信息，構(gòu)建所有移動(dòng)目標(biāo)軌跡；

2）按日期劃分移動(dòng)目標(biāo)的軌跡信息，并按出現(xiàn)時(shí)間進(jìn)行升序排序，對(duì)相同日期的軌跡集進(jìn)行兩兩不重復(fù)的匹配操作；

3）基于FT 的過(guò)濾規(guī)則篩選出候選2 元時(shí)空引發(fā)同現(xiàn)模式，通過(guò)有向邊對(duì)節(jié)點(diǎn)之間進(jìn)行連接，并記錄候選2元時(shí)空引發(fā)同現(xiàn)模式p，及其軌跡組合。

4）迭代步驟3），直到所有軌跡匹配完成，由此構(gòu)建出粗粒度的引發(fā)關(guān)系網(wǎng)絡(luò)。

5）將記錄下的候選2 元時(shí)空引發(fā)同現(xiàn)模式輸入細(xì)粒度的時(shí)空聚合網(wǎng)絡(luò)層，根據(jù)已知的軌跡標(biāo)識(shí)映射到軌跡點(diǎn)集，建立時(shí)空聚合網(wǎng)絡(luò)，給粗粒度層返回結(jié)果。同時(shí)，更新移動(dòng)目標(biāo)對(duì)的引發(fā)序列。

其中，細(xì)粒度的移動(dòng)目標(biāo)時(shí)空聚合網(wǎng)絡(luò)的構(gòu)建步驟如下。

1）如果粗粒度層不再獲取新的軌跡組，則完成時(shí)空聚合網(wǎng)絡(luò)構(gòu)建，結(jié)束；否則獲取軌跡組

2）對(duì)其中任意一對(duì)未訪問(wèn)過(guò)的軌跡對(duì)Ai，Bj進(jìn)行匹配。

3）新建軌跡的節(jié)點(diǎn)，根據(jù)引發(fā)關(guān)系網(wǎng)絡(luò)中節(jié)點(diǎn)的軌跡出現(xiàn)時(shí)間、消失時(shí)間信息，計(jì)算時(shí)間交集，根據(jù)時(shí)間交集進(jìn)行軌跡點(diǎn)抽樣，每條軌跡抽取其軌跡點(diǎn)集的c個(gè)軌跡點(diǎn)，得到軌跡點(diǎn)集合DAi、DBj。

4）對(duì)軌跡點(diǎn)集合DAi、DBj之間進(jìn)行歐式距離計(jì)算，添加軌跡的節(jié)點(diǎn)之間的連線，如果滿足鄰近距離R，那么時(shí)空鄰近序列添加1，否則序列添加0，直到遍歷完DAi、DBj的所有抽樣軌跡點(diǎn)，計(jì)算時(shí)空鄰近頻繁度SPF，如果滿足時(shí)空鄰近頻繁閾值θSPF，那么給粗粒度層返回1，否則返回0。

5）判斷是否遍歷完軌跡組{ }Ai，Bj，…，Ck中的所有軌跡對(duì)，如果沒(méi)有則返回2），否則返回1）。

2.2 移動(dòng)目標(biāo)關(guān)聯(lián)性挖掘算法

移動(dòng)目標(biāo)關(guān)聯(lián)性挖掘，其粗粒度的引發(fā)關(guān)系網(wǎng)絡(luò)層存儲(chǔ)移動(dòng)目標(biāo)對(duì)的引發(fā)序列，挖掘過(guò)程中能夠快速找到候選關(guān)聯(lián)性模式，提前對(duì)不滿足引發(fā)閾值的移動(dòng)目標(biāo)組合進(jìn)行剪枝，減少了關(guān)聯(lián)性模式算法挖掘過(guò)程的時(shí)間消耗；其細(xì)粒度的時(shí)空聚合網(wǎng)絡(luò)層基于時(shí)間匯總圖的建模方式，軌跡對(duì)是基于自身出現(xiàn)的有效時(shí)間段的，能夠快速挖掘多條軌跡之間的時(shí)間交集，在時(shí)間交集下建立時(shí)間槽并計(jì)算多軌跡間的時(shí)空鄰近頻繁度，減少了挖掘過(guò)程中的冗余計(jì)算，進(jìn)一步減少了關(guān)聯(lián)性模式算法挖掘的時(shí)間與空間消耗問(wèn)題。

本節(jié)借鑒Huang Yan 等提出的基于連接的空間同位模式挖掘［15］，將該挖掘方法應(yīng)用到移動(dòng)目標(biāo)時(shí)空引發(fā)同現(xiàn)模式挖掘中。基于連接的移動(dòng)目標(biāo)關(guān)聯(lián)性模式挖掘方法如下。

1）遍歷粗粒度的引發(fā)關(guān)系層的候選2 元時(shí)空引發(fā)同現(xiàn)模式，根據(jù)引發(fā)序列計(jì)算時(shí)空引發(fā)率I( p )，當(dāng)時(shí)空引發(fā)率值滿足設(shè)定的時(shí)空引發(fā)閾值θI時(shí)，輸出2 元時(shí)空引發(fā)同現(xiàn)模式。否則直接對(duì)其剪枝，減少后續(xù)計(jì)算量。

2）利用2 元時(shí)空引發(fā)同現(xiàn)模式集對(duì)應(yīng)的軌跡組合做連接操作，如果結(jié)果不為空，則對(duì)應(yīng)的移動(dòng)目標(biāo)組合構(gòu)成候選3 元時(shí)空引發(fā)同現(xiàn)模式集，記錄軌跡組合。例如，已知2 元時(shí)空引發(fā)同現(xiàn)模式集F1、F2，模式與對(duì)應(yīng)軌跡組合為F1 →{C 1，C2} ，F(xiàn)2 →{C 1，C3} ，對(duì) F1、F2 做 連 接，生 成F3 →{C 1，C2，C3} ，并且基于FT 過(guò)濾規(guī)則進(jìn)行剪枝，如果沒(méi)有被剪枝，則模式F3 為候選3 元時(shí)空引發(fā)同現(xiàn)模式。

3）根據(jù)候選3 元時(shí)空引發(fā)同現(xiàn)模式中軌跡組合各軌跡的出現(xiàn)時(shí)間、消失時(shí)間計(jì)算交集時(shí)長(zhǎng)，在有效時(shí)間段內(nèi)進(jìn)行時(shí)空鄰近頻繁度SPF計(jì)算，若時(shí)空鄰近頻繁度SPF滿足時(shí)空鄰近頻繁閾值，n(p)加1，skyfi(p)加1，否則僅n(p)加1。

4）遍歷完該候選3 元時(shí)空引發(fā)同現(xiàn)模式的所有軌跡組合集，計(jì)算時(shí)空引發(fā)率I( )p ，如果引發(fā)率大于引發(fā)閾值，則為3 元時(shí)空引發(fā)同現(xiàn)模式。以此類推，直到k 元時(shí)空引發(fā)同現(xiàn)模式集數(shù)量小于2。則結(jié)束計(jì)算，最終生成2，3…，k 元時(shí)空引發(fā)同現(xiàn)模式。

這里需要說(shuō)明的是，基于移動(dòng)目標(biāo)之間的關(guān)聯(lián)性模式，其移動(dòng)目標(biāo)在同一時(shí)間槽下不會(huì)出現(xiàn)多個(gè)實(shí)例，在任意時(shí)間槽下，實(shí)例的空間頻繁度的值不是0 就是1，所以在挖掘時(shí)簡(jiǎn)化了空間頻繁度的計(jì)算。本文是基于帶有效時(shí)段的時(shí)間匯總圖，因此只在實(shí)例處于有效時(shí)段的時(shí)候?qū)?shí)例之間進(jìn)行計(jì)算，即空間頻繁度為1，保證其值大于空間頻繁閾值。

2.3 移動(dòng)目標(biāo)關(guān)聯(lián)性挖掘算法分析

本節(jié)分析推導(dǎo)了CFCMDCOP Graph Miner挖掘的完整性與正確性，以及分析了建模和挖掘過(guò)程的時(shí)間復(fù)雜度［16］，并在挖掘算法的時(shí)間復(fù)雜度上與傳統(tǒng)算法fastMDCOP-Miner 算法運(yùn)行的時(shí)間效率進(jìn)行對(duì)比。

2.3.1 時(shí)空引發(fā)同現(xiàn)模式的單調(diào)非遞增性

如果模式pi是模式pj的子模式，那么假設(shè)pi的時(shí)空引發(fā)率大于設(shè)定引發(fā)閾值θI，則pj的時(shí)空引發(fā)率一定不小于引發(fā)閾值θI，符合單調(diào)非遞增的性質(zhì)。

所以，挖掘過(guò)程不會(huì)存在子模式不存在，而模式存在的情況。換句話說(shuō)，如果模式存在，則其子模式一定存在。

2.3.2 時(shí)空引發(fā)同現(xiàn)模式的完整性

CFCMDCOP Graph 建模過(guò)程是先基于軌跡構(gòu)建及軌跡兩兩匹配，再進(jìn)行軌跡之間的時(shí)空聚合網(wǎng)絡(luò)構(gòu)建的，由于時(shí)空聚合網(wǎng)絡(luò)基于TAG 建模［5］，則時(shí)空聚合網(wǎng)絡(luò)建模是完整的，那么針對(duì)軌跡構(gòu)建，在不破壞原軌跡點(diǎn)集結(jié)構(gòu)的基礎(chǔ)上，不同的軌跡拆分構(gòu)建規(guī)則可能對(duì)同一條軌跡拆分出不同的子軌跡集。因此，驗(yàn)證并推導(dǎo)不同的軌跡拆分規(guī)則不會(huì)導(dǎo)致時(shí)空引發(fā)同現(xiàn)模式挖掘結(jié)果的缺失，是保證時(shí)空引發(fā)同現(xiàn)模式挖掘完整性的前提。

證明方式如下：現(xiàn)有移動(dòng)目標(biāo)的原軌跡Tr，將Tr 拆分成Tr1與Tr2，其中Tr1、Tr2與待匹配軌跡Trw的有效時(shí)間槽分別為s1、s2，滿足鄰近距離的時(shí)間槽數(shù)分別為rs1、rs2，易知原軌跡Tr 與待匹配軌跡Trw的有效時(shí)間槽、滿足鄰近距離的時(shí)間槽數(shù)分別為s1+s2、rs1+rs2。假設(shè)原軌跡Tr 與待匹配軌跡Trw滿足時(shí)空鄰近狀態(tài)，即：

即假設(shè)Tr1與Trw不滿足時(shí)空鄰近狀態(tài)。對(duì)式（3）進(jìn)行推導(dǎo)，得到

根據(jù)上述結(jié)果可以推斷，若原軌跡與待匹配軌跡之間滿足時(shí)空鄰近狀態(tài)，則子軌跡中至少存在一條軌跡與待匹配軌跡滿足時(shí)空鄰近狀態(tài)。

如果通過(guò)原始軌跡點(diǎn)集構(gòu)建出若干條軌跡信息，那么滿足時(shí)空鄰近狀態(tài)的軌跡組合的數(shù)量一定不少于構(gòu)建前的原軌跡生成的時(shí)空鄰近軌跡組合的數(shù)量。但是，由于拆分構(gòu)建的不確定性，可能會(huì)存在不同情況構(gòu)建出軌跡的出現(xiàn)時(shí)間不同，導(dǎo)致模式的方向性發(fā)生變化。

綜上所述，基于軌跡匹配的時(shí)空引發(fā)同現(xiàn)模式挖掘結(jié)果不會(huì)因軌跡構(gòu)建規(guī)則變化而缺失，適當(dāng)調(diào)整引發(fā)閾值可以保證挖掘時(shí)空引發(fā)同現(xiàn)模式的完整性。

2.3.3 建模時(shí)間復(fù)雜度分析

建模過(guò)程包括根據(jù)軌跡點(diǎn)構(gòu)建軌跡集合、構(gòu)建混合網(wǎng)絡(luò)。首先構(gòu)建軌跡集合，在已排序好的軌跡點(diǎn)集中進(jìn)行遍歷，得到軌跡點(diǎn)的經(jīng)過(guò)區(qū)域、出現(xiàn)時(shí)間與消失時(shí)間，生成軌跡，并通過(guò)外鍵對(duì)軌跡與軌跡點(diǎn)進(jìn)行關(guān)聯(lián)，這個(gè)過(guò)程的時(shí)間復(fù)雜度為O( n )，n表示軌跡點(diǎn)的總數(shù)量。

在粗粒度移動(dòng)目標(biāo)引發(fā)關(guān)系網(wǎng)絡(luò)構(gòu)建過(guò)程中，主要通過(guò)對(duì)軌跡信息之間進(jìn)行兩兩不重復(fù)的匹配操作，這個(gè)過(guò)程的時(shí)間復(fù)雜度為中N表示構(gòu)建的軌跡集合的大小。

在細(xì)粒度移動(dòng)目標(biāo)空間關(guān)系建模過(guò)程中，主要是對(duì)移動(dòng)目標(biāo)實(shí)例的交集時(shí)長(zhǎng)進(jìn)行計(jì)算，提取相應(yīng)時(shí)間段內(nèi)的軌跡點(diǎn)，然后進(jìn)行軌跡點(diǎn)抽樣提取，采樣方式采用等時(shí)間間隔采樣，假設(shè)已知抽樣點(diǎn)個(gè)數(shù)c，粗粒度層計(jì)算完成后，滿足FT 過(guò)濾規(guī)則的有效移動(dòng)目標(biāo)組合數(shù)量為Ne，則細(xì)粒度層建?？偟臅r(shí)間復(fù)雜度為O()。

根據(jù)數(shù)據(jù)集的不同大小，對(duì)粗粒度引發(fā)關(guān)系網(wǎng)絡(luò)層與細(xì)粒度的時(shí)空聚合網(wǎng)絡(luò)層進(jìn)行建模，其建模時(shí)間如圖2。

圖2 粗細(xì)粒度混合建模耗時(shí)

2.3.4 挖掘時(shí)間復(fù)雜度分析

本節(jié)針對(duì)真實(shí)的行人數(shù)據(jù)，采用fastMDCOP-Miner［1］和CFCMDCOP Graph Miner 進(jìn)行模式挖掘比較。

移動(dòng)目標(biāo)關(guān)聯(lián)性挖掘算法主要進(jìn)行移動(dòng)目標(biāo)間引發(fā)率的計(jì)算、移動(dòng)目標(biāo)對(duì)應(yīng)軌跡組合的空間頻繁度計(jì)算、時(shí)空鄰近頻繁度計(jì)算，移動(dòng)目標(biāo)及對(duì)應(yīng)軌跡組合的連接操作，從而完成移動(dòng)目標(biāo)時(shí)空引發(fā)同現(xiàn)模式挖掘。

綜上所述，總復(fù)雜度為OCFCMDCOPGraphMiner=。

圖3 算法挖掘時(shí)間對(duì)比

分別使用傳統(tǒng)挖掘算法與CFCMDCOP 挖掘算法，對(duì)現(xiàn)有行人數(shù)據(jù)進(jìn)行時(shí)空引發(fā)同現(xiàn)模式挖掘，控制時(shí)間槽數(shù)、鄰近距離、空間頻繁閾值等相同。實(shí)驗(yàn)結(jié)果如圖5 所示，由圖可知，隨著軌跡點(diǎn)數(shù)量不斷增加，算法執(zhí)行的時(shí)間呈遞增趨勢(shì)，CFCMDCOP挖掘算法比傳統(tǒng)挖掘算法花費(fèi)時(shí)間更少，算法效率更高。

2.3.5 實(shí)驗(yàn)環(huán)境及結(jié)果

數(shù)據(jù)實(shí)驗(yàn)環(huán)境為Win7 虛擬機(jī)，JDK1.8，2 核CPU、8GB內(nèi)存，硬盤容量50GB，MySQL版本5.5。

本文實(shí)驗(yàn)所用的行人移動(dòng)目標(biāo)的軌跡數(shù)據(jù)來(lái)自于微軟亞洲研究院Geolife項(xiàng)目采集的數(shù)據(jù)集［17］。

人的軌跡數(shù)據(jù)源數(shù)據(jù)是由182位用戶為期5年的軌跡數(shù)據(jù)構(gòu)成，這些數(shù)據(jù)是用戶手機(jī)和GPS記錄儀記錄的軌跡點(diǎn)數(shù)據(jù)，每個(gè)軌跡點(diǎn)記錄以經(jīng)緯度、日期、時(shí)間等多個(gè)數(shù)據(jù)字段組成，樣本數(shù)據(jù)如表1所示。本文選取2008-10-23 至2008-11-21 的30天數(shù)據(jù)進(jìn)行挖掘分析計(jì)算。

表1 行人移動(dòng)目標(biāo)源數(shù)據(jù)

為了驗(yàn)證挖掘效率，本文將閾值設(shè)定調(diào)整到較低的限度。保證大多數(shù)模式能夠被發(fā)現(xiàn)。挖掘結(jié)果如表2所示。

表2 挖掘結(jié)果

3 結(jié)語(yǔ)

本文基于行人移動(dòng)目標(biāo)時(shí)空數(shù)據(jù)集，提出一種移動(dòng)目標(biāo)粗細(xì)粒度結(jié)合的混合網(wǎng)絡(luò)模型CFCMDCOP Graph，并給出挖掘算法CFCMDCOP Graph Miner。本文主要工作如下：1）對(duì)粗細(xì)粒度結(jié)合的模型CFCMDCOP Graph的結(jié)構(gòu)進(jìn)行描述，定義時(shí)空引發(fā)同現(xiàn)模式，為設(shè)計(jì)有效挖掘算法提供基礎(chǔ)；2）提出建模方法，粗粒度層的構(gòu)建基于移動(dòng)目標(biāo)軌跡信息匹配及FT 過(guò)濾器篩選，代替了直接遍歷軌跡點(diǎn)集，通過(guò)減少計(jì)算對(duì)象來(lái)降低建模耗時(shí)；3）提出針對(duì)混合模型的挖掘算法CFCMDCOP Graph Miner。挖掘中通過(guò)對(duì)粗粒度層的引發(fā)序列計(jì)算，提前對(duì)不滿足引發(fā)閾值的移動(dòng)目標(biāo)組合進(jìn)行剪枝，其細(xì)粒度層能夠快速挖掘多條軌跡之間的時(shí)間交集，在時(shí)間交集下建立時(shí)間槽并計(jì)算多軌跡間的時(shí)空鄰近頻繁度，減少挖掘過(guò)程中的冗余計(jì)算來(lái)提高算法挖掘效率。

最后，通過(guò)實(shí)驗(yàn)結(jié)果對(duì)建模與挖掘進(jìn)行驗(yàn)證，結(jié)果表明該模型能夠?qū)σ苿?dòng)目標(biāo)及其軌跡點(diǎn)實(shí)例的時(shí)空關(guān)系進(jìn)行快速建模，并且在移動(dòng)目標(biāo)模式挖掘方面較傳統(tǒng)算法具有更少的時(shí)間消耗、效率更高。