基于圖結(jié)構(gòu)挖掘算法的研究與應(yīng)用.pdf

1、面對著迅速增長的數(shù)據(jù)信息量,人們受到“信息爆炸”的巨大壓力的同時(shí)又陷入“數(shù)據(jù)太多,知識太少”的窘境。數(shù)據(jù)挖掘技術(shù)的產(chǎn)生與發(fā)展為人們擺脫這種困境提供了強(qiáng)有力的手段。數(shù)據(jù)挖掘本質(zhì)上來說是讓數(shù)據(jù)自己說明自身的價(jià)值,即是按照既定的業(yè)務(wù)目標(biāo),對大量的企業(yè)數(shù)據(jù)進(jìn)行探索、揭示隱藏其中的規(guī)律性并進(jìn)一步將之模型化的先進(jìn)、有效的方法。在整個(gè)數(shù)據(jù)挖掘的研究中,算法的研究占有特別重要的地位。一方面,數(shù)據(jù)挖掘面對的是大數(shù)據(jù)集(稱海量數(shù)據(jù)),因此算法的效率將對其應(yīng)

2、用起關(guān)鍵的作用;另一方面,我們面對的計(jì)算機(jī)系統(tǒng)在其性能上遠(yuǎn)遠(yuǎn)不能滿足對大數(shù)據(jù)集進(jìn)行處理的要求,因此我們必須研究和改進(jìn)現(xiàn)有的算法使其有更廣泛的應(yīng)用前景。再者,由于近年來生物信息技術(shù)、網(wǎng)絡(luò)開發(fā)技術(shù)的迅速發(fā)展,越來越多的人們意識到用圖能更好地描述事物之間的復(fù)雜關(guān)系,進(jìn)而在此基礎(chǔ)上進(jìn)行挖掘可以得到更多的有用信息。鑒于此,本文選擇了對圖結(jié)構(gòu)數(shù)據(jù)挖掘算法進(jìn)行研究。本文對數(shù)據(jù)挖掘中的圖結(jié)構(gòu)挖掘算法作了比較深入的研究。JiaweiHan等人針對類Apr

3、iori算法(如FSG、AGM、AcGM)連接和剪枝耗時(shí)很大的缺點(diǎn),提出了gSpan算法和Close Graph算法。gSpan算法和CloseGraph算法相對于類Apriori算法是比較好的算法,它們通過引入新的方法和概念——DFS Lexilographic Order、最小DFScode和最右擴(kuò)展,使得無需按Apriori算法的思想而是直接生成頻繁子圖,大大提高了算法的效率。但它們也存在以下問題:挖掘結(jié)果集中考慮了圖的標(biāo)記,即具

4、有不同標(biāo)記的圖被認(rèn)為是不同的圖。而很多情況下,標(biāo)記不同的圖具有相同的結(jié)構(gòu)?；谇叭说难芯?本文提出了兩個(gè)新的算法——極大完全子圖挖掘算法(MaxcodeFMCG算法)和頻繁子圖結(jié)構(gòu)挖掘算法(FSA算法),并將Maxcode FMCG算法與已有的頻繁模式挖掘算法FP-Growth算法相結(jié)合,產(chǎn)生了一種基于圖結(jié)構(gòu)的頻繁模式挖掘算法(Maxcode FP-Tree算法)。Maxcode FP-Tree算法的主要優(yōu)點(diǎn)是解決了FP-Growth算