基于圖結構挖掘算法的研究與應用.pdf

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

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

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

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