论文部分内容阅读
摘要：软件缺陷预测技术通过分析软件静态信息，对软件模块的缺陷倾向性做出判断，合理分配测试资源。但有时搜集的大量度量元信息是无关或冗余的，这些高维的特征增加了缺陷预测的复杂性。文章提出了一种新的度量元选择方法，首先通过样本聚类将相似度高的样本聚在同一簇中，然后在每个簇中按照最低冗余度进行特征子集的挑选，主要选择相互间冗余度低，且预测能力强的度量元。最后通过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.停止准则：预测效果超过给定阂值（
关键词：软件缺陷预测;特征选择;特征聚类
中图法分类号：TP311
文献标识码：A
1 引言
随着现代信息技术的发展，软件规模不断增长，程序复杂度不断提高，致使软件中隐藏的缺陷也越来越多，由此引发的软件故障给国家、给企业带来了不可估量的损失。软件缺陷预测技术从20世纪70年代发展至今，一直备受关注。软件缺陷预测技术可以分为静态缺陷预测技术和动态缺陷预测技术[1]。静态缺陷预测技术主要分析软件静态信息，利用与缺陷相关的度量元，准确预测出软件模块的缺陷数量或缺陷分布情况。这样在软件测试时可以合理分配测试资源，给软件质量保证提供了重要的途径。
在分析软件模块时，有大量的软件度量元（即特征）可以提取，而特征间是存在冗余关系的，即一个特征可以由其他一个或几个特征信息推导出来。这些冗余特征将影响构建预测模型的效率，甚至还会降低预测模型的准确度[2]。因此使用特征选择或提取的方法移除这类特征有重要研究意义。
特征选择就是从一组数量为Ⅳ的特征中选择出数量为M的最优特征，其中M
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.停止准则：预测效果超过给定阂值（