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

李偉湋 郭鴻昌

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

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

李偉湋1郭鴻昌2

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

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

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

引 言

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

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

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

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

1.1 三支決策粗糙集模型

定義1 決策表可表示為一個(gè)四元組

(1)

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

(2)

(3)

(4)

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

Tab. 1 Different decision costs based on different actions

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

根據(jù)貝葉斯最小風(fēng)險(xiǎn)決策原則，可以得到的決策規(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)一步簡(jiǎn)化上述三支決策規(guī)則為

1.2 鄰域粗糙集模型

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

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

(7)

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

(8)

(9)

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

(10)

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

(11)

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

(12)

(13)

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

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

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

Hu等基于鄰域粗糙集模型提出了一種二支決策鄰域分類器，該分類器可以直接對(duì)連續(xù)型數(shù)據(jù)進(jìn)行處理。該分類器在對(duì)對(duì)象x進(jìn)行分類時(shí)，通常分配δ(x)中樣本占多數(shù)的決策類標(biāo)D+。二支決策分類器的優(yōu)勢(shì)是能夠快速地對(duì)測(cè)試對(duì)象做出立即決策。然而，這種立即決策方式常常伴隨更多的預(yù)測(cè)錯(cuò)誤和更大的決策代價(jià)。假定存在一個(gè)模棱兩可的對(duì)象，它被分到類別D+的概率為51%，分到類別D-的概率為49%。按照多數(shù)準(zhǔn)則將其劃分到D+中時(shí)，則意味著其有49%概率被分錯(cuò)。針對(duì)二支決策分類的劣勢(shì)，三支決策方法則將模糊不清的對(duì)象劃分到邊界域中，作出延遲決策，等待專家的進(jìn)一步處理?；谌Q策理論和鄰域二支決策分類器，在鄰域三支決策粗糙集模型下設(shè)計(jì)了一種三支決策鄰域分類器用于軟件缺陷分類，該分類器的目的是減少分類錯(cuò)誤率。該分類算法具體思想如下：對(duì)于待分類的軟件模塊x，計(jì)算其屬于有缺陷趨勢(shì)類別D+的概率p(D+|δB(x))，通過(guò)判斷該概率值與基于代價(jià)函數(shù)矩陣計(jì)算出的閾值對(duì)(α,β)之間的大小關(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+中，即為有缺陷趨勢(shì)模塊，x若為拒絕決策則將其劃分到D-中，即為無(wú)缺陷趨勢(shì)模塊，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é)有限元計(jì)算模塊，建立在損傷結(jié)構(gòu)一端施加固定約束，另一端施加大小為100 MPa方向背離損傷結(jié)構(gòu)的均布拉伸載荷的情況下，含有中心表面裂紋損傷結(jié)構(gòu)的再制造膠粘修復(fù)有限元模型，并利用位移外推法求解裂紋尖端的應(yīng)力強(qiáng)度因子K。

輸出: Class ofx.

BEGIN

(2)FOReachsinU

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

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

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

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

(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; //將其判定為無(wú)缺陷模塊

(15)ENDIF

ENDBEGIN

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

(14)

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

3 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

表3 實(shí)驗(yàn)各參數(shù)設(shè)置

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

(15)

覆蓋率定義為

(16)

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

(17)

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

(18)

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[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] 王青, 伍書(shū)劍, 李明樹(shù). 軟件缺陷預(yù)測(cè)技術(shù)[J]. 軟件學(xué)報(bào), 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

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

2016-10-21；

2017-01-01

TP18

A

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

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