基于字典学习的软件缺陷检测算法

张蕾　朱义鑫　徐春

摘要：

针对目前存在的字典学习方法不能有效构造具有鉴别能力字典的问题，提出具有鉴别表示能力的字典学习算法，并将其应用于软件缺陷检测。首先，重新构建稀疏表示模型，通过在目标函数中设计字典鉴别项学习具有鉴别表示能力的字典，使某一类的字典对于本类的样本具有较强的表示能力，对于异类样本的表示效果则很差；其次，添加Fisher准则系数鉴别项，使得不同类的表示系数具有较好的鉴别能力；最后对设计的字典学习模型进行优化求解，以获得具有强鉴别和稀疏表示能力的结构化字典。选择经过预处理的NASA软件缺陷数据集作为实验数据，与主成分分析（PCA）、逻辑回归、决策树、支持向量机（SVM）和代表性的字典学习方法进行对比，结果表明所提出的具有鉴别表示能力的字典学习算法的准确率与Fmeasure值均有提高，能在改善分类器性能的基础上提高检测精度。

关键词：

字典学习；稀疏表示；Fisher准则；软件缺陷检测；机器学习

中图分类号：

TP399

文献标志码：A

Abstract：

Since the exsiting dictionary learning methods can not effectively construct discriminant structured dictionary， a discriminant dictionary learning method with discriminant and representative ability was proposed and applied in software defect detection. Firstly， sparse representation model was redesigned to train structured dictionary by adding the discriminant constraint term into the object function， which made the classdictionary have strong representation ability for the corresponding classsamples but poor representation ability for the irrelevant classsamples【and vice versa什么鬼，作者檢查确认. Secondly， the Fisher criterion discriminant term was added to make the representative coefficients have discriminant ability in different classes. Finally， the optimization of the designed dictionary learning model was solved to obtain strongly structured and sparsely representative dictionary. The NASA defect dataset was selected as the experiment data， and compared with Principal Component Analysis （PCA）， Logistics Regression （LR）， decision tree， Support Vector Machine （SVM） and the typical dictionary learning method， the accuracy and Fmeasure value of the proposed method were both increased. Experimental results indicate that the proposed method can increase detection accuracy with improving the classifier performance.

英文关键词Key words：

dictionary learning； sparse representation； Fisher criterion； software defect detection； machine learning

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={x1，x2，…，xN}∈Rm×n，其中xi表示X中的某一个样本，根据稀疏表示理论xi可以通过样本集X中的样本以线性组合的形式进行表示：

4实验分析

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

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）定义为无缺陷数据预测正确预测为无缺陷数据。

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

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

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

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

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

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

Fmeasure=2*β*re*pre/（re+β2pre）

（18）

在实验中取β的值为1，即通常所说的F1measure值。其中re是召回率，pre是缺陷检测准确率，另外定义pf表示为错误接受率，acc表示准确率。从以上定义显然可以看出，所有的评估指标的取值范围均在0～1。

4.3实验结果及分析

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

4.4实验分析

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

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

5结语

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

参考文献：

[1]

BAGGEN R， CORREIA J P， SCHILL K， et al. Standardized code quality benchmarking for improving software maintainability [J]. Software Quality Journal， 2012， 20（2）： 287-307.

[2]

SHEPPERD M， SONG Q， SUN Z， et al. Data quality： some comments on the nasa software defect datasets [J]. IEEE Transactions on Software Engineering， 2013， 39（9）： 1208-1215.

[3]

MA Y， LUO G， ZENG X， et al. Transfer learning for crosscompany software defect prediction [J]. Information and Software Technology， 2012， 54（3）： 248-256.

[4]

WANG S， YAO X. Using class imbalance learning for software defect prediction [J]. IEEE Transactions on Reliability， 2013， 62（2）： 434-443.

[5]

SONG Q， JIA Z， SHEPPERD M， et al. A general software defectproneness prediction framework [J]. IEEE Transactions on Software Engineering， 2011， 37（3）： 356-370.