0 引言

随着计算机信息科学的飞速发展，软件技术已经渗透到科学、工业、经济和文化的各个领域，对人类社会的进步和发展起着举足轻重的作用，同时影响和改变着人们工作、学习和生活的方式^[1]。一方面，软件技术的发展和应用水平已经成为衡量一个国家科学技术实力的标志，但是另一方面，随着软件规模、复杂度、系统集成度的不断上升，软件中存在的缺陷问题大大影响了产品开发的质量和效率^[2-3]，甚至历史上一些由于软件缺陷而造成的事故也频频发生，比如1962年美国国家宇航局(National Aeronautics and Space Administration, NASA)马里纳1号空间探测器由于Fortran语言少写了一个连字符造成火箭偏离，其损失约8000万美元；20世纪80年代由于错误的软件导致对癌症患者的致命过量辐射事故；20世纪90年代丹麦机场行李处理系统的缺陷导致行李箱损坏，为此花费大量金钱及人力恢复正常运营等。

软件缺陷^[4-5]通常指计算机软件或者代码中能引起失效的错误的编码。在软件工程领域，合理地预测缺陷能够有助于及时找出未被发现但是真实存在的缺陷以及缺陷分布^[6]，因此不仅可以节约大量的成本，提高产品质量，还能够客观地评价测试结果，让开发者合理地权衡潜在的预测风险和测试成本之间的关系，便于科学地进行软件测试工作。虽然不同度量元的数据采集方法不同，但在预测算法中对不同的度量元并不区分处理，预测算法具有通用性。

软件缺陷检测技术^[7]分为动态检测和静态检测技术。前者主要靠研究人员通过统计分析、经验研究等方式来考察软件缺陷随软件周期的分布，一些软件的可靠性模型便是基于这类技术；后者通过分析利用软件的规模、复杂度、软件缺陷的度量元等特征数据来预测软件中潜在的缺陷。本文的研究内容针对后者，即静态的软件缺陷检测技术。比如来源于NASA的著名软件度量程序(Metric Data Program, MDP)^[8]，其主要针对于软件度量元数据的收集、组织、存储等情况，这个公开项目已经成为软件缺陷检测领域经典的数据集。

1 相关算法

目前，机器学习算法得到了飞速的发展，其中一些具有代表性的算法已被用于软件缺陷检测领域，比如支持向量机(Support Vector Machine，SVM)^[9-10] 、分类回归树(Classification and Regression Tree, CART)^[11]、人工神经网络(Artificial Neural Network, ANN)^[12]、主成分分析(Principal Component Analysis, PCA)^[13-14]、聚类分析(Cluster Analysis, CA)^[15-16]、Logistics回归(Logistics Regression, LR)方法^[17-18]等。

字典学习方法^[19-20]实质上基于稀疏表示方法(Sparse Representation)，其通过训练样本构造结构化的字典，使用学习得到的结构化字典对样本进行线性编码，然后利用编码之后的重构误差对样本进行分类，其已被广泛用在信号压缩、图像分类等领域。从目前来看，尽管经典的机器学习方法已经被广泛用于软件缺陷检测领域，但是基于字典学习的方法仍未被利用。从本质上来看，软件度量数据集中的数据依然可以看成是某种形式的信号，因此基于字典学习的算法完全可以应用在软件缺陷检测领域。

常规的字典学习算法不能有效利用数据集之中不同类样本的鉴别性质，具体表现在不能有效构造具有鉴别性质的结构化字典。本文提出了一种基于鉴别字典学习(Discriminant Dictionary Learning, DDL)的软件缺陷检测方法，其通过在传统的字典学习模型目标函数之中加入鉴别约束项来构造具有鉴别性质的字典原子以提高模型的分类性能。

2 本文算法

传统的字典学习模型没有较好的鉴别能力，其仅简单地考虑整体字典对于某个数据样本的表示，而没有考虑不同类字典之间的表示关系。本文对传统的字典学习模型进行两点改进：1) 在字典学习模型中，整体字典对某一个样本应该具有较强的表示能力，同时，如果单独考虑这个样本所在类的字典应该也对其具有较强的表示能力，而该类字典对其他类样本则表示能力很差，因此通过引入鉴别约束项可以满足此条件，以达到很好的鉴别性能；2) 字典学习的目的是通过求解表示系数对样本进行表示，因此可以考虑使用字典对不同类样本进行稀疏表示时，它们的表示系数之间应该具有较强的区分能力，从而进一步达到鉴别的目的。本文所提出的基于字典学习的软件缺陷检测流程如图 1所示。

3 基于字典学习的软件缺陷检测算法 3.1 稀疏表示分类器

稀疏表示最早在信号处理领域中得到应用。由于小波变换和傅里叶变换技术的发展，科研人员需要处理的数据维数越来越高，稀疏表示分类(Sparse Representation Classification, SRC)技术开始引起了研究人员的极大兴趣，并逐步发展形成了一个独立性的理论方法，并且推广到了机器学习、图像处理及模式识别等领域^[21]。假设存在一个样本集X={x₁, x₂, …, x_N}∈R^m×n, 其中x_i表示X中的某一个样本，根据稀疏表示理论x_i可以通过样本集X中的样本以线性组合的形式进行表示：

$ {\boldsymbol{x}_i} = \sum\limits_{j = 1}^N {{d_{i,j}}{x_j} = } \boldsymbol{X}{\boldsymbol{d}_i} $

(1)

其中：

d_{i, j}为表示系数，d_i=[d_{i, 1}, d_{i, 2}, …, d_{i, t-1}, 0, d_{i, t+1}, …, d_{i, j-1}, d_{i, j}, d_{i, j+1}, …, d_iN]^T是稀疏系数向量，0表示x_i不参与重构。系数d可以转化为如下形式的优化问题:

$ \begin{gathered} \mathop {\min }\limits_{{\boldsymbol{d}_i}} {\left\| {{\boldsymbol{d}_i}} \right\|_0} \hfill \\ s.t.\;\;\;\;{\boldsymbol{x}_i} = \boldsymbol{X}{\boldsymbol{d}_i} \hfill \\ \end{gathered} $

(2)

式(2)是一个NP难问题，较难求解，可以使用l₁范数取代l₀范数转化得到下式等价的优化问题：

$ \begin{gathered} \mathop {\min }\limits_{{\boldsymbol{d}_i}} {\left\| {{\boldsymbol{d}_i}} \right\|_1} \hfill \\ s.t.\;\;\;\;{\boldsymbol{x}_i} = \boldsymbol{X}{\boldsymbol{d}_i} \hfill \\ \end{gathered} $

(3)

由于噪声和观察值误差的存在，可以放宽上述优化问题的约束条件，得到下式优化问题。

$ \begin{gathered} \mathop {\min }\limits_{{\boldsymbol{d}_i}} {\left\| {{\boldsymbol{d}_i}} \right\|_1} \hfill \\ s.t.\;\;\;\;\left\| {{\boldsymbol{x}_i} = \boldsymbol{X}{\boldsymbol{d}_i}} \right\| < \varepsilon \hfill \\ \end{gathered} $

(4)

其中ε为误差阈值。式(4)可以通过标准线性规划求解。

3.2 鉴别字典学习方法

传统的字典学习方法难以学习具有鉴别表示能力的结构化的字典，因为其所有的训练样本共享一个字典集合，本文通过添加鉴别项对其进行改进，最终在学习过程中得到一个结构化的鉴别字典D=D₁, D₂, …, D_i, …, D_c], 其中D_i是关于第i类样本的子字典，c是样本的总个数，在训练鉴别的结构化字典之后对数据集进行稀疏表示重构，最后通过重构的误差来进行分类工作，这一过程和SRC分类器类似。

定义A=A₁, A₂, …, A_i, …, A_c]为给定的训练样本集合，其中A_i为第i类的子样本集合，定义X=X₁, X₂, …, X_i, …, X_c]为A关于字典集合D的表示系数矩阵，即使用这些系数对于样本集合进行线性组合表示：

$ \boldsymbol{A} \approx \boldsymbol{DX} $

(5)

其中, X_i是第i类样本A_i关于D集合训练得到的表示系数。在本文提出的鉴别字典模型中，不仅要求字典D能够对整体的原始样本集合A有较强的重构能力，同时也需要对于A中每个不同的类别有较强的鉴别能力，基于此设计了包含字典鉴别项的学习模型，其数学模型如下：

$ {\boldsymbol{J}_{\left( {\boldsymbol{D},\boldsymbol{X}} \right)}} = \mathop {\arg \min }\limits_{\left( {\boldsymbol{D},\boldsymbol{X}} \right)} \left\{ {r\left( {\boldsymbol{A},\boldsymbol{D},\boldsymbol{X}} \right) + \lambda {{\left\| \boldsymbol{X} \right\|}_1}} \right\} $

(6)

其中r(A, D, X)是鉴别精确项，其能够较好地衡量样本的鉴别能力，‖X‖₁为稀疏表示系数；参数是一个平衡因子。对于某一类样本的稀疏表示系数X_i可以表示为X_i=X_i¹, X_i², …, X_i^c], 其中X_i^j是A_i关于子字典D_j的编码系数矩阵。定义字典D_k对A_i的稀疏表示为：

$ {\boldsymbol{R}_k} = {\boldsymbol{D}_k}\boldsymbol{X}_i^k $

(7)

鉴别字典学习模型首先需要使整体字典D能够尽可能近似地表示出任一类样本集合A_i, 因此需要满足下式：

$ {\boldsymbol{A}_i}\simeq{\text{【}}\boldsymbol{D}{\boldsymbol{X}_i} = {\boldsymbol{D}_1}\boldsymbol{X}_i^1 + {\boldsymbol{D}_2}\boldsymbol{X}_i^2 + \cdots + {\boldsymbol{D}_i}\boldsymbol{X}_i^i + \cdots + {\boldsymbol{D}_c}\boldsymbol{X}_i^c $

(8)

其次，由于子字典D_i是关于第i类的，显然希望尽可能地使得第i类样本A_i也能够由相应类的子字典D_i (非D_j)进行近似表示，此时误差项‖A_i-DX_i‖_F²及‖A_i-D_iX_iⁱ‖_F²均应该最小化；而由不同类的字典表示的值‖D_jX_i^j‖_F²较小。根据以上的分析，最终本文将鉴别项定义为：

$ \begin{gathered} r\left( {\boldsymbol{A},\boldsymbol{D},\boldsymbol{X}} \right) = \sum\limits_{i = 1}^c {r\left( {{\boldsymbol{A}_i},\boldsymbol{D},{\boldsymbol{X}_i}} \right)} = \\ \sum\limits_{i = 1}^c {\left( {\left\| {{\boldsymbol{A}_i} - \boldsymbol{D}{\boldsymbol{X}_i}} \right\|_F^2 + \left\| {{\boldsymbol{A}_i} - {\boldsymbol{D}_i}\boldsymbol{X}_i^i} \right\|_F^2 + } \right.} \\ \left. {\sum\limits_{j = 1,j \ne i}^c {\left\| {{\boldsymbol{D}_j}\boldsymbol{X}_i^j} \right\|_F^2} } \right) \\ \end{gathered} $

(9)

图 2对式(9)中的各项给予直观的显示。其中图(a)表示如果仅最小化‖A_i-DX_i‖_F²项，那么表示后的样本R_i将可能偏离原始样本A_i，这样会造成子字典D_i并不能较好地表示样本A_i。因此为了使模型能够达到较强的样本重构能力同时兼具较强的鉴别性质，本文添加另外两个约束项‖A_i-D_iX_iⁱ‖_F²及‖D_jX_i^j‖_F²，这两项在提出的目标函数中均要求进行最小化。因此，相应的图(b)表示本文所设计的鉴别模型够较好地解决上述问题。

3.3 Fisher鉴别项

为了进一步改善字典D的鉴别能力，本文考虑在稀疏表示项中添加Fisher鉴别约束项f(X), 以使得使用字典D对图像集A进行表示时有较好的区分能力。因此可以定义关于表示系数矩阵X的类内、类间散度矩阵如下：

$ \begin{gathered} {S_W}\left( \boldsymbol{X} \right) = \sum\limits_{i = 1}^c {\sum\limits_{{\boldsymbol{x}_k} \in {\boldsymbol{X}_i}} {\left( {{\boldsymbol{x}_k} - {\boldsymbol{m}_i}} \right){{\left( {{\boldsymbol{x}_k} - {\boldsymbol{m}_i}} \right)}^T}} } \hfill \end{gathered} $

(10)

$ \begin{gathered} {S_B}\left( \boldsymbol{X} \right) = \sum\limits_{i = 1}^c {{n_i}\left( {{\boldsymbol{m}_i} - \boldsymbol{m}} \right){{\left( {{\boldsymbol{m}_i} - \boldsymbol{m}} \right)}^T}} \hfill \end{gathered} $

(11)

其中：m_i表示第i类表示系数的均值，x_k表示第i类中一个样本表示系数，m为总的样本表示均值，n_i是第i类样本的个数。Fisher鉴别准则的目标函数通常可以化简为tr(S_W(X))/tr(S_B(X))的形式，其中tr( )表示矩阵的迹。另外也有一些专家提出了Fisher鉴别的另一种形式，即散度差形式：

$ f\left( \boldsymbol{X} \right) = tr\left( {{S_W}\left( \boldsymbol{X} \right)} \right) - a \cdot tr\left( {{\boldsymbol{S}_B}\left( \boldsymbol{X} \right)} \right) $

(12)

在本文的目标函数中采用散度差的约束形式以便于优化推导，同时取a的值为1。因此得到的Fisher鉴别项为：

$ f\left( \boldsymbol{X} \right) = tr\left( {{S_W}\left( \boldsymbol{X} \right)} \right) - tr\left( {{S_B}\left( \boldsymbol{X} \right)} \right) $

(13)

式(13)中的目标函数是非凸的，并且不够稳定，本文引入弹性项‖X‖_F², 以使得f(X)能够平滑且收敛；而引入弹性项的另外一个好处是可以和式(6)中的‖X‖₁融合，以便在满足稀疏约束的同时使f(X)更加稳定。因此添加Fisher鉴别约束项后的目标函数由式(6)变换为：

$ \begin{gathered} \mathop {\min }\limits_{\left( {D,X} \right)} \left\{ {r\left( {\boldsymbol{A},\boldsymbol{D},\boldsymbol{X}} \right) + {\lambda _1}{{\left\| \boldsymbol{X} \right\|}_1} + } \right. \hfill \\ \left. {\left. {{\lambda _2}\left( {tr\left( {{S_W}\left( \boldsymbol{X} \right)} \right) - tr\left( {{S_B}\left( \boldsymbol{X} \right)} \right)} \right) + \eta \left\| \boldsymbol{X} \right\|_F^2} \right)} \right\} \hfill \\ s.t.\;\;\;\;{\left\| {{\boldsymbol{d}_n}} \right\|_2} = 1,\forall n \hfill \\ \end{gathered} $

(14)

3.4 模型化简

式(14)可以表示为如下形式：

$ \begin{gathered} \mathop {\min }\limits_{\left( {\boldsymbol{D},\boldsymbol{X}} \right)} \sum\limits_{i = 1}^c {\left( {\left\| {{\boldsymbol{A}_i} - \boldsymbol{D}{\boldsymbol{X}_i}} \right\|_F^2 + \left\| {{\boldsymbol{A}_i} - \boldsymbol{DX}_i^i} \right\|_F^2} \right) + {\lambda _1}{{\left\| \boldsymbol{X} \right\|}_1} + } \hfill \\ \left. {{\lambda _2}\left( {tr\left( {{S_W}\left( \boldsymbol{X} \right)} \right) - tr\left( {{S_B}\left( \boldsymbol{X} \right)} \right) + \eta \left\| \boldsymbol{X} \right\|_F^2} \right)} \right\} \hfill \\ s.t.\;\;\;\;{\left\| {{\boldsymbol{d}_n}} \right\|_2} = 1,\forall n;\left\| {{\boldsymbol{\boldsymbol{D}}_j}\boldsymbol{X}_i^j} \right\|_F^2 \leqslant \varepsilon ,\forall i \ne j \hfill \\ \end{gathered} $

(15)

式(15)中‖D_jX_i^j‖_F²≤ε为约束项，其表示使得非本类的字典对该类样本表示的效果很差。式(15)的表示形式较为复杂，考虑到‖D_jX_i^j‖_F²的值应该很小，近似为0，而且从物理意义来看，其相当于X_i^j=0。因此式(15)可以化简为：

$ \begin{gathered} \mathop {\min }\limits_{\left( {\boldsymbol{D},\boldsymbol{X}} \right)} \sum\limits_{i = 1}^c {\left( {\left\| {{\boldsymbol{A}_i} - \boldsymbol{D}{\boldsymbol{X}_i}} \right\|_F^2 + \left\| {{\boldsymbol{A}_i} - \boldsymbol{DX}_i^i} \right\|_F^2} \right) + } \hfill \\ \;\;\;\;\;{\lambda _1}{\left\| \boldsymbol{X} \right\|_1} + {\lambda _2}\left( {tr\left( {{S_W}\left( \boldsymbol{X} \right)} \right) - tr\left( {{S_B}\left( \boldsymbol{X} \right)} \right) + } \right. \hfill \\ \;\;\;\;\;\left. {\left. {\eta \left\| \boldsymbol{X} \right\|_F^2} \right)} \right\} \hfill \\ s.t.\;\;\;\;{\left\| {{\boldsymbol{d}_n}} \right\|_2} = 1,\forall n;\boldsymbol{X}_i^j{\text{ = }}0,\forall i \ne j \hfill \\ \end{gathered} $

(16)

下面考虑对式(16)进行化简，首先介绍定理1，然后在定理2中给出式(16)的化简过程。

定理1  $tr\left( {{S_B}\left( \boldsymbol{X} \right)} \right){\text{ = }}\sum\limits_{i = 1}^c {{\kappa _i}{n_i}\left\| {\boldsymbol{m}_i^i} \right\|_2^2} $, 其中κ_i=1-n_i/n, m_iⁱ为某一类样本关于同类字典的平均表示系数向量。

证明  首先定义m_iⁱ、m_i和m分别为X_iⁱ、X_i和X的平均向量。考虑到对于i≠j时有X_i^j=0, 因此可以重写为：m_i=[0;…; m_iⁱ; …; 0]和m=[n₁m₁¹; …; n_im_iⁱ; …; n_cm_c^c]/n。

此时$tr\left( {{S_B}\left( \boldsymbol{X} \right)} \right){\text{ = }}\sum\limits_{i = 1}^c {{n_i}\left\| {\boldsymbol{m}_i^i - \boldsymbol{m}} \right\|} $可以化简为：

$ \begin{gathered} tr\left( {{S_B}\left( \boldsymbol{X} \right)} \right){\text{ = }} \hfill \\ \;\;\;\;\sum\limits_{i = 1}^c {{n_i}/{n^2}\left\| {\left[ { - {n_1}\boldsymbol{m}_1^1; \cdots ;\left( {n - {n_i}} \right)\boldsymbol{m}_i^i; \cdots ; - {n_c}\boldsymbol{m}_c^c} \right]} \right\|_2^2 = } \hfill \\ \;\;\;\;\sum\limits_{i = 1}^c {{\kappa _i}{n_i}\left\| {\boldsymbol{m}_i^i} \right\|_2^2} \hfill \\ \end{gathered} $

(17)

定理2  式(16)可以化简为如下形式：

$ \begin{gathered} \mathop {\min }\limits_{\left( {\boldsymbol{D},\boldsymbol{X}} \right)} \sum\limits_{i = 1}^c {\left( {\left\| {{\boldsymbol{A}_i} - {\boldsymbol{D}_i}\boldsymbol{X}_i^i} \right\|_F^2 + {\lambda _1}^\prime {{\left\| {\boldsymbol{X}_i^i} \right\|}_1}} \right. + } \hfill \\ \;\;\;\;\;\left. {{\lambda _2}^\prime \left\| {\boldsymbol{X}_i^i - \boldsymbol{M}_i^i} \right\| + {\lambda _3}^\prime \left\| {\boldsymbol{X}_i^i} \right\|_F^2} \right) \hfill \\ s.t.\;\;\;\;{\left\| {{\boldsymbol{d}_n}} \right\|_2} = 1,\forall n \hfill \\ \end{gathered} $

(18)

其中各项系数的定义为：λ′₁=λ₁/2;λ′₂=λ₂(1+κ_i)/2;κ_i=1-n_i/n; λ′₃=λ₂(η-κ_i)/2；M_iⁱ是由m_iⁱ为列向量组成的矩阵；其他相关定义可参考定理1中的证明。

证明  类似于定理1，类内散度矩阵可以化简为：

$ {S_W}\left( \boldsymbol{X} \right) = \sum\limits_{i = 1}^c {\sum\limits_{{\boldsymbol{x}_k} \in {\boldsymbol{X}_i}} {\left( {\boldsymbol{x}_k^i - \boldsymbol{m}_i^i} \right){{\left( {\boldsymbol{x}_k^i - \boldsymbol{m}_i^i} \right)}^T}} } $

相应的类内散度矩阵的迹为：

$ tr\left( {{S_W}\left( \boldsymbol{X} \right)} \right) = \sum\limits_{i = 1}^c {\sum\limits_{{\boldsymbol{x}_k} \in {\boldsymbol{X}_i}} {\left\| {\boldsymbol{x}_k^i - \boldsymbol{m}_i^i} \right\|_2^2} } $

结合定理1，可以将f(X)进行化简：

$ \begin{gathered} f\left( \boldsymbol{X} \right) = \sum\limits_{i = 1}^c {\left( {\sum\limits_{{\boldsymbol{x}_k} \in {\boldsymbol{X}_i}} {\left\| {\boldsymbol{x}_k^i - \boldsymbol{m}_i^i} \right\|_2^2 + } } \right.} \\ {\kappa _i}\left( {\left\| {\boldsymbol{X}_i^i} \right\|_F^2 - {n_i}\left\| {\boldsymbol{m}_i^i} \right\|_F^2} \right) + \left( {\eta - {\kappa _i}} \right)\left\| {\boldsymbol{X}_i^i} \right\|_F^2 \\ \end{gathered} $

(19)

定义矩阵E_i^j=[1]_nj×nj, M_iⁱ=[m_iⁱ]_1×ni=X_iⁱE_iⁱ/n_i, 此时可以得到：

$ \begin{gathered} \left\| {\boldsymbol{X}_i^i} \right\|_F^2 - {n_i}\left\| {\boldsymbol{m}_i^i} \right\|_F^2 = \left\| {\boldsymbol{X}_i^i} \right\|_F^2 - \left\| {{{\left[ {\boldsymbol{m}_i^i} \right]}_{1 \times {n_i}}}} \right\|_F^2 = \hfill \\ \;\;\;\;{\text{tr}}\left( {\boldsymbol{X}_i^i\left( {I - \boldsymbol{E}_i^i/{n_i}{{\left( {\boldsymbol{E}_i^i/n} \right)}^T}} \right){{\left( {\boldsymbol{X}_i^i} \right)}^T}} \right) = \hfill \\ \;\;\;\;\left\| {\boldsymbol{X}_i^i - \boldsymbol{M}_i^i} \right\|_F^2 \hfill \\ \end{gathered} $

(20)

因此Fisher鉴别项可以化简为：

$ f\left( \boldsymbol{X} \right) = \sum\limits_{i = 1}^c {\left( {\left( {1 + {\kappa _i}} \right)\left\| {\boldsymbol{X}_i^i - \boldsymbol{M}_i^i} \right\|_F^2 + \left( {\eta - {\kappa _i}} \right)\left\| {\boldsymbol{X}_i^i} \right\|_F^2} \right)} $

当i≠j时有X_i^j=0【，因此‖A_i-DX_i‖_F²=‖A_i-D_iX_iⁱ‖_F²。

综合式(16)以及以上各式，最终定理2得以证明。

3.5 鉴别字典学习模型的优化

式(16)中需要求解最终的结构化字典，以使之符合本文提出的算法模型，其优化过程可以通过交替迭代来进行：首先通过固定字典集D来更新系数矩阵X, 然后通固定系数矩阵X来更新字典集D, 通过这种模式来求解所需的结构化字典。

3.5.1 固定字典求解编码系数

首先考虑固定字典D, 那么式(16)可以转化为求解一般性的稀疏编码问题。考虑到本文的软件缺陷检测数据集仅包含两类，相应的系数矩阵X=X₁, X₂], 可以考虑对二者依次迭代求解：通过固定X₁来求解X₂, 然后通过固定X₂来求解X₁。式(16)可以改写为：

$ \mathop {\min }\limits_{{\boldsymbol{X}_i}} \left\{ {r\left( {{\boldsymbol{A}_i},\boldsymbol{D},\boldsymbol{X}} \right) + {\lambda _1}\left\| {{\boldsymbol{X}_i}} \right\| + {\lambda _2}{f_i}\left( {{\boldsymbol{X}_i}} \right)} \right\} $

(21)

$ {f_i}\left( {{\boldsymbol{X}_i}} \right) = \left\| {{\boldsymbol{X}_i} - {\boldsymbol{M}_i}} \right\|_F^2 - \sum\limits_{k = 1}^c {\left\| {{\boldsymbol{M}_k} - \boldsymbol{M}} \right\|_F^2 + \eta \left\| {{\boldsymbol{X}_i}} \right\|_F^2} $

(22)

在满足η > κ_i的情况下式(22)中的目标函数严格凸优化，在本文中取η的值为1，将式(21)改写为如下形式：

$ \mathop {\min }\limits_{{\boldsymbol{X}_i}} \left\{ {Q\left( {{\boldsymbol{X}_i}} \right) + 2\tau {{\left\| {{\boldsymbol{X}_i}} \right\|}_1}} \right\} $

(23)

其中：

$ Q\left( {{\boldsymbol{X}_i}} \right) = r\left( {{\boldsymbol{A}_i},\boldsymbol{D},\boldsymbol{X}} \right) + {\lambda _2}{f_i}\left( {{\boldsymbol{X}_i}} \right) $

(23)

或者：

$ \begin{gathered} Q\left( {{\boldsymbol{X}_i}} \right) = \left\| {{\boldsymbol{A}_i} - {\boldsymbol{D}_i}\boldsymbol{X}_i^i} \right\|_F^2 + {\lambda _2}^\prime \left\| {\boldsymbol{X}_i^i - \boldsymbol{M}_i^i} \right\|_2^2 + \\ {\lambda _3}^\prime \left\| {\boldsymbol{X}_i^i} \right\|_F^2 \\ \end{gathered} $

(24)

$ \tau = {\lambda _1}/2 $

(25)

式(23)可以通过IMP(Iterative Projection Method)以迭代的形式进行求解，为了方便优化，η=κ_i=1-n_i/n, 即λ₃′=0。定义迭代步长σ, 步长的选择对于最终的求解比较关键，具体的推导及取值可以参考文献[22]。定义迭代序列数为h, 软阈值因子如式(26)所示(软阈值因子的详细定义及求解过程可以参见文献[23])。

$ \left[ {{S_{\tau /\sigma }}} \right] = \left\{ \begin{gathered} 0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\| {{\boldsymbol{x}_j}} \right\| > \tau /\sigma \hfill \\ {\boldsymbol{x}_j} - \operatorname{sign} \left( {{\boldsymbol{x}_j}} \right)\tau /\sigma ,\;\;\;\;\left\| {{\boldsymbol{x}_j}} \right\| > \tau /\sigma \hfill \\ \end{gathered} \right. $

(26)

其求解过程如下：

1) 输入：σ和τ, σ > 0, τ > 0。

2) 初始化：X_i⁽¹⁾=0, h=1。

3) 开始迭代：

①迭代终止条件：前后差值开始收敛或达到最终迭代次数。

②迭代次数h=h+1。

③ $\boldsymbol{X}_i^{\left( h \right)} = {S_{\tau /\sigma }}\left( {\boldsymbol{X}_i^{\left( {h - 1} \right)} - \frac{1}{{2\sigma }}\nabla Q\left( {\boldsymbol{X}_i^{\left( {h - 1} \right)}} \right)} \right)$，其中：${\nabla Q\left( {\boldsymbol{X}_i^{\left( {h - 1} \right)}} \right)}$表示对X_i的导数，S的定义如式(26)所示。

4) 返回X_i=X_i^(h)。

3.5.2 固定编码系数求解字典

在3.4.1节中系数矩阵X被求解后固定下来，可以通过轮流更新迭代求解字典D₁和D₂。此时可以将式(18)改写为如下形式：

$ \begin{gathered} {J_{\left( {{\boldsymbol{D}_i}} \right)}} = \mathop {\arg \;\;\min }\limits_{\left( {{\boldsymbol{D}_i}} \right)} \left\{ {\left\| {\boldsymbol{A} - {\boldsymbol{D}_i}{\boldsymbol{X}^i} - \sum\limits_{j = 1,j \ne i}^2 {{\boldsymbol{D}_j}{\boldsymbol{X}^j}} } \right\|_F^2 + } \right. \hfill \\ \;\;\;\;\;\;\;\left. {\left\| {{\boldsymbol{A}_i} - {\boldsymbol{D}_i}\boldsymbol{X}_i^i} \right\|_F^2 + \sum\limits_{j = 1}^2 {\left\| {{\boldsymbol{D}_j}\boldsymbol{X}_i^j} \right\|_F^2} } \right\} \hfill \\ s.t.\;\;\;\;{\left\| {{\boldsymbol{d}_n}} \right\|_2} = 1 \end{gathered} $

(27)

这里的Xⁱ为样本集A关于D_i的编码系数。式(27)是一个凸优化问题，其求解过程具体可以参考文献[24]，由于篇幅所限，本文不再详细介绍。

最终DDL模型的求解步骤如下：。

1) 初始化字典集合D。

2) 固定字典D, 通过3.5.1中的求解过程分别迭代求解系数集合X₁及X₂。

3) 固定步骤2)中的X₁及X₂, 根据文献[24]求解D₁及D₂, 得到最终的结构化字典。

4) 使用SRC分类器对样本进行重构，利用重构之后的误差进行分类工作。

4 实验分析

本文通过引入几种重要的分类器性能指标进行实验对比，并选择来源于美国国家宇航局(NASA)的软件度量程序(MDP)作为实验数据。在实验过程中，将选择支持向量机(SVM)、决策树(C4.5)、主成分分析(PCA)、Logistics回归(LR)方法、具有代表性的字典学习方法DLSDP(Dictionary Learning based Software Defect Prediction)^[25]这几种算法作为对比算法。本文选择Matlab R2011a作为实验工具，实验所用PC配置为Intel酷睿i7 6700 CPU，32 GB内存。

4.1 数据集介绍

本文选择来自NASA的MDP项目进行实验。MDP项目是一个向全球公开的数据度量项目，任何用户均能够从NASA的官网下载其中的数据。MDP项目包含多个软件缺陷数据集子集，本文选择其中的JM1、CM1、KC1、MW1及PC1作为实验对比数据集。以其中的JM1为例，JM1数据集始于某个地面预测系统的软件项目，使用C++进行开发，共有10879个模块、21个软件度量属性以及1维的是否为缺陷的标签，其中21个属性包含总代码行数，McCabe的循环复杂度、基本复杂度、设计复杂度，Halstead程序的级别、容量、工作量、时间、长度等属性。

4.2 分类器性能评价指标

表 1中定义了几种分类的行为，其中正确预测为正类(True Positive, TP)表示在分类过程中实际为有缺陷的数据正确分类为有缺陷；错误预测为负类(False Negative, FN)表示实际为有缺陷的数据预测为无缺陷；错误预测为正类(False Positive, FP)表示实际为无缺陷的数据被预测为有缺陷，正确预测为负类(True Negative, TN)定义为无缺陷数据预测正确预测为无缺陷数据。

由于最终的检测结果是判断数据是否有缺陷，因此是一个两类问题，仅仅通过分类准确率来评价一个算法的有效性是不够全面的，因此在本文的实验中引入召回率、错误接受率、查准率、准确率以及F-measure值较为全面地衡量分类算法的有效性。以下简单介绍这几种值的定义：

1) 召回率：re=TP/(TP+FN)。召回率是一种重要的分类器性能衡量指标，因为在实际应用中需要重点考虑的是有缺陷的数据，其反映了被正确判定的缺陷样本占总的缺陷样本的比重，即衡量有缺陷样本检测的全面程度。

2) 错误接受率：pf=FP/(FP+TN)，其反映了分类结果中无缺陷数据被预测为有缺陷数据的比例。

3) 查准率：pre=TP/(TP+FP), 用来衡量检测到有缺陷样本的准确率。

4) 准确率：acc=(TP+TN)/(TP+FN+FP+TN)，用来衡量着所有正确分类的样本占总样本的比例。

从以上定义看出，一个好的分类器预测模型，希望能满足较高的召回率、缺陷检测准确率以及准确率，较低的错误接受率，尤其是查准率和召回率是两类问题中比较重要的指标。然而，实际情况中，查准率和召回率之间往往难以同时都达到较高的值，需要在二者之间寻求权衡，因此需要折中考虑二者。本文引入F-measure值来考虑衡量准确率和召回率的调和平均数，其被定义为：

$ F - measure = 2*\beta *re*pre/\left( {re + {\beta ^2}pre} \right) $

(18)

在实验中取β的值为1，即通常所说的F1-measure值。从以上定义显然可以看出，所有的评估指标的取值范围均在0~1。

4.3 实验结果及分析

在实验过程中，对于SVM算法采用径向基核，同时选择惩罚因子C=1来分别进行实验。对于本文提出的DDL模型，取迭代步长σ的值为0.1，λ₁的值取0.01，λ₂的值为0.005。为了公平地进行实验，在本文的实验中每种算法最终选择随机进行20组交叉实验验证，以合理地进行算法对比，最终得到的re、pf、pre实验结果如表 2所示，acc以及F1-measure如表 3所示。

4.4 实验分析

从表 2、3可以看出，与其他算法相比，本文提出的DDL算法最终能够将F1-measure提高0.03~0.26，而准确率能够提高0.03~0.20，而召回率、查准率也有一定程度的改善。其主要原因主要是本文提出的字典学习模型具有较强的鉴别分类能力，对比其他几种机器学习方法，字典学习模型本身又有较好的抗干扰能力。而PCA由于其是一种无监督的降维方法，没有有效利用丰富的标签信息，相对于其他集中算法效果最差；LR是一种模型较为简单的回归算法，模型本身不具有鉴别能力，同时从其自身的应该来看，算法泛化能力较差，因此实验效果相对较差；C4.5其容易出现过度拟合的问题，而且其对连续性的字段难以作出准确的预测；对于SVM，其虽然拥有较强的泛化能力，但是需要选择合适的核函数，而SVM本身也具有多种形式的模型，因此如何选择合适的参数也是一个问题，同时SVM也没有很强的鉴别分类能力。

值得一提的是本文选择了DLSDP算法进行对比，可以发现，DLSDP也是一种字典学习方法，由于其在算法中主要使用代价敏感方法来解决类不平衡问题，因此所得到的F-_measure值和本文的算法相比很接近；另一方面，由于其没有考虑不同类字典的鉴别性质，因此在检测精度上略差于本文算法。

5 结语

为解决传统的字典学习方法不能有效构造具有鉴别能力字典的问题，提出了一种新的基于鉴别字典学习的分类算法，并用于软件缺陷检测，即基于鉴别字典学习的软件缺陷检测算法。该算法首先通过添加鉴别表示项以突出不同类字典对不同类样本的表示能力，其次添加Fisher准则系数鉴别项，使得不同类的表示系数具有较好的鉴别能力；然后通过迭代算法求解相应模型的目标函数，最后选择在MDP数据集上进行实验，获得的实验结果表明能够在改善检测性能的基础上提高检测精度。现实当中二分类经常面临正负样本不平衡的问题，在本文提出的算法中，可以通过引入代价敏感约束进一步提高算法的分类性能，考虑不同类样本数目对分类造成的代价影响。