基于决策树算法的设计模式抽取

《基于决策树算法的设计模式抽取》由会员分享，可在线阅读，更多相关《基于决策树算法的设计模式抽取（6页珍藏版）》请在装配图网上搜索。

1、精品论文基于决策树算法的设计模式抽取赵洋，林辉跃（南京理工大学计算机学院，南京 210094）5摘要：设计模式被广泛的应用于各种软件系统设计中，但是这种架构的设计模式的相关信息 在大量的系统中常常丢失，使得优秀的设计不能充分的发挥其应有的作用。从面向对象软件 程序中抽取设计模式就是把这些埋葬在代码里或者设计图中的使用过的设计模式抽取出来， 这不仅仅能使得我们对大的系统更加容易理解，更重要的是它们能够让我们知道原始的系统 的设计意图。本文研究利用决策树的智能算法从面向对象的软件中抽取设计模式。设计和实10现利用开源系统 Junit 对设计模式进行模式的训练，以产生模式规则，然后利用模式规则抽 取

2、相应的设计模式。实验证明，利用决策树算法不仅可以抽取标准的设计模式的实例，而且能够大大的提高对变体模式的抽取。 关键词：决策树算法；设计模式；机器学习算法 中图分类号：TP31915Recovery of Design Patterns based on the Decision TreeAlgorithmZHAO Yang, LIN Huiyue(School of Computer Science, Nanjing University of Science and Technology, NanJing 210094)20Abstract: Design patterns have be

3、en widely used in software development. However, they may be buried in the software life cycle, and hence good experiences are gone. Therefore, we need torecover patterns from object-oriented source code to understand software developers original design intent. In this paper, we borrow the decision

4、tree algorithm to recover patterns from source code. In order to generate pattern rules, the open source Junit has been used to do training for25patterns. The experimental results shows that our solution can not only detect regular patterns, butalso work for their variants.Keywords: decision tree al

5、gorithm; design pattern; machine learning algorithm0引言30近二十年以来，基于专家设计经验的设计模式1,2,3已经被广泛的应用到了软件工业中， 软件开发者很自然地重用设计模式去解决软件设计中经常出现的问题。然而，在软件系统中， 利用设计模式和实现设计模式的实例后，源代码中与模式有关的很多信息都不再被利用，我 们很难在源代码中跟踪这些设计上的一些信息。尤其在大的软件系统中，你几乎不可能找到 设计模式的实例。35不同的设计模式抽取方法已在文献4中进行全面阐述，例如 Kramer 等研究人员实现的 抽取设计模式实例的工具 Pat5和 Bansiya

6、 等研究人员实现的抽取工具 DP+6等。机器学习 算法，如决策树和神经网络，已经被应用到抽取潜在的设计模式实例中7,8，然而这两种方 法都不能完全自动化，它需要手工的收集和人为干预。更重要的是，其训练集来自于另一种 抽取的设计模式的工具，使用机器学习的算法，只是以微调方法从该工具中获取训练集。而40且，这些方法应用机器学习技术主要目标是为了消除从其他工具产生的潜在 false-positive 的 结果，而不是直接的抽取设计模式。因此，他们的训练样本被它所用的工具所限制，这可能 会丢失一些真正的设计模式实例。本文设计和实现了利用决策树的智能算法从面向对象的软件系统中抽取设计模式，利用基金项目：

7、高等学校博士学科点专项科研基金（编号：20093219120026）作者简介：赵洋（，1978-），男，副教授，主要研究方向：软件工程，程序静态分析。E-mail: yangzhao- 6 -开源系统训练模式规则，然后利用模式规则从开源代码中抽取设计模式。451用决策树算法挖掘设计模式的架构本文研究利用决策树智能算法抽取设计模式实例包括两个阶段，一个阶段是从有模式标 号的训练样本中获得模式的规则，如图 1 所示，另一个阶段是根据从第一阶段训练出来的模 式规则，从大量的不带模式标号的样本中抽取设计模式实例，如图 2 所示。首先将面向对象 软件设计的源代码转换为 XML 文件存储该软件系统的类结构

8、的信息，接着 XML 文件输入50到一个预处理系统中，输出训练样本。在模式规则的产生过程中，要对训练样本进行模式的 标号，然后将这些样本集输入到决策树算法中，输出模式规则。而在模式的抽取阶段，在获 得训练样本后，直接将其作为模式规则的输入，抽取出设计模式实例。图 1 模式规则的产生过程55图 2 模式抽取的过程2预处理系统602.1预处理系统的概述本文是研究设计和实现利用决策树算法训练样本以产生模式规则，然后利用规则抽取设 计模式，如图 1 和图 2。首先将源代码转换为 XMI 的中间表示格式，然后作为预处理系统 的输入。在预处理系统中分为几个步骤，首先解析源代码的 XMI 文件，获得源码的系

9、统的 类信息，接着建立样本的混合记录，然后设计模式的预测器和计算每个混合记录的预测器的65值。预处理系统输出的训练样本就可以输入到决策树算法中用于概念的学习。学习后的模式 的规则，就可以抽取别的开源系统的相应的设计模式了，本章节将具体实现预处理系统。2.2解析 XML 文件获取类信息利用 Rational Rose 系统将源代码转换为 XML 文件后，本节将解析 XML 文件，以获取 该开源系统的信息，包括类信息和类与类之间的关系，包括每个类的信息，比如该类是抽取70类还是具体类或者是接口，该类的属性、方法等等。Java 解析 XML 文档，常用的有两种方法：使用基于事件的 XML 简单 AP

10、I(Simple API for XML)称为 SAX 和基于树和节点的文档对象模型(Document Object Module)称为 dom。Sun 公司提供了 Java API for XML Parsing 接口来使用 SAX 和 dom。本实验利用了基于树和节点的文档对象模型来解析 XML 文件，该解析过程包括以下几75个步骤。首先它先用工具类 DocumentBuilderFactory 来实例化一个对象 factory ，如 factory=DocumentBuilderFactory.newInstance() ，接着 该对象 创建一 个文 档构建 器， 即 DocumentB

11、uilder builder=factory.newDocumentBuilder()，然后利用该文档构建器对象解析 XMI 文件，即 Document document=builder.parse(File file)。通过 document 对象，它可以获得 节点列表。最后获得每个类的信息和每个类之间的关系。802.3样本的混合记录的产生设计模式涉及到一组类和类之间的关系，所以我们不能简单的把每个类简单的组合在一 起来作为训练样本，因为这种组合是巨大的。考虑一个软件系统中有多 1000 个类，3 个类10003 = 109的组合的大小为。所以本章节应用混合记录的算法实现，即把带有相同属性和

12、相同的关系的组合归为一类，计算它们出现这类的次数，然后冲每个混合记录的类中抽取合85适数量的记录出来，用于训练样本，产生模式规则。利用这种方法，它不会丢失特征，但是 大大的降低了软件系统的复杂度，使得利用决策树算法抽取设计模式成为可能。利用混合记录的算法，计算系统中的混合记录出现的次数。比如一个系统把 3 个类作为 一个组合，并且每个类只有一种属性，即是否是具体类，如是具体类，则表示 C，如果不是 具体类，则表示 A。那么这种组合只有 4 种，不考虑组合排序，即 AAA，AAC，ACC，CCC。90然后计算每种组合中类之间的关系的组合出现的次数。假设考虑类之间有两种关系，关联关 系和代理关系，

13、那么一个混合记录 ACA 的关系组合包括 27 中组合，然后计算它们每个组 合出现的个数，如表 1 列出了部分的组合关系和出现的次数。表 1 多关系的训练样本类号属性组合第一个类与第二个类的关系第二个类与第三个类的关系第一个类与第三个类的关系发生的次数1ACA关联和代理代理代理42ACA代理代理关联233ACA关联代理代理和关联54ACA关联关联代理795100105计算了多关系的样本的发生次数后，接着就是对每种样本进行抽样。我们可以用临界的 类的属性或者临界的类的关系划分所有的样本。我们可以仅仅考虑那些对挖掘设计模式有重 要作用的属性和关系的类。比如，如果我们认为泛化和关联关系对挖掘一个设计

14、模式实例非 常的重要，那么我们就只考虑这两这种关系，而不考虑其他的关系。这种抽样，不仅提高了 效率，而且不会丢失类之间的关系，提高了抽样的质量。2.4模式的预测器的设计本文是设计和实现利用决策树算法抽取设计模式，所以必须要为每个模式设计预测器， 决策树会通过预测器的值进行分类，所以预测器设计的好坏，直接影响了模式的规则的产生 和抽取的质量。本文列举了适配器模式的预测器。适配器的预测器包括20个预测器，它们如下所示：CompositeAttribute：该预测器属性是表示三个类的组合的类型，如果一个类是具体类， 那么用C表示，如果一个类不是具体类，即用A表示。由于适配器模式涉及到三个角色类， 所

15、以是三个类的组合。同时此组合不包括位置的不同。所以在该设计模式中，该属性的值域110115120125130135140为：AAA，AAC，ACC，CCC四种值域。association_1_2：表示类1是否关联了类2，是则为true，否则为false。 association_1_3：表示类1是否关联了类3，是则为true，否则为false。 association_2_1：表示类2是否关联了类1，是则为true，否则为false。 association_2_3：表示类2是否关联了类3，是则为true，否则为false。 association_3_1：表示类3是否关联了类1，是则为tru

16、e，否则为false。 association_3_2：表示类3是否关联了类2，是则为true，否则为false。 generation_1_2：表示类1是否是类2的子类，是则为true，否则为false。 generation_1_3：表示类1是否是类3的子类，是则为true，否则为false。 generation_2_1：表示类2是否是类1的子类，是则为true，否则为false。 generation_2_3：表示类2是否是类3的子类，是则为true，否则为false。 generation_3_1：表示类3是否是类2的子类，是则为true，否则为false。 generation_3

17、_2：表示类3是否是类2的子类，是则为true，否则为false。 contain_adapter_1：类1是否包含adapter字符串，如果包含，那么很可能这个类就是我们要找的适配器类,该预测器试图通过语义识别适配器模式。Contain_adapter_2: 类2是否包含adapter字符串，如果包含，那么很可能这个类就是我们 要找的适配器类，,该预测器试图通过语义识别适配器模式Contain_adapter_3: 类3是否包含adapter字符串，如果包含，那么很可能这个类就是我们 要找的适配器类，,该预测器试图通过语义识别适配器模式。Public_SameMethodMore_1_2：在

18、类1和类2有父类和子类的关系的情况下，判断类1和类2中相同的public方法是否比其中一个的子类的非public的方法多，如果类1是类2的父类，同 时类1还有自己的父类，那么这里的比较是类2的方法与类1和其父类的所有方法的比较，因 为也许真正的适配器的接口是类1的父类。这个是预测器是根据适配器的意图提出来的，因 为适配器模式的意图是将一个类的接口转换为客户需要的另外一个接口，所以应该来说要作 为适配器类，该类从父类继承下来的方法必须要比自己的public方法更多。Public_SameMethodMore_1_3：在类1和类3有父类和子类的关系的情况下，判断类1和类3中相同的public方法是

19、否比其中的子类的非public的方法多。如果类1是类3的父类，同时类1 还有自己的父类，那么这里的比较是类3的方法与类1和其父类的所有方法的比较，因为也许 真正的适配器的接口是类1的父类。Public_SameMethodMore_2_3：在类3和类2有父类和子类的关系的情况下，判断类2和类3中相同的public方法是否比其中一个的子类的非public的方法多。如果类2是类3的父类，同 时类1还有自己的父类，那么这里的比较是类3的方法与类2和其父类的所有方法的比较，因 为也许真正的适配器的接口是类1的父类。Invoke_method：该三个类中的两个类中有父类和子类的关系时，判断该子类是否调用

20、了第三个类中的方法。调用则 true，否则 false。1451501551601651703决策树算法现在，数据挖掘、机器学习的智能算法广泛的应该于各行各业中，它们的共同点都是从 大量的数据中挖掘出有意义的知识，用于预测未来。这些智能算法中，用的最普遍的就是分 类算法，它是从大量的数据中，抽取出一个有意义的数据模型，用于以后预测数据。在 20 世纪 70 年代后期到 80 年代初期，机器学习研究人员 J.Ross Quinlan 开发了决策树 算法，称为迭代的二分器，即所说的 ID3 决策树算法 C4.5 是一种增强版的 ID3 算法的实现， 它是由 Quinlan 于 1993 年提出10

21、。该 C4.5 算法充分利用修剪后的规则的一个变种方法，该 方法精度高，更能找到学习问题的目标概念题。它通过递归分割数据为给定的数据集产生一 个分类的决策树。训练样本通过属性描述的，它的值作为对于一个给定的树节点，该节点是 根据在树的生长过程中获得的信息增益率决定的。最后，修剪的规则，通过重新排列和删除 类似的分支树，以减小树大小。C4.5 可以同时处理离散值和并连续的值，但是也会失去训 练样本中的预测值。本文利用了一个开源的系统名叫 Weka。Weka 全名叫做怀卡托智能分析环境，它是一 款免费的、非商业化的、基于 java 环境下的开源的机器学习以及数据挖掘软件。该系统功 能非常的强大，集

22、合了机器学习各种算法，包括对数据进行预处理、分类、回归、聚类、关 联规则以及在新的交互式界面的可视化。本文利用 weka 系统中的 J4.8 算法对样本进行学习， J4.8 算法是 C4.5 算法的修正版。图 3 适配器模式的决策树4实验结果本文设计和实现利用决策树算法抽取设计模式，本文把适配器作为一个例子，设计和实 现了利用决策树算法产生了策略模式模式的模式规则和模式的决策树，如图 3，然后利用模 式规则从开源代码 JhotDraw、JRefactory、Java.Awt 中抽取适配器的设计模式的实例。利用 类似的方法，设计和实现了策略设计模式和抽象工厂设计模式的模式规则的产生和利用该模 式

23、规则从开源系统中抽取这三种设计模式的实例，抽取到的设计模式的统计信息如表 2 所 示。表 2 利用模式规则从开源系统中抽取到的相应的设计模式的统计模式JhotDraw(v6.0)JRefactory(v2.6.24)Java.Awt(v5.0)适配器模式302639抽象工厂模式202734策略模式2425341751805结论本文设计和实现了利用决策树算法抽取设计模式实例。首先本文具体的实现了样本的预 处理系统，解析系统的源代码的 XMI 文件，获得系统的类信息，接着利用混合记录的算法 产生混合记录和利用抽样的方法优化了样本的数量和提高了系统的性能，然后具体的列举了 适配器的预测器的设计，将预

24、处理系统输出的混合记录输入到决策树算法学习，训练出模式 的规则。然后利用规则抽取了设计模式实例。从实验的结果可以看出，利用决策树可以抽取 到大量软件系统中的设计模式及其变体。参考文献 (References)1851901952001 F.Buschmann, R.Meunier, H.Rohnert, P.Sommerlad,and M.Stal. Pattern-Oriented Software Architecture:Asystem of PatternsM. Wiley,1996.2 L.Bass, P.Clements, and R.Kazman. Software Archit

25、ecture in practiceM.Addison Weslsy, 2003.3 E. Gamma, R. Helm, R. Johnson, et a1. 设计模式：可复用面向对象软件的基础M. 李英军等译. 北京: 机械工业出版社.4 J. Dong, Y. Zhao, and T. Peng, Architecture and Design Pattern Discovery Techniques - A ReviewA. Proceedings of International Conference on Software Engineering Research and Prac

26、tice (SERP), USA, June 2007. 5 C. Kramer and L. Prechelt. Design recovery by automated search for structural design patterns in object-oriented softwareA. In Proceedings of 6th International Workshop on Program Compression (IWPC 98),1998, pp. 208-215.6 J. Bansiya. Automating design-pattern identific

27、ation - DP+ is a tool for C+ programsJ. Dr. Dobbs Journal,1998.7 R. Ferenc, A. Beszedes, L. Fulop and J. Lele, Design Pattern Mining Enhanced by Machine LearningA. 21stIEEE International Conference on Software Maintenance (ICSM05) pp. 295-304.8 Y.-G. Gueheneuc, H. Sahraoui, and F. Zaidi, Fingerprint

28、ing Design PatternsA. Proc. 11th Working Conf. onReverse Eng. (WCRE), 2004.9 H.Huang,S.Zhang,J.Cao,and Y.Duan. A practiacal pattern recovery approach based on both structural andbehavioral analysisJ. Journal of Systems and Software 75(1-2) 69-87, 2005.10 J. Quinlan. C4.5: Programs for Machine LearningM. Morgan Kaufmann, 1993.