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

張海濤，李濟平，羅 城，冀 康，沈慧嫻

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

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

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

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

1 基本概念

1.1 移動性知識

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

1.2 復雜網(wǎng)絡

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

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

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

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

2.1 基本定義

定義1 移動軌跡定義為移動對象的時空演變，表示為 T ＝ ｛（tp1，t1），（tp2，t2），…，（tpn，tn）｝。其中，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é)點的集合，對應于移動軌跡中的軌跡點tpi（i∈n）；E（G） ＝ ｛ek＝ （vi，vj） ｜vi，vj∈ V（G）｝ 為圖G中邊的集合，對應于移動軌跡中的軌跡點間的演變 （tpi→ tpj｜i，j ∈ n）；L（V（G）） ＝ ｛L（vi）｜?vi∈V（G）｝為節(jié)點的標號集合， L（E（G）） ＝｛L（ek） ｜?ek∈E（G）｝為邊的標號集合，L為標號函數(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 的子圖。 進一步給定移動軌跡有向圖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}， 設置最小支持度閾值為minsup。如果δ（g，GD）≥minsup，則稱g是一個頻繁子圖。

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

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

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

（1） e′1＝ e′2， 當且僅當 ci＝ di，i＝ 1 ～ 5；

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

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

2.2 算法設計

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

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

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

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

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

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

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

2.3 算法時間復雜度分析

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

2.4 實例分析

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

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

2.4.1 預處理

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

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

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

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

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

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

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

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

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

對于預處理后的軌跡有向圖數(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)絡

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

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

3 實驗

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

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

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

3.2 實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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