基于不確定圖數(shù)據(jù)頻繁挖掘的研究.pdf

1、21世紀是一個信息至上的時代,各行各業(yè)每分每秒都在追趕著信息的腳步,如何從海量的信息中發(fā)現(xiàn)有價值的信息是一大挑戰(zhàn)。圖數(shù)據(jù)挖掘由于圖數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢深受廣大研究愛好者的青睞,被廣泛應用于各行各業(yè)中,如生物領域、化學領域、社交網(wǎng)絡領域等。如何從圖數(shù)據(jù)中發(fā)現(xiàn)有趣的模式已成為數(shù)據(jù)挖掘領域的一個重要研究方向。
　　本文在研究了圖挖掘的應用背景、基本原理與國內(nèi)外關(guān)于圖挖掘的現(xiàn)狀的基礎之上,分析了圖挖掘中還存在的一些問題,針對目前的幾個不確定頻繁

2、子圖挖掘算法的不足之處,提出了相應的改進算法。本文的主要研究成果如下:
　　(1)針對挖掘不確定頻繁子圖的經(jīng)典MUSE算法存在期望支持度計算消耗大、時間效率不夠高等問題提出了一種基于邊支持度樹的寬度優(yōu)先搜索算法EBFS。它首先用改進過的gSpan算法進行不確定的子圖數(shù)據(jù)預處理,然后將處理過后的數(shù)據(jù)進行劃分,并在劃分的子塊中構(gòu)建支持度樹,最后對支持度樹采用寬度優(yōu)先搜索算法挖掘頻繁子圖,實驗結(jié)果表明,EBFS算法在大數(shù)據(jù)的情況下顯得效

3、率更高。
　　(2)針對挖掘極大不確定頻繁子圖的RAKING算法存在時間效率與空間效率不夠高的問題提出了UDMFS算法。UDMFS算法本算法是基于EBFS的,整個算法由兩個階段構(gòu)成:第一階段是通過EBFS算法產(chǎn)生不確定的頻繁子圖集;第二階段是從頻繁子圖集中按最右規(guī)則擴展,產(chǎn)生一個新的候選極大頻繁子圖,再通過計算該候選子圖的期望支持度與判斷其能否繼續(xù)最右規(guī)則擴展,將產(chǎn)生一個極大頻繁子圖,實驗結(jié)果表明,UDMFS算法在挖掘極大頻繁子圖