Improved binary similarity measures for software modularization

Rashid NASEEM; Mustafa Bin Mat DERIS; Onaiza MAQBOOL; Jing-peng LI; Sara SHAHZAD; Habib SHAH

doi:10.1631/FITEE.1500373

Your Location：

Home >

Browse articles >

Improved binary similarity measures for software modularization

Regular Papers | Updated：2022-05-19

- Improved binary similarity measures for software modularization
- 改进的软件模块化二元相似度测量
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 8, Pages: 1082-1107(2017)
- Affiliations：
  
  Faculty of Computer Science and Information Technology, Universiti Tun Hussein Onn Malaysia, Parit Raja 86400, Malaysia
  Department of Computer Science, Quaid-i-Azam University, Islamabad 45320, Pakistan
  Division of Computer Science and Mathematics, University of Stirling, Stirling FK9 4LA, UK
  Department of Computer Science, University of Peshawar, Peshawar 25120, Pakistan
  Faculty of Computer and Information Systems, Islamic University Madina, Madina POBox 170, KSA
- Author bio：
- Funds：
- DOI：10.1631/FITEE.1500373
  CLC： TP311
- Received：30 October 2015，
  
  Revised：2017-;8-;4，
  
  Published：2017-08
- Accepted：
Scan QR Code
Rashid NASEEM, Mustafa Bin Mat DERIS, Onaiza MAQBOOL, et al. Improved binary similarity measures for software modularization[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(8): 1082-1107.
DOI：

Rashid NASEEM, Mustafa Bin Mat DERIS, Onaiza MAQBOOL, et al. Improved binary similarity measures for software modularization[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(8): 1082-1107. DOI： 10.1631/FITEE.1500373.

摘要

目的

各种各样的二元相似度测量在聚类方法中被用来确定数据中的相似实体的同类组。这些相似度测量大多数仅基于特征的存在或缺失。二元相似度测量在软件模块化中亦能与不同的聚类方法一起用于提高软件系统的可理解性与可管理性。每种相似度测量都有其优势与不足，分别能使聚类结果优化或恶化。

创新点

本文强调了软件模块化中一些已有的著名的二元相似度测量的优势。此外，基于这些已有的相似度测量，新提出了几种改进的相似度测量。

方法

首先，介绍了一些软件模块化中已有的著名的二元相似度测量的优势。接着，提出了几种改进的新的相似度测量。结合具体例子，说明这些新方法整合了JC、JNM和RR这几种已有的二元相似度测量的优势。最后，通过实验比较新方法与已有方法的结果，验证所提新方法的有效性。

结论

实验结果表明相较于已有的相似度测量，本文所提出的新的二元相似度测量结果的可信度更高。这些新方法能减少任意决策的数量，增加聚类过程中聚类的数量。尽管这些新方法仅基于数据的二元特征向量表达，它们能被用来测试任何编程语言编写的软件系统。

Abstract

Various binary similarity measures have been employed in clustering approaches to make homogeneous groups of similar entities in the data. These similarity measures are mostly based only on the presence or absence of features. Binary similarity measures have also been explored with different clustering approaches (e.g.

agglomerative hierarchical clustering) for software modularization to make software systems understandable and manageable. Each similarity measure has its own strengths and weaknesses which improve and deteriorate the clustering results

respectively. We highlight the strengths of some well-known existing binary similarity measures for software modularization. Furthermore

based on these existing similarity measures

we introduce several improved new binary similarity measures. Proofs of the correctness with illustration and a series of experiments are presented to evaluate the effectiveness of our new binary similarity measures.

关键词

Keywords

references

B. Andreopoulos , , , A.J. An , , , V. Tzerpos , , , 等 . . Multiple layer clustering of large software systems . . Proc. 12th Working Conf. on Reverse Engineering , , 2005 . . p.79 - - 88 . . DOI: 10.1109/wcre.2005.24 http://doi.org/10.1109/wcre.2005.24 . .

P. Andritsos , , , V. Tzerpos . . Information-theoretic software clustering . . IEEE Trans. Softw. Eng. , , 2005 . . 31 ( ( 2 ): ): 150 - - 165 . . DOI: 10.1109/tse.2005.25 http://doi.org/10.1109/tse.2005.25 . .

N. Anquetil , , , T.C. Lethbridge . . Experiments with clustering as a software remodularization method . . Proc. 6th Working Conf. on Reverse Engineering , , 1999 . . p.235 - - 255 . . DOI: 10.1109/wcre.1999.806964 http://doi.org/10.1109/wcre.1999.806964 . .

M. Bauer , , , M. Trifu . . Architecture-aware adaptive clustering of OO systems . . Proc. 8th European Conf. on Software Maintenance and Reengineering , , 2004 . . p.3 - - 14 . . DOI: 10.1109/csmr.2004.1281401 http://doi.org/10.1109/csmr.2004.1281401 . .

R.A. Bittencourt , , , D.D.S. Guerrero . . Comparison of graph clustering algorithms for recovering software architecture module views . . Proc. 13th European Conf. on Software Maintenance and Reengineering , , 2009 . . p.251 - - 254 . . DOI: 10.1109/csmr.2009.28 http://doi.org/10.1109/csmr.2009.28 . .

A.H. Cheetham , , , J.E. Hazel . . Binary (presenceabsence) similarity coefficents . . J. Paleontol. , , 1969 . . 43 ( ( 5 ): ): 1130 - - 1136 . . . .

C.Y. Chong , , , S.P. Lee , , , T.C. Ling . . Efficient software clustering technique using an adaptive and preventive dendrogram cutting approach . . Inform. Softw. Technol. , , 2013 . . 55 ( ( 11 ): ): 1994 - - 2012 . . DOI: 10.1016/j.infsof.2013.07.002 http://doi.org/10.1016/j.infsof.2013.07.002 . .

J.F. Cui , , , H.S. Chae . . Applying agglomerative hierarchical clustering algorithms to component identification for legacy systems . . Inform. Softw. Technol. , , 2011 . . 53 ( ( 6 ): ): 601 - - 614 . . DOI: 10.1016/j.infsof.2011.01.006 http://doi.org/10.1016/j.infsof.2011.01.006 . .

J. Davey , , , E. Burd . . Evaluating the suitability of data clustering for software remodularisation . . Proc. 7th Working Conf. on Reverse Engineering , , 2000 . . p.268 - - 276 . . DOI: 10.1109/wcre.2000.891478 http://doi.org/10.1109/wcre.2000.891478 . .

P. Dugerdil , , , S. Jossi . . Reverse-architecting legacy software based on roles: an industrial experiment . . Commun. Comput. Inform. Sci. , , 2008 . . 22 114 - - 127 . . DOI: 10.1007/978-3-540-88655-6_9 http://doi.org/10.1007/978-3-540-88655-6_9 . .

M. Glorie , , , A. Zaidman , , , A. van Deursen , , , 等 . . Splitting a large software repository for easing future software evolution—an industrial experience report . . J. Softw. Mainten. Evol. Res. Pract. , , 2009 . . 21 ( ( 2 ): ): 113 - - 141 . . DOI: 10.1002/smr.401 http://doi.org/10.1002/smr.401 . .

M.W. Godfrey , , , E.H. Lee . . Secrets from the monster: extracting Mozilla's software architecture . . Proc. Int. Symp. on Constructing Software Engineering Tools , , 2000 . . p.1 - - 10 . . . .

M. Hall , , , N. Walkinshaw , , , P. McMinn . . Supervised software modularisation . . Proc. 28th IEEE Int. Conf. on Software Maintenance , , 2012 . . p.472 - - 481 . . DOI: 10.1109/icsm.2012.6405309 http://doi.org/10.1109/icsm.2012.6405309 . .

I. Hussain , , , A. Khanum , , , A.Q. Abbasi , , , 等 . . A novel approach for software architecture recovery using particle swarm optimization . . Int. Arab. J. Inform. Technol. , , 2015 . . 12 ( ( 1 ): ): 1 - - 10 . . . .

D.A. Jackson , , , K.M. Somers , , , H.H. Harvey . . Similarity coefficients: measures of co-occurrence and association or simply measures of occurrence . . Am. Nat. , , 1989 . . 133 ( ( 3 ): ): 436 - - 453 . . DOI: 10.1086/284927 http://doi.org/10.1086/284927 . .

J.H. Jahnke . . Reverse engineering software architecture using rough clusters . . Proc. IEEE Annual Meeting of the Fuzzy Information , , 2004 . . p.4 - - 9 . . DOI: 10.1109/nafips.2004.1336239 http://doi.org/10.1109/nafips.2004.1336239 . .

Y. Kanellopoulos , , , P. Antonellis , , , C. Tjortjis , , , 等 . . K-attractors: a clustering algorithm for software measurement data analysis . . Proc. 19th IEEE Int. Conf. on Tools with Artificial Intelligence , , 2007 . . p.358 - - 365 . . DOI: 10.1109/ictai.2007.31 http://doi.org/10.1109/ictai.2007.31 . .

A. Lakhotia . . A unified framework for expressing software subsystem classification techniques . . J. Syst. Softw. , , 1997 . . 36 ( ( 3 ): ): 211 - - 231 . . DOI: 10.1016/0164-1212(95)00098-4 http://doi.org/10.1016/0164-1212(95)00098-4 . .

M.J. Lesot , , , M. Rifqi , , , H. Benhadda . . Similarity measures for binary and numerical data: a survey . . Int. J. Knowl. Eng. Soft Data Parad. , , 2009 . . 1 ( ( 1 ): ): 63 DOI: 10.1504/ijkesdp.2009.021985 http://doi.org/10.1504/ijkesdp.2009.021985 . .

C.H. Lung , , , M. Zaman , , , A. Nandi . . Applications of clustering techniques to software partitioning, recovery and restructuring . . J. Syst. Softw. , , 2004 . . 73 ( ( 2 ): ): 227 - - 244 . . DOI: 10.1016/s0164-1212(03)00234-6 http://doi.org/10.1016/s0164-1212(03)00234-6 . .

T. Lutellier , , , D. Chollak , , , J. Garcia , , , 等 . . Comparing software architecture recovery techniques using accurate dependencies . . Proc. 37th IEEE Int. Conf. on Software Engineerin , , 2015 . . p.69 - - 78 . . DOI: 10.1109/icse.2015.136 http://doi.org/10.1109/icse.2015.136 . .

O. Maqbool , , , H. Babri . . The weighted combined algorithm: a linkage algorithm for software clustering . . Proc. 8th European Conf. on Software Maintenance and Reengineering , , 2004 . . p.15 - - 24 . . DOI: 10.1109/csmr.2004.1281402 http://doi.org/10.1109/csmr.2004.1281402 . .

O. Maqbool , , , H. Babri . . Hierarchical clustering for software architecture recovery . . IEEE Trans. Softw. Eng. , , 2007 . . 33 ( ( 11 ): ): 759 - - 780 . . DOI: 10.1109/tse.2007.70732 http://doi.org/10.1109/tse.2007.70732 . .

B.S. Mitchell . . Clustering Software Systems to Identify Subsystem Structures. Technical Report, Department of Mathematics and Computer Science , , : : USA Drexel University , , 2006 . . .

B.S. Mitchell , , , S. Mancoridis . . On the automatic modularization of software systems using the Bunch tool . . IEEE Trans. Softw. Eng. , , 2006 . . 32 ( ( 3 ): ): 193 - - 208 . . DOI: 10.1109/tse.2006.31 http://doi.org/10.1109/tse.2006.31 . .

S. Muhammad , , , O. Maqbool , , , A.Q. Abbasi . . Evaluating relationship categories for clustering object-oriented software systems . . IET Softw. , , 2012 . . 6 ( ( 3 ): ): 260 - - 274 . . DOI: 10.1049/iet-sen.2011.0061 http://doi.org/10.1049/iet-sen.2011.0061 . .

R. Naseem , , , O. Maqbool , , , S. Muhammad . . An improved similarity measure for binary features in software clustering . . Proc. 2nd Int. Conf. on Computational Intelligence, Modelling and Simulation , , 2010 . . p.111 - - 116 . . DOI: 10.1109/cimsim.2010.34 http://doi.org/10.1109/cimsim.2010.34 . .

R. Naseem , , , O. Maqbool , , , S. Muhammad . . Improved similarity measures for software clustering . . Proc. 15th European Conf. on Software Maintenance and Reengineering , , 2011 . . p.45 - - 54 . . DOI: 10.1109/csmr.2011.9 http://doi.org/10.1109/csmr.2011.9 . .

R. Naseem , , , O. Maqbool , , , S. Muhammad . . Cooperative clustering for software modularization . . J. Syst. Softw. , , 2013 . . 86 ( ( 8 ): ): 2045 - - 2062 . . DOI: 10.1016/j.jss.2013.03.080 http://doi.org/10.1016/j.jss.2013.03.080 . .

C. Patel , , , A. Hamou-Lhadj , , , J. Rilling . . Software clustering using dynamic analysis and static dependencies . . Proc. 13th European Conf. on Software Maintenance and Reengineering , , 2009 . . p.27 - - 36 . . DOI: 10.1109/csmr.2009.62 http://doi.org/10.1109/csmr.2009.62 . .

K. Praditwong . . Solving software module clustering problem by evolutionary algorithms . . Proc. 8th Int. Joint Conf. on Computer Science and Software Engineering , , 2011 . . p.154 - - 159 . . DOI: 10.1109/jcsse.2011.5930112 http://doi.org/10.1109/jcsse.2011.5930112 . .

K. Praditwong , , , M. Harman , , , X. Yao . . Software module clustering as a multi-objective search problem . . IEEE Trans. Softw. Eng. , , 2011 . . 37 ( ( 2 ): ): 264 - - 282 . . DOI: 10.1109/tse.2010.26 http://doi.org/10.1109/tse.2010.26 . .

M. Saeed , , , O. Maqbool , , , H. Babri , , , 等 . . Software clustering techniques and the use of combined algorithm . . Proc. 7th European Conf. on Software Maintenance and Reengineering , , 2003 . . p.301 - - 306 . . DOI: 10.1109/csmr.2003.1192438 http://doi.org/10.1109/csmr.2003.1192438 . .

K. Sartipi , , , K. Kontogiannis . . On modeling software architecture recovery as graph matching . . Proc. Int. Conf. on Software Maintenance , , 2003 . . p.224 - - 234 . . DOI: 10.1109/icsm.2003.1235425 http://doi.org/10.1109/icsm.2003.1235425 . .

C. Seung-Seok , , , S.H. Cha , , , C.C. Tappert . . A survey of binary similarity and distance measures . . J. Syst. Cybern. Inform. , , 2010 . . 8 ( ( 1 ): ): 43 - - 48 . . . .

Z. Shah , , , R. Naseem , , , M. Orgun , , , 等 . . Software clustering using automated feature subset selection . . Proc. Int. Conf. on Advanced Data Mining and Applications , , 2013 . . p.47 - - 58 . . DOI: 10.1007/978-3-642-53917-6_5 http://doi.org/10.1007/978-3-642-53917-6_5 . .

M. Shtern , , , V. Tzerpos . . On the comparability of software clustering algorithms . . Proc. IEEE 18th Int. Conf. on Program Comprehension , , 2010 . . p.64 - - 67 . . DOI: 10.1109/icpc.2010.25 http://doi.org/10.1109/icpc.2010.25 . .

M. Shtern , , , V. Tzerpos . . Clustering methodologies for software engineering . . Adv. Softw. Eng. , , 2012 . . 2012 792024.1 - - 792024.18 . . DOI: 10.1155/2012/792024 http://doi.org/10.1155/2012/792024 . .

M. Shtern , , , V. Tzerpos . . Methods for selecting and improving software clustering algorithms . . Softw. Pract. Exp. , , 2014 . . 44 ( ( 1 ): ): 33 - - 46 . . DOI: 10.1002/spe.2147 http://doi.org/10.1002/spe.2147 . .

F. Siddique , , , O. Maqbool . . Enhancing comprehensibility of software clustering results . . IET Softw. , , 2012 . . 6 ( ( 4 ): ): 283 DOI: 10.1049/iet-sen.2012.0027 http://doi.org/10.1049/iet-sen.2012.0027 . .

N. Synytskyy , , , R.C. Holt , , , I. Davis . . Browsing software architectures with LSEdit . . Proc. 13th Int. Workshop on Program Comprehension , , 2005 . . p.176 - - 178 . . DOI: 10.1109/wpc.2005.11 http://doi.org/10.1109/wpc.2005.11 . .

P. Tonella . . Concept analysis for module restructuring . . IEEE Trans. Softw. Eng. , , 2001 . . 27 ( ( 4 ): ): 351 - - 363 . . DOI: 10.1109/32.917524 http://doi.org/10.1109/32.917524 . .

V. Tzerpos , , , R.C. Holt . . MoJo: a distance metric for software clusterings . . Proc. 6th Working Conf. on Reverse Engineering , , 1999 . . p.187 - - 193 . . DOI: 10.1109/wcre.1999.806959 http://doi.org/10.1109/wcre.1999.806959 . .

V. Tzerpos , , , R.C. Holt . . On the stability of software clustering algorithms . . Proc. 8th Int. Workshop on Program Comprehension , , 2000 . . p.211 - - 218 . . DOI: 10.1109/wpc.2000.852495 http://doi.org/10.1109/wpc.2000.852495 . .

A. Vasconcelos , , , C. Werner . . Architecture recovery and evaluation aiming at program understanding and reuse . . Proc. Int. Conf. on the Quality of Software Architectures , , 2007 . . p.72 - - 89 . . DOI: 10.1007/978-3-540-77619-2_5 http://doi.org/10.1007/978-3-540-77619-2_5 . .

B.W.G. Veal . . Binary Similarity Measures and Their Applications in Machine Learning. PhD Thesis , , : : London, UK London School of Economics , , 2011 . . .

Y. Wang , , , P. Liu , , , H. Guo , , , 等 . . Improved hierarchical clustering algorithm for software architecture recovery . . Proc. Int. Conf. on Intelligent Computing and Cognitive Informatics , , 2010 . . p.247 - - 250 . . DOI: 10.1109/icicci.2010.45 http://doi.org/10.1109/icicci.2010.45 . .

Z. Wen , , , V. Tzerpos . . An optimal algorithm for MoJo distance . . Proc. 11th IEEE Int. Workshop on Program Comprehension , , 2003 . . p.227 - - 235 . . DOI: 10.1109/wpc.2003.1199206 http://doi.org/10.1109/wpc.2003.1199206 . .

Z. Wen , , , V. Tzerpos . . An effectiveness measure for software clustering algorithms . . Proc. 12th IEEE Int. Workshop on Program Comprehension , , 2004 . . p.194 - - 203 . . DOI: 10.1109/wpc.2004.1311061 http://doi.org/10.1109/wpc.2004.1311061 . .

T.A. Wiggerts . . Using clustering algorithms in legacy systems remodularization . . Proc. 4th Working Conf. on Reverse Engineering , , 1997 . . p.33 - - 43 . . DOI: 10.1109/wcre.1997.624574 http://doi.org/10.1109/wcre.1997.624574 . .

J. Wu , , , A.E. Hassan , , , R.C. Holt . . Comparison of clustering algorithms in the context of software evolution . . Proc. 21st IEEE Int. Conf. on Software Maintenance , , 2005 . . p.525 - - 535 . . DOI: 10.1109/icsm.2005.31 http://doi.org/10.1109/icsm.2005.31 . .

S. Xanthos , , , N. Goodwin . . Clustering object-oriented software systems using spectral graph partitioning . . Urbana , , 2006 . . 51 ( ( 1 ): ): 1 - - 5 . . . .

C. Xia , , , V. Tzerpos . . Software clustering based on dynamic dependencies . . Proc. 9th European Conf. on Software Maintenance and Reengineering , , 2005 . . p.124 - - 133 . . DOI: 10.1109/csmr.2005.49 http://doi.org/10.1109/csmr.2005.49 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰