張蕾　朱義鑫　徐春

摘要：

針對(duì)目前存在的字典學(xué)習(xí)方法不能有效構(gòu)造具有鑒別能力字典的問(wèn)題，提出具有鑒別表示能力的字典學(xué)習(xí)算法，并將其應(yīng)用于軟件缺陷檢測(cè)。首先，重新構(gòu)建稀疏表示模型，通過(guò)在目標(biāo)函數(shù)中設(shè)計(jì)字典鑒別項(xiàng)學(xué)習(xí)具有鑒別表示能力的字典，使某一類(lèi)的字典對(duì)于本類(lèi)的樣本具有較強(qiáng)的表示能力，對(duì)于異類(lèi)樣本的表示效果則很差；其次，添加Fisher準(zhǔn)則系數(shù)鑒別項(xiàng)，使得不同類(lèi)的表示系數(shù)具有較好的鑒別能力；最后對(duì)設(shè)計(jì)的字典學(xué)習(xí)模型進(jìn)行優(yōu)化求解，以獲得具有強(qiáng)鑒別和稀疏表示能力的結(jié)構(gòu)化字典。選擇經(jīng)過(guò)預(yù)處理的NASA軟件缺陷數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，與主成分分析（PCA）、邏輯回歸、決策樹(shù)、支持向量機(jī)（SVM）和代表性的字典學(xué)習(xí)方法進(jìn)行對(duì)比，結(jié)果表明所提出的具有鑒別表示能力的字典學(xué)習(xí)算法的準(zhǔn)確率與Fmeasure值均有提高，能在改善分類(lèi)器性能的基礎(chǔ)上提高檢測(cè)精度。

關(guān)鍵詞：

字典學(xué)習(xí)；稀疏表示；Fisher準(zhǔn)則；軟件缺陷檢測(cè)；機(jī)器學(xué)習(xí)

中圖分類(lèi)號(hào)：

TP399

文獻(xiàn)標(biāo)志碼：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什么鬼，作者檢查確認(rèn). 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.

英文關(guān)鍵詞Key words：

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

0引言

隨著計(jì)算機(jī)信息科學(xué)的飛速發(fā)展，軟件技術(shù)已經(jīng)滲透到科學(xué)、工業(yè)、經(jīng)濟(jì)和文化的各個(gè)領(lǐng)域，對(duì)人類(lèi)社會(huì)的進(jìn)步和發(fā)展起著舉足輕重的作用，同時(shí)影響和改變著人們工作、學(xué)習(xí)和生活的方式[1]。一方面，軟件技術(shù)的發(fā)展和應(yīng)用水平已經(jīng)成為衡量一個(gè)國(guó)家科學(xué)技術(shù)實(shí)力的標(biāo)志，但是另一方面，隨著軟件規(guī)模、復(fù)雜度、系統(tǒng)集成度的不斷上升，軟件中存在的缺陷問(wèn)題大大影響了產(chǎn)品開(kāi)發(fā)的質(zhì)量和效率[2-3]，甚至歷史上一些由于軟件缺陷而造成的事故也頻頻發(fā)生，比如1962年

美國(guó)國(guó)家宇航局（National Aeronautics and Space Administration， NASA）馬里納1號(hào)空間探測(cè)器由于Fortran語(yǔ)言少寫(xiě)了一個(gè)連字符造成火箭偏離，其損失約8000萬(wàn)美元；20世紀(jì)80年代由于錯(cuò)誤的軟件導(dǎo)致對(duì)癌癥患者的致命過(guò)量輻射事故；20世紀(jì)90年代丹麥機(jī)場(chǎng)行李處理系統(tǒng)的缺陷導(dǎo)致行李箱損壞，為此花費(fèi)大量金錢(qián)及人力恢復(fù)正常運(yùn)營(yíng)等。

軟件缺陷[4-5]通常指計(jì)算機(jī)軟件或者代碼中能引起失效的錯(cuò)誤的編碼。在軟件工程領(lǐng)域，合理地預(yù)測(cè)缺陷能夠有助于及時(shí)找出未被發(fā)現(xiàn)但是真實(shí)存在的缺陷以及缺陷分布[6]，因此不僅可以節(jié)約大量的成本，提高產(chǎn)品質(zhì)量，還能夠客觀地評(píng)價(jià)測(cè)試結(jié)果，讓開(kāi)發(fā)者合理地權(quán)衡潛在的預(yù)測(cè)風(fēng)險(xiǎn)和測(cè)試成本之間的關(guān)系，便于科學(xué)地進(jìn)行軟件測(cè)試工作。雖然不同度量元的數(shù)據(jù)采集方法不同，但在預(yù)測(cè)算法中對(duì)不同的度量元并不區(qū)分處理，預(yù)測(cè)算法具有通用性。

軟件缺陷檢測(cè)技術(shù)[7]分為動(dòng)態(tài)檢測(cè)和靜態(tài)檢測(cè)技術(shù)。前者主要靠研究人員通過(guò)統(tǒng)計(jì)分析、經(jīng)驗(yàn)研究等方式來(lái)考察軟件缺陷隨軟件周期的分布，一些軟件的可靠性模型便是基于這類(lèi)技術(shù)；后者通過(guò)分析利用軟件的規(guī)模、復(fù)雜度、軟件缺陷的度量元等特征數(shù)據(jù)來(lái)預(yù)測(cè)軟件中潛在的缺陷。本文的研究?jī)?nèi)容針對(duì)后者，即靜態(tài)的軟件缺陷檢測(cè)技術(shù)。比如來(lái)源于NASA的著名軟件度量程序（Metric Data Program， MDP）[8]，其主要針對(duì)于軟件度量元數(shù)據(jù)的收集、組織、存儲(chǔ)等情況，這個(gè)公開(kāi)項(xiàng)目已經(jīng)成為軟件缺陷檢測(cè)領(lǐng)域經(jīng)典的數(shù)據(jù)集。

1相關(guān)算法

目前，機(jī)器學(xué)習(xí)算法得到了飛速的發(fā)展，其中一些具有代表性的算法已被用于軟件缺陷檢測(cè)領(lǐng)域，比如支持向量機(jī)（Support Vector Machine，SVM）[9-10] 、分類(lèi)回歸樹(shù)（Classification and Regression Tree， CART）[11]、人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network， ANN）[12]、主成分分析（Principal Component Analysis， PCA）[13-14]、聚類(lèi)分析（Cluster Analysis， CA）[15-16]、Logistics回歸（Logistics Regression， LR）方法[17-18]等。

字典學(xué)習(xí)方法[19-20]實(shí)質(zhì)上基于稀疏表示方法（Sparse Representation），其通過(guò)訓(xùn)練樣本構(gòu)造結(jié)構(gòu)化的字典，使用學(xué)習(xí)得到的結(jié)構(gòu)化字典對(duì)樣本進(jìn)行線(xiàn)性編碼，然后利用編碼之后的重構(gòu)誤差對(duì)樣本進(jìn)行分類(lèi)，其已被廣泛用在信號(hào)壓縮、圖像分類(lèi)等領(lǐng)域。從目前來(lái)看，盡管經(jīng)典的機(jī)器學(xué)習(xí)方法已經(jīng)被廣泛用于軟件缺陷檢測(cè)領(lǐng)域，但是基于字典學(xué)習(xí)的方法仍未被利用。從本質(zhì)上來(lái)看，軟件度量數(shù)據(jù)集中的數(shù)據(jù)依然可以看成是某種形式的信號(hào)，因此基于字典學(xué)習(xí)的算法完全可以應(yīng)用在軟件缺陷檢測(cè)領(lǐng)域。

常規(guī)的字典學(xué)習(xí)算法不能有效利用數(shù)據(jù)集之中不同類(lèi)樣本的鑒別性質(zhì)，具體表現(xiàn)在不能有效構(gòu)造具有鑒別性質(zhì)的結(jié)構(gòu)化字典。本文提出了一種基于鑒別字典學(xué)習(xí)（Discriminant Dictionary Learning， DDL）的軟件缺陷檢測(cè)方法，其通過(guò)在傳統(tǒng)的字典學(xué)習(xí)模型目標(biāo)函數(shù)之中加入鑒別約束項(xiàng)來(lái)構(gòu)造具有鑒別性質(zhì)的字典原子以提高模型的分類(lèi)性能。

2本文算法

傳統(tǒng)的字典學(xué)習(xí)模型沒(méi)有較好的鑒別能力，其僅簡(jiǎn)單地考慮整體字典對(duì)于某個(gè)數(shù)據(jù)樣本的表示，而沒(méi)有考慮不同類(lèi)字典之間的表示關(guān)系。本文對(duì)傳統(tǒng)的字典學(xué)習(xí)模型進(jìn)行兩點(diǎn)改進(jìn)：1）在字典學(xué)習(xí)模型中，整體字典對(duì)某一個(gè)樣本應(yīng)該具有較強(qiáng)的表示能力，同時(shí)，如果單獨(dú)考慮這個(gè)樣本所在類(lèi)的字典應(yīng)該也對(duì)其具有較強(qiáng)的表示能力，而該類(lèi)字典對(duì)其他類(lèi)樣本則表示能力很差，因此通過(guò)引入鑒別約束項(xiàng)可以滿(mǎn)足此條件，以達(dá)到很好的鑒別性能；

2）字典學(xué)習(xí)的目的是通過(guò)求解表示系數(shù)對(duì)樣本進(jìn)行表示，因此可以考慮使用字典對(duì)不同類(lèi)樣本進(jìn)行稀疏表示時(shí)，它們的表示系數(shù)之間應(yīng)該具有較強(qiáng)的區(qū)分能力，從而進(jìn)一步達(dá)到鑒別的目的。本文所提出的基于字典學(xué)習(xí)的軟件缺陷檢測(cè)流程如圖1所示。

3基于字典學(xué)習(xí)的軟件缺陷檢測(cè)算法

3.1稀疏表示分類(lèi)器

稀疏表示最早在信號(hào)處理領(lǐng)域中得到應(yīng)用。由于小波變換和傅里葉變換技術(shù)的發(fā)展，科研人員需要處理的數(shù)據(jù)維數(shù)越來(lái)越高，稀疏表示分類(lèi)（Sparse Representation Classification， SRC）技術(shù)開(kāi)始引起了研究人員的極大興趣，并逐步發(fā)展形成了一個(gè)獨(dú)立性的理論方法，并且推廣到了機(jī)器學(xué)習(xí)、圖像處理及模式識(shí)別等領(lǐng)域[21]。假設(shè)存在一個(gè)樣本集X={x1，x2，…，xN}∈Rm×n，其中xi表示X中的某一個(gè)樣本，根據(jù)稀疏表示理論xi可以通過(guò)樣本集X中的樣本以線(xiàn)性組合的形式進(jìn)行表示：

4實(shí)驗(yàn)分析

本文通過(guò)引入幾種重要的分類(lèi)器性能指標(biāo)進(jìn)行實(shí)驗(yàn)對(duì)比，并選擇來(lái)源于美國(guó)國(guó)家宇航局（NASA）的軟件度量程序（MDP）作為實(shí)驗(yàn)數(shù)據(jù)。在實(shí)驗(yàn)過(guò)程中，將選擇支持向量機(jī)（SVM）、決策樹(shù)（C4.5）、主成分分析（PCA）、Logistics回歸（LR）方法、具有代表性的字典學(xué)習(xí)方法DLSDP（Dictionary Learning based Software Defect Prediction）[25]這幾種算法作為對(duì)比算法。本文選擇Matlab R2011a作為實(shí)驗(yàn)工具，實(shí)驗(yàn)所用PC配置為Intel 酷睿i7 6700 CPU，32GB內(nèi)存。

4.1數(shù)據(jù)集介紹

本文選擇來(lái)自NASA的MDP項(xiàng)目進(jìn)行實(shí)驗(yàn)。MDP項(xiàng)目是一個(gè)向全球公開(kāi)的數(shù)據(jù)度量項(xiàng)目，任何用戶(hù)均能夠從NASA的官網(wǎng)下載其中的數(shù)據(jù)。MDP項(xiàng)目包含多個(gè)軟件缺陷數(shù)據(jù)集子集，本文選擇其中的JM1、CM1、KC1、MW1及PC1作為實(shí)驗(yàn)對(duì)比數(shù)據(jù)集。以其中的JM1為例，JM1數(shù)據(jù)集始于某個(gè)地面預(yù)測(cè)系統(tǒng)的軟件項(xiàng)目，使用C++進(jìn)行開(kāi)發(fā)，共有10879個(gè)模塊、21個(gè)軟件度量屬性以及1維的是否為缺陷的標(biāo)簽，其中21個(gè)屬性包含總代碼行數(shù)，McCabe的循環(huán)復(fù)雜度、基本復(fù)雜度、設(shè)計(jì)復(fù)雜度，Halstead程序的級(jí)別、容量、工作量、時(shí)間、長(zhǎng)度等屬性。

4.2分類(lèi)器性能評(píng)價(jià)指標(biāo)

表1中定義了幾種分類(lèi)的行為，其中正確預(yù)測(cè)為正類(lèi)（True Positive， TP）表示在分類(lèi)過(guò)程中實(shí)際為有缺陷的數(shù)據(jù)正確分類(lèi)為有缺陷；錯(cuò)誤預(yù)測(cè)為負(fù)類(lèi)（False Negative， FN）表示實(shí)際為有缺陷的數(shù)據(jù)預(yù)測(cè)為無(wú)缺陷；錯(cuò)誤預(yù)測(cè)為正類(lèi)（False Positive， FP）表示實(shí)際為無(wú)缺陷的數(shù)據(jù)被預(yù)測(cè)為有缺陷，正確預(yù)測(cè)為負(fù)類(lèi)（True Negative， TN）定義為無(wú)缺陷數(shù)據(jù)預(yù)測(cè)正確預(yù)測(cè)為無(wú)缺陷數(shù)據(jù)。

由于最終的檢測(cè)結(jié)果是判斷數(shù)據(jù)是否有缺陷，因此是一個(gè)兩類(lèi)問(wèn)題，僅僅通過(guò)分類(lèi)準(zhǔn)確率來(lái)評(píng)價(jià)一個(gè)算法的有效性是不夠全面的，因此在本文的實(shí)驗(yàn)中引入這里說(shuō)的名稱(chēng)與下面定義介紹不一致，以下面的介紹為準(zhǔn)，請(qǐng)確認(rèn)召回率、錯(cuò)誤接受率、查準(zhǔn)率、準(zhǔn)確率以及Fmeasure值較為全面地衡量分類(lèi)算法的有效性。以下簡(jiǎn)單介紹這幾種值的定義：

1）召回率：re=TP/（TP+FN）。召回率是一種重要的分類(lèi)器性能衡量指標(biāo)，因?yàn)樵趯?shí)際應(yīng)用中需要重點(diǎn)考慮的是有缺陷的數(shù)據(jù)，其反映了被正確判定的缺陷樣本占總的缺陷樣本的比重，即衡量有缺陷樣本檢測(cè)的全面程度。

2）錯(cuò)誤接受率：pf=FP/（FP+TN），其反映了分類(lèi)結(jié)果中無(wú)缺陷數(shù)據(jù)被預(yù)測(cè)為有缺陷數(shù)據(jù)的比例。

3）查準(zhǔn)率：pre=TP/（TP+FP），用來(lái)衡量檢測(cè)到有缺陷樣本的準(zhǔn)確率。

4）準(zhǔn)確率：acc=（TP+TN）/（TP+FN+FP+TN），用來(lái)衡量著所有正確分類(lèi)的樣本占總樣本的比例。

從以上定義看出，一個(gè)好的分類(lèi)器預(yù)測(cè)模型，希望能滿(mǎn)足較高的召回率、缺陷檢測(cè)準(zhǔn)確率以及準(zhǔn)確率，較低的錯(cuò)誤接受率，尤其是查準(zhǔn)率和召回率是兩類(lèi)問(wèn)題中比較重要的指標(biāo)。然而，實(shí)際情況中，查準(zhǔn)率和召回率之間往往難以同時(shí)都達(dá)到較高的值，需要在二者之間尋求權(quán)衡，因此需要折中考慮二者。本文引入Fmeasure值來(lái)考慮衡量準(zhǔn)確率和召回率的調(diào)和平均數(shù)，其被定義為：

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

（18）

在實(shí)驗(yàn)中取β的值為1，即通常所說(shuō)的F1measure值。其中re是召回率，pre是缺陷檢測(cè)準(zhǔn)確率，另外定義pf表示為錯(cuò)誤接受率，acc表示準(zhǔn)確率。從以上定義顯然可以看出，所有的評(píng)估指標(biāo)的取值范圍均在0～1。

4.3實(shí)驗(yàn)結(jié)果及分析

在實(shí)驗(yàn)過(guò)程中，對(duì)于SVM算法采用徑向基核，同時(shí)選擇懲罰因子C=1來(lái)分別進(jìn)行實(shí)驗(yàn)。對(duì)于本文提出的DDL模型，取迭代步長(zhǎng)σ的值為0.1，λ1的值取0.01，λ2的值為0005。為了公平地進(jìn)行實(shí)驗(yàn)，在本文的實(shí)驗(yàn)中每種算法最終選擇隨機(jī)進(jìn)行20組交叉實(shí)驗(yàn)驗(yàn)證，以合理地進(jìn)行算法對(duì)比，最終得到的re、pf、pre實(shí)驗(yàn)結(jié)果如表2所示，acc以及F1measure如表3所示。

4.4實(shí)驗(yàn)分析

從表2、3可以看出，與其他算法相比，本文提出的DDL算法最終能夠?qū)1measure提高0.03～0.26，而準(zhǔn)確率能夠提高0.03～0.20，而召回率、查準(zhǔn)率也有一定程度的改善。其主要原因主要是本文提出的字典學(xué)習(xí)模型具有較強(qiáng)的鑒別分類(lèi)能力，對(duì)比其他幾種機(jī)器學(xué)習(xí)方法，字典學(xué)習(xí)模型本身又有較好的抗干擾能力。而PCA由于其是一種無(wú)監(jiān)督的降維方法，沒(méi)有有效利用豐富的標(biāo)簽信息，相對(duì)于其他集中算法效果最差；LR是一種模型較為簡(jiǎn)單的回歸算法，模型本身不具有鑒別能力，同時(shí)從其自身的應(yīng)該來(lái)看，算法泛化能力較差，因此實(shí)驗(yàn)效果相對(duì)較差；C4.5其容易出現(xiàn)過(guò)度擬合的問(wèn)題，而且其對(duì)連續(xù)性的字段難以作出準(zhǔn)確的預(yù)測(cè)；對(duì)于SVM，其雖然擁有較強(qiáng)的泛化能力，但是需要選擇合適的核函數(shù)，而SVM本身也具有多種形式的模型，因此如何選擇合適的參數(shù)也是一個(gè)問(wèn)題，同時(shí)SVM也沒(méi)有很強(qiáng)的鑒別分類(lèi)能力。

值得一提的是本文選擇了DLSDP算法進(jìn)行對(duì)比，可以發(fā)現(xiàn)，DLSDP也是一種字典學(xué)習(xí)方法，由于其在算法中主要使用代價(jià)敏感方法來(lái)解決類(lèi)不平衡問(wèn)題，因此所得到的Fmeasure值和本文的算法相比很接近；另一方面，由于其沒(méi)有考慮不同類(lèi)字典的鑒別性質(zhì)，因此在檢測(cè)精度上略差于本文算法。

5結(jié)語(yǔ)

為解決傳統(tǒng)的字典學(xué)習(xí)方法不能有效構(gòu)造具有鑒別能力字典的問(wèn)題，提出了一種新的基于鑒別字典學(xué)習(xí)的分類(lèi)算法，并用于軟件缺陷檢測(cè)，即基于鑒別字典學(xué)習(xí)的軟件缺陷檢測(cè)算法。該算法首先通過(guò)添加鑒別表示項(xiàng)以突出不同類(lèi)字典對(duì)不同類(lèi)樣本的表示能力，其次添加Fisher準(zhǔn)則系數(shù)鑒別項(xiàng)，使得不同類(lèi)的表示系數(shù)具有較好的鑒別能力；然后通過(guò)迭代算法求解相應(yīng)模型的目標(biāo)函數(shù)，最后選擇在MDP數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，獲得的實(shí)驗(yàn)結(jié)果表明能夠在改善檢測(cè)性能的基礎(chǔ)上提高檢測(cè)精度。現(xiàn)實(shí)當(dāng)中二分類(lèi)經(jīng)常面臨正負(fù)樣本不平衡的問(wèn)題，在本文提出的算法中，可以通過(guò)引入代價(jià)敏感約束進(jìn)一步提高算法的分類(lèi)性能，考慮不同類(lèi)樣本數(shù)目對(duì)分類(lèi)造成的代價(jià)影響，本文的后續(xù)工作可以圍繞這項(xiàng)內(nèi)容展開(kāi)工作。

參考文獻(xiàn)：

[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.