張海濤，李濟(jì)平，羅 城，冀 康，沈慧嫻

(1.南京郵電大學(xué) 地理與生物信息學(xué)院，江蘇 南京 210023 2.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

隨著通信技術(shù)、互聯(lián)網(wǎng)的發(fā)展，提供位置服務(wù)智能終端的數(shù)量日益增加，產(chǎn)生了大量的移動軌跡數(shù)據(jù)［1］。將移動軌跡數(shù)據(jù)與眾多行業(yè)的專題數(shù)據(jù)進(jìn)行集成關(guān)聯(lián)分析以及數(shù)據(jù)挖掘處理后，能發(fā)現(xiàn)含有豐富語義隱喻信息的移動性知識［2－6］。對獲取的移動性知識進(jìn)行研究分析，能為眾多行業(yè)應(yīng)用帶來有效的輔助決策［7］。同時，移動性知識的分析方法還可為研究人口流動和經(jīng)濟(jì)、資源等具有動態(tài)變化特征的復(fù)雜系統(tǒng)提供重要支撐［8］。

當(dāng)前對于移動性知識的研究，通常基于時空數(shù)據(jù)庫的概念進(jìn)行定義，主要包含關(guān)聯(lián)規(guī)則［9］、序列模式［10］等簡單移動性模式。分析單一的簡單移動性知識，不容易找出其中的關(guān)聯(lián)關(guān)系和整體結(jié)構(gòu)特性。而基于簡單移動性知識間的共同項構(gòu)建移動性模式網(wǎng)絡(luò)［11－12］，通過分析網(wǎng)絡(luò)的結(jié)構(gòu)特征，可以發(fā)現(xiàn)移動性模式形成的潛在規(guī)律。因此，從移動軌跡數(shù)據(jù)中挖掘移動性知識并構(gòu)建復(fù)雜網(wǎng)絡(luò)對于分析產(chǎn)生移動軌跡數(shù)據(jù)的復(fù)雜系統(tǒng)的特性具有重要意義。

目前，國內(nèi)外學(xué)者提出了一些移動性知識復(fù)雜網(wǎng)絡(luò)的構(gòu)建方法［13］。典型的方法包括：2008年Lacasa等［14］首次提出的基于時間序列構(gòu)建復(fù)雜網(wǎng)絡(luò)的可視圖建網(wǎng)算法。2009年Luque等［15］提出的一種便捷、效率高的水平可視圖算法。但是，這兩種方法主要應(yīng)用于時間序列的數(shù)據(jù)處理，缺乏對數(shù)據(jù)空間特性的考慮。2018年汪佩佩［16］提出了一種基于圖挖掘的移動性知識復(fù)雜網(wǎng)絡(luò)構(gòu)建方法。這種基于圖論的構(gòu)網(wǎng)方法，充分考慮了移動軌跡的空間特性，構(gòu)建出的網(wǎng)絡(luò)能夠很大程度表現(xiàn)移動數(shù)據(jù)運(yùn)動規(guī)律。但是該方法存在的主要問題是：沒有考慮移動軌跡的有向性，構(gòu)建的移動性模式網(wǎng)絡(luò)為無向加權(quán)網(wǎng)絡(luò)。這種方法很大程度上制約了對于移動性模式網(wǎng)絡(luò)的進(jìn)一步分析應(yīng)用。因此，本文提出了基于有向圖的頻繁子圖挖掘方法。

1 基本概念

1.1 移動性知識

移動性知識是指使用某種挖掘方法，依據(jù)設(shè)定的閾值，從大量移動軌跡數(shù)據(jù)中發(fā)現(xiàn)的某種頻繁出現(xiàn)的規(guī)律性知識。簡單的移動性知識包括：關(guān)聯(lián)規(guī)則、序列模式等形式的移動性模式。其中，關(guān)聯(lián)規(guī)則是數(shù)據(jù)庫中支持度和置信度大于等于閾值的移動性模式。關(guān)聯(lián)規(guī)則中的數(shù)據(jù)項目是并發(fā)關(guān)系，不區(qū)分發(fā)生的時間先后順序。序列模式是數(shù)據(jù)庫中支持度大于等于閾值的移動性模式。序列模式中的數(shù)據(jù)項目不指定具體的時間，只區(qū)分時間先后順序。本文構(gòu)建移動性模式網(wǎng)絡(luò)中使用的移動軌跡頻繁子圖［17］可視為序列模式的圖形式表達(dá)。

1.2 復(fù)雜網(wǎng)絡(luò)

復(fù)雜網(wǎng)絡(luò)［18］是復(fù)雜系統(tǒng)的拓?fù)涑橄?。點和邊是復(fù)雜網(wǎng)絡(luò)的基本構(gòu)成單元。依據(jù)邊是否具有方向，網(wǎng)絡(luò)進(jìn)一步分為有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)。分析復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特性，可以了解復(fù)雜系統(tǒng)的宏觀特征，發(fā)現(xiàn)隱藏復(fù)雜系統(tǒng)中的機(jī)制規(guī)律。復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特性主要包括：節(jié)點的度和度分布、平均最短路徑長度、聚集系數(shù)等。

從移動軌跡數(shù)據(jù)構(gòu)建的移動性模式網(wǎng)絡(luò)，實際是有向加權(quán)的地理空間交互網(wǎng)絡(luò)，其通常是諸如智能交通［19－21］、城市規(guī)劃［22－24］、疾病傳染［25－27］等大量具有地理空間特征的復(fù)雜系統(tǒng)拓?fù)涑橄?。本文重點關(guān)注移動性模式網(wǎng)絡(luò)的節(jié)點度值、聚集系數(shù)這兩類網(wǎng)絡(luò)特征。

2 基于有向頻繁子圖挖掘的移動性模式網(wǎng)絡(luò)構(gòu)建方法

網(wǎng)絡(luò)構(gòu)建方法包含兩個階段：基于有向圖的頻繁子圖挖掘，從移動軌跡有向圖中挖掘頻繁子圖；使用大數(shù)據(jù)計算平臺Apache Spark的圖并行計算引擎GraphX實現(xiàn)頻繁子圖連接和網(wǎng)絡(luò)構(gòu)建。首先給出方法涉及的基本定義，然后進(jìn)行算法設(shè)計和實例分析。

2.1 基本定義

定義1 移動軌跡定義為移動對象的時空演變，表示為 T ＝ ｛（tp1，t1），（tp2，t2），…，（tpn，tn）｝。其中，n表示對象在運(yùn)動過程中記錄采樣點的數(shù)量；tpi表示第i個軌跡點；ti表示第i個時間間隔；tpi在tpi＋1之前出現(xiàn)。

定義2 移動軌跡有向圖定義為G＝｛V（G），E（G），L（V（G）），L（E（G）），L｝。 其中， V（G） 為圖G中節(jié)點的集合，對應(yīng)于移動軌跡中的軌跡點tpi（i∈n）；E（G） ＝ ｛ek＝ （vi，vj） ｜vi，vj∈ V（G）｝ 為圖G中邊的集合，對應(yīng)于移動軌跡中的軌跡點間的演變 （tpi→ tpj｜i，j ∈ n）；L（V（G）） ＝ ｛L（vi）｜?vi∈V（G）｝為節(jié)點的標(biāo)號集合， L（E（G）） ＝｛L（ek） ｜?ek∈E（G）｝為邊的標(biāo)號集合，L為標(biāo)號函數(shù)。

定義3 對于移動軌跡有向圖G1，G2，如果存在映射函數(shù) f：V（G1） → V（G2），滿足條件： e ＝ （vi，vj） 是 G1的一條邊， e′＝ （f（vi），f（vj）） 是 G2的一條邊，則稱圖 G1，G2同構(gòu)。

對于移動軌跡有向圖 G，G′， 如果 V（G′） ?V（G） 且 E（G′） ?E（G） ，則稱 G′是 G 的子圖。 進(jìn)一步給定移動軌跡有向圖G″，若有圖 G″和 G′同構(gòu)，則稱圖G″和G是子圖同構(gòu)。

定義4 給定移動軌跡有向圖數(shù)據(jù)庫GD＝，若子圖g與Gi子圖同構(gòu)，則δ（g，Gi） ＝ 1， 否則 δ（g，Gi） ＝ 0。

定義5 給定移動軌跡有向圖數(shù)據(jù)庫GD＝{G1，G2，…，Gn}， 設(shè)置最小支持度閾值為minsup。如果δ（g，GD）≥minsup，則稱g是一個頻繁子圖。

定義6 給定頻繁子圖數(shù)據(jù)庫gD＝｛g1，g2，…，gn｝，n≥1，頻繁子圖網(wǎng)絡(luò)定義為：gN＝ ｛V，E｝，其中，V 為 gD中節(jié)點的集合，E ＝｛ek＝（vi，vj）｜vi，vj∈V｝為gD中邊的集合。合并頻繁子圖數(shù)據(jù)庫gD中的共同項可構(gòu)建頻繁子圖網(wǎng)絡(luò)gN。

定義7 給定移動軌跡有向圖G，對于其中的任一有向邊e＝（vi，vj），按照其兩個節(jié)點標(biāo)識、源節(jié)點標(biāo)號、邊標(biāo)號、目標(biāo)節(jié)點標(biāo)號的順序進(jìn)行擴(kuò)展，得到其對應(yīng)的擴(kuò)展邊 e′＝ （vi，vj，li，li，lj）， 其中，邊標(biāo)號與源節(jié)點標(biāo)號相同，表示邊的有向性。按照深度優(yōu)先遍歷圖G中所有邊，得到對應(yīng)擴(kuò)展邊的序列，記為圖G的DFS編碼。

定義8 一個圖G可能生成多個DFS編碼，對多個編碼建立字典序，選擇其中一個最小序來對圖G進(jìn)行唯一標(biāo)識。其中，字典序定義為a?b?c?…?z和A?B?C?…?Z，對其中任意兩條擴(kuò)展邊e′1＝（c1，c2，c3，c4，c5）和e′2＝（d1，d2，d3，d4，d5）滿足條件：

（1） e′1＝ e′2， 當(dāng)且僅當(dāng) ci＝ di，i＝ 1 ～ 5；

（2） e′1? e′2，當(dāng) ci＝ di，i＝ 1，2，…，n － 1 且 cn?dn，n ＝ 1 ～ 5；

（3） e′1? e′2， 其他。

2.2 算法設(shè)計

基于有向頻繁子圖挖掘的移動性模式網(wǎng)絡(luò)構(gòu)建方法包括：基于有向圖的頻繁子圖挖掘和頻繁子圖網(wǎng)絡(luò)構(gòu)建?；谟邢驁D的頻繁子圖挖掘是基于用戶設(shè)置的最小支持度閾值從移動軌跡有向圖庫中找到全部1階頻繁子圖的過程。具體的步驟包括：（1）將所有移動軌跡數(shù)據(jù)轉(zhuǎn)換成移動軌跡有向圖，并形成有向圖數(shù)據(jù)庫。（2）遍歷所有有向圖，計算出圖中節(jié)點的支持度。（3）去掉所有不頻繁的節(jié)點，以及對應(yīng)的孤立節(jié)點和不連通邊，簡化有向圖數(shù)據(jù)庫。（4）重復(fù)步驟（3），直至不存在孤立節(jié)點和不連通邊，并且所有節(jié)點均滿足最小支持度閾值，得到最終的簡化有向圖數(shù)據(jù)庫。（5）遍歷最終的簡化有向圖數(shù)據(jù)庫，得到所有滿足最小支持度閾值的1階頻繁子圖。

基于有向圖的頻繁子圖挖掘算法實現(xiàn)偽代碼見算法1。

算法1 基于有向圖的頻繁子圖挖掘

其中，第1行將移動軌跡數(shù)據(jù)庫轉(zhuǎn)換為移動軌跡有向圖庫；第2～6行是預(yù)處理過程，其中第2～4行基于minsup得到所有的頻繁節(jié)點，第5～6行重復(fù)去除孤立節(jié)點和單點邊，最終得到簡化后的有向圖數(shù)據(jù)庫；第7行是掃描簡化后的有向圖數(shù)據(jù)庫，找出所有頻繁單邊，得到1階頻繁子圖集。

頻繁子圖網(wǎng)絡(luò)構(gòu)建過程是：合并1階頻繁子圖集中的共同項，得到頻繁子圖網(wǎng)絡(luò)。算法實現(xiàn)的偽代碼見算法2。

算法2 頻繁子圖網(wǎng)絡(luò)構(gòu)建

其中，第1行合并1階頻繁子圖集中的相同節(jié)點，合并結(jié)果記為V；第2行合并1階頻繁子圖集中的相同邊，合并結(jié)果記為E；第3行基于1階頻繁子圖數(shù)據(jù)庫中節(jié)點和邊，生成頻繁子圖網(wǎng)絡(luò)。

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

本文提出方法包含移動性知識挖掘和復(fù)雜網(wǎng)絡(luò)構(gòu)建。移動性知識的挖掘采用基于有向圖的頻繁子圖挖掘算法，從移動軌跡有向圖中挖掘頻繁子圖。分析移動性知識挖掘算法的時間復(fù)雜度包括：（1）移動軌跡數(shù)據(jù)轉(zhuǎn)換為移動軌跡有向圖。假設(shè)存在n條移動軌跡數(shù)據(jù)，每條軌跡數(shù)據(jù)包含m個節(jié)點，形成n個有向標(biāo)記圖，其時間復(fù)雜度為Ttrans（n）＝O（n?m）。 （2） 移動性知識挖掘過程包括預(yù)處理階段和頻繁子圖挖掘階段。其中，預(yù)處理階段計算n個有向標(biāo)記圖中的m個節(jié)點的支持度，去掉所有不頻繁的節(jié)點以及對應(yīng)的孤立節(jié)點和不連通邊，簡化有向圖數(shù)據(jù)庫，其時間復(fù)雜度為Tpre（n）＝O（n?m）；頻繁子圖挖掘階段遍歷簡化后的n個有向圖數(shù)據(jù)庫，得到所有的滿足最小支持度閾值的1階頻繁子圖。假設(shè)簡化后的圖庫中包含p個節(jié)點，挖掘過程的時間復(fù)雜度為Tdm（n）＝O（n?p2）。 因此，挖掘算法的時間復(fù)雜度為Tmining（n）＝max｛O（n?m），O（n?p2）｝。 復(fù)雜網(wǎng)絡(luò)構(gòu)建合并 1階頻繁子圖集中的共同項，得到頻繁子圖網(wǎng)絡(luò)。假設(shè)1階頻繁子圖集中包含q個頻繁子圖，則構(gòu)建網(wǎng)絡(luò)過程的時間復(fù)雜度為Tcon（q）＝O（q）。

2.4 實例分析

下面通過一個例子來說明從移動軌跡有向圖庫中挖掘頻繁子圖，進(jìn)而構(gòu)建頻繁子圖網(wǎng)絡(luò)的具體過程。如表1所示，初始移動軌跡有向圖庫由3個有向標(biāo)記圖G1、G2、G3構(gòu)成。設(shè)置最小支持度閾值min sup＝1。

表1 移動軌跡的有向圖數(shù)據(jù)庫

2.4.1 預(yù)處理

基于移動軌跡有向圖數(shù)據(jù)庫的頻繁子圖挖掘和網(wǎng)絡(luò)構(gòu)建過程包括3個步驟：

（1）統(tǒng)計表1中所有節(jié)點的標(biāo)號個數(shù)，并計算對應(yīng)的支持度，結(jié)果如表2所示。

表2 各節(jié)點的標(biāo)號個數(shù)及支持度

基于設(shè)定的最小支持度閾值，去掉不頻繁的節(jié)點標(biāo)號E。

（2）刪除孤立節(jié)點標(biāo)號、不連通邊（單點邊）。刪除節(jié)點標(biāo)號E后，G2中連通D、E的邊變得不連通，需要刪除；同理G3中連通D、E和連通B、E的邊也變得不連通，也需要刪除。最終，得到簡化后的軌跡有向圖數(shù)據(jù)庫如表3所示。

表3 簡化后的軌跡有向圖數(shù)據(jù)庫

（3） 簡化軌跡有向圖數(shù)據(jù)庫，重復(fù)（1）和（2），直至統(tǒng)計結(jié)果均滿足min sup＝1為止。最終得到簡化的軌跡圖有向圖數(shù)據(jù)庫如表4所示。

表4 預(yù)處理后的軌跡有向圖數(shù)據(jù)庫

2.4.2 獲取1階頻繁子圖數(shù)據(jù)庫

對于預(yù)處理后的軌跡有向圖數(shù)據(jù)庫，基于min sup＝1獲取頻繁單邊集。遍歷有向圖數(shù)據(jù)庫，計算所有單邊的支持度，每條邊均使用5元組DFS編碼表示，結(jié)果如表5所示。

表5 圖庫中的所有單邊及其支持度

刪除支持度小于min sup＝1的單邊，得到頻繁單邊集，即1階頻繁子圖數(shù)據(jù)庫。結(jié)果如表6所示。

表6 1階頻繁子圖數(shù)據(jù)庫

（3）構(gòu)建頻繁子圖網(wǎng)絡(luò)

合并1階頻繁子圖數(shù)據(jù)庫中的共同項，即可得到頻繁子圖網(wǎng)絡(luò)。將表6轉(zhuǎn)換為圖的形式，合并其中的共同項得到頻繁子圖網(wǎng)絡(luò)，如圖1所示。

圖1 頻繁子圖網(wǎng)絡(luò)

3 實驗

3.1 實驗數(shù)據(jù)

本文采用的實驗數(shù)據(jù)是收集于2019年7月13日南京市的2 612輛出租車的GPS軌跡數(shù)據(jù)。實驗設(shè)定的相對支持度閾值為0.01。為保證方法性能測試的穩(wěn)定性，隨機(jī)采樣了10個批次的數(shù)據(jù)，基本信息如表7所示。

表7 10個批次移動軌跡的基本信息

3.2 實驗結(jié)果

通過采用本文提出的方法，得到10個批次移動軌跡數(shù)據(jù)對應(yīng)的移動性模式網(wǎng)絡(luò)，圖示表達(dá)分別如圖2和圖3所示。從10個批次數(shù)據(jù)對應(yīng)的移動性模式網(wǎng)絡(luò)的空間分布可以看出，每個網(wǎng)絡(luò)都可以清晰反映生成移動軌跡數(shù)據(jù)的出租車輛的頻繁運(yùn)行路線和主要的空間聚集區(qū)域。

圖2 第1～6個批次移動軌跡數(shù)據(jù)對應(yīng)的移動性模式網(wǎng)絡(luò)

圖3 第7～10個批次移動軌跡數(shù)據(jù)對應(yīng)的移動性模式網(wǎng)絡(luò)

3.3 網(wǎng)絡(luò)特征分析

分析10個批次網(wǎng)絡(luò)的網(wǎng)絡(luò)特征如圖4～7所示。

圖4 頻繁子圖數(shù)量

從圖4至圖7可以看出10個批次移動軌跡數(shù)據(jù)對應(yīng)移動性模式網(wǎng)絡(luò)的特征具有較為顯著的區(qū)分。其中，第5批次和第6批次由于數(shù)據(jù)挖掘得到的頻繁子圖的數(shù)量較多（見圖4），相應(yīng)地，其構(gòu)建網(wǎng)絡(luò)的平均聚集系數(shù)、平均節(jié)點度、平均節(jié)點入度、平均節(jié)點出度等網(wǎng)絡(luò)特征值較大（分別見圖5、圖6、圖7）。表明兩個批次數(shù)據(jù)生成的網(wǎng)絡(luò)聚集程度高，網(wǎng)絡(luò)的連通性強(qiáng)，更易發(fā)現(xiàn)網(wǎng)絡(luò)中多次被訪問、較為重要的節(jié)點。而對于第7批次的數(shù)據(jù)，挖掘出的頻繁子圖的數(shù)量較少，其對應(yīng)構(gòu)建網(wǎng)絡(luò)的特征值則具有相反的結(jié)果。

圖5 平均聚集系數(shù)

圖6 平均節(jié)點度數(shù)

圖7 平均節(jié)點入度／出度

4 結(jié)束語

由于傳統(tǒng)移動性知識特征表達(dá)太過單一而不能反映出生成移動性知識的復(fù)雜系統(tǒng)的潛在規(guī)律，本文提出了一種基于有向頻繁子圖挖掘的移動性模式網(wǎng)絡(luò)構(gòu)建方法。該方法通過移動軌跡數(shù)據(jù)到移動軌跡有向圖的轉(zhuǎn)換、基于有向圖的移動軌跡頻繁子圖挖掘以及基于GraphX圖框架處理實現(xiàn)移動性模式網(wǎng)絡(luò)構(gòu)建。實驗結(jié)果表明：基于有向圖的頻繁子圖挖掘方法構(gòu)建出的復(fù)雜網(wǎng)絡(luò)能清晰地反映移動軌跡數(shù)據(jù)的特征，具有可用性。今后，隨著大規(guī)模移動軌跡數(shù)據(jù)分析和應(yīng)用需要的增加，需要進(jìn)一步研究減少內(nèi)存開銷和提高處理速度等性能優(yōu)化問題。同時，如何將基于本文提出方法構(gòu)建的移動性模式網(wǎng)絡(luò)應(yīng)用于最優(yōu)路徑規(guī)劃，傳播分析等場景應(yīng)用，也是未來關(guān)注的重點方向。