图数据库频繁模式挖掘关键技术研究.pdf

《图数据库频繁模式挖掘关键技术研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中文接要中文摘要从图数据库挖掘频繁模式在化学信息学、计算生物学、WEB信息管理、社会网络分析等领域有着广泛的应用。因此本文重点研究了从图数据库中挖掘频繁模式的关键技术，并针对频繁模式挖掘所面临的效率瓶颈、结果集庞大以及高复杂、冗余性等问题，在本文中提出了基于随机化挖掘极大频繁子图的方法RMPM、挖掘具有代表性频繁子图的算法FRSM、InRSM。本文的主要研究成果有：1．随机化方法在挖掘海量数据集时非常高效，但是因为随机性，会造成结果的重复发现，势必造成很多重复和无用的子图同构计算。本文提出的基于随机化挖掘极大频繁子图的方法RMPM，通过对已挖掘到的结果建立索引，提高了随机算法的效率。在真实和模

2、拟数据集上的实验结果也证实了RMPM算法是高效、可伸缩的。本文提出的随机算法的思想是通用的，可以应用于各种各样的模式，比如自由树、项集等，在真实数据集上挖掘极大频繁自由树的实验结果也证实了RMPM算法是通用的。2．为了压缩频繁模式集合，挖掘出更小、更有代表性的频繁模式集合，本文提出了挖掘具有代表性频繁模式的算法FRSM，算法第一步采用本文提出的效率更高的RMPM算法作为频繁模式挖掘算法，第二步在RMPM结果集上聚类，在聚类时，综合考虑频繁子图在事务空间上的相似性和模式空间上的相似性，使得聚类的质量更好，获得的模式更具代表性。在大量的实验上也证明了FRSM算法所得到的代表模式集合比不考虑或只考虑

3、模式在事务空间上的相似性的聚类所得到的模式更具代表性。3．本文也提出直接从图数据库中挖掘代表模式集合的算法InRSM，它比两步算法FRSM更加高效，InRSM算法同样考虑了模式在事务空间上和模式空间上的相似性，大量的实验也证明了InRSM算法是高效的和可伸缩的。关键词：数据挖掘；频繁子图；极大频繁子图；代表性模式黑龙江大学硕士学位论文ABSTRACTMiningfrequentpatternsfromthegraphdatabasehaswiderangeofapplicationssuchasCheminformatics，ComputationalBiology,WEBinformatio

4、nmanagement，Socialnetworkanalysis．Inthispaper,wefocusonthetechniquesoffindingfrequentsubgraphsfromgraphdatabasesinordertoaddresstheproblem，suchasscalability,theexponentialnumberoffrequentpatterns，highcomplex，redundant，etc．WeintroducearandomizedapproachRMPMforminingmaximalfrequentpatterns，andproposet

5、woalgorithms，FRSMandInRSMwhichminesasummaryrepresentationofthesetoffrequentgraphs．Themaincontributionsofthispaperareasfollows：1．Traditionalornaiverandomizedalgorithmshaveahigheffectivenessinfrequentpatternsmining，buttheywillobtainthesamepatternmanytimes，therebyinevitablycausesmultipleanduselesssubgr

6、aphisomorphismcomputing．Inordertoimprovetheefficiencyoftheexistingrandomizedalgorithms，RMPMcanusethepatternsminedalreadytogeneratemaximalfrequentsubgraphs．Theextensiveexperimentsonrealandsyntheticdatasetsverifytheeffectivenessandefficiencyofouralgorithms；experimentalsoshowsthatRMPMoffersverygoodscal

7、abilitytolargegraphdatabases．Therandomizedalgorithmsthatweproposesisgenericandisequallyapplicabletodifferentkindsofpatterns，suchasfreetrees，itemset，etc．Theextensiveexperimentsofminingmaximalfrequentfr