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

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

2、如生物信息學(xué)中的蛋白質(zhì)相互作用網(wǎng)絡(luò),無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)間的拓?fù)浣Y(jié)構(gòu)等等。
　　在圖挖掘技術(shù)中,頻繁子圖模式挖掘是非常重要且被廣泛研究應(yīng)用的一類。圖數(shù)據(jù)中挖掘頻繁子圖模式可以獲得很多有價(jià)值的信息,在諸如蛋白質(zhì)相互作用網(wǎng)絡(luò)研究,無線傳感器網(wǎng)絡(luò)研究等領(lǐng)域中得到了廣泛的重視和研究。而如何在圖數(shù)據(jù)庫中進(jìn)行頻繁子圖模式挖掘,得到了越來越多的關(guān)注。圖數(shù)據(jù)庫中挖掘頻繁子圖模式的難點(diǎn)之處在于,不僅存在著海量的可能子圖模式需要檢驗(yàn),而且還需要做極大

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

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