基于不相似性的軟件缺陷預測算法

，

(1.中國電子科學研究院，北京 100041; 2.北京自動化控制設備研究所，北京 100074)

0 引言

軟件缺陷數(shù)據(jù)集中有缺陷的樣本數(shù)量往往比無缺陷的樣本數(shù)量少得多，因此，軟件缺陷預測可被視作一個類不均衡學習問題。在類不均衡學習學習過程中，不同類別的誤分代價各不相等，少數(shù)類(有缺陷)的誤分代價遠高于多數(shù)類(無缺陷)的誤分代價，為盡可能地降低誤分代價，預測算法更重視那些有缺陷的少數(shù)類樣本的預測結果。然而，傳統(tǒng)的分類算法通常建立在類分布均衡且誤分代價相等的前提下，以最小化分類誤差為最終目標，因此直接采用決策樹分類[1-3]、神經(jīng)網(wǎng)絡[3]、貝葉斯分類[4]、支持向量機[3-6]及k-最近鄰分類[1,7]等傳統(tǒng)的機器學習算法并不能獲得較好的軟件缺陷預測性能。

近年來，類不均衡學習問題受到了學術界的廣泛關注，機器學習和數(shù)據(jù)挖掘領域專家們在AAAI’00[8]、ICML’03[9]及ACM SIGKDD’04[10]等權威研討會上，對類不均衡問題的本質、解決方法及其性能評估指標進行了深入地探索與研究，并從數(shù)據(jù)層和算法層兩方面提出了許多行之有效的解決方法。

數(shù)據(jù)層方法，主要通過(1)抽樣或生成新樣本的方式，使類分布恢復均衡，如隨機欠抽樣[11](RUS)和隨機過抽樣[12](ROS)。重復抽樣可以平衡類分布，但欠抽樣往往會忽略某些重要樣本，導致信息缺失；反之，過抽樣會引入大量副本，產(chǎn)生冗余信息，導致過擬合。

算法層方法，側重于改進已有分類算法或研究新的分類算法，以更好地解決類不均衡學習問題。(1)“One-Class Learning”方法[13]，該方法僅在多數(shù)類上構建分類模型，難以準確預測少數(shù)類；(2)組合學習方法，通過重復抽樣構建多個分類模型、迭代更新訓練樣本的權重或組合多個決策樹的方式，獲得穩(wěn)定的分類精度，如Bagging[14]、Boosting[15]及Random Forest[16]等算法。特別是，當分類模型間存在顯著差異時，組合分類模型比基本分類模型更準確，但其計算量大且復雜度較高；(3)代價敏感分析，以最小化誤分類代價為學習目標，如MetaCost[17]不依賴于分類算法，且可應用于任意形式的代價矩陣上，但如何確定代價矩陣目前仍然是一個難題。

學者們[18]發(fā)現(xiàn)：除不均衡的類分布以外，小樣本、高維度及問題復雜度等因素也會影響算法性能。預測算法本質上是在挖掘數(shù)據(jù)集中屬性特征與類目標概念間內在的關聯(lián)關系，并建立相應的形式化預測模型。當不均衡數(shù)據(jù)集自身屬性對類目標概念缺乏判別能力時，預測算法的性能將會有所下降，特別是少數(shù)類樣本的預測。

現(xiàn)有的類不均衡學習方法側重于如何調整類分布或改進算法，而忽略了類不均衡數(shù)據(jù)集中屬性特征的判別能力。為了提升數(shù)據(jù)集屬性特征的判別能力，Pekalska和Duin等人[19]提出了一種基于不相似性的表示法，用樣本間不相似性替代原始屬性特征，不僅保留了數(shù)據(jù)集原有統(tǒng)計信息，也能夠獲取到數(shù)據(jù)集內在的結構信息，該方法已被證實有利于預測模型的構建[20-21]?；谝延械难芯砍晒岢隽艘环N基于不相似性的軟件缺陷預測算法(Dissimilarity-based Software Defect Prediction Algorithm, DSDPA)，用以提升軟件缺陷的預測性能。

DSDPA主要由原型選擇、不相似性轉換和缺陷預測三部分組成。實驗過程中，采用隨機選擇法進行原型選擇，歐幾里德距離衡量樣本間的不相似性，將18個軟件缺陷數(shù)據(jù)集轉換到不相似性空間；然后，采用最近鄰分類算法(1-NN, IB1)、決策樹(Decision Tree，DT)、神經(jīng)網(wǎng)絡(Multi-layer Perceptron，MLP)、樸素貝葉斯(Naive Bayes，NB)、隨機森林(Random Forest，RF)和支持向量機(Support Vector Machine，SVM)6種傳統(tǒng)機器學習算法，在基于不相似空間中的軟件缺陷數(shù)據(jù)集上構建預測模型；最后，對比分析了基于不相似性的軟件缺陷預測方法DSDPA的預測性能。實驗結果表明，DSDPA能夠有效地改善軟件缺陷預測的準確性。

1 算法原理及框架

當利用機器學習算法預測軟件缺陷時，預測模型的建立通?；陟o態(tài)度量元的軟件缺陷數(shù)據(jù)集上，而基于不相似性的軟件缺陷預測算法(DSDPA)則是將原始數(shù)據(jù)集預先映射到不相似性空間，而后在不相似性空間中構建軟件缺陷預測模型。DSDPA主要由原型選擇、不相似性轉換和分類三部分組成。圖 1給出了DSDPA的基本框架，主要由基于不相似性預測模型的構建和軟件缺陷預測兩大環(huán)節(jié)組成。

圖1 基于不相似性的軟件缺陷預測算法框架

1)基于不相似性預測模型的構建。

基于不相似性的軟件缺陷預測算法的構建過程主要由原型選擇、不相似性轉換及構建預測模型三部分組成。首先，采用原型選擇方法從原始數(shù)據(jù)集中篩選出具有代表性的樣本作為原型，創(chuàng)建原型集；然后，計算原始數(shù)據(jù)集與原型集樣本間的不相似性，從而將其映射到相應的不相似性空間中；最后，利用傳統(tǒng)分類算法在不相似性空間中構建軟件缺陷預測模型。

2)軟件缺陷預測。

當未知樣本到來時，首先計算未知樣本與原型集中各樣本間的不相似性，將其映射到到不相似性空間；然后，利用已構建的軟件缺陷預測模型對不相似性空間中的未知樣本進行預測，即可獲悉未知樣本是否有缺陷。

1.1 原型選擇

原型選擇旨在從原始數(shù)據(jù)集中選取具有代表性的樣本作為原型，作為不相似性轉換時的參照。為了更好的選取原型，學者們提出了基于共享最近鄰(Shared Nearest Neighbors，SNN)的 Jarvis-Patrick clustering(JPC)算法[21]、隨機選擇[22](RandomC，RC)、線性規(guī)劃[23](LinPro)、屬性選擇[24](FeaSel)、模式搜索[25](ModeSeek)、基于聚類的線性規(guī)劃[26](KCenters-LP)及編輯壓縮(EdiCon)等方法。其中，隨機選擇法(RC)，即隨機地從原始數(shù)據(jù)集中抽取指定數(shù)量的樣本作為原型，是最簡單且有效的一種原型選擇方法。Pekalska等人[26,21]對比分析了上述原型方法對基于不相似性分類方法性能的影響，實驗結果表明：RC和KCenters總體表現(xiàn)較好，但RC更便捷。

為了保證DSDPA算法的性能，選用RC作為原型選擇方法，從原始軟件缺陷數(shù)據(jù)集中抽取具有代表性的樣本，創(chuàng)建原型集。假設D代表一個軟件缺陷數(shù)據(jù)集，屬于二類分類問題，即C={c1,c2}，Dt為訓練集，D1和D2分別代表有缺陷和無缺陷類的訓練集。從D抽取r個樣本作為原型集合P，利用隨機選擇的方法分別從D1和D2中隨機抽取r1和r2個樣本，使原型集P={r1,r2}。

1.2 不相似性轉換

不相似性轉換旨在將原始數(shù)據(jù)集映射到不相似性空間，圖 2給出了不相似性轉換的詳細過程。

圖2 不相似性轉換

假設D={x1,x2,...,xn}代表樣本數(shù)量為n的軟件缺陷數(shù)據(jù)集。其中，xi={ai1,ai2,...,aim,ci}代表數(shù)據(jù)集D中第i個樣本；xi由m個獨立屬性和一個類屬性組成。P={p1,p2,...,pr}表示由r個具有代表性的樣本構成的原型集，其中pi= {ai1′,ai2′,...,aim′,ci′} 代表第i個原型。

當評估密集、連續(xù)型樣本間的不相似性時，基于度量的距離樣本間的不相似性通常用距離度量來描述，距離越大，越不相似；反之，則越相似。目前最常用的距離度量有歐幾里德距離、曼哈頓距離及閔可夫斯基距離。其中，閔可夫斯基距離是歐幾里德距離和曼哈頓距離的推廣，其計算方法見公式(1)：

(1)

式中，l是實數(shù)，l≥1。

當l=1時，曼哈頓距離，即L1范數(shù)；

當l=2時，歐幾里德距離，即L2范數(shù)，常用于度量密集、連續(xù)的數(shù)據(jù)集中樣本間的不相似性；

當l=∞時，上確界距離，又稱L∞范數(shù)和切比雪夫距離，度量樣本間的最大值差。

不相似性轉換過程

輸入：D={x1,x2,...,xn}為原始的軟件缺陷數(shù)據(jù)集；

P={p1,p2,...,pr}為原型集合；

1: for eachxi∈Ddo

2: for eachpj∈Pdo

4: end

由于軟件缺陷數(shù)據(jù)集中大多數(shù)屬性特征是密集連續(xù)的，所以選用基于度量的歐幾里德距離來度量樣本間的不相似性，以實現(xiàn)軟件缺陷數(shù)據(jù)集從原始特征空間到不相似性空間的轉換。

1.3 時間復雜度分析

DSDPA算法由原型選擇、不相似性轉換及分類三個環(huán)節(jié)組成，其算法時間復雜度即各環(huán)節(jié)時間復雜度的總和。給定一個軟件缺陷不均衡數(shù)據(jù)集D，樣本數(shù)量為n，屬性數(shù)量為m，利用DSDPA算法在D上進行缺陷預測時，各環(huán)節(jié)時間復雜度的計算方法如下所述：

1)原型選擇的時間復雜度。

從樣本數(shù)量為n的不均衡數(shù)據(jù)集中選取r個原型時，不同的原型選擇方法的時間復雜也不相同。隨機選擇方法無放回抽樣，重復r次的時間復雜度為TRC=O(r)。

2)不相似性轉換的時間復雜度。

不相似性轉換旨在計算原始的軟件缺陷數(shù)據(jù)集與原型集中樣本間的不相似性，從而將其轉換到不相似性空間，不相似性轉換的時間復雜度為TDT=O(n·r)。

3)缺陷預測的時間復雜度。

在樣本數(shù)量為n，屬性數(shù)量為r+1的基于不相似性的軟件缺陷數(shù)據(jù)集上進行預測時，時間復雜度依賴于所選用的機器學習算法，TC=O(C(n,r+1))。

DSDPA算法的時間復雜度TDSDPA=TRC+TDT+TC，即TDSDPA=O(r)+O(n·r)+O(C(n,r+1))。

2 實驗結果與分析

為了保證實驗的客觀性和可再現(xiàn)性，在公開的軟件缺陷數(shù)據(jù)集上對DSDPA的預測性能進行了實驗評估與驗證。

2.1 實驗數(shù)據(jù)

本實驗在18來自Promise[27]數(shù)據(jù)庫的軟件缺陷數(shù)據(jù)集，其中5個源自PROMISE軟件工程數(shù)據(jù)庫，13個源自美國宇航局(NASA)MDP項目的數(shù)據(jù)集。MDP是由美國宇航局提供一個軟件度量庫，并通過網(wǎng)站提供給普通用戶。MDP數(shù)據(jù)存儲了系統(tǒng)在模塊(函數(shù)/方法)級的軟件產(chǎn)品的度量數(shù)據(jù)和相關的缺陷數(shù)據(jù)；實驗數(shù)據(jù)集的樣本數(shù)量分布在36～171 68之間，屬性數(shù)量分布于22～41之間，不均衡率分布在1.049 2～138.21之間。表 1給出了18個軟件缺陷數(shù)據(jù)集的統(tǒng)計信息，其中I、F、Cmin、Cmaj和 IR分別代表樣本數(shù)量、屬性數(shù)量、少數(shù)類樣本數(shù)量(有缺陷的樣本數(shù)量)、多數(shù)類樣本數(shù)量(無缺陷的樣本數(shù)量)以及不均衡率(Cmaj/ Cmin)。

表1 18軟件缺陷數(shù)據(jù)集的統(tǒng)計信息

2.2 實驗設置

為了全面地驗證基于不相似性軟件缺陷預測算法(DSDPA)的有效性，并保證實驗的可再現(xiàn)性，本節(jié)對實驗中的各環(huán)節(jié)進行了如下設置：

1)軟件缺陷預測算法。

不同的機器學習算法在軟件缺陷數(shù)據(jù)集上的預測性能也不相同。為了考察DSDPA能否有效地改善軟件缺陷數(shù)據(jù)集上的預測性能，采用了6種最常用的機器學習算法作為候選預測算法[28-29]，包括：基于實例學習的k-最近鄰算法(1-NN，IB1)、決策樹(J48)、神經(jīng)網(wǎng)絡(MLP)、樸素貝葉斯(NB)、隨機森林(Random Forest)和支持向量機(SVM)，用以對不相似性空間中的軟件缺陷數(shù)據(jù)集進行預測。

2)性能評估方法。

在評估不均衡學習方法的性能時，采用10×10折交叉驗證，充分利用數(shù)據(jù)信息的同時，盡可能地減少隨機序列產(chǎn)生的偶然誤差。

3)性能評價指標。

為了評價軟件缺陷預測性能，特別是有缺陷樣本的預測準確率，采用AUC評估各算法在軟件缺陷數(shù)據(jù)集上的預測準確性。

2.3 結果與分析

表2給出了采用DSDPA與原始數(shù)據(jù)上(Org)時，最近鄰(IB1)、決策樹(J48)、神經(jīng)網(wǎng)絡(MLP)、樸素貝葉斯(NB)、隨機森林(RF)及支持向量機(SVM)6種機器學習方法在18個軟件缺陷數(shù)據(jù)集上的預測性能AUC。由表可見，提出的DSDPA方法能夠有效地改善傳統(tǒng)機器學習方法在軟件缺陷數(shù)據(jù)集上的預測性能，特別是在使用IB1和支持向量機SVM算法進行軟件缺陷缺陷預測時，IB1算法在軟件缺陷數(shù)據(jù)集上的分類性能平均提升了11.11%；SVM算法在軟件缺陷數(shù)據(jù)集上的分類性能平均提升了12%。J48、MLP、NB算法在軟件缺陷數(shù)據(jù)集上的平均分類性能也得到了提升，提升率分別為3.12%、2.5%、2.6%及2.7%。

表2算法性能比較(AUC)

3 結論

從改善軟件缺陷數(shù)據(jù)集中屬性特征判別能力的角度出發(fā)，提出了一種基于不相似性的軟件缺陷預測算法(DSDPA)，主要由原型選擇、不相似性轉換及缺陷預測三部分組成。針對最近鄰、決策樹、神經(jīng)網(wǎng)絡、樸素貝葉斯、隨機森林及支持向量機6種傳統(tǒng)機器學習算法，對比分析了DSDPA在軟件缺陷數(shù)據(jù)集上的預測性能AUC。實驗結果表明：DSDPA算法能夠有效地改善傳統(tǒng)機器學習算法在軟件缺陷數(shù)據(jù)集上的預測性能。

[1] Chawla NV, Japkowicz N, Kotcz A. Editorial: special issue on learning from imbalanced data sets[J]. ACM SIGKDD Explorations Newsletter, 2004, 6 (1): 1-6.

[2] Batista GE, Prati RC, Monard MC. A study of the behavior of several methods for balancing machine learning training data[J]. ACM SIGKDD Explorations Newsletter, 2004, 6 (1): 20-29.

[3] Japkowicz N, Stephen S. The class imbalance problem: A systematic study[J]. Intelligent Data Analysis, 2002, 6 (5): 429-449.

[4] Ezawa KJ, Singh M, Norton SW. Learning goal oriented Bayesian networks for telecommunications risk management[A]. International Conference on Machine Learning[C].1996: 139-147.

[5] Raskutti B, Kowalczyk A. Extreme re-balancing for SVMs: a case study[J]. ACM SIGKDD Explorations Newsletter, 2004, 6 (1): 60-69.

[6] Wu G, Chang EY. Class-boundary alignment for imbalanced dataset learning[C]. ICML 2003 workshop on learning from imbalanced data sets II, 2003: 49-56.

[7] Mani I, Zhang I. kNN approach to unbalanced data distributions: a case study involving information extraction[C]. Proceedings of Workshop on Learning from Imbalanced Datasets, 2003.

[8] Japkowicz N, others. Learning from imbalanced data sets: a comparison of various strategies[C]. AAAI workshop on learning from imbalanced data sets, 2000, 68.

[9] Japkowicz N. Class imbalances: are we focusing on the right issue[C]. Workshop on Learning from Imbalanced Data Sets II, 2003, 1723: 63.

[10] Chawla NV, Japkowicz N, Kotcz A. Editorial: special issue on learning from imbalanced data sets[J]. ACM SIGKDD Explorations Newsletter, 2004, 6 (1): 1-6.

[11] Kotsiantis SB, Pintelas PE. Mixture of expert agents for handling imbalanced data sets[J]. Annals of Mathematics, Computing & Teleinformatics, 2003, 1 (1): 46-55.

[12] Kubat M, Matwin S, others. Addressing the curse of imbalanced training sets: one-sided selection[A]. International Conference on Machine Learning[C].1997: 179-186.

[13] Manevitz LM, Yousef M. One-class SVMs for document classification[J]. The Journal of Machine Learning Research, 2002, 2: 139-154.

[14] Breiman L. Bagging predictors[J]. Machine Learning, 1996, 24 (2): 123-140.

[15] Joshi MV, Kumar V, Agarwal RC. Evaluating boosting algorithms to classify rare classes: Comparison and improvements[A]. IEEE International Conference on Data Mining[C]. 2001: 257-264.

[16] Breiman L. Random forests[J]. Machine Learning, 2001, 45 (1): 5-32.

[17] Domingos P. Metacost: A general method for making classifiers cost-sensitive[A]. Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining[C].1999: 155-164.

[18] Batista GE, Prati RC, Monard MC. A study of the behavior of several methods for balancing machine learning training data[J]. ACM SIGKDD Explorations Newsletter, 2004, 6 (1): 20-29.

[19] Pkekalska E, Duin RP. The dissimilarity representation for pattern recognition: foundations and applications[M]. World Scientific, 2005.

[20] Pkekalska E, Duin RPW. Dissimilarity representations allow for building good classifiers[J]. Pattern Recognition Letters, 2002, 23 (8): 943-956.

[21] Zhang XY, Song QB, Zhang KY, He L, Jia XL. A dissimilarity-based imbalance data classification algorithm [J]. Applied Intelligence, 2015, 42(3):544-565.

[22] Pekalska E, Paclik P, Duin RP. A generalized kernel approach to dissimilarity-based classification[J]. Journal of Machine Learning Research, 2002, 2: 175-211.

[23] Bradley PS, Mangasarian OL, Street W. Feature selection via mathematical programming[J]. Informs Journal on Computing, 1998, 10: 209-217.

[24] Jain A, Zongker D. Feature selection: Evaluation, application, and small sample performance[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19 (2): 153-158.

[25] Cheng Y. Mean shift, mode seeking, and clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17 (8): 790-799.

[26] Pekalska E, Duin RPW, Paclik P. Prototype selection for dissimilarity-based classifiers[J]. Pattern Recognition, 2006, 39 (2): 189-208.

[27] Boetticher G, Menzies T, Ostrand T. Promise repository of empirical software engineering data. Department of Computer Science[J]. West Virginia University, 2007.

[28] 馬 櫻. 基于機器學習的軟件缺陷預測技術研究[D]. 成都. 電子科技大學，2012.

[29] 程 俊，張雪瑩，李瑞賢. 基于元學習的軟件缺陷預測推薦方法[J]. 中國電子科學研究院學報, 2015, 10(6): 620-627.