一種有效的在不確定圖數(shù)據(jù)庫中挖掘頻繁子圖模式的MUSIC算法

王文龍　李建中

摘要：近年來，如何在不確定圖數(shù)據(jù)庫中挖掘頻繁子圖模式得到了越來越多的關(guān)注。該問題的主要難點(diǎn)在于，不僅存在著海量的可能子圖模式需要檢驗(yàn)，而且還需要做大數(shù)量的子圖同構(gòu)性測試來判別圖中是否蘊(yùn)含一個(gè)給定的模式。傳統(tǒng)的算法是利用近似算法計(jì)算子圖模式的期望支持度，但計(jì)算開銷仍然十分巨大。為此提供一個(gè)基于建立在不確定數(shù)據(jù)庫上的索引的算法。算法首先根據(jù)apriori性質(zhì)枚舉所有可能的首選子圖模式，然后利用索引對候選子圖模式空間進(jìn)行剪枝以減少子圖同構(gòu)性檢驗(yàn)從而減少期望支持度的計(jì)算開銷。通過在一個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)顯示本算法可以有效地在不確定圖數(shù)據(jù)庫中挖掘頻繁子圖模式。

關(guān)鍵詞：不確定圖； 頻繁子圖模式； 期望支持度； 不確定圖索引

中圖分類號：TP311.13 [KG*2]文獻(xiàn)標(biāo)識碼：A[KG*2][HT5”H]文章編號：2095-2163（2013）05-0020-04

0引言

在不確定圖數(shù)據(jù)庫中挖掘頻繁子圖模式是一個(gè)具有挑戰(zhàn)性的問題。在期望語義下，檢驗(yàn)子圖模式是否頻繁的標(biāo)準(zhǔn)由其在不確定圖數(shù)據(jù)庫的所有蘊(yùn)含圖數(shù)據(jù)庫中的支持度的期望值來評價(jià)，稱之為期望支持度。

在文獻(xiàn)[1]中通過將問題轉(zhuǎn)化為DNF計(jì)數(shù)問題的一個(gè)實(shí)例，給出了一個(gè)計(jì)算子圖模式的期望支持度的近似算法。雖然該方法可以減少針對單一不確定圖的計(jì)算開銷，但整體開銷仍然非常巨大。文獻(xiàn)[2，3]分別給出了一個(gè)有效的子圖同構(gòu)性檢驗(yàn)算法，但由于本問題巨大的子圖同構(gòu)性檢驗(yàn)次數(shù)，并不能有效降低挖掘所需的時(shí)間。

本文提出了MUSIC算法，來解決在不確定圖數(shù)據(jù)庫中挖掘頻繁子圖模式的問題。算法通過索引來減少判斷支持度的計(jì)算開銷。文中的實(shí)驗(yàn)顯示了MUSIC算法的有效性。

1數(shù)據(jù)模型和問題定義