一种软件缺陷不平衡数据分类新方法

刘文英，林亚林，李克文，雷永秀

(中国石油大学(华东) 计算机科学与技术学院，山东 青岛 266580)

对软件缺陷预测的研究表明，80%的缺陷集中发生在20%的模块中，这说明软件系统中的数据分布是不平衡的，有缺陷模块的数量远远少于无缺陷模块的数量。虽然有缺陷类样本的数量很少，但正确识别有缺陷样本是软件缺陷预测的关键，错误预测有缺陷样本可能会导致遗漏关键错误从而增加软件开发成本。因此，解决不平衡数据问题对于提高软件质量、减少预测误差和成功部署软件具有重要意义。

不平衡数据处理[1]是机器学习研究中的热点之一，更是软件缺陷预测方向不可或缺的部分，已有不少学者专注于不平衡数据的研究。目前公认的解决不平衡数据问题的方法是从数据和算法两个层面进行的。数据层面通过采样方法进行处理，算法层面通过应用集成分类算法、代价敏感算法等处理数据。例如，Patel等[2]提出合并自适应K最近邻和模糊K最近邻的方法来提高不平衡数据的分类性能。Marwa等[3]提出一种多目标进化方法优化倾斜决策树，并将其应用到不平衡数据分类。Liu等[4]提出了两阶段成本敏感学习方法，该方法将成本信息处理分为特征选择和分类两个阶段。Rodriguez等[5]比较了成本敏感算法、采样方法、混合技术和集成技术来处理不平衡数据集，结果表明，不平衡数据经过处理后提高了预测模型的性能。Ruchika等[6]提出一种新的过采样算法SPIDER3，并将采样算法与成本敏感分类器结合使用，解决缺陷数据集的不平衡问题，提高预测模型的性能。Siers等[7]提出成本敏感决策树和成本敏感投票两种技术来处理不平衡数据问题，还结合SMOTE过采样方法来优化决策森林进行软件缺陷预测。张忠林等[8]提出一种融合了阈值移动技术和Bagging算法的PT-Bagging集成算法，相较于Bagging算法，所提算法在处理不平衡数据时具有更好的性能。Yuan等[9]提出一种新的集成学习算法SE-gcForest，在gcForest算法基础上结合SMOTE和EasyEnsemble来处理不平衡数据。

随着实际软件系统复杂度越来越高，相应的软件缺陷预测面临的数据不平衡问题也越来越突出，目前已出现了一些关于软件缺陷预测与不平衡数据相结合的研究，但是采样技术、特征降维、软件缺陷预测模型等仍然存在很多问题值得去探索。由于混合采样技术理论上同时具备欠采样和过采样的优点，本研究提出一种改进的RUS-RSMOTE混合采样方法，克服SMOTE算法合成新样本时随机数取值不精确的缺点，引入影响因素posFac对随机数进行约束，在此基础上结合随机欠采样技术，对不平衡的软件缺陷数据集进行处理，并利用F-value、AUC、G-mean对不平衡的软件缺陷数据分类结果进行评价。

1 相关算法

1.1 随机欠采样(Random under-sampling, RUS)

欠采样技术通过一定的规则或公式减少多数类样本的数量，改变不平衡数据集的样本分布，缓解数据集的不平衡程度，降低计算成本。随机欠采样、压缩最近邻[10]、Tomek links方法以及邻域清理都是常用的欠采样方法。

随机欠采样通过删除数据集中的多数类样本实现类分布均衡的目的，进而提高分类模型的效率，但是由于删除多数类样本的过程具有随机性、偶然性，容易使重要信息丢失，降低学习器的分类效果。例如，NASA发布的软件缺陷数据集PC2中有5 589个样本，其中23个(缺陷率0.41%)为有缺陷样本，5 566个为无缺陷样本，不平衡率高达242，若使用随机欠采样技术实现1∶1(无缺陷样本数∶有缺陷样本数)的数据分布，那么经过随机欠采样处理后的新数据集只有46个样本(23个无缺陷样本和23个有缺陷样本)。图1是某一不平衡数据集经过随机欠采样前后的样本分布图。

图1 随机欠采样前后样本分布图

1.2 SMOTE

SMOTE算法是最具代表性的过采样算法，通过相邻少数类样本间线性插值生成新样本[11]，从而改变不平衡数据集的类分布情况。SMOTE算法通过少数类样本间线性插值的方式生成新样本，克服了随机过采样由于单纯复制少数类样本而导致分类器过拟合的现象，但也存在两个方面的问题，一是增加了数据集样本量，从而增加了分类器训练时间；二是函数rand(0,1)取值范围过大，未进行精细控制，导致新合成样本质量无法得到保证。

过采样技术和欠采样技术都是通过改变样本数量来改变类分布，从而缓解不平衡数据集的样本分布情况，降低不平衡率。这两种采样技术都有各自的优缺点，目前关于两种技术的比较尚未形成统一的定论。而混合采样技术[16]将欠采样和过采样结合起来，首先对不平衡数据集进行欠采样，然后在此基础上进行过采样。混合采样可以是欠采样和过采样具体方法中任意两种的组合体。

1.3 主成分分析

主成分分析(principal components analysis,PCA)实质是用一组正交向量对原始特征进行变换得到新特征，且新特征间互不相关。数据本身决定着数据从原来的坐标系转换到新坐标系，第一个新坐标轴是由原始数据中方差最大的方向确定的，第二个新坐标轴是由和第一个新坐标轴正交并且方差最大的方向确定的，不断重复该过程，使得重复次数等于原始数据中的特征数d，得到投影变化后的新坐标轴为{w1,w2,…,wd}。研究发现，大部分方差都包含在最开始的{w1,w2,w3，…，wd′}几个坐标轴中，剩下的坐标轴可以忽略，将维度从d降低到d′实现特征降维，也可以设置一个重构阈值t，选择占原始数据的方差中一定百分比的特征向量，t一般取95%。PCA适用于对数值型数据进行处理，优点是仅需识别最重要的多个特征来降低数据的复杂性，缺点是有可能损失重要信息。

1.4 Vote

集成分类器通过某种策略结合多个单分类器来完成学习任务，实际上是一种组合分类器的方法，集成分类器的结构如图2所示。如果把单分类器看作是一位决策者，那么集成分类器相当于综合多个决策者的智慧来解决问题。集成分类器可以根据分类器的类型分为同质集成和异质集成，同质集成是由类型相同的单分类器结合而成，例如“决策树集成分类器”中的单分类器都是决策树；异质集成是由类型不同的单分类器结合而成，例如同时包含决策树和朴素贝叶斯的集成分类器。在不平衡的软件缺陷数据集上应用集成分类器，可以使得集成分类器的泛化能力明显高于单分类器，避免过拟合现象的发生，有效地降低了单分类器在不平衡数据分类时所产生的偏差[12]。

图2 集成分类器结构

Vote是一种集成分类器结合策略，包括三种投票方法：相对多数投票法即少数服从多数，预测结果是得票最高的类；绝对多数投票法要求最终预测类别所得票数过半；加权投票法将每个类别的票数进行加权求和，结果最大的类别即为预测结果。投票策略既可以集成相同类型的分类器，又可以集成不同类型的分类器，因此可以使用投票策略构建异质集成分类器，综合多个分类器的优势构建预测模型。

本研究利用5种集成技术(如表1)来构建软件缺陷预测模型。

2 基于RUS-RSMOTE-PCA-Vote的软件缺陷不平衡数据分类方法

利用混合采样技术可以同时具备欠采样和过采样的优点，提出一种改进的RUS-RSMOTE混合采样方法。首先对原始缺陷数据集进行随机欠采样来减少无缺陷样本的数量；然后使用SMOTE算法进行过采样，同时考虑无缺陷样本分布的影响作用，融入影响因素posFac约束随机数rand(0,1)的取值。为解决不平衡数据集中的数据维度问题，将提出的RUS-RSMOTE与PCA相结合对软件缺陷数据集进行处理。首先对不平衡数据集进行RUS-RSMOTE混合采样，根据类别标记将样本划分为有缺陷样本和无缺陷样本，对无缺陷样本进行随机欠采样，对有缺陷样本进行RSMOTE过采样；然后对经过RUS-RSMOTE混合采样处理后的数据集进行PCA降维，将所有样本进行中心化，计算样本的协方差矩阵XXT并进行特征值分解，最后取前面最大的d′个特征值对应的特征向量进行降维。最后，应用Vote集成到的个体学习器，构建适合不平衡数据的软件缺陷预测模型。

表1 本研究采用的五种分类器及相关文献

2.1 改进的RSMOTE过采样方法

针对SMOTE算法合成新样本时随机数取值不精确的缺点，引入影响因素posFac对随机数进行约束[18]，使得新样本合成过程中的随机数取值更有针对性以更加合理地扩展少数类样本，使新数据集趋于平衡，提高分类器对于少数类样本的分类能力。影响因素posFac的计算如下：

1) 计算有缺陷样本xi与其K个同类近邻的平均欧几里得距离

(1)

2) 计算所有有缺陷样本xi与其K个同类近邻的平均欧几里得距离之和

(2)

其中，m表示有缺陷样本的数量。

3) 计算m个有缺陷样本与同类近邻的平均欧几里得距离和的均值

(3)

4) 计算有缺陷样本xi与其K个无缺陷样本近邻的平均欧几里得距离

(4)

5) 计算所有有缺陷样本xi与其K个无缺陷样本近邻的平均欧几里得距离之和

(5)

6) 计算有缺陷样本与无缺陷样本间的平均欧几里得距离和的均值

(6)

7) 计算当前被选中的边界样本与其K个同类近邻的平均欧几里得距离

(7)

8) 计算当前被选中的边界样本与其K个无缺陷样本近邻的平均欧几里得距离

(8)

9) 计算相对距离比

(7)

10) 得到影响因素

(8)

基于样本分布的RSMOTE算法描述：计算任意一个少数类样本xi到数据集中所有同类样本的欧几里得距离，接着寻找样本xi的K最近邻，根据采样倍率N从xi的K最近邻中随机选择N个样本与xi进行线性插值合成新样本xnew，假设xj为被选中的xi的K最近邻样本，新样本合成公式为xnew=xi+posFac(xj-xi)。

2.2 基于RUS-RSMOTE-PCA-Vote的软件缺陷不平衡数据分类方法

基于RUS-RSMOTE和PCA的特征降维框架如图3所示，相应的算法具体过程如下：

图3 基于RUS-RSMOTE和PCA的特征降维框架

输入：DataSet-原不平衡数据集；

输出：带有标记的分类结果。

//RUS-RSMOTE混合采样阶段：

根据类别标记将DataSet划分成DefectSet和NonDefectSet；

对数据集NonDefectSet按照预期达到的不平衡率进行随机欠采样，记为数据集newNonDefectSet；

有缺陷样本数m=DefectSet.size( )；

对数据集DefectSet进行随机化处理；

初始化随机变量i=0；

WHILEi

i++；

END WHILE；

newDataSet=newDataSet+DefectSet+new NonDefectSet；

//PCA降维阶段：

将所有样本xi进行中心化；

计算样本的协方差矩阵XXT并进行特征值分解；

对特征值按从大到小的顺序进行排序；

取前面最大的d′个特征值对应的特征向量w1,w2,…,wd′；

利用特征向量实现数据降维得到新数据集；

//Vote构建集成分类器阶段：

将经过前两个阶段处理后的数据集在朴素贝叶斯、决策树、支持向量机、K最近邻4种算法上进行分类；

分析所有数据集在朴素贝叶斯、决策树、支持向量机、K最近邻4种算法上的分类效果，确定最终用于集成的个体分类器，组合规则为“Average of Probabilities”。

3 实验设计与分析

3.1 实验对象

利用数据挖掘工具WEAK，使用NASA发布的软件缺陷数据集进行实验，实验数据集的具体情况见表2。

表2 用于实验的10个软件缺陷数据集基本信息

3.2 实验评价指标

通常情况下精准率(precision)和召回率(recall)是评价分类器性能的常用指标，但是对于软件缺陷预测模型而言，由于面临着数据不平衡问题，不适合使用上述两个指标进行模型评价，本研究使用F-value、AUC、G-mean作为评价指标。

F-value是精准率和召回率的调和均值，是不平衡数据分类问题中常用的评价指标，当精准率和召回率的取值都大时，F-value值才大，且值越大代表预测模型性能越好。计算公式为：

(9)

AUC(Area Under the Curve)表示ROC曲线与坐标轴所围成的面积，取值范围是0～1，是不平衡数据分类问题中常用的评价指标，AUC值越大，则预测模型的性能越好。

G-mean是有缺陷样本召回率和无缺陷样本召回率的几何均值，是衡量不平衡软件缺陷数据集整体分类情况的性能评价指标，只有当有缺陷样本和无缺陷样本的召回率都较大时，G-mean值才大，同样值越大代表预测模型性能越好。计算公式为：

(10)

表3 分类器情况统计

数据集中样本的预测结果要么是“有缺陷”要么是“无缺陷”，是一个典型的二分类问题，样本的预测类别与实际类别相比会产生4种结果(如表3)，TP表示正确分类的有缺陷样本数，TN表示正确分类的无缺陷样本数，FP表示实际为无缺陷类但被预测为有缺类的样本数，FN表示实际为有缺陷类但被预测为无缺类的样本数。

3.3 实验设计与结果分析

实验中的软件缺陷数据集不平衡程度较高，MC1数据集的不平衡率最高，为138.21，KC1数据集的不平衡率最低，为5.48。为降低不平衡率且最大限度的保持原始数据分布，设置欠采样后的不平衡率降为5，过采样的邻域值K取5。

为评估RUS-RSMOTE混合采样方法在不平衡数据集处理方面的有效性，将其与RUS[19]、SMOTE[20]、RSMOTE[18]、RUS-SMOTE[21]进行对比，选用CM1、KC1、KC3、MC1、MW1、PC2作为实验数据集，在经过采样处理后的新数据集上使用决策树(J48)构建软件缺陷预测模型，为保证客观性，所有实验采用十折交叉验证进行，选用F-value、AUC和G-mean作为验证RUS-RSMOTE混合采样方法在软件缺陷预测中的有效性的评价指标。

图4～6是6个软件缺陷数据集经过5种采样方法处理后的F-value、AUC、G-mean评价指标对应的柱状图。由图4可见，所有数据集经过RUS-RSMOTE算法处理后的F-value值普遍高于其他采样算法，在数据集KC3上尤为明显。由图5、6可见，除数据集CM1外，剩余5个数据集经过RUS-RSMOTE算法处理后的AUC、G-mean值的高于其他采样算法。

图4 不同算法上的F-value值对比

图5 不同算法上的AUC值对比

图6 不同算法上的G-mean值对比

综合三个评价指标来看，经过随机欠采样处理的不平衡数据集的性能最差，评价指标取值最低。RUS-RSMOTE算法与其他采样算法相比，在不平衡软件缺陷数据集上的F-value、AUC、G-mean值更高，证实了RUS-RSMOTE算法对于处理不平衡的软件缺陷数据集的有效性。

PC2数据集中某两种属性的数据分布如图7所示，图7(a)表示原始数据集分布，图7(b)表示在RUS-RSMOTE混合采样的基础上进行PCA特征降维后的数据分布。其中，红色标记表示无缺陷样本，蓝色标记表示有缺陷样本，可以看出图7(a)中的无缺陷样本远远多于有缺陷样本，样本的不平衡程度非常高，无法找到合适的分割线对样本进行分类，图7(b)的样本分布更适合分类器学习。

表4列出了经过RUS-RSMOTE混合采样和PCA降维后的10种数据集在朴素贝叶斯、决策树、支持向量机、K最近邻4种机器学习算法上进行分类的F-value、AUC、G-mean指标对比，表格中加粗以及下划线表示的数据代表值最高。F-value、G-mean值方面，K最近邻算法在10个数据集上均取得最大值；AUC值方面，K最近邻算法在除PC4之外的9个数据集上取得最大值。比较4种分类算法在F-value、AUC、G-mean 3个指标上的平均值发现，K最近邻算法的最大，决策树算法次之。综上所述，K最近邻算法在软件缺陷数据集上的分类性能最好，决策树算法次之，朴素贝叶斯和支持向量机的分类性能相对较差。而支持向量机算法的最终决策函数只由少数的支持向量所确定，鲁棒性较强。因此，将K最近邻、决策树、支持向量机利用投票机制Vote进行异质集成。

图7 PC2数据集的二维散点图

表4 不同算法上的评价指标对比

为了验证Vote集成分类器的性能，将其与Bagging、AdaBoostM1、RandomTree、RandomForest集成分类器进行对比，比较这些集成分类器在软件缺陷预测性能方面的差异;为了更好地体现分类效果，同时与性能较好的单分类器K最近邻(KNN)进行比较。其中，Bagging、AdaBoostM1为元分类器，使用K最近邻作为基分类器。为保证客观性，所有实验采用十折交叉验证进行，同样选用F-value、G-mean和AUC作为验证集成分类器在软件缺陷预测中的性能评价指标。

表5是10种软件缺陷数据集在6种分类算法上的F-value值对比。由表5可以看出：

1) 使用kNN作为基分类器的Bagging、AdaBoostM1在F-value值上几乎没有提高，应用Bagging、AdaBoostM1后的平均F-value值与kNN相等，甚至在应用Bagging后数据集KC1、MW1、PC1、PC3的F-value值反而略微降低。

2) Vote在9个数据集上具有最高的F-value值，平均F-value值为0.87；RandomForest次之，值为0.86。

表6是10种软件缺陷数据集在6种分类算法上的AUC值对比。由表6可以看出：

1) 使用kNN作为基分类器的Bagging在AUC值上有显著提升，而应用AdaBoostM1后数据集KC1、KC3、MC1、PC1、PC2、PC5的AUC值略微降低，平均AUC值也低于kNN。

2) RandomForest和Vote的AUC均值相等，值为0.94，相比其他分类器，在软件缺陷预测方面具有明显优势。

表5 不同算法上的F-value值对比

表6 不同算法上的AUC值对比

表7是10种软件缺陷数据集在6种分类算法上的G-mean值对比。通过观察可以得到如下结论：

1) 对比Bagging、AdaBoostM1和kNN发现， Bagging、AdaBoostM1几乎没有贡献，与单分类器的平均G-mean值相等。

2) 与AUC值情况一样，RandomForest和Vote在G-mean上的均值相等，值为0.89，相比其他分类器，这两种集成算法在软件缺陷预测方面具有明显优势。

图8～10是采用Vote、kNN算法在10个数据集上的F-value、AUC、G-mean对比。从图8可以看出，采用Vote进行分类的数据集中除PC1外，其他9个数据集的F-value值普遍高于kNN，在数据集PC4上尤为明显。从图9可以看出，两者在PC5数据集上的AUC值都是0.97，除此之外，采用Vote进行分类的AUC值明显优于kNN。图10的柱状图显示两者在3个数据集上的G-mean值相等，采用Vote进行分类的6个数据集的G-mean值高于kNN。综上所述，采用Vote集成K最近邻、决策树、支持向量机的分类器性能远远超过个体分类器kNN。

表7 不同算法上的G-mean值对比

图8 kNN和Vote的F-value值对比

图9 kNN和Vote的AUC值对比

图10 kNN和Vote的G-mean值对比

综合6种分类算法在F-value、AUC、G-mean 3项指标的表现来看，将K最近邻、决策树、支持向量机利用投票机制Vote进行异质集成的分类器在软件缺陷预测方面具有显著的性能优势。

4 总结与展望

为解决软件缺陷预测中存在的数据不平衡、特征维度高以及预测精度低等问题，提出了一种基于RUS-RSMOTE-PCA-Vote的软件缺陷不平衡数据分类方法，首先通过随机欠采样来减少无缺陷样本的数量，然后进行SMOTE过采样，在过采样中综合总体样本的分布状况引入影响因素posFac指导新样本的合成，对经过RUS-RSMOTE混合采样处理后的数据集进行PCA降维，最后应用Vote组合K最近邻、决策树、支持向量机构造集成分类器。实验结果表明，所提方法可以有效地解决软件缺陷预测中存在的数据不平衡、特征维度高以及预测精度低等问题。

由于综合考虑了软件缺陷数据存在的数据不平衡、特征维度高以及预测精度低等问题，因此本方法在时间复杂度上稍高于其他方法，接下来将探究不同运行参数对于软件缺陷预测的分类性能影响并提高运行速度。同时结合机器学习、深度学习的新技术进行不平衡数据处理，例如探讨生成对抗网络(generative adversarial networks, GAN)在数据扩充方面的应用等。