頻繁子圖挖掘算法的若干問題

楊 盛

(長沙礦山研究院, 湖南長沙 410012)

頻繁子圖挖掘算法的若干問題

楊 盛

(長沙礦山研究院, 湖南長沙 410012)

介紹了基于頻繁子圖挖掘算法的思想及其相關算法,提出了頻繁子圖挖掘算法的一些問題,對所挖掘圖的存儲方式進行了討論,重點介紹了隱式存儲方式及其優點。在頻繁子圖挖掘一般步驟的基礎上,提出了通過構建頻繁子圖決策樹 (FSDT)來實現挖掘算法的預處理問題,最后初步提出寬度優先子圖同構法 (BFSI)來實現頻繁子圖決策樹 (FSDT)。

頻繁子圖;圖存儲方式;預處理;頻繁子圖決策樹

在數據挖掘和機器學習的發展中,人們漸漸的意識到傳統的屬性值和數據項集表示模式已經不能滿足許多實際應用領域的要求[1～4],則提出了基于頻繁子圖的索引方法,通過控制頻繁閾值可以控制頻繁子圖的數量。目前圖結構數據的索引方法主要有 2種:基于路徑的索引方法;基于頻繁子圖的索引方法。基于路徑的索引方法存在自身的缺點,首先,路徑太簡單,丟掉了圖的結構信息;同時,路徑的數量太大,1個圖數據庫的路徑集合往往非常巨大,該索引方法在長沙礦山研究院的數據庫應用中就存在效率低的缺點。而基于頻繁子圖的索引方法使用頻繁子圖作為索引,融合了部分圖的結構信息,在結構信息的使用上比路徑索引有優勢,因此本文主要介紹和論述此方法。

1 頻繁子圖挖掘算法

1.1 圖的存儲

關于圖的存儲也可以稱為圖的表示 (graph representation)。目前圖的表示有鄰接數組 (Adjacency Arrays)、鄰接鏈表 (Adjacency Lists)、鄰接矩陣 (Adjacency Matrix)、隱式表示 (Implicit Representation)。其中鄰接數組主要用來描述靜態數組,鄰接鏈表主要用來表示動態圖,鄰接矩陣在表示稠密圖上有很大優勢。本文主要介紹以下 2種隱式表示方式。

(1)區間圖表示方法[5]。區間圖由一系列區間集合定義,每個區間對應圖的 1個結點,2個結點間的關系通過間隔的重疊來表示。這種表示方法的一個優勢是可以很容易的判斷 1個圖是否是連通圖。將表示結點的區間的端點按序排列,然后按序掃描這些端點。如果有 1個或以上的區間不與其它區間重疊,那么這個圖就不是連通的。否則就是連通的。另外 1個優勢是存儲圖時空間很省,只需要O(n)級別的空間,而且還可進行有效的遍歷。

(2)用 BDD來表示圖[6]。BDD是 1個基于有序變量集上的布爾函數,其規范和緊湊性使其空間需求非常小,而且查詢等操作速度較高,適用于圖的數量大且需要較高的查詢效率時。主要采用了如下技術進行處理:若圖 G有 n個結點,則可定義 k個布爾變量 x1,x2,...,xk,其中 k為不小于 log2(n)的自然數。使用變量集 X=x1,x2,...,xk對每個結點編碼,記為 E(u)。為了表示結點間的關聯關系,引入另一組變量 X’=x1’,x2’,...,xk’。把 E’(u)稱為E(u)的后繼編碼,這里 E’(u)是把 E(u)中 x1,x2,...,xk用相應的 x1’,x2’,...,xk’替換。如果節點 i和 j之間存在邊 E(i,j),則生成 BDDbij:bij=E(i)∧E’(j),圖 G的所有關聯關系可表示如下:T(G)=∨bij,其中 i,j取遍 1到 n。如果 i和 j不相鄰,則 bij=false。此時 BDD T(G)已經能夠把無權圖 G表示出來。

1.2 圖數據庫的預處理

原來的各種算法中,除了沒有討論圖的存儲形式外,也都沒有對數據庫中的圖進行預處理。本文提出對數據庫中的圖結構數據進行頻繁子圖挖掘前首先要進行預處理。

圖結構數據在各個行業中一般都是以非常大的數量出現,通常是海量信息。當進行頻繁子圖的挖掘時,就會存在如下問題。

(1)圖數據庫中存在某些圖是另外一些圖的子圖。當前的頻繁子圖挖掘算法都是先對圖建立規范編碼,然后對整個數據庫的圖逐個進行規范化,以便簡化子圖同構。下一步就是對整個數據庫中的圖進行頻繁子圖的候選子圖生成。對于生成候選子圖時,必須有基礎的頻繁子圖 (可能是 1個頂點或者 1條邊、2條邊等組成)。這些頻繁子圖需要在數據庫逐個掃描圖時統計其在圖數據庫各個圖中出現的次數,掃描結束時將這個次數與閾值進行比較,從而判斷該頻繁子圖是否是基礎頻繁子圖。這一步是計算基礎頻繁子圖的支持度,需要判斷和記錄基礎頻繁子圖在圖數據庫中出現的次數。這樣當圖數據庫中有一些圖是另外一些圖的子圖時,就可以通過預先對圖數據庫中的圖利用規范編碼等一些技術對圖數據庫中的圖進行頻繁子圖判斷,并建立頻繁子圖決策樹 (FSDT),來減少基礎頻繁子圖挖掘時所要掃描圖的數量。這在圖數據庫的數量很大或者圖數據庫中有很多子圖包含情況時有很好的效果。

分析構建后的頻繁子圖決策樹時發現,深度大于等于閾值的層上的圖 (GLDET)是頻繁子圖,同時其任何子圖也是頻繁子圖。這時如果按照 FSG算法來取所有以 1條邊和 2條邊為基礎頻繁子圖的話,那么頻繁子圖決策樹上滿足深度大于等于閾值的圖的所有單邊及其任何 2條邊的連通組合都是基礎頻繁子圖。建立這個 FSDT的優勢在于可以自動挖掘出大量的頻繁子圖,而且可以通過將不是 GLDET的圖與未成為 FSDT的圖在采用普通的頻繁子圖生成方法進行掃描計數。

(2)計算候選子圖的支持度時需要多次掃描候選集的情況。在進行計算頻繁子圖的支持度時,就會重復進行若干子圖同構測試。目前我們使用的 2種計算候選子圖支持度的方法分別為:embedding list方法和 recomputed embedding方法[7]。

embedding list。對于只有 1個頂點的圖,存儲輸入數據庫中出現該頂點的所有圖的編號。對于多頂點子圖,存儲輸入數據庫中所有出現該子圖的圖的編號以及該子圖在這些圖中的位置。這種方法計算起來速度快,但是要占用大量的存儲空間,不適合大型輸入數據庫。

recomputed embedding。每次記錄下出現該頻繁子圖的那些圖的編號,通過掃描出現過 k頻繁子圖的那些圖來計算 k+1候選子圖的支持度,這樣每次只記錄圖的編號,不用記錄子圖出現的位置,通過重復計算來獲得規模為 k+1的子圖的支持度,從而避免了全局掃描數據庫。可以用來處理大型數據庫,但是速度不如第一種方法。

從上面介紹的 2種方法可以看出處理大型數據庫時,當需要生 k+1規模的子圖時要掃描 k頻繁子圖集合,同樣可以把 FSDT方法用在 k頻繁子圖集合中,可減少同構的次數和生成 k+1規模頻繁子圖。規模為 k+1的頻繁子圖可在 FSDT中尋找,同時還可以將 GLDET中的各個圖添加一條邊來生成規模為 k+1的頻繁子圖。同樣規模為 k+2的頻繁子圖也同樣可以采用如上的方法。但是生成的頻繁子圖也有許多冗余頻繁候選子圖需要才剪掉,比較原先的 Level-wise search方法、貪心方法和深度優先等方法來說,具有非常好的效果。

2 構建頻繁子圖決策樹 (FSDT)的算法

采用寬度優先子圖同構法 (BFSI)構建頻繁子圖決策樹,即通過對圖庫中的圖依次進行子圖同構來構建子圖決策樹。

圖數據庫中 GD={G1,G2,...,Gn},對圖庫中的圖按大小排序后建立的圖的鏈表為 T={T1,T2,...,Tn},其中 T1為大小最大的圖集,T2為大小小于 T1的圖集,依次排序。Ti為圖的大小相同的圖的集合的數組,i∈n;Tij為 Ti圖集中的圖。j∈n。具體算法如下:

該算法通過寬度優先的方式從大到小進行子圖同構,然后建立頻繁子圖決策樹,從而可以使以后的頻繁子圖挖掘算法中的多次掃描數據庫和計算候選子圖支持度時的子圖同構得以大幅減少,從而提高算法效率。該算法本身的復雜度為O(n2/2)級別的子圖同構。

3 總 結

本文討論了基于圖的頻繁子圖的挖掘算法的算法思想和基于這些思想上的一些算法,介紹了基于Apriori思想和 FP-growth思想的及其衍生的各種頻繁子圖挖掘算法,歸納了頻繁子圖挖掘算法的基本步驟和流程。

文章中對前人忽視的圖庫中圖的存儲方式進行了介紹,并且介紹了 2種隱式存儲方式。這 2種隱式存儲方式可以節省大量空間,并且對圖的各種處理有若干優勢,是圖存儲的發展方向,也是圖的頻繁子圖挖掘算法的基礎,是未來改進圖的頻繁子圖的性能的重要突破點之一。另外提出了 FSDT來處理圖數據庫中存在多個圖是另外一些圖的子圖的問題,討論了 FSDT解決方案的優點,及其在基礎頻繁子圖的生成和候選子圖生成時的作用和優勢,并提出了寬度優先子圖同構法來構建頻繁子圖決策樹。

[1] BerendtB.,Hotho A.,Stumme G.Towards semantic web mining[C].IS WC,2002:264-278.

[2] DeshpandeM.,KuramochiM.,Karypis G.Automated approaches for classifying structures[C].In Proc.of the 2nd Workshop on Data Mining in Bioinformatics(B I OKDD’02),2002:11-18.

[3] Deshpande M.,KuramochiM.,Karypis G.Frequent sub-structure based approaches for classifying chemical compounds[C].In Proc.of 2003 IEEE International Conference on Data Mining(ICDM),2003:35-42.

[4] Gonzalez J.,Holder L.B.,Cook D.J.Application of graphbased concept learning to the predictive toxicology domain[J].In Proc.of the Predictive Toxicology Challenge Workshop,2001.

[5] KurtMehlhorn.Algorithms and Data Structures[C].Springer-Verlag Berlin and Heidelberg GmbH&Co.K,2008.

[6] Huan Jun,Wang Wei,Prins Jan.Efficient Mining of Frequent Subgraph in the presence of Isomorphism[C].ICDM,2003.

[7] 王艷輝,吳 斌,王 柏.頻繁子圖挖掘算法綜述[J].計算機科學,2005,32(10):193-197.

2011-07-26)

楊 盛 (1983-),女,湖南衡陽人,助理工程師,研究方向為計算機科學與技術,Email:ys-89@hotmail.com。