李偉湋 郭鴻昌

(1.南京航空航天大學(xué)航天學(xué)院，南京,210016；2.東部戰(zhàn)區(qū)空軍裝備部，南京,210081)

基于鄰域三支決策粗糙集模型的軟件缺陷預(yù)測方法*

李偉湋1郭鴻昌2

(1.南京航空航天大學(xué)航天學(xué)院，南京,210016；2.東部戰(zhàn)區(qū)空軍裝備部，南京,210081)

基于已有軟件缺陷數(shù)據(jù)，建立分類模型對待測軟件模塊進(jìn)行預(yù)測，能夠提高測試效率和降低測試成本?，F(xiàn)有基于機器學(xué)習(xí)方法對軟件缺陷預(yù)測的研究大部分基于二支決策方式，存在誤分率較高等問題。本文針對軟件缺陷數(shù)據(jù)具有代價敏感特性且軟件度量取值為連續(xù)值等特性，提出了一種基于鄰域三支決策粗糙集模型的軟件缺陷預(yù)測方法，該方法對易分錯的待測軟件模塊作出延遲決策，和二支決策方法相比，降低了誤分類率。在NASA軟件數(shù)據(jù)集上的實驗表明所提方法能夠提高分類正確率并減小誤分類代價。

軟件缺陷分類；鄰域三支決策粗糙集模型；三支決策

引 言

軟件缺陷預(yù)測在減少軟件開發(fā)成本和提高軟件質(zhì)量方面發(fā)揮著重要作用[1-3]。在軟件測試過程中，通過軟件缺陷預(yù)測可以幫助軟件項目管理者合理安排有限的測試時間和人力資源，從而在有限的測試資源情況下提高軟件測試的有效性及軟件質(zhì)量。目前對軟件缺陷預(yù)測的研究主要可以分為兩類：(1)通過對軟件模塊缺陷數(shù)目的預(yù)測，將某些模塊定位為高缺陷率模塊或低缺陷率模塊，這種方法通常將軟件缺陷預(yù)測看作回歸問題[4]。(2)將軟件缺陷預(yù)測看作分類問題[5]，將軟件缺陷分類為有缺陷趨勢模塊和無缺陷趨勢的模塊，通常使用決策樹、貝葉斯網(wǎng)絡(luò)、人工神經(jīng)網(wǎng)絡(luò)和支持向量機等機器學(xué)習(xí)方法[6]。也有部分學(xué)者考慮到軟件缺陷預(yù)測具有代價敏感特性，將代價敏感學(xué)習(xí)方法應(yīng)用到軟件缺陷分類。如Zheng[7]和Arar等[8]將基于代價敏感神經(jīng)網(wǎng)絡(luò)模型用于軟件缺陷分類。Liu等[9]將代價敏感特征選擇和代價敏感BP神經(jīng)網(wǎng)絡(luò)應(yīng)用與軟件缺陷分類。不論在缺陷分類問題中是否考慮代價敏感，現(xiàn)有的研究都是假設(shè)缺陷分類是一個二分類問題，并應(yīng)用二支決策方式，即對軟件模塊做出接受其為有缺陷趨勢模塊和拒絕其為有缺陷趨勢模塊的決策。二支決策方法屬于立即決策方式，能夠簡單快速地給出分類結(jié)果，但是存在著誤分類率較高的問題。簡單二支決策方法會基于多數(shù)原則依據(jù)給定軟件模塊屬于缺陷趨勢模塊的條件概率對其進(jìn)行判定，這就導(dǎo)致對處于中間模糊地帶不易劃分的軟件模塊容易做出錯誤的決策。立即決策方式誤分率較高，由此帶來的誤分類代價也會增加[10]。

針對此類問題提出了一種代價敏感相關(guān)的鄰域三支決策粗糙集模型，并在此基礎(chǔ)上設(shè)計了一種三支決策鄰域分類方法。該分類方法考慮到軟件缺陷預(yù)測的代價敏感問題，對軟件模塊進(jìn)行分類采用三支決策方法，依據(jù)不同錯誤分類帶來的損失代價不同，設(shè)置相應(yīng)的代價函數(shù)，計算三支決策所需閾值對，將誤分率高的軟件模塊劃分到邊界域中，交由專家評判或等待進(jìn)一步處理，從而能夠降低缺陷分類的誤分類率，減少代價損失。在NASA軟件數(shù)據(jù)集上進(jìn)行了相應(yīng)的對比實驗，實驗結(jié)果表明該方法能有效地提高分類正確率，降低誤分類代價。

1 鄰域三支決策粗糙集模型

考慮軟件缺陷數(shù)據(jù)具有代價敏感特性，且通過對軟件缺陷數(shù)據(jù)進(jìn)行度量提取出的特征或?qū)傩匀≈禐檫B續(xù)值的特點，結(jié)合三支決策粗糙集模型[11]和鄰域粗糙集模型的優(yōu)點，提出了一種鄰域三支決策粗糙集模型，使之能夠處理具有復(fù)雜特性的軟件缺陷數(shù)據(jù)。

1.1 三支決策粗糙集模型

定義1 決策表可表示為一個四元組

(1)

式中：有限集合U為論域;At為屬性集合;C為條件屬性集;D為決策屬性集;Vat表示屬性at的值域;Iat:U→Vat為從U到Vat的映射函數(shù)，通常Iat假設(shè)為單值的，任意對象x∈U在屬性at∈At上的取值可以表示為Iat(x)。在粗糙集領(lǐng)域，通常用等價類的形式來刻畫或描述對象x。對象x的等價類定義為

(2)

(3)

(4)

表1 不同決策行為在不同狀態(tài)下的風(fēng)險代價

Tab. 1 Different decision costs based on different actions

決策行為aPaBaNXλPPλBPλNPXcλPNλBNλNN

根據(jù)貝葉斯最小風(fēng)險決策原則，可以得到的決策規(guī)則為

(P)若RP≤RB且RP≤RN，則判定x∈POS(X)；

(B)若RB≤RP且RB≤RN，則判定x∈BND(X)；

(N)若RN≤RP且RN≤RB，則判定x∈NEG(X)。

其中α，β和γ值分別為

(5)

考慮條件

(6)

可得0≤β<γ<α≤1，則可以進(jìn)一步簡化上述三支決策規(guī)則為

1.2 鄰域粗糙集模型

經(jīng)典粗糙集方法只能處理離散值，而為了能夠處理數(shù)值型數(shù)據(jù)，很多學(xué)者將其擴展到鄰域系統(tǒng)中。一種最具代表性的模型是文獻(xiàn)[12]提出的基于距離的鄰域粗糙集模型。

定義2 給定決策表S，對象xi∈U且A?At，在子空間A中，xi的鄰域粒子δA(xi)定義為

(7)

式中Δ為度量函數(shù)，兩個對象之間的Minkowski距離定義為

(8)

(9)

根據(jù)粗糙集的上下近似定義，鄰域粗糙集的正域、邊界域和負(fù)域可表示為

(10)

1.3 領(lǐng)域三支決策粗糙集模型

(11)

對于任意子集X?U，在子空間B?At，X的正域、邊界域和負(fù)域定義為

(12)

(13)

決策粗糙集可以看作是鄰域三支決策粗糙集的一種特例,即δ=0。當(dāng)δ=0，δ(x)表示等價關(guān)系。另外，若鄰域決策粗糙集中的α=1且β=0時，則鄰域三支決策粗糙集模型轉(zhuǎn)化為經(jīng)典鄰域粗糙集模型。

定理2表示隨著α值的增大，正域單調(diào)性減小，定理3表示隨著β值的增大，正域單調(diào)性減小。這兩個定理表明通過修改(α,β)的值能調(diào)整X的正域和邊界域的大小。

2 基于三支決策鄰域分類器的軟件缺陷分類方法

Hu等基于鄰域粗糙集模型提出了一種二支決策鄰域分類器，該分類器可以直接對連續(xù)型數(shù)據(jù)進(jìn)行處理。該分類器在對對象x進(jìn)行分類時，通常分配δ(x)中樣本占多數(shù)的決策類標(biāo)D+。二支決策分類器的優(yōu)勢是能夠快速地對測試對象做出立即決策。然而，這種立即決策方式常常伴隨更多的預(yù)測錯誤和更大的決策代價。假定存在一個模棱兩可的對象，它被分到類別D+的概率為51%，分到類別D-的概率為49%。按照多數(shù)準(zhǔn)則將其劃分到D+中時，則意味著其有49%概率被分錯。針對二支決策分類的劣勢，三支決策方法則將模糊不清的對象劃分到邊界域中，作出延遲決策，等待專家的進(jìn)一步處理。基于三支決策理論和鄰域二支決策分類器，在鄰域三支決策粗糙集模型下設(shè)計了一種三支決策鄰域分類器用于軟件缺陷分類，該分類器的目的是減少分類錯誤率。該分類算法具體思想如下：對于待分類的軟件模塊x，計算其屬于有缺陷趨勢類別D+的概率p(D+|δB(x))，通過判斷該概率值與基于代價函數(shù)矩陣計算出的閾值對(α,β)之間的大小關(guān)系作出相應(yīng)的三支決策，具體如下：

(P)若p(D+|δB(x))>α，則x屬于D+；

(B)若β≤p(D+|δB(x))≤α，則x需進(jìn)一步檢查；

(N)若p(D+|δB(x))<β，則x屬于D-。

x若為接受決策則將其劃分到D+中，即為有缺陷趨勢模塊，x若為拒絕決策則將其劃分到D-中，即為無缺陷趨勢模塊，x若為延遲決策則需要等待做進(jìn)一步檢查。詳細(xì)算法如下所示。

算法1 Three-way decisions based neighborhood classifier (TDNEC)輸入: Training set: 〈U,C,D〉;

Testobject:x;

Parameterω;

本文應(yīng)用ANSYS Workbench全新的斷裂力學(xué)有限元計算模塊，建立在損傷結(jié)構(gòu)一端施加固定約束，另一端施加大小為100 MPa方向背離損傷結(jié)構(gòu)的均布拉伸載荷的情況下，含有中心表面裂紋損傷結(jié)構(gòu)的再制造膠粘修復(fù)有限元模型，并利用位移外推法求解裂紋尖端的應(yīng)力強度因子K。

輸出: Class ofx.

BEGIN

(2)FOReachsinU

(3)ComputethedistanceΔ(x,s)betweenxandswiththeusednorm;//計算距離

(4)MIN=min(Δ(x,s));

(5)MAX=max(Δ(x,s));

(7)δ(x)=MIN+ω·(MAX-MIN); //計算其鄰域

(8)p=p(D+|δ(x));

(9)IFp>α

(10)AssignD+totestobjectandxisadefect-pronemodule;//將其判定為有缺陷模塊

(11)ELSEIFβ≤p≤α

(12)xisintheboundaryregionofD+andxneedstofurther-examined;//等待進(jìn)一步處理

(13)ELSE

(14)xisanon-defect-pronemodule; //將其判定為無缺陷模塊

(15)ENDIF

ENDBEGIN

在該算法中，鄰域粒子的大小由閾值δ決定，采用文獻(xiàn)[12]中建議的方式，由待測對象x的局部和全局信息動態(tài)決定，則

(14)

式中：si(i=1,...,n)為訓(xùn)練對象集；min(Δ(si,x))和max(Δ(si,x)分別表示si和測試對象x最小和最大距離值。

3 實驗驗證

本節(jié)通過實驗來考察所提三支決策鄰域分類器在軟件缺陷分類任務(wù)上的性能，實驗對比三支決策鄰域分類器(TDNEC)、二支決策鄰域分類器(NEC)[12]，C4.5，k-NN和SVM在分類準(zhǔn)確率、F值和誤分類代價上的性能。

3.1 實驗數(shù)據(jù)集和參數(shù)設(shè)置

表2的11個數(shù)據(jù)集均是NASA的實際項目，來自于公共的PROMISE庫[15]，包括了衛(wèi)星飛行軟件、衛(wèi)星模擬器軟件和地面站數(shù)據(jù)管理軟件等。數(shù)據(jù)集覆蓋了3種編程語言。在這些數(shù)據(jù)集中，缺陷模塊的百分率分布為3.0%～32.29%。，每個數(shù)據(jù)采樣描述一個模塊的屬性是否是缺陷。模塊的屬性包括McCabe度量值、Halstead度量值、操作符數(shù)和代碼行數(shù)等。

表2 NASA數(shù)據(jù)集

實驗的相關(guān)參數(shù)設(shè)置如表3所示。由于采用10倍交叉驗證，在試驗結(jié)果中僅給出平均結(jié)果。對于每個數(shù)據(jù)集，隨機產(chǎn)生10組不同的代價函數(shù)，即對每個分類任務(wù)運行10次10倍交叉驗證。ω值參考文獻(xiàn)[12]的設(shè)置，ω值介于0和0.1。

表3 實驗各參數(shù)設(shè)置

3.2 評價標(biāo)準(zhǔn)

令NPP表示分類器將實際為有缺陷的模塊判定正確的個數(shù)，NNN表示分類器將實際為無缺陷的模塊判定正確的個數(shù)，NPN表示將無缺陷的模塊判定為有缺陷模塊的個數(shù)，NNP表示將有缺陷的模塊判定為無缺陷模塊的個數(shù)，則分類正確率定義為

(15)

覆蓋率定義為

(16)

TDNEC基于三支決策，一些對象會被分類到邊界域中，因此，TDNEC覆蓋率的值常常小于1。在大多數(shù)情況下，分類正確率和覆蓋率是一種tradeoff的關(guān)系，常用F值來表示分類器的折衷性能。基于分類正確率和覆蓋率的F值定義為

(17)

基于表1給定的代價函數(shù)，誤分類代價定義為

(18)

3.3 實驗結(jié)果及分析

表4～6為三支決策鄰域分類器，NEC，C4.5，k-NN和SVM五種分類器在分類正確率、F值和誤分類代價上的性能對比結(jié)果。對于分類正確率，TDNEC在5個數(shù)據(jù)集上表現(xiàn)優(yōu)于其他算法，SVM表現(xiàn)其次，4個最優(yōu)，C4.5有2個最優(yōu)。TDNEC由于采用三支決策方法，對于模棱兩可的對象都將被延遲做進(jìn)一步的檢驗，這在理論上保證了三支決策方法具有較高的分類精度。對于F值，SVM最好，有7個最優(yōu)，C4.5其次，有2個最優(yōu)，NEC有1個最優(yōu)。對于TDNEC的表現(xiàn)，這是可預(yù)期的，因為F值是由分類正確率和覆蓋度共同決定的，雖然TDNEC能夠取得較好的分類正確率，TDNEC的覆蓋度小于1，而其他算法的覆蓋度都等于1，由此決定了TNDEC在一定程度上無法取得較高的F值。對于誤分類代價，TDNEC有5個數(shù)據(jù)集上最優(yōu)，SVM表現(xiàn)其次，4個最優(yōu)，C4.5有2個最優(yōu)。從理論上分析，TDNEC基于最小化貝葉斯決策代價理論，這保證了TDNEC能夠得到較小的誤分類代價。

表4 各分類器在航天軟件缺陷數(shù)據(jù)上分類正確率的對比結(jié)果(加粗表示最好的值)

表5 各分類器在航天軟件缺陷數(shù)據(jù)上F值的對比結(jié)果(加粗表示最好的值)

表6 各分類器在航天軟件缺陷數(shù)據(jù)上誤分類代價的對比結(jié)果(加粗表示最好的值)

4 結(jié)束語

本文針對軟件缺陷數(shù)據(jù)具有代價敏感特性且屬性值為連續(xù)型數(shù)據(jù)等特點，提出了一種基于鄰域三支決策粗糙集模型的軟件缺陷預(yù)測方法。在鄰域三支決策粗糙集模型中，既可以通過代價函數(shù)矩陣求出三支決策所需的閾值，又能通過鄰域系統(tǒng)來表示和計算連續(xù)型數(shù)據(jù)?；谠撃Ｐ吞岢龅娜Q策分類器對于具有較高確信度和較低確信度的待測軟件模塊作出明確的接受和拒絕決策，而對于模糊不清的待測軟件模塊則做出延遲決策，交由專家進(jìn)一步處理。在NASA數(shù)據(jù)集上的實驗結(jié)果表明，三支決策鄰域分類器在大部分?jǐn)?shù)據(jù)集上能夠取得較高的分類正確率和較低的誤分類代價。

[1] Huai J P. Views about future networked software technologies[J].Communications of the CCF, 2008, 4(1):19-26.

[2] President′s information technology advisory committee. Computational Science: Ensuring America's competitiveness[R]．Washington: PITAC,2005.

[3] Ramler R, Wolfmaier K. Economic perspectives in test automation: Balancing automated and manual testing with opportunity cost[C]//Proceedings of the 2006 International Workshop on Automation of Software Test． New York, USA：ACM，2006: 85-91.

[4] 王青, 伍書劍, 李明樹. 軟件缺陷預(yù)測技術(shù)[J]. 軟件學(xué)報, 2008, 19(7): 1565-1580.

Wang Qing，Wu Shujian，Li Mingshu. Software defect prediction[J]. Journal of Software，2008，19(7)：1565-1580.

[5] Lessmann S, Baesens B, Mues C, et al. Benchmarking classification models for software defect prediction: A proposed framework and novel findings[J]. Software Engineering, IEEE Transactions on, 2008, 34(4)：485-496.

[6] 黎銘，霍軒.半監(jiān)督軟件缺陷挖掘研究綜述[J].數(shù)據(jù)采集與處理，2016,31(1)：56-64.

Li Ming，Huo Xuan. Software defect mining based on semi-supervised learning [J]. Journal of Data Acquisition and Processing，2016，31(1)：56-64.

[7] Zheng J. Cost-sensitive boosting neural networks for software defect prediction [J]. Expert Systems with Applications, 2010, 37(6): 4537-4543.

[8] Arar O F，Ayan K. Software defect prediction using cost-sensitive neural network[J]. Applied Soft Computing，2015，33：263-277.

[9] Liu M X, Miao L S, Zhang D Q. Two-stage cost-sensitive learning for software defect prediction[J]. IEEE Transactions on Reliability, 2014, 63(2): 676-686.

[10] Li W W，Huang Z Q，Li Q. Three-way decisions based software defect prediction[J]. Knowledge-Based Systems，2016，91：263-274.

[11] Yao Y Y. The superiority of three-way decisions in probabilistic rough set models[J]. Information Sciences, 2011, 181(6): 1080-1096.

[12] Hu Q H, Yu D R, Xie Z X. Neighborhood classifiers[J]. Expert Systems with Applications： An International Journal, 2008, 34: 866-876.

[13] 楊霽琳，張賢勇，唐孝. 基于三支決策的模糊信息系統(tǒng)OWA算子參數(shù)選擇[J].數(shù)據(jù)采集與處理，2016，31(6)：1156-1163.

Yang Jilin，Zhang Xianyong，Tang Xiao. Three-way decisions based parameter selection of OWA operations in fuzzy information system[J]. Journal of Data Acquisition and Processing，2016，31(6)：1156-1163.

[14] Jia X Y，Liao W H，Tang Z M，et al. Minimum cost attribute reduction in decision-theoretic rough set models[J]. Information Sciences，2013，219：151-167.

[15] Sayyad S J, Menzies T J. The PROMISE repository of software engineering databases[EB/OL].University of Ottawa, Canada, http://promise.site.uottawa.ca/SERepository, 2006-01-01/2017-01-10.

Software Defect Prediction Method Based on Neighborhood Three-way Decision-theoretic Rough Set Model

Li Weiwei1, Guo Hongchang2

(1.College of Astronautics, Nanjing University of Aeronautics and Astronautics, Nanjing, 210016, China; 2. Air Force Equipment Department of Eastern Theater Command，Nanjing, 210081, China)

Based on existing software defect data, it is possible to improve the efficiency of software testing and reduce the test cost by establishing the classification model to predict the software modules. Most machine learning based defect prediction researches are based on two-way decision method. Since software defect prediction can be seen as a kind of cost-sensitive learning problem, and the software data has continuous values, this paper proposes a classification method based on neighborhood three-way decision-theoretic rough set model. For ambiguous testing modules, compared with two-way decision methods, this method makes a deferment decision to reduce the misclassification rate. Experimental results on NASA software datasets show that the proposed method can get a higher classification accuracy and a lower misclassification cost.

software defect classification; neighborhood three-way decision-theoretic rough set model; three-way decisions

國家高技術(shù)研究發(fā)展計劃(“八六三”計劃)(2015AA105303)資助項目。

2016-10-21；

2017-01-01

TP18

A

李偉湋(1981-)，女，助理研究員，研究方向：軟件挖掘、機器學(xué)習(xí)，E-mail:liweiwei@nuaa.edu.cn。

郭鴻昌(1979-)，男，工程師, 研究方向：軟件工程、機器學(xué)習(xí)。