一種高效的不確定圖數據庫上頻繁子圖模式挖掘算法.pdf

1、隨著信息技術日新月異的的發(fā)展變化,在越來越多的領域中,研究者開始使用圖這種數據結構來表示和存儲數據對象之間的關系。這些數據被稱為圖數據。圖數據中包含了大量的我們希望獲得的知識和信息。如何從圖數據中挖掘數據對象間的結構特征、形成規(guī)律及存在模式等知識,具有重要學術價值和實際意義。
　　在許多領域的實際引用中,由于數據獲取技術的客觀局限、數據的不精確性等原因,獲得的數據天然的帶有不確定性。這種帶有不確定性的圖數據,稱之為不確定圖數據,例

2、如生物信息學中的蛋白質相互作用網絡,無線傳感器網絡的節(jié)點間的拓撲結構等等。
　　在圖挖掘技術中,頻繁子圖模式挖掘是非常重要且被廣泛研究應用的一類。圖數據中挖掘頻繁子圖模式可以獲得很多有價值的信息,在諸如蛋白質相互作用網絡研究,無線傳感器網絡研究等領域中得到了廣泛的重視和研究。而如何在圖數據庫中進行頻繁子圖模式挖掘,得到了越來越多的關注。圖數據庫中挖掘頻繁子圖模式的難點之處在于,不僅存在著海量的可能子圖模式需要檢驗,而且還需要做極大

3、數量的子圖同構性測試來判別圖中是否蘊含一個給定的模式。而若處理的圖數據帶有不確定性,則第二個難點更為突出。
　　本文綜合運用數據挖掘的相關理論、概率論的基本知識和算法學,以最小化不確定圖數據庫中挖掘頻繁子圖模式算法運行的時間開銷和空間開銷為目的,研究期望語義下的不確定圖數據庫中頻繁子圖模式挖掘算法。主要的研究成果提供一個在不確定圖數據庫中能夠有效挖掘頻繁子圖模式的算法MUSIC(MiningUncertainSubgraphPat

4、ternsWithIndexofConnectivityandEdge),該算法運用建立在不確定圖數據庫上的UG索引(UncertainGraph)來減少為了挖掘頻繁子圖模式所需要的比較次數。MUSIC算法根據apriori性質可以有效地枚舉可能的子圖模式,而建立在不確定圖數據庫上的UG索引則可被用來減少為了計算每個候選模式的期望支持度所進行的比較次數。本文還提供額外的基于待檢驗蘊含圖調度和剪枝的優(yōu)化策略,這樣可以有效的提高算法的性能。