代价敏感的Boosting 软件缺陷预测方法

李 莉，任振康，石可欣

（东北林业大学 信息与计算机工程学院，哈尔滨 150040）

0 概述

软件的可靠性是软件工程领域最重要的指标之一［1-2］，软件缺陷预测技术可以有效提高软件可靠性，降低测试成本，合理进行软件缺陷预测可以帮助测试团队快速定位软件缺陷，修复系统存在的漏洞。近年来的软件缺陷预测研究结果表明［3］，绝大多数软件缺陷集中在较小比例的软件模块中，即软件缺陷预测领域存在严重的类不平衡问题。现有软件缺陷预测技术产生的错误分类主要分为2 种［4］：将有缺陷的模块误分为无缺陷的模块；将无缺陷的模块误分为有缺陷的模块。在软件工程实践中，第一类错误的代价远高于第二类错误。随着机器学习技术的发展，众多研究人员将机器学习技术应用于软件缺陷预测领域。研究结果表明，代价敏感学习技术可较好地解决样本中类不平衡问题［5］，能够为软件项目的决策提供支持［6-7］。

目前，软件缺陷预测领域采用的主要方法包括神经网络［8］、逻辑回归（Logistic Regression，LR）［9］、支持向量机（Support Vector Machine，SVM）［10］、贝叶斯模型［11］、集成学习方法［12］等。然而，上述方法在面对第一类和第二类错误分类代价不同的情况时，并未给出有效的解决方案。

YANG等使用以多个K最近邻（K-Nearest Neighbor，KNN）为基分类器的Boosting算法进行软件缺陷预测［13］，但使用KNN 算法时存在以下问题：KNN 算法复杂度较高，且在处理类不平衡问题时对于稀有类别的预测准确率低。例如，在样本不平衡时，即有缺陷类样本容量很小、无缺陷类样本容量很大，此时若输入一个新的缺陷样本，该样本的K个邻居中可能大容量类占大多数，从而导致分类结果误差偏大。

相较KNN 算法，决策树易于理解和实现，可以较直观地体现数据特点，且其擅长处理二分类问题，但决策树模型对多类别问题或连续型字段的分类效果不佳。在软件缺陷预测领域，分类问题是一个二分类问题，即预测模块是有缺陷模块还是无缺陷模块，因此，可以选取决策树作为基分类器。李勇等使用以C4.5 决策树作为基分类器的代价敏感Bagging算法进行软件缺陷预测［14］，实验结果表明，该算法具有较好的性能，但时间复杂度较高。

针对以上问题，本文提出一种代价敏感的Boosting 软件缺陷预测方法CSBst，以提升Boosting方法在二分类问题中的预测性能［15-17］。针对不同的错误分类赋予其不同权重，采用阈值移动方法进行决策树基分类器集成，从而解决类不平衡问题并在提高预测性能的同时降低算法的时间复杂度。

1 常规Boosting 方法

设训练数据集为{(x1，y1)，(x2，y2)，…，(xN，yN)}，其中：xi为一个含有d个元素的列向量，即xi∈X⊆R；yi为该训练数据集中的标签集，y∈{-1，+1}。Boosting 方法具体步骤如下：

1）给出N个数据，初始化每个数据的权重并取值相同：

2）对每一个弱分类器（1，2，…，m），按照样本分布权重Dm训练数据，得到m个基学习器Gm(x)。Gm(x)的取值范围为：

计算Gm(x)在加权训练集中的分类误差：

式（3）表示模型的误差等于每一个错分的样本权重之和。

计算Gm(x)的系数，即该基分类器的权重：

3）根据模型权重更新数据的权重：

其中：Zm是正规化系数，用来确保所有的数据权重总和为1。

指数内部为：

若弱分类器m的分类结果和真实结果相同，则θm小于1，该数据集的样本权重降低；若弱分类器m的分类结果和真实结果不一致，即θm大于1，则该数据集样本权重增加。

4）通过迭代将多个弱分类器集成为一个强分类器：弱分类器i的权重为ai，弱分类器对于样本i的分类结果为Gi(x)，集成之后的学习器为G(x)，sign（x）为符号函数，x>0 时输出为1，x<0 时输出为-1，集成学习的公式为：

2 代价敏感的Boosting 方法

2.1 方法步骤

在软件缺陷预测领域对于误报与漏报的惩罚因子实际不相同，误报率较高易导致开发和测试资源的浪费，漏报率较高易导致含有缺陷模块的软件被交付到用户手中［18］。软件开发后期对缺陷的修复代价是前期的指数倍，交付后存在的软件缺陷甚至会威胁客户的生命财产安全，因此，软件缺陷预测过程中对漏报的惩罚应大于误报［19-20］。CSBst 方法在更新样本权重时，增加产生第一类错误样本的权重，使产生第一类错误的样本权重高于无缺陷类样本权重和产生第二类错误的样本权重［21-22］，由此可大幅提高预测结果的准确率。CSBst 方法流程如图1 所示，其中，加粗标注为相对常规Boosting 的改进部分。

图1 CSBst 方法流程Fig.1 Procedure of CSBst method

CSBst 方法具体步骤如下：

1）第一步同常规Boosting 方法。

2）第二步同常规Boosting 方法。

3）根据模型权重更新数据的权重：

其中：Zm是正规化系数，用来确保所有的数据权重总和为1。

指数内部为：

若弱分类器m的分类结果和真实结果相同，即分类正确，则Rresult<1，该数据集的样本权重降低。若弱分类器m的分类结果和真实结果不同，即分类错误，则Rresult>1，该数据集的样本权重增加。数据集的样本权重由CL值决定。其中，CL的取值为：

4）通过迭代将多个弱基分类器集成为一个强分类器，集成学习的公式如下：

其中：弱分类器i的权重为ai；弱分类器对于样本i的分类结果为Gi(x)；集成之后的学习器为G(x)；Tthreshold为调整阈值的参数；sign（x）为符号函数，x>0 时输出为1，x<0 时输出为-1。

2.2 CSBst 方法实现

CSBst 方法主要包括数据处理和阈值选择2 个阶段：

1）在数据处理阶段，对数据集进行提取，将数据集分割为特征集和标签集，使用基分类器决策树进行数据集分类。决策树对第一个特征进行划分，该特征最大值为FFEATURE_MAX，最小值为FFEATURE_MIN。对于该特征划分的步长SStep为：

从FFEATURE_MIN开始，每次增加一个SStep进行特征划分，计算方式如式（16）所示，划分完成后计算该划分下的错误率。每个特征计算20 次，依次计算每个特征直至遍历特征集合，选出并存储分类错误率最低的特征和特征阈值。

2）阈值选择阶段主要对上述数据进行进一步处理。基于CSBst 方法思想，对于已经完成分类的第一个弱分类器，更新第一类错误、第二类错误和正确样本的权重。依次处理每个弱分类器，最后根据基分类器的错误率更新其权重。

在CSBst 方法中，一直增加样本权重虽会提高样本的预测率，但也会在一定程度上使样本过拟合，导致误报率提高，无法有效解决类不平衡问题。为平衡预测率和误报率，本文引入阈值移动的思想。在集成基分类器分类结果时，选择合适值作为区分待预测模块是否为缺陷模块的阈值，集成加权结果小于该阈值的模块并标记为正常模块，大于该阈值的模块标记为缺陷模块。

在软件缺陷预测领域，评价准则TPR、误报率FPR、预测率P、平衡值BAL、平衡值F1 分别如式（17）～式（21）所示，定义二值分类的混淆矩阵如表1 所示。

表1 混淆矩阵Table 1 Confusion matrix

由混淆矩阵可知，TPR 值升高，FPR 值随之升高。选取BAL 来平衡TPR 和FPR，最优阈值和权重的选择以BAL 取得最大值为标准。

在CSBst 方法中，设置阈值为Threshold，初始值为0，权重为Weigh，初始值为1。遍历Weigh 和Threshold，Weigh 为2.5 或Threshold 为1.5 时，TPR 值等于1，故设置Weigh 最大值为2.5，Threshold 最大值为1.5。每次遍历步长为0.1，循环结束或TPR 值为1时遍历停止。以BAL 取得最大值为模型的最优解。

2.3 CSBst 伪代码

CSBst 方法的伪代码如算法1 所示。

算法1代价敏感的软件缺陷预测算法

3 实验结果与分析

3.1 实验环境

本文实验采用公开的NASA 软件缺陷预测数据集，包括CM1、PC1、KC1、PC3 数据集。所有结果采用10 次十折交叉验证的平均值。实验环境为Windows10 64 位操作系统，计算机内存为8 GB，处理器为Core i5-8250u。实验选取文献［16］提出的CSBKNN 方 法、CSCE 方法和Boosting 方法进行对比。数据集特征如表2 所示。

表2 数据集及其特征Table 2 Datasets and their characteristics

3.2 方法时间复杂度分析

CSBst 与CSBKNN 集成方式相同，与CSCE 集成时间复杂度一致。因此，CSBst 的时间复杂度由基分类器的时间复杂度决定。

CSBst 方法使用的基分类器为一维决策树，决策树的训练时间复杂度为O(NMD)，其中：N为训练集中的样本数；M为数据的维度；D是树的深度。一维决策树的深度为1，则时间复杂度为O(NM)。

CSBKNN 为KNN 集成的Boosting 方 法，KNN的时间复杂度为O(NM)。

CSCE 是C4.5 决策树集成的代价敏感Bagging方法，决策树的训练时间复杂度为O(NMD)。

综上，CSBst 方法与CSBKNN 方法所采用的基分类器时间复杂度以及集成时间复杂度均相同，因此，CSBst 与CSBKNN 时间复杂度一致。CSBst 和CSCE 相比，前者的基分类器时间复杂度更低，两者集成时间复杂度相同，因此，CSBst 方法的时间复杂度低于CSCE 方法。

3.3 结果分析

3.3.1 实验结果

本文选用4 个NASA 缺陷预测数据集作为测试数据集，实验结果如表3 所示。

表3 4 种方法实验结果对比Table 3 Comparison of experimental results of four methods

从表3 可以看出：

1）与CSBKNN、CSCE 以及常规Boosting 方法相比，CSBst 方法在大部分数据集中均能取得较好的预测率。CSBst方法的平均TPR 值为76%，而CSBKNN、CSCE 以及常规Boosting 方法分别为62.4%、76.2%、18.56%，其中，常规Boosting 方法的预测率最低，主要是因为其没有处理类不平衡问题，预测结果自然偏向多数类。

2）CSBst、CSCE、CSBKNN方法的平均误报率分别为31.6%、36%、25.8%，而常规Boosting 方法的平均误报率仅为3.76%。本文选取BAL 作为综合指标来评价预测性能，CSBst 方法具有较高的误报率和预测率。

常规Boosting 与CSBKNN、CSCE 以及CSBst 方法相比，在方法流程中没有考虑类不平衡问题的处理。CSBKNN、CSCE 以及CSBst 是专门为处理类不平衡问题而提出的代价敏感方法。本文选取的数据集取自真实的软件项目，都存在类不平衡问题，因此，常规Boosting 方法性能较低。此外，为提高预测率，本文选取的性能评价标准为BAL=TPR-FPR。3 种代价敏感的方法通常都具有高预测率、高误报率的特点，常规Boosting 方法具有低预测率和低误报率的特点，预测率和误报率等比增长，最后评价指标BAL 也等比增长，因此，在本文所采用的评价指标中常规Boosting 方法性能偏低。

综上，常规Boosting 方法与CSBKNN、CSCE、CSBst 的性能差距主要是因为采用了特定的数据集与评价指标。对于性能较为接近的CSBst 和CSCE方法，本文选用F1 指标继续进行深入分析，实验结果如表4 所示。

表4 CSBst 与CSCE 的F1 指标结果对比Table 4 Comparison of F1 index results between CSBst and CSCE

从表4 可以看出，对于综合评价指标F1，CSBst在4 个数据集中的性能均高于CSCE，分别高出0.41、0.33、0.25、0.31。CSBst 方法的F1 值较高，是由于其预测准确率P和预测率TPR 均较高所致。

相较CSBKNN 方法，在4 个NASA 实验数据集中，CSBst 方法的BAL 提高7%，TPR 提高13.6%，FPR提高5.8%。相较CSCE 方法，在4 个实验数据集中，CSBst 方法的BAL 平均提高3%，TPR 降低0.22%，FPR 降低4.4%，总体性能接近。在F1 指标上，CSBst性能优于CSCE，且CSBst 具有更低的时间复杂度，因此，CSBst 方法性能优于CSCE。与常规Boosting方法进行如上的比较分析，能够得出同样的结论。

综上，CSBst 方法对软件缺陷进行预测的整体性能明显高于同类代价敏感的缺陷预测方法。

3.3.2a取值对实验结果的影响

本节以PC1 数据集为例，给出实验中代价因子a取值的选择过程，为进行简化，设置threshold 值为0。在采用CSBst 方法构建预测模型时，代价因子a≥1。当a>1 时，表示将有缺陷模块预测为无缺陷模块的代价较高；当a=1 时，表示正确和错误分类具有相同的代价。较低的TPR 意味着没有找全有缺陷模块，较高的FPR 意味着要利用较多的人力资源来对没有缺陷的模块进行测试。

从图2 可以看出：

图2 a 取值对模型性能的影响Fig.2 Influence of a values on model performance

1）当a=1 时，误报率FPR 为3.1%，预测率TPR 为20%，预测率和误报率均较低，但预测率FPR 低于60%，无法投入实际应用。

2）随着a值的逐渐增大，误报率FPR 和预测率TPR 都逐渐上升，当a=1.6 时，综合性能指标BAL 最高，可以认为a=1.6 为CSBst 在PC1 数据集上的最优解。

3）当a＞1.6 时，随着a值的增大，综合评价指标BAL 下降，TPR 升高，适用于对系统要求较高或测试资源较充足的情况。

4）当a>2.4 时，TPR>95%，随着a值的继续增大，TPR 呈稳定趋势，FPR 不断增长，因此，BAL 不断减小。综上，1.6 为a的最佳取值。

4 结束语

为提升软件缺陷预测精确度，本文提出一种代价敏感的Boosting 软件缺陷预测方法CSBst。通过细化不同种类错误样本的权重更新方式来筛选出存在第一类错误的模块，采用移动阈值加权集成的方法解决软件缺陷模块中的类不平衡问题，并有效提高软件缺陷的预测率。在NASA 软件缺陷预测数据集上进行实验，结果表明，与CSBKNN、CSCE 方法相比，在指标相同的情况下，CSBst 方法的预测性能较高，时间复杂度较低，对于第一类错误分类样本具有更好的查找效果。下一步将针对本文所设置的BAL 指标调整TPR 和FTR 的比重，研究更加合理稳定的比重设计方法，以保证算法的稳定性。此外，将探究线性回归、逻辑回归等不同基分类器对算法预测性能的影响。