2. 广州大学计算机科学与教育软件学院, 广东 广州 510006;
3. 湖南高速公路管理局, 湖南 长沙 410209
2.School of Computer Science ＆ Education, Guangzhou University, Guangzhou 510006, Guangdong, China;
3.Hunan Highway Administration Bureau, Changsha 410209, Hunan, China
设计模式是一项重要的软件复用技术,通常用来获取为解决软件设计问题而所需的软件知识[1]。文献[2, 3, 4]阐述了设计模式对软件质量好坏的影响。虽然设计模式非常实用,但如何选择一个合适的设计模式一直是困扰设计者的问题,对于一些经验相对欠缺的设计者显得尤为明显。因此,设计模式检测技术对解决具体的软件问题是有意义的。现有技
术对索引局限性问题的检测效果不是特别理想,通常情况下,指标值的分配很难和用户关键字匹配成功,为解决这个问题,提出了一种基于形式概念分析(formal concept analysis,FCA)和实例推理(case based reasoning,CBR)的设计模式检测方法。FCA是一种数据分析技术,能发现隐藏在一个案例库指标与案例间的知识,CBR是一种智能学习模型,是用于解决该问题的重要工具,这二者结合将可有效解决索引局限性问题。
本研究给出的模型中,当用户输入一个新问题描述后,系统会通过相似函数来检测类似的案例,给出用户检索的解决方案,并将之作为新知识存储到系统。如果用户不满意该检索得到的解决方案,系统能够通过FCA的相似方法来找到更适合的设计实现。首先,通过FCA发现相关案例,该案例的问题描述可加深用户对问题的理解;其次,FCA技术可生成相关指标,进而做出更完整的问题说明;最后,使用CBR作为检索和改进相似性过程的知识工具,并为后续工作保留新的经验。
1 相关研究目前有多种检测设计模式的方法与工具[5, 6, 7],文献[8, 9]提出了一种设计模式逆向工程的评估框架,侧重设计模式检测技术及相关工具的研究,并将不同的方法与工具进行了比较。文献[10, 11]提出对设计模式中主要角色的特征进行注释的检测方法,该方法侧重了类结构,但对类关系的检测缺乏约束机制。文献[12]基于GOF(gang of four)的23种设计模式分层次提出了一种自动检测设计模式的方法。文献[13]中允许开发者依据源码,通过面向方面的Java注释来对所开发软件进行不同设计模式的选择,提出了切点的概念,对类所承担不同职责的角色进行了改进。作者前期工作实现了对设计模式中角色之间基于GOF经典模式变异关系的约束规则制定与设计模式检测[14]。
文献[15]提出了一种能够检测设计模式变异的非标准化实现,能自行定义,新模式可在引入现有模式基础上重复检测早期源码,对存储的相关数据库进行分析,并进行修改,但该方法在找出所有设计模式之前,需进一步转换为结构化查询的逻辑公式,这个步骤难度较大,且容易出错。文献[16]提供了一种基于多Agent的检测方法,该方法依赖一个隐式的知识框架来搜索基于软件设计领域的解决方案。这种方法共享了软件设计者之间的交流经验,从而让用户可以选择合适的设计模式去解决软件设计问题。这种方法只允许对以往的知识进行复用,然而,共享未经证实的知识是该系统的主要弱点。为解决上述问题,文献[17]使用了基于设计模式信息检索的IR搜索模型,但其精度有待改进。文献[18, 19]中设计模式借助视觉语言分析技术来映射每个设计模式的图形表示形式,该方法有其可视化的优点,具有很好的精度,但仅限于结构型模式,针对创新型与行为型模式效果不够理想。
2 FCA与CBR相关知识实例推理(CBR)[20]是一个借鉴以往的经验知识来解决相似问题的解决方案,其知识表示为一个涉及问题描述和解决方案的案例,并且一些案例被存储到案例库中。CBR过程主要包括以下4个部分:(1)从以往案例中检索最相似的案例;(2)复用一个新的检索方案;(3)修改解决方案以增加结果的精确度;(4)在遇到一个新的问题描述时,对其进行保存。
为执行CBR过程,形式概念分析(FCA)[21]用来处理案例库。FCA是一种有效的数学知识,采用了基于概念格的数据分析方法来提取对象属性之间的相关知识。形式化描述是实现一个FCA的重要手段,表示为一个三元(O,P,I),其中O表示对象集,P为属性集,I是二者的关系集I⊆O×P 。
FCA实现了一组概念,该概念由对象相关的属性组成,一个正式的概念由两部分组成,概念的外延和内涵,外延包括分享指定属性的所有对象,内涵包括给定对象所共享的所有属性。正式的概念可认为是其对象集或超集属性之间关系的子集,即子概念之间的关系,可理解为一个层次概念。
文献[22]提出了一种结合了CBR和FCA的基本方法,并初步掌握了利用FCA技术将发掘的知识嵌入到案例的能力,该研究中,每个对象表示为一个案例或一个指标的属性,其中,指定的符号被研究。基于FCA的概念格也可作为设计模式案例库的一部分,从FCA的定义来看,模型能够检测具有相似性问题并共享指标的相关案例,该系统提供了一个相对完整的基于FCA指标的问题描述。
3 基于FCA与CBR的设计模式检测图1中的CBR模型涉及两个主要部分:
(1)案例库的案例表示、案例检索与案例组织;
(2)CBR引擎。
|
图1 设计模式检测系统的结构模型 Fig.1 Architecture of design patterns detecting system |
CBR引擎包括以下4个步骤:
(1)检索
用户提出新的问题后,通过一种相似性函数从案例库中检索能够解决该问题的案例。通常,一个案例问题的解决系统包括问题的描述和解决方案。
(2)复用
用户提出检索方案并通过复用解决问题。
(3)修改
对所检索解决方案的精确度进行改进,从而得到更完整的表示。
(4)保存
在分析了问题,并对之改进后,新经验表示为一个新的案例,并存入案例库。
3.1 案例表示与检测 3.1.1 案例表示案例表示[23]是实例推理(CBR)模型最基本的元素,为了解决这个描述的问题,将一个案例分为两个部分,问题的描述与其对应的解决方案。
(1)问题描述
在CBR模型中,首先输入一个新问题到案例库,再将之和以往的案例进行比较。
(2)解决方案
在CBR系统中,提出一个可重用解决问题的方案。文中,解决方案通过CBR从一组案例集或案例训练来获得一个可靠的案例库。案例库包括设计模式问题描述、模式名称、设计模式分类(创建型、结构型、行为型)、设计模式目的等信息。
3.1.2 案例索引案例索引主要是用来分配索引中的特征值。前文提出了一个解决问题系统的案例描述,其目的是记录非结构化案例或文本。基于CBR检索系统的主要特点体现在可使用有价值的指标来识别用于解决问题的成功案例。本研究将利用文本格式转换的方法来对案例结构的部署进行表示,并仔细分析了案例库的几个典型特征,如主名、分类等,见表1。
|
表1 典型特征描述 Table 1 Description of typical feature |
表2描述了一个特征值的例子,其中Ci表示第i个案例,这些特征作为一个新的方法来表示信息,从而改进实例推理的检索效率。
文中FCA用来产生一个引出案例库中案例与指标之间知识的概念格。以二进制形式(0,1)描述了FCA的实现,表3是一个基于案例对象与设计模式检索属性间的二进制例子。其中“1”表示匹配到了结果,“0”表示未匹配结果。二进制值被转换成定义为由一组案例集外延与指标集内涵组合而成的正式概念。概念的外延表示一个共享了指标的案例集,内涵是一个指出了相关案例的指标集,FCA的最终结果是一个依据形式概念生成的概念格结构。图2描述了一种基于设计模式案例库的概念格结构。FCA的概念格有助于获得一个案例库中可用的知识标引,文中知识标引为得到更好的检索方案将进一步改进问题的描述,此外,概念格在一定程度上克服了为防止相关案例被发现而对指标的依赖。
|
|
表2 问题特征描述 Table 2 Features of problem description |
|
|
表3 基于设计模式的形式背景 Table 3 Formal context based on design pattern |
本研究提出了一种检索方法,该方法能够对用户问题进行检索与排序。根据本研究中提及的案例库概念格,FCA的外延与内涵属性将作为一个相似方法的关键。一个概念的内涵表示一个案例中涉及问题描述指标集,外延是一个被内涵描述的案例集。例如,一个概念的内涵,图2中概念A表示为｛creational,instantiate,create｝,其概念的外延表示为｛C1,C3｝,当用户输入一个新的问题到系统意味着检索过程的开始,需要将一个新问题与案例库中的检索结果进行匹配。而如何找到一个合适的解决方案是非常重要的步骤,系统采用相似度函数对结果进行排序。考虑到信息检索中,每个词条拥有不同的度,而文档应由一个有权值的特征向量表示,且权值的计算取决于信息在该案例中出现的频率等。综合上述,本研究选用Cosine理论[24]表示一个输入的新问题与案例库概念之间的相似度函数,详见式(1),给出了两个概念U与C,U是一个用户问题的概念,C表示案例库概念,I表示一个包含在案例库指标集的内涵,U与C的值表示为“0”或“1”,相似性评估取值为“0”到“1”之间,其中“0”表示相似为0％,“1”表示相似为100％。
| \[{\text{simlarity}}\left( {U,C} \right) = \frac{{\sum\limits_{i = 1}^n {{I_{u,i}} \times {I_{C,i}}} }}{{\sqrt {\sum\limits_{i = 1}^n {{{\left( {{I_{u,i}}} \right)}^2} \times \sum\limits_{i = 1}^n {{{\left( {{I_{u,i}}} \right)}^2}} } } }}\] | (1) |
(1)式中:n表示上限,Iu,i中i表示用户问题概念的指数Ic,i表示案例库概念的指数,检索结果包括了用户问题的案例概念及相似值排序后的概念。其中排序为第一级相似性值最大,较适合作为新问题的相关解决方案。并且每个检索到的结果可能涉及到几个案例,但这并不意味着会有几种解决方案,因为大多数情况下,可先持有一个相似的解决方案,接着对CBR模型进行改进,进而提出一种合适的精确度检测方法。
3.4 案例改进案例改进过程的目的是增加检索过程的精确度。由于用户对问题描述不够清晰,其匹配效果可能不太理想。为解决上述问题,改进过程提供了相关的问题描述,同时不断缩小用户问题的范围,从而生成一个更完整的问题描述说明。改进过程中FCA有两个性质应用如下。
|
图2 基于设计模式的概念格推理实例 Fig.2 Concept lattice case reasoning based on design pattern |
首先是FCA概念格的分类情况,使用此属性,对相关符合用户问题的指标进行处理。文中一个作为一级排序的概念节点被检索,并用来引导相关案例,该案例通过当前概念的外延被发现。此外,根据定义,超概念的外延包含了当前的概念与一个共享指标的超集案例。由于当前概念与超集概念共享了指标,因此,系统提出的相关问题将从这两个概念类型的外延来获得。如图2 概念A作为｛C1,C3｝提出。
其次FCA方法提供了一种指出描述完整问题说明的规则。系统从检索过程中取得最好结果的当前概念节点着手,并考虑文中当前节点的子概念节点。通常,一个当前概念包含匹配和非匹配指标,虽然当前一些概念指标不能匹配用户的问题,但是应该有最接近的解决方案来改进原来存在的不匹配问题。本研究以式(1)得出的Simlarity(U,C)值与设定的阈值0.2进行比较,小于0.2时,对之进行过滤,即不再考虑其子概念的计算;否则,根据定义,由于子概念的内涵是当前的概念内涵一个超集,因此,系统建议当前子概念的内涵提供给用户。本研究子概念被认为最接近当前概念,因其包含当前概念案例的最大相关指标。例如:图2中最接近的当前概念A的子概念由概念D与E二部分组成,A可以表示为 ｛creational,create,instantiate｝,概念D表示为｛interface,instantiate｝,概念E表示｛concretebulider,convert｝。
考虑到子概念的递归,将所有层级概念的相似性值加权相乘,并进行累加后,取其平均值,得到最终的相似度值Score,见式
\[\operatorname{Score} = \sum\limits_{i = 1}^n {{W_i}} \times {\operatorname{simlarity} _i}\left( {U,C} \right)/n,\]
(2)
| \[{W_i} = \left\{ \begin{gathered} 0.2,i = 1; \hfill \\ 0.3,i = 2; \hfill \\ 0.5,i = 3; \hfill \\ 0.7,i = 4; \hfill \\ 0.9,i > 4 \hfill \\ \end{gathered} \right.\] | (3) |
案例保存的目的是对经验进行学习,从而保存一个有助于解决相似问题的新知识。通常情况下,一个新的案例包括一个新问题的解决方案,在这项研究中,一个新的案例在进行检索与改进后的结果将被保存。其过程如下:首先,描述了对案例检索的结果进行保存,当CBR检索操作终止时,一个新的案例生成, 新的案例作为一个问题的描述和检索的解决方案在优先级排序后,用来表示具体的软件设计,这种方式便于用户取得检索结果后的最终实现。其次,CBR系统保留对问题描述的改进,其解决方案可作为一个新案例。当用户依据指标要求改进原有问题时,新的案例将被创建。此外,系统需通过设计模式专家来解决通过对系统单独操作而不能解决的问题。
4 案例检索步骤Step 1 输入问题的描述,并将问题特征依据表1的结构进行拆分。
Step 2 依据Step 1的结果,对设计模式案例库中的设计模式特征进行匹配。
Step 3 若有完全匹配的结果则匹配成功;此外,如相似度值低于“0.2”,表示无相应的查找结果,即匹配失败,退出检索。
Step 4 若仅是部分匹配,即相似度值的取值范围在[0.2,1]之间,如能与表2中的部分子特征进行匹配,则子问题特征作为二级子概念,并对之进行递归引导,得到三级,甚至多级子概念,式(2)、(3)将所有层级的子概念相似度值与权值相乘累加后取平均值,而得到最终的相似度值Score。
Step 5 对于输入的同一问题,其检测结果将可能出现多个不同的Score值,此时,需对Score进行排序,从而选择相似度Score值最大的作为最优选择。
Step 6 在Step 5的基础上将取得最大相似度Score对应的拆分特征值进行保存。
5 检测模型原型的描述搜索过程开始时用户输入一个新的问题描述,根据前文检索步骤,由图3可知,输入的问题与Abstract Factory模式的检索相似度Score为0.4173,排序等级为“1级”,宜作为最优解。此外,系统返回的相关问题将存储在案例库,这有助于用户获得更精确的结果。出于是否应该改进原有问题指标的考虑,系统提出了一种具有代表性的特征,以方便用户在设计模式专家的指导下对Score相似度值进行选定。用相关指标对这些特征进行描述,并帮助用户选择合适的指标,从而做出更完整的问题说明。
|
图3 设计模式检测系统相似度图 Fig.3 Similarity graph of design pattern detection system |
试验使用平均精度MAP[25]进行计算,其实质是对单个问题的精确度汇总后取平均值,见式(4):
\[MAP = \frac{1}{n}\sum\limits_{j = 1}^n {\frac{1}{{{p_j}}}} \sum\limits_{i = 1}^{{p_j}} {PRE\left( {{C_{i,j}}} \right)} \]
(4)
本研究检测提供两组数据集。一组是对知识进行有效训练的训练案例集,另外一组是通过一组测试案例来检验模型有效性的测试案例集。
(1) 试验数据1
训练案例集包括两个数据源获取的1212个例子。首先,设计模式包括了23个经典的解决方案,而这些可用作初步的模型数据,其余1189例来自设计模式中的设计问题,它们被认为是以数据训练为目的的问题描述。
(2) 试验数据2
设计模式专家分析了问题描述的质量后,对之进行训练,将其解决方案保存到案例库中。测试案例集是一个数据集,通过241个设计模式初学者对模型进行检验而获得,其测试用例分成两组,其中组A包括1528个案例,组B包括1404个案例。
6.3 试验方案与结果分析 6.3.1 对比试验试验评价了修改过程中的检索性能,其目的是比较原有问题及当前一些主流的检索方法与基于FCA与CBR改进后的问题对建议指标适应的精确度比较。试验过程依据第4部分的检索步骤,并使用了试验数据2中组A的1528个输入案例来观察建议指标的优势。依据式(2),n取值1528,Pj表示针对第j个问题的案例数,其中j的取值范围为[1,1528], PRE(Ci,j)表示检测后第j个问题对应第i个案例的的相似度Score值,表4列出了改进模型后的检索性能,并通过指标建议对问题改进后的MAP与其他主流的技术MAP值进行比较。由于对于智能学习的效果不够理想,原有问题MAP指标值仅为18.84％,效果明显较弱,多Agent检索技术在智能化与个性化方面的优势使其MAP值达到42.34％,而IR检索模型虽然采用一种近似匹配的方法,并逐步求精来获得查询和检索结果,也一定程度上避免了传统检索方法所带来的不确定性,其MAP值达到47.78％,但这二者缺乏使用FCA来对案例库进行深度知识的挖掘,MAP值较融合了FCA与CBR的本研究的结果73.14％有所差异。
|
|
表4 问题改进效果表 Table 4 The improvement effect of questions |
在CBR模型中,保存过程提供了有效的学习能力。测试组A被看成是可以增加到案例库的有用案例,在表4试验完成后,依据第4部分中的Step 6,案例库将新增1528条相关的特征指标,在此基础上,再将试验数据2中的数据组B进行输入并检索,从而用来测试在添加了一个新的测试案例组A后,其检索过程的性能。表5显示了上述情况的MAP值比较,分别为案例库中添加新的测试案例(即:案例库的学习)的效率与原有案例(即:案例库的训练)的效果比较。可见基于FCA与CBR的本研究使用CBR作为改进新增问题的重要工具,一定程度上避免了检索的局限性问题,并取得了73.98％的检索效果,较原有问题的23.14％,多Agent检索的46.05％,IR检索的49.26％,有较明显的改进。
|
|
表5 案例库学习性能表 Table 5 The case base learning performance |
本研究提出了一种设计模式检测模型,该模型结合了CBR和FCA的特点,一定程度上解决了现有研究基础上的检索局限性问题。改进技术有助于系统取得更加完整的描述问题的指标,从而得到更加精确的结果。该模型还提供了一种解决系统相似问题的学习方法及原型开发评估模型。通过对该模型平均精度MAP测量的结果表明,其性能较一般情况下的检测模型有较大的改进。下一步工作中,将结合仿生算法对本研究工作进行进一步的优化,并通过Jrefactory v2.634、Junit v3.7等经典的设计模式开源原型系统对之进行验证与比较评估,从而为大型遗产系统的重构提供有力支持。
| [1] | ERICH Gamma. Design pattern[M]. Beijing:China Machine Press, 2000:1-22.( 1) |
| [2] | AMPATZOGLOU A, FRANTZESKOU G, STAMELOS I. A methodology to assess the impact of design patterns on software quality[J]. Information and Software Technology, 2012, 54(4):331-346.(1) |
| [3] | ISSAOUI I, BOUASSIDA N, BEN-ABDALLAH H. Using metric-based filtering to improve design pattern detection approaches[J]. Innovations in Systems and Software Engineering, 2015, 11(1):39-53.(1) |
| [4] | ISSAOUI I, BOUASSIDA N, BEN-ABDALLAH H. A new approach for interactive design pattern recommendation[J]. Lecture Notes on Software Engineering, 2015, 3(3):173-178.(1) |
| [5] | DONG J, ZHAO Y, PENG T. A review of design pattern mining techniques[J]. International Journal of Software Engineering and Knowledge Engineering(IJSEKE), 2009, 16(6):823-855.(1) |
| [6] | DONGJING Y, GE J, WU W. Detection of design pattern instances based on graph isomorphism[C]／／Proc 4th IEEE International Conference on Software Engineering and Service Science (ICSESS).Beijing,China:IEEE Computer Society, 2013:874-877.(1) |
| [7] | RASOOL G, MADER P. A customizable approach to design patterns recognition based on feature types[J]. Arabian Journal for Science and Engineering, 2014, 39(12):8851-8873.(1) |
| [8] | PETTERSON N, LOWE W, NIVRE J. Evaluation of accuracy in design pattern occurrence detection[J]. IEEE Transactions on Software Engineering, 2010, 36(4):575-590.(1) |
| [9] | BOUASSIDA N, BEN-ABDALLAH H, ISSAOUI I. Evaluation of an automated multi-phase approach for patterns discovery[J]. International Journal of Software Engineering and Knowledge Engineering, 2013, 23(10):1367-1398.(1) |
| [10] | RASOOL G, PHILIPPOW I. Design pattern recovery based on annotations[J]. Advances in Engineering Software, 2010, 36(41):519-526.(1) |
| [11] | SABO M,PORUB DJ. Preserving design patterns using source code annotations[J]. Journal of Computer Science and Control Systems, 2009, 34(2):53-56.(1) |
| [12] | GU-EH-ENEUC Y G, ANTONIOL G.DEMIMA: a multilayered approach for design pattern identication[J]. IEEE Transactions on Software Engineering, 2008, 34(5): 667-684.(1) |
| [13] | CALLVGN A, TRAMONTANA E. Delivering dependable reusable components by expressing and enforcing design decisions [C]／／Proceedings of Computer Software and Applications Conference (COMPSAC) Workshop QUORS. Kyoto, Japan:IEEE Computer Society, 2013:493-498.(1) |
| [14] | 肖卓宇,何锫,黎妍.基于设计模式角色的附加关系检测研究[J].计算机应用研究, 2015,32(7):2042-2045. XIAO Zhuoyu, HE Pei, LI Yan. Study on the additional relationships based on design pattens′s roles[J]. Application Research of Computers, 2015, 32(7):2042-2045.( 1) |
| [15] | STENCEL K,WEGRZYNOWICZ P. Detection of diverse design pattern variants[C]／／15th Asia-Pacific Software Engineering Conference. Beijing, China: IEEE Computer Society, 2008:51-57.(1) |
| [16] | ALIAKSANDR B, ENRICO B,PAOLO G. Choosing the right design pattern: the implicit culture approach [C]／／Proceedings of the Workshop on Multi-Agent Systems and Simulation at the Industrial Simulation Conference 2006 (ISC-2006). Trento, Italy:RoMEO, 2006:71-81.(1) |
| [17] | YATES B, BERTHIER R. Modern information retrieval[M]. New Jersey: Addison Wesley, 1999:17-35.(1) |
| [18] | LUCIA A D, DEUFEMIA V, GRAVINO C, et al. Design pattern recovery through visual language parsing and source code analysis[J]. Journal of Systems and Software, 2010, 82(7):1177-1193.(1) |
| [19] | LUCIA A D, DEUFEMIA V, GRAVINO C, et al. Behavioral Pattern Identification through Visual Language Parsing and Code Instrumentation[C]／／Proceedings of European Conference on Software Maintenance and Reengineering. Kaiserslautern, Germany: IEEE Computer Society, 2009:99-108.(1) |
| [20] | 杜辉, 叶文华, 楼佩煌. 基于实例推理技术在模块变型设计中的应用研究[J]. 山东大学学报(工学版), 2011,41(1):78-85. DU Hui, YE Wenhua, LOU Peihuang. Application research on CBR technology used in modular variant design[J]. Journal of Shandong University(Engineering Science), 2011, 41(1):78-85.( 1) |
| [21] | UTA PRISS. Formal concept analysis in information Science[J]. Annual Review of Information Science and Technology, 2006, 40(3):1-22.(1) |
| [22] | BELEN D, ANTONIO M G, PABLO P G, et al. Formal concept analysis for knowledge refinement in case base reasoning[C]／／In Proc of the 25th International Conference on Innovative Techniques and Applications of Artificial Intelligence. Cambridge, UK: SGAI, 2005:233-245.(1) |
| [23] | RALPH B,KOLODNER J. Representation in case based reasoning[J].Knowledge Engineering Review, 2005, 20(1):209-213.(1) |
| [24] | PRAMANIK S, MONDAL K. Cosine similarity measure of rough neutrosophic sets and its application in medical diagnosis[J]. Global Journal of Advanced Research, 2015, 2(1):212-220.(1) |
| [25] | MOHD Sanusi AZMI, MOHAMAD Faidzul Nasrudin, KHAIRUDDIN Omar, et al. Farsi／arabic digit class-ification using triangle based model features with ranking measures[C]／／2012 International Conference on Network and Computational Intelligence(ICNCI 2012). Singapore City, Singapore:IACSIT, 2012:91-97.(1) |