UMCS tree based hybrid similarity measure of UML class diagram

doi:10.11772/j.issn.1001-9081.2022111702

Abstract

Abstract:

Software reuse is to retrieve previously developed software artifacts from a repository according to given conditions. The retrieval is based on similarity measure. UML （Unified Modeling Language） class diagram is widely applied to software design， and its reuse as a core of software design reuse has attracted much attention. Therefore， the research on the similarity of UML class diagrams was carried out. UML class diagram contains semantic and structural contents. At present， the similarity research of UML class diagrams mainly focuses on semantics， and there are also some discussions on structural similarity， but the combination of semantics and structure has not been considered. Therefore， a hybrid similarity measure combining semantics and structure was proposed. Due to the non-formal nature of UML class diagram， the UML class diagram was transformed into a graph model for similarity measure， the Maximum Common Subgraph List （MCSL） was searched， a Maximum Common Subgraph （MCS） tree was created based on MCSL， and a hybrid similarity measure method was proposed based on MCS sequence. The semantic matching and structural matching were defined corresponding to concept and structure common subgraphs， respectively. The similarity comparison and similarity based classification quality comparison experiments were carried out， and the experimental results validate the advantages of the proposed method.

Key words: UML (Unified Modeling Language) class diagram, model transformation, hybrid similarity, maximum common subgraph tree, semantic matching, structural matching

摘要：

软件重用是基于给定条件从存储库中检索以前开发的软件产品，检索基于相似性度量。UML（Unified Modeling Language）类图被广泛应用于软件设计，UML类图重用作为软件设计重用的核心而备受关注。因此，对UML类图的相似性开展研究。类图包含语义和结构信息。目前，UML类图的相似性研究主要集中在语义，也有个别讨论结构相似性，但没有考虑将语义和结构相结合。因此，提出一种结合语义和结构的混合相似性度量。鉴于UML类图的非形式化特征，将UML类图转换成图模型，搜索最大公共子图列表，构建了最大公共子图树，提出一个基于最大公共子图序列的混合相似性度量方法。针对概念公共子图和结构公共子图分别定义了语义匹配和结构匹配，并开展了相似性对比和基于相似性的分类质量比较实验，实验结果验证了所提出方法的优势。

关键词: UML类图, 模型转换, 混合相似性, 最大公共子图树, 语义匹配, 结构匹配

CLC Number:

TP311

Zhongchen YUAN, Zongmin MA. UMCS tree based hybrid similarity measure of UML class diagram[J]. Journal of Computer Applications, 2024, 44(3): 883-889.

袁中臣, 马宗民. 基于UMCS树的UML类图的混合相似性度量[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 883-889.

Figures/Tables 17

Fig. 1 Similarity examples of UML class diagram

Fig. 2 Fragment of ontology WordNet

Tab. 1 Element types of UML class diagram and UCG

UML类图的元素类型	UCG元素类型	标签
类	类顶点	cv
属性	属性顶点	av
属性	属性边	e_a
操作	操作顶点	ov
操作	操作边	e_o
参数	参数顶点	pv
参数	参数边	e_p
关系	关联边	e₁
	泛化边	e₂
	聚合边	e₃
	组合边	e₄
	依赖边	e₅
	实现边	e₆

Fig. 3 Fragment of UML class diagram

Fig. 4 UCG model representation of UML class diagram

Fig. 5 UMCS tree

Fig. 6 UMCS tree for hybrid similarity measure

Tab. 2 Matching value between any type pair

类型	String	Integer	Double	Char	Byte	Long	Float	Void	Inst₂
String	1.00	0.29	0.35	0.69	0.49	0.79	0.34	0.00	0.00
Integer	—	1.00	0.93	0.92	0.95	0.97	0.93	0.00	0.00
Double	—	—	1.00	0.46	0.24	0.57	0.95	0.00	0.00
Char	—	—	—	1.00	0.95	0.70	0.57	0.00	0.00
Byte	—	—	—	—	1.00	0.65	0.33	0.00	0.00
Long	—	—	—	—	—	1.00	0.55	0.00	0.00
Float	—	—	—	—	—	—	1.00	0.00	0.00
Void	—	—	—	—	—	—	—	1.00	0.00
Inst₁	—	—	—	—	—	—	—	—	Mat

Fig. 7 Example of semantic matching

Fig. 8 SUMCS list between ug1 and ug2

Fig. 9 SUMCS tree

Tab. 3 Characteristics of class diagrams used for experiment

测试组	样例数	平均尺寸	分布目录
$g 1$	5， 10	13， 14	H1，（H1）
$g 2$	5， 20	12， 13	H1，（H1，H2）
$g 3$	5， 30	11， 12	H1，（H1，H2， H3）
$g 4$	5， 10	22， 24	H1，（H1）
$g 5$	5， 20	24， 25	H1，（H1，H2）
$g 6$	5， 30	23， 24	H1，（H1，H2， H3）

Tab. 3 Characteristics of class diagrams used for experiment

测试组	样例数	平均尺寸	分布目录
$g 1$	5， 10	13， 14	H1，（H1）
$g 2$	5， 20	12， 13	H1，（H1，H2）
$g 3$	5， 30	11， 12	H1，（H1，H2， H3）
$g 4$	5， 10	22， 24	H1，（H1）
$g 5$	5， 20	24， 25	H1，（H1，H2）
$g 6$	5， 30	23， 24	H1，（H1，H2， H3）

Fig. 10 Similarity comparison of testing samples

Tab. 4 Characteristics of class diagram samples used for clustering

样例组	样例数	分布	平均尺寸
$g 1$	100	H1（25%）， H2（26%），H3（24%）， H4（25%）	12.5，13.5，12.6，13.0
$g 2$	100	H1（40%）， H2（35%），H3（15%）， H4（10%）	12.0，14.0，12.5，13.5
$g 3$	100	H1（26%）， H2（24%），H3（25%）， H4（25%）	25.4，13.5，12.5，7.5
$g 4$	100	H1（40%）， H2（40%），H3（10%）， H4（10%）	12.5，13.5，7.6，25.0

Tab. 4 Characteristics of class diagram samples used for clustering

样例组	样例数	分布	平均尺寸
$g 1$	100	H1（25%）， H2（26%），H3（24%）， H4（25%）	12.5，13.5，12.6，13.0
$g 2$	100	H1（40%）， H2（35%），H3（15%）， H4（10%）	12.0，14.0，12.5，13.5
$g 3$	100	H1（26%）， H2（24%），H3（25%）， H4（25%）	25.4，13.5，12.5，7.5
$g 4$	100	H1（40%）， H2（40%），H3（10%）， H4（10%）	12.5，13.5，7.6，25.0

Tab. 5 Composition of testing samples

组成	样例数	分布	平均尺寸
P1	60	H1（30%）， H2（30%）	13.0
P2	20	H3（10%）， H4（10%）	25.0
P3	20	H1（10%）， H4（10%）	8.0

Fig. 11 Clustering and classification quality comparison of different testing groups

Fig. 12 Clustering and classification quality comparison of different methods

References 30

1	KIM D K， SONG E， RYOO J， et al. Special issue on software reuse［J］. Software： Practice and Experience， 2017， 47（7）： 941-942. 10.1002/spe.2504
2	SUTCLIFFE A. Software reuse： state of the art and survey of technical approaches ［M］// Integrated Software Reuse： Management and Techniques. London： Routledge Press， 2019： 51-76. 10.4324/9780429455520-6
3	HASSELBRING W. Software architecture： past， present， future［M］// The Essence of Software Engineering. Cham： Springer， 2018： 169-184. 10.1007/978-3-319-73897-0_10
4	RUMBAUGH J， JACOBSON I， BOOCH G. The Unified Modeling Language Reference Manual［M］. 2nd ed. Noida， Uttar Pradesh： Pearson Education India， 2004：23-38.
5	MEDVIDOVIC N， ROSENBLUM D S， REDMILES D F， et al. Modeling software architectures in the Unified Modeling Language ［J］. ACM Transactions on Software Engineering and Methodology， 2002，11（1）： 2-57. 10.1145/504087.504088
6	MIKKONEN T， TAIVALSAARI A. Software reuse in the era of opportunistic design ［J］. IEEE Software， 2019， 36（3）： 105-111. 10.1109/ms.2018.2884883
7	TEKLI J， CHBEIR R， YETONGNON K. A hybrid approach for XML similarity ［C］// Proceedings of the 2007 International Conference on Current Trends in Theory and Practice of Computer Science. Berlin： Springer， 2007： 783-795. 10.1007/978-3-540-69507-3_68
8	DAI Y， REN X. A hybrid method to evaluate similarity of XML document ［C］// Proceedings of the 2016 International Conference on Education， Management， Computer and Society. Amsterdam： Atlantis Press， 2016： 677-680. 10.2991/emcs-16.2016.165
9	MA Z， ZHAO Z， YAN L. Heterogeneous fuzzy XML data integration based on structural and semantic similarities ［J］. Fuzzy Sets and Systems， 2018， 351： 64-89. 10.1016/j.fss.2018.04.018
10	SRINIVAS C， RAO C V G， RADHAKRISHNA V. Feature vector based component clustering for software reuse［C］// Proceedings of the Fourth International Conference on Engineering & MIS 2018. New York： ACM， 2018： No.39. 10.1145/3234698.3234737
11	SALAMI H O， AHMED M. Class diagram retrieval using genetic algorithm［C］// Proceedings of the 12th International Conference on Machine Learning and Applications. Piscataway： IEEE， 2013： 96-101. 10.1109/icmla.2013.112
12	NIKIFOROVA O， GUSAROVS K， KOZACENKO L， et al. An approach to compare UML class diagrams based on semantical features of their elements ［C］// Proceedings of the 10th International Conference on Software Engineering Advances. ［S.l.］： IARIA Press， 2015： 147-152. 10.1515/acss-2014-0011
13	ROBLES K， FRAGA A， MORATO J， et al. Towards an ontology-based retrieval of UML class diagrams ［J］. Information and Software Technology， 2012， 54（1）：72-86. 10.1016/j.infsof.2011.07.003
14	A-R AL-KHIATY M， AHMED MA. UML class diagrams： similarity aspects and matching ［J］. Lecture Notes on Software Engineering， 2016， 4 （1）：41-47. 10.7763/lnse.2016.v4.221
15	袁中臣，马宗民.基于语义和结构的UML类图的检索［J］.东北大学学报（自然科学版），2020，41（1）：23-28.
	YUAN Z C， MA Z M. Retrieval of UML class diagrams based on semantics and structure［J］. Journal of Northeastern University （Natural Science）， 2020， 41（1）： 23-28.
16	袁中臣，马宗民.基于语义的UML类图的集成分类［J］.计算机工程与应用，2021，57（12）：257-262.
	YUAN Z C， MA Z M. Ensemble classification for UML class diagram based on semantics［J］. Computer Engineering and Applications， 2021， 57（12）： 257-262.
17	MA Z， YUAN Z， YAN L. Two-level clustering of UML class diagrams based on semantics and structure ［J］. Information and Software Technology， 2021， 130： 106456. 10.1016/j.infsof.2020.106456
18	MENG L， HUANG R， GU J. A review of semantic similarity measures in WordNet ［J］. International Journal of Hybrid Information Technology， 2013， 6（1）： 1-12.
19	FAUZAN R， SIAHAAN D， ROCHIMAH S， et al. Class diagram similarity measurement： a different approach［C］// Proceedings of the 3rd International Conference on Information Technology， Information System and Electrical Engineering. Piscataway： IEEE， 2018： 215-219. 10.1109/icitisee.2018.8721021
20	QIU D H， LI H， SUN J L. Measuring software similarity based on structure and property of class diagram［C］// Proceedings of the 6th International Conference on Advanced Computational Intelligence. Piscataway： IEEE， 2013：75-80. 10.1109/icaci.2013.6748477
21	LUCRÉDIO D， FORTES RPM， WHITTLE J. MOOGLE： a metamodel-based model search engine ［J］. Software and Systems Modeling， 2012， 11（2）： 183-208. 10.1007/s10270-010-0167-7
22	ZHANG X， CHEN H， ZHANG T. An UML model query method based on structure pattern matching ［C］// Proceedings of the 2012 International Conference on Trustworthy Computing and Services. 2013： 506-513. 10.1007/978-3-642-35795-4_64
23	YUAN Z， YAN L， MA Z. Structural similarity measure between UML class diagrams based on UCG ［J］. Requirements Engineering， 2020， 25（2）：213-229. 10.1007/s00766-019-00317-w
24	GROSS J L， YELLEN J， ANDERSON M. Graph Theory and Its Applications［M］. 3rd ed. New York： Chapman and Hall/CRC， 2018： 34-57. 10.1201/9780429425134
25	CONTE D， FOGGIA P， SANSONE C， et al. Thirty years of graph matching in pattern recognition ［J］. International Journal of Pattern Recognition and Artificial Intelligence， 2004， 18（3）： 265-298. 10.1142/s0218001404003228
26	SAVAGE N. Graph matching in theory and practice ［J］. Communications of the ACM， 2016， 59（7）：12-14. 10.1145/2933412
27	EGOZI A， KELLER Y， GUTERMAN H. A probabilistic approach to spectral graph matching ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 35（1）： 18-27. 10.1109/tpami.2012.51
28	SABIR U， AZAM F， HAQ S U， et al. A model driven reverse engineering framework for generating high level UML models from java source code［J］. IEEE Access， 2019， 7： 158931-158950. 10.1109/access.2019.2950884
29	SATHYA R， ABRAHAM A.Comparison of supervised and unsupervised learning algorithms for pattern classification ［J］.International Journal of Advanced Research in Artificial Intelligence， 2013， 2（2）： 34-38. 10.14569/ijarai.2013.020206
30	HOSSIN M， SULAIMAN M N. A review on evaluation metrics for data classification evaluations ［J］. International Journal of Data Mining & Knowledge Management Process， 2015， 5（2）： 1-11. 10.5121/ijdkp.2015.5201

[1]	LU Qiang, LIU Xingyu. Semantic matching model of knowledge graph in question answering system based on transfer learning [J]. Journal of Computer Applications, 2018, 38(7): 1846-1852.
[2]	HOU Jinkui, WANG Chengduan. Formal description approach for software component in model-driven development [J]. Journal of Computer Applications, 2015, 35(9): 2692-2700.
[3]	. Object-oriented three-layer modeling in MDA [J]. Journal of Computer Applications, 2010, 30(2): 385-389.
[4]	. Study on model transformation and computer demonstration of virtual prototype [J]. Journal of Computer Applications, 2006, 26(9): 2057-2058.
[5]	CHENG Guo-da,ZOU Ya-hui,ZHU Jing. A self-adaptive approach for information integration [J]. Journal of Computer Applications, 2005, 25(03): 666-669.