陳 翔，沈宇翔，孟少卿，崔展齊，鞠小林，王 贊

1.南通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南通 226019

2.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

3.天津大學(xué) 信息與網(wǎng)絡(luò)中心，天津 300072

4.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101

5.天津大學(xué) 軟件學(xué)院，天津 300072

1 引言

開發(fā)人員在編碼過程中經(jīng)常會(huì)在無意中引入軟件缺陷。缺陷產(chǎn)生的原因可能來自于對(duì)實(shí)際需求的錯(cuò)誤理解、不合理的開發(fā)過程或開發(fā)人員的經(jīng)驗(yàn)不足等。含有缺陷的軟件在部署后可能會(huì)產(chǎn)生預(yù)期之外的行為，嚴(yán)重的時(shí)候甚至?xí)o企業(yè)造成巨大的經(jīng)濟(jì)損失。因此項(xiàng)目經(jīng)理希望借助軟件測(cè)試和代碼審查等手段，能夠盡可能多地檢測(cè)出被測(cè)項(xiàng)目內(nèi)的嚴(yán)重缺陷。然而實(shí)際的軟件測(cè)試資源是有限的，因此項(xiàng)目經(jīng)理希望能夠找到有效的方法可以預(yù)先識(shí)別出可能含有缺陷的程序模塊，并對(duì)其投入足夠的測(cè)試資源（例如針對(duì)這些模塊設(shè)計(jì)更多的測(cè)試用例或進(jìn)行更為嚴(yán)格的代碼審查）。軟件缺陷預(yù)測(cè)（software defect prediction）[1-3]是其中一種有效方法，通過挖掘軟件歷史倉庫（例如版本控制系統(tǒng)、缺陷跟蹤系統(tǒng)或開發(fā)人員間的電子郵件等）來構(gòu)建缺陷預(yù)測(cè)模型，并用該模型來預(yù)測(cè)出被測(cè)項(xiàng)目內(nèi)的可疑程序模塊。

為了更好地進(jìn)行缺陷預(yù)測(cè)，研究人員提出了很多與缺陷具有強(qiáng)相關(guān)性的度量元（metrics）來對(duì)程序模塊進(jìn)行度量。這些度量元一般通過分析代碼復(fù)雜度和軟件開發(fā)過程特征來進(jìn)行設(shè)計(jì)。從數(shù)據(jù)挖掘的角度來看，度量元也可以被視為是數(shù)據(jù)集的特征。但一般來說，并不是所有的特征都有助于構(gòu)建高質(zhì)量的模型。具體來說，冗余特征和無關(guān)特征的存在會(huì)提高模型的構(gòu)建時(shí)間，甚至有時(shí)會(huì)降低模型的預(yù)測(cè)效果。該問題又被稱為維數(shù)災(zāi)難問題。因此設(shè)計(jì)出新穎有效的特征選擇方法具有重要的研究意義和價(jià)值。除此之外，更少的特征還有助于提高模型的可解釋性和模型的可視化。

Harman等人[4-5]認(rèn)為基于搜索的軟件工程方法（尤其是多目標(biāo)優(yōu)化方法）可以在軟件工作量估算、軟件缺陷預(yù)測(cè)或性能預(yù)測(cè)等研究問題上取得成功。雖然近些年來研究人員嘗試將特征選擇應(yīng)用于軟件缺陷預(yù)測(cè)領(lǐng)域并取得了一些研究成果[6-15]，但是研究人員考慮的特征選擇方法都是基于單目標(biāo)優(yōu)化的，目前尚未有研究人員將軟件缺陷預(yù)測(cè)特征選擇問題建模為多目標(biāo)優(yōu)化問題并展開深入研究，因此本文從這個(gè)角度入手嘗試提高缺陷預(yù)測(cè)模型的預(yù)測(cè)效果，具體來說，主要考慮兩個(gè)優(yōu)化目標(biāo)，一個(gè)目標(biāo)從成本分析角度出發(fā)，嘗試最小化選出的特征數(shù)；另一個(gè)目標(biāo)從收益分析角度出發(fā)，嘗試最大化缺陷預(yù)測(cè)模型的預(yù)測(cè)效果。隨后本文提出了MOFES（multiobjective optimization feature selection）方法來平衡這兩個(gè)潛在矛盾優(yōu)化目標(biāo)。為了驗(yàn)證本文所提方法的有效性，選擇了來自實(shí)際開源項(xiàng)目的PROMISE和RELINK數(shù)據(jù)集作為評(píng)測(cè)對(duì)象，使用k近鄰法來構(gòu)建模型，使用AUC評(píng)測(cè)指標(biāo)來度量模型的預(yù)測(cè)效果。與一些經(jīng)典的基準(zhǔn)方法（例如FULL、SOFS、GFS和GBS）進(jìn)行對(duì)比，發(fā)現(xiàn)：（1）在大部分情況下，MOFES方法可以更為有效地探索搜索空間，最終可以選出規(guī)模更小的特征子集，并且同時(shí)可以獲取更好的預(yù)測(cè)效果。（2）MOFES的計(jì)算開銷要超過GFS方法和GBS方法，但要少于SOFS方法，總體來看，MOFES方法的計(jì)算開銷在可接受的范圍之內(nèi)。

本文的主要貢獻(xiàn)總結(jié)如下：

（1）將軟件缺陷預(yù)測(cè)特征選擇問題建模為多目標(biāo)優(yōu)化問題，提出一種基于多目標(biāo)優(yōu)化的包裹式軟件缺陷預(yù)測(cè)特征選擇方法MOFES，其嘗試最小化選出的特征數(shù)及最大化構(gòu)建出的缺陷預(yù)測(cè)模型性能。

（2）在來自實(shí)際開源項(xiàng)目的兩組數(shù)據(jù)集上進(jìn)行實(shí)證研究，來驗(yàn)證MOFES方法的有效性。這兩組數(shù)據(jù)集考慮的度量元和分析的開源項(xiàng)目均不相同，因此可以確保實(shí)證研究結(jié)論具有一般性。最終結(jié)果表明多目標(biāo)優(yōu)化方法在軟件缺陷預(yù)測(cè)特征選擇問題上具有一定的優(yōu)勢(shì)。

2 研究背景和相關(guān)工作

軟件缺陷預(yù)測(cè)[1-3,16-18]是當(dāng)前軟件工程數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)研究熱點(diǎn)。其主要包含兩個(gè)階段：模型構(gòu)建階段和模型應(yīng)用階段[3]。具體來說，模型構(gòu)建階段會(huì)首先挖掘軟件歷史倉庫來抽取程序模塊并對(duì)其進(jìn)行標(biāo)記（即標(biāo)記為有缺陷模塊或無缺陷模塊）。其中程序模塊粒度可根據(jù)實(shí)際需要，將其設(shè)置為文件、類或代碼修改等。隨后通過分析代碼復(fù)雜度或軟件開發(fā)過程，設(shè)計(jì)出與缺陷存在相關(guān)性的度量元來對(duì)抽取出的模塊進(jìn)行度量?；谏鲜霾襟E，可以構(gòu)造出缺陷預(yù)測(cè)數(shù)據(jù)集并選擇特定的分類器（例如決策樹、k近鄰法等）來構(gòu)建出缺陷預(yù)測(cè)模型。在模型應(yīng)用階段，可以使用構(gòu)建出的模型來預(yù)測(cè)出被測(cè)項(xiàng)目內(nèi)的可疑缺陷模塊。具體過程如圖1所示。

若考慮多種度量元，則搜集的缺陷預(yù)測(cè)數(shù)據(jù)集內(nèi)可能會(huì)存在維數(shù)災(zāi)難問題[11-13]。假設(shè)數(shù)據(jù)集含有n個(gè)特征，則所有可能的特征子集數(shù)為2n。因此當(dāng)n值增大時(shí)，其搜索空間規(guī)模將呈指數(shù)級(jí)增長。其次特征之間的交互關(guān)系較為復(fù)雜，例如：一個(gè)特征可能跟類標(biāo)之間的相關(guān)度不高，但如果與其他具有互補(bǔ)關(guān)系的特征相結(jié)合構(gòu)成特征子集，則可能會(huì)提高隨后構(gòu)建的模型性能。或者一個(gè)特征可能跟類標(biāo)之間的相關(guān)度很高，但如果與其他特征相結(jié)合構(gòu)成特征子集，則該特征可能會(huì)成為冗余特征。特征選擇是緩解維數(shù)災(zāi)難問題的一種有效方法，其嘗試盡可能多地識(shí)別并移除已有特征集中的無關(guān)特征和冗余特征。其中無關(guān)特征與類標(biāo)的相關(guān)性較低，而冗余特征則會(huì)含有其他特征含有的信息。已有的特征選擇方法可以簡單分為兩類：包裹式方法和過濾式方法。其中包裹式方法需要借助指定的建模方法來評(píng)估選出的特征子集的質(zhì)量，而過濾式方法則僅借助數(shù)據(jù)集的特征來評(píng)估選出的特征子集的質(zhì)量。因此后一類方法的計(jì)算開銷較小，但預(yù)測(cè)效果難以保障[19]。

Fig.1 Process of software defect prediction圖1 軟件缺陷預(yù)測(cè)流程

近些年來，研究人員嘗試借助特征選擇來提高缺陷預(yù)測(cè)模型的性能。大部分研究人員考慮的是過濾式方法。Menzies等人[6]考慮了基于信息增益的特征選擇方法，主要考慮了前向搜索和窮盡搜索策略。Gao等人[7]在大規(guī)模遺留軟件系統(tǒng)上考慮了特征選擇方法，他們考慮了不同的特征排序和子集評(píng)估策略。Wang等人[8]借助集成學(xué)習(xí)來提高特征選擇的性能。Liu等人[11]提出一種基于特征聚類和特征排序的特征選擇框架FECAR，隨后Liu等人[12]提出一種兩階段數(shù)據(jù)集預(yù)處理方法，其同時(shí)考慮了特征選擇和實(shí)例選擇。最后發(fā)現(xiàn)數(shù)據(jù)集中的噪音是難以徹底移除的，因此Liu等人[13]提出具有一定噪音容忍能力的特征選擇框架FECS。與FECAR相似，Xu等人[14]同樣提出一種基于聚類分析的特征選擇方法MICHAC（defect prediction via maximal information coefficient with hierarchical agglomerative clustering）。Shivaji等人[10]在基于代碼修改的缺陷預(yù)測(cè)[20]中考慮了不同的特征選擇方法?？紤]包裹式特征選擇方法的研究工作相對(duì)較少，Song等人[9]在他們的通用缺陷預(yù)測(cè)框架中考慮了包裹式特征選擇方法。Xu等人[15]分析了32種不同的特征選擇方法，這些方法被分為5類（過濾式特征排序方法、過濾式子集選擇方法、包裹式子集選擇方法、基于聚類的方法、基于抽取的方法）。在大規(guī)模實(shí)證研究中，他們發(fā)現(xiàn)在不同數(shù)據(jù)集上，不同方法之間基于預(yù)測(cè)效果的排序并不一致。

基于相關(guān)工作分析發(fā)現(xiàn)雖然研究人員對(duì)軟件缺陷預(yù)測(cè)特征選擇的研究已經(jīng)取得了一定的研究進(jìn)展，但并未有研究人員將該問題建模為多目標(biāo)優(yōu)化問題。雖然Canfora等人[21]曾經(jīng)將多目標(biāo)優(yōu)化應(yīng)用到軟件缺陷預(yù)測(cè)中，但本文工作與他們工作的不同之處有兩點(diǎn)：首先關(guān)注的問題不同，Canfora等人關(guān)注的是跨項(xiàng)目缺陷預(yù)測(cè)問題，重點(diǎn)關(guān)注的是缺陷預(yù)測(cè)特征選擇問題。其次關(guān)注的優(yōu)化目標(biāo)不同，他們嘗試借助多目標(biāo)優(yōu)化方法在識(shí)別出的缺陷模塊數(shù)和需要的代碼審查量之間進(jìn)行折衷選擇。而本文嘗試借助多目標(biāo)優(yōu)化方法在選出的特征子集規(guī)模和隨后構(gòu)建出的缺陷預(yù)測(cè)模型性能之間進(jìn)行折衷選擇。

3 MOFES方法

本文屬于基于搜索的軟件工程（search based software engineering，SBSE）[4]研究領(lǐng)域。SBSE的概念最早由Mark Harman提出并逐漸成為軟件工程領(lǐng)域的一個(gè)研究熱點(diǎn)。目前已經(jīng)逐漸應(yīng)用到軟件開發(fā)生命周期的各個(gè)階段，從需求分析、軟件設(shè)計(jì)、軟件測(cè)試到軟件維護(hù)等。SBSE之所以受到很多研究人員的關(guān)注，是因?yàn)槠涮峁┝俗詣?dòng)化或半自動(dòng)化的解決方案，有助于在擁有大規(guī)模搜索空間的復(fù)雜軟件工程問題中找到高質(zhì)量解。Harman[5]同樣認(rèn)為SBSE（尤其是多目標(biāo)優(yōu)化方法）可以用于輔助構(gòu)建高質(zhì)量的缺陷預(yù)測(cè)模型。

針對(duì)軟件缺陷預(yù)測(cè)特征選擇問題，定義了兩個(gè)優(yōu)化目標(biāo)，其中一個(gè)優(yōu)化目標(biāo)從問題的成本角度出發(fā)，希望能夠盡可能減少需要選出的特征數(shù)，另一個(gè)優(yōu)化目標(biāo)從問題的收益角度出發(fā)，希望能夠盡可能多地提高缺陷預(yù)測(cè)模型的預(yù)測(cè)效果。不難看出，大部分情況下這兩種優(yōu)化目標(biāo)存在明顯的矛盾。具體來說，若希望選出的特征數(shù)越少，則可能會(huì)降低隨后構(gòu)建出的模型預(yù)測(cè)效果。相反若希望提高隨后構(gòu)建出的模型預(yù)測(cè)效果，則可能需要選出更多的特征。因此希望借助多目標(biāo)優(yōu)化方法在這兩個(gè)潛在矛盾的優(yōu)化目標(biāo)中進(jìn)行折衷，并設(shè)計(jì)出MOFES方法。借助該方法，可以獲得一系列具有非支配關(guān)系的特征子集，并且可以根據(jù)偏好（例如傾向于選出更少的特征數(shù)或傾向于構(gòu)造出更高預(yù)測(cè)效果的模型）從中選出實(shí)際需要的特征子集。

為了方便隨后的描述，首先給出與多目標(biāo)優(yōu)化相關(guān)的定義。

定義1（Pareto支配關(guān)系）假設(shè)wi和wj是缺陷預(yù)測(cè)特征選擇問題的兩個(gè)可行解，稱wiPareto支配wj，當(dāng)且僅當(dāng)：

在該問題中，可行解表示某個(gè)特征子集，benefit函數(shù)返回使用該特征子集后構(gòu)建出的模型預(yù)測(cè)效果，cost函數(shù)返回的是該特征子集的規(guī)模。

定義2（Pareto最優(yōu)解）一個(gè)可行解w是Pareto最優(yōu)解，當(dāng)且僅當(dāng)不存在任何可行解w*，可以Pareto支配w。

定義3（Pareto最優(yōu)解集）該集合包含可行解中所有的Pareto最優(yōu)解。

使用一個(gè)虛擬實(shí)例來闡述上述定義。假設(shè)MOFES方法生成了7個(gè)可行解，如圖2所示。其中x坐標(biāo)軸表示可行解對(duì)應(yīng)的特征數(shù)（即cost目標(biāo)），y坐標(biāo)軸表示可行解基于選定特征構(gòu)建出的模型預(yù)測(cè)性能（即benefit目標(biāo)）。不難看出可行解BPareto支配可行解E，因?yàn)閎enefit(B)＞benefit(E)并且cost(B)≤cost(E)。同時(shí)可行解A、B、C和D均是Pareto最優(yōu)解并構(gòu)成了Pareto最優(yōu)解集，在圖2中，不存在其他可行解，可以Pareto支配這些解。

Fig.2 Interpretation for definitions in multi-objective optimization圖2 對(duì)多目標(biāo)優(yōu)化中定義的解釋

研究人員提出了多種不同的演化多目標(biāo)優(yōu)化算法，這些算法借助演化算法來嘗試構(gòu)造出Pareto最優(yōu)解集。本文提出的MOFES主要基于一種經(jīng)典的演化多目標(biāo)優(yōu)化算法NSGA-Ⅱ[22]，NSGA-II算法在每次種群演化時(shí)，首先借助演化算子生成新的染色體，隨后將這些染色體與上一輪種群的染色體合并，接著進(jìn)行基于分層的快速非支配排序，同時(shí)對(duì)于每個(gè)非支配層中的染色體進(jìn)行擁擠度計(jì)算，最后根據(jù)非支配關(guān)系以及染色體的擁擠度，選擇合適的染色體組成新的種群。其中基于分層的非支配排序、擁擠度計(jì)算以及精英保留機(jī)制均可以有效避免種群的過早收斂問題。其整體框架如算法1所示。

算法1MOFES

輸入：種群規(guī)模N，最大迭代次數(shù)T。

輸出：Pareto最優(yōu)解集。

首先介紹染色體的編碼方案，針對(duì)該問題，若數(shù)據(jù)集有n個(gè)特征，則染色體可以用n比特串來表示。假如第i個(gè)比特取值為1，則表示對(duì)應(yīng)的第i個(gè)特征被選入，若取值為0，則表示對(duì)應(yīng)的第i個(gè)特征未被選入。假設(shè)數(shù)據(jù)集考慮了5個(gè)特征{f1,f2,f3,f4,f5}，并且初始種群為{10010,00100,10110}。這表明該初始種群包含3個(gè)染色體，其對(duì)應(yīng)的特征子集分別為{f1,f4}、{f3}和{f1,f3,f4}。

算法1首先使用步驟2中的initPop函數(shù)來初始化種群，其中種群規(guī)模為N，種群中每個(gè)染色體隨機(jī)生成。針對(duì)軟件缺陷預(yù)測(cè)特征選擇問題，有3種啟發(fā)式種群初始化策略：small初始化策略、large初始化策略和hybrid初始化策略。其中在small初始化策略中，種群中的每個(gè)染色體隨機(jī)選出的特征數(shù)小于原有特征數(shù)的一半。在large初始化策略中，種群中的每個(gè)染色體隨機(jī)選出的特征數(shù)大于原有特征數(shù)的一半。在hybrid初始化策略中，一半的染色體采用small初始化策略，另一半染色體使用large初始化策略。在MOFES方法中small初始化策略更為有效。

隨后MOFES在步驟4中使用makeNewPop函數(shù)，借助演化算子（例如交叉算子、變異算子）來生成新的染色體。具體來說，交叉算子會(huì)根據(jù)交叉概率隨機(jī)選出兩個(gè)染色體，進(jìn)行交叉并生成兩個(gè)新的染色體，變異算子會(huì)根據(jù)變異概率隨機(jī)選出一個(gè)染色體，進(jìn)行變異并生成一個(gè)新的染色體。

接著MOFES通過步驟5到步驟16，借助選擇算子從已有染色體中選出更高質(zhì)量（基于Pareto支配關(guān)系分析）的染色體到下一輪種群中。具體來說，首先將原有的染色體和借助變異算子和交叉算子生成的新染色體合并到集合Bi中。然后使用fastNondominated-Sort函數(shù)來為Bi中的每個(gè)染色體算出NDR（nondominated rank）值。具體來說，首先從Bi中識(shí)別出所有不被Pareto支配的染色體，將他們的NDR值設(shè)置為1，并將它們從集合Bi中移到集合F1。隨后繼續(xù)從Bi中識(shí)別出所有不被Pareto支配的染色體，將它們的NDR值設(shè)置為2，并將它們從集合Bi中移到集合F2。重復(fù)執(zhí)行上述過程，直至集合Bi為空?；谌旧w的NDR值，會(huì)盡力選擇NDR值更小的染色體到下一輪種群中。在步驟14中，使用了擁擠距離（crowding distance）[21]的概念，通過擁擠距離可以避免選出具有高相似度的染色體。

當(dāng)達(dá)到最大迭代次數(shù)后，MOFES方法滿足終止條件并返回當(dāng)前種群中的所有Pareto最優(yōu)解。

4 實(shí)證研究

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

為了驗(yàn)證MOFES方法的有效性，本文選擇了PROMISE和RELINK數(shù)據(jù)集作為評(píng)測(cè)對(duì)象。這些數(shù)據(jù)集中共涉及了13個(gè)開源項(xiàng)目，累計(jì)共有5 757個(gè)程序模塊。這些開源項(xiàng)目處于不同類型領(lǐng)域，例如Ant是Java程序的構(gòu)建程序，Lucene是搜索引擎工具包。除此之外，這兩個(gè)數(shù)據(jù)集也分別考慮了不同類型的度量元。因此不難看出，本文選擇的評(píng)測(cè)對(duì)象具有一定的代表性。

PROMISE數(shù)據(jù)集由Jureczko和Madeyski[23]搜集完成，其主要來自10個(gè)不同的開源項(xiàng)目（例如Ant、Lucene、Poi等）。他們將程序模塊的粒度設(shè)置為類，并考慮了20種度量元，這些度量元考慮了面向?qū)ο蟪绦蛑械姆庋b、繼承和多態(tài)等特征。PROMISE數(shù)據(jù)集的統(tǒng)計(jì)信息（包括項(xiàng)目名稱、模塊粒度、模塊數(shù)以及缺陷模塊數(shù)）如表1所示。

RELINK數(shù)據(jù)集由Wu等人[24]搜集，他們分析的開源項(xiàng)目是Apache HTTPServer、Safe和ZXing。該數(shù)據(jù)集共考慮了26種度量元，這些度量元均關(guān)注的是代碼復(fù)雜度，并借助Understand工具進(jìn)行搜集。他們隨后通過手工驗(yàn)證和校對(duì)等方式進(jìn)一步提高了數(shù)據(jù)集的質(zhì)量。RELINK數(shù)據(jù)集的統(tǒng)計(jì)信息（包括項(xiàng)目名稱、模塊粒度、模塊數(shù)以及缺陷模塊數(shù)）如表2所示。

4.2 模型預(yù)測(cè)效果評(píng)測(cè)指標(biāo)

本文使用AUC（area under the ROC curve）指標(biāo)來評(píng)估缺陷預(yù)測(cè)模型的預(yù)測(cè)效果。其中AUC值為ROC曲線下的面積，其取值越接近于1，表示對(duì)應(yīng)的模型的預(yù)測(cè)效果越好。使用ROC曲線可以考慮不同的閾值，其中水平坐標(biāo)軸表示TPR（true positive rate）值，垂直坐標(biāo)軸表示FPR（false positive rate）值。根據(jù)不同的閾值，模型會(huì)具有不同的TPR值和FPR值并對(duì)應(yīng)為坐標(biāo)上的一個(gè)點(diǎn)，將所有點(diǎn)進(jìn)行連接就可以形成ROC曲線。因此與傳統(tǒng)查準(zhǔn)率、查全率、F1指標(biāo)相比，AUC指標(biāo)更適用于具有類不平衡問題的軟件缺陷預(yù)測(cè)研究[15]。

Table 1 Characteristics of PROMISE datasets表1PROMISE數(shù)據(jù)集的統(tǒng)計(jì)信息

Table 2 Characteristics of RELINK datasets表2RELINK數(shù)據(jù)集的統(tǒng)計(jì)信息

4.3 實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證MOFES方法的有效性，考慮了4種基準(zhǔn)方法。

（1）第1種基準(zhǔn)方法不進(jìn)行特征選擇，即使用原有的特征來構(gòu)建模型，本文將該方法稱為FULL方法。

（2）第2種基準(zhǔn)方法是基于單目標(biāo)優(yōu)化的包裹式特征選擇方法，與MOFES不同之處在于該方法僅優(yōu)化單一目標(biāo)（即模型的預(yù)測(cè)效果）。本文將該方法稱為SOFS方法。

（3）第3種基準(zhǔn)方法和第4種基準(zhǔn)方法是基于貪心前向搜索和貪心后向搜索的包裹式特征選擇方法。本文將這兩種方法分別稱為GFS方法和GBS方法。Song等人[9]在他們提出的通用軟件缺陷預(yù)測(cè)框架中考慮了這兩種特征選擇方法。具體來說，GFS方法會(huì)從空集開始（即不包含任何特征），借助爬山法每次添加一個(gè)最優(yōu)特征，直至模型的預(yù)測(cè)效果不能得到提升為止。GBS方法會(huì)從原有特征集開始，借助爬山法每次移除一個(gè)特征，直至模型的預(yù)測(cè)效果不能得到提升為止。上述兩種方法均存在嵌套效應(yīng)，即一旦一個(gè)特征被添加（或移除），其在后續(xù)迭代過程中，就不會(huì)被移除（或添加），該問題會(huì)使得這兩種方法在搜索時(shí)容易陷入局部最優(yōu)。

這里需要注意的是本文重點(diǎn)研究的是包裹式特征選擇方法，因此在選擇基準(zhǔn)方法的時(shí)候并未考慮在相關(guān)工作中提到的過濾式特征選擇方法。

當(dāng)完成特征選擇后，使用k近鄰法來構(gòu)建缺陷預(yù)測(cè)模型。k近鄰法的建模質(zhì)量與選出的特征質(zhì)量密切相關(guān)，選出更好的特征將有助于更為精準(zhǔn)地計(jì)算出程序模塊間的相似度，從而更好完成對(duì)軟件模塊的缺陷預(yù)測(cè)?；谔卣鬟x擇的模型性能評(píng)估過程如圖3所示：首先使用分層采樣來分別構(gòu)建訓(xùn)練集和測(cè)試集，即選擇70%的實(shí)例來構(gòu)成訓(xùn)練集，而用剩余30%的實(shí)例來構(gòu)成測(cè)試集，借助分層采樣可以保證訓(xùn)練集和測(cè)試集中不同類型的實(shí)例分布保持一致。在測(cè)試集上借助MOFES方法生成Pareto最優(yōu)解集，對(duì)于集合中的每個(gè)Pareto最優(yōu)解，會(huì)根據(jù)其選中的特征子集同時(shí)對(duì)訓(xùn)練集和測(cè)試集進(jìn)行數(shù)據(jù)預(yù)處理，在預(yù)處理后的訓(xùn)練集上借助k近鄰法構(gòu)建模型，并將模型應(yīng)用于測(cè)試集上并得到該特征子集對(duì)應(yīng)的模型預(yù)測(cè)效果。為了在測(cè)試集上評(píng)估每個(gè)染色體（即特征子集）的適應(yīng)值，進(jìn)一步在測(cè)試集上使用3折交叉驗(yàn)證，即首先將測(cè)試集上的數(shù)據(jù)借助分層采樣方法將之劃分為3組，每次用兩組數(shù)據(jù)根據(jù)染色體對(duì)應(yīng)的特征子集進(jìn)行數(shù)據(jù)預(yù)處理，借助k近鄰法構(gòu)建模型，并用剩余1組的數(shù)據(jù)來評(píng)估該模型的性能，重復(fù)3次（即確保每個(gè)實(shí)例都被預(yù)測(cè)過1次），并取這3次性能的均值作為該染色體的適應(yīng)值。

Fig.3 Process of model performance evaluation圖3 模型預(yù)測(cè)效果的評(píng)估過程

MOFES方法和SOFS方法中的參數(shù)名稱和具體取值如表3所示，包括種群規(guī)模、最大迭代次數(shù)、交叉概率和變異概率。增加最大迭代次數(shù)可能會(huì)選出質(zhì)量更高的特征子集，并提高隨后構(gòu)建出的模型預(yù)測(cè)效果，但也會(huì)大幅度提高特征選擇方法的執(zhí)行時(shí)間開銷。在實(shí)證研究中，根據(jù)實(shí)際執(zhí)行效果和多目標(biāo)優(yōu)化算法在數(shù)值問題求解中的建議取值[25]確定了表3所示的參數(shù)取值。

Table 3 Name of parameters and their value used in MOFES表3 MOFES方法中使用的參數(shù)名稱和取值

MOFES方法和所有基準(zhǔn)方法均借助Weka軟件包編程實(shí)現(xiàn)，并統(tǒng)一運(yùn)行在Win 10操作系統(tǒng)（Intel i7-3612QM CPU，8 GB內(nèi)存）。

4.4 結(jié)果分析

4.4.1 模型預(yù)測(cè)效果比較

本節(jié)主要從模型預(yù)測(cè)效果角度將MOFES方法與基準(zhǔn)方法進(jìn)行比較。由于MOFES方法和一些基準(zhǔn)方法內(nèi)存在隨機(jī)因素，因此獨(dú)立運(yùn)行這些方法10次?；赑ROMISE和RELINK數(shù)據(jù)集的結(jié)果分別如圖4和圖5所示。在每個(gè)子圖中，項(xiàng)目名稱后的括號(hào)內(nèi)包含原有特征數(shù)以及未進(jìn)行特征選擇（即使用FULL方法）時(shí)構(gòu)建的模型預(yù)測(cè)效果。例如：Camel-1.6后括號(hào)內(nèi)的內(nèi)容為（20，0.6），這表示原有的特征數(shù)為20，未進(jìn)行特征選擇時(shí)的模型預(yù)測(cè)效果為0.6（基于AUC評(píng)測(cè)指標(biāo)）。在每個(gè)子圖中，橫坐標(biāo)表示不同方法選出的特征數(shù)，縱坐標(biāo)表示使用該特征子集構(gòu)建出的模型預(yù)測(cè)效果。SOFS、GFS和GBS均會(huì)獨(dú)立執(zhí)行10次，但可能會(huì)在不同執(zhí)行過程中選出相同的特征子集，因此在一些子圖中可能會(huì)出現(xiàn)實(shí)際點(diǎn)的數(shù)量少于10的情況。除此之外，MOFES方法基于測(cè)試集上的執(zhí)行結(jié)果也會(huì)產(chǎn)生10個(gè)不同的Pareto最優(yōu)解集。用兩種方式表示MOFES方法的執(zhí)行結(jié)果。首先將這10個(gè)不同Pareto最優(yōu)解集中的解合并到一個(gè)集合T，第一種方式將集合T中具有相同特征子集規(guī)模的解合并到同一組，并計(jì)算出模型性能的均值（因?yàn)橄嗤奶卣髯蛹?guī)模并不一定代表選出相同的特征），其用MOFES-A折線表示。第二種方式會(huì)從T中進(jìn)一步找出Pareto最優(yōu)解集并返回，其用MOFES-B折線表示。

首先將MOFES、SOFS、GFS和GBS這4種方法與FULL方法進(jìn)行比較，通過2個(gè)數(shù)據(jù)集的13個(gè)項(xiàng)目發(fā)現(xiàn)借助特征選擇，總存在一些方法可以找出一些特征子集，其隨后構(gòu)建出的模型預(yù)測(cè)效果要優(yōu)于使用原有特征集構(gòu)建的模型預(yù)測(cè)效果。以Camel-1.6為例，其使用原有特征集構(gòu)建出的模型預(yù)測(cè)效果為0.604（基于AUC評(píng)測(cè)指標(biāo)）。借助GBS方法，其最好的結(jié)果是通過選出17個(gè)特征，其模型預(yù)測(cè)效果可達(dá)到0.647。借助GFS方法，其最好的結(jié)果是通過選出6個(gè)特征，其模型預(yù)測(cè)效果可達(dá)到0.66。借助SOFS方法，其最好的結(jié)果是通過選出10個(gè)特征，其模型預(yù)測(cè)效果可達(dá)到0.677。而本文所提的MOFES方法，其最好的結(jié)果是通過選出4個(gè)特征，其模型預(yù)測(cè)效果可達(dá)到0.711。這些結(jié)果均超過0.604。同時(shí)MOFES方法在這個(gè)項(xiàng)目中可以選出更少的特征，并達(dá)到最好的預(yù)測(cè)效果。

其次分析MOFES、SOFS、GFS和GBS這4種方法選出的特征數(shù)，不難看出GFS方法選出的特征子集規(guī)模最小，GBS方法選出的特征子集規(guī)模更大，SOFS選出的特征子集規(guī)模介于兩者之間，而本文所提的MOFES方法，由于每次返回的是Pareto最優(yōu)解集，其選出的特征子集規(guī)模分布較廣，因此在選擇的時(shí)候具有更強(qiáng)的靈活性。

Fig.4 Prediction performance comparison of different methods for PROMISE datasets圖4 不同特征選擇方法在PROMISE數(shù)據(jù)集上的結(jié)果

接著給出MOFES、SOFS、GFS和GBS這4種方法在10次獨(dú)立執(zhí)行后可以取得的最好模型預(yù)測(cè)效果。其中基于PROMISE數(shù)據(jù)集的結(jié)果如表4所示，基于RELINK數(shù)據(jù)集的結(jié)果如表5所示，其中括號(hào)內(nèi)表示對(duì)應(yīng)選出的特征子集規(guī)模，對(duì)每個(gè)項(xiàng)目上的最好結(jié)果進(jìn)行了加粗，每個(gè)表的最后一行顯示的是在數(shù)據(jù)集所有項(xiàng)目上的均值。不難看出，除了在Ant-1.7和Xerces-1.4，MOFES總能獲得最好的預(yù)測(cè)效果。進(jìn)一步將MOFES方法與單目標(biāo)特征選擇方法SOFS進(jìn)行對(duì)比，MOFES方法在大部分情況下，可以在獲得更好的預(yù)測(cè)效果時(shí)，選出的特征數(shù)更少（除了Xalan-2.6、Xerces-1.4和 ZXing）?？傮w來說，基于PROMISE數(shù)據(jù)集的均值分析，MOFES相對(duì)SOFS、GFS和GBS來講，其模型預(yù)測(cè)效果分別有3.37%、4.16%和5.35%的提升?；赗ELINK數(shù)據(jù)集的均值分析，MOFES相對(duì)SOFS、GFS和GBS來講，其模型預(yù)測(cè)效果分別有5.19%、4.50%和9.27%的提升。

Fig.5 Prediction performance comparison of different methods for RELINK datasets圖5 不同特征選擇方法在RELINK數(shù)據(jù)集上的結(jié)果

Table 4 Best result of different methods for PROMISE datasets表4 不同特征選擇方法在PROMISE數(shù)據(jù)集上的最好結(jié)果

因此與單目標(biāo)優(yōu)化方法相比，借助多目標(biāo)優(yōu)化方法可以更為有效地探索搜索空間，并找出質(zhì)量更高的特征子集。除此之外基于圖4和圖5中的MOFES-B，在選出的特征數(shù)和模型的預(yù)測(cè)效果上存在明顯的折衷，這也驗(yàn)證了這兩個(gè)優(yōu)化目標(biāo)存在一定的沖突性。以Ant-1.7為例，其MOFES-B折線對(duì)應(yīng)4個(gè)解，分別是解A（1，0.672）、解B（2，0.758）、解C（3，0.763）和解D（6，0.766）。不難看出這4個(gè)解構(gòu)成了Pareto最優(yōu)解集。若選擇特征數(shù)較少的解（例如解A），其隨后構(gòu)建的模型預(yù)測(cè)效果為0.672，要弱于選擇特征數(shù)較多的解（例如解D）隨后構(gòu)建的模型預(yù)測(cè)效果（0.766）。

綜上所述，在兩組數(shù)據(jù)集的13個(gè)項(xiàng)目中，MOFES方法在其中11個(gè)項(xiàng)目上可以選出更高質(zhì)量的特征子集并獲取更好的模型預(yù)測(cè)效果。

4.4.2 執(zhí)行時(shí)間開銷比較

本節(jié)主要將MOFES方法的執(zhí)行時(shí)間開銷與其他基準(zhǔn)方法進(jìn)行比較。搜集了每個(gè)特征選擇方法獨(dú)立運(yùn)行10次的時(shí)間總和。其中基于PROMISE數(shù)據(jù)集的運(yùn)行時(shí)間結(jié)果如表6所示，基于RELINK數(shù)據(jù)集的執(zhí)行時(shí)間結(jié)果如表7所示。基于PROMISE數(shù)據(jù)集，MOFES方法的執(zhí)行時(shí)間是GFS方法的14.13～25.61倍，是GBS方法的4.86～8.82倍，但僅是SOFS方法的0.77～0.85倍?；赗ELINK數(shù)據(jù)集，MOFES方法的執(zhí)行時(shí)間是GFS方法的11.46～12.85倍，是GBS方法的4.47～6.62倍，但僅是SOFS方法的0.81～0.88倍。

Table 6 Computational cost of different methods for PROMISE datasets表6 基于PROMISE數(shù)據(jù)集的運(yùn)行時(shí)間 s

Table 7 Computational cost of different methods for RELINK datasets表7 基于RELINK數(shù)據(jù)集的運(yùn)行時(shí)間 s

綜上所示，MOFES方法運(yùn)行時(shí)間要超過GFS方法和GBS方法，但要少于SOFS方法，并且總體來看其計(jì)算開銷是可接受的。例如在PROMISE數(shù)據(jù)集中，MOFES方法的執(zhí)行時(shí)間最多是1 205.109 s。在RELINK數(shù)據(jù)集中，MOFES方法的執(zhí)行時(shí)間最多是339.022 s。同時(shí)在模型預(yù)測(cè)效果比較時(shí)，MOFES方法雖然需要花費(fèi)一定的時(shí)間進(jìn)行特征選擇，但在大部分情況都能訓(xùn)練出預(yù)測(cè)效果更好的缺陷預(yù)測(cè)模型。

4.4.3 MOFES選出的特征統(tǒng)計(jì)

本節(jié)主要分析MOFES方法經(jīng)常選出的特征，其分析結(jié)果有助于選出最有價(jià)值的特征來指導(dǎo)缺陷預(yù)測(cè)數(shù)據(jù)集的搜集。

由于MOFES方法在每個(gè)數(shù)據(jù)集上均會(huì)獨(dú)立運(yùn)行10次，每次會(huì)獲得一個(gè)Pareto最優(yōu)解集。因此基于10組Pareto最優(yōu)解集，可以算出每個(gè)特征的被選頻率。假設(shè)針對(duì)項(xiàng)目d，其10組Pareto最優(yōu)解集中共含有100個(gè)解，其中60個(gè)解含有特征fi，則特征fi的被選頻率為60%。以PROMISE數(shù)據(jù)集為例，該數(shù)據(jù)集含有10個(gè)項(xiàng)目，因此針對(duì)每個(gè)特征會(huì)有10個(gè)被選頻率，在特征排序時(shí)，首先按照10個(gè)被選頻率的中位數(shù)進(jìn)行排序，若中位數(shù)取值相等，則進(jìn)一步按照均值進(jìn)行排序?；赑ROMISE數(shù)據(jù)集和RELINK數(shù)據(jù)集的最終結(jié)果如表8所示，其特征具體含義可參考對(duì)應(yīng)文獻(xiàn)[22-23]。

4.5 有效性影響因素分析

本節(jié)簡要討論可能影響到實(shí)證研究結(jié)論有效性的一些影響因素。外部有效性主要涉及到實(shí)證研究得到的結(jié)論是否具有一般性。為避免該影響因素，本文選擇了軟件缺陷預(yù)測(cè)研究中經(jīng)常使用的評(píng)測(cè)數(shù)據(jù)集PROMISE和RELINK[18,21,23-24]。這些數(shù)據(jù)集共含有5 757個(gè)程序模塊，涉及到13個(gè)不同類型的開源項(xiàng)目，因此可以確保研究結(jié)論具有一定的代表性。除此之外，本文對(duì)缺陷預(yù)測(cè)研究中使用較多的其他數(shù)據(jù)集（例如NASA、Softlab等）也進(jìn)行了驗(yàn)證并得到了相似結(jié)論。內(nèi)部有效性主要涉及到可能影響到實(shí)證研究結(jié)果正確性的內(nèi)部因素。為避免該影響因素，本文在實(shí)現(xiàn)方法時(shí)主要基于Weka軟件包，因此可以最大程度保證分類器和一些基準(zhǔn)特征選擇方法實(shí)現(xiàn)的正確性，除此之外，還通過一些簡單實(shí)例對(duì)MOFES方法的正確性進(jìn)行了驗(yàn)證。構(gòu)造有效性主要涉及到使用的評(píng)測(cè)指標(biāo)是否合理。因?yàn)閿?shù)據(jù)集內(nèi)存在類不平衡問題，為避免該影響因素，使用了AUC評(píng)測(cè)指標(biāo)。

Table 8 5 features with the highest selected frequency表8 被選頻率最高的5個(gè)特征

5 結(jié)束語

目前多目標(biāo)優(yōu)化在軟件缺陷預(yù)測(cè)問題中的應(yīng)用并不多，本文將軟件缺陷預(yù)測(cè)特征選擇方法建模為多目標(biāo)優(yōu)化問題，并提出了MOFES方法?；趤碜詫?shí)際開源項(xiàng)目的PROMISE數(shù)據(jù)集和RELINK數(shù)據(jù)集驗(yàn)證了MOFES方法的有效性。

在下一步工作中，首先將嘗試基于更多實(shí)際項(xiàng)目（尤其是來自商業(yè)項(xiàng)目）的數(shù)據(jù)集來驗(yàn)證本文所提方法的有效性。其次嘗試考慮其他多目標(biāo)優(yōu)化算法（例如SPEA[26]、基于粒子群優(yōu)化的SMPSO等[27]）來豐富MOFES方法，并采取合適的指標(biāo)（例如hypervolume）來評(píng)估不同多目標(biāo)優(yōu)化算法生成的Pareto最優(yōu)解集的質(zhì)量。接著嘗試考慮更多的分類器（例如決策樹、樸素貝葉斯、集成學(xué)習(xí)等）來分析MOFES方法是否會(huì)受到分類方法的影響。然后嘗試通過尋找最優(yōu)參數(shù)取值以及設(shè)計(jì)更為有效的演化算子來優(yōu)化MOFES方法。最后本文所考慮的PROMISE數(shù)據(jù)集和RELINK數(shù)據(jù)集的度量元介于20～30之間，若研究人員考慮更多的度量元，則本文所提的MOFES方法會(huì)存在計(jì)算開銷過大的問題，這時(shí)候?qū)⑦M(jìn)一步針對(duì)軟件缺陷預(yù)測(cè)特征選擇問題研究基于多目標(biāo)優(yōu)化的過濾式特征選擇方法。