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

厦门大学软件学院毕业设计（论文）开题报告学生姓名班级 学号 校内指导教师姓名职称 所在单位厦门大学软件学院毕业设计（论文）题 目基于子图发现的设计模式识别系统子图发现算法的设计与实现毕业设计（论文）的目标：设计一个系统使其能够发现目标系统中基本形式的设计模式和修改版本的设计模式，同时对变化的设计模式有一定预判的能力。系统有人性化的用户界面，强大易用的数据处理，跨平台（Windows、Linux和Unix），性能良好，结果精确（即整个目标系统中未被挖掘出的设计模式和被误认为是设计模式的数量在可接受范围内）。论文的研究目标包括子图发现算法和并行算法的设计与实现。论文将从搜索集初始化、子图扩展和子图集合并等方面对子图发现算法进行描述，然后从数据分解、线程并行、临界区设置等方面阐述并行算法的设计。基于这个目的，在开源系统JUnit3.8.2、JHotdraw5.1、JRefactory2.6.24上进行一系列的实验以评估该方法。实现方法：一、基本环境开发工具：Eclipse 3.4开发语言：Java jdk1.6.0操作系统：Windows Vista Ultimate处理器： Intel Core 2 CPU 1.86GHz目标系统：JUnit3.8.2、JHotdraw5.1、JRefactory2.6.24二、基本原理1.目标系统选择为了便于从源码中挖掘元素和进行评估，我们需要一个系统满足以下条件：l 它的大小应该是合理的。l 它的源码应该是开放的l 它应该是面向对象的设计，因为目前主流软件均是面向对象设计l 它应该被广泛使用我们选择JUnit3.8.2、JHotdraw5.1、JRefactory2.6.24作为目标系统原由有三点：一、这些项目开发时，设计模式的思想已经成熟而且被广泛应用；二、JUnit、JHotDraw、JRefactory都是开源项目，源码是公开的，方便对识别结果的验证，三个项目的规模逐步递增，可以更好地评估本文提出的设计模式识别方法；三、其他相关的设计模式发现研究采用了一个或多个这样的系统来评估他们的方法，所以选择上述3个项目能够比较和评价实验结果。2.图表示在进行子图挖掘之前，有必要为研究的系统和要挖掘的模式定义一种图表示方式，本文将使用抽象语义图(Abstract Semantic Graph, ASG)进行建模。下表定义了ASG所使用的图形符号。在表示系统源码和设计模式签名的ASG中，图的顶点为抽象类、具体类、方法中的一种，图的边为表关联关系的一种(如泛化、聚合、返回类型依赖等)。表：抽象语义图使用的图形符号符号 含义 抽象类或接口 具体类 类或接口中的方法类或接口之间的一对一的属性关联类或接口之间的一对多的属性关联类或接口之间的泛化关系目标方法是源类或接口的一个操作源方法和目标类或接口之间的返回类型依赖源方法接收目标类或接口类型的参数源方法调用目标方法源方法重载目标方法源方法中实例化了目标类，生成对象3.子图挖掘(1)图定义：用无限制的字符标签来定义属性图是一种普遍的定义图的方式。(2)图匹配分为精确的图匹配和容错的图匹配方法。(3)频繁子图挖掘算法：基于Apriori方法和PatternGrowth方法(4)Subdue算法：作为一种无需监管的挖掘算法，Subdue算法查找输入图的一个最佳压缩子结构或者子图。Subdue在它的主搜索算法用的是集束搜索的一种变形方法，算法大致框架如下图所示。算法：SUBDUE。查找最佳地压缩图集子结构的算法。输入：图数据集Graph，束宽度BeamWidth，最佳压缩图集的大小MaxBest，最大子结构数量MaxSubSize，处理子结构的上限Limit输出：最佳压缩图集的子结构集合BestList1: ParentList = Null;2: ChildList = Null;3: BestList = Null;4: ProcessedSubs = 0;5: Create a substructure from each unique vertex label and its single-vertex instances;6: Insert the resulting substructures in ParentList;7: while ProcessedSubs Limit and ParentList not empty do8: while ParentList is not empty do9: Parent = RemoveHead(ParentList);10: Extend each instance of Parent in all possible ways;11: Group the extended instances into Child substructures;12: for each Child do13: if SizeOf(Child) less than MaxSubSize then14: Evaluate Child;15: Insert Child in ChildList in order by value;16: if BeamWidth Length(ChildList) then17: Destroy substructure at end of ChildList;18: Increment ProcessedSubs;19: Insert Parent in BestList in order by value;20: if MaxBest Length(BestList) then21: Destroy substructure at end of BestList;22: Switch ParentList and ChildList;23: return BestList;图：Subdue算法4.并行算法(1)并行性识别：在一个程序中，首先要识别出哪些部分可以并行地执行。也就是说，对于来自同一个串行程序的两个不同语句，在什么情况下可以并行执行，且计算结果与串行程序执行结果一致。(2)分解技术：将计算划分成许多小的计算，再把它们分配到不同处理器中以便并行执行，这是并行算法设计中的两个关键步骤。目前有一些经常使用的分解技术，这些技术可概括分类为递归分解、数据分解、探测性分解以及推测性分解。递归分解和数据分解技术是比较通用的，因为它们能适用于大量的各种问题。探测性和推测性分解技术是专用性质的，因为它们只适用特定类型的问题。(3)编程模型：人们已经开发了许多编程语言和程序库用于显式并行编程，这些编程语言及程序库的区别在于程序员可使用的地址空间，对并发活动的同步程度，以及程序的多重性。常用的编程模型有共享存储编程模型和消息传递编程模式。(4)并行算法模型：一个算法模型就是通过选择一种分解和映射技术并用合适的策略最小化交互来构造并行算法的一种典型方法。并行算法模型包括数据并行模型，任务图模型，工作池模型，主从模型，流水线模型以及混合模型。5.子图发现算法设计与实现： 本研究将从搜索集初始化、子图扩展、子图集合并等方面对子图发现算法进行设计，然后选择适当的分解技术和编程模型将原有算法设计成并行的算法，以大幅提高程序性能。时间进度安排：2008年11月17日-2008年1月16日 理解毕业设计的任务，阅读有关文献，熟悉开发工具。征求导师的意见，提交毕业设计开题报告。2009年1月17日-2009年2月28日 对必要技术及子图挖掘算法进一步了解学习，初步建立Design Pattern的数据模型。建立子图发现算法的基本框架，了解目标系统源码中所使用的设计模式。2009年3月1日-2009年3月20日 完成串行子图发现算法的设计，在目标系统上进行实验，提交毕业设计的中期检查报告。2009年3月21日-2009年5月30日 根据第一阶段的实验结果，将原算法设计成并行算法，重新在目标系统上进行测试，撰写论文。2009年6月1日-2009年6月11 日 提交毕业论文，准备毕业答辩。指导教师审核意见： 校内指导教师签名： 2009年 月 日厦门大学软件学院毕业设计（论文）中期检查报告学生姓名班级二班学号23020051204442校内指导教师姓名职称助理教授所在单位厦门大学软件学院毕业设计（论文）题 目基于子图发现的设计模式识别系统子图发现算法的设计与实现毕业设计（论文）的目标和主要任务：设计一个系统使其能够发现目标系统中基本形式的设计模式和修改版本的设计模式，同时对变化的设计模式有一定预判的能力。系统有人性化的用户界面，强大易用的数据处理，跨平台（Windows、Linux和Unix），性能良好，结果精确（即整个目标系统中未被挖掘出的设计模式和被误认为是设计模式的数量在可接受范围内）。论文的研究目标包括子图发现算法和并行算法的设计与实现。论文将从搜索集初始化、子图扩展和子图集合并等方面对子图发现算法进行描述，然后从数据分解、线程并行、临界区设置等方面阐述并行算法的设计。基于这个目的，在开源系统JUnit3.8.2、JHotdraw5.1、JRefactory2.6.24上进行一系列的实验以评估该方法。已经完成毕业设计（论文）任务的情况：1.子图发现算法的设计为设计模式识别算法所设计的子图发现算法，与Subdue算法类似，但是该算法与Subdue算法主要有两个不同之处：首先该算法没有采用启发式集束搜索方法，因为它会丢失设计模式。其次该算法使用了DFA来去除那些不可能作为模式候选集的子图。子图发现算法的大致框架如图1所示。算法：SubgraphDiscovery。应用于设计模式识别的子图发现算法。输入：数据集 G，最多处理的边数 procLimit，模式指纹确定有限自动机DFA输出：发现的子结构 resultList1: searchList = Null;2: candidateList = Null;3: resultList = Null;4: processedEdges = 0;5: Create substructures that are isomorphic to the initial states of DFA;6: Find the isomorphic instances in G and put them into the substructures;7: Insert the resulting substructures into the searchList;8: while processedEdges procLimit and searchList is not empty do9: for each st in searchList;10: if st is one of the final states of DFA then11: Add st to resultList;12: else13: Extend each instance of st conforming to DFA;14: Group the extended instances into stList substructures;15: for each candidateStucture in stList do16: Merge candidateStucture into the candidateList ;17: searchList = Null;18: Copy candidateList to searchList;19: candidateList = Null;20: processedEdges+;21: return resultList;图 1：子图发现算法(1) 初始化搜索集搜索集的初始化是在图G中查找所有的单边子图，它们与DFA的初始态图是同构的。图2展示了初始化搜索集算法的细节。算法：InitStructure。初始化搜索集算法。输入：数据集 G，模式指纹确定有限自动机DFA输出：初始搜索集 initList1: initList = Null;2:initStatesList Get the initial states of DFA;3:for each edge in G do4:Create a single-edge graph g;5:for each state in initStatesList do6:if g is isomorphic to state then7:add g to corresponding node of initList;8: return initList;图2：初始化搜索集算法(2) 扩展子图在候选集生成过程中，通过给定的k边图生成一系列k+1边图。通过DFA 得到从此状态迁移到下一状态所需的信息，然后添加一条边将k边图扩展成k+1边图。DFA中保存的迁移信息包括用于扩展的顶点，扩展边，边的另一个顶点。扩展子图的大致算法如图3所示。算法：ExtendIns。子图扩展算法。输入：数据集 G，用于扩展的实例 parentIns，对应DFA某一状态的图structure，扩展信息transaction输出：扩展子图集extList1: extList = Null;2: Get isomorphism relation between parentIns and structure;3: if corresponding extended vertex is found4: if the extended edge is not link to a new vertex5: touchingEdges Get all edges connect two corresponding vertices in G6: for each edge in touchingEdges do7: Confirm it is a new edge of same type then add the new edge to parentIns;8:Add the new instance to extList;9: else10:touchingEdges Get all edges touch corresponding extended vertex;11: for each edge in touchingEdges do12: Confirm another new vertex and a same edge then add the new edge to parentIns;13:Add the new instance to extList;14:return extList;图 3：扩展子图算法(3) 合并子图集在子图发现算法中需要用一种数据结构来保存候选子图集。PatternList是自定义的链表结构，PatternList链表的结点由PatterNode组成，PatterNode结点包含了一个在DFA中定义的状态和在图G中的所有实例。PatternList设计如图4所示。图4：PatternList设计类图2.在Junit上实验结果本算法在操作系统为Windows Vista Ultimate，处理器为Intel Core 2 CPU 1.86GHz，RAM 2GB的计算机上进行实验，目标软件系统为Junit3.8.2。表1给出了识别出设计模式实例的个数。图5给出了识别各个设计模式所消耗的CPU时间对比。表1： 基于子图发现的设计模式识别结果 单位：个JUnit v3.8.2设计模式TPFPAdapter00Bridge70Command10Composite10Decorator10Factory Method10Observer20Proxy00Singleton00State/Strategy30Template Method10Visitor00图5：各个设计模式识别所消耗CPU时间对比 单位ms存在的问题和困难（包括需要学院协助解决的问题和困难）：在子图发现算法的子图扩展部分涉及到子图同构检验，这是一个NP完全问题，其计算复杂度相当高。当程序以独占CPU的方式串行执行时，子图同构后面的指令必须等待，使得CPU的利用率不高。指导教师审核意见： 校外指导教师签名： 2009年 月 日 校内指导教师签名： 2009年 月 日学院检查组意见： 学院检查组组长（签章）： 2009年 月 日毕业论文任务书题 目：基于子图发现的设计模式识别系统子图发现算法的设计与实现目标要求：设计一个系统使其能够发现目标系统中基本形式的设计模式和修改版本的设计模式，同时对变化的设计模式有一定预判的能力。系统有人性化的用户界面，强大易用的数据处理，跨平台（Windows、Linux和Unix），性能良好。子图查找算法只需运行一次就能找到所有符合设计模式签名的实例，能够根据用户需求改变算法的并发性。支持条件：开发工具：Eclipse 3.4开发语言