基于子图发现的设计模式识别系统——子图发现算法的设计与实现---开题报告等附件.doc

《基于子图发现的设计模式识别系统——子图发现算法的设计与实现---开题报告等附件.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、厦门大学软件学院《毕业设计（论文）》开题报告学生姓名班级学号校内指导教师姓名职称所在单位厦门大学软件学院毕业设计（论文）题目基于子图发现的设计模式识别系统——子图发现算法的设计与实现毕业设计（论文）的目标：设计一个系统使其能够发现目标系统中基本形式的设计模式和修改版本的设计模式，同时对变化的设计模式有一定预判的能力。系统有人性化的用户界面，强大易用的数据处理，跨平台（Windows、Linux和Unix），性能良好，结果精确（即整个目标系统中未被挖掘出的设计模式和被误认为是设计模式的数量在可接受范围内）。论文

2、的研究目标包括子图发现算法和并行算法的设计与实现。论文将从搜索集初始化、子图扩展和子图集合并等方面对子图发现算法进行描述，然后从数据分解、线程并行、临界区设置等方面阐述并行算法的设计。基于这个目的，在开源系统JUnit3.8.2、JHotdraw5.1、JRefactory2.6.24上进行一系列的实验以评估该方法。实现方法：一、基本环境开发工具：Eclipse3.4开发语言：Javajdk1.6.0操作系统：WindowsVistaUltimate处理器：IntelCore2CPU1.86GHz目标系统：J

3、Unit3.8.2、JHotdraw5.1、JRefactory2.6.24二、基本原理1.目标系统选择为了便于从源码中挖掘元素和进行评估，我们需要一个系统满足以下条件：l它的大小应该是合理的。l它的源码应该是开放的l它应该是面向对象的设计，因为目前主流软件均是面向对象设计l它应该被广泛使用我们选择JUnit3.8.2、JHotdraw5.1、JRefactory2.6.24作为目标系统原由有三点：一、这些项目开发时，设计模式的思想已经成熟而且被广泛应用；二、JUnit、JHotDraw、JRefactory

4、都是开源项目，源码是公开的，方便对识别结果的验证，三个项目的规模逐步递增，可以更好地评估本文提出的设计模式识别方法；三、其他相关的设计模式发现研究采用了一个或多个这样的系统来评估他们的方法，所以选择上述3个项目能够比较和评价实验结果。2.图表示在进行子图挖掘之前，有必要为研究的系统和要挖掘的模式定义一种图表示方式，本文将使用抽象语义图(AbstractSemanticGraph,ASG)进行建模。下表定义了ASG所使用的图形符号。在表示系统源码和设计模式签名的ASG中，图的顶点为抽象类、具体类、方法中的一种，

5、图的边为表关联关系的一种(如泛化、聚合、返回类型依赖等)。表：抽象语义图使用的图形符号符号含义抽象类或接口具体类类或接口中的方法类或接口之间的一对一的属性关联类或接口之间的一对多的属性关联类或接口之间的泛化关系目标方法是源类或接口的一个操作源方法和目标类或接口之间的返回类型依赖源方法接收目标类或接口类型的参数源方法调用目标方法源方法重载目标方法源方法中实例化了目标类，生成对象3.子图挖掘(1)图定义：用无限制的字符标签来定义属性图是一种普遍的定义图的方式。(2)图匹配分为精确的图匹配和容错的图匹配方法。(3)

6、频繁子图挖掘算法：基于Apriori方法和PatternGrowth方法(4)Subdue算法：作为一种无需监管的挖掘算法，Subdue算法查找输入图的一个最佳压缩子结构或者子图。Subdue在它的主搜索算法用的是集束搜索的一种变形方法，算法大致框架如下图所示。算法：SUBDUE。查找最佳地压缩图集子结构的算法。输入：图数据集Graph，束宽度BeamWidth，最佳压缩图集的大小MaxBest，最大子结构数量MaxSubSize，处理子结构的上限Limit输出：最佳压缩图集的子结构集合BestList1:P

7、arentList=Null;2:ChildList=Null;1:BestList=Null;2:ProcessedSubs=0;3:Createasubstructurefromeachuniquevertexlabelanditssingle-vertexinstances;4:InserttheresultingsubstructuresinParentList;5:whileProcessedSubs≤LimitandParentListnotemptydo6:whileParentListisno

8、temptydo7:Parent=RemoveHead(ParentList);8:ExtendeachinstanceofParentinallpossibleways;9:GrouptheextendedinstancesintoChildsubstructures;10:foreachChilddo11:ifSizeOf(Child)lessthanMaxSubSizethen12:Evalu