基于多目標優(yōu)化的軟件缺陷預測特征選擇方法*

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

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

2.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林 541004

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

4.北京信息科技大學 計算機學院，北京 100101

5.天津大學 軟件學院，天津 300072

1 引言

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

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

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

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

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

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

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

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

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

Fig.1 Process of software defect prediction圖1 軟件缺陷預測流程

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

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

3 MOFES方法

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

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

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

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

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

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

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

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

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

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

算法1MOFES

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

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

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

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

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

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

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

4 實證研究

4.1 評測對象

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

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

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

4.2 模型預測效果評測指標

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

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

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

4.3 實驗設(shè)計

為驗證MOFES方法的有效性，考慮了4種基準方法。

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

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

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

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

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

Fig.3 Process of model performance evaluation圖3 模型預測效果的評估過程

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

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

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

4.4 結(jié)果分析

4.4.1 模型預測效果比較

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

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

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

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

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

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

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

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

本節(jié)主要將MOFES方法的執(zhí)行時間開銷與其他基準方法進行比較。搜集了每個特征選擇方法獨立運行10次的時間總和。其中基于PROMISE數(shù)據(jù)集的運行時間結(jié)果如表6所示，基于RELINK數(shù)據(jù)集的執(zhí)行時間結(jié)果如表7所示?；赑ROMISE數(shù)據(jù)集，MOFES方法的執(zhí)行時間是GFS方法的14.13～25.61倍，是GBS方法的4.86～8.82倍，但僅是SOFS方法的0.77～0.85倍?；赗ELINK數(shù)據(jù)集，MOFES方法的執(zhí)行時間是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ù)集的運行時間 s

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

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

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

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

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

4.5 有效性影響因素分析

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

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

5 結(jié)束語

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

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