最小權(quán)重有向頻繁子圖挖掘

任 威

（鐵道部經(jīng)濟(jì)規(guī)劃研究院 經(jīng)濟(jì)管理咨詢部，北京 100038）

面對(duì)海量的圖數(shù)據(jù)時(shí)，挖掘滿足最小支持度的頻繁子圖是人們感興趣的。當(dāng)前圖挖掘的熱點(diǎn)在于有向圖，即在大量的有向頻繁圖中挖掘出一種性質(zhì)更優(yōu)的圖。本文介紹一類特殊的頻繁子圖—最小權(quán)重有向頻繁子圖，它滿足最小支持度閾值，并且所包含的邊和頂點(diǎn)的權(quán)重之和在所有同構(gòu)子圖中是最小的，本文提出的挖掘方法用于處理此類頻繁子圖，在廠區(qū)鐵路運(yùn)輸分析研究中有實(shí)際應(yīng)用。根據(jù)廠區(qū)鐵路分布規(guī)模小、運(yùn)輸密度高的特點(diǎn)，用加權(quán)有向圖表示某廠區(qū)鐵路線路網(wǎng)結(jié)構(gòu)，不同標(biāo)記頂點(diǎn)表示不同類型的車間，不同標(biāo)記的有向邊表示不同的廠區(qū)鐵路線，頂點(diǎn)和邊的權(quán)重表示對(duì)應(yīng)的運(yùn)輸成本，權(quán)重越小成本越小。權(quán)重之和最小的子圖是運(yùn)輸成本最小的廠區(qū)鐵路網(wǎng)結(jié)構(gòu)，是在海量路網(wǎng)結(jié)構(gòu)中要尋找的目標(biāo)。

關(guān)于挖掘頻繁子圖的算法可以分為兩部分：（1）寬度優(yōu)先算法（BFS）,采用apriori性質(zhì)枚舉出現(xiàn)的子圖以保證滿足最小支持度，有代表性的是AGM[1]和FSG[2]兩種算法，分別針對(duì)頂點(diǎn)和邊進(jìn)行擴(kuò)展，但會(huì)產(chǎn)生大量復(fù)制圖，效率不高。（2）深度優(yōu)先算法（DFS），包括gSpan，F(xiàn)FSM和GraphGen等，通過(guò)擴(kuò)展頻繁邊來(lái)逐步得到頻繁子圖。Han和Yan提出的gSpan[3]對(duì)標(biāo)記圖進(jìn)行挖掘，但無(wú)法避免子圖同構(gòu)測(cè)試，F(xiàn)FSM算法[4]巧妙地將子圖擴(kuò)展問(wèn)題轉(zhuǎn)化為矩陣操作，降低了算法復(fù)雜度。GraphGen算法[5]運(yùn)用圖論理論，將子圖擴(kuò)展轉(zhuǎn)化為子樹擴(kuò)展，進(jìn)一步提高了算法效率。

以上是無(wú)向圖的挖掘，Li Yuhua等人提出的mSpan[6]針對(duì)有向圖進(jìn)行挖掘，收效良好。Masaki Shinoda等人提出的GWF-mine算法[7]考慮了權(quán)重因素，將其作為挖掘條件。

針對(duì)廠區(qū)鐵路運(yùn)輸線路結(jié)構(gòu)的研究，挖掘的是既帶有方向標(biāo)識(shí)，也帶有權(quán)重的圖數(shù)據(jù)。本文提出的算法針對(duì)此特殊圖數(shù)據(jù)集進(jìn)行挖掘，達(dá)到了預(yù)期目的，在第1種算法基礎(chǔ)上，提出了第2種改進(jìn)算法。

1 基本概念

定義1（子圖）：設(shè)G=(V, E)是一個(gè)圖，設(shè)V'?V和E'?E，若對(duì)E'中任意一條邊eij={vi, vj}，都有vi∈N'和vj∈N'，則稱G'=(V', E')是G的一個(gè)子圖。

定義2（子圖同構(gòu)）：設(shè)圖G=(V, E)和G'=(V', E')，若存在一一映射g:vi→v'i，且e={vi,vj}是 G的一條邊，且僅當(dāng)e'=(g(vi),g(v'i))是G'一條邊，則G與G'同構(gòu)。

定義3（圖規(guī)模）：有向圖中節(jié)點(diǎn)與兩個(gè)節(jié)點(diǎn)之間單個(gè)或成對(duì)有向邊（計(jì)數(shù)為1）的數(shù)量和。

2 最小權(quán)重有向頻繁子圖挖掘算法

本文提出兩種算法，第1種算法WDSpan先挖掘出頻繁子圖，再考慮權(quán)重，采用鄰接矩陣比較法篩選最小權(quán)重頻繁子圖。第2種算法MWD以加入權(quán)重的支持度閾值作為挖掘和剪枝的條件，通過(guò)同構(gòu)測(cè)試和平均權(quán)重的比較更新，既保證了結(jié)果的正確性和完整性，又減少了存儲(chǔ)空間，起到了改進(jìn)效果。

圖1 權(quán)重有向例圖

2.1 WDSpan

采用gSpan算法框架，定義最右頂點(diǎn)，最右路徑，前向邊和后向邊，前向擴(kuò)展和后向擴(kuò)展以及最右擴(kuò)展[5]，核心是深度優(yōu)先方法，搜索最小DFS編碼，稱為基本下標(biāo)，記為dfs(s)。

對(duì)圖1進(jìn)行DFS標(biāo)記，頂點(diǎn)間存在單向和雙向邊，對(duì)不同的邊給予不同的標(biāo)記，以0代表雙向邊，1代表與前向邊有相同方向的邊，_1代表與后向邊有相同方向的邊。

圖2是權(quán)重有向圖的3種不同的DFS標(biāo)記，加粗表示前向邊，其余為后向邊。頂點(diǎn)采用字母（數(shù)字）表示方法，字母表示頂點(diǎn)類別，括號(hào)中的數(shù)字表示頂點(diǎn)訪問(wèn)順序，邊上的字母表示有向邊類別（雙向邊中兩條有向邊的類型相同），數(shù)字表示有向邊的方向。以（C）為例，μ1是起始頂點(diǎn)，μs是最右頂點(diǎn)，最右路徑為 μ1— μ2—μ4—μ5。

圖2 3種不同的DFS標(biāo)記

對(duì)每個(gè)DFS標(biāo)記，定義邊序組織有向邊，邊序是在給出頂點(diǎn)訪問(wèn)順序的基礎(chǔ)上，所有后向邊出現(xiàn)在該頂點(diǎn)前向邊之前，若此頂點(diǎn)沒有前向邊，則把它的后向邊放在上一個(gè)訪問(wèn)節(jié)點(diǎn)前向邊之后。基于邊序可將加下標(biāo)的有向圖轉(zhuǎn)換為邊的序列。

定義4（DFS編碼序）：若存在某個(gè)圖數(shù)據(jù)的兩種不同DFS編碼，γ1={e11e12…e1n}和γ2={e21e22…e2m}，其中eij表示圖γi遍歷的第j條邊，γ1和γ2的線性序由下例條件決定：

（1）γ1=γ2，當(dāng)且僅當(dāng) m=n，且 e1i=e2i，其中1≤ i≤ n。

或者：n

（3）γ2? γ1其他情況

序列排序規(guī)則為：令邊序? T占據(jù)第1優(yōu)先級(jí)，邊的起始頂點(diǎn)標(biāo)記占據(jù)第2優(yōu)先級(jí)，方向標(biāo)示（1 ? 0? _1 ）占據(jù)第3優(yōu)先級(jí)，邊的標(biāo)記占據(jù)第四優(yōu)先級(jí)，邊的終止頂點(diǎn)標(biāo)記在最末級(jí)。上面 3種 DFS編碼的第 1條邊 (μ1μ2A 1 a A)、(μ1μ2A _1 a A)和(μ1μ2A _1 c C)中，? T無(wú)差別，起始頂點(diǎn)μj無(wú)差別，方向標(biāo)示1? _1，所以得到γ1? γ2? γ3，γ1就是要找的基本下標(biāo)。與圖2對(duì)應(yīng)的不同的DFS編碼如表1所示。

表1 3種不同的DFS編碼

使用標(biāo)準(zhǔn)鄰接矩陣把權(quán)重有向圖的權(quán)重表示為方陣中的元素，主對(duì)角線上的元素表示有向圖節(jié)點(diǎn)權(quán)重，其余各點(diǎn)表示特定兩節(jié)點(diǎn)間有向邊的權(quán)重。圖1記錄為下面的鄰接方陣。

對(duì)任意頂點(diǎn)，如果點(diǎn)權(quán)重與和它有關(guān)聯(lián)的邊權(quán)重太大，表示運(yùn)輸成本過(guò)大，要將其剪枝。假設(shè)權(quán)重關(guān)聯(lián)最大閾值不能超過(guò)20，頂點(diǎn)i的相關(guān)權(quán)重計(jì)算公式為：(ai1+ai2+…ain)+(a1i+a2i+ani)_aii，上例中，5個(gè)頂點(diǎn)權(quán)重分別為16、12、19、15、15，小于最大權(quán)重閾值。為了簡(jiǎn)便，判斷一個(gè)圖是否可以剪枝，先求出鄰接矩陣的1_范數(shù)和∞_范數(shù)并相加，若小于規(guī)定的頂點(diǎn)權(quán)重關(guān)聯(lián)最大閾值，則必然滿足條件；否則計(jì)算每個(gè)頂點(diǎn)的權(quán)重關(guān)聯(lián)值來(lái)逐一比較。

可比較的鄰接矩陣一定有相同結(jié)構(gòu)，只需把非零處的權(quán)重相加求和再比較大小即可，不用遍歷整個(gè)矩陣。

2.1.1 算法描述（gSpan）

輸入：權(quán)重有向圖數(shù)據(jù)集WDGD，最小支持度閾值min_sup，DFS編碼 S。

輸出：頻繁子圖集合S。

（1）put S、T←φ'S，為頻繁子圖集合。T為使s最右擴(kuò)展一次后的結(jié)果集；

（2）if s≠dfs(s) then ；

（3）return；

（4）put S←s；

（5）遍歷WDGD一次，找出所有可使S最右擴(kuò)展的邊e，put T←s+e；

（6）用DFS詞典序?qū)排序；

（7）for each T中的頻繁s+e，do；

（8）對(duì)s+e重復(fù)s的擴(kuò)展過(guò)程。

2.1.2 算法描述（WDSpan）

輸入：頻繁子圖集合S，單獨(dú)頂點(diǎn)的權(quán)重關(guān)聯(lián)最大閾值t。

輸出：最小權(quán)重頻繁子圖集合C 。

（1）計(jì)算S中每個(gè)子圖s的1-范數(shù)和 ∞-范數(shù)，相加求和，if 和小于t，則放在C1中；

（2）記和大于t的子圖s= {v1, v2, …, vn}；

（3）For i=1, 2, …, n

計(jì)算每個(gè)頂點(diǎn)的關(guān)聯(lián)權(quán)重w1, w2, …, wn若他們都小于t，則放在C1中；

（4）對(duì)同構(gòu)的矩陣，找到權(quán)重和最小的，記為 s1，put C ← s1。

2.2 算法MWD

WDSpan中，第1步是挖掘，第2步根據(jù)權(quán)重來(lái)剪枝和篩選，得到最小權(quán)重頻繁子圖，但會(huì)出現(xiàn)很多權(quán)重很大的頻繁子圖作為中間結(jié)果再剪枝，使算法復(fù)雜度偏高。對(duì)此缺陷，本文根據(jù)權(quán)重圖特點(diǎn)，把圖數(shù)據(jù)的權(quán)重和支持度閾值相結(jié)合作為剪枝標(biāo)準(zhǔn)，以圖1為例來(lái)說(shuō)明新的剪枝計(jì)算方法。

定義5（平均權(quán)重）：一個(gè)權(quán)重有向圖，圖規(guī)模為n，則它的平均權(quán)重為每個(gè)點(diǎn)和成對(duì)或單向有向邊權(quán)重之和除以n，即(vi+eij)/n，其中vi(i∈1, 2, …, m)表示m個(gè)頂點(diǎn)的權(quán)重，eij(i, j∈1, 2, …,m)且i< j表示單獨(dú)或成對(duì)有向邊的權(quán)重，eij= (vi·aij+vj·aij)/(vi+vj) 。

計(jì)算得：圖1的規(guī)模為11，平均權(quán)重約為2.84。

定義6（平均權(quán)重支持度閾值—MWeight）：一個(gè)圖數(shù)據(jù)的平均權(quán)重和它出現(xiàn)在圖數(shù)據(jù)庫(kù)中支持度計(jì)數(shù)的乘積。

平均權(quán)重支持度閾值是一個(gè)對(duì)圖數(shù)據(jù)剪枝的標(biāo)準(zhǔn)，給定子圖的支持度計(jì)數(shù)和平均權(quán)重支持度閾值，采用以下兩個(gè)條件進(jìn)行剪枝。

（1）sup(G)

（2）MWeight(G)≥MWeight(G3)所有的平均值， G3表示已挖掘出的兩個(gè)頂點(diǎn)和有向邊組成的規(guī)模為3的子圖，是有實(shí)際意義的最小子結(jié)構(gòu)。

第（2）條表示若某個(gè)子圖的MWeight不比規(guī)模為3的“小”子圖的平均值小，則再對(duì)它進(jìn)行擴(kuò)展也不能得到感興趣的子圖（反單調(diào)性）。

首先，計(jì)算得到所有G3的平均權(quán)重支持度閾值的平均值。采用深度優(yōu)先策略，獲得1—權(quán)重頻繁子圖并按權(quán)重由小到大排序，從最小點(diǎn)進(jìn)行擴(kuò)展，按照由小到大順序依次將頻繁有向邊連接到頂點(diǎn)上，形成2—權(quán)重頻繁子圖。按照權(quán)重排序把頻繁頂點(diǎn)連接到頻繁有向邊上，可以形成G3，計(jì)算所有G3的平均權(quán)重支持度閾值再求平均值，就可以得到剪枝條件（2）。如此再挖掘G4、G5直到Gn，總是把頻繁頂點(diǎn)連接到原圖上，滿足最小支持度閾值，再計(jì)算平均權(quán)重支持度閾值，進(jìn)而剪枝。

子圖擴(kuò)展總是將權(quán)重最小的有向邊和頂點(diǎn)連接到原子圖中，但它可能并不出現(xiàn)在圖數(shù)據(jù)庫(kù)中，需進(jìn)行子圖同構(gòu)測(cè)試。比較從不同權(quán)重?cái)U(kuò)展的生成子圖的平均權(quán)重，尋找生成的最小權(quán)重子圖作為下次擴(kuò)展的首選，如圖3所示。

圖3 （a）最小權(quán)重子圖

圖3 （b）最小權(quán)重子圖

圖3（a）權(quán)重為2.58，圖3（b）權(quán)重為2.28，挖掘時(shí)先得到上面的生成子圖，但要將圖3（b）作為下一步擴(kuò)展的首選子圖。

2.2.1 算法描述（MWD）

輸入：權(quán)重有向圖數(shù)據(jù)集WDGD，最小支持度閾值min_sup

輸出：最小權(quán)重有向頻繁子圖集合C

（1）找到所有1—頻繁子圖，按照權(quán)重由小到大進(jìn)行排序(頂點(diǎn)和有向邊分別排序)， put G1←所有1—頻繁子圖。G1={v1, v2, …, vm; e1, e2, …,en}；

（2）put Gk→φ(k=3, 4, …, l)， l 是 WDGD中最大圖規(guī)模；

（3）put Hk→φ(k=3, 4, …, l) ；

（4）找到所有3—頻繁子圖，對(duì)不同構(gòu)的子圖，找到有最小平均權(quán)重的那些子圖，記為min_g3，同理，其他K—頻繁子圖不同構(gòu)的最小平均權(quán)重子圖記為min_gk-1；

（5）Put G3← min_g3；

（6）for k=4, 5, …, l for每個(gè)vi和ejdo ；

join min_gk-1+ ej，+ min_gk-1+ vi；

（7）if MWeight(min_gk-1+ ej)≥ MWE（所有3—頻繁子圖權(quán)重和的平均值）剪枝；

（8）if MWeight(min_gk-1+ vi)≥MWeight（所有3—頻繁子圖權(quán)重和的平均值）剪枝；

（9）find min_gk-1+ ej以及min_gk-1+ vi中平均權(quán)重最小的子圖，put them→Gkput others →Hk；

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

性能測(cè)評(píng)實(shí)驗(yàn)的平臺(tái)是Pentium IV 2 GHz CPU，2 GB內(nèi)存，硬盤為300 G，操作系統(tǒng)Windows server 2008，實(shí)驗(yàn)用MATLAB環(huán)境編寫。實(shí)驗(yàn)所用的數(shù)據(jù)來(lái)自人工模擬合成的關(guān)于廠區(qū)鐵路結(jié)構(gòu)數(shù)據(jù)集。表2列出了數(shù)據(jù)模擬使用到的參數(shù)和含義。

表2 實(shí)驗(yàn)數(shù)據(jù)參數(shù)及意義

采用的有向圖數(shù)據(jù)集表示為D10KT30-L50I10E50F20，實(shí)驗(yàn)對(duì)兩種算法在挖掘的完整性和運(yùn)行效率上進(jìn)行了比較分析。

圖4（a）、（b）分別給出在不同的支持度閾值下，兩種算法發(fā)現(xiàn)頻繁子圖的數(shù)目和最小權(quán)重頻繁子圖的數(shù)目。增大，兩種算法的運(yùn)行時(shí)間逐漸接近。

圖4 （a）WDSpan的子圖數(shù)目對(duì)比

圖4 （b）MWD的子圖數(shù)目對(duì)比

圖4 （c）運(yùn)行時(shí)間對(duì)比

4 結(jié)束語(yǔ)

本文針對(duì)權(quán)重有向圖數(shù)據(jù)集，提出兩種挖掘最小權(quán)重頻繁子圖的算法。采用電腦人工合成數(shù)據(jù)集進(jìn)行性能分析實(shí)驗(yàn)，表明兩種算法都可以保證挖掘結(jié)果的正確性和連通完整性。得到最小權(quán)重有向頻繁子圖，是運(yùn)輸成本最小且有一定出現(xiàn)比例的廠區(qū)鐵路線結(jié)構(gòu)模型。分析原因，改變?cè)O(shè)計(jì)，可以降低廠區(qū)鐵路運(yùn)輸成本。

進(jìn)一步分析發(fā)現(xiàn)，MWD的性能要優(yōu)于WDSpan，表現(xiàn)為更少的運(yùn)行時(shí)間和更小的存儲(chǔ)空間。但是MWD算法也有不足，如不可避免子圖同構(gòu)測(cè)試，每一次擴(kuò)展都要和其他擴(kuò)展結(jié)果通過(guò)比較平均權(quán)重找到最小權(quán)重頻繁子圖。

橫坐標(biāo)表示遞增的最小支持度閾值，表示挖掘到的頻繁子圖數(shù)目呈遞減趨勢(shì)。隨著最小支持度閾值的增大，原來(lái)頻繁的子圖有可能變?yōu)椴活l繁被剪枝，造成頻繁子圖數(shù)目減少。

對(duì)比（a）和（b）兩幅圖，WDSpan產(chǎn)生頻繁子圖的數(shù)目遠(yuǎn)多于MWD產(chǎn)生的數(shù)目，而它們產(chǎn)生的最小權(quán)重頻繁子圖數(shù)目卻差不多，說(shuō)明兩種算法挖掘結(jié)果是相當(dāng)?shù)?，但后者產(chǎn)生更少的中間產(chǎn)物，需要較少的存儲(chǔ)空間，算法性能更好。

圖4（c）給出了在不同的支持度閾值下，WDSpan和MWD的運(yùn)行時(shí)間對(duì)比。支持度較小時(shí)，兩種算法運(yùn)行時(shí)間相差很大，隨著支持度的

[1]Inokuchi A, Washio T, Okada T. An apriori-based algorithm for mining frequent substructures from graph data[C]. Proc.of the PKDD 2000. LNAI 1910, 2000：13-23.

[2]Michihiro Kuramochi, George Karypis. An Efficient Algori

thm for Discovering Frequent Subgraphs[J]. IEEE TRAN

SACTIONS ON KNOWLEDGE AND DATA ENGINEE

RING, VOL. 16, NO. 9, SEPTEMBER 2004.

[3]Yan Y, Han J. gSpan: Graph-Based substructure pattern mining[C]. Proc. of the 2002 Int’l Conf. on Data Mining (ICDM 2002).Maebashi, 2002.

[4]Han J, Wang W, Prins J. Efficient mining of frequent subgraphs in the presence of isomorphism[C]. Proc. of the IEEE Int’l Conf.on Data Mining (ICDM 2003). 2003.

[5]LI XT , LI JZ .An efficient frequent subgraph mining algorithm[J]. Journal of Software, Vol.18, No.10, October 2007.

[6]LI Yuhua. A Directed Labeled Graph Frequent Pattern Mining Algorithm based on Minimum Code[C]. Third International Conference on Multimedia and Ubiquitous Engineering.2009.

[7]Masaki Shinoda, Tomonobu Ozaki.Weighted Frequent Subgraph Mining inWeighted Graph Databases[C]. 2009 IEEE International Conference on Data Mining Workshops.