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

王文龍　李建中

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

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

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

0引言

在不確定圖數據庫中挖掘頻繁子圖模式是一個具有挑戰性的問題。在期望語義下，檢驗子圖模式是否頻繁的標準由其在不確定圖數據庫的所有蘊含圖數據庫中的支持度的期望值來評價，稱之為期望支持度。

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

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

1數據模型和問題定義