过采样与集成学习方法在软件缺陷预测中的对比研究

王 海,江 峰,杜军威,赵 军

(1.青岛科技大学信息科学技术学院，山东 青岛 266061； 2.青岛科技大学档案馆，山东 青岛 266061)

0 引 言

近年来，作为数据挖掘领域的一种特殊情况，不平衡数据的分类问题受到了广泛关注。不平衡数据是指数据集中某个或某些类别样本的数量要远远多于其他类别，通常把样本数量较多的类别称为多数类(也称负类)，样本数量较少的类别称为少数类(也称正类)。在很多实际应用中，少数类样本所包含的信息可能更加关键，例如，分辨非健康广告、入侵检测、欺诈检测、医疗诊断等。因此，在这些应用中，人们更加关注具有重要价值的少数类样本。

软件缺陷是指软件未满足预期或者规定用途有关的要求，从而导致软件系统出错甚至崩溃。软件缺陷预测是根据历史数据以及已发现缺陷等软件度量数据，预测出有出错倾向的模块，它对降低研发成本、合理配置资源具有重要意义。

软件缺陷预测[1]中普遍存在类别不平衡[2]问题。例如在NASA MDP (Metric Data Program)数据集中，有缺陷样本数占整个样本数的比例最多也不超过20%，正负类样本比例严重失衡。目前，针对类别不平衡问题的研究已成为机器学习以及数据挖掘中的一个重要研究方向，具有较大的实用价值。不平衡数据的处理方法有很多，主要分为2大类：数据层面和算法层面。从数据层面来看，不平衡数据的处理方法主要包括：欠采样方法和过采样方法。另外，从算法层面来看，不平衡数据的处理方法主要包括：代价敏感学习、集成学习算法等。

针对软件缺陷预测[3]中类别不平衡问题的处理，本文同时将数据层面和算法层面的方法有效地结合在一起，从而获得更好的缺陷预测性能。首先，在数据层面，本文主要关注于过采样方法；其次，在算法层面，本文主要考虑集成学习算法。近年来，不同的过采样方法和集成学习方法已被用于缺陷预测中不平衡数据的处理。简艺恒等[4]提出了一种基于数据过采样和集成学习的软件缺陷数目预测方法——SMOTENDEL，通过训练得到一个组合软件缺陷数目预测模型，对新的软件模块进行缺陷预测。Malhotra等[5]提出了SPIDER3过采样方法，通过应用该采样方法和代价敏感的分类器评估机器学习分类器对NASA数据集的缺陷预测的有效性。戴翔等[6]提出了一种处理不平衡数据的采样方法，利用启发性的混合采样方法来平衡数据,然后综合多个单分类器来进行投票集成预测分类。

作为数据层面和算法层面上2类具有代表性的不平衡数据处理方法，非常有必要将过采样[7]方法与集成方法结合起来，从而有望构造出一种更加有效的不平衡数据处理方法。因此，本文研究如何把过采样方法和集成学习方法更好地组合在一起，从而为缺陷预测中类别不平衡问题的处理提供一种新途径。对此，本文专门选取了4种典型的过采样方法：1)随机过采样(RandomOverSampler)[8]；2)合成少数类过采样技术(Synthetic Minority Oversampling Technique, SMOTE)[9]；3)Borderliner-SMOTE[10]算法；4)自适应综合过采样技术(Adaptive Synthetic Sampling Approach, ADASYN)[11]。另外，还专门选取了4种典型的集成学习方法：1) Bagging算法；2) Random Forest算法；3) AdaBoost算法；4) GBDT[12]算法。本文分别从上述8种方法中随机选择一种过采样方法与一种集成学习方法，将这2种方法组合在一起，从而形成不同的组合。通过对比每一种组合的缺陷预测性能，从而获得最优组合，为缺陷预测中不平衡问题的处理提供有益参考。

本文在NASA MDP软件缺陷预测[13]数据集上进行大量实验，实验结果表明，ADASYN方法在所有过采样方法中表现最好，相对于其他过采样方法，ADASYN能够更好地处理缺陷预测中的不平衡问题。另外，ADASYN与集成学习方法GBDT的组合具有比其他组合更好的软件缺陷预测性能，更适合用于软件缺陷预测[14]中不平衡数据的处理。

1 4种类型的过采样方法

过采样是对不平衡数据进行重采样的常用方法，它通过增加少数类样本个数，从而改善类别平衡度。目前，典型的过采样方法主要有4类。

1.1 RandomOverSampler

针对不平衡数据,最简单的一种过采样方法就是随机过采样，具体而言，从少数类样本中进行随机采样来增加新的样本，随机地复制、重复少数类样本，最终使得少数类与多数类的个数相同，从而得到一个新的平衡的数据集。

1.2 SMOTE

SMOTE[15]是基于随机过采样算法的一种改进方案，SMOTE算法的基本思想是对少数类样本进行分析并根据少数类样本人工合成新样本添加到数据集中。SMOTE算法的步骤如下：

1)对于少数类中每一个样本a，计算它到少数类样本集中所有样本的欧氏距离，得到其k个最近邻。

2)根据样本不平衡比例设置一个采样比例以确定采样倍率N，N的计算公式如式(1)：

N=round(ID)

(1)

其中，ID为多数类个数与少数类个数比值。

3)对于每一个少数类样本a，从其k近邻中随机选择若干个样本。

4)对于每一个随机选出的近邻yi，分别与原样本按照如下的公式构建新的样本mi：

mi=a+rand(0,1)×(yi-a)，i=1,2，…，N

(2)

其中，a表示少数类样本；rand(0, 1)表示(0, 1)之间的一个随机数；yi表示a的N个最近邻样本中的第i个样本。

5)将原始样本集与新合成的少数类样本集合并起来，组成新的样本集。

1.3 Borderline-SMOTE

Borderline-SMOTE[16]与原始SMOTE不同的地方在于，它先根据规则判断出少数类的边界样本，再对这些样本生成新样本，即它只是过采样或加强边界少数类的样本数。合成样本的方式如下：

syntheticj=y′i+rj×dj，j=1,2,…，m

(3)

其中，dj表示y′i与其m个近邻的距离；rj是介于0～1间的随机数；将最终所得的少数类样本与原始的样本集合并成新的样本集。

1.4 ADASYN

ADASYN算法的目的是通过现有少数类样本之间的线性插值综合创建少数类的新样本来改善类平衡，它关注的是在那些基于k最近邻分类器被错误分类的原始样本附近生成新的少数类样本。算法步骤如下：

1)计算不平衡度。记少数类样本数量为ms，多数类样本数量为ml，则不平衡度为d=ms/ml，则d∈(0,1)。

2)计算需要合成的样本数量：

G=(ml-ms)×b，b∈[0,1]

(4)

其中，b是用于指定生成合成数据后所需的平衡参数。当b=1时，G等于多数类与少数类的差值，此时，合成数据后的多数类个数和少数类个数正好平衡。

3)用欧氏距离计算少数类的k个邻居，并计算比例ri=△i/k，△i为k个邻居中属于多数类的样本数目。

4)计算每个少数类样本的周围多数类的情况：

(5)

5)对每个少数类样本计算合成样本的数目：

gi=ri′×G

(6)

6)在每个少数类样本周围k个近邻中选择1个少数类样本，根据下列等式重复合成直到满足步骤5的数目：

si=xi+(xzi-xi)×λ，λ∈[0,1]

(7)

其中，xi表示少数类样本，xzi表示在k个近邻中所选择的一个少数类样本，si表示合成的样本，λ表示0～1之间的随机数。

2 4种典型的集成学习算法

集成学习是指使用一系列学习器进行学习，并使用某种规则把各个学习结果整合起来从而获得比单个学习器更好的学习效果的一种机器学习方法。目前，典型的集成学习方法主要有4类。

2.1 Bagging算法

Bagging[17]是并行式集成学习的代表方法。Bagging算法的基本思想是基于“自助采样法”(bootstrap sampling)来对训练集进行扰动。Bagging的主要步骤有：首先，通过自助采样法产生T个不同的采样集，其中，每个采样集都包含m个样本；然后，基于每个采样集训练出一个基学习器；最后，将T个基学习器组合在一起，从而得到集成学习器。

2.2 随机森林(Random Forest)算法

随机森林算法的思想是在Bagging算法的基础上，增加随机属性选择这一步骤。在随机森林算法中，对基决策树的每个节点，先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优的属性作为划分属性。在上述过程中，参数k控制了随机性的引入程度，若令k等于全体属性的个数，则随机森林算法所构建的基决策树与传统决策树[18]一致。

2.3 AdaBoost算法

AdaBoost是最著名的Boosting[19]族算法。AdaBoost算法的基本流程如下：首先，在第一轮，所有样本的权重都相同，通过训练得到第一个基学习器；然后，从第二轮开始，每轮开始前都先根据上一轮基学习器的性能来调整每个样本的权重，上一轮分错的样本其权重将提高，分对的样本其权重将减少。根据新得到的样本权重来指导本轮基学习器的训练，即在考虑样本权重不同的情况下得到本轮错误率最低的基学习器。重复以上步骤直至训练到约定的轮数结束，每一轮训练得到一个基学习器。因此，远离边界的样本点总是分类正确，而分类边界附近的样本点总是有大概率被基学习器分错，所以权值会变高，即边界附近的样本点会在分类时得到更多的重视。

2.4 GBDT算法

GBDT(Gradient Boosting Decision Tree)又叫梯度提升树,它是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论加起来作为最终答案。它的思想是每次建立模型是在之前建立的模型损失函数的梯度下降方向。GBDT的提升方法采用的是加法模型与前向分布算法,以决策树为基函数的提升方法称为提升树，对分类问题决策树是二叉分类树，对回归问题决策树是二叉决策树。GBDT与AdaBoost最主要的区别在于，AdaBoost用错分数据点来识别问题，通过调整错分数据点的权重来改进模型，GBDT通过负梯度来识别问题，通过计算负梯度来改进模型。

3 实 验

3.1 实验数据

本实验采用美国国家航空航天局(NASA)的MDP(Metric Data Program)项目中的8个软件缺陷预测数据集CM1、JM1、KC1、KC3、MW1、PC1、PC3、PC4。美国国家航空航天局很早便基于航空系统软件开展了软件模块的度量数据库项目MDP，从而为软件缺陷预测的研究提供了数据支撑。表1显示了NASA MDP数据集的基本信息。

表1 NASA数据集

3.2 评价指标

软件缺陷预测模型的评价指标有：精确率(Precision)、召回率(Recall)、F1-measure。这些指标都是基于表2所示的二分类数据集的混淆矩阵。

表2 混淆矩阵

1)精确率(Precision)，查准率。即正确预测为正类样本数量与所有被预测为正类样本的数量的比值。

(8)

2)召回率(Recall)，查全率。即正确预测为正类样本数量与样本集中全部正类样本的数量的比值。

(9)

3)F1-measure是分类问题的一个衡量指标。它是Precision和Recall的加权调和平均，当F1-measure较高时说明实验方法比较理想，当二者之一过小时，F1-measure也会非常小，进而提示模型异常。

(10)

3.3 实验设置

实验选择RandomOverSampler、SMOTE、Borderline-SMOTE、ADASYN这4种过采样方法，以及Bagging、Random Forest、AdaBoost、GBDT这4种集成学习方法。实验过程中，分别将上述4种过采样方法与上述4种集成学习算法进行一一搭配，总共构建出16种组合用于软件缺陷预测。针对每一种组合，分别获取该组合在不同数据集上的软件缺陷预测效果，进而分析、比较该组合与其他组合在处理不平衡问题方面的性能差异。实验从原始数据集中随机选取50%作为训练集，剩下的50%作为测试集，这里的基学习器采用CART算法进行训练。

实验在Win 10操作系统下进行，所涉及的过采样算法和集成学习算法均使用Python语言进行编写。实验中对数据进行离散化处理，运用4种过采样方法均将正类样本数量增加到数据总量的50%(即4种过采样方法均对数据集中正类数据进行过采样，使得正类数据的数量占总体数量的50%，从而达到正负类比例为1:1平衡)。实验的基学习器的个数统一设为10。本文的实验通过比较F1-measure值来比较各种组合的优劣。本文关于软件缺陷预测[20]的对比研究都是针对不平衡数据进行的，为了更好地比较这几种组合在对不平衡数据进行缺陷预测[21]时的优劣，统计的实验结果都是正类样本的预测结果。

3.4 实验结果与分析

在表3～表6中，Bagging、RF、AdaBoost、GBDT分别表示集成学习算法Bagging、Random Forest、AdaBoost和GBDT。在获取表3中的实验结果时，先利用RandomOverSampler方法进行过采样，再利用不同的集成学习算法进行缺陷预测[22]。类似地，在获取表4～表6中的实验结果时，先分别利用SMOTE[23]、Borderline-SMOTE、ADASYN方法进行过采样，再利用不同的集成学习算法进行缺陷预测。

以下为不同组合的缺陷预测实验结果表和折线图：

表3 原始(未采样)数据集上不同集成学习算法的F1-measure

表4 RandomOverSampler+不同集成学习算法的F1-measure

表5 SMOTE+不同集成学习算法的F1-measure

表6 Borderline-SMOTE+不同集成学习算法的F1-measure

表7 ADASYN+不同集成学习算法的F1-measure

从表3与表4～表7的实验结果对比可以看出，运用了过采样算法的软件缺陷预测F1-measure值要明显高于未经处理的原始数据集的软件缺陷预测F1-measure值，这说明过采样算法在处理不平衡数据方面具有优势。再对比表4～表7这4个不同过采样[22]方法与不同集成学习算法组合的F1-measure值结果，可以看出，过采样算法ADASYN与GBDT算法相结合的总体预测效果要好于其他过采样方法与集成学习算法的组合。综上，可以得出结论：在进行软件缺陷预测时，采用ADASYN算法与GBDT算法相结合的方式能够获得最理想的软件预测效果[24]。

4 结束语

本文主要考察了RandomOverSampler、SMOTE、Borderline-SMOTE、ADASYN这4种过采样方法与Bagging、Random Forest、AdaBoost、GBDT这4种集成学习方法的不同组合在处理软件缺陷预测中不平衡问题上的性能优劣。通过将上述过采样方法与集成方法两两组合在一起来进行缺陷预测，并采用F1-measure作为性能评价指标，从而为缺陷预测中不平衡问题的处理提供了有益参考。通过在8个NASA数据集上进行实验，本文得出如下结论：过采样方法ADASYN与集成方法GBDT的组合能够为软件缺陷预测中不平衡数据的处理提供最有效的结果[24]。

在下一步的工作中，笔者将引入更多最新的过采样方法与集成学习方法，并考虑过采样与代价敏感学习的组合问题，即将不同的过采样方法与代价敏感学习方法组合在一起，从而为软件缺陷预测中不平衡数据的处理提供更多的途径。