基于图结构挖掘算法的研究与应用

《基于图结构挖掘算法的研究与应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、MasterDissertationofChongqingUniversityResearchandApplicationofMiningGraphStructureAlgorithmMasterCandidate:KangYanrongSupervisor:AssociateProf.GuopingMajor:ComputerApplicationtechnologyCollegeofComputerScienceChongqingUniversityOctober2005摘要面对着迅速增长的数据信息量，人们受到“信息爆炸，啲巨大压力的同时乂陷入“数据太多，知识太

2、少''的窘境。数据挖掘技术的产生与发展为人们摆脱这种困境捉供了强冇力的手段。数据挖掘本质上来说是让数据自己说明自身的价值，即是按照既定的业务ri标，对大量的企业数据进行探索、揭示隐藏其小的规律性并进一步将z模型化的先进、冇效的方法。在整个数据挖掘的研究中，算法的研究占有特别重要的地位。一方面，数据挖掘面对的是大数据集（称海量数据），因此算法的效率将对其应用起关键的作用；另一方面，我们面对的计算机系统在其性能上远远不能满足对大数据集进行处理的要求，因此我们必须研究和改进现有的算法使其有更广泛的应用而景。再者，由于近年来生物信息技术、网络开发技术的迅速发展，越来越多的人

3、们意识到用图能更好地描述事物之间的复杂关系，进而在此基础上进行挖掘可以得到更多的有用信息。鉴于此，本文选择了对图结构数据挖掘算法进行研究。木文对数据挖掘中的图结构挖掘算法作了比较深入的研究。JiaweiHan等人针对类Apriori算法（如FSG、AGM、AcGM）连接和剪枝耗吋很大的缺点，提出了gSpan算法和CloseGraph算法。gSpan算法和CloseGraph算法相对于类Apriori算法是比较好的算法，它们通过引入新的方法和概念DFSLexilographicOrder、最小DFScode和最右扩展，使得无需按Apriori算法的思想而是直接生成频繁

4、子图，大大提高了算法的效率。但它们也存在以下问题：挖掘结果集中考虑了图的标记，即具有不同标记的图被认为是不同的图。而很多情况下，标记不同的图具有相同的结构。基于前人的研究，本文提岀了两个新的算法——极大完全子图挖掘算法（MaxcodeFMCG算法）和频繁子图结构挖掘算法（FSA算法），并将MaxcodeFMCG算法与已有的频繁模式挖掘算法FP-Growth算法相结合，产生了一种基于图结构的频繁模式挖掘算法（MaxcodeFP-Tree算法）。MaxcodeFP-Tree算法的主要优点是解决了FP-Growth算法中存在的内存不足的问题。FSA算法则主要是解决了以往的

5、频繁子图挖掘算法中存在的“标记不同但结构相同的图被认为是不同的''的问题，有利于对结构挖掘进行更深入的研究。最后，本文对gSpan算法和FSA算法的频繁子图情况进行了比较，通过大量的实验结果表明，FSA算法在一定程度上优于gSpan算法。关键词：数据挖掘，图结构挖掘，极大完全了图，频繁了图，频繁了图结构ABSTRACTInfaceofthesoaringamountofinformation,peopleareintimidatedby"DataBomb"whiletheyfallintothefearof"shortageofknowledge^.KDDconin

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

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