基于部分標(biāo)記圖的頻繁子圖挖掘算法研究.pdf

1、近年來，數(shù)據(jù)挖掘在科學(xué)研究和實(shí)際應(yīng)用領(lǐng)域都取得了巨大的成功。隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展和實(shí)際應(yīng)用的需要，數(shù)據(jù)挖掘的對(duì)象逐漸由傳統(tǒng)的項(xiàng)目集數(shù)據(jù)擴(kuò)展到了結(jié)構(gòu)化的數(shù)據(jù)，如路徑，樹，圖等復(fù)雜結(jié)構(gòu)，因此，圖形挖掘成為了當(dāng)前數(shù)據(jù)挖掘研究領(lǐng)域的熱點(diǎn)。
　　 和傳統(tǒng)數(shù)據(jù)集挖掘中頻繁項(xiàng)目集是挖掘任務(wù)的基礎(chǔ)一樣，圖形挖掘任務(wù)中，頻繁子圖(即圖集數(shù)據(jù)庫中最頻繁的子結(jié)構(gòu))是圖形挖掘的基礎(chǔ)。但是頻繁子圖挖掘的復(fù)雜性要遠(yuǎn)遠(yuǎn)大于項(xiàng)目集挖掘，因?yàn)轭l繁子圖挖掘的核心

2、問題是同構(gòu)測(cè)試，而圖的同構(gòu)測(cè)試已經(jīng)被證明是一個(gè)NP完全問題。隨著研究的深入，迄今為止人們已經(jīng)提出了許多高效和可伸縮的頻繁子圖挖掘算法，如gSpan，Gaston等.
　　 但是，目前的算法大多都是對(duì)有標(biāo)記圖進(jìn)行數(shù)據(jù)挖掘，對(duì)部分標(biāo)記圖要么無法挖掘，要么沒有對(duì)部分標(biāo)記圖做特定優(yōu)化處理，為此，本文提出了一種基于部分標(biāo)記圖的頻繁子圖挖掘算法：PLSG((P-)artially(L-)abeled based(S-)tructural(G

3、-)raphMining)。PLSG算法提出了部分標(biāo)記圖的精確匹配和模糊匹配的概念，并據(jù)此對(duì)部分標(biāo)記圖進(jìn)行預(yù)處理，首先將部分標(biāo)記圖轉(zhuǎn)換為全部標(biāo)記圖，再對(duì)其進(jìn)行頻繁子圖挖掘。為了達(dá)到算法的高效性和可伸縮性，PLSG使用了很多優(yōu)化方法，諸如用規(guī)范化標(biāo)記避免子圖同構(gòu)測(cè)試、采用邊→路徑→樹→圖的候選子圖生成策略達(dá)到盡早剪枝等。
　　 本文通過大量的實(shí)驗(yàn)結(jié)果表明：(1)對(duì)部分標(biāo)記圖挖掘時(shí)，無論是精確匹配還是模糊匹配，PLSG都能對(duì)部分標(biāo)記