欢迎来到天天文库
浏览记录
ID:51199829
大小:6.10 MB
页数:75页
时间:2020-03-20
《图数据库频繁模式挖掘关键技术研究.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
此文档下载收益归作者所有