基于組織協(xié)同進化的軟件缺陷預(yù)測方法*

常瑞花

（武警工程大學(xué)科研部，西安 710086）

基于組織協(xié)同進化的軟件缺陷預(yù)測方法*

常瑞花

（武警工程大學(xué)科研部，西安 710086）

針對傳統(tǒng)有標識軟件度量元數(shù)據(jù)存在軟件缺陷預(yù)測精度低的問題，首先對比選擇合適的離散化方法，然后將組織協(xié)同進化分類算法引入并應(yīng)用到航天軟件缺陷預(yù)測領(lǐng)域，給出了一種基于組織協(xié)同進化的軟件缺陷預(yù)測方法。該方法根據(jù)預(yù)測目標將離散后的軟件度量元數(shù)據(jù)劃分為不同種群，在各種群內(nèi)部形成進化個體（組織）。組織在增減算子、交換算子、合并算子和組織選擇機制的作用下不斷進化，并基于屬性重要度協(xié)同進化的方式進行適應(yīng)度函數(shù)的計算，實現(xiàn)了有標識軟件度量元數(shù)據(jù)缺陷預(yù)測精度的提高。最后通過兩組仿真實驗，驗證了基于組織協(xié)同進化航天軟件缺陷預(yù)測方法的有效性。

軟件缺陷，預(yù)測，度量元，協(xié)同進化

0 引言

研究表明普遍存在的軟件缺陷，已成為制約航天軟件可靠性的瓶頸。而當前常用的檢驗、驗證手段往往難以發(fā)現(xiàn)并排除所有的軟件缺陷。為此，軟件缺陷預(yù)測技術(shù)應(yīng)運而生，成為當前國內(nèi)外研究的熱點［1-4］，并相應(yīng)提出了許多軟件缺陷預(yù)測方法，例如，分類回歸樹，決策樹，人工神經(jīng)網(wǎng)絡(luò)等等。然而有標識軟件度量元數(shù)據(jù)的缺陷預(yù)測問題依然沒有得到徹底解決，存在預(yù)測精度不高的問題。

近年來為了提高遺傳算法的性能，興起一個新的研究熱點——協(xié)同進化算法［5］。它與傳統(tǒng)進化算法的區(qū)別在于：協(xié)同進化在進化算法的基礎(chǔ)上，考慮了種群與環(huán)境之間、種群與種群之間在進化過程中的協(xié)調(diào)。由于協(xié)同進化算法的優(yōu)越性，自提出以來便引起了許多學(xué)者的重視，在文本分類、生產(chǎn)調(diào)度等領(lǐng)域［6-8］得到廣泛的應(yīng)用，然而協(xié)同進化算法在軟件缺陷預(yù)測領(lǐng)域中的研究還很少。

文獻［9］提出了組織協(xié)同進化分類（Organizational Co-Evolutionary algorithm for Classification，OCEC）算法，該算法與現(xiàn)有遺傳分類算法的運行機制不同，它從數(shù)據(jù)本身出發(fā)采用“自上而下”的進化機制，進化操作直接作用于數(shù)據(jù)，避免了進化過程中產(chǎn)生無意義的規(guī)則，而且進化個體不需要編碼，個體以組織的形式在三種組織進化算子以及組織選擇機制下協(xié)同進化，同時基于屬性重要度的協(xié)同進化完成適應(yīng)度函數(shù)的計算。該算法在UCI數(shù)據(jù)集、遙感圖像和雷達圖像識別上，與現(xiàn)有基于遺傳和非遺傳的分類方法進行了比較，獲得了很好的分類結(jié)果。之后，許多學(xué)者在該算法的基礎(chǔ)上展開研究。例如：文獻［10］針對該算法進化算子參數(shù)恒定不符合實際情況的問題，改進了進化算子，并將其應(yīng)用到Web日志挖掘中。文獻［11］將該算法應(yīng)用于遮擋點恢復(fù)，提出一種組織進化的遮擋點恢復(fù)算法，較好地恢復(fù)了遮擋點的位置。

鑒于組織協(xié)同進化分類算法良好的性能，例如沒有復(fù)雜的計算，運算效率比較高，同時針對傳統(tǒng)有標識軟件度量元數(shù)據(jù)缺陷預(yù)測精度有待進一步提高的問題，并結(jié)合軟件度量元數(shù)據(jù)的特點，本文首先對比選擇一種適用于軟件度量元數(shù)據(jù)的離散化方法，然后將該算法引入并應(yīng)用于軟件缺陷預(yù)測領(lǐng)域中，給出了一種基于組織協(xié)同進化的軟件缺陷預(yù)測方法，同時將該方法與基準的軟件缺陷預(yù)測方法進行對比，分析該方法的優(yōu)缺點。

1 基于組織協(xié)同進化的軟件缺陷預(yù)測方法

下面給出基于組織協(xié)同進化的軟件缺陷預(yù)測方法的結(jié)構(gòu)圖，如圖1所示。

在基于組織協(xié)同進化的軟件缺陷預(yù)測方法中，首先需要對軟件度量元和缺陷數(shù)據(jù)集進行離散化處理，通過本文后面的實驗可以發(fā)現(xiàn)，合理的離散化是一個重要的過程，離散的結(jié)果直接影響著組織協(xié)同進化分類算法的性能。在基于組織協(xié)同進化的軟件缺陷預(yù)測方法中，本文從三種常用的離散化方法中對比選擇出類-屬性相依性最大方法（Class-Attribute Interdependence Maximization，CAIM）用于軟件度量元數(shù)據(jù)的離散化處理。經(jīng)過離散化處理后，根據(jù)軟件缺陷預(yù)測目標將軟件度量元和缺陷數(shù)據(jù)劃分為有缺陷（Defective）和無缺陷（Non-Defective）兩個種群。在每個種群的進化過程中，數(shù)據(jù)個體形成進化個體組織，組織在三種進化算子（合并算子、增減算子和交換算子）以及相應(yīng)的選擇機制下不斷進化。適應(yīng)度函數(shù)是基于組織的屬性重要度計算的，各屬性的重要度不是提前賦予的固定值而是不斷進化的，且屬性重要度的進化指導(dǎo)和影響著缺陷和無缺陷兩個種群的進化，最后使得兩個種群共同達到一個最優(yōu)的狀態(tài)。在屬性重要度的計算過程中，同時進行著有用屬性的計算和標記。在該方法中，組織是進化的個體，組織不需要編碼，進化結(jié)束后可以從組織中提取出預(yù)測規(guī)則。

圖1 基于組織協(xié)同進化的軟件缺陷預(yù)測方法

需要指出的是，在軟件缺陷預(yù)測的過程中，由于不同組織所含的軟件度量元和缺陷數(shù)據(jù)個數(shù)是不相同的，有的多有的少。因此，在組織進化的增減算子和交換算子計算的過程中，如果按照文獻［9］的方法，則為一常數(shù)且只能取規(guī)模最小的組織所含對象的個數(shù)，通常為1，這在許多情況下是不符合實際情況的。鑒于此，本文采用文獻［10］的方法，即將N定為當前組織所含個數(shù)與一個百分數(shù)的乘積取整，最小為1，這樣當組織規(guī)模變化時，組織參與進化操作的對象個數(shù)也是自適應(yīng)動態(tài)變化的，在軟件缺陷預(yù)測的過程中，將該百分比設(shè)定為20%。

另外，在軟件缺陷預(yù)測過程中，當種群中只剩下一個組織時，不再進行上述三種進化算子，該組織個體直接進入下一代。否則，通過組織選擇機制從上述三種進化算子產(chǎn)生的子代與父代中選擇最優(yōu)個體進入下一代。

2 仿真實驗與分析

實驗用機配置為：Pentium（R）3.2 G CPU、1G DDR內(nèi)存、Windows XP操作系統(tǒng)，本文方法在Mat-Lab 7.0環(huán)境下運行。軟件缺陷預(yù)測方法運行之前，首先對所選的軟件度量元數(shù)據(jù)集進行其他必要的預(yù)處理，包括數(shù)據(jù)類別數(shù)值化即將類別的文字標識（True/False或者Defective/Non-Defective）替換為數(shù)值標識（1/0）、以及缺失數(shù)據(jù)、重復(fù)數(shù)據(jù)和沖突數(shù)據(jù)的檢測和處理。

2.1 仿真實驗1

軟件度量元數(shù)據(jù)是連續(xù)的，而組織協(xié)同進化分類算法僅能處理離散數(shù)據(jù)，因此，離散化是基于組織協(xié)同進化軟件缺陷預(yù)測方法的一個首要且關(guān)鍵的步驟。為了對比分析離散化過程對該算法性能的影響，下面選擇三種常用的典型離散化方法進行對比仿真實驗，離散化方法分別為：①等寬離散化（Equal Width Discretization，EWD）方法；②等頻離散化（E-qual Frequency Discretization，EFD）方法；③類-屬性相依性最大（Class-Attribute Interdependence Maximization，CAIM）方法。

目前，UCI數(shù)據(jù)庫［12］中的機器學(xué)習數(shù)據(jù)集被廣泛應(yīng)用于算法性能的測試。本文選擇了兩組最常用的Iris和Wine數(shù)據(jù)集進行仿真實驗。

Iris是鳶尾花數(shù)據(jù)集，包含150個樣本，它用萼片的長度、寬度和花瓣的長度、寬度4個連續(xù)的條件屬性來區(qū)分3種不同的花，每種花的比例均為1/3，其中有兩個條件屬性與分類結(jié)果相關(guān)性較強；Wine是葡萄酒數(shù)據(jù)集，包含178個樣本，分為3類，共13個屬性。

算法參數(shù)設(shè)置如下：最大運行代數(shù)E設(shè)置為500，N=20，在等寬和等頻離散化方法中，區(qū)間數(shù)K=4。采用準確率（%）和標準方差對算法性能進行評測，準確率指標Accuracy=N1/N2，其中，N1為正確分類的樣本數(shù)，N2為全部樣本數(shù)。為了更準確地衡量算法的性能，實驗均采用了十折交叉驗證，并給出了算法10次獨立運行的平均準確率。仿真結(jié)果如表1所示。

表1 不同離散化處理的分類結(jié)果

由上述仿真結(jié)果可以看出，在Iris數(shù)據(jù)和Wine數(shù)據(jù)上，CAIM離散化方法均是最有效的，組織協(xié)同進化分類算法在CAIM離散處理的數(shù)據(jù)上，具有最高的準確率和最低的標準方差，說明了CAIM離散化方法的高效性和穩(wěn)定性。

進一步對比和分析這三種離散化方法可以發(fā)現(xiàn)，EWD和EFD方法都是無監(jiān)督離散化方法，實現(xiàn)簡單，但需要人為設(shè)置劃分維數(shù)。二者根據(jù)給定的參數(shù)將各屬性的值域等距離或等頻率劃分為幾個離散的區(qū)間，忽視了樣本分布信息，因而，難以將區(qū)間邊界設(shè)置在最合適的位置上，從而使得離散后的結(jié)果沒有保障，例如本實驗中Wine數(shù)據(jù)上的分類結(jié)果則無法令人滿意。CAIM離散化方法與其他兩種方法不同，它是在信息熵量度的基礎(chǔ)上提出的，是一種全局的、靜態(tài)的、自下而上的有監(jiān)督離散化方法，在離散過程中不需要人為輸入?yún)?shù)，它以達到類與屬性相關(guān)度最大化和最少的斷點為目標，按順序?qū)γ恳粋€連續(xù)屬性進行離散化，采用caim離散判別式作為離散標準，迭代過程自動選擇離散斷點，直到滿足停止條件為止。

下面給出經(jīng)過CAIM離散處理后Iris和Wine數(shù)據(jù)各屬性的屬性重要度變化情況。首先對于Iris數(shù)據(jù)而言，如圖2所示。

圖2 Iris數(shù)據(jù)屬性重要度的進化圖

由圖2可以看出，Iris數(shù)據(jù)sepallength的屬性重要度值在前150代內(nèi)明顯最高，在后面300多代的進化過程中，其與petallength的屬性重要度不分上下。這與主成分分析等方法的判別結(jié)果是一致的，即這兩個屬性與分類結(jié)果相關(guān)性較強。

圖3給出了算法結(jié)束后，Iris數(shù)據(jù)在第500代時各屬性的屬性重要度。

圖3 Iris數(shù)據(jù)第500代屬性重要度

首先需要說明的是，在圖3中屬性1到屬性4，分別對應(yīng)屬性sepallength、sepalwidth、petallength和petalwidth，可以看出屬性1和屬性3的重要度值較高，為影響分類結(jié)果的兩個主要屬性。

對于Wine數(shù)據(jù)而言，Wine數(shù)據(jù)屬性較多，而且在仿真實驗過程中，發(fā)現(xiàn)大部分屬性在進化過程中屬性重要度的變化范圍和變化幅度是相近的，因此，限于篇幅的考慮，僅給出了屬性1，2，5，8，12的屬性重要度變化圖，如圖4所示。需要說明的是：這5個屬性分別是Wine數(shù)據(jù)從左到右第1，2，5，8，12位置對應(yīng)的條件屬性。

圖4 Wine數(shù)據(jù)屬性重要度的進化圖

由圖4可以看出，屬性1的重要度在500代的進化過程都明顯高于其他屬性，而其他的屬性在進化過程中屬性重要度的變化范圍和變化幅度是相近的。圖5給出了進化過程結(jié)束后，Wine數(shù)據(jù)集在第500代各屬性的屬性重要度值。

圖5 Wine數(shù)據(jù)第500代屬性重要度

總之，由圖4和圖5不難看出，對分類結(jié)果影響最大的屬性是屬性1。

2.2 仿真實驗2

為了驗證基于組織協(xié)同進化的軟件缺陷預(yù)測方法的有效性，在公開的Promise［13］數(shù)據(jù)庫中隨機選擇7組航空航天數(shù)據(jù)，與文獻［14］即軟件缺陷預(yù)測的基準方法（即樸素貝葉斯方法）進行對比，當前國內(nèi)外的許多文獻均選擇與樸素貝葉斯方法對比，進行方法優(yōu)劣的判斷。這7組數(shù)據(jù)的基本特征如表2所示，軟件度量元特征如表3所示。

表2 軟件數(shù)據(jù)集

表3 軟件度量元

在文獻［14］中，預(yù)測算法的評價指標為（PD，PF，Balance），為了便于對比，本文也給出在該組評價指標下的預(yù)測結(jié)果，下面首先給出二維混淆矩陣，并由此推導(dǎo)出該指標，具體如下。

表4 二維混淆矩陣

對于PD和PF指標而言，PD值越高且PF值越低，則認為該預(yù)測模型越好，然而精確率PD值的增加，往往會導(dǎo)致虛警率即PF值的增加，而Balance值可以實現(xiàn)二者的折中，因此，本文給出三者的仿真結(jié)果。

在該實驗中，基于組織協(xié)同進化的軟件缺陷預(yù)測方法的參數(shù)設(shè)置如下：CAIM離散化方法，最大進化代數(shù)為500，N=20，采用十折交叉驗證方法，并給出了算法10次獨立運行的平均值。仿真結(jié)果如表5所示。

表5 結(jié)果對比

在表5中，左側(cè)為對比算法文獻［14］的預(yù)測結(jié)果，右側(cè)為本文方法的仿真結(jié)果。首先從表5中可以看出，對于數(shù)據(jù)PC2、PC3和PC4而言，文獻［14］取得了較高的PD值，但其PF值也很高，導(dǎo)致Balance值均低于本文基于組織協(xié)同進化的軟件缺陷預(yù)測方法。對于數(shù)據(jù)CM1、PC1和MW1而言，與文獻［14］相比，本文基于組織協(xié)同進化的軟件缺陷預(yù)測方法在提高PD值的同時降低了PF值，因此，大大提高了Balance值。但對于KC3數(shù)據(jù)而言，本文基于組織協(xié)同進化的軟件缺陷預(yù)測方法僅降低了PF值，PD值低于文獻［14］，導(dǎo)致Balance值也低于文獻［14］。

但從總體上看，本文基于組織協(xié)同進化的軟件缺陷預(yù)測方法在這7組數(shù)據(jù)上獲得了較高的PD平均值（75），較低的PF平均值（4）和較高的Balance平均值（0.82），遠遠優(yōu)于對比算法：PD平均值（70），較低的PF平均值（24）和較高的Balance平均值（0.71），因此，從總體上看將組織協(xié)同進化分類算法應(yīng)用于軟件缺陷預(yù)測領(lǐng)域是可行的。

2.3 實驗結(jié)果分析

對上述的仿真實驗結(jié)果分析，首先由仿真實驗1可以看出，文獻［9］算法僅能處理離散數(shù)據(jù)，而且算法性能易受離散化結(jié)果的影響，因此，對于連續(xù)的軟件度量元數(shù)據(jù)選擇合適的離散化方法是首要的。

由仿真實驗2可以看出，離散化方法CAIM方法與文獻［9］算法相結(jié)合并應(yīng)用于軟件缺陷預(yù)測中是可行的。因為基于組織協(xié)同進化的軟件缺陷預(yù)測方法在大部分軟件度量元和缺陷數(shù)據(jù)集上的預(yù)測結(jié)果是優(yōu)秀的，在提高Balance值的同時，降低了軟件缺陷預(yù)測的虛警率即PF值，大大降低了軟件開發(fā)和維護的成本。

然而基于組織協(xié)同進化的軟件缺陷預(yù)測方法并不是萬能的（例如對于KC3數(shù)據(jù)）。分析其原因可以發(fā)現(xiàn)組織協(xié)同進化分類算法在進化過程中，對當前用于模型訓(xùn)練的軟件度量元數(shù)據(jù)樣本的要求是很高的，當樣本數(shù)量不足，或者是樣本質(zhì)量不高時，例如取樣不均勻時容易出現(xiàn)過擬合現(xiàn)象。因此，該算法對于大樣本或者高質(zhì)量的軟件缺陷數(shù)據(jù)性能較好，對于小樣本數(shù)據(jù)或噪聲數(shù)據(jù)較多的樣本容易出現(xiàn)過學(xué)習或過擬合，導(dǎo)致其預(yù)測性能的降低。

3 結(jié)束語

本文將組織協(xié)同進化分類算法引入并應(yīng)用到軟件缺陷預(yù)測領(lǐng)域，給出了一種基于組織協(xié)同進化的軟件缺陷預(yù)測方法。首先根據(jù)軟件度量元和缺陷數(shù)據(jù)的特點，對比選擇了CAIM方法用于度量元數(shù)據(jù)的離散化，然后將離散后的軟件度量元數(shù)據(jù)以組織的形式表示，在三種組織進化算子和選擇機制的作用下協(xié)同進化，并在屬性重要度協(xié)同進化的基礎(chǔ)上完成了適應(yīng)度函數(shù)的計算。最后通過兩組仿真實驗，在不同數(shù)據(jù)上對基于組織協(xié)同進化的軟件缺陷預(yù)測方法的性能進行分析和對比，仿真結(jié)果表明，該方法進一步提高了航空航天軟件缺陷預(yù)測的精度，為傳統(tǒng)有標識軟件度量元缺陷預(yù)測問題的解決提供了新的思路。

［1］Parag C P.Exhaustive and Heuristic Search Approaches for Learning a Software Defect Prediction Model［J］.Engineering Application of Artificial Intelligence，2010，23（1）：34-40.

［2］Daniel R,Roberto R，Jose C R,et al.A Study of Subgroup Discovery Approaches for Defect Prediction［J］.Information and Software Technology，2013，55（10）：1810-1822.

［3］Jin C，Jin S W.Software Reliability Prediction Model Based on Support Vector Regression with Improved Estimation of Distribution Algorithms［J］.Applied Software Computing, 2014（15）：113-120.

［4］Chen Y，Shen X H,Wang A B，et al.Application of Probabilistic Relational Model to Aerospace Software Defect Prediction［J］.Optics and Precision Engineering，2013，21（7）：1865-1872.

［5］Potter M A.The Design and Analysis of a Computational Model of cooperative Co-evolution［D］.Washington：George Mason University，1997.

［6］Zhu F M，Guan S U.Cooperative Co-evolution of GA-based Classifiers Ba sed on In put Increments［J］.Engine ering Applications of Artificial Intelligence，2008，21（8）：1360-1369.

［7］Wu K J,Lu H W.PCEGA Used to Solve Text Feature Selection［J］.Systems Engineering-Theory&Practice，2012，32（10）：2215-2220.

［8］羅書強，趙鵬，張根保.車間生產(chǎn)調(diào)度中動態(tài)小生境協(xié)同進化算法［J］.重慶大學(xué)學(xué)報，2011，12（34）：96-101.

［9］Liu J，Zhong W C，Jiao L C.An Organizational Evolutionary Algorithm for Numerical Optimization［J］.IEEE Trans.On System,Man,and CyberneticsPartB，2007，37（4）：1052-1064.

［10］Cai X J.Organization Co-evolutionary Algorithms for Web Log Mining［D］.Xi’an：Xidian University，2005.

［11］Peng Y L，Liu F.Organization Evolutionary Algorithm for Occlusion Recovery［J］.Journal of Xidian University，2013，40（4）：137-141.

［12］Blake C，Merz C.UCI Repository of Machine Learning Databases［DB/EL］.http：//www.ics.uci.edu/～mlearn/ML Repository.html，2014.

［13］Sayyad S J，Menzies T J.The Promise Repository of Software Engineering Database［EB/OL］.Canada：University of Ottawa，http：//promise.site.uottawa.ca/SERepository，2014.

［14］Menzies T,Greenw A L D J，F(xiàn)rank A.Data Mining Static Code Attributes to Learn Defect Predictors［J］.IEEE Transactions on Software Engineering，2007，33（1）：2-13.

Software Defect Prediction Based on Organizational Co-evolutionary Algorithm

CHANG Rui-hua
（Institute of Department of Scientific Research，Engineering University of Armed Police Force，Xi’an 710086，China）

Aiming at the problem of low software defect prediction accuracy for common labeled software metrics datasets,the software defect predictor based on organization co-evolutionary algorithm is presented.Firstly,an appropriate discretization method is chosen by compared with others.Then organizational co-evolutionary algorithm for classification is introduced and applied into the fields of aerospace software defect prediction.In this method,according to the prediction target,the discrete metrics datasets are divided into different species groups.Inside each species group,new evolutionary individual (organization)is formed.And organizations evolve through add and subtract operator, exchange operator,unite operator and a selection mechanism.Meantime,fitness function is calculated based on co-evolutionary importance of attribute.It improves software defect prediction accuracy of labeled software metrics.Finally,two case studies are used to validate the method,and the results show that this method is effective.

software defect，prediction，software metrics，co-evolutionary

TP311

A

1002-0640（2015）07-0126-05

2014-04-24

2014-06-25

國家自然科學(xué)基金（No.61309022）；陜西省自然科學(xué)基金（No.2013JQ8031）；武警工程大學(xué)基礎(chǔ)研究基金資助項目（No.WJY201315）

常瑞花（1982- ），女，山西清徐人，博士，工程師。研究方向：信息處理和信息安全。