开放科学(资源服务)标志码(OSID):

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方法

设训练数据集为$ \left\{({\mathit{x}}_{1}, {y}_{1})，({\mathit{x}}_{2}, {y}_{2})，\cdots ，({\mathit{x}}_{N}, {y}_{N})\right\} $，其中：$ {\mathit{x}}_{i} $为一个含有d个元素的列向量，即$ {\mathit{x}}_{i}\in X\subseteq \mathbb{R} $；$ {y}_{i} $为该训练数据集中的标签集，$ y\in \{-1，+1\} $。Boosting方法具体步骤如下：

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

$ {D}_{1}=({\omega }_{11}, {\omega }_{12}, \cdots , {\omega }_{1N}, ), {\omega }_{1i}=\frac{1}{N}, i=\mathrm{1, 2}, \cdots , N $

(1)

2）对每一个弱分类器$ （1，2，\cdots ，m） $，按照样本分布权重$ {D}_{\mathrm{m}} $训练数据，得到m个基学习器$ {G}_{m}\left(x\right) $。$ {G}_{m}\left(x\right) $的取值范围为：

$ {G}_{m}\left(x\right)：X\in \left\{-1\text{，}+1\right\} $

(2)

计算$ {G}_{m}\left(x\right) $在加权训练集中的分类误差：

$ {\xi }_{m}=\sum\limits_{i=1}^{n}{\omega }_{mi}P\left({G}_{m}\right({\mathit{x}}_{i})\ne {y}_{i}) $

(3)

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

计算$ {G}_{m}\left(x\right) $的系数，即该基分类器的权重：

$ {\theta }_{m}=\frac{1}{2}\mathrm{l}\mathrm{n}\left(\frac{1-{\xi }_{m}}{{\xi }_{m}}\right) $

(4)

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

$ {D}_{m+1}=（{\omega }_{m+\mathrm{1, 1}}, {\omega }_{m+\mathrm{1, 2}}, \cdots , {\omega }_{m+1, N}） $

(5)

$ {\omega }_{m+1, i}=\frac{{\omega }_{mi}\mathrm{e}\mathrm{x}\mathrm{p}[-{\alpha }_{m}{y}_{i}{G}_{m}({\mathit{x}}_{i}\left)\right]}{{Z}_{m}}, i=\mathrm{1, 2}, \cdots , N $

(6)

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

指数内部为：

$ -{\alpha }_{m}{y}_{i}{G}_{m}\left({\mathit{x}}_{i}\right), i=\mathrm{1, 2}, \cdots , N $

(7)

$ \mathrm{e}\mathrm{x}\mathrm{p}\left[-{\alpha }_{m}{y}_{i}{G}_{m}\left({\mathit{x}}_{i}\right)\right]={\theta }_{m}, i=\mathrm{1, 2}, \cdots , N $

(8)

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

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

$ \begin{array}{l}G\left(x\right)=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left[f\right(x\left)\right]=\\ \ \ \ \ \ \ \ \ \ \ \ \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left[{\alpha }_{1}{G}_{1}\right(x)+{\alpha }_{2}{G}_{2}(x)+\cdots +{\alpha }_{n}{G}_{n}(x\left)\right]\end{array} $

(9)

2 代价敏感的Boosting方法 2.1 方法步骤

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

CSBst方法具体步骤如下：

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

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

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

$ {D}_{m+1}=（{\omega }_{m+\mathrm{1, 1}}, {\omega }_{m+\mathrm{1, 2}}, \cdots , {\omega }_{m+1\text{，}N}） $

(10)

$ {\omega }_{m+1, i}=\frac{{\omega }_{mi}\mathrm{e}\mathrm{x}\mathrm{p}[-{C}_{L}{\alpha }_{m}{y}_{i}{G}_{m}({\mathit{x}}_{i}\left)\right]}{{Z}_{m}}, i=\mathrm{1, 2}, \cdots , N $

(11)

其中：$ {Z}_{m} $是正规化系数，用来确保所有的数据权重总和为1。

指数内部为：

$ -{C}_{L}{\alpha }_{m}{y}_{i}{G}_{m}\left({\mathit{x}}_{i}\right), i=\mathrm{1, 2}, \cdots , N $

(12)

$ {R}_{\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{u}\mathrm{l}\mathrm{t}}=\mathrm{e}\mathrm{x}\mathrm{p}\left[-{C}_{L}{\alpha }_{m}{y}_{i}{G}_{m}\left({\mathit{x}}_{i}\right)\right], i=\mathrm{1, 2}, \cdots , N $

(13)

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

$ {C}_{L}=\left\{\begin{array}{l}1\text{，}\mathrm{分}\mathrm{类}\mathrm{正}\mathrm{确}\\ 1\text{，}\mathrm{第}\mathrm{二}\mathrm{类}\mathrm{错}\mathrm{误}\\ a\text{，}\mathrm{第}\mathrm{一}\mathrm{类}\mathrm{错}\mathrm{误}\text{，}a > 1\end{array}\right. $

(14)

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

$ \begin{array}{l}G\left(x\right)=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left[f\right(x\left)\right]=\\ \ \ \ \ \ \ \ \ \ \ \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left[{\alpha }_{1}{G}_{1}\right(x)+{\alpha }_{2}{G}_{2}(x)+\cdots +{\alpha }_{n}{G}_{n}(x)+{T}_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{d}}]\end{array} $

(15)

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

2.2 CSBst方法实现

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

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

$ {S}_{\mathrm{S}\mathrm{t}\mathrm{e}\mathrm{p}}=\frac{{F}_{\mathrm{F}\mathrm{E}\mathrm{A}\mathrm{T}\mathrm{U}\mathrm{R}\mathrm{E}\_\mathrm{M}\mathrm{A}\mathrm{X}}-{F}_{\mathrm{F}\mathrm{E}\mathrm{A}\mathrm{T}\mathrm{U}\mathrm{R}\mathrm{E}\_\mathrm{M}\mathrm{I}\mathrm{N}}}{20} $

(16)

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

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

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

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

$ {T}_{\mathrm{T}\mathrm{P}\mathrm{R}}=\frac{{T}_{\mathrm{T}\mathrm{P}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{N}}} $

(17)

$ {F}_{\mathrm{F}\mathrm{P}\mathrm{R}}=\frac{{F}_{\mathrm{F}\mathrm{P}}}{{F}_{\mathrm{F}\mathrm{P}}+{T}_{\mathrm{T}\mathrm{N}}} $

(18)

$ P=\frac{{T}_{\mathrm{T}\mathrm{P}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{P}}} $

(19)

$ {B}_{\mathrm{B}\mathrm{A}\mathrm{L}}={T}_{\mathrm{T}\mathrm{P}\mathrm{R}}-{F}_{\mathrm{F}\mathrm{P}\mathrm{R}} $

(20)

$ \mathrm{F}1=\frac{2\times {T}_{\mathrm{T}\mathrm{P}\mathrm{R}}\times P}{{T}_{\mathrm{T}\mathrm{P}\mathrm{R}}+P} $

(21)

由混淆矩阵可知，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  代价敏感的软件缺陷预测算法

输入  特征集合，标签集合，最大循环次数，初始权重

输出  存储的单层决策树和该决策树的错误率

1.m =数据集的行数

2.D = mat（ones（m，1）/m）//初始化样本权重，每个样本//权重相等，为1/m

3.ZeroMat=zeros（（m，1））//ZeroMat为m行1列的0矩阵

4.for i in range（最大循环次数）：

5.BestStump，error，classEst=buiudStump（dataArr，class Labels，D）//根据数据集、标签集、样本集构建单层决策树

6.alpha=float（0.5∗log_a（（1.0-error）/max（error，1e-16）））//计算弱学习算法权重alpha，且error≠0

7.ClassArr.append（bestStump）//存储单层决策树

8.e的指数项等于-1∗alpha∗mat（classLabels）.T∗classEst

9.Expon（tempMat == 2）= Weigh ∗ alpha//有缺陷模块//预测为无缺陷模块时，e的指数项为原来的Weigh倍

10.D = D ∗（e∗∗expon）

11.D = D/D.sum（）

12.aggClassEst += alpha ∗ classEst //错误率累加

13.S = mat（[threshold] ∗ m）.T//生成调整阈值矩阵

14.aggErrors =（sign（aggClassEst + S）！=mat（classLabels）.T）∗ones（m，1）//计算AdaBoost误差，当误差为0时退出循//环，sign函数为取正负号的函数，取正负号之后与数据标签//不相等则为预测错误标签

15.errorRate = aggErrors.sum（）/m //计算误差率

16.if errorRate == 0.0：

17.break//误差为0，退出循环

18.end if

19.end for

20.返回存储的单层决策树和该决策树的错误率

3 实验结果与分析 3.1 实验环境

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

3.2 方法时间复杂度分析

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

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

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

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

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

3.3 结果分析 3.3.1 实验结果

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

从表 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方法性能较低。此外，为提高预测率，本文选取的性能评价标准为$ \mathrm{B}\mathrm{A}\mathrm{L}=\mathrm{T}\mathrm{P}\mathrm{R}-\mathrm{F}\mathrm{P}\mathrm{R} $。3种代价敏感的方法通常都具有高预测率、高误报率的特点，常规Boosting方法具有低预测率和低误报率的特点，预测率和误报率等比增长，最后评价指标BAL也等比增长，因此，在本文所采用的评价指标中常规Boosting方法性能偏低。

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

从表 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.2 a取值对实验结果的影响

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

从图 2可以看出：

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的比重，研究更加合理稳定的比重设计方法，以保证算法的稳定性。此外，将探究线性回归、逻辑回归等不同基分类器对算法预测性能的影响。