【软件分析与挖掘】Multiple kernel ensemble learning for software defect prediction

摘要：

       利用软件中的历史缺陷数据来建立分类器，进行软件缺陷的检测。

       多核学习(Multiple kernel learning)：把历史缺陷数据映射到高维特征空间，使得数据能够更好地表达；

       集成学习(ensemble learning)：使用一系列的分类器来减少由主类带来的分类误差，使具有更好的检测结果。

       本文采用集成学习的方法构建一个多核分类器，集多核学习和集成学习的优点，提出方法： propose a multiple kernel ensemble learning (MKEL) approach for software defect classiﬁcation and prediction。考虑到软件缺陷预测中的成本风险，设计了一个新的样本权重向量更新策略来减少由误分类所带来的成本风险。

        使用数据集： NASA MDP。

S1   Introduction

多核学习+集成学习：

       a.把历史缺陷数据映射到高维空间以挖掘更多有用的信息；

       b.类不平衡的问题；

       c.避免复杂的参数优化问题；

       d.根据不同的应用需求调节分类器的精度；

误分类是一个问题，尤其是把有缺陷的看作是没有缺陷的。

contribution:

        a.首次把 the multiple kernel learning technique引入software defect prediction领域；

        b.考虑到成本风险，设计一个新的样本权重向量更新策略：训练阶段，通过增加缺陷样本的权重，减少非缺陷样本的权重来更加关注缺陷模块，减少把有缺陷当作无缺陷的成本风险，并获取一个较好的结果。

S2 相关工作

软件缺陷预测技术分两类：静态和动态。

静态如下图所示：先标记有无缺陷，然后特征提取构成训练样本，构造分类器。

许多传统的机器学习的分类算法如贝叶斯，SVM，决策树等等都可用于静态缺陷预测技术。为了解决类不平衡问题，采用重采样，集成学习和代价敏感等方法。

本文采用多核学习算法来预测软件模块的缺陷倾向，提出多核集成学习(MKEL)算法。不同于先前的研究，MKEL有以下几个特点：

结合多核学习和集成学习的优势，首次把多核学习的方法应用到软件缺陷预测；
权向量更新部分，根据历史缺陷数据，我们采用成本风险来解决缺陷数据预测。

S3 MKEL

a.问题定义

给定标记好的训练集：；

给定M个基本核函数：

MKEL旨在学习到一个基于多个核函数的分类器f(x)：

获取一个有效的boosting机制来学习到每一个boosting trial中，最佳的基于核函数的多项式ft以及它的权重αt。当这T个boosting试验完成之后，获取T个 ft (x)和αt，最后集成学习来把它们进行整合。

b.多核学习

映射：原始的问题是，现在通过把它映射到一个新的特征空间，在这个新的特征空间中去考虑原始的问题。

多核学习：

多核学习方法是当前核机器学习领域的一个新的热点. 核方法是解决非线性模式分析问题的一种有效方法, 但在一
些复杂情形下, 由单个核函数构成的核机器并不能满足诸如数据异构或不规则、样本规模巨大、样本不平坦分布等实际的应用
需求, 因此将多个核函数进行组合, 以获得更好的结果是一种必然选择.

优化问题：----------->

这期间需要大量复杂的运算，为了避免这个缺点，使用boosting方法来计算多核问题。

-------------------------------------------------------------------------------------------多核学习课外知识（头）----------------------------------------------------------------------------------

《多核学习方法》

由于不同的核函数具有的特性并不相同, 从而使得在不同的应用场合, 核函数的性能表现差别很大, 且核函数的构造或选择至今没有完善的理论依据. 此外, 当样本特征含有异构信息(Heterogeneous information)[20−26], 样本规模很大[27−30], 多维数据的不规则(Unnormalised data)[31−32] 或数据在高维特征空间分布的不平坦(Non-ﬂat)[33−34], 采用单个简单核进行映射的方式对所有样本进行处理并不合理. 针对这些问题, 近年来, 出现了大量关于核组合(Kernel combination) 方法的研究, 即多核学习方法[23, 31, 35−40].

多核模型是一类灵活性更强的基于核的学习模型, 近来的理论和应用已经证明利用多核代替单核能增强决策函数的可解释性(Interpretability),并能获得比单核模型或单核机器组合模型更优的性能[41−42]. 构造多核模型, 最简单也最常用的一种方法就是考虑多个基本核函数的凸组合, 其形如: 这里Kj是基本核函数, M 是基本核的总个数, βj是权系数. 因此, 在多核框架下, 样本在特征空间中的表示问题转化成为基本核与权系数的选择问题. 在这个由多个特征空间构建的组合空间中, 由于组合利用了各基本核的特征映射能力, 很好地解决了核函数的选择以及与核目标度量(Kernel tar-get alignment, KTA)[43−44] 相关的变量与模型的选择难题[31, 45−46]. 同时, 通过将异构数据的不同特征分量分别输入对应的核函数进行映射, 使数据在新的特征空间中得到更好的表达, 能显著提高分类正确率或预测精度. 但是, 这里最重要的问题就是如何得到这个组合的特征空间, 也就是如何学习得到权系数. 针对这一问题, 近来出现了多种有效的多核学习理论及方法. 如早期的基于Boosting[21, 47] 的多核组合模型学习方法, 基于半定规划(Semideﬁnite programming, SDP)[41] 的多核学习方法, 基于二次约束型二次规划(Quadrat-ically constrained quadratic program, QCQP)[36]的学习方法, 基于半无限线性规划(Semi-inﬁnitelinear program, SILP)[24, 37] 的学习方法, 基于超核(Hyperkernels)[31] 的学习方法, 以及近来出现的简单多核学习(Simple MKL)[27, 29] 方法和基于分组Lasso 思想的多核学习方法. 在权系数与核函数的组合方面, 研究人员也对多核方法进行了一些改进,如非平稳的多核学习方法[23], 局部多核学习方法[40],非稀疏多核学习方法[30] 等. 此外, 基于一类具有多尺度表示特性的核函数, 多核学习方法向多尺度核方法方向又出现了众多的扩展[32−34, 48−52]. 前述的这些多核学习方法都是在有限个基本核函数组合假设下进行的, 容易看到, 有限核的组合受限于选择的有限性, 为了将其扩展到大量核组合的情形, 近来又出现了基于无限核的学习方法[39, 53−54].

还可以参考：http://zipperary.com/2014/11/27/mkl/?utm_source=tuicool

------------------------------------------------------------------------------------------多核学习课外知识（尾）-----------------------------------------------------------------------------------

c.多核集成学习

基于相同的样本，采用不同的核函数，他们的权重是不同的，构造出了T个分类器，然后利用boosting方法来进行权重的计算。

步骤：

建立初始样本——采用随机抽样的策略作为初始训练集；
刚开始的时候，每个样本的权重都是一样的，通过boosting算法的迭代后，权重根据一定的策略会进行调整，为了关注那些在下一轮boosting需要引起关注的样本；
一旦初始集合和权重确定之后，运行boosting算法：用于衡量第t次boosting时误分类的性能。而分类器就是为了使误分类的可能性尽可能小。
为了从所有弱分类器中获取最终的分类结果，每个分类器被指定一个权重。对于第t轮boosting迭代中，它的权重可以通过计算得到；
在下一轮boosting中更新权重（一般boosting算法更新权重只根据分类结果：在t论boosting中被正确分类的权重将减小，被误分类的将增加，这样，在下一轮中，就重点关注那些误分类的，因为把有缺陷的当作没有缺陷的严重性远远大于把没有缺陷当作有缺陷的，对于有缺陷的样本，如果他们被正确判断，则权重不变，否则，权重增加；对于没有缺陷的样本，如果他们被误判，权重不变，否则，权重减小，如下图：）；
迭代完毕，得到最终的分类器：

流程图：

S4   实验

主要包括基本数据集、评估标准、实验设计。

4.1   基本数据集

NASA12个数据集的20种基本指标：

12个数据集中有缺陷与没有缺陷的数量比

4.2   评价指标

缺陷预测指标

Pd= A/(A + B)，越高表示尽可能地找出有缺陷的模块；
Pf=C/(C + D)，
Precision=A/(A + C)，越高表示尽可能正确的预测有缺陷的模块；
Accuracy= (A + D)/(A + B + C + D)

因为Pd越高，会导致Precision越低，反之亦然。所以，需要推出一种新的度量指标来作为权衡——F − measure：

                                    F − measure = 2∗Pd∗ precision/ (Pd + precision) .

F − measure介于0~1，F − measure越高，表示性能越好。

4.3   实验设计

步骤如下：

随机选择50%的有缺陷和没有缺陷的样本作为训练集，剩下的50%拿来测试；
为了得到更一般的结论，我们在每一个数据集上重复算法20次，并记录每次的结果；
30个基本的核函数，其中包括：21个不同宽度的高斯核函数(Radial Basis Function Kernel)，从(2^−10, 2^−9, · · · , 2^10)；9个多项式核函数从1~9；
SVM就用LIBSVM；
boosting训练集采用：随机选择其中40%的训练样本作为初始训练样本，默认boosting trial100次，因此，最终的分类器将集成100个基于核的弱分类器；

S5 实验结论

实验评估MKEL的同时，还与其他的一些方法进行比较，如解决类不平衡的方法： coding based ensemble learning (CEL)和 dynamic version of AdaBoost.NC (DVA，采用十折交叉验证，9/10用于建立模型，其中8/9用于训练集，1/9用于验证集，) ，以及其他一些比较具有代表性的缺陷检测方法：朴素贝叶斯，决策树，成本敏感型神经网络，非对称核主成分分类等。

实验结果观察到：Pd最高，Pf也不低。

关于F-measure也不低：

还进行了Mcnemar’s test （主要用于配对资料率的检验（相当于配对卡方检验））这里把MKEL方法与其他方法进行比较，当p值低于0.05，则说明两种方法具有不同的统计学意义。

为了比较缺陷预测问题中，多核学习与单核学习对结果的影响有多大以及初始抽样比例的不同和boosting试验的次数对性能的影响。

结论：

多核性能要比单核的好；

抽样比例的多少对性能的影响不大；

boosting实验次数对性能的影响程度不大。

S6 有效性风险

与文章中提到的方法一样，都有一个相同的问题就是在初始化训练集的过程中，采用一种随机抽取的策略，因为类不平衡的问题，这样会导致不存在缺陷（即无法保证初始训练集中既含有有缺陷的模块，也含有没有缺陷的模块）。