楊 盛

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

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

楊 盛

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

介紹了基于頻繁子圖挖掘算法的思想及其相關(guān)算法,提出了頻繁子圖挖掘算法的一些問題,對所挖掘圖的存儲方式進(jìn)行了討論,重點(diǎn)介紹了隱式存儲方式及其優(yōu)點(diǎn)。在頻繁子圖挖掘一般步驟的基礎(chǔ)上,提出了通過構(gòu)建頻繁子圖決策樹 (FSDT)來實(shí)現(xiàn)挖掘算法的預(yù)處理問題,最后初步提出寬度優(yōu)先子圖同構(gòu)法 (BFSI)來實(shí)現(xiàn)頻繁子圖決策樹 (FSDT)。

頻繁子圖;圖存儲方式;預(yù)處理;頻繁子圖決策樹

在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的發(fā)展中,人們漸漸的意識到傳統(tǒng)的屬性值和數(shù)據(jù)項(xiàng)集表示模式已經(jīng)不能滿足許多實(shí)際應(yīng)用領(lǐng)域的要求[1～4],則提出了基于頻繁子圖的索引方法,通過控制頻繁閾值可以控制頻繁子圖的數(shù)量。目前圖結(jié)構(gòu)數(shù)據(jù)的索引方法主要有 2種:基于路徑的索引方法;基于頻繁子圖的索引方法?；诼窂降乃饕椒ù嬖谧陨淼娜秉c(diǎn),首先,路徑太簡單,丟掉了圖的結(jié)構(gòu)信息;同時(shí),路徑的數(shù)量太大,1個(gè)圖數(shù)據(jù)庫的路徑集合往往非常巨大,該索引方法在長沙礦山研究院的數(shù)據(jù)庫應(yīng)用中就存在效率低的缺點(diǎn)。而基于頻繁子圖的索引方法使用頻繁子圖作為索引,融合了部分圖的結(jié)構(gòu)信息,在結(jié)構(gòu)信息的使用上比路徑索引有優(yōu)勢,因此本文主要介紹和論述此方法。

1 頻繁子圖挖掘算法

1.1 圖的存儲

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

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

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

1.2 圖數(shù)據(jù)庫的預(yù)處理

原來的各種算法中,除了沒有討論圖的存儲形式外,也都沒有對數(shù)據(jù)庫中的圖進(jìn)行預(yù)處理。本文提出對數(shù)據(jù)庫中的圖結(jié)構(gòu)數(shù)據(jù)進(jìn)行頻繁子圖挖掘前首先要進(jìn)行預(yù)處理。

圖結(jié)構(gòu)數(shù)據(jù)在各個(gè)行業(yè)中一般都是以非常大的數(shù)量出現(xiàn),通常是海量信息。當(dāng)進(jìn)行頻繁子圖的挖掘時(shí),就會存在如下問題。

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

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

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

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

recomputed embedding。每次記錄下出現(xiàn)該頻繁子圖的那些圖的編號,通過掃描出現(xiàn)過 k頻繁子圖的那些圖來計(jì)算 k+1候選子圖的支持度,這樣每次只記錄圖的編號,不用記錄子圖出現(xiàn)的位置,通過重復(fù)計(jì)算來獲得規(guī)模為 k+1的子圖的支持度,從而避免了全局掃描數(shù)據(jù)庫?？梢杂脕硖幚泶笮蛿?shù)據(jù)庫,但是速度不如第一種方法。

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

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

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

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

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

3 總 結(jié)

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

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

[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].計(jì)算機(jī)科學(xué),2005,32(10):193-197.

2011-07-26)

楊 盛 (1983-),女,湖南衡陽人,助理工程師,研究方向?yàn)橛?jì)算機(jī)科學(xué)與技術(shù),Email:ys-89@hotmail.com。