一种面向软件缺陷预测的特征聚类选择方法

李丽媛 江国华

摘要：软件缺陷预测技术通过分析软件静态信息，对软件模块的缺陷倾向性做出判断，合理分配测试资源。但有时搜集的大量度量元信息是无关或冗余的，这些高维的特征增加了缺陷预测的复杂性。文章提出了一种新的度量元选择方法，首先通过样本聚类将相似度高的样本聚在同一簇中，然后在每个簇中按照最低冗余度进行特征子集的挑选，主要选择相互间冗余度低，且预测能力强的度量元。最后通过NASA数据集的实例证明本文方法能有效降低特征子集的冗余率，并能有效提高预测的准确度。

关键词：软件缺陷预测;特征选择;特征聚类

中图法分类号：TP311

文献标识码：A

1 引言

随着现代信息技术的发展，软件规模不断增长，程序复杂度不断提高，致使软件中隐藏的缺陷也越来越多，由此引发的软件故障给国家、给企业带来了不可估量的损失。软件缺陷预测技术从20世纪70年代发展至今，一直备受关注。软件缺陷预测技术可以分为静态缺陷预测技术和动态缺陷预测技术[1]。静态缺陷预测技术主要分析软件静态信息，利用与缺陷相关的度量元，准确预测出软件模块的缺陷数量或缺陷分布情况。这样在软件测试时可以合理分配测试资源，给软件质量保证提供了重要的途径。

在分析软件模块时，有大量的软件度量元（即特征）可以提取，而特征间是存在冗余关系的，即一个特征可以由其他一个或几个特征信息推导出来。这些冗余特征将影响构建预测模型的效率，甚至还会降低预测模型的准确度[2]。因此使用特征选择或提取的方法移除这类特征有重要研究意义。

特征选择就是从一组数量为Ⅳ的特征中选择出数量为M的最优特征，其中M

对特征选择的研究比较著名的有：Gao等人[4]考虑了七种特征排序方法和三种特征子集选择方法，基于一个大型传统通信系统的研究发现移除85%的特征不会降低缺陷预测效果，甚至有时还能提高缺陷预测的性能。Guo等人[5]使用了随机森林方法对特征进行排序，他们发现前5个特征的预测效果和使用21个特征进行预测的效果相当。Menzies等人[6]使用信息增益对特征进行排序，他们的结论和Guo相似：使用前3个特征的预测效果和使用全部特征效果相当。Wang等人[7]认为单个特征选择技术不稳定，因此集成了多个特征选择方法以获得稳定的特征集合。在17种不同的集成方案中发现集成2-4种方法时，预测效果最佳;随着集成数量的增加，预测效果反而开始下降。Mitra等人[8]使用最大信息压缩指标来度量不同变量间的相似度，对特征集进行聚类，然后在聚类结果中选出具有代表性的特征组成特征子集。该方法需要指定期望特征个数K，并且对不同的K值比较敏感。此外，刘树龙等人[9]提出一种基于聚类分析的特征子集选择框架FECAR，FECAR首先根据特征间的相关性将特征进行聚类分析，然后从每个聚类簇中选择和类标最相关的特征组成最终的特征子集。经实证对比，能较好的降低冗余度，并提高预测效率。目前缺陷预测领域的特征选择大部分考虑无关特征，较少考虑冗余特征，上述文献结合聚类和特征排序的方法能够移除部分冗余特征，但建立在簇内排序基础上的特征选择仍有冗余特征存在，本文方法改进了这一点，在簇内进行基于分类器性能的特征子集选择方法，可进一步去除更多的冗余特征，减少了运行时的时间、空间开销，并经实例验证，还进一步提高了分类预测的精度。

2 传统特征聚类方法

聚类方法是一种无监督学习方法，主要依据样本相互之间的依赖程度进行划分，帮助分析和提取隐藏在其中的潜在规律。聚类的划分标准就是样本间的相关性，其度量标准大概可分为四种：距离度量、信息度量、依赖性度量和一致性度量。

距离度量利用距离来定义样本之间的相似度，距离越近，样本间相似度越高。常用的距离度量有欧式距离、S阶Minkowski度量、Chebychev距离、平方距离等。其中欧氏距离可以看作是2阶Minkowski距离。

信息度量引入了信息论中不确定性度量的熵函数作为评价标准，从特征分类的角度来看，不确定性越小，特征分类越准确。通常采用信息增益（IG）衡量一个特征区分样本类别的能力。信息增益定义为先验概率与后验概率之间的不确定性差异，对于两个随机变量X、Y，它们之间的信息增益IG（XIY）使用信息熵来计算：

信息增益不仅可以用来计算两个随机变量间的相关性，也可以用来衡量变量与类别间的相互关系。FCBF （fast correlation-based filter）是基于相互關系度量的一种算法，采用SU（非线性的对称不确定性）来度量特征间相关性：

依赖性度量既可以利用相关系数，找出特征和类别之间的相互关系;又可以利用特征之间的依赖关系，来表示特征的冗余性。Hall给出一种既考虑了特征的类区分能力，同时又考虑特征间冗余性的相关性度量标准。

一致性度量和训练数据集关系密切，主要是找到与全集有同样区分类别能力的最小子集，但由于其对噪声数据敏感，且只适合离散特征，应用较少。典型算法有Focus，LVF等。

基于聚类的特征选择方法一般与特征排序结合，样本聚类过程结束后，在每一个聚类中按照单个特征与类别间的相关性进行排序，选择指定数量的特征，组成最终的最优子集，构建软件缺陷预测模型，但通常这类方法效果不佳。因为从聚类中选择特征时，选择了和类标最相关的特征组成最终的特征子集。然而，每个聚类中不只保留一个特征，而且保留的特征和类标的相关性都较大，因此最终选择的特征子集中仍有一定的冗余信息。

3 聚类特征子集选择方法

本文方法不同于传统的特征聚类方法，因为特征聚类是将冗余性大的特征聚为一类，那么类间特征，尤其是经过与类标相关性排序选择出的几个特征，可能有较大概率存在冗余。由此启发，本文采用在聚类中进行包装式的特征子集选择，这样选择出组合效果最大的一组特征子集，而不是单个效果最好的特征之间的累加。以分类器效果作为评价指标，选择出最适应分类器的特征子集。

3.1 算法框架

聚类特征子集选择方法的思想是：通过先对原始样本数据集进行聚类分析，将相似度高的样本聚为一类，随后，在每一个聚类中，进行特征子集选择，这样降低了子集搜索的空间，提高了搜索效率，挑选出的特征间也有更低的冗余度。算法基本框架如图1所示。

3.2 特征聚类方法

聚类分析是根据数据对象间的相似性将其分到不同聚类中的过程。总之，同一聚类中样本的相似性越高，不同聚类间样本相似性越小，则聚类效果越好。本文采用K-means聚类算法，使用欧式距离作为度量方式。欧式距离计算公式如公式（5）所示：

其中X，Y分别是两个Ⅳ维特征向量，距离D（X，y）越小，目标间相似度越大。采用欧式距离，首先计算简单明了，收敛速度快以及局部搜索能力强等特点，整个聚类过程比较简单，时间复杂度近似线性。具体如算法1所示。

在此算法中，我们选择k=2作为聚类簇的个数。因为在软件缺陷预测领域，一般将软件模块分为有缺陷倾向性和无缺陷倾向性，相应的聚类簇的类标应为有缺陷标记和无缺陷标记，所以我们将样本数据聚为两个簇。

3.3 特征子集选择方法

包装式子集选择方法首先要用搜索算法挑选出子集，再使用评价算法判断评价当前子集是否满足要求。搜索时可以将单个特征作为初始候选子集，选出最优的候选子集后不断加入新的特征进行评价，直至评分不再增加，得到最优子集。

特征子集选择主要目的是挑选与类别关系密切且相互之间相关度较低的特征，因此不仅要度量任两个特征间的相关性，还要度量特征与类别的相关性。基于关联规则的特征选择算法（correlation-based feature selection： CFS）就是这样一种基于相关性的度量方式。下面从特征子集选择的四要素方面具体叙述：

1.搜索起点和方向：实验中从一个空集开始，进行带回溯的前向式搜索。

2.搜索策略：每次加入新的特征，判断当前特征子集的预测效果是否优于原特征子集。

3.特征评估函数：根据属性子集中每一个特征的预测能力以及它们之间的关联性进行评估，倾向于选择与类别的相关性高，相互之间关联度低的特征。相关度量计算方法见公式（6）：

4.停止准则：预测效果超过给定阂值（>0.6）且不再增加为止。

本文通过结合K-means聚类算法，用极小的系统代价改善了包装式特征子集选择方法的搜索空间大，计算开销大的缺点，并能获得低冗余率的特征子集，且对后续预测模型的性能也有提高。

4 实验内容与结果

4.1 数据集

研究中使用的是NASA（美国国家航空航天局）的MDP项目数据集。MDP是由NASA提供的一个软件度量库，存储了模块（函数/方法）级的度量数据和相关的缺陷数据。该公开缺陷数据信息库，为不同研究者以及不同的缺陷预测方法，提供了可供比较的基准。本文选择MDP公开数据集，以便于和其他算法比较，同时能让其他研究者重复本文方法，进行比较改进。本文获取了Promise库中11个数据集的项目数据，具体信息如表2所示。

4.2 实验流程

本文提出的聚类特征子集选择方法称为Fea-ture Cluster and Subset Selection （FCASS），此外，为证明本文方法的有效性，实验对比了传统的特征选择方法FC-Ranking （Feature Cluster and Ranking），即先进行聚类分析，随后在聚类中根据信息增益计算出每个特征与类标间的相关性，并按照相关性从大到小排序，保留[Log2M]的特征。按照Gao等人[4]的建议，保留[Log2M]的特征可使特征子集包含信息最大化的同时含有较低的冗余率。此外，不经特征选择过程，直接使用全部特征集（FullSet）构建模型也作为证明特征选择必要性的对比实验。

首先由不同的特征选择方法进行处理得到最优子集，然后在原始样本数据集中只保留最优子集中的特征，得到新的样本数据集。实验采用十折交叉验证，具体方法是将新的样本数据集随机划分为10份，其中的9份作为训练集，l份作为测试集。实验重复10次，确保每个实例都被预测过一次，最终取10次运行结果的平均值。最后基于训练集构建软件缺陷预测模型。后续预测模型我们采用weka平台的朴素贝叶斯（Naive Bayes）分类模型，分类器参数为默认值。

4.3 评价标准

在软件缺陷预测领域，常常用混淆矩阵的相关指标对分类器性能进行评价。缺陷预测中不同类别的實例误分的代价是不同的，本文主要关注精确率（Precision，简称P）、召回率（Recall，简称R）和F-measure等评价度量指标。

精确率和召回率本身有一定局限，难以单独评价分类器性能的优劣，F度量是精确率与召回率的调和平均值，可以对精确率和召回率这两个指标进行有效的平衡，其取值越高，表明模型预测效果越好。其计算公式为：

4.4 结果分析

针对软件缺陷预测领域的特征聚类选择方法，主要考虑两个问题：一是使用特征选择是否降低了特征维度;二是经过特征选择是否提高了缺陷模块的预测精度？

表4为经不同特征选择方法进行选择后剩余的特征个数，由表可知，经过特征选择明显降低了特征维度，本文提出的FCASS方法平均降低了81.8%，传统特征聚类方法FC -Ranking平均降低了83.2%。实事求是地讲，因为传统特征选择方法总是选择[Log2M]个特征，在特征数量以数十计时，比较有优势，当特征更高维度时，包装式特征子集选择方法的优势会越来越明显。

运用三种不同特征选择方法，构建缺陷预测模型，预测结果如表5所示。从表5统计结果可知，本文方法FCASS对缺陷模块的预测精确度在0.673 -0.967之间，平均值为0.83，其中仅有MC2数据集上是0.7以下，其余均在0.7以上，尤其PC5软件缺陷集达到了0.967的精确度。在召回率方面，除KC1、MC2数据集外，其余均优于传统特征聚类选择方法和全集方法，平均值最高为0.847。F度量指标上，FCASS方法显著优于传统特征聚类方法和全集方法，Fl值介于0.673 -0.969之间，平均值为0.835，在PC5数据集上，达到最高0.969。值得注意的是PC3数据集上，全集方法的精确度较高，但召回率差，两者的调和平均值Fl值不如本文FCASS方法和传统特征聚类方法。由此可见单一指标难以反映模型的优劣。

由图2的综合指标F度量值可知，基于聚类的特征子集选择方法构建的模型整体预测效果优于特征全集构建的模型和传统先聚类后排序构建的模型，同时，传统先聚类后排序方法又优于特征全集构建的模型，证实了对样本数据集进行特征选择的必要性，以及样本聚类在特征选择过程中的作用。

5 结束语

本文针对软件缺陷预测领域，样本数据集中存在特征维度高、相互间有冗余的问题，提出了结合聚类分析和特征子集选择的方法，首先对样本进行聚类，这样可以将具有冗余关系的样本集中在同一聚类中，同时有效降低了子集搜索空间，改善了传统特征选择计算开销大的问题;其次再对每一个聚类簇进行特征子集选择，选择出组合效果最大的一组特征子集，而不是单个预测效果较好的特征的累加。经实例证明本文方法不仅降低了特征子集的冗余率，并能有效提高预测的准确度。在后续工作中，我们将对其他特征相关性度量方法做进一步研究，比较其对缺陷预测性能的影响。

参考文献

[1]陈翔，顾庆，刘望舒，等.静态软件缺陷预测方法研究[J].软件学报，2016，27（1）：1-25

[2]王青，伍书剑，李明树.软件缺陷预测技术[J].软件学报.2008，19 （7）：1565-1580

[3]刘望舒，陈翔，顾庆，等，软件缺陷预测中基于聚类分析的特征选择方法[J].中国科学：信息科学，2016，46：1298-1320

[4] GAO K H，KHOSHCOFTAAR T M， WANC H J，et al.Choos-ing software metrics for defect prediction：an investigation on fea-ture selection techniques [J]. Software-practice& Experience：2011，41（5）：579-606

[5] GUO L，MA Y，CUKIC B，et al.Robust prediction of fault-proneness by random forestsECl.ISSRE，IEEE，2004：417-428

[6] MENZIES T，GREENWALD J，FRANK A.Data ruining staticcode attributes to leam defect predictors [C].IEEE Transactionson Software， 2007，32：1-12

[7] WANC H J，KHOSHCOFTAAR T M，NAPOLITANO A.A com-parative study of ensemble feature selection techniques for soft-ware defect prediction [C]. Proceedings of the Intema-tionalConference on Machine Learrung and Applications， Washing-ton， 2010：135-140

[8] MlrIRA P，MURTHY C，PAL S.Unsupervised feature selectionusing feature similarity[C].IEEE Transactions on Pattem Analy-sis and Machine Intelligence，2002：24 （3） ，301-312

[9] LIU Shu-long， CHEN Xiang，LIU Wang-shu.FECAR：A Fea-ture Selection Framework for Software Defect Prediction [C].IEEE 38th Annual International Computers， Software and Ap-plications Conference， 2014：426-435

[10] ZHANC Hong-yu.An Investigation of the Relationships betweenLines of Code and Defects [C].IEEE Intemational Conference onSoftware Maintenance， 2009： 274-283

[11] DUBEY V-K，SAXENA A-K，SHRIVAS M-M.A Cluster-FilterFeature Selection Approach [C].ICTBIC，IEEE，2017： 1-5

[12] MENZIES T，GREENWALD J，FRANK A.Data Mining StaticCode Attrihutes to Leam Defect Predictors [C]. IEEE Transac-tions on Software Engineering，2007，33（1）：2-13

[13]王培，金聪.面向软件缺陷预测的互信息属性选择方法[J].计算机应用，2012，32 （6）：1738-1740

[14]王连喜，蒋盛益.一种基于特征聚类的特征选择方法[J].計算机应用研究，2015 （5）：1305-1308