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

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

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

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