頻繁子圖挖掘算法gSpaｎ的設(shè)計(jì)與實(shí)現(xiàn)

摘 要：由于大部分圖挖掘算法都需要利用頻繁子圖，頻繁子圖挖掘逐漸成為了數(shù)據(jù)挖掘領(lǐng)域中的熱點(diǎn)研究內(nèi)容。目前，很多高效的頻繁子圖挖掘算法已經(jīng)被提出。其中，ｇＳｐａｎ算法是目前公認(rèn)的最好的頻繁子圖挖掘算法。然而，在化合物數(shù)據(jù)集上，還可以利用化合物的特殊結(jié)構(gòu)進(jìn)一步優(yōu)化ｇＳｐａｎ算法的性能。文獻(xiàn)利用了化合物分子結(jié)構(gòu)的對稱性和原子類型分布的不均衡性，提出了一些新的優(yōu)化策略，進(jìn)一步改進(jìn)了ｇＳｐａｎ的性能。鑒于ｇＳｐａｎ算法在圖挖掘領(lǐng)域乃至整個(gè)數(shù)據(jù)挖掘領(lǐng)域的重要性，設(shè)計(jì)并實(shí)現(xiàn)ｇＳｐａｎ算法。同時(shí)，采用文獻(xiàn)[４]中的優(yōu)化策略，進(jìn)一步提高ｇＳｐａｎ算法在化合物數(shù)據(jù)集上的運(yùn)行效率。

關(guān)鍵詞：

中圖分類號： ＴＰ３１１ 文獻(xiàn)標(biāo)識碼： Ａ 文章編號：２０９５－２１６３（２０１１）０３－００５５－０３

Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ａ Ｆｒｅｑｕｅｎｔ Ｓｕｂｇｒａｐｈ Ｍｉｎｉｎｇ Ａｌｇｏｒｉｔｈｍ ｇＳｐａｎ

ＧＵＯ Ｙｕｌｉｎ， ＬＩＵ Ｙｏｎｇ

Ａｂｓｔｒａｃｔ： Since most of the graph mining algorithms are needed to make frequent subgraph，frequent subgraph mining is gradually becoming the hot spot in the field of research. At present， many efficient frequent subgraph mining algorithms have been proposed. Among them， gSpan algorithm is currently accepted as the best frequent subgraph mining algorithm. However， in the compound datasets， the performance of gSpan algorithm based on the special structure could be further optimized. The paper uses the symetry of the molecular structure of compounds and the unequilibrium of the distribution of atomic types， and puts forward some new optimization strategy， so as to further improve the performance of gSpan algorithm. Because gSpan algorithm is very vital in graph mining areas and the entire data mining field， this paper designes and implementes gSpan algorithm. Meanwhile， the paper also prepares to adopt the optimization strategy in the literature[4]， further improves the gSpan algorithm operation efficiency in compound datasets.

Ｋｅｙ ｗｏｒｄｓ：

０ 引言

由于大部分圖挖掘算法[１－３]都需要利用頻繁子圖，頻繁子圖挖掘逐漸成為了數(shù)據(jù)挖掘領(lǐng)域中的熱點(diǎn)研究內(nèi)容。目前，很多高效的頻繁子圖挖掘算法已經(jīng)被提出。其中，ｇＳｐａｎ算法是目前公認(rèn)的最好的頻繁子圖挖掘算法。該算法利用模式增長（ｐａｔｔｅｒｎ－ｇｒｏｗｔｈ）策略，采用深度優(yōu)先方式遍歷模式搜索空間。在某個(gè)頻繁子圖ｐ的基礎(chǔ)上，擴(kuò)展產(chǎn)生ｐ的孩子（ｐ的超模式） 并計(jì)算其支持度，對ｐ的每個(gè)頻繁孩子，以深度優(yōu)先方式繼續(xù)擴(kuò)展，直到發(fā)現(xiàn)全部頻繁子圖為止。

然而，在化合物數(shù)據(jù)集上，還可以利用化合物的特殊結(jié)構(gòu)進(jìn)一步優(yōu)化ｇＳｐａｎ算法的性能。文獻(xiàn)[４]利用了化合物分子結(jié)構(gòu)的對稱性和原子類型分布的不均衡性，提出了一些新的優(yōu)化策略，進(jìn)一步改進(jìn)了ｇＳｐａｎ的性能。

本文內(nèi)容安排如下：第１節(jié)給出問題定義 第２節(jié)給出算法描述 第３節(jié)給出實(shí)驗(yàn)結(jié)果第４節(jié)總結(jié)全文。

１ 問題定義

本節(jié)首先介紹預(yù)備知識，然后給出問題的形式化定義。

本文主要考慮連通的無向標(biāo)號簡單圖。通過簡單修改，本文的ｇＳｐａｎ算法也適用于有向圖，無標(biāo)號圖和不連通圖。如無特別說明，本文中的圖均指連通的無向標(biāo)號圖。一個(gè)圖Ｇ定義為一個(gè)四元組Ｇ＝（ Ｖ，Ｅ，Σ，ｌ ），其中，Ｖ是頂點(diǎn)集合，Ｅ?哿Ｖ×Ｖ是邊集合，Σ是標(biāo)號集合， ｌ：Ｖ∪Ｅ→Σ是一個(gè)函數(shù)， 用來對頂點(diǎn)和邊分配標(biāo)號。

定義１ （圖同構(gòu)）：圖的同構(gòu)是一個(gè)雙射ｆ： Ｖ（Ｇ）?圮Ｖ（Ｇ′）。對于圖Ｇ＝Ｖ，Ｅ，ΣＶ，ΣＥ，Ｌ?妖與圖Ｇ′＝Ｖ′，Ｅ′，ΣＶ′，ΣＥ′，Ｌ′?妖，若Ｇ與Ｇ′是同構(gòu)的，則滿足如下條件：

單射函數(shù)ｆ也稱為Ｇ在Ｇ′中的一個(gè)嵌入。

如果存在一個(gè)從Ｇ到Ｇ′的子圖同構(gòu)，則Ｇ稱為Ｇ′的子圖， Ｇ′稱為Ｇ的超圖，記為Ｇ?哿Ｇ′。如果Ｇ?哿Ｇ′且Ｇ≠Ｇ′，則Ｇ稱為Ｇ′的真子圖， Ｇ′稱為Ｇ的真超圖，記為Ｇ?奐Ｇ′。子圖同構(gòu)測試已被證明是一個(gè)ＮＰ－完全問題．如果Ｇ?哿Ｇ′，也稱Ｇ′包含Ｇ。

給定一個(gè)圖集合Ｄ＝Ｇ１，Ｇ２，…，Ｇｎ?妖和一個(gè)圖模式Ｐ， Ｐ在Ｄ中的支持集定義為Ｄ中包含Ｐ的圖集合，記為Ｄｓｕｐｐ（Ｐ）＝Ｇｉ｜Ｐ?哿Ｇｉ， Ｇｉ∈Ｄ?妖。｜Ｄｓｕｐｐ（Ｐ）｜稱為Ｐ在Ｄ中的支持度，記為ｓｕｐｐ（ＰＤ）。｜Ｄｓｕｐｐ（Ｐ）｜／｜Ｄ｜稱為Ｐ在Ｄ中的相對支持度。支持度度量具有反單調(diào)性質(zhì)：如果Ｐ１?哿Ｐ２，則ｓｕｐｐ（Ｐ１Ｄ）≥ｓｕｐｐ（Ｐ２Ｄ）。對于用戶給定的一個(gè)最小支持度閾值ｍｉｎ＿ｓｕｐ，如果ｓｕｐｐ（ＰＤ）≥ｍｉｎ＿ｓｕｐ，稱Ｐ在Ｄ中是頻繁的。Ｄ中所有頻繁圖模式集合記為ＦＳ＝Ｐ｜ ｓｕｐｐ（ＰＤ）≥ｍｉｎ＿ｓｕｐ?妖。

本文要解決的頻繁子圖挖掘問題可描述為：給定一個(gè)圖數(shù)據(jù)庫Ｄ，一個(gè)用戶指定的最小支持度閾值ｍｉｎ＿ｓｕｐ，挖掘該圖數(shù)據(jù)庫上的所有頻繁子圖。

要使用ｇＳｐａｎ算法完成該任務(wù)，需要實(shí)現(xiàn)ｇＳｐａｎ算法中的如下關(guān)鍵技術(shù)：

（１）為圖模式設(shè)計(jì)一種唯一性編碼方案，使得每個(gè)圖模式都對應(yīng)唯一一個(gè)的編碼

（２）為高效遍歷圖模式搜索空間，設(shè)計(jì)了一種深度優(yōu)先枚舉框架

（３）基于支持度的反單調(diào)性質(zhì)，使用分支限界算法對圖模式搜索空間進(jìn)行剪枝，以提高挖掘效率

（４）計(jì)算圖模式支持度時(shí)，設(shè)計(jì)一些優(yōu)化策略，在某些條件下，使用嵌入鏈表方式可以明顯改善挖掘效率

（５）利用化合物的特殊結(jié)構(gòu)（分子化合物中存在很多對稱結(jié)構(gòu)，分子化合物中原子類型分布不均衡）來設(shè)計(jì)ｇＳｐａｎ算法的優(yōu)化策略。

２ 算法

本算法通過ｍａｉｎ函數(shù)傳遞參數(shù)，參數(shù)包括－ｍ ｉ、－ｐ、－ｔ、ｍｉｎＳｕｐ、ｉｎｐｕｔｆｉｌｅ和ｏｕｔｐｕｔｆｉｌｅ等。

－ｍ ｉ：在挖掘子圖過程中，只針對規(guī)模小于或等于ｉ的頻繁圖進(jìn)行挖掘。

－ｐ：只保留線性結(jié)構(gòu)。

－ｔ：只保留樹形結(jié)構(gòu)。

ｍｉｎＳｕｐ：指定最小支持度的參數(shù)，為整形變量。

ｉｎｐｕｔｆｉｌｅ：輸入數(shù)據(jù)文件名。

ｏｕｔｐｕｔｆｉｌｅ：輸出數(shù)據(jù)文件名。

本算法首先使用ｐｒｅｐｒｏｃｅｓｓＤＢ函數(shù)進(jìn)行數(shù)據(jù)導(dǎo)入處理，并創(chuàng)建與存儲(chǔ)相關(guān)的數(shù)據(jù)結(jié)構(gòu)。此后算法采用遞歸調(diào)用，進(jìn)行深度優(yōu)先挖掘。

深度優(yōu)先挖掘是算法的核心，主要包含以下三個(gè)函數(shù)和子程序：ＧｒａｐｈＳｅｔ＿Ｐｒｏｊｅｃｔｉｏｎ（ＧＳ，Ｓ），Ｓｕｂｇｒａｐｈ＿Ｍｉｎｇ（ＧＳ，Ｓ，ｓ），Ｅｎｕｍｅｒａｔｅ（ｓ）。

函數(shù)：ＧｒａｐｈＳｅｔ＿Ｐｒｏｊｅｃｔｉｏｎ（ＧＳ，Ｓ）

（１）從集合ＧＳ（ｇｒａｐｈＳｅｔ）中讀圖數(shù)據(jù)，對點(diǎn)與邊按頻度進(jìn)行排序

（２）移除不頻繁的點(diǎn)與邊

（３）移除后，余下的頻繁的點(diǎn)與邊重新標(biāo)號，進(jìn)行降序排列

（４）把集合ＧＳ中的頻繁一邊圖存于集合Ｓ１中

（５）按ＤＦＳ詞典序，對集合Ｓ１進(jìn)行排序

（６）把集合Ｓ１中元素存于集合Ｓ中

（７）遍歷集合Ｓ１中單邊ｅ

（８）用邊ｅ初始化ｓ，遍歷集合ＧＳ中的ｇ，凡是包含邊ｅ的圖ｇ，賦予ｓ的ＧＳ中（只記錄ｇ的ＩＤ）

（９） Ｓｕｂｇｒａｐｈ＿Ｍｉｎｉｎｇ（ＧＳ，Ｓ，ｓ）

（１０） 在集合ＧＳ中刪除邊ｅ

（１１）如果集合ＧＳ中ｇ（ｇｒａｐｈ）的個(gè)數(shù)小于ｍｉｎＳｕｐ

（１２） 停止

子程序１：Ｓｕｂｇｒａｐｈ＿Ｍｉｎｉｎｇ（ＧＳ，Ｓ，ｓ）

（１）如果ｓ不是ｍｉｎ（ｓ）

（２）返回；

（３）把集合ｓ加入集合Ｓ中；

（４）添加一條邊，生成集合ｓ的孩子，即超模式；

（５）Ｅｎｕｍｅｒａｔｅ（ｓ）；

（６）依次遍歷集合ｓ的孩子ｃ

（７） 如果ｃ的支持度大于等于ｍｉｎＳｕｐ

（８）就把ｃ賦予ｓ中；

（９）Ｓｕｂｇｒａｐｈ＿Ｍｉｎｉｎｇ（ＧＳ，Ｓ，ｓ）

子程序２：Ｅｎｕｍｅｒａｔｅ（ｓ）

（１）依次遍歷ｓ的所有超圖ｇ

（２） 在圖ｇ中枚舉ｓ的擴(kuò)展，即孩子；

（３） 依次遍歷ｓ的孩子ｃ，同時(shí)ｃ是圖ｇ的子圖

把圖ｇ作為ｃ的超圖，鏈入ｃ的超圖鏈表中；

（４） 如果圖ｇ覆蓋了ｓ的所有孩子，ｂｒｅａｋ；

細(xì)節(jié)流程見圖１。

３ 實(shí)驗(yàn)

程序在ＶＣ６．０[５]環(huán)境下開發(fā)。運(yùn)行環(huán)境如下：Ｍｉｃｒｏｓｏｆｔ Ｗｉｎｄｏｗｓ ＸＰ Ｐｒｏｆｅｓｓｉｏｎａｌ 版本２００２ Ｓｅｒｖｉｃｅ Ｐａｃｋ ３，ＡＭＤ Ａｔｈｌｏｎ（ｔｍ）６４ Ｘ２ Ｄｕａｌ Ｃｏｒｅ Ｐｒｏｃｅｓｓｏｒ ４２００＋ ２．２０ ＧＨｚ，１．００ＧＢ的內(nèi)存，８０ＧＢ的硬盤。實(shí)驗(yàn)結(jié)果顯示：隨著支持度的加大，頻繁子圖數(shù)目在減小，最大的頻繁子圖規(guī)模在減小。如圖２所示。

以下關(guān)于Ｃｈｅｍｉｃａｌ＿３４０，內(nèi)含３４０個(gè)連通圖，每個(gè)圖規(guī)模不一，以下為ｍｉｎＳｕｐ＝１５的測試數(shù)據(jù)。

４ 結(jié)束語

本文研究了頻繁子圖挖掘問題，設(shè)計(jì)并實(shí)現(xiàn)了ｇＳｐａｎ算法進(jìn)行頻繁子圖挖掘。實(shí)驗(yàn)結(jié)果表明：ｇＳｐａｎ算法是一種高效的頻繁子圖挖掘算法。

參考文獻(xiàn)：

[１] ＹＡＮ Ｘｉｆｅｎｇ，ＨＡＮ Ｊｉａｗｅｉ． ｇＳｐａｎ：Ｇｒａｐｈ－Ｂａｓｅｄ ｓｕｂｓｔｒｕｃｔｕｒｅ ｐ－

ａｔｔｅｒｎ ｍｉｎｉｎｇ[Ｒ]． Ｍａｄｒｉｄ：Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ＩＣ－

ＤＭ，２００２．

[２] ＨＡＮ Ｊｉａｗｅｉ，ＰＥＩ Ｊｉａｎ，ＹＩＮ Ｙｉｗｅｎ．Ｍｉｎｉｎｇ ｆｒｅｑｕｅｎｔ ｐａｔｔｅｒｎｓ ｗｉｔｈｏｕｔ

ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｔｉｏｎ[Ｒ] ． Ｃａｎａｄａ ：Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｉｎｇ Ｓｃｉｅｎｃｅ， Ｓ－

ｉｍｏｎ Ｆｒａｓｅｒ Ｕｎｉｖｅｒｓｉｔｙ， ＳＩＧＭＯＤ，２０００．

[３] ＫＵＲＡＭＯＣＨＩ Ｍ，ＫＡＲＹＰＩＳ Ｇ． Ａｎ ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｉｓ－

ｃｏｖｅｒｉｎｇ ｆｒｅｑｕｅｎｔ ｓｕｂｇｒａｐｈｓ[Ｒ]． ＵＳＡ：Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ

Ｓｃｉｅｎｃｅ／Ａｒｍｙ ＨＰＣ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍｉｎｎｅｓｏｔａ，

Ｉｎ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００２．

[４] ＡＧＲＡＷＡＬ Ｒ，ＳＲＩＫＡＮＴ Ｒ． Ｆａｓｔ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｍｉｎｉｎｇ ａｓｓｏｃｉ－

ａｔｉｏｎ ｒｕｌｅｓ[Ｒ]． Ｃａｌｉｆｏｒｎｉａ ：ＩＢＭ Ａｌｍａｄｅｎ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ，ＶＬＤＢ，

１９９４．

[５] 楊永國． Ｖｉｓｕａｌ Ｃ＋＋ ６．０開發(fā)技巧與實(shí)例教程[Ｍ]． 北京：清華大學(xué)

出版社，２００４：２３－４５．

[６] ＪＡＨＮ Ｋ，ＫＲＡＭＥＲ Ｓ． Ｏｐｔｉｍｉｚｉｎｇ ｇＳｐａｎ ｆｏｒ ｍｏｌｅｃｕｌａｒ ｄａｔａｓｅｔｓ

[Ｒ]． Ｇｅｒｍａｎｙ：Ｔｅｃｈｎｉｓｃｈｅ Ｕｎｉｖｅｒｓｉｔｔ Ｍüｎｃｈｅｎ， Ｌｕｄｗｉｇ－Ｍａｘｉｍ－

ｉｌｉａｎｓ－Ｕｎｉｖｅｒｓｉｔｔ Ｍüｎｃｈｅｎ．

[７] ＢＯＲＧＥＬＴ Ｃ，ＭＥＩＮＬ Ｔ，ＢＥＲＴＨＯＬＤ Ｍ． Ａｄｖａｎｃｅｄ ｐｒｕｎｉｎｇ ｓｔ－

ｒａｔｅｇｉｅｓ ｔｏ ｓｐｅｅｄ ｕｐ ｃｌｏｓｅｄ ｍｏｌｅｃｕｌａｒ ｆｒａｇｍｅｎｔｓ[Ｒ]． ＵＳＡ：Ｐｒｏｃ．

ＩＥＥＥ Ｃｏｎｆ．ｏｎ Ｓｙｓｔｅｍｓ，Ｍａｎ ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ，２００４．

[８] ＨＡＮ Ｊｉａｗｅｉ，ＫＡＭＢＥＲ Ｍ． Ｄａｔａ ｍｉｎｉｎｇ ｃｏｎｃｅｐｔｓ ａｎｄ ｔｅｃｈｎｉｑｕ－

ｅｓ[Ｍ]． Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ． 北京：機(jī)械工業(yè)出版社，２００６：２２６－２３３，

５３５－５５４．

[９] ＨＡＮ Ｊｉａｗｅｉ，ＫＡＭＢＥＲ Ｍ著． 數(shù)據(jù)挖掘概念與技術(shù)[Ｍ]． 范明，

孟小峰，譯． 北京：機(jī)械工業(yè)出版社，２００７：１４６－１４９，３５１－３６１．

[１０] 嚴(yán)蔚敏，吳偉民． 數(shù)據(jù)結(jié)構(gòu)（Ｃ語言版）[Ｍ]． 北京：清華大學(xué)出版社，

２００５：４６－７２．

[１１] 許榮斌，謝瑩，吳建國． 基于化合物庫測試的ｇＳｐａｎ算法[Ｒ]． 合

肥：安徽大學(xué)，計(jì)算智能與信號處理教育部重點(diǎn)實(shí)驗(yàn)室，２００７．