不確定圖數(shù)據(jù)庫上基于預(yù)裁剪的頻繁子圖挖掘.pdf

1、隨著信息技術(shù)的發(fā)展，各類領(lǐng)域的學(xué)者都開始使用圖來表示數(shù)據(jù)單元之間錯綜復(fù)雜的對應(yīng)關(guān)系。圖數(shù)據(jù)中包含了大量信息，因而如何從圖數(shù)據(jù)中挖掘數(shù)據(jù)對象間的各種知識具有重要學(xué)術(shù)價值和實際意義。在圖挖掘技術(shù)中，對頻繁子圖進(jìn)行挖掘是該門類的研究熱點，由于頻繁子圖包含了很多有代表性的信息，因而得到了廣泛的重視和研究。然而在許多領(lǐng)域，由于理論及實際技術(shù)的限制，獲得的數(shù)據(jù)通常帶有不確定性。不確定圖數(shù)據(jù)是指包含不確定性的圖數(shù)據(jù)。在不確定圖數(shù)據(jù)中對頻繁子圖進(jìn)行挖掘

2、同樣具有理論和實際意義。
　　MUSE算法是第一個在不確定圖數(shù)據(jù)庫中進(jìn)行頻繁子圖挖掘的高效算法，其通過對子圖同構(gòu)概率進(jìn)行近似計算，成功將子圖同構(gòu)概率計算復(fù)雜度由指數(shù)級別降為線性級別。然而在不確定圖數(shù)據(jù)庫規(guī)模較大時其計算效率仍然較低。在頻繁子圖的挖掘中很重要的一環(huán)是計算子圖同構(gòu)概率，然而計算子圖同構(gòu)概率時需求解候選子圖在不確定圖中的所有嵌入，為此構(gòu)建基于不確定圖數(shù)據(jù)庫的不確定圖邊索引，使得可以在不進(jìn)行子圖同構(gòu)測試的同時快速求解候選子

3、圖在不確定圖中的近似嵌入集，同時結(jié)合算法流程與求解特征引入了不考慮子圖模式重合關(guān)系的子圖同構(gòu)概率近似計算方法。最后將近似嵌入集合與文中的子圖同構(gòu)概率近似計算方法相結(jié)合形成了新的混合求解預(yù)剪枝策略，并運(yùn)用到MUSE算法中組成了新的MUSE+算法。
　　在相同數(shù)據(jù)集合下，分別用MUSE算法與MUSE+算法進(jìn)行求解并進(jìn)行求解時間對比。實驗結(jié)果表明，在大部分情況下，使用混合求解策略的MUSE+算法性能得到了提高且隨著支持度閾值的提高性能優(yōu)