Apr.2021Vol. $2 No. $
202#年$月 第$2卷第$期
计算机工程与设计
COMPUTER ENGINEERING AND DESIGN
基于改进的C4. 5算法的代码异味检测方法
王帆！吴海涛！高建华+
（上海师范大学信息与机电工程学院，上海20023$）
摘 要：为检测软件结构中的代码异味！提出在属性选择过程中将ReliefF 算法和互信息结合，筛选出相关度大而冗余度
小的条件属性集。传统C4. 5算法在构造决策树时，只考虑条件属性和目标属性的相关度！忽略条件属性间的相关度！基 于这个问题提出在C4. 5算法中加入对称不确定性（SU ）利用SU 计算条件属性间的相关度，更新信息增益率的计算！提
高代码异味检测精确度。对比实验结果表明！该算法能够提高代码异味的检测精确度！有利延长软件生存周期。
关键词：代码异味；C4. 5算法；对称不确定性；RelefF 算法；互信息中图法分类号：TP31# 文献标识号：A
文章编号：#000-7024 （2021） 04-0969-07
doi ： #0. #6208/j. issnl 000-7024. 2021. 0$. 01#
CodeBme l detection method baBed on improved C4.5algorithm
WANG Fan , WU Hai-tao GAO Jian-hua +
(College of Information , Mechanical and Electrical Engineering , Shanghai Normal University & Shanghai 200234 & China)
Abstract : To detect the code smell in the software structure & the ReliefF algorithm and the mutual information were combined in thea t ributelectionprocesstofilterouttheconditionala t ributetwithlargecorrelationandsma l redundancy. Whencon-
structingadecisiontree &thetraditionalC4.5algorithmonlyconsiderstheco r elationbetweenconditionala t ributesandtarget
a t ributes &andignoresthecorrelationbetweenconditionala t ributes. Tosolvethisproblem &symmetricuncertainty (SU )was added to C4.5algorithm. SU was ud to calculate the correlation between conditional a t ributes and the calculation of the infor-
mationgainratewasupdatedtoimprovetheaccuracyofcodesme l detection. Throughcomparativeexperimentalanalysis &the propodalgorithmcanimprovethedetectionaccuracyofcodesme l andprolongthesoftwarelifecycle.Key words ： code smells ； C4. 5 algorithm ； symmetric uncertainty ； ReliefF algorithm ； mutual information
2引言
在软件生命周期阶段，代码异味导致软件质量逐渐衰
退，降低软件理解性和维护性代码异味检测已经成为 发现软件源码或设计问题的方法，过去几十年中，大量研
究者研究出不同的代码异味检测技术。Baydaa 等⑵在基于 相似性度量基础上提出两种新的度量检测Refud Bequest 代码异味。Palomba 等*〕提出一种“HIST ”检测技术，通
过挖掘系统版本变更历史来检测代码异味，解决单个版本 容易丢失重要信息的缺点。近些年来，越来越多的研究者 使用机器学习方法检测代码异味。Wang 等4使用代码变更 信息来提升代码异味数据集中的标签质量，得到更可靠的
训练集，提高代码异味检测准确率。Amonm 等5将C5. 0 算法和遗传算法相结合进行代码异味检测。Fontana 等6使
用#6种机器学习算法对$种代码异味进行检测，其目的是 评估哪种机器学习算法在检测代码异味上准确率更高。
为了提高代码异味检测精确度并使开发人员便于理解
代码异味检测过程，提高开发人员识别代码异味的信心， 本文使用机器学习中的C4. 5算法对其进行检测。在属性选 择阶段，本文提出使用ReliefF 算法计算条件属性和目标属
性相关性，使用互信息计算条件属性间的冗余度，选择出
相关性大而冗余度小的条件属性集，通过划分子集并依据 机器学习算法求得F 值最大的条件属性子集，减少生成决 策树的计算开销。同时提出在C4. 5算法中加入对称不确定
收稿日期：2019-06-24；修订日期：2020-09-10基金项目：国家自然科学基金项目（61672355）
作者简介：王帆（993 -），女，安徽安庆人，硕士研究生，研究方向为软件工程、代码异味与重构；吴海涛（970 -），女，甘肃兰州人，
硕士，副教授，研究方向为软件工程、数据挖掘；+通讯作者：高建华（1963 -），男，浙江绍兴人，博士，教授，CCF 高级会员，研究方
向为软件可靠性理论与设计、软件开发环境与开发技术、数据安全与计算机安全、网络测试、LSI/VLSI 测试等’
E-mail : jhgao@shnu. edu. cn
・970・计算机工程与设计2021年
性（SU），选择信息增益率高且与条件属性间相关度低的作为分，建立新的算型。
岀，该模型在检测代码异味的精确度和召回率方面均所提高。
1背景
1.1代码异味
代码异味是软件结构中的一种设计缺陷，阻碍代码理解，影响软件质量和维护。代码异味在软件版本中生存周期长研究者给岀22种代码异味的定义，并列岀特定的重构方分别移除每种代码异味。但是研究是在一平面上给岀22种代码异味的定义&并一-分类。文献*+根据每种代码异味的特点将Fow-ler定义的代码异味分为7&代码异并认识到代码异的关系，表1列岀代码异味的分。
表1代码异味分类
编号类别描述代码异味
1Bloaters
含代码、方法和增使用
的代码异味。通常这些代码异会马上出现&
是随着项目的发。
LargeClass&LongParameterList&DataClumps&Long
MethodandPrimitiveObssion
2 3 4Object-Orientation此类别代码异味都是面向对象编程原则的不完整
Aburs或不正确的应用。
Change
Preventers
Dispensables
代码异味阻碍软改&在代码某个
位改内容，在位许多
改。
含要和无用的代码异味&删除可以
是代码容&、。
AlternativeClasswithDiferentInterfaces&Temporary
Field&Switch Statements&ParalelInheritance Hierar-
chies&RefudBequest
ShotgunSurgery&DivergentChange
Data Class,Speculative Generality,Duplicate code,Lazy
Class
5Encapsulators此类别包含处理封装和数据通信的代码异味。6Middle Man MessageChains
Couples 此类别代码异味都会导致类间过度耦合。InappropriateIntimacy FeatureEnvy 7Others含在上述6个中的代码异。Comments IncompleteLibraryClass
1.2C4.5算法
C4.5算法是决策树算法中的一种算法&可以用于解决分类和回归问题&代码异分类。
假设D是一目的，|D|为数据集的总数。本文涉及二分类，即目 C 个不同的取值｛P,N2,|P|,|N|分别为D中目标属性值为P& N的总数&这里|P|+|N|=|D|。对D中的分类所需的信息爛为
infoCD）%-寄
lcg—带⑴假定选择条件属性A划分数据集D中样本，若A有$种不同的取值a a，…，a，…，a$2，则属性A按照$种
GainRatio(D,A)—【吧^呼严0)
Spl i t/nfo A(
5) C4.5算法选择信息增益率大的条件属性，即能够最大减少目标属性不确定程度的属性，作为当前节点的分。
2代码异味检测方法
本文研究一种基于改进的C4.5算法的代码异味检测技术，提岀增加的相关度，更新信息增益率的方并在过程中，提岀将ReliefF算法和互信息结岀最优。图1总结了代码异味检测技术的要过程。
取值将D划分为$个子集｛Di,2，…，口，…，Dm Dj为D中属性A取值为a的子集D的样本总数。属性A分D的信息为
info A(D)%$ID]info(Dz)(2)通过A分的的信息增为
InfoGaHn(D&A)%H nfo(D)—Hnfo A(D)(3)
A D的分信息为
Splitlnfo A%-$H log?|D(4)条件属性A对数据集D的信息增益率为
测试集最终模型标签
图1代码异味检测过程
2.1RMIO属性选择算法
属性选择是数据挖掘数据预处理中的重要和常用技术
第$2卷第$期王帆，吴海涛，高建华：基于改进的C$.5算法的代码异味检测方法•971•
之一在有限的样本数据中，冗余的、不相关的条件属性只会使分类器计算开销大并且分类性能差。本文每种代码异味有6#种软件度量即条件属性，并不是每种条件属性对于检测代码异味都是相关的，通过属性选择可以删除冗余的无关的条件属性，提高分类器效率。
ReliefF算法由Kononenko在Kira等的研究成果基础上提出，用于解决多类问题
*0+，是一种属性权重算法。ReliefF算法的主要思想是从训练集中随机选择一个样本S，依次从与S相
同类别和不同类别的训练集中选择M个最近邻样本，然后根据权重公式计算条件属性的权重值并更新排名。上述过程不断重复，直到每个条件属性与目标属性的权重都被计算，最终得到按照权重降序的条件属性排名。权重越大，代表该条件属性对分类作用越大，即该条件属性和目标属性相关度越大，反之，表示该条件属性对分类作用越小。通过设定阈值选择相关度大的条件属性子集，剔除无效、不相关的条件属性。
虽然ReliefF算法可以对属性进行选择，但是不能解决属性冗余的缺点，即得到的属性子集中仍然存在冗余项。可以通过互信息(mutual information)*#+计算条件属性间的冗余度，也表示两个条件属性间的依赖程度。互信息的计算公式为
I<XY)%g$P<x,.)log(P P X))⑹其中，P X，)是X和Y的联合概率分布函数，而P X)和P))分别是X和Y的边缘概率分布函数。互信息度量的是两个条件属性间，一个条件属性对另一个不确定减少的程度，依赖性越强，I(X；Y)的值越大。
通过ReliefF算法计算条件属性和目标属性间的相关度，使用互信息计算条件属性间的冗余度，选择出与目标属性相关度大而与其它条件属性冗余度小的条件属性，所以把该算法称为RMIO属性选择算法，伪代码如算法#所示”
算法I：RMIO属性选择算法
输入：数据集D，包含条件属性集X
输出：最优条件属性集S
(#)ForX中的每个条件属性x,
⑵使用ReliefF算法计算x.和目标属性C之间的相
W(X i，C%
(3%EndFor
($)选择相关度最大的条件属性x—argmaxW(*,C)，其中x*#X
(5)S%S7X
(6)For z%#To X—S Do
(7)从X—S中选择相关性最大冗余度最小的条件属性X i#X—S
(8)S%S7x
(9%EndFor
(#0)将S中条件属性划分成”份，Si…S”
(11%For i%1To/Do
(#2)利用C4.5算法选出F值最大的条件属性集
S%@rgm@x(C4.5(S i%%
(13%EndFor
(14%ReturnS
2.2SU_C4.5算法
数据集合中的条件属性并非都对模型的分类包含相同的期望信息，有些条件属性对分类起到一定的正作用，有些则相反。例如对Long Method代码异味进行分类，条件属性“LOC”(代码量)包含更多的期望信息，对其分类有更多作用，而条件属性“DIT”(类的继承深度)只包含少量期望信息。同样，利用C4.5算法构造决策树时，在数据中一个作为分，的
性集中，有的条件属性对分裂属性影响较大，有的则相反。例如天气的两个条件属性温度和季节，季节的变化会影响温度的高低，这两个条件属性将有一定的影响，具有一定的关联关系。
本文认为任意两个属性都有一定的关联关系，并且定义这种关联关系为相关度。C4.5算法在构造决策树时，只考虑条件属性与目标属性的相关度，忽略条件属性间的相关度。改进的C4.5算法通过计算对称不确定性来确定两个条件属性间的相关度。
对称不确定性(SU)
*2+常用来判断条件属性与目标属性、条件属性间的相关度。SU的公式可参考第#章的式(#)〜式(3)，条件属性X和条件属性Y的相关度公式如下
SU(X，Y%
InfoGain(X,Y)]
info(X)+info(Y)」(7% SU(X,Y)取值范围为［0,#」，当SU(X,Y)=0时，表示X与Y为两个相互独立的条件属性，当SU(X,Y)=#时，表示X与Y为两个完全相关的条件属性。则条件属性A与其它所有条件属性的平均相关度公式为
$SU(A,AQ
SU(A,A,)—--------(8)式(8)中E为不包含条件属性A的属性子集，丨E
为集合E的属性总数。
C4.5算法构造决策树选择分裂属性时需要考虑该条件属性与目标属性有最大相关度，同时在该条件属性与其它条件属性间需要有最小相关度，即该条件属性与其它条件属性有最小的平均相关度。改进后的算法公式如式(9)
所
•972•计算机工程与设计2021年
GainRatio(D,A%InfoGain(D,A)
SplitInfo A+SU(A,AQ(9)如果条件属性A与其它条件属性的相关度越小，平均相关度就越小，信息增益率就越大。本文将对称不确定性(SU)加入C4.5算法中，更新信息增益率的计算，所以把该改进算法称为SU_C4.5算法，伪代码如算法2所示。
算法2：SU_C4.5算法
输入：数据集D(有”个属性，其中”一1个是条件属性，第”个是目标属性)
输出：一棵决策树
(1)创建根节点N
(2)I所有样本都属于同一类别C，then
(3)Return N为叶子结点，标记为类C
(4)ForD中的每个条件属性A
(5)计算条件属性间的相关度和信息增益率
(6Endfor
⑺选择使GainRatio(D,A)(信息增益率)最大的条件属性作为分裂属性
(8)将数据集D按照选择的分裂属性进行划分
(9)对于分裂后的每部分数据集，循环执行以上算法过程
2.3算法复杂度分析
使用RMIO算法对条件属性进行属性选择，与一般的Wrapper方法相比，时间复杂度大大降低。一般的Wrapper 方法，有多少个特征子集，分类器就要运行相应次数来对其进行评价。以完全搜索选择属性算法为例，假如在D个条件属性中选择M个条件属性，传统的Wrapper算法需要运行C Q次，而RMIO算法只需要运行D次即可。尤其对
，统的Wrapper算相，RMIO算法执行时间更少。
在传统的C4.5算法中，计算信息增益率的时间复杂度是O(m*n)，其中m是属性的个数，”是样本的个数*3+。在SU_C4.5算法中，计算信息增益率之前，需要先计算条件属性间的相关度，需要扫描为整个区间去计算每个条件属性间的相关度，其时间复杂度为O(m*n)所以在使用SU_C4.5算法计算信息增益率最坏情况下的时间复杂度仍然为O(m*”)。
3实验
为了验证本文提出的SU_C4.5算法的有效性，在4个开源软件Eclip3.3.1，Mylyn3.1.1，ArgoUML0.26和Rhino1.6上进行了实证性研究。本实验主要关注以下3个问题：
QI：C4.5算法在属性选择后的数据集上的分类准确率是否有提高？
Q2：SU3C4.5算法相对于传统C4.5算法的分类准确率是高？
Q3：SU—C4.5算法相对于其它机器学习算法的分类确率是高？
3.1实验数据集
实验中使用的数据集来自于Lucas Amonm等
*〕的论文中的数据集，数据集D%{(N；,A,C)i%1,2,3,•••,/}，N，表示代码类实体的ID,A，表示代码实体的属性(本文指度量，如LOC)WMC等)，C，表示该实体是否是代码异味。数据集D来自4个java开源软件Eclip 3.3.1、Mylyn 3. 1.1、ArgoUML0.26和Rhino 1.6，总共有7952个样本，61个条件属性，9种代码异味。本文实验采用十折交叉验证来测试C4.5算法的准确性。
9代码异&Antisingleton、Blob、Class DataShouldBePrivate、ComplexClass、LargeClass、Long Method、Long Parameter List、Message Chains禾口Swiss Army Knife o对于这9种代码异味，在文献口4］中有详细的定义。
(1)Antisingleton(AS)：该类的对象只有一个实例，承担很多责任，在一定程度上违背“单一职责原则”。
(2)Blob(Bb)：系统中类承担很多的责任，有很多属性、操作，并且依赖数据类。
(3)ClassDataShouldBePrivate(CP)：的类，违反封装原则。
(4)Complex Class(CC)：类中至少包含一个大而复杂的方法，可以用圈复杂度和代码行数度量。
(5)Large Class(LC)：类中至少包含一个大的方法。
(6)Long Method(LM)：类中有过长方法。
(7%LongParameterList(LPL%：中至含一个方法，该方法相对系统中每个方法的平均参数数量的长参数列表。
(8)Message Chains(MC)：一个使用长链方法调用来实现(至少)其功能之一的类。
(9)Swiss Army Knife(SK)：类中某方法可以分为多种方法的分离集，从而提供许多不同的不相关的功能。
3.2模型评价指标
本文使用信息检索中最基本指标召回率和精确度来评估模型的好坏，其中召回率和精确度的计算方法
如下
召回率'帀叽(10)
精确度'tp+fp(1)这TP(truepositive)确检测出的代码异，FP(falpositive)将代码异检测为代码异的，FN(falnegative)将代码异检测为代码异
的数量。由于精确度和召回率是两个值，无法根据两个值来比较模型的好坏，需要F 值来综合精确度和召回率•计
第42卷第4期王帆！吴海涛！高建华：基于改进的C4.5算法的代码异味检测方法・973・
算方法如下
F佶=2*精确度*召回率$⑵％
F但—精确度+召回率#2 3.3实验设计
实验环境如下：操作系统是windows10&处理器是inter(R)Core(TM)i5-8250U@1.6GHz，内存是8GB，实验是在Weka3.8和eclip中完成，开发语言是java。
一：本文每种代码异的总数和条件属性总数见表2。使用RMIO算9种代码异味数
RMIO算法最后一会给岀按照的一序，的值代的相关度及，值最相关度最最小的条件在首位，值最相最最低的排在末尾。每种代码异的都有61种&为了优的子集，首先将61序
分成6份，第#含前10个，第2含前20个，依推，第5含前50个，第6份含所。使用C4.5算法在的的代码异上分类&F值最大的依次士1,2,3个，再使用C4.5算法在 的数上进行分类，此时F值最大的为最优条件
表2代码异味数据集样本总数和条件属性总数
代码异总总
AS795261
Bb795261
CP795261
CC795261
LC795261
LM795261
LPL795261
MC795261
SK795261
实验二：分别使用SU_C4.5算法和传统C4.5算法在RMIO的9种代码异上。通过十折交证法计算代码异味分确率，最后比较两个算法的精确度、召回率及F值。
实验三：分别使用SU_C4.5算法和JRip算法及朴素贝叶斯算法在RMIO的9种代码异上。通过十折交证法计算代码异味分 确率，最后比较SU_C4.5算法和JRip算法及朴素贝叶斯算法的精确度、召回率及F值。
3.4实验结果与分析
通过上述3组实验的设计，得到3组实验结果，根据实验结果，逐一回答前文提到的Q-Q3问题。
Q1：对9种代码异使用RMIO算法进行属性选择，使用C4.5算为基准分类算法&最优的
属性子集&并的，得到的见表3。其中“△”使用RMIO算的属子集和未的构造的模型，"+”
使用RMIO算构造的模型结果更好, "―”的构造的模型更好。从表3中可以看岀Message Chains数据集中的条件属性总数减到10,Blob和CDSBP数据集的条件属性总数减,300从表3能够看岀，C4.5算法在使用RIMO算的上构造的型的分
确率有明显提高，其中分类精确度最高提高5.9%，召回率提高3.7%,F值提高4.1%o通过图2能够直观看岀, C4.5算法在RIMO的上的分类F所提高，明在预阶RMIO属性选能够高分器能。
表3RMIO算法与未属性选择的比较结果
代码异
数据集
条件属性
子
精确度
(△)
召回率
(△)
F
(△)
AS20+4.6%
+C.7%+4.#%
Bb30+4.1%
+1.C%
+2.5% CP30+5.9%—1.9%
+#.3%
CC29+0.2%+0.3%+0.2%
LC11
+$.6%
—0.4%
+#.9%
LM13+1.6%+3%+2.3%
LPL20+0.7%+1.6%
+#.2%
MC10+5.7%
+#.7%
+3.5% SK21—3.1%+1.9 %—0.7%
100.00%
95.00%
90.00%
85.00%
80.00%
75.00%
70.00%
65.00%
60.00%
55.00%
50.00%
45.00%ullllll
AS Bb CP CC LC LM LPL MC SI<
■RMIO算法■未属性选择
图2属性选择前后F值对比
Q2：根据表4的实验结果，可以看岀SU_C4.5算法和传统C4.5算法相比&代码异味分确率有明显提升，中分类精确度最高提高4.9%，召回率最高提高6.8%, F值最高提高4.7%，虽然Message Chains异味的召回率和F所，但是平均各指标的值都有所提高。从图4可以看岀传统C4.5算法检测代码异味时，Blob的F值近似50%，代码异味的F值都在68.5%以上，其中Long Parameter List的F值为97.4%。这是因为代码异味
