论文最大频繁子图挖掘算法DMFS，本文是算法方面论文范本和DMFS和算法和挖掘相关函授毕业论文范文.
最大频繁子图挖掘算法DMFS
柴 然,刘媛媛,郭彦颖
（沧州医学高等专科学校,河北 沧州 061001）
［摘 要］最大频繁子图挖掘得到的结果数量少而且不会丢失信息,有益于对结果的理解和应用.为了避免挖掘所有频繁子图,降低挖掘难度,本文应用决策树挖掘最大频繁子图.挖掘过程中,首先构造决策树,然后对决策树进行剪枝得到最大频繁子图,最后通过实验验证算法的可行性以及正确性.
［关键词］数据；挖掘；最大频繁子图；决策树；子图同构
doi：10.3969/j.issn.1673 - 0194.2017.04.099
［中图分类号］TP301.6 ［文献标识码］A ［文章编号］1673-0194（2017）04-0-02
基于图的数据挖掘提出时间不长,但图论作为数学的研究领域已经有了很长的历史,所以频繁子图挖掘得以很好地发展.但是频繁子图挖掘得到的结果数量巨大,影响着对结果的理解、应用以及分析工作.最大频繁子图包含了所有频繁子图,挖掘最大频繁子图可以保证信息的完整性,而且挖掘最大频繁子图可以得到少量结果从而节省了空间,简化了分析工作.基于此,可以将频繁子图挖掘转换为最大频繁子图挖掘.MARGIN算法和SPIN算法是经典的最大频繁子图挖掘算法,它们必须挖掘出所有的频繁子图,然后再挖掘最大频繁子图.虽然最大频繁子图挖掘得到的结果少了,但挖掘过程很复杂,难度很高.
针对最大频繁子图挖掘算法中存在的问题,本文提出新的最大频繁子图挖掘算法DMFS（Decision tree to Mining Maximal Frequent Subgraph）.DMFS算法利用决策树来挖掘最大频繁子图,首先构造决策树,其次对决策树进行剪枝（剪掉决策树中不频繁的节点）,最后通过剪枝后的决策树来得到最大频繁子图集合.
1
图挖掘相关概念
（1）标记图用五元组G等于(V,E,ΣV,ΣE,L)表示标记图,V是结点集,E是边集,ΣV,ΣE分别为结点标记和边标记的集合,L为V→ΣV,E→ΣE的映射.
（2）子图给定图G1等于(V1,E1,ΣV1,ΣE1,L1)和G2等于(V2,E2,ΣV2,ΣE2,L2),
G1为G2的子图当且仅当：
V1V2,E1E2
?u∈V1,L1(u)等于L2(u)
?(u,v)∈E1,L1(u,v)等于L2(u,v)
（3）同构如果图G1等于(V1,E1,ΣV1,ΣE1,L1)同构于图G2等于(V2,E2,ΣV2,
ΣE2,L2)当且仅当存在映射f：
?u∈V1,L1(u)等于L2(f(u))
?u,v∈V1,(u,v)∈E1则(f(u))∈E2
?(u,v)∈E1则L1(u,v)等于L2(f(u),f(v))
（4）子图同构若图G1子图同构于图G2,当且仅当在图G2中存在子图G2＇,使G2＇同构于图G1.
（5）支持度给定一个大小为n的图数据库D等于{G1,G2,…,Gn}
设
则g在图数据库D中的支持度sup(g,D)等于?(g,D)/n.
（6）频繁子图给定最小支持度minsup,如果图g的支持度sup(g,D)≥minsup则称图g为频繁子图.如果频繁子图g的任意超图均不频繁,则图g为最大频繁子图.
2 决策树
决策树是基于机器学习的数据挖掘技术,它形式简单,分类速度快,无需先验知识,而且由决策树表达的规则直观清晰.应用决策树计算支持度的想法来源于F算法,F算法存在不能正确计算出支持度的问题,本文通过改进决策树解决这个问题,具体改进如下.
①DMFS算法在构造决策树时不是采取每次增加一个顶点的方式,而是每次增加一条边.②F算法中将某节点的支持度计为其孩子节点的支持度的总和,忽略了决策树中会有很多重复的leaf node,所以必须改变支持度的计算方法.③结合经典MARGIN算法的剪枝策略,通过对决策树进行剪枝得到最大频繁子图.
2.1 构造决策树方法
（1）为了正确且简单地计算子图的支持度,对图集中的两个图进行编号.
（2）在构造决策树之前,首先找到图集中所有不同的结点标记,然后计算结点支持度生成两个集合,分别为频繁结点集和非频繁结点集,如果某结点标记的支持度为100%,则仅将该结点标记添加到决策树中第二层,将其作为根节点的孩子节点.
（3）从编号为1的图以每次添加一条边的方式构造图集的决策树.
2.2 构造决策树实例
假设图集中含有两个图,minsup等于100%,为图集构造决策树如下.①将图进行编号为G1、G2.②A、B、C均为频繁的结点标记,结点标记A的支持度为100%,将A添加到决策树的第二层,将其作为根节点的孩子节点.③现在从图G1的结点A开始构造它的决策树,与A关联的边有两条分别为（A,1,B）（A,2,C）,将表示这两条边的节点添加在决策书的第三层,作为A的孩子节点.与（A,1,B）关联的有两条边分别为（A,2,C）及（B,2,C）,通过扩展得到两个含有两条边的图,将其作为（A,1,B）的孩子添加到决策树的第四层,以同样的方式继续扩展图,构造出的决策树如图1所示.继续将G2添加到决策树中,同样从结点A开始构造,如果在当前的决策树中存在表示同一图的节点则不重复添加节点,图G1是图G2的超图则将表示图G2的节点作为自身的孩子节点,编号为G2.
3 DMFS算法
DMFS算法从决策树的倒数第二层依次向上判断,剪枝的原则为：①若节点v不频繁且其所有兄弟节点都不频繁,此时如果节点v的双亲节点u是频繁的,则删除以v和它的兄弟节点为根节点的决策树,使u成为叶子节点,不再判断u的双亲节点；②如果节点v是频繁的,例如图((A,1,B)(A,2,C)),则只删除以v的不频繁的兄弟节点,例如图((A,1,B)(B,2,C))的节点,为根节点的决策树,不再判断v的双亲；③对决策树进行剪枝后得到新的决策树,但在新的决策树中可能存在重复的叶子,或某些叶子节点同构,所以为了得到最大频繁子图集合还是需要进行子图同构判断.
对图1中的决策树进行剪枝后得到新的决策树如图2所示.
4
实验结果
模拟数据集由X.Yan 等人提供的数据模拟器进行模拟,不同类型的关系模拟为边标记.本文用数据模拟器产生图集时以参数D、E、V、L为基础,D为图集的大小,E、V分别为不同的边标记和结点标记的数量,L为最大频繁子图的平均大小.在这个实验中L由4变化到12,D等于1K,minsup等于2℅,E等于20,V等于20.即生成图的总数为1 000个,最大频繁子图的平均大小从4变化到12,不同的结点标记的数量和不同的边标记的数量均为20.
从图3可以看出,当L很小时DMFS算法与最大频繁子图挖掘算法MARGIN运行时间相差不是很明显,但随着L的增大,算法DMFS的优势越来越明显,且运行时间随挖掘得到的最大频繁子图的增大不断增长.通过理论和实验相结合,可知DMFS算法优于MARGIN算法.
5 结 语
本文提出了新的最大频繁子图挖掘算法DMFS,通过构造决策树并对其进行剪枝来得到最大频繁子图,减少了子图同构判断的次数,提高了算法的挖掘效率.DMFS算法采用的是自顶向下的挖掘思想,可以避免挖掘所有的频繁子图,降低挖掘难度.最后,实验验证了DMFS算法较经典的最大频繁子图挖掘算法MARGIN算法更高效.
主要参考文献
［1］王映龙,杨珺,周法国,等.加权最大频繁子图挖掘算法的研究［J］.计算机工程与应用,2009(20).
［2］Jiawei Han,Micheline Kamber.数据挖掘概念与技术［M］.范明,孟小峰,译.北京:机械工业出版社,2012.
［3］Abraham Silberschatz,Henry F Korth,S Sudarshan.数据库系统概念［M］.第6版.杨冬青,李红燕,唐世渭,译.北京:机械工业出版社,2012.
［4］邹兆年.不确定图数据挖掘［M］.哈尔滨:哈尔滨工业大学出版社,2013.
［5］谭浩强.C语言程序设计题解与上机指导［M］.北京:清华大学出版社,2000.
［6］陈晓,刘凤春,李建晶,等.一种新的自顶向下挖掘最大频繁子图的算法［J］.计算机工程与科学,2013(4).
［7］郭景峰,张伟,柴然.一种新的频繁子图挖掘算法［J］.计算机工程,2011(20).
［8］唐德权,吴绍兵,凌志刚.一种新的图聚类算法研究［J］.计算机应用与软件,2014(6).
综上资料，上述文章是关于DMFS和算法和挖掘方面的算法论文题目、论文提纲、算法论文开题报告、文献综述、参考文献的相关大学硕士和本科毕业论文.
参考文献：
1、 弱关联冗余环境下的挖掘算法 蔡柳萍(广东技术师范学院天河学院信息与传媒学院,广东 广州 510540)摘 要在弱关联冗余环境下,开展的挖掘算法应用需要考虑关联属性,本文主要从模糊神经元网络学习算法与弱关联规则模型,建立两方面内.
2、 基于Hadoop平台的并行数据挖掘算法 【摘要】 本文采用Hadoop 分布式云计算平台的两大核心技术MapReduce 和HDFS,实现数据挖掘算法中分类聚类算法的并行化,这一算法是在传统算法的基础上的改进,通过实践论证了该平台的分类聚类.
3、 不同修剪处理对大果榛子产量影响的分析 摘要针对大果榛子在现阶段的修剪技术进行分析,并通过对大果榛子采取不同修剪处理方式的试验,来分析修剪处理方式与大果榛子产量之间的关系,为科学合理修剪大果榛子提供参考 关键词农业技术；大果榛子；果树修剪技.
4、 子陵铺模式：稻虾共作成富民大产业 水清稻绿,龙虾成群,几只白鹭忽地从虾稻田飞起,在空中翩翩起舞……在荆门市东宝区子陵铺镇龙泉村百里泉水产养殖专业合作社“稻虾共作”种养基地,广袤农田里.
5、 正方体展开图大揭秘 正方体是一种常见的立体图形,把正方体按不同的方式展开得到的平面展开图是不一样的 那么,正方体到底有哪些平面展开图呢下面让我们一起来探索这一问题的答案 一、平面展开图的形状正方体的平面展开图有11 种.