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

《基于圖結(jié)構(gòu)挖掘算法的研究與應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、MasterDissertationofChongqingUniversityResearchandApplicationofMiningGraphStructureAlgorithmMasterCandidate:KangYanrongSupervisor:AssociateProf.GuopingMajor:ComputerApplicationtechnologyCollegeofComputerScienceChongqingUniversityOctober2005摘要面對著迅速增長的數(shù)據(jù)信息量，人們受到“信息爆炸，啲巨大壓力的同時乂陷入“數(shù)據(jù)太多，知識太

2、少''的窘境。數(shù)據(jù)挖掘技術(shù)的產(chǎn)生與發(fā)展為人們擺脫這種困境捉供了強冇力的手段。數(shù)據(jù)挖掘本質(zhì)上來說是讓數(shù)據(jù)自己說明自身的價值，即是按照既定的業(yè)務(wù)ri標，對大量的企業(yè)數(shù)據(jù)進行探索、揭示隱藏其小的規(guī)律性并進一步將z模型化的先進、冇效的方法。在整個數(shù)據(jù)挖掘的研究中，算法的研究占有特別重要的地位。一方面，數(shù)據(jù)挖掘面對的是大數(shù)據(jù)集（稱海量數(shù)據(jù)），因此算法的效率將對其應(yīng)用起關(guān)鍵的作用；另一方面，我們面對的計算機系統(tǒng)在其性能上遠遠不能滿足對大數(shù)據(jù)集進行處理的要求，因此我們必須研究和改進現(xiàn)有的算法使其有更廣泛的應(yīng)用而景。再者，由于近年來生物信息技術(shù)、網(wǎng)絡(luò)開發(fā)技術(shù)的迅速發(fā)展，越來越多的人

3、們意識到用圖能更好地描述事物之間的復(fù)雜關(guān)系，進而在此基礎(chǔ)上進行挖掘可以得到更多的有用信息。鑒于此，本文選擇了對圖結(jié)構(gòu)數(shù)據(jù)挖掘算法進行研究。木文對數(shù)據(jù)挖掘中的圖結(jié)構(gòu)挖掘算法作了比較深入的研究。JiaweiHan等人針對類Apriori算法（如FSG、AGM、AcGM）連接和剪枝耗吋很大的缺點，提出了gSpan算法和CloseGraph算法。gSpan算法和CloseGraph算法相對于類Apriori算法是比較好的算法，它們通過引入新的方法和概念DFSLexilographicOrder、最小DFScode和最右擴展，使得無需按Apriori算法的思想而是直接生成頻繁

4、子圖，大大提高了算法的效率。但它們也存在以下問題：挖掘結(jié)果集中考慮了圖的標記，即具有不同標記的圖被認為是不同的圖。而很多情況下，標記不同的圖具有相同的結(jié)構(gòu)?；谇叭说难芯浚疚奶釋缌藘蓚€新的算法——極大完全子圖挖掘算法（MaxcodeFMCG算法）和頻繁子圖結(jié)構(gòu)挖掘算法（FSA算法），并將MaxcodeFMCG算法與已有的頻繁模式挖掘算法FP-Growth算法相結(jié)合，產(chǎn)生了一種基于圖結(jié)構(gòu)的頻繁模式挖掘算法（MaxcodeFP-Tree算法）。MaxcodeFP-Tree算法的主要優(yōu)點是解決了FP-Growth算法中存在的內(nèi)存不足的問題。FSA算法則主要是解決了以往的

5、頻繁子圖挖掘算法中存在的“標記不同但結(jié)構(gòu)相同的圖被認為是不同的''的問題，有利于對結(jié)構(gòu)挖掘進行更深入的研究。最后，本文對gSpan算法和FSA算法的頻繁子圖情況進行了比較，通過大量的實驗結(jié)果表明，F(xiàn)SA算法在一定程度上優(yōu)于gSpan算法。關(guān)鍵詞：數(shù)據(jù)挖掘，圖結(jié)構(gòu)挖掘，極大完全了圖，頻繁了圖，頻繁了圖結(jié)構(gòu)ABSTRACTInfaceofthesoaringamountofinformation,peopleareintimidatedby"DataBomb"whiletheyfallintothefearof"shortageofknowledge^.KDDconin

6、gfortheneedhasbecomeoneofthestrongestweaponsthatpeoplecanusetosolvetheparadoxicalproblem,DataMiningisthenontrivialprocessofidentifyingvalid,novel,potentiallyuseful,andultimatelyunderstandablepatternsindata.AlgorithmisthekeypartinKDD,forthisreasontoresearchforefficient.Ononehand,DataMin

7、ingisusedtoprocessLargedatabase,andsotheefficiencyofalgorithmisthemostimportant;OntheotherhandthecomputerinuseisnotsatisfyingtotheprocessingofLaragdatabase.Third,withthefastdevelopmentofbioinfonnaticsandwebexploration,moreandmorepeoplerealizethatgraphcandescribethecomplexedrelationsb