基于最大信息系數(shù)的軟件缺陷數(shù)目預(yù)測(cè)特征選擇方法

劉國(guó)慶，王興起，魏丹，方景龍，邵艷利

（杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州 310018）

1 引言

隨著信息時(shí)代的到來(lái)，計(jì)算機(jī)軟件數(shù)量、種類(lèi)快速增長(zhǎng)，軟件質(zhì)量問(wèn)題被越來(lái)越多的人關(guān)注。在軟件開(kāi)發(fā)的過(guò)程中，對(duì)軟件需求的錯(cuò)誤理解或人員的經(jīng)驗(yàn)不足都可能引入缺陷。軟件缺陷是軟件質(zhì)量的對(duì)立面，威脅著軟件質(zhì)量[1]。從軟件開(kāi)發(fā)的角度來(lái)看，處理軟件缺陷是一項(xiàng)至關(guān)重要的任務(wù)。缺陷的存在不僅降低了軟件的質(zhì)量，而且還增加了軟件的開(kāi)發(fā)、測(cè)試和維護(hù)成本。因此，在軟件開(kāi)發(fā)的早期階段預(yù)測(cè)出軟件缺陷模塊，可以指導(dǎo)軟件測(cè)試人員關(guān)注缺陷模塊，有助于提高軟件質(zhì)量。

目前在軟件缺陷預(yù)測(cè)領(lǐng)域已經(jīng)有大量研究工作，絕大多數(shù)致力于識(shí)別軟件模塊中有缺陷或無(wú)缺陷，含有不同缺陷數(shù)量的軟件模塊在軟件測(cè)試中被同等對(duì)待。然而，對(duì)于有缺陷的模塊，有些軟件模塊含有的缺陷較多，有些模塊含有的缺陷數(shù)較少，與含有較少缺陷的模塊相比，缺陷數(shù)量相對(duì)較多的軟件模塊則需要付出更多的資源去測(cè)試和修改。因此，僅根據(jù)有缺陷和無(wú)缺陷分配質(zhì)量保證資源可能會(huì)導(dǎo)致資源利用效率低下，而預(yù)測(cè)軟件模塊的缺陷數(shù)目可以給軟件測(cè)試提供更多的參考，更有利于分配測(cè)試資源。

目前，已有工作提出并且評(píng)估了基于回歸模型的軟件缺陷數(shù)目預(yù)測(cè)的方法，這類(lèi)方法可以預(yù)測(cè)軟件模塊中有多少缺陷。但大部分都是基于模型的角度，利用從軟件歷史倉(cāng)庫(kù)挖掘的數(shù)據(jù)集，通過(guò)對(duì)比不同的回歸模型，得到一個(gè)性能較好的回歸模型。在構(gòu)建缺陷數(shù)目預(yù)測(cè)模型時(shí)，數(shù)據(jù)集中的度量元含有冗余特征或無(wú)關(guān)特征，這些特征的存在會(huì)嚴(yán)重影響預(yù)測(cè)模型的性能。因此，設(shè)計(jì)有效的特征選擇方法來(lái)移除這類(lèi)特征具有重要意義。

特征相關(guān)性度量標(biāo)準(zhǔn)的選取對(duì)于冗余特征和無(wú)關(guān)特征的衡量非常重要。目前軟件缺陷預(yù)測(cè)中常見(jiàn)的特征度量[2]大多僅能度量特征間的線(xiàn)性關(guān)系，難以刻畫(huà)特征間的非線(xiàn)性關(guān)系。在軟件缺陷數(shù)據(jù)中特征之間既存在線(xiàn)性相關(guān)關(guān)系，也存在非線(xiàn)性相關(guān)關(guān)系。對(duì)于軟件度量特征來(lái)說(shuō)，非線(xiàn)性的相關(guān)度度量方法比線(xiàn)性方法更為實(shí)際有效[3-4]。最大信息系數(shù)（maximum information coefficient，MIC）能夠廣泛地度量變量間的依賴(lài)關(guān)系，包括線(xiàn)性關(guān)系、非線(xiàn)性關(guān)系以及非函數(shù)依賴(lài)關(guān)系。

本文提出了一種基于MIC的兩階段特征選擇方法（two-stage feature selection method based on maximum information coefficient，MIC-TSFS），該方法基于MIC度量特征與特征之間、特征與軟件缺陷數(shù)目之間的關(guān)聯(lián)性，衡量特征之間線(xiàn)性和非線(xiàn)性相關(guān)性，從而建立將特征冗余性分析和相關(guān)性性分析相分離的兩階段特征選擇框架。為驗(yàn)證MIC-TSFS方法的有效性，在PROMISE真實(shí)軟件項(xiàng)目上進(jìn)行了實(shí)證性的研究，實(shí)驗(yàn)結(jié)果表明，MIC-TSFS能夠移除冗余特征和無(wú)關(guān)特征，得到優(yōu)化的特征子集，構(gòu)建更有效的軟件缺陷數(shù)目預(yù)測(cè)模型。

2 相關(guān)工作

軟件缺陷數(shù)目預(yù)測(cè)從軟件歷史倉(cāng)庫(kù)中得到歷史缺陷數(shù)據(jù)，然后構(gòu)建缺陷數(shù)目預(yù)測(cè)模型，并用模型來(lái)預(yù)測(cè)出被測(cè)項(xiàng)目中軟件模塊的缺陷數(shù)目，從而為軟件測(cè)試中如何分配測(cè)試資源提供指導(dǎo)意見(jiàn)。軟件缺陷數(shù)目預(yù)測(cè)是智能化軟件工程領(lǐng)域中的一個(gè)研究熱點(diǎn)。

目前，國(guó)內(nèi)外的研究者提出了多種有效的軟件缺陷數(shù)目預(yù)測(cè)模型。Graves等[3]建立線(xiàn)性回歸（linear regression，LR）模型并應(yīng)用于大型的電信系統(tǒng)項(xiàng)目。Ostrand等[4]使用負(fù)二項(xiàng)回歸（negative binomial regression，NBR）技術(shù)對(duì)故障數(shù)和故障密度預(yù)測(cè)進(jìn)行了研究。Chen等[5]探究了一些典型的回歸模型在軟件缺陷個(gè)數(shù)預(yù)測(cè)上的可行性，實(shí)驗(yàn)結(jié)果表明，決策樹(shù)回歸取得了較好預(yù)測(cè)結(jié)果。Rathore等[6]提出了一種基于遺傳編程的軟件缺陷預(yù)測(cè)方法，實(shí)驗(yàn)結(jié)果表明，利用該方法對(duì)缺陷數(shù)目進(jìn)行預(yù)測(cè)能夠取得較好結(jié)果。Rathore等[7]探究了決策樹(shù)回歸模型在版本內(nèi)缺陷數(shù)目預(yù)測(cè)和跨版本缺陷數(shù)目預(yù)測(cè)兩種不同的研究場(chǎng)景下的預(yù)測(cè)能力，結(jié)果表明該方法在版本內(nèi)進(jìn)行預(yù)測(cè)時(shí)能夠取得較好的結(jié)果。Rathore[8]比較了6種用于軟件缺陷數(shù)目預(yù)測(cè)的方法（遺傳編程（genetic programming）、多層感知（multi-layer perceptron）、線(xiàn)性回歸（linear regression）、決策樹(shù)回歸（decision tree regression）、零膨脹泊松回歸 （zero-inflated Poisson regression）和負(fù)二項(xiàng)回歸 （negative binomial regression））對(duì)于軟件缺陷數(shù)目的預(yù)測(cè)能力，實(shí)驗(yàn)結(jié)果表明決策樹(shù)回歸、遺傳編程、多層感知和線(xiàn)性回歸通常會(huì)有較好的預(yù)測(cè)性能，而零膨脹泊松回歸和負(fù)二項(xiàng)回歸表現(xiàn)通常不佳。Chen等[9]探究了有監(jiān)督方法與無(wú)監(jiān)督方法在缺陷數(shù)目預(yù)測(cè)方面的能力，將9種結(jié)合SMOTEND的有監(jiān)督方法與基于LOC度量的無(wú)監(jiān)督方法在版本內(nèi)預(yù)測(cè)、跨版本預(yù)測(cè)、跨項(xiàng)目預(yù)測(cè)中分別進(jìn)行了比較。

除上述基礎(chǔ)模型外，也有些研究工作針對(duì)缺陷數(shù)目預(yù)測(cè)提出了一些集成方法。Rathore等[10]研究了集成學(xué)習(xí)方法在軟件缺陷數(shù)預(yù)測(cè)方面的性能，先評(píng)價(jià)6種基礎(chǔ)模型，然后從中選擇3種性能較優(yōu)的模型進(jìn)行集成。他們[11]還提出了兩種線(xiàn)性規(guī)則、兩種非線(xiàn)性規(guī)則，用于集成基礎(chǔ)模型的輸出。并且做了實(shí)證研究，評(píng)估了在版本內(nèi)預(yù)測(cè)以及版本間預(yù)測(cè)兩種情景模式下，各個(gè)集成規(guī)則的預(yù)測(cè)性能。Yu等[12]探索了采樣（SMOTEND和RUSND）和集成學(xué)習(xí)（AdaBoost.R2）方法對(duì)軟件缺陷數(shù)目的預(yù)測(cè)能力，然后提出了SMOTENDBoost和RUSNDBoost這兩種混合方法，實(shí)驗(yàn)結(jié)果表明融合過(guò)采樣與集成學(xué)習(xí)可以有效提高對(duì)于缺陷數(shù)量的預(yù)測(cè)性能。

以上研究都是從模型的構(gòu)建的角度出發(fā)，致力于找到一個(gè)性能較好的預(yù)測(cè)模型。然而，在構(gòu)建軟件缺陷數(shù)目預(yù)測(cè)模型時(shí)，在軟件缺陷的大量度量元中不可避免地會(huì)產(chǎn)生冗余特征和無(wú)關(guān)特征。冗余特征大量或完全重復(fù)了其他單個(gè)或多個(gè)特征中含有的信息，而無(wú)關(guān)特征則不能對(duì)采用的數(shù)據(jù)挖掘算法提供任何幫助。若在構(gòu)建模型之前去除冗余特征和無(wú)關(guān)特征，則能在一定程度上提升模型的性能。

特征選擇通過(guò)挖掘特征間以及特征與缺陷數(shù)目間的內(nèi)在聯(lián)系，保留最有利于預(yù)測(cè)的有效特征，是除去冗余特征和無(wú)關(guān)特征的一種有效的方法。除去冗余特征和無(wú)關(guān)特征時(shí)需要衡量變量之間的相關(guān)性，信息增益[13]、ReliefF等是衡量相關(guān)性的常見(jiàn)方法。目前已有的特征選擇算法可以分為兩大類(lèi)：基于子集搜索的特征選擇算法和基于排序的特征選擇算法?；谧蛹阉鞯奶卣鬟x擇算法考慮特征之間的冗余性和特征與類(lèi)別之間的相關(guān)性，但這類(lèi)方法需要搜索的特征子集空間太大，計(jì)算開(kāi)銷(xiāo)過(guò)大；基于排序的特征選擇算法根據(jù)特征與類(lèi)別之間的相關(guān)性從高到低排序，排名越靠前，與類(lèi)別屬性的相關(guān)性越高，表明該特征區(qū)分不同類(lèi)別的能力越強(qiáng)，然后從中選出排名靠前的特征來(lái)構(gòu)建預(yù)測(cè)模型，其運(yùn)行效率比較高，但選出的特征子集內(nèi)通常含有冗余特征。

目前已有研究人員將特征選擇方法應(yīng)用到軟件缺陷數(shù)目預(yù)測(cè)問(wèn)題中。李葉飛等[14]提出了一種針對(duì)軟件缺陷數(shù)目預(yù)測(cè)的特征選擇方法——FSDNP，該方法采用歐氏距離度量特征間相關(guān)性，使用密度峰聚類(lèi)對(duì)特征進(jìn)行聚類(lèi)，結(jié)合采用Pearson相關(guān)系數(shù)計(jì)算特征與缺陷數(shù)目之間的相關(guān)性時(shí)表現(xiàn)性能較好。Yu等[15]提出軟件缺陷預(yù)測(cè)下的特征選擇方法——FSCR，該方法首先基于特征間的Pearson相關(guān)系數(shù)進(jìn)行譜聚類(lèi)，然后根據(jù)ReliefF算法挑選與缺陷數(shù)目相關(guān)的特征。馬子逸等[16]提出了一種面向軟件缺陷個(gè)數(shù)預(yù)測(cè)的混合式特征選擇方法——HFSNFP，該方法先使用ReliefF算法計(jì)算特征與缺陷個(gè)數(shù)之間的相關(guān)性，移除無(wú)關(guān)特征，隨后根據(jù)特征與特征之間的Pearson相關(guān)系數(shù)對(duì)特征集進(jìn)行譜聚類(lèi)，將冗余度高的特征聚類(lèi)到同一個(gè)簇中，最后基于包裹式特征選擇的思想依次從每個(gè)簇中將最相關(guān)的特征加入特征子集中。這類(lèi)針對(duì)缺陷數(shù)目預(yù)測(cè)而提出的特征選擇方法在衡量特征與特征之間的相關(guān)性時(shí)通常采用Pearson相關(guān)系數(shù)或距離度量，僅表示了特征間的線(xiàn)性關(guān)系，忽略了特征之間的非線(xiàn)性相關(guān)性，不利于特征間的冗余性分析；此外，這類(lèi)方法中采用的聚類(lèi)方法需要事先設(shè)定參數(shù)，這些設(shè)定具有很大的主觀(guān)性和經(jīng)驗(yàn)性，設(shè)定不當(dāng)會(huì)影響預(yù)測(cè)模型的性能。

基于以上分析，為了有效地識(shí)別并移除特征集中的冗余特征和無(wú)關(guān)特征，本文提出了一種基于最大信息系數(shù)的特征選擇方法，該方法包括冗余性分析階段和相關(guān)性分析階段。在冗余性分析階段，根據(jù)特征與特征間的關(guān)聯(lián)度，采用自底向上的層次聚類(lèi)的算法對(duì)特征進(jìn)行聚類(lèi)得到特征簇，降低所選特征子集的冗余率；在相關(guān)性分析階段，根據(jù)特征與缺陷數(shù)目之間的關(guān)聯(lián)度將每個(gè)特征簇中的特征進(jìn)行排序，然后從每個(gè)特征簇中選擇排名靠前的特征組成特征子集，過(guò)濾掉無(wú)關(guān)特征。

3 基于最大信息系數(shù)的特征選擇方法

3.1 最大信息系數(shù)

最大信息系數(shù)可以用于衡量?jī)勺兞康南嚓P(guān)程度，其主要思想是：如果兩個(gè)變量之間存在一定的關(guān)聯(lián)，在這兩個(gè)變量的散點(diǎn)圖上進(jìn)行某種網(wǎng)格劃分之后，根據(jù)這兩個(gè)變量在網(wǎng)格中的近似概率密度分布，計(jì)算這兩個(gè)變量的互信息，該值經(jīng)過(guò)正則化后可用于度量這兩個(gè)變量之間的相關(guān)性。最大信息系數(shù)是互信息的推廣，不僅可以度量變量間的線(xiàn)性關(guān)系，而且可以度量變量間的非線(xiàn)性關(guān)系和非函數(shù)依賴(lài)關(guān)系。

假設(shè)有限集合D由X和Y組成，定義劃分G將變量X的值域分成x段，將Y的值域分成y段，得到一個(gè)x×y的網(wǎng)格，在得到的每一種網(wǎng)格劃分內(nèi)部計(jì)算互信息MI(X,Y)，取不同劃分的最大互信息作為劃分G的互信息值，定義劃分G下D的最大互信息公式為：

其中，D|G表示數(shù)據(jù)D使用G進(jìn)行劃分。

對(duì)于不同的劃分都會(huì)得到一個(gè)MI值，將所有MI值組成特征矩陣，并對(duì)該特征矩陣進(jìn)行規(guī)范化并定義為M(D)x,y，其計(jì)算式如下：

M(D)x,y為D在不同網(wǎng)格劃分下的規(guī)范化后的特征矩陣。最大信息系數(shù)MIC的計(jì)算式如下：

其中，B(n)為網(wǎng)絡(luò)劃分x×y的上限值， 一般地，，參考文獻(xiàn)[17]中給出B(n)=n0.6時(shí)效果較好。

MIC通過(guò)對(duì)連續(xù)型變量實(shí)施不等間隔的離散化尋優(yōu)來(lái)挖掘非線(xiàn)性關(guān)聯(lián)，并進(jìn)一步通過(guò)標(biāo)準(zhǔn)化使得MIC(X,Y)∈[0,1]。如果X、Y相互獨(dú)立，MIC(X,Y)=0，MIC值越大，兩個(gè)特征越相關(guān)；MIC具有對(duì)稱(chēng)性，即MIC(X,Y)=MIC(Y,X)；當(dāng)Y=f(X)時(shí)，MIC(X,Y)=1，即當(dāng)兩個(gè)變量之間存在函數(shù)關(guān)系時(shí)，這兩個(gè)變量之間的MIC值為1；若對(duì)變量X做任何單調(diào)函數(shù)g(X)變換，MIC不變，即MIC(X,Y)=MIC(g(X),Y)。

在軟件缺陷預(yù)測(cè)領(lǐng)域中，為了充分描述軟件特性，度量元特征集中存在冗余特征和無(wú)關(guān)特征。一些特征由同一組程序基本屬性計(jì)算得到，這些特征之間有很大概率存在冗余。缺陷數(shù)據(jù)特征之間不僅存在線(xiàn)性關(guān)系（如變量個(gè)數(shù)與代碼行數(shù)），也存在非線(xiàn)性關(guān)系（如類(lèi)個(gè)數(shù)與類(lèi)繼承樹(shù)深度）。一般的相關(guān)系數(shù)（如Pearson相關(guān)系數(shù)）因僅表示特征間的線(xiàn)性關(guān)系，不能充分表征特征間的相關(guān)性；而MIC具有較好的廣泛性和均勻性，能夠檢測(cè)出變量間的線(xiàn)性和非線(xiàn)性關(guān)系，進(jìn)而有效表達(dá)特征之間的相關(guān)性。本文把MIC作為特征與特征間相關(guān)性度量判據(jù)，從而通過(guò)移除冗余特征初步篩選特征集。

無(wú)關(guān)特征是與預(yù)測(cè)目標(biāo)不相關(guān)的特征，特征子集的優(yōu)劣可以通過(guò)特征與缺陷數(shù)目的相關(guān)性來(lái)度量。一般認(rèn)為，好的特征子集中的特征與缺陷數(shù)目相關(guān)度較高。在傳統(tǒng)的特征選擇方法中，若特征與缺陷數(shù)目間存在非線(xiàn)性函數(shù)依賴(lài)關(guān)系，很有可能被排除在模型外；而MIC受噪聲影響較小，可以敏感地檢測(cè)出變量之間的各種函數(shù)以及非函數(shù)關(guān)系。另外，一般的相關(guān)系數(shù)對(duì)變量變換很敏感，然而在構(gòu)建預(yù)測(cè)模型時(shí)變換并不明確，相關(guān)系數(shù)容易受到影響；而無(wú)論做何種單調(diào)變換，變量間的MIC值不變。因此，MIC穩(wěn)健性更好，能夠有效地度量特征與缺陷數(shù)目之間的相依關(guān)系。

基于上述分析，用MIC來(lái)選擇特征適用于有復(fù)雜的軟件缺陷的數(shù)據(jù)。因此，本文采用MIC衡量特征與特征間的相關(guān)性、特征與缺陷數(shù)目間的相關(guān)性，以此來(lái)移除冗余特征、初步篩選特征集，隨后剔除一些無(wú)關(guān)特征，進(jìn)而提高模型的預(yù)測(cè)性能。

3.2 特征關(guān)聯(lián)性度量

給定一個(gè)n條樣本的數(shù)據(jù)集F{f1,f2,f3,…,fN,d}，其中fi(i=1,2,3,…,N)為特征集中第i個(gè)特征，N為特征總數(shù)，d為軟件缺陷數(shù)目。對(duì)任意特征fi和fj，它們之間的相關(guān)度定義為FFfifj：

在軟件預(yù)測(cè)數(shù)據(jù)集中，特征間的冗余性越大，則它們相關(guān)度值越大。FFfifj值越大，說(shuō)明fi和fj之間的可替代性越強(qiáng)，即冗余性越強(qiáng)，聚類(lèi)時(shí)趨向于聚在同一個(gè)類(lèi)簇中。FFfifj值越小，說(shuō)明fi和fj之間越相互獨(dú)立，聚類(lèi)時(shí)趨向與聚在不同的簇類(lèi)中。

特征fi與軟件缺陷數(shù)目d之間的相關(guān)度定義為FDi：

FDi值越大表明特征fi與軟件缺陷數(shù)目d間的相關(guān)性越強(qiáng)，則fi為強(qiáng)相關(guān)特征，越傾向被保留；FDi值越小，表明特征fi與軟件缺陷數(shù)目d的相關(guān)性越弱，則fi為弱相關(guān)特征，越傾向被刪除。

3.3 MIC-TSFS方法

MIC-TSFS是一種將特征冗余性分析和相關(guān)性分析分離的兩個(gè)階段特征選擇方法，其總體框架如圖1所示。

圖1 MIC-TSFS框架

第一階段是冗余性分析階段，根據(jù)特征與特征之間的相關(guān)度，采用層次聚類(lèi)將原始數(shù)據(jù)集中的特征進(jìn)行聚類(lèi)，使得相關(guān)性較高的特征被劃分到同一簇中，而相關(guān)性較低的特征被劃分到不同簇中，這樣同一個(gè)簇里的特征冗余性較高，不同簇中的特征冗余性較低。將這一階段處理得到的特征簇作為第二階段的輸入。第二階段是相關(guān)性分析階段，在每個(gè)特征簇中計(jì)算特征與軟件缺陷數(shù)目的相關(guān)度，根據(jù)該值對(duì)特征簇內(nèi)的特征進(jìn)行排序，在每個(gè)簇中選取排名靠前的特征組成新的特征子集。

3.3.1 冗余性分析階段

為了降低特征間的冗余性，根據(jù)特征與特征之間的相關(guān)度，采用“自底向上”的凝聚層次聚類(lèi)將數(shù)據(jù)集中的特征集合進(jìn)行聚類(lèi)，將特征分為若干個(gè)特征簇，同一簇中的特征相關(guān)度高，不同簇的特征相關(guān)度低。相對(duì)于最常用的密度峰聚類(lèi)和譜聚類(lèi)算法，層次聚類(lèi)算法具有對(duì)聚類(lèi)參數(shù)依賴(lài)小、適用于任意形狀數(shù)據(jù)集聚類(lèi)的優(yōu)勢(shì)。因此，MIC-TSFS在冗余性分析階段選取了更適用于構(gòu)建魯棒特征選擇算法的凝聚層次聚類(lèi)算法。凝聚層次聚類(lèi)算法過(guò)程是：初始時(shí)將每個(gè)樣本看作一個(gè)類(lèi)簇，然后依據(jù)某種準(zhǔn)則合并這些初始的類(lèi)簇，直到達(dá)到某種條件或者達(dá)到設(shè)定的分類(lèi)數(shù)目，具體如算法1所示。

算法1凝聚層次聚類(lèi)算法

將樣本集中的所有的樣本點(diǎn)都當(dāng)作一個(gè)獨(dú)立的類(lèi)簇

達(dá)到聚類(lèi)的數(shù)目或者達(dá)到設(shè)定的條件在算法1中，有多種方法可以計(jì)算簇間相似度，包括最小相似度、最大相似度和均值相似度，由于最小和最大相似度量代表了簇間相似度量的兩個(gè)極端，它們趨向?qū)υ肼晹?shù)據(jù)過(guò)分敏感，因此，MIC-TSFS采用均值來(lái)度量簇間相似度。給定兩個(gè)特征簇Ci和Cj，簇Ci中包含p個(gè)特征，表示為簇Cj中包含q個(gè)特征，采用如下計(jì)算式計(jì)算它們之間的相關(guān)度：

若不提前中止簇合并，算法1會(huì)將所有的特征合并到同一個(gè)簇中。在算法1中，可設(shè)置達(dá)到聚類(lèi)的數(shù)目或者達(dá)到設(shè)定的條件，使合并的過(guò)程提前停止。為了避免參數(shù)依賴(lài)問(wèn)題，MIC-TSFS通過(guò)自適應(yīng)調(diào)參方式設(shè)置合并中止條件：

其中，N為特征的個(gè)數(shù)。當(dāng)?shù)^(guò)程中擬合并的兩個(gè)簇之間的相似度小于r時(shí)，簇與簇之間的相似度較小，不再進(jìn)行簇間的合并，從而結(jié)束迭代過(guò)程。

3.3.2 相關(guān)性分析階段

在相關(guān)性分析階段，為了過(guò)濾掉與軟件缺陷數(shù)目無(wú)關(guān)的特征，選擇對(duì)軟件缺陷數(shù)目預(yù)測(cè)較為有用的特征。依據(jù)特征和軟件缺陷數(shù)目之間的相關(guān)度，對(duì)每個(gè)特征簇中的特征進(jìn)行排序，然后依據(jù)簇的大小從每個(gè)特征簇中挑選排名靠前的特征。具體步驟如下：

（1）對(duì)于每個(gè)特征簇，逐個(gè)計(jì)算簇內(nèi)特征fi與軟件缺陷數(shù)目d之間的相關(guān)度FiD；

（2）從每個(gè)特征簇中選取前M個(gè)特征。對(duì)于M的取值，參考文獻(xiàn)[18]認(rèn)為將軟件缺陷數(shù)據(jù)集中特征數(shù)目減少為較為合適?？紤]到簇中特征數(shù)目可能存在為1的情況，此時(shí)，會(huì)導(dǎo)致此特征將無(wú)法被有效處理，因此，MIC-TSFS設(shè)置M的取值為，其中p為每個(gè)簇的特征個(gè)數(shù)。

3.4 算法描述

MIC-TSFS特征選擇方法的實(shí)現(xiàn)過(guò)程如算法2所示。

算法2MIC-TSFS算法

輸入F{f1,f2,f3,…,fN,d}：原始數(shù)據(jù)集

輸出Fsub{fi1,fi2,fi3,…,fim}：最終選擇出來(lái)的特征子集

冗余性分析階段

（1）初始化特征簇，對(duì)于含有N個(gè)特征的特征集{f1,f2,f3,…,fN}，每個(gè)特征作為一個(gè)簇，共有N個(gè)簇。

（2）根據(jù)式（8）計(jì)算閾值r，作為聚類(lèi)結(jié)束的判斷條件。

（3）根據(jù)式（7）計(jì)算簇與簇之間的相似度，選取簇間相關(guān)度最大兩個(gè)簇Ci和Cj。

合并這兩個(gè)簇；

根據(jù)式（7）重新計(jì)算簇與簇之間的相似度，選擇相關(guān)度最大兩個(gè)簇。

相關(guān)性分析階段

（7）foriin 1：N′ do。

（9）從中選取前M個(gè)特征并入Fsub

（10）end for

（11）returnFsub

步驟（1）～步驟（5）為使用特征間相關(guān)度與凝聚層次聚類(lèi)算法對(duì)冗余特征的處理過(guò)程，經(jīng)過(guò)聚類(lèi)之后，將冗余特征分到同一個(gè)特征簇中，即每個(gè)特征簇中包含大量的冗余特征，將在第二階段進(jìn)行刪除。步驟（6）～步驟（8），在每個(gè)特征簇中計(jì)算特征與軟件缺陷數(shù)目間的相關(guān)度，然后按照此相關(guān)度的值對(duì)特征進(jìn)行降序排序。步驟（9）選取每個(gè)特征簇中排名靠前的特征組成特征子集。經(jīng)過(guò)MIC-TSFS處理之后，原始數(shù)據(jù)集中的冗余特征和不相關(guān)特征將被過(guò)濾，從而得到高質(zhì)量特征子集，該特征子集可以作為回歸模型的輸入構(gòu)建軟件缺陷數(shù)目預(yù)測(cè)模型。

4 實(shí)證研究

4.1 評(píng)測(cè)對(duì)象

從軟件缺陷常用數(shù)據(jù)PROMISE項(xiàng)目集[10]中選取4個(gè)項(xiàng)目共14個(gè)常用公開(kāi)數(shù)據(jù)集進(jìn)行實(shí)證研究，這4個(gè)項(xiàng)目均是Apache的實(shí)際項(xiàng)目。其中Ant是Apache中一個(gè)由Java語(yǔ)言進(jìn)行編寫(xiě)的子項(xiàng)目；Camel是Apache的一個(gè)開(kāi)源項(xiàng)目，提供基于規(guī)則的路由引擎；Xerces是一項(xiàng)用于XML文檔解析的開(kāi)源項(xiàng)目；ivy是Ant的子項(xiàng)目，主要用來(lái)解決Ant的jar包的版本管理。對(duì)各個(gè)版本的項(xiàng)目源程序按照參考文獻(xiàn)[19]的度量方式進(jìn)行度量，從而得到項(xiàng)目中每個(gè)模塊的特征。每個(gè)項(xiàng)目都含有很多類(lèi)級(jí)別的特征，例如特征dit表示一個(gè)類(lèi)的繼承數(shù)的深度；特征noc表示一個(gè)類(lèi)的直接子類(lèi)的個(gè)數(shù)；特征loc表示類(lèi)的二進(jìn)制碼的行數(shù)等。這些特征都是基于代碼復(fù)雜度和面向?qū)ο筇匦赃M(jìn)行設(shè)計(jì)的。數(shù)據(jù)集特征見(jiàn)表1，Release表示軟件項(xiàng)目不同的發(fā)行版本，#Instance表示實(shí)例的數(shù)量，#Defects表示實(shí)例中缺陷的總數(shù)，%Defects表示有缺陷的實(shí)例占所有實(shí)例的百分比，Max表示所有實(shí)例中最大的缺陷個(gè)數(shù)。這些項(xiàng)目在之前的研究工作中被廣泛使用，并可從PROMISE中免費(fèi)獲取。

表1 數(shù)據(jù)集特征

4.2 評(píng)測(cè)指標(biāo)

為了評(píng)估MIC-TSFS在軟件缺陷數(shù)目預(yù)測(cè)中的性能，使用平均絕對(duì)誤差（average absolute error，AAE）、平均相對(duì)誤差（average relative error，ARE）、G-mean評(píng)價(jià)指標(biāo)。

AAE是一組預(yù)測(cè)數(shù)據(jù)中所有誤差的平均值，它表明了預(yù)測(cè)結(jié)果和真實(shí)結(jié)果之間的差距。其定義如下：

其中，ARE表示當(dāng)整體目標(biāo)項(xiàng)目被評(píng)估時(shí)相對(duì)誤差的大小，其定義如下：

其中，表示測(cè)試集中的第i個(gè)樣本的預(yù)測(cè)缺陷數(shù)目，iY表示測(cè)試集中的第i個(gè)樣本真實(shí)含有的缺陷數(shù)目，n表示測(cè)試集中的樣本數(shù)目。

為了進(jìn)一步比較各種方法之間的性能，本文使用“Win/Draw/Loss”分析：“Win”表示“方法1”好于“方法2”的次數(shù)；“Draw”表示“方法 1”相似與“方法2”的次數(shù)；“Loss”表示“方法1”差于“方法2”的次數(shù)。

在軟件缺陷數(shù)目預(yù)測(cè)中，平均絕對(duì)誤差與平均相對(duì)誤差反映了預(yù)測(cè)值偏離真實(shí)值的程度。為了衡量預(yù)測(cè)的準(zhǔn)確性，引入G-mean作為評(píng)價(jià)指標(biāo)，其定義如下：

TP/(TP+FN)描述模型能正確搜索缺陷數(shù)目大于0的樣本的能力；TN/(TN+FP)描述模型能正確搜索缺陷數(shù)目等于0的樣本的能力；G-mean是這兩種能力的綜合評(píng)價(jià)指標(biāo)，其值越大，表示模型預(yù)測(cè)性能越好。其中，TP是指被正確預(yù)測(cè)的有缺陷的樣本數(shù)，F(xiàn)P是指被錯(cuò)誤預(yù)測(cè)為有缺陷的無(wú)缺陷的樣本數(shù)，F(xiàn)N是指被錯(cuò)誤預(yù)測(cè)為無(wú)缺陷的有缺陷的樣本數(shù)，TN是指被正確預(yù)測(cè)的無(wú)缺陷的樣本數(shù)。本文預(yù)測(cè)軟件缺陷數(shù)目，即缺陷數(shù)目大于0的實(shí)例被認(rèn)為有缺陷，缺陷數(shù)目等于0即無(wú)缺陷。

4.3 回歸模型

本文采用了3種回歸模型來(lái)構(gòu)建軟件缺陷數(shù)目預(yù)測(cè)模型：貝葉斯嶺回歸（Bayesian ridge regression）、線(xiàn)性回歸（linear regression）和決策樹(shù)回歸（decision tree regression）。這3種回歸模型是在軟件缺陷數(shù)目預(yù)測(cè)中常用而且性能較優(yōu)的模型[17]。

· 貝葉斯嶺回歸：該方法類(lèi)似于經(jīng)典的嶺回歸方法。這種方法的超參數(shù)是通過(guò)先驗(yàn)概率引入的，然后基于概率模型的最大化邊緣對(duì)數(shù)似然來(lái)評(píng)估。

· 線(xiàn)性回歸：它通常被用于求解一個(gè)或多個(gè)自變量和一個(gè)因變量之間的線(xiàn)性關(guān)系的最小二乘函數(shù)。

· 決策樹(shù)回歸：該方法學(xué)習(xí)簡(jiǎn)單的決策規(guī)則來(lái)近似擬合給定的訓(xùn)練數(shù)據(jù)，然后預(yù)測(cè)目標(biāo)變量。

在實(shí)驗(yàn)中，采用10折交叉驗(yàn)證，即將原始數(shù)據(jù)集等分為10份，使用其中的9份作為訓(xùn)練集，剩余的1份作為測(cè)試集，反復(fù)10次。在此過(guò)程中，每1份數(shù)據(jù)都保證恰好有一次作為測(cè)試集，最后結(jié)果采用10次交叉實(shí)驗(yàn)結(jié)果的平均值。

4.4 結(jié)果分析

在PROMISE數(shù)據(jù)集上對(duì)所提出的方法進(jìn)行了實(shí)證性研究，對(duì)比了ReliefF算法、信息增益、卡方檢驗(yàn)3種傳統(tǒng)的特征選擇方法，以及HFSNFP[18]、FSCR[17]、FSDNP[16]3種用于軟件缺陷數(shù)目預(yù)測(cè)的特征選擇方法。對(duì)于傳統(tǒng)的特征選擇方法，本文選取的特征數(shù)為其中N為特征的總數(shù)量。對(duì)于HFSNFP、FSCR和FSDNP方法，本文分別根據(jù)參考文獻(xiàn)[16-18]中的設(shè)置來(lái)選擇特征。在貝葉斯嶺回歸模型中，全特征（full）、ReliefF算法、信息增益（info）、卡方檢驗(yàn)（chi2）、HFSNFP、FSCR、FSDNP等方法與MIC-TSFS方法的AAE見(jiàn)表2。

在貝葉斯嶺回歸模型中全特征（full）、ReliefF算法、信息增益（info）、卡方檢驗(yàn)（chi2）、HFSNFP、FSCR、FSDNP等方法與MIC-TSFS方法的ARE的對(duì)比結(jié)果見(jiàn)表3。在表2中，第1列表示項(xiàng)目的名稱(chēng)，剩余列表示各種方法的AAE平均值。最后一行表示MIC-TSFS方法與其他方法之間的“Win/Draw/Loss”比較結(jié)果。例如MIC-TSFS與全特征的結(jié)果為“10/1/3”，即在10個(gè)數(shù)據(jù)集上MIC-TSFS比全特征的性能較好，在1個(gè)數(shù)據(jù)集上MIC-TSFS與全特征性能相似，在3個(gè)數(shù)據(jù)集上MIC-TSFS比全特征的性能弱。貝葉斯嶺回歸模型下，MIC-TSFS與傳統(tǒng)的特征選擇方法ReliefF、信息增益、卡方檢驗(yàn)進(jìn)行比較，“Win/Draw/Loss”的結(jié)果分別為“10/1/3”“10/1/3”“10/2/2”。MIC-TSFS與HFSNFP方法、FSCR以及FSNNP對(duì)比，“Win/Draw/Loss”的結(jié)果為“10/1/3”“9/2/3”“9/1/4”，AAE分別降低了5.9%、10.5%、3.8%。倒數(shù)第二行mean表示在所有數(shù)據(jù)集上AAE，貝葉斯嶺回歸模型下在MIC-TSFS上，AAE的均值最低，即在所有數(shù)據(jù)集上，MIC-TSFS方法的整體平均絕對(duì)誤差最小。

表2 貝葉斯嶺回歸模型的AAE

表3 貝葉斯嶺歸模型的ARE

表3列出了MIC-TSFS方法、全特征（full）、ReliefF算法、信息增益、卡方檢驗(yàn)、FSCR、FSDNP以及HFSNFP方法等在貝葉斯嶺歸模型中的ARE值。MIC-TSFS與這幾種方法對(duì)比的“Win/Draw/Loss”的結(jié)果分別為“9/1/4”“9/1/4”“7/1/6”“9/1/4”“8/2/4”“8/1/5”“10/1/3”。在大多數(shù)的數(shù)據(jù)集下，MIC-TSFS能獲得較優(yōu)的結(jié)果，而且在所有數(shù)據(jù)集上MIC-TSFS的ARE最低。由此可見(jiàn)在貝葉斯嶺回歸下MIC-TSFS的性能相對(duì)其他特征方法的性能較好，即選出的特征能構(gòu)造更有效的貝葉斯嶺回歸缺陷數(shù)目預(yù)測(cè)模型。

在線(xiàn)性回歸模型中，各種方法的AAE與ARE的對(duì)比結(jié)果見(jiàn)表4和表5。在表4中，MIC-TSFS方法與全特征（full）、ReliefF算法、信息增益、卡方檢驗(yàn)、HFSNFP方法、FSCR以及FSDNP中AAE的“Win/Draw/Loss”對(duì)比結(jié)果分別為：“8/2/4”“8/2/4”“9/1/4”“9/1/4”“8/1/5”“8/1/5”“8/1/5”。對(duì)比FSCR以及FSDNP方法，AAE分別降低3.9%、1.5%。在大多數(shù)數(shù)據(jù)集中，MIC-TSFS方法對(duì)比其他特征選擇方法，得到的AAE較小。

在表5中，在線(xiàn)性回歸模型下，MIC-TSFS方法對(duì)比全特征、卡方檢驗(yàn)的“Win/Draw/Loss”對(duì)比結(jié)果分別為“8/2/4”“9/1/4”，表明在大部分?jǐn)?shù)據(jù)集中，MIC-TSFS方法得到的ARE較?。籑IC-TSFS與ReliefF算法、信息增益、HFSNFP方法、FSCR方法以及FSDNP方法的ARE“Win/Draw/Loss”對(duì)比結(jié)果分別為 “7/2/5”“7/1/6”“7/1/6”“7/1/6”“7/1/6”，表明在過(guò)半的數(shù)據(jù)集上MIC-TSFS比ReliefF算法、信息增益、HFSNFP方法、FSCR方法以及FSDNP方法，MIC-TSFS所得到的ARE小，且MIC-TSFS方法選出的特征構(gòu)建的線(xiàn)性回歸模型在所有數(shù)據(jù)集上的AAE與ARE最低。因此MIC-TSFS方法選出的特征也能構(gòu)造更為有效的線(xiàn)性回歸預(yù)測(cè)模型。

表6和表7分別列出了在決策樹(shù)回歸模型下各種方法的AAE與ARE的對(duì)比結(jié)果。

表4 線(xiàn)性回歸模型的AAE

在表6中，MIC-TSFS方法所有數(shù)據(jù)集的AAE均值最小，且MIC-TSFS方法與全特征、ReliefF算法、信息增益、卡方檢驗(yàn)、HFSNFP方法的AAE“Win/Draw/Loss”比較結(jié)果分別為：“9/1/4”“9/1/4”“8/2/4”“8/2/4”“8/1/5”。在表 7中，所有數(shù)據(jù)集上MIC-TSFS的ARE均值最低，且MIC-TSFS方法與全特征、ReliefF算法、信息增益、卡方檢驗(yàn)、HFSNFP方法的AAE“Win/Draw/Loss”的結(jié)果分別為“9/1/4 ”“8/1/5”“9/2/3”“8/2/4”“8/2/4”。說(shuō)明在大多數(shù)數(shù)據(jù)集中，由MIC-TSFS方法所挑選的特征訓(xùn)練出的模型誤差較小。MIC-TSFS相比于FSCR與FSDNP方法，AAE分別降低3.5%、3.2%，ARE分別降低3.8%、5.4%。由此可以看出MIC-TSFS方法選擇的特征，也能構(gòu)造更為有效的決策樹(shù)回歸模型。

表5 線(xiàn)性回歸模型的ARE

表6 決策樹(shù)回歸模型的AAE

表7 決策樹(shù)回歸模型的ARE

為進(jìn)一步說(shuō)明MIC-TSFS方法的有效性，表8～表10分別給出經(jīng)由各種特征選擇方法選出的特征子集分別在貝葉斯嶺回歸、線(xiàn)性回歸以及決策樹(shù)回歸模型中得到G-mean值。

在表8中，MIC-TSFS的G-mean均值最高。與ReliefF算法、信息增益、卡方檢驗(yàn)、HFSNFP、FSCR以及FSDNP的特征選擇方法相比，G-mean均值分別提升4.9%、7.2%、4.1%、5.9%、9.8%、10.5%。

在表9中，MIC-TSFS的G-mean同樣具有最高的均值，與不使用特征選擇方法的full相比，其G-mean均值提高5.3%，而對(duì)比ReliefF算法、信息增益、卡方檢驗(yàn)，G-mean均值分別提升6.4%、29.1%、8.2%。MIC-TSFS相對(duì)于HFSNFP、FSCR以及FSDNP特征選擇方法G-mean均值提升3.7%、5.4%、13.5%。

從表10可以看出MIC-TSFS同樣具有較高的G-mean均值。與ReliefF算法、信息增益、卡方檢驗(yàn)、HFSNFP、FSCR以及FSDNP的特征選擇方法相比，G-mean均值分別提升3.2%、17.6%、2.8%、3.9%、3.2%、5.7%；而與不使用任何特征選擇方法相比，G-mean均值提升3.8%。

在貝葉斯嶺回歸、線(xiàn)性回歸以及決策樹(shù)回歸3種模型中，MIC-TSFS方法的G-mean的平均值都達(dá)到最優(yōu)，說(shuō)明就整體情況而言，MIC-TSFS方法要優(yōu)于其他特征選擇方法。然而，在數(shù)據(jù)集camel-1.0與ivy-1.4上，特征選擇方法的大多數(shù)G-mean值為0，其可能原因是這兩個(gè)數(shù)據(jù)集中數(shù)據(jù)不平衡率較高（其中缺陷數(shù)目大于0的樣

本的占比分別是3.8%、6.7%），受數(shù)據(jù)不平衡的影響，這3種回歸模型均沒(méi)有正確找到的缺陷數(shù)不為0的樣本，從而導(dǎo)致混淆矩陣中TP為0。因此，在后續(xù)工作中可以考慮對(duì)不平衡因素進(jìn)行處理，如結(jié)合smote過(guò)采樣或代價(jià)敏感，以進(jìn)一步提高模型預(yù)測(cè)性能。

表8 貝葉斯嶺回歸模型的G-mean

表9 線(xiàn)性回歸模型的G-mean

表10 決策樹(shù)回歸模型的G-mean

對(duì)比在貝葉斯嶺回歸、線(xiàn)性回歸、決策樹(shù)回歸模型下，MIC-TSFS方法相對(duì)傳統(tǒng)的特征選擇方法的性能較好，這是因?yàn)镸IC-TSFS除了考慮特征和標(biāo)簽之間相關(guān)性外，還考慮了特征與特征之間的冗余，通過(guò)特征聚類(lèi)讓較為相關(guān)的特征聚在同一個(gè)簇中，這樣再?gòu)牟煌拇刂蟹謩e挑選特征，就能很好地改善特征冗余帶來(lái)的負(fù)面影響，從而提高預(yù)測(cè)性能。與HFSNFP、FSCR、FSDNP方法相比，Pearson系數(shù)僅能衡量特征間的線(xiàn)性關(guān)系，MIC-TSFS方法采用最大信息系數(shù)，不僅可以描述線(xiàn)性關(guān)系，還可以很好地描述非線(xiàn)性、非函數(shù)關(guān)系等依賴(lài)關(guān)系，能夠挖掘特征間以及特征與軟件缺陷數(shù)目間更多的依賴(lài)關(guān)系。

從特征間的冗余性角度，MIC-TSFS方法能夠更為公平地刪除更多的冗余特征，使得特征間的冗余性進(jìn)一步降低。從特征與軟件缺陷數(shù)目間的相關(guān)性角度，MIC-TSFS方法能夠最大限度地保留與軟件缺陷數(shù)目相關(guān)的、更有區(qū)分能力的特征，也可以避免特征與軟件缺陷數(shù)目的相關(guān)性評(píng)價(jià)的偏置。由此，MIC-TSFS 方法選擇的特征對(duì)軟件缺陷數(shù)目的識(shí)別能力更強(qiáng)，且冗余度低，因此預(yù)測(cè)準(zhǔn)確率有所提升。

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

本文提出一種基于最大信息系數(shù)的軟件數(shù)目預(yù)測(cè)特征選擇方法MIC-TSFS，用于刪除冗余特征和不相關(guān)特征。在PROMISE公開(kāi)數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明MIC-TSFS能夠有效地刪除冗余特征和不相關(guān)特征，可以提高軟件缺陷數(shù)目預(yù)測(cè)模型的預(yù)測(cè)精度。但該方法仍有一些后續(xù)工作值得擴(kuò)展，包括：在冗余性分析階段，探討聚類(lèi)中止條件的設(shè)置對(duì)MIC-TSFS方法是否存在影響；在相關(guān)性分析階段，研究獲取的特征數(shù)最優(yōu)值的方法；討論數(shù)據(jù)不平衡率對(duì)預(yù)測(cè)結(jié)果所產(chǎn)生的影響，并結(jié)合smote過(guò)采樣方法、代價(jià)敏感等不平衡處理方法，進(jìn)一步提高模型預(yù)測(cè)性能。此外，實(shí)驗(yàn)中MIC-TSFS方法僅應(yīng)用于中小型項(xiàng)目（程序模塊在1 000以?xún)?nèi)），討論其在大型程序項(xiàng)目中的實(shí)際應(yīng)用效果是下一步工作的重點(diǎn)。