基于机器学习的软件缺陷预测研究

□□□□□□□□□作者单位：100080北京中国科学院软件研究所互联网实验室1基于机器学习的软件缺陷预测研究刘旸[摘要]基于机器学习的软件缺陷预测是一种有效的提高软件可靠性的方法。该方法基于软件模块的统计特性预测软件模块可能出现的缺陷数或是否容易出现缺陷。通过对软件模块缺陷状况的预测，软件开发组织可以将有限的资源集中于容易出现缺陷的模块，从而有效的提高软件产品的质量。基于机器学习的软件缺陷预测近年来出现了很多研究成果，本文概述该领域近年来的主要研究成果，并根据各方法的特点进行了分类。[关键词]软件缺陷预测；机器学习SurveyonSoftwarePredictionbasedonMachineLearningLiuYangLabforInternetSoftwareTechnologiesInstituteofSoftware[Abstract]SoftwareQualityPredictionBasedonMachineLearningisaneffectivewaytoimprovesoftwarereliability.Thistechnologypredictsthenumberoffaultsinsoftwaremoduleorwhetherasoftwaremoduleisfault-proneornotbasedonstatisticalfeatureofsoftwaremodule.Accordingtothepredictionoffaultsinsoftwaremodule,softwaredevelopingorganizationcanfocusonfault-pronemoduletoimprovesoftwarequalityeffectively.Thistechnologyisnowaprovenwaytoimprovesoftwarequality.Improvementemergedinrecentyearsaboutit.Thispaperwillstudytheseimprovementsbycategories.[keyword]SoftwareFaultPrediction;MachineLearning1.引言在软件度量工作中，与软件产品相关的常用度量元可以分为静态度量元和动态度量元两类。静态度量元可以通过对软件产品的静态统计得到，如代码行数、函数/方法的数量等等，这些度量元也称作统计度量元。与之对应的，需要在产品运行过程中采集的非统计性的度量元也称作动态度量元或动态指标。如缺陷数量。软件缺陷是指可运行产品中会导致软件失效的瑕疵[1][2]。软件缺陷数量属于动态度量元，需要通过对产品进行完整测试才能获得。针对软件模块进行完整测试成本高昂，并且必须在软件产品开发完成之后才能进行测试，因而难以控制软件产品缺陷数量。为了更好的提高软件质量，对软件模块的缺陷进行预测是一个可行的方法。软件缺陷预测方法的假定前提是软件的复杂度和软件的缺陷数量有密切关系。复杂度高的软件模块会比复杂度低的模块包含更多的缺陷。软件缺陷预测的思路是使用静态度量元表征软件的复杂度，进而预测软件模块可能的缺陷数量或者发生缺陷的可能性。通过机器学习进行软件缺陷预测，能够以较低的成本在项目开发的早期预测产品的缺陷分布状况，以便调整有限的项目资源，集中处理可能出现较多缺陷的高风险模块，从而提高软件产品整体的质量。基于机器学习的早期缺陷预测已经被证明是获得高软件可靠性的有效方法[1]。基于机器学习的的缺陷预测包含3个步骤：1.选择适当的统计度量元集合并采集软件产品的统计数据；2.构造预测模型；3.将统计数据输入预测模型得到预测结果。在实际的应用中，根据应用环境、开发项目、开发组织等等的不同，预测方法所选取的度量元集合通常会有所不同。常用的表示复杂度的度量元有代码行LOC等。研究表明，使用多度量元能够更好的表达程序的特征，从而更好的预测软件缺陷[8]。度量元的选取在很大程度上仍然依赖于度量人员的经验。目前的研究多集中于使用面向对象或面向过程技术的传统软件产品的缺陷预测。虽然不同度量元的数据采集方法不同，但在步骤2的预测算法中对不同的度量元并不区分处理，预测算法具有通用性。2.常用的预测方法□□□□□□□□□作者单位：100080北京中国科学院软件研究所互联网实验室2在基于机器学习的软件缺陷预测方法中，预测模型是最核心的部分。在确定度量元并按照这些度量元在实际项目中采集一定数据之后，预测方法将根据采集到的数据建立预测模型。这样在输入度量元数据时，模型即可预测模块的缺陷状况。根据建立预测模型方法的不同，以下将对缺陷预测中常用的一些机器学习预测方法进行分类说明。按照预测目标的不同，缺陷预测方法可以为分类思路和回归思路两类。分类思路将软件模块分为三类：高缺陷率模块、低缺陷率模块和中等缺陷率模块。也有一些研究将其简化为高缺陷率模块（fault-prone，fp）和低缺陷率模块（nonfault-prone，nfp）两类。此时预测问题转化为模式识别问题。预测算法根据已有训练集的数据，判断未知的软件模块是否属于有高缺陷风险的那一类。分类思路在一定程度上减少了训练数据中噪音的干扰。同时模式识别也是人工智能/机器学习领域研究热点之一，模式识别领域的一些研究成果可以方便的应用在分类思路上。分类思路可以应用的预测方法有：线性判别分析LDA，布尔判别函数BDF，分类回归树CART，优化集精简方法OSR，人工神经网络ANN，聚类分析Clustering。回归思路采用回归分析的思路，将所需要预测的缺陷数量/软件质量指标看作依赖于统计度量元的连续函数，用预测模型逼近这个未知的函数。此时预测问题转化为对于一个未知多元函数的拟合问题。回归思路可以应用的预测方法有：多线性回归MLR，CART，OSR，ANN。可以看到有一些预测方法可以同时应用于分类和回归思路。由于软件开发存在着很多的不确定因素，因此训练数据中不可避免的带有噪音。预测算法一方面要尽可能的从训练数据中提取问题的规律，另一方面也要避免由于预测算法对训练数据的过度适应而影响算法的泛化能力（Generalization）。3.基于机器学习的软件缺陷预测实现3.1主分量分析PCA主分量分析（PrincipleComponentAnalysis，PCA）也称作KL变换。在缺陷预测领域，PCA被用于去除统计度量元数据之间的相关性并进行度量元数据维度压缩。直接从软件项目中得到的软件度量数据通常都有很强的相关性。这样的数据通常会降低预测模型的稳定性和预测结果的精度。因此很多研究使用PCA去除数据的相关性。PCA的目标是寻找可逆的线性变换Q，使得对aQx的截断在均方误差意义下最优。这里的x是输入的度量数据向量，a是x线性变换得到的结果。即要求变换后的分量具有依次降低的方差。当满足此条件时，12,,...,TmQqqq中的单位向量jq代表主方向，输入向量x在jq上的投影Tjjaqx即为第j个主分量。jq满足10ijqq，jiji。原始度量数据经过线性变换得到的结果称作主分量（PrincipleComponent，PC）或领域特征。通过丢弃一些方差比较小的领域特征，可以达到维数压缩的目的：1212,,...,,,...,TTTTTlmaaaqqqx，lm研究表明PCA方法能够有效地去除数据相关性，提高缺陷预测的准确性[4][5][6]。3.2线性判别分析LDA线性判别分析（LinearDiscriminantAnalysis，LDA）也称作费舍尔（Fisher）判别方法。在缺陷预测领域中用于高缺陷风险的程序识别[8]。LDA的数学表述如下：为了实现最优分类，需要知道后验概率Pr|GX。设kfx是类Gk中X的类条件密度，而k是类k的先验概率，并且11Kkk。由贝叶斯定理有：1Pr|kkKlllfxGkXxfx用多元高斯分布对每个类密度建模，每个类具有共同的协方差矩阵k，k。为了比较两个类k和l，考察对数比率有：11Pr|logloglogPr|1log2kkllTTkklklkllGkXxfxGlXxfxx判定规则的等价描述为：□□□□□□□□□作者单位：100080北京中国科学院软件研究所互联网实验室3111log2TTkkkkkxx其中argmaxkkGxxLDA的学习过程就是根据训练数据估计高斯分布参数的过程：1///iikkkikgkTKkkiikgkNNxNxxNKLDA的特点决定了它只能应用于分类思路。LDA的优点是易于实现，计算复杂度低。但由于LDA假设预测对象的每个分类都服从具有相同协方差矩阵的多元高斯分布，因而预测能力比较差，不能适应软件度量数据之间复杂的关系。研究表明LDA的分类性能低于ANN[21]。3.3多线性回归MLR多线性回归（MultipleLinearRegression，MLR）方法是一种统计学方法，用于估计或者预测自变量为一系列已知变量的函数。MLR也称为回归分析（RegressionAnalysis，RA）。常用的MLR模型有如下的形式：011011......iipipiipipiyaaxaxyaaxaxe这里1,...,iipxx是采集到的度量数据，0,...,paa是需要估计的参数，iy是预测的输出值，iy是实际的输出值，iiieyy是第i次数据预测的误差。在MLR中训练过程也就是确定模型参数的过程，该过程也称为模型选择。MLR有多种不同的模型选择方法可以使用。在渐进回归方法[6]中会对自变量集合进行优化调整，首先决定选用或者不选用某些自变量，然后按照最小平方的原则估计参数。为了提高回归分析的适应能力，1992年Khoshgoftaar[9]提出用相对最小平方（RelativeLeastSquare，RLS）和平均相对误差（AverageRelativeError，ARE）作为误差函数进行线性回归。MLR方法相对比较简单，易于实现。研究结果表明MLR方法预测性能一般[6]。3.4布尔判别函数BDF布尔判别分析（BooleanDiscriminantFunction）的想法类似于LDA，但不同的是在BDF中针对每一个度量元设置了一个关键值（criticalvalue）或称阈值。如果有任意一个度量元超过这个阈值，则将该模块判定为高风险或者高缺陷模块，否则判定为低缺陷模块。即：ifpClassxnfp当ETrueEFalse这里1122...iiimmExcxcxc。fp表示高缺陷风险，nfp表示低缺陷风险。imx表示采集到的度量数据，mc表示阈值。BDF的优点是可以在训练过程中人为的调整1类错误（将低风险模块预测为高风险模块）和2类错误（将高风险模块预测为低风险模块）的比例。BDF的缺点在于判定低风险模块的条件过于苛刻，虽然很少产生2类错误，但1类错误率非常高，造成项目有限的资源浪费在大量错判为高风险的模块上。针对这个问题，Khoshgoftaar提出改进的GBDF方法[7]。在GBDF中增加了参数c，对于一个3m、1c的判别问题，其判别函数如下：ifpClassxnfp当3131mcmcETrueEFalse这里311122mciiimmExcxcxc。GBDF一定程度上放宽了对于低风险模块的判别条件，因此降低了1类错误率。但是对一些关键性的软件产品如与生命安全直接相关的软件产品，软件开发组织通常并不在意过高的1类错误率。在这些情况下使用BDF仍然是最好的选择。3.5基于样本的推理CBR基于样本的推理（CaseBasedReasoning，CBR）的思路是通过获取过去相似的事