一種面向軟件缺陷預(yù)測(cè)的特征聚類選擇方法

李麗媛 江國(guó)華

摘要：軟件缺陷預(yù)測(cè)技術(shù)通過分析軟件靜態(tài)信息，對(duì)軟件模塊的缺陷傾向性做出判斷，合理分配測(cè)試資源。但有時(shí)搜集的大量度量元信息是無關(guān)或冗余的，這些高維的特征增加了缺陷預(yù)測(cè)的復(fù)雜性。文章提出了一種新的度量元選擇方法，首先通過樣本聚類將相似度高的樣本聚在同一簇中，然后在每個(gè)簇中按照最低冗余度進(jìn)行特征子集的挑選，主要選擇相互間冗余度低，且預(yù)測(cè)能力強(qiáng)的度量元。最后通過NASA數(shù)據(jù)集的實(shí)例證明本文方法能有效降低特征子集的冗余率，并能有效提高預(yù)測(cè)的準(zhǔn)確度。

關(guān)鍵詞：軟件缺陷預(yù)測(cè);特征選擇;特征聚類

中圖法分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A

1 引言

隨著現(xiàn)代信息技術(shù)的發(fā)展，軟件規(guī)模不斷增長(zhǎng)，程序復(fù)雜度不斷提高，致使軟件中隱藏的缺陷也越來越多，由此引發(fā)的軟件故障給國(guó)家、給企業(yè)帶來了不可估量的損失。軟件缺陷預(yù)測(cè)技術(shù)從20世紀(jì)70年代發(fā)展至今，一直備受關(guān)注。軟件缺陷預(yù)測(cè)技術(shù)可以分為靜態(tài)缺陷預(yù)測(cè)技術(shù)和動(dòng)態(tài)缺陷預(yù)測(cè)技術(shù)[1]。靜態(tài)缺陷預(yù)測(cè)技術(shù)主要分析軟件靜態(tài)信息，利用與缺陷相關(guān)的度量元，準(zhǔn)確預(yù)測(cè)出軟件模塊的缺陷數(shù)量或缺陷分布情況。這樣在軟件測(cè)試時(shí)可以合理分配測(cè)試資源，給軟件質(zhì)量保證提供了重要的途徑。

在分析軟件模塊時(shí)，有大量的軟件度量元（即特征）可以提取，而特征間是存在冗余關(guān)系的，即一個(gè)特征可以由其他一個(gè)或幾個(gè)特征信息推導(dǎo)出來。這些冗余特征將影響構(gòu)建預(yù)測(cè)模型的效率，甚至還會(huì)降低預(yù)測(cè)模型的準(zhǔn)確度[2]。因此使用特征選擇或提取的方法移除這類特征有重要研究意義。

特征選擇就是從一組數(shù)量為Ⅳ的特征中選擇出數(shù)量為M的最優(yōu)特征，其中M

對(duì)特征選擇的研究比較著名的有：Gao等人[4]考慮了七種特征排序方法和三種特征子集選擇方法，基于一個(gè)大型傳統(tǒng)通信系統(tǒng)的研究發(fā)現(xiàn)移除85%的特征不會(huì)降低缺陷預(yù)測(cè)效果，甚至有時(shí)還能提高缺陷預(yù)測(cè)的性能。Guo等人[5]使用了隨機(jī)森林方法對(duì)特征進(jìn)行排序，他們發(fā)現(xiàn)前5個(gè)特征的預(yù)測(cè)效果和使用21個(gè)特征進(jìn)行預(yù)測(cè)的效果相當(dāng)。Menzies等人[6]使用信息增益對(duì)特征進(jìn)行排序，他們的結(jié)論和Guo相似：使用前3個(gè)特征的預(yù)測(cè)效果和使用全部特征效果相當(dāng)。Wang等人[7]認(rèn)為單個(gè)特征選擇技術(shù)不穩(wěn)定，因此集成了多個(gè)特征選擇方法以獲得穩(wěn)定的特征集合。在17種不同的集成方案中發(fā)現(xiàn)集成2-4種方法時(shí)，預(yù)測(cè)效果最佳;隨著集成數(shù)量的增加，預(yù)測(cè)效果反而開始下降。Mitra等人[8]使用最大信息壓縮指標(biāo)來度量不同變量間的相似度，對(duì)特征集進(jìn)行聚類，然后在聚類結(jié)果中選出具有代表性的特征組成特征子集。該方法需要指定期望特征個(gè)數(shù)K，并且對(duì)不同的K值比較敏感。此外，劉樹龍等人[9]提出一種基于聚類分析的特征子集選擇框架FECAR，F(xiàn)ECAR首先根據(jù)特征間的相關(guān)性將特征進(jìn)行聚類分析，然后從每個(gè)聚類簇中選擇和類標(biāo)最相關(guān)的特征組成最終的特征子集。經(jīng)實(shí)證對(duì)比，能較好的降低冗余度，并提高預(yù)測(cè)效率。目前缺陷預(yù)測(cè)領(lǐng)域的特征選擇大部分考慮無關(guān)特征，較少考慮冗余特征，上述文獻(xiàn)結(jié)合聚類和特征排序的方法能夠移除部分冗余特征，但建立在簇內(nèi)排序基礎(chǔ)上的特征選擇仍有冗余特征存在，本文方法改進(jìn)了這一點(diǎn)，在簇內(nèi)進(jìn)行基于分類器性能的特征子集選擇方法，可進(jìn)一步去除更多的冗余特征，減少了運(yùn)行時(shí)的時(shí)間、空間開銷，并經(jīng)實(shí)例驗(yàn)證，還進(jìn)一步提高了分類預(yù)測(cè)的精度。

2 傳統(tǒng)特征聚類方法

聚類方法是一種無監(jiān)督學(xué)習(xí)方法，主要依據(jù)樣本相互之間的依賴程度進(jìn)行劃分，幫助分析和提取隱藏在其中的潛在規(guī)律。聚類的劃分標(biāo)準(zhǔn)就是樣本間的相關(guān)性，其度量標(biāo)準(zhǔn)大概可分為四種：距離度量、信息度量、依賴性度量和一致性度量。

距離度量利用距離來定義樣本之間的相似度，距離越近，樣本間相似度越高。常用的距離度量有歐式距離、S階Minkowski度量、Chebychev距離、平方距離等。其中歐氏距離可以看作是2階Minkowski距離。

信息度量引入了信息論中不確定性度量的熵函數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)，從特征分類的角度來看，不確定性越小，特征分類越準(zhǔn)確。通常采用信息增益（IG）衡量一個(gè)特征區(qū)分樣本類別的能力。信息增益定義為先驗(yàn)概率與后驗(yàn)概率之間的不確定性差異，對(duì)于兩個(gè)隨機(jī)變量X、Y，它們之間的信息增益IG（XIY）使用信息熵來計(jì)算：

信息增益不僅可以用來計(jì)算兩個(gè)隨機(jī)變量間的相關(guān)性，也可以用來衡量變量與類別間的相互關(guān)系。FCBF （fast correlation-based filter）是基于相互關(guān)系度量的一種算法，采用SU（非線性的對(duì)稱不確定性）來度量特征間相關(guān)性：

依賴性度量既可以利用相關(guān)系數(shù)，找出特征和類別之間的相互關(guān)系;又可以利用特征之間的依賴關(guān)系，來表示特征的冗余性。Hall給出一種既考慮了特征的類區(qū)分能力，同時(shí)又考慮特征間冗余性的相關(guān)性度量標(biāo)準(zhǔn)。

一致性度量和訓(xùn)練數(shù)據(jù)集關(guān)系密切，主要是找到與全集有同樣區(qū)分類別能力的最小子集，但由于其對(duì)噪聲數(shù)據(jù)敏感，且只適合離散特征，應(yīng)用較少。典型算法有Focus，LVF等。

基于聚類的特征選擇方法一般與特征排序結(jié)合，樣本聚類過程結(jié)束后，在每一個(gè)聚類中按照單個(gè)特征與類別間的相關(guān)性進(jìn)行排序，選擇指定數(shù)量的特征，組成最終的最優(yōu)子集，構(gòu)建軟件缺陷預(yù)測(cè)模型，但通常這類方法效果不佳。因?yàn)閺木垲愔羞x擇特征時(shí)，選擇了和類標(biāo)最相關(guān)的特征組成最終的特征子集。然而，每個(gè)聚類中不只保留一個(gè)特征，而且保留的特征和類標(biāo)的相關(guān)性都較大，因此最終選擇的特征子集中仍有一定的冗余信息。

3 聚類特征子集選擇方法

本文方法不同于傳統(tǒng)的特征聚類方法，因?yàn)樘卣骶垲愂菍⑷哂嘈源蟮奶卣骶蹫橐活?，那么類間特征，尤其是經(jīng)過與類標(biāo)相關(guān)性排序選擇出的幾個(gè)特征，可能有較大概率存在冗余。由此啟發(fā)，本文采用在聚類中進(jìn)行包裝式的特征子集選擇，這樣選擇出組合效果最大的一組特征子集，而不是單個(gè)效果最好的特征之間的累加。以分類器效果作為評(píng)價(jià)指標(biāo)，選擇出最適應(yīng)分類器的特征子集。

3.1 算法框架

聚類特征子集選擇方法的思想是：通過先對(duì)原始樣本數(shù)據(jù)集進(jìn)行聚類分析，將相似度高的樣本聚為一類，隨后，在每一個(gè)聚類中，進(jìn)行特征子集選擇，這樣降低了子集搜索的空間，提高了搜索效率，挑選出的特征間也有更低的冗余度。算法基本框架如圖1所示。

3.2 特征聚類方法

聚類分析是根據(jù)數(shù)據(jù)對(duì)象間的相似性將其分到不同聚類中的過程?？傊痪垲愔袠颖镜南嗨菩栽礁?，不同聚類間樣本相似性越小，則聚類效果越好。本文采用K-means聚類算法，使用歐式距離作為度量方式。歐式距離計(jì)算公式如公式（5）所示：

其中X，Y分別是兩個(gè)Ⅳ維特征向量，距離D（X，y）越小，目標(biāo)間相似度越大。采用歐式距離，首先計(jì)算簡(jiǎn)單明了，收斂速度快以及局部搜索能力強(qiáng)等特點(diǎn)，整個(gè)聚類過程比較簡(jiǎn)單，時(shí)間復(fù)雜度近似線性。具體如算法1所示。

在此算法中，我們選擇k=2作為聚類簇的個(gè)數(shù)。因?yàn)樵谲浖毕蓊A(yù)測(cè)領(lǐng)域，一般將軟件模塊分為有缺陷傾向性和無缺陷傾向性，相應(yīng)的聚類簇的類標(biāo)應(yīng)為有缺陷標(biāo)記和無缺陷標(biāo)記，所以我們將樣本數(shù)據(jù)聚為兩個(gè)簇。

3.3 特征子集選擇方法

包裝式子集選擇方法首先要用搜索算法挑選出子集，再使用評(píng)價(jià)算法判斷評(píng)價(jià)當(dāng)前子集是否滿足要求。搜索時(shí)可以將單個(gè)特征作為初始候選子集，選出最優(yōu)的候選子集后不斷加入新的特征進(jìn)行評(píng)價(jià)，直至評(píng)分不再增加，得到最優(yōu)子集。

特征子集選擇主要目的是挑選與類別關(guān)系密切且相互之間相關(guān)度較低的特征，因此不僅要度量任兩個(gè)特征間的相關(guān)性，還要度量特征與類別的相關(guān)性?；陉P(guān)聯(lián)規(guī)則的特征選擇算法（correlation-based feature selection： CFS）就是這樣一種基于相關(guān)性的度量方式。下面從特征子集選擇的四要素方面具體敘述：

1.搜索起點(diǎn)和方向：實(shí)驗(yàn)中從一個(gè)空集開始，進(jìn)行帶回溯的前向式搜索。

2.搜索策略：每次加入新的特征，判斷當(dāng)前特征子集的預(yù)測(cè)效果是否優(yōu)于原特征子集。

3.特征評(píng)估函數(shù)：根據(jù)屬性子集中每一個(gè)特征的預(yù)測(cè)能力以及它們之間的關(guān)聯(lián)性進(jìn)行評(píng)估，傾向于選擇與類別的相關(guān)性高，相互之間關(guān)聯(lián)度低的特征。相關(guān)度量計(jì)算方法見公式（6）：

4.停止準(zhǔn)則：預(yù)測(cè)效果超過給定閡值（>0.6）且不再增加為止。

本文通過結(jié)合K-means聚類算法，用極小的系統(tǒng)代價(jià)改善了包裝式特征子集選擇方法的搜索空間大，計(jì)算開銷大的缺點(diǎn)，并能獲得低冗余率的特征子集，且對(duì)后續(xù)預(yù)測(cè)模型的性能也有提高。

4 實(shí)驗(yàn)內(nèi)容與結(jié)果

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

研究中使用的是NASA（美國(guó)國(guó)家航空航天局）的MDP項(xiàng)目數(shù)據(jù)集。MDP是由NASA提供的一個(gè)軟件度量庫，存儲(chǔ)了模塊（函數(shù)/方法）級(jí)的度量數(shù)據(jù)和相關(guān)的缺陷數(shù)據(jù)。該公開缺陷數(shù)據(jù)信息庫，為不同研究者以及不同的缺陷預(yù)測(cè)方法，提供了可供比較的基準(zhǔn)。本文選擇MDP公開數(shù)據(jù)集，以便于和其他算法比較，同時(shí)能讓其他研究者重復(fù)本文方法，進(jìn)行比較改進(jìn)。本文獲取了Promise庫中11個(gè)數(shù)據(jù)集的項(xiàng)目數(shù)據(jù)，具體信息如表2所示。

4.2 實(shí)驗(yàn)流程

本文提出的聚類特征子集選擇方法稱為Fea-ture Cluster and Subset Selection （FCASS），此外，為證明本文方法的有效性，實(shí)驗(yàn)對(duì)比了傳統(tǒng)的特征選擇方法FC-Ranking （Feature Cluster and Ranking），即先進(jìn)行聚類分析，隨后在聚類中根據(jù)信息增益計(jì)算出每個(gè)特征與類標(biāo)間的相關(guān)性，并按照相關(guān)性從大到小排序，保留[Log2M]的特征。按照Gao等人[4]的建議，保留[Log2M]的特征可使特征子集包含信息最大化的同時(shí)含有較低的冗余率。此外，不經(jīng)特征選擇過程，直接使用全部特征集（FullSet）構(gòu)建模型也作為證明特征選擇必要性的對(duì)比實(shí)驗(yàn)。

首先由不同的特征選擇方法進(jìn)行處理得到最優(yōu)子集，然后在原始樣本數(shù)據(jù)集中只保留最優(yōu)子集中的特征，得到新的樣本數(shù)據(jù)集。實(shí)驗(yàn)采用十折交叉驗(yàn)證，具體方法是將新的樣本數(shù)據(jù)集隨機(jī)劃分為10份，其中的9份作為訓(xùn)練集，l份作為測(cè)試集。實(shí)驗(yàn)重復(fù)10次，確保每個(gè)實(shí)例都被預(yù)測(cè)過一次，最終取10次運(yùn)行結(jié)果的平均值。最后基于訓(xùn)練集構(gòu)建軟件缺陷預(yù)測(cè)模型。后續(xù)預(yù)測(cè)模型我們采用weka平臺(tái)的樸素貝葉斯（Naive Bayes）分類模型，分類器參數(shù)為默認(rèn)值。

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

在軟件缺陷預(yù)測(cè)領(lǐng)域，常常用混淆矩陣的相關(guān)指標(biāo)對(duì)分類器性能進(jìn)行評(píng)價(jià)。缺陷預(yù)測(cè)中不同類別的實(shí)例誤分的代價(jià)是不同的，本文主要關(guān)注精確率（Precision，簡(jiǎn)稱P）、召回率（Recall，簡(jiǎn)稱R）和F-measure等評(píng)價(jià)度量指標(biāo)。

精確率和召回率本身有一定局限，難以單獨(dú)評(píng)價(jià)分類器性能的優(yōu)劣，F(xiàn)度量是精確率與召回率的調(diào)和平均值，可以對(duì)精確率和召回率這兩個(gè)指標(biāo)進(jìn)行有效的平衡，其取值越高，表明模型預(yù)測(cè)效果越好。其計(jì)算公式為：

4.4 結(jié)果分析

針對(duì)軟件缺陷預(yù)測(cè)領(lǐng)域的特征聚類選擇方法，主要考慮兩個(gè)問題：一是使用特征選擇是否降低了特征維度;二是經(jīng)過特征選擇是否提高了缺陷模塊的預(yù)測(cè)精度？

表4為經(jīng)不同特征選擇方法進(jìn)行選擇后剩余的特征個(gè)數(shù)，由表可知，經(jīng)過特征選擇明顯降低了特征維度，本文提出的FCASS方法平均降低了81.8%，傳統(tǒng)特征聚類方法FC -Ranking平均降低了83.2%。實(shí)事求是地講，因?yàn)閭鹘y(tǒng)特征選擇方法總是選擇[Log2M]個(gè)特征，在特征數(shù)量以數(shù)十計(jì)時(shí)，比較有優(yōu)勢(shì)，當(dāng)特征更高維度時(shí)，包裝式特征子集選擇方法的優(yōu)勢(shì)會(huì)越來越明顯。

運(yùn)用三種不同特征選擇方法，構(gòu)建缺陷預(yù)測(cè)模型，預(yù)測(cè)結(jié)果如表5所示。從表5統(tǒng)計(jì)結(jié)果可知，本文方法FCASS對(duì)缺陷模塊的預(yù)測(cè)精確度在0.673 -0.967之間，平均值為0.83，其中僅有MC2數(shù)據(jù)集上是0.7以下，其余均在0.7以上，尤其PC5軟件缺陷集達(dá)到了0.967的精確度。在召回率方面，除KC1、MC2數(shù)據(jù)集外，其余均優(yōu)于傳統(tǒng)特征聚類選擇方法和全集方法，平均值最高為0.847。F度量指標(biāo)上，F(xiàn)CASS方法顯著優(yōu)于傳統(tǒng)特征聚類方法和全集方法，F(xiàn)l值介于0.673 -0.969之間，平均值為0.835，在PC5數(shù)據(jù)集上，達(dá)到最高0.969。值得注意的是PC3數(shù)據(jù)集上，全集方法的精確度較高，但召回率差，兩者的調(diào)和平均值Fl值不如本文FCASS方法和傳統(tǒng)特征聚類方法。由此可見單一指標(biāo)難以反映模型的優(yōu)劣。

由圖2的綜合指標(biāo)F度量值可知，基于聚類的特征子集選擇方法構(gòu)建的模型整體預(yù)測(cè)效果優(yōu)于特征全集構(gòu)建的模型和傳統(tǒng)先聚類后排序構(gòu)建的模型，同時(shí)，傳統(tǒng)先聚類后排序方法又優(yōu)于特征全集構(gòu)建的模型，證實(shí)了對(duì)樣本數(shù)據(jù)集進(jìn)行特征選擇的必要性，以及樣本聚類在特征選擇過程中的作用。

5 結(jié)束語

本文針對(duì)軟件缺陷預(yù)測(cè)領(lǐng)域，樣本數(shù)據(jù)集中存在特征維度高、相互間有冗余的問題，提出了結(jié)合聚類分析和特征子集選擇的方法，首先對(duì)樣本進(jìn)行聚類，這樣可以將具有冗余關(guān)系的樣本集中在同一聚類中，同時(shí)有效降低了子集搜索空間，改善了傳統(tǒng)特征選擇計(jì)算開銷大的問題;其次再對(duì)每一個(gè)聚類簇進(jìn)行特征子集選擇，選擇出組合效果最大的一組特征子集，而不是單個(gè)預(yù)測(cè)效果較好的特征的累加。經(jīng)實(shí)例證明本文方法不僅降低了特征子集的冗余率，并能有效提高預(yù)測(cè)的準(zhǔn)確度。在后續(xù)工作中，我們將對(duì)其他特征相關(guān)性度量方法做進(jìn)一步研究，比較其對(duì)缺陷預(yù)測(cè)性能的影響。

參考文獻(xiàn)

[1]陳翔，顧慶，劉望舒，等.靜態(tài)軟件缺陷預(yù)測(cè)方法研究[J].軟件學(xué)報(bào)，2016，27（1）：1-25

[2]王青，伍書劍，李明樹.軟件缺陷預(yù)測(cè)技術(shù)[J].軟件學(xué)報(bào).2008，19 （7）：1565-1580

[3]劉望舒，陳翔，顧慶，等，軟件缺陷預(yù)測(cè)中基于聚類分析的特征選擇方法[J].中國(guó)科學(xué)：信息科學(xué)，2016，46：1298-1320

[4] GAO K H，KHOSHCOFTAAR T M， WANC H J，et al.Choos-ing software metrics for defect prediction：an investigation on fea-ture selection techniques [J]. Software-practice& Experience：2011，41（5）：579-606

[5] GUO L，MA Y，CUKIC B，et al.Robust prediction of fault-proneness by random forestsECl.ISSRE，IEEE，2004：417-428

[6] MENZIES T，GREENWALD J，F(xiàn)RANK A.Data ruining staticcode attributes to leam defect predictors [C].IEEE Transactionson Software， 2007，32：1-12

[7] WANC H J，KHOSHCOFTAAR T M，NAPOLITANO A.A com-parative study of ensemble feature selection techniques for soft-ware defect prediction [C]. Proceedings of the Intema-tionalConference on Machine Learrung and Applications， Washing-ton， 2010：135-140

[8] MlrIRA P，MURTHY C，PAL S.Unsupervised feature selectionusing feature similarity[C].IEEE Transactions on Pattem Analy-sis and Machine Intelligence，2002：24 （3） ，301-312

[9] LIU Shu-long， CHEN Xiang，LIU Wang-shu.FECAR：A Fea-ture Selection Framework for Software Defect Prediction [C].IEEE 38th Annual International Computers， Software and Ap-plications Conference， 2014：426-435

[10] ZHANC Hong-yu.An Investigation of the Relationships betweenLines of Code and Defects [C].IEEE Intemational Conference onSoftware Maintenance， 2009： 274-283

[11] DUBEY V-K，SAXENA A-K，SHRIVAS M-M.A Cluster-FilterFeature Selection Approach [C].ICTBIC，IEEE，2017： 1-5

[12] MENZIES T，GREENWALD J，F(xiàn)RANK A.Data Mining StaticCode Attrihutes to Leam Defect Predictors [C]. IEEE Transac-tions on Software Engineering，2007，33（1）：2-13

[13]王培，金聰.面向軟件缺陷預(yù)測(cè)的互信息屬性選擇方法[J].計(jì)算機(jī)應(yīng)用，2012，32 （6）：1738-1740

[14]王連喜，蔣盛益.一種基于特征聚類的特征選擇方法[J].計(jì)算機(jī)應(yīng)用研究，2015 （5）：1305-1308