基于UMCS树的UML类图的混合相似性度量

doi:10.11772/j.issn.1001-9081.2022111702

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (3): 883-889.DOI: 10.11772/j.issn.1001-9081.2022111702

基于UMCS树的UML类图的混合相似性度量

袁中臣¹(), 马宗民²

^1.沈阳工业大学化工过程自动化学院，辽宁辽阳 111004
^2.南京航空航天大学计算机科学与技术学院，南京 211106

收稿日期:2022-11-16 修回日期:2023-11-15 接受日期:2023-12-05 发布日期:2024-01-05 出版日期:2024-03-10
通讯作者: 袁中臣
作者简介:马宗民（1965—），男，山东金乡人，教授，博士生导师，博士，CCF高级会员，主要研究方向：知识图谱。
基金资助:
国家自然科学基金资助项目(62176121);辽宁省教育厅基本研究项目(LJKZ0165)

UMCS tree based hybrid similarity measure of UML class diagram

Zhongchen YUAN¹(), Zongmin MA²

^1.School of Chemical Process Automation，Shenyang University of Technology，Liaoyang Shenyang 111004，China
^2.School of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing Jiangsu 211106，China

Received:2022-11-16 Revised:2023-11-15 Accepted:2023-12-05 Online:2024-01-05 Published:2024-03-10
Contact: Zhongchen YUAN
About author:MA Zongmin， born in 1965， Ph. D.， professor. His research interests include knowledge graph.
Supported by:
National Natural Science Foundation of China(62176121);Basic Research Project of Education Department of Liaoning Province(LJKZ0165)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP311

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

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

图/表 17

图1 UML类图相似性实例

Fig. 1 Similarity examples of UML class diagram

图2 本体WordNet的片段

Fig. 2 Fragment of ontology WordNet

表1 UML类图和UCG的元素类型

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₆

图3 UML类图片段

Fig. 3 Fragment of UML class diagram

图4 UML类图的UCG模型表示

Fig. 4 UCG model representation of UML class diagram

图5 UMCS树

Fig. 5 UMCS tree

图6 混合相似性度量的UMCS树

Fig. 6 UMCS tree for hybrid similarity measure

表2 类型对匹配值

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

图7 语义匹配实例

Fig. 7 Example of semantic matching

图8 ug1和ug2的结构最大公共子图列表

Fig. 8 SUMCS list between ug1 and ug2

图9 SUMCS树

Fig. 9 SUMCS tree

表3 实验类图特征

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）

表3 实验类图特征

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）

图10 测试样例相似性比较

Fig. 10 Similarity comparison of testing samples

表4 用于聚类的类图样例特征

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

表4 用于聚类的类图样例特征

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

表5 测试样例的组成

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

图11 不同测试组的聚类和分类质量比较

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

图12 不同方法的聚类与分类质量比较

Fig. 12 Clustering and classification quality comparison of different methods

参考文献 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]	赵小虎, 赵成龙. 基于多特征语义匹配的知识库问答系统[J]. 计算机应用, 2020, 40(7): 1873-1878.
[2]	鲁强, 刘兴昱. 基于迁移学习的知识图谱问答语义匹配模型[J]. 计算机应用, 2018, 38(7): 1846-1852.
[3]	侯金奎, 王成端. 支持模型驱动开发的软构件形式化描述方法[J]. 计算机应用, 2015, 35(9): 2692-2700.
[4]	齐军张月菊王涛. 工作流集成中基于代数表达式的语义匹配机制[J]. 计算机应用, 2011, 31(08): 2253-2257.
[5]	黄建庭张立臣古金峰. 基于面向对象的MDA三级建模技术研究[J]. 计算机应用, 2010, 30(2): 385-389.
[6]	张颖王茜刘骥. 基于三维模型转换器的虚拟植物可视化[J]. 计算机应用, 2008, 28(7): 1652-1655.
[7]	李峰徐诚郭凯王亚平 . 虚拟样机模型转换及演示技术研究[J]. 计算机应用, 2006, 26(9): 2057-2058.

基于UMCS树的UML类图的混合相似性度量

UMCS tree based hybrid similarity measure of UML class diagram

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 30

相关文章 7

编辑推荐

Metrics