摘? 要? 针对传统软件缺陷预测模型的应用范围通常被局限在一定的子空间而影响其适用性和准确性的问题, 文中利用支持向量机(SVM)的非线性运算能力和蚁群优化算法(ACO) 的寻优能力提出了一种基于 ACO?SVM 的软件缺陷预测模型. 文中首先对待预测的数据进行主成分分析降低数据的维数以提高运算速度, 然后根据蚁群优化算法来计算最优的 SVM 参数, 然后再运用 SVM 进行软件缺陷的预测. 并基于十折交叉方法进行实验, 通过与传统方法的对比, 证明文中方法具有较高的预测精度.

关键词? 软件测试; 软件缺陷预测; 支持向量机; 蚁群算法; 主成分分析

1 ? 引 ? 言

随着计算机系统应用领域的不断扩大, 软件缺陷预测 [ 1] 问题变得越来越受到人们的关注. 例如, 在银行和股票等系统中, 由于系统一旦失效将会导致巨大的经济损失, 软件缺陷是软件开发首要因素. 而软件缺陷预测模型能够在软件开发的早期预测出哪些模块有出错的倾向从而找到相应的解决方案, 是软件可靠性工程的重要组成部分, 对提高软件可靠性具有重要的意义.

目前, 软件缺陷预测模型主要包括马尔可夫模型 [ 2] 、 分类回归树模型 [ 3] 、 人工神经网络模型 [ 4] 、 线性判别分析模型 [ 5] 、 时间序列分析模型、 分类树模型 [ 6] 等, 但这些方法尚存在一定问题, 难以达到理想的效果. 例如, 马尔可夫模型需要对软件内部错误及失效过程的特性做出很多假设; 分类回归树模型的泛化能力差; 人工神经网络模型的网络结构选择尚无统一完整的理论指导.

逻辑回归( Logistic Regression, LR)[ 7]是对线性回归的进一步改善, 线性回归难以解决分类时出现的 0~ 1 之外的非法概率值问题, 针对这一问题,LR 采用对数变换, 使其结果值不再局限于 0~ 1 范围, 而是负无穷大和正无穷大之间的任意值. 由于LR 模型进行二次判别可以显著提高计算速度和识别率, 所以被广泛应用于构建软件缺陷预测模型. 但是该方法适用于大样本的情况, 对小样本的预测效果不理想.

支持向量机[ 8]( Support Vector Machine, SVM)是 Cortes 和 Vapnik 等人于 1995 年首先提出的, 是在统计学习理论基础上发展起来的一种新的机器学习方法, 在解决小样本、 非线性及高维模式识别中表现出许多特有的优势, 但 SVM 的参数选择没有理论上的指导, 是一个亟待解决的问题.

蚁群优化算法( Ant Colony Optimization, ACO)[ 9]是 Dorigo 等人于 20 世纪 90 年代提出的, 是一种模拟蚂蚁种群进化的启发式搜索算法, 具有随机搜索、 全局优化、分布式和正反馈等优点.为了提高软件缺陷预测模型的准确性, 本文提出了一种基于 ACO?SVM 的软件缺陷预测模型. 即分别利用 SVM 和 ACO 建立和优化软件缺陷预测模型, 并基于主成分分析方法进行降维处理, 最后利用 ACO?SVM 建立软件缺陷预测模型.

2 ? 相关工作

2. 1? 支持向量机支持向量机的基本思想是求解核函数和二次规划问题, 通过核函数将数据映射到高维特征空间来解决非线性可分的问题. 径向基核函数(Radial BasisFunction, RBF)具有较宽的收敛范围, 是较理想的分类依据函数, 其表达式如式(1)所示.exp(- ??x- x??2 )( 1)其中, x 和 x ?是特征向量, ?是径向基核函数的带宽.在二分类问题中, 假设给定训练集 T = {( x 1 ,y 1 ), ?, (x l , y l )} ? (Rn? y)l , 其中 x i? R n , y i ? Y ={+ 1, - 1} , i= 1, 2, ?, l, x i 是特征向量, y i 是类别标签. SVM 将决策函数的求解转化为带有约束条件的二次规划问题求解, 如式(2)所示, 其中 ? i 、 ? j 是拉格朗日乘子, K( x i , x j )是核函数.min?12?li = 1?lj = 1y i y j K ( x i , x j )? i ? j -?lj = 1? js. t.?li = 1y i ? j = 0, 0 ?? i ?C, i= 1, 2, ?, l(2)方程式的解为 ?*= (?*1 , ?, ?*l )T , 决策函数的偏置项 b*如式(3) 所示.b*= y j -?li = 1y i a*i K (x i , y j ) (3)决策函数如式(4) 所示.f (x) = sgn?li = 1y i ?*i K (x i , x) + b*(4)

2. 2?蚁群优化算法基本蚁群算法引进了正反馈和并行机制, 较好地解决了 旅行商 ( T raveling Salesman Problem,T SP)问题, 但是收敛速度较慢. 1997 年 Dorigo 等人在基本蚁群算法的基础上提出了蚁群系统, 证明了该算法优于模拟退火、 进化计算等仿生算法.蚁群系统的搜索过程如下:1. 蚂蚁的配置和信息素的初始化.2. 对每只蚂蚁按式( 5) 或式( 6) 选择下一个城市, 并基于式( 7) 、 (8)更新该路径上的信息素.p k ij ( t+ 1)=[? ij (t)]? (?ij )??k? tabu k[? ik ( t)]? (?ik )? ,j ? tabu k0, 其它(5)j=arg maxj ? J k (i){ [? ij ( t)]? (?ij )? } ,q ?q 0S, 其它(6)? ij (t+ 1)= ( 1- ? )? ij (t) + ? ?? k ij (7)?? k ij =Ql jb, ( i, j) ? Tk0, 其它(8)其中, q 0 ? [0, 1] 是初始设定的参数, q 是一个随机数, ? ij ( t)是 t 时刻在城市节点i、 j 之间路径上残留的信息素, ? ij 是城市 i 转移到城市j 的启发式信息, ?用来衡量残留信息素的相对重要程度, ?用来衡量期望信息的相对重要程度, S 是根据式( 5) 决定的随机变量, tabu k 是蚂蚁 k 当前走过的城市( 禁忌表), l jb 是蚂蚁k 从开始城市到当前城市已走过的路径长度, Q 为常数, T k 为蚂蚁 k 经过的路径.3. 当所有蚂蚁走完所有城市后, 通过计算它们的最短距离获得最佳路径. 按下式更新最佳路径上的信息素.? newij = (1- ? )?lodij + ???kij (9)?? k ij =1l k, (i, j) ? O k0, 其它(10) 其中, ?为全信息素挥发系数, l k 为最佳路径的长度, O k 表示蚂蚁k 所走的是最佳路径.4. 输出最优解.

2. 3?主成分分析算法主成分分析算法( PCA) 是由 Hotelling 提出的. 主成分分析将给定的一组相关变量通过线性变换转换为另一组不相关的变量, 这些新的变量按照方差递减的顺序排列, 构成相应的主成分.PCA 的步骤如下:1. 设 X= ( X 1 , X 2 , ?, X n )T 是一个 n 维随机向量, 计算X 的协方差矩阵 ?= XX T .2. 计算 ? 的特征值? i (? 1 ?? 2 ? ? ?? n ) 及其特征值对应的特征向量 p i ( i= 1, 2, ?, n), 则 X 的第i 主成分为 Y i =p Ti X.3. 定义? k?ni= 1? i 为主成分 Y k 的贡献率, 定义 a=?mi= 1? i?ni = 1? i 为主成分的累积贡献率. 主成分的个数由 a 决定, 一般取 a> 95%

.3 ?软件缺陷预测模型的建立

3. 1?软件缺陷预测模型基于 ACO?SVM 和 PCA 方法建立软件缺陷预测模型主要包括以下几个步骤, 如图 1 所示.图 1? 建立软件缺陷预测模型的流程建立软件缺陷预测模型步骤如下:1. 获取软件复杂度度量数据集;2. 对数据集进行主成分分析, 降低数据集维数;3. 用训练样本基于 SVM 建立软件缺陷预测模型, 核函数选择 RBF 核函数;4. 利用 ACO 进行模型参数 C 和? 的优化;5. 用测试样本进行程序模块的分类预测. 如果预测结果满足终止条件, 则得到优化的软件缺陷预测模型并结束;否则返回步 4 继续优化模型.其中, 终止条件为模型预测准确率达到了事先给定的阈值或者循环次数超过了事先设定的最大循环次数.

3. 2?软件缺陷预测模型参数的优化本文利用 ACO 算法进行模型参数 C 和 ?的优化. 即根据 ACO 算法搜索出的最优路径来确定模型参数. 在参数优化过程中, ACO 算法不是根据路径的长度来更新路径上的信息素, 而是根据系统的性能指标( 分类准确率) 来更新信息素. 为了利用ACO 算法进行参数优化, 需要先将模型的参数 C 和?离散化, 根据经验, C 和 ?的有效位个数均取 5 位,各个有效位上的值取[ 0, 9] 之间的整数. 参数 C 的最高位是百位, 其取值范围是(0, 999?99] . 参数 ?最高位是个位, 所以其取值范围是( 0, 9 ?9999] . ACO算法以 10 个有效位作为行、 以 10 个整数值(0~ 9)作为列, 在直角坐标系中, 画出 10 ? 10 的平面结构图作为模型参数优化蚂蚁运行图. 图中城市节点的横坐标是有效位, 纵坐标是该有效位上的取值. 每只蚂蚁走完一条路径后, 根据小数点的位置可以计算出两个参数的值, 根据最优路径就能计算出模型的最优参数.设启发式信息 ? ij = 1, 用分类准确率评估支持向量机性能, 在全局信息更新过程中, 令 Q 是信息素强度, ?? ij = Q? A ccuracy, Accuracy 是每次循环中最高的分类准确率, 执行过程如下:1. 使用参数离散化方法离散化 C 和?;2. 初始化 ? ij = 1 , 信息素增量 ?? ij = 0;3. 第一次执行以下搜索过程寻找最优路径:3 ? 1. 将所有蚂蚁置于坐标系原点;3 ? 2. 随机地将蚂蚁放置到下一个需要访问的城市节点, 且该节点的横坐标 x 不同于以前访问过的城市节点的横坐标;

3 ? 3. 对每只蚂蚁根据式( 7) 、 ( 8) 更新转移路径上的信息素;

3 ? 4. 如果所有蚂蚁完成了路径上的所有城市节点的访问, 那么根据式(9) 、 ( 10)对最优蚂蚁走过的路径进行信息素更新. 否则转到步 3 ? 2.4. 再次将所有蚂蚁放到坐标系原点;5. 根据式( 5) 、 (6)使蚂蚁移到下一个城市;6. 根据式(7)、 (8)更新每只蚂蚁转移路径上的信息素.如果蚂蚁完成所有城市的访问, 转到步 7; 否则转到步 5; 7. 使用蚂蚁移动过程得到的 C 和? 训练 SVM. 找到具有最高分类准确率的最优蚂蚁, 根据式( 9) 、 ( 10) 更新其所走路径上的信息素. 如果分类准确率达到终止条件或者循环次数超过最大循环次数, 则转到步 8, 否则转到步 4;8. 输出 C、 ? 和最高分类准确率.

4 ?基于 ACO?SVM 的软件缺陷预测模型实验

4. 1? 实验数据实验数据是美国国家航空航天局( NASA) 提供的一个数据包? . 该数据包共有 13 个数据集, 如表 1所示.表 1? 实验数据数据集 模块数 维数 数据集 模块数 维数JM1 10878 23 PC1 1107 42KC1 2107 26 PC2 5589 42KC3 458 42 PC3 1273 42KC4 125 42 PC4 3840 42MC1 9466 41 PC5 17186 42MC2 161 42 CM1 505 40MW1 403 42本文根据 ERROR_COUNT 属性对各数据集中各模块是否有缺陷进行分类, 设每个数据集中ERROR_COUNT ? 1 的模块为有缺陷模块, 否则为无缺陷模块. 为了缩短分类时间, 针对模块数比较多的数据集, 我们在此数据集中随机选取 200 个模块作为训练样本, 选取 100 个模块作为预测样本. 每个数据集选取 10 维数据作为分类度量.

4. 2? 实验结果与分析为了验证模型的预测能力, 本文采用十折交叉验证( 10?fold CV) 进行实验. 即将每一个数据集平均分成 10 份, 轮流将其中 9 份做训练, 剩余的 1 份做预测, 取 10次预测结果的均值作为对算法预测能力的评价.本文采用准确度、 查准率、 查全率和 F1 值 [ 10] 来评价模型的预测能力. 这些度量来自表 2 所示的交叉矩阵.表 2? 交叉矩阵实际值预测值容易出错模块 不易出错模块容易出错模块 正确的正例( T P) 错误的负例( FN )不易出错模块 错误的正例( FP) 正确的负例( T N)实际正例个数 P= T P+ FN, 实际负例个数N= FP+ T N, 实例总数 C= P+ N. 模型评价指标的定义如下:准确度(accuracy)表示正确分类的测试实例的个数占测试实例总数的比例, 计算公式如下:accuracy =TP+ T NC(11)查准率(precision)表示正确分类的正例个数占分类为正例的实例个数的比例, 计算公式如下:precision=TPT P+ FP(12)查全率(recall)表示正确分类的正例个数占实际正例个数的比例, 计算公式如下:recall =T PP(13)F1 表示查全率与查准率的调和平均, 计算公式如下:F1=21precision +1recall(14)将基于本文方法( ACO?SVM) 和 Fisher 线性判别分析( LDA) 、 聚类分析 ( CA) 、 BP 神经网络( BPNN) 、 逻辑回归( LR) 、 支持向量机( SVM) 等方法建立的软件缺陷预测模型进行比较. 基于十折交叉验证( 10?fold CV) 分别对 13 个数据集进行实验,计算 13 组评价指标( 准确度、 查准率、 查全率、 F1值), 本文方法在预测过程中的最优参数选择如表 3所示, 预测结果如图 2 所示.表 3? 最优参数选择数据集 C ? 数据集 C ?JM1 756 ?47 0 ? 0040 PC1 711 ? 72 0 ? 0040KC1 195 ?41 0 ? 0086 PC2 676 ? 79 0 ? 0050KC3 20 ?04 0 ? 0054 PC3 4 ? 09 0 ? 0078KC4 691 ?16 0 ? 0020 PC4 90 ? 99 0 ? 0070MC1 594 ?69 0 ? 0054 PC5 248 ? 03 0 ? 0029MC2 260 ?95 0 ? 0028 CM1 440 ? 82 0 ? 0043M W1 663 ?06 0 ? 0076图 2( a) ~ ( m) 分别为本文方法与传统方法在13 个数据集上的预测结果对比, ( n) 为 13 个数据集预测结果的平均值对比. 从图 2 可以看出: 基于LDA 建立的模型的预测结果较差, 这是由于该方法基于线性分类函数进行分类, 而软件复杂性度量数据之间呈非线性关系; 基于 CA、 BPNN 建立的模型的预测结果明显优于基于 LDA 方法, 但是由于 CA方法需要较多的先验知识, BPNN 网络结构选择尚无一种确定而有效的方法, 因此这两种方法的泛化能力不十分理想; 基于LR建立的模型预测结果较好, 但是该模型受到样本容量的局限, 只有样本容量较大时该模型才能取得较好的预测效果; 基于 SVM建立的预测模型的参数选择没有理论指导, 只能根据经验选取, 故预测能力不稳定; 本文方法利用SVM 在小样本情况下的预测优势, 利用 ACO 对模型参数进行优化, 并利用 PCA 缩减特征空间以减少计算成本, 使得模型的各项评价指标均优于 LDA、CA、 NN、 LR、 SVM 模型. 但是由于在 ACO 参数寻优的过程中需要多次训练样本, 计算成本仍然需要进一步减少.

5 ? 结 ?论

本文的贡献是针对软件缺陷预测问题提出了一种新颖的基于 ACO?SVM 的软件缺陷预测模型, 其基本思想是基于 PCA 缩减特征空间、 基于 ACO?SVM 建立和优化软件缺陷预测模型. 实验结果表明, 该模型比传统方法具有更好的预测效果. 但是该方法在参数寻优过程中需要较长的时间, 如何进一步降低模型的运行时间和提高模型的预测准确率,是今后的课题.

参 考 文 献[ 1] Challagulla V U B, Bastani F B, I ?Ling Yen, Paul R A. Em?pirical assessment of machine learning based software defectprediction techniques/ /Proceedings of the 10th IEEE Interna?tional Workshop on Object?Oriented Real?T ime DependableSystems. Washington, DC, USA, 2005: 263 ?270 [ 2] Lyu Michael R. Handbook of Software Reliability Engineer ?ing. New York: IEEE Computer Society Press and M cGraw?Hill Book Company, 1996[ 3] Khoshgoftaar T aghi M, Seliya Naeen. T ree?based softwarequality estimation models for fault prediction/ / Proceedings ofthe 8th International Symposium on Software Metrics.Washington, DC, U SA, 2002: 123 ?128[ 4] Stich T imothy Janes, Spoerre Julie K, Velasco T omas. T heapplication of artificial neural networks to monitoring andcontrol of an induction hardening process. Journal of Indus?trial T echnology, 2000, 16( 1) : 1 ?11[ 5] Ohlsson Niclas, Alberg Hans. Predicting fault?prone soft?ware modules in telephone switches. IEEE Transactions onSoftware Engineering, 1996, 22( 12) : 886 ?894[ 6] Khoshgoftaar T aghi M, Seliya Naeem. Software quantityclassification modeling using the SPRINT decision tree algo?rithm/ / Proceeding s of the 14th IEEE International Confer ?ence on Tools with Artificial Intellig ence. Washington, DC,USA, 2002: 365 ?367[ 7] Briand L C, Melo W L, Wust J. Assessing the applicabilityof fault?proneness models across object?oriented softwareprojects. IEEE T ransactions on Software Engineering, 2002,28( 7) : 706 ?720[ 8] Cortes Corinna, Vapnik Vladimir. Support?vector networks.Machine Learning, 1995, 20( 3) : 273 ?297[ 9] Dorigo M, Gambardella L M. Ant colony system: A cooper ?ative learning approach to the traveling salesman problem.IEEE T ransactions on Evolutionary Computation, 1997,1( 1) : 53 ?66[ 10] Wang X H, Shu P, Cao L et al. A ROC curve method forperformance evaluation of support vector machine with opti ?mization strategy. Computer Science Technology and Appli ?cations, 2009, ( 2) : 117 ?120