一种基于核主成分分析和极限学习机的软件缺陷预测方法

摘要

本发明公开了一种基于核主成分分析和极限学习机的软件缺陷预测方法，针对软件缺陷个数的预测中不相关的模块特征损害了缺陷预测模型性能，原始特征可能无法正确表示原始缺陷数据的问题，首先采用核主成分分析，通过非线性映射将原始数据投影到潜在特征空间中，使得映射的特征可以正确表征复杂数据结构、增加空间内数据的线性可分离性的概率，然后提取数据的代表性特征，最后根据特征提取后的数据，采用极限学习机构建缺陷预测模型。

说明书

技术领域

本发明属于软件缺陷预测技术领域，涉及一种基于特征选择和集成学习的软件缺陷预测方法，特别是涉及一种基于核主成分分析和极限学习机的软件缺陷预测方法。

背景技术

(1)软件缺陷预测技术

软件已经成为影响国民经济、军事、政治乃至社会生活的重要因素。高可靠和复杂的软件系统依赖于其采用的软件的可靠性。软件的缺陷是导致相关系统出错、失效、崩溃甚至机毁人亡的潜在根源。所谓缺陷，到目前为止，学术界，产业界有很多相关的术语和定义，比如故障、缺陷、bug、错误、失误、失效、失败等。根据ISO 9000对缺陷的定义为：满足与预期或者规定用途有关的要求，缺陷是软件中已经存在的一个部分，可以通过修改软件而消除。然而软件技术发展至今，任何检验、验证手段都不可能发现并排除所有的缺陷，软件作为一种无形的产物，虽然不会磨损用坏，却随时可能因为我们不易查知的原因出现故障甚至失效。事实上，从第一个软件诞生，就伴随出现软件缺陷的检测和预测技术。检测技术在于发现缺陷，而预测技术则在于预测还未发现的缺陷。

20世纪70年代，出现了利用统计学习技术，根据历史数据以及已经发现的缺陷等软件度量数据预测软件系统的缺陷数目及类型。缺陷预测技术的目的在于统计计算机软件系统的缺陷数，以决定系统是否可以交付使用。缺陷预测技术为软件质量的提高和保证起着非常重要的作用，同时也促进了软件工程技术向前大大的发展了一步。

软件缺陷预测过程的第一步是收集和标注软件实例。一个软件实例能够被标记为有缺陷和无缺陷。第二步，抽取软件实例的度量属性。到目前为止，研究人员从不同的角度提出了许多软件度量属性，而与软件缺陷预测密切相关的度量属性主要有代码度量、McCabe度量和Halstead度量三种。代码度量是最直接、应用最普遍的度量属性。通过对程序进行简单的计数，我们可以得到相关代码的度量值。它包含总行数(LOC)、空白行数目(LOCb)、注释行数目(LOCc)、代码行数目(LOCe)和代码和注释总数目(LOCec)(文献1)。软件复杂性通过程序结构的复杂性表现出来，而程序结构的复杂性主要值的是实例内部程序的复杂性。MaCabe度量的正是实例内部程序的复杂性。它由三种度量组成，分别为环形复杂度(Cyclomatic Complexity)、基本复杂度(Essential Complexity)和设计复杂度(DessignComplexity)。Halstead度量不仅度量了程序长度，还描述了程序的最小实现和实际实现之间的关系，并据此阐述程序语言的等级高低。Halstead度量方法充分考虑了程序中出现的算子和操作数，它包括软件长度(N)、容量(V)、级别(L)、难度(D)、工作量(E)、时间(T)、误差估计(B)、程序消息(I)等度量。第三步，建立缺陷预测模型，缺陷预测模型本质上属于模式识别的范畴。而缺陷预测模型的建立过程就是通过一定的机器学习算法来搭建模型结构并确定度量属性之间依赖强度的过程，即为模型的结构学习和参数学习过程。第四步，通过模型预测结果，由于建立好的缺陷预测模型可以通过自身模型结构和模型参数来量化描述度量属性与预测结果之间的因果关系，这样给定一个软件实例的度量属性数据集，使用训练好的预测模型就可以得到该实例是否存在缺陷，即完成软件缺陷预测的过程。

(2)核主成分分析技术(KPCA)

主成分分析(PCA)是一种降维的数据分析技术。核主成分分析(KPCA)认为原有数据具有更高的维数，首先通过非线性映射函数将原始数据映射到高维特征空间中，在特征空间中数据大致遵循高斯分布，然后对特征空间中映射的数据执行线性主成分分析。核主成分分析在数据点使用“核技巧”，简化计算过程。与主成分分析相比，如果原始数据具有复杂的非线性关系，则核主成分分析更适合于特征提取，最大程度上反应原始数据结构。

(3)极限学习机技术(ELM)

极限学习机(Extreme Learning Machine)，是由黄广斌提出来的求解单隐层神经网络的算法。极限学习机最大的特点是对于传统的神经网络，尤其是单隐层前馈神经网络(SLFNs)，在保证学习精度的前提下比传统的学习算法速度更快。

(4)技术问题

缺陷预测的核心挑战是找到可揭示缺陷数据内在结构的代表性特征，现有的基于过滤器和基于包裹式的特征选择方法仅选择原始特征的子集，不进行任何转换，原始特征可能无法正确表示原始缺陷数据。主成分分析方法能将原始特征映射到低维空间，在这个空间中，特征是原始特征的线性组合，然而仅当数据线性可分并遵循高斯分布时，主成分分析效果良好。现实中的数据具有一些复杂的结构[2]，主成分分析的非线性扩展形式—核主成分分析可以将原始数据投影到具有内核功能的潜在高维特征空间中，映射的特征可以适当地表征复杂数据结构，并增加了空间内的数据的线性可分离性的概率[3][4]。图2显示了特征映射的优点，数据在低维空间线性不可分离，但在高维空间变得易于分离。

目前许多分类器被运用于软件缺陷预测，如朴素贝叶斯、随机森林等，然而Lessmann等人[5]建议选择分类器时，更多地考虑一些额外的标准，例如计算效率，简单性和可理解性。现有研究表明，极限学习机具有更快的学习速度，更好的泛化能力，可以避免局部最优化[6]。虽然极限学习机已经受到计算机视觉和模式识别的高度重视，然而没有研究调查了极限学习机对缺陷预测的潜力。

[文献1]：包晓露，王小娟，贾有良、申来安。软件测试基础:方法与度量[M].北京:人民邮电出版社，2007:74-76.

[文献2]：T.Wang,Z.Zhang,X.Jing,and L.Zhang.Multiple kernel ensemblelearning for software defect prediction.Automated Software Engineering,1-22,2015.

[文献3]：B.SchCilkopf and A.Smola.Nonlinear component analysis as akernel eigenvalue problem.Neural Computation,10(5):1299-1319,1998.

[文献4]：K.I.Kim,M.O.Franz,and B.Scholkopf.Iterative kernel principalcomponent analysis for image modeling.IEEE Transactions on Pattern Analysisand Machine Intelligence,27(9):1351-1366,2005.

[文献5]：S Lessmann,B.Baesens,C.Mues,and S.Pietsch.Benchmarkingclassification models for software defect prediction:A proposed framework andnovel findings.IEEE Transactions on Software Engineering,34(4):485-496,2008.

[文献6]：G.Huang,G.B.Huang,S.Song,and K.You.Trends in extreme learningmachines:a review.Neural Networks,61:32-48,2015.

发明内容

为了解决上述技术问题，本发明提供了一种基于核主成分分析和极限学习机的软件缺陷预测方法。

本发明所采用的技术方案是：一种基于核主成分分析和极限学习机的软件缺陷预测方法，其特征在于，包括以下步骤：

步骤1：挖掘软件历史仓库，从中抽取出程序模块；然后标记程序模块的类标号；

步骤2：提取出与软件缺陷有关的特征，并构建出软件缺陷训练集；

步骤3：使用核主成分分析方法进行特征提取；

步骤4：利用提取后的特征，采用极限学习机构建缺陷预测模型；

步骤5：用训练得到的预测模型预测待测程序模块。

相对于国内外已有的跨项目软件缺陷预测方法，本发明针对软件缺陷预测中真实的缺陷数据具有潜在的复杂结构的问题，提出了一种基于核主成分分析和极限学习机的软件缺陷预测方法。相比于传统的基于过滤器，基于包裹式的特征选择方法，核主成分分析更能正确的表征复杂数据结构，提取出最具代表性的特征。极限学习机是一种普遍的机器学习算法，它具有更快的学习速度，更好的泛化能力，可以避免局部最优化。方法包括两个主要阶段；在第一阶段，应用核主成分分析，通过非线性映射将原始数据映射到潜在特征空间中，并提取数据的代表性特征；第二阶段，依据特征提取后的数据，采用最先进的学习算法极限学习机构建缺陷预测模型。

为了验证本方法的优越性，我们使用两类公开的数据集：MORPH数据集和NASA数据集进行实验，三种性能度量方法：F-measure、G-measure和MCC，将本方法与一些流行分类器进行比较：通过将其他分类器与核主成分分析相结合的方式，检查极限学习机对本方法的有效性；通过与不进行核主成分分析，仅使用其他分类器的方式，检查本方法的整体有效性。我们选择了五种代表性分类器：最近邻、随机森林、集成学习、神经网络和支持向量机，并且在实验中执行非参数检验Mann-Whitney U检验和Delta方法来量化本方法与另一种方法之间的差异。

在MORPH数据集中的15个项目中，本方法的平均F-measure、G-measure和MCC值均高于其他所有方法。其中，平均F-measure提高了3.6％至17.8％，平均G-measure值(0.59)提高了2.8％至44.6％，平均MCC值(0.336)改善了4.3％至23.5％。在NASA数据集上，三个指标的平均值方面表现同样优于所有其他方法，并在大多数情况下，本方法获得更好的度量值。通过非参数检验结果可知，本方法与其他方法的差异具有统计学意义。通过上述实验提供的证据，我们得出结论，基于核主成分分析和极限学习机的方法对缺陷预测具有更佳的性能。

附图说明

图1本发明实施例的流程图。

图2本发明实施例的特征映射图。

图3本发明实施例的核主成分分析流程图。

图4本发明实施例的极限学习机架构图。

具体实施方式

为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施例对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解释本发明，并不用于限定本发明。

请见图1，本发明提供的一种基于核主成分分析和极限学习机的软件缺陷预测方法，包括以下步骤：

步骤1：挖掘软件历史仓库，从中抽取出程序模块；程序模块粒度可根据实际应用场景，可设置为文件、包、类或函数等，然后人工标记程序模块的类标号，有缺陷为Y，无缺陷为N。

步骤2：提取出与软件缺陷有关的特征，并构建出软件缺陷训练集。假设数据实例共有20个度量属性：加权方法数(wmc)，继承树深度(dit)，孩子数(noc)，对象类之间的耦合度(cbo)，类的响应(rfc)，内聚缺乏度(lcom)，传入耦合(ca)，传出耦合(ce)，公开方法数(npm)，代码行数(loc)，数据访问度量(dam)，聚合度量(moa)，功能抽象度量(mfa)，方法间的内聚度(cam)，继承耦合(ic)，方法间耦合(cbm)，平均方法复杂度(amc)，最大McCabe环形复杂度(max_cc)，平均McCabe环形复杂度(avg_cc)。

本实施过程假设在提取度量属性后形成了14个跨项目实例：

x₁＝{3.0,1.0,0.0,8.0,14.0,3.0,3.0,5.0,3.0,2.0,85.0,0.0,0.0,0.0,0.5,0.0,0.0,27.33333333,9.0,3.3333,Y},

x₂＝{13.0,1.0,0.0,1.0,17.0,64.0,0.0,1.0,12.0,0.917,117.0,1.0,0.0,0.0,0.462,0.0,0.0,7.462，3.0，1.385，N}，

x₃＝{4.0，1.0，0.0，4.0，4.0，6.0，2.0，2.0，4.0，2.0，4.0，0.0，0.0，0.0，1.0，0.0，0.0，0.0，1.0，1.0，N}，

x₄={10.0，1.0，0.0，6.0，31.0，1.0，0.0，6.0，9.0，0.5，156.0，1.0，1.0，0.0，0.355555556，0.0，0.0，14.4，1.0，0.8，Y}，

x₅＝{7.0，1.0，0.0，6.0，19.0，7.0，0.0，6.0，6.0，0.75，117.0，1.0，2.0，0.0，0.367，0.0，0.0，15.143，3.0，1.1429，N}，

x₆＝{38.0，1.0，0.0，30.0，155.0，485.0，0.0，30.0，34.0，0.9，1564.0，1.0，7.0，0.0，0.14，0.0，0.0，39.6，7.0，1.5，Y}，

x₇={25.0，1.0，0.0，13.0，74.0，0.0，0.0，13.0，23.0，0.444，901.0，1.0，2.0，0.0，0.2，0.0，0.0，34.92，1.0，0.92，Y}，

x₈={13.0，1.0，0.0，19.0，56.0，54.0，0.0，19.0，11.0，0.9，224.0，1.0，4.0，0.0，0.17，0.0，0.0，15.54，4.0，1.1538，Y}，

x₉={7.0，4.0，4.0，48.0，12.0，19.0，47.0，1.0，6.0，0.94，44.0，0.33，0.0，0.867，0.458，0.0，0.0，4.86，1.0，0.29，N}，

x₁₀＝{7.0，1.0，0.0，4.0，7.0，21.0，2.0，2.0，7.0，2.0，7.0，0.0，0.0，0.0，0.357142857，0.0，0.0，0.0，1.0，1.0，Y}，

x₁₁＝{4.0，1.0，0.0，2.0，4.0，6.0，2.0，0.0，4.0，2.0，4.0，0.0，0.0，0.0，0.875，0.0，0.0，0.0，1.0，1.0，N}，x₁₂＝{35.0，1.0，0.0，29.0，121.0，373.0，0.0，29.0，31.0，0.9，1250.0，1.0，5.0，0.0，0.17，0.0，0.0，34.1，5.0，1.2，Y}，

x₁₃＝{8.0，1.0，0.0，16.0，21.0，14.0，13.0，3.0，8.0，0.81，111.0，1.0，0.0，0.0，0.35，1.0，1.0，12.5，7.0，1.875，Y}，

x₁₄＝{11.0，1.0，0.0，8.0，18.0，13.0，7.0，1.0，11.0，0.775，130.0，1.0，1.0，0.0，0.29，1.0，1.0，10.45，7.0，1.36，N}。

步骤3：使用核主成分分析方法进行特征提取。

请见图3，本发明采用核主成分分析提取代表性特征，揭示原始数据潜在的复杂结构。核主成分分析使用非线性映射函数将低维空间内的每个原始数据点映射为高维特征空间F内的新点。给定数据集{x_i，y_i}，i＝1，2，...，n，其中x_i＝[x_i1，x_i2，...，x_im]^T∈R^m表示特征集，y_i＝[y_i1，y_i2，...，y_ic]^T∈R^c表类标号集。此时数据集可表示为{(x₁，y₁)，(x₂，y₂)，...，(x₁₄，y₁₄)}。

步骤3.1，映射特征向量，并且对角化及归一化。

假设每个数据点x_i被映射到新的点并且映射的数据点集中：

映射特征的协方差矩阵C的计算公式如下：

为在高维空间F执行线性主成分分析，将协方差矩阵C对角化，可被视为以下特征值问题的解：

CV＝λV(3)

其中λ和V表示协方差矩阵C的特征值和特征向量，由于所有的解V都位于的跨度中，本实施例将(3)式的两边同时乘以得到：

同时，存在系数α₁，α₂，...，α_m，使得可线性表示协方差矩阵C的特征向量：

将式(2)和式(5)带入式(4)：

步骤3.2，定义核函数以及核矩阵。

定义核函数κ(x_i，x_j)为：

则式(6)可被写为：

定义大小为n×n的核矩阵K_i，j：

式(9)可以被写为：

K²α＝nλKα(10)

其中α＝[α₁，α₂，...，α_n]^T。

式(10)的解相当于求解非零特征值λ和其对应的特征向量α：

Kα＝nλα(11)

步骤3.1是假设映射的数据点集中；若不集中，则使用Gram矩阵来代替内核矩阵K：

其中1_n表示所有值等于1/n的n×n矩阵

同理只需解决下列公式的特征向量：

步骤3.3，计算特征向量的映射，提取特征值。

为了提取新的测试数据点的非线性主成分，计算第k个核分量的映射：

核主成分分析采用内核技巧，通过计算两个数据点的内积来简化特征映射，而不是明确地计算出内核函数被定义为：

其中||·||表示l₂范数，2σ²＝ω表示高斯函数的宽度。

为消除数据中的潜在噪声，在潜在特征空间中执行主成分分析时，我们保持最重要的主要组成部，提取累积贡献率达到95％的特征值。

经过计算，17个属性：加权方法数(wmc)，继承树深度(dit)，孩子数(noc)，对象类之间的耦合度(cbo)，类的响应(rfc)，内聚缺乏度(lcom)，传入耦合(ca)，传出耦合(ce)，公开方法数(npm)，代码行数(loc)，数据访问度量(dam)，聚合度量(moa)，功能抽象度量(mfa)，方法间的内聚度(cam)，继承耦合(ic)，方法间耦合(cbm)的累计贡献率达到96.43％＞95％，因此选择上述17个属性进行下一步的建模。因此原始训练数据被转换为具有17维度的新集合{x_i′，y_i}∈R¹⁷×R^c(i＝1，2，...，14)。

步骤4，利用提取后的特征，采用极限学习机构建缺陷预测模型。

请见图4，步骤4的具体实现包括以下子步骤：

步骤4.1，随机分配隐藏层的的输入权重向量w_i和偏差b_i(i＝1，2，...，q)。

给定具有n个任意不同样本的数据集{x_i′，y_i}∈R^m1×R^c，i＝1，2，...，n，隐藏节点个数q和激活函数h(x′)。广义单隐层前馈网络(SLFN)的输出可表示为：

其中j＝1，2，...，n，w_i＝[w_i1，w_i2，...，w_im1]^T表示连接输入节点和第i个隐藏节点的输入权重向量，b_i表示第i个隐藏节点的偏差，β_i＝[β_i1，β_i2，...，β_ic]^T表示连接输出节点和第i个隐藏节点的输出权重向量，o_j表示第j个样本的预期输出。

经过特征提取后的实例样本为：

x₁＝{3.0，1.0，0.0，8.0，14.0，3.0，3.0，5.0，3.0，2.0，85.0，0.0，0.0，0.0，0.5，0.0，0.0，Y}，

x₂＝{13.0，1.0，0.0，1.0，17.0，64.0，0.0，1.0，12.0，0.917，117.0，1.0，0.0，0.0，0.462，0.0，0.0，N}，

x₃＝{4.0，1.0，0.0，4.0，4.0，6.0，2.0，2.0，4.0，2.0，4.0，0.0，0.0，0.0，1.0，0.0，0.0，N}，

x₄＝{10.0，1.0，0.0，6.0，31.0，1.0，0.0，6.0，9.0，0.5，156.0，1.0，1.0，0.0，0.355555556，0.0，0.0，Y}，

x₅＝{7.0，1.0，0.0，6.0，19.0，7.0，0.0，6.0，6.0，0.75，117.0，1.0，2.0，0.0，0.367，0.0，0.0，N}，

x₆＝{38.0，1.0，0.0，30.0，155.0，485.0，0.0，30.0，34.0，0.9，1564.0，1.0，7.0，0.0，0.14，0.0，0.0，Y}，

x₇＝{25.0，1.0，0.0，13.0，74.0，0.0，0.0，13.0，23.0，0.444，901.0，1.0，2.0，0.0，0.2，0.0，0.0，Y}，

x₈={13.0，1.0，0.0，19.0，56.0，54.0，0.0，19.0，11.0，0.9，224.0，1.0，4.0，0.0，0.17，0.0，0.0，Y}，

x₉={7.0，4.0，4.0，48.0，12.0，19.0，47.0，1.0，6.0，0.94，44.0，0.33，0.0，0.867，0.458，0.0，0.0，N}，

x₁₀={7.0，1.0，0.0，4.0，7.0，21.0，2.0，2.0，7.0，2.0，7.0，0.0，0.0，0.0，0.357142857，0.0，0.0，Y}，

x₁₁={4.0，1.0，0.0，2.0，4.0，6.0，2.0，0.0，4.0，2.0，4.0，0.0，0.0，0.0，0.875，0.0，0.0，N}，

x₁₂＝{35.0，1.0，0.0，29.0，121.0，373.0，0.0，29.0，31.0，0.9，1250.0，1.0，5.0，0.0，0.17，0.0，0.0，Y}，

x₁₃＝{8.0，1.0，0.0，16.0，21.0，14.0，13.0，3.0，8.0，0.81，111.0，1.0，0.0，0.0，0.35，1.0，1.0，Y}，

x₁₄={11.0，1.0，0.0，8.0，18.0，13.0，7.0，1.0，11.0，0.775，130.0，1.0，1.0，0.0，0.29，1.0，1.0，N}。

为测试的准确度，随机生成100组权重w和偏差b，得到大小为17*100的权重矩阵W，14*100的偏差矩阵B。

步骤4.2，依据权重向量w_i和偏差b_i，构建隐层输出矩阵H。一旦输入权重向量w_i和隐层节点的偏置b_i的值被随机分配，H的解被唯一确定。SLFN的隐层输出矩阵H被定义为：

其中H的第i列表示相对于输入样本的第i个隐藏节点的输出向量x₁′，x₂′，...，x_n′，第H行表示输出向量隐藏层相对于输入样本x_j′。

上述实例通过计算得到大小为14*100的隐层输出矩阵H。

步骤4.3，计算输出权重矩阵β。

β表示连接隐层和输出层的权重矩阵：

步骤4.4，求得极限学习机的输出权重，获得预测函数。

广义单隐层前馈网络(SLFN)的输出式(16)可写为

Hβ＝O(19)

O表示期望的标签矩阵，每行代表一个样本的输出向量。

由于训练SLFN的目的是使输出误差最小化，即以零误差逼近输入样本：

其中表示目标输出矩阵。

重点是计算下面的公式：

Hβ＝Y(22)

对于极限学习机，可以独立地随机指定输入连接的权重w_i和隐层节点的偏置b_i。一旦这些参数被随机分配，H的解被唯一地确定。因此，(22)式被转换为线性模式，并且通过找到线性模式的最小二乘解可以分析地确定输出权重矩阵β，即：

minβ||Hβ-Y||(23)

其中||·||表示Frobenius规范。(23)式的最优解为：

其中表示隐层输出矩阵的Moore-Penrose广义逆。获得的可以确保最小的训练误差，获得最优的泛化能力，并避免唯一而陷入局部最优。极限学习机的分类函数如下所示：

上述实例经计算可得目标输出矩阵T，以及隐层输出矩阵的Moore-Penrose广义逆从而得到极限学习机的预测函数f(x)。

步骤5：用训练得到的预测模型预测待测程序模块。如待测程序模块：x＝{2.0，1.0，0.0，2.0，4.0，4.0，2.0，3.0，4.0，7.6，2.3，9.5，2.0，4.0，0.0，0.0，0.0，0.875，0.0，0.0}.

步骤5.1，待测程序模块的特征筛选。提取出待测程序模块相应特征：加权方法数(wmc)，继承树深度(dit)，孩子数(noc)，对象类之间的耦合度(cbo)，类的响应(rfc)，内聚缺乏度(lcom)，传入耦合(ca)，传出耦合(ce)，公开方法数(npm)，代码行数(loc)，数据访问度量(dam)，聚合度量(moa)，功能抽象度量(mfa)，方法间的内聚度(cam)，继承耦合(ic)，方法间耦合(cbm)，生成新数据实例x＝{2.0，1.0，0.0，2.0，4.0，4.0，2.0，3.0，4.0，7.6，2.3，9.5，2.0，4.0，0.0，0.0，0.0}。

步骤5.2，判定目标的类标号。将新的数据实例带入到步骤5中训练的极限学习机预测模型中，预测待测程序模块有无缺陷，经计算得到f(x)＝0，因此实例x无缺陷。

应当理解的是，本说明书未详细阐述的部分均属于现有技术。

应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。