，

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

0 引言

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

近年來，類不均衡學(xué)習(xí)問題受到了學(xué)術(shù)界的廣泛關(guān)注，機器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域?qū)＜覀冊贏AAI’00[8]、ICML’03[9]及ACM SIGKDD’04[10]等權(quán)威研討會上，對類不均衡問題的本質(zhì)、解決方法及其性能評估指標(biāo)進行了深入地探索與研究，并從數(shù)據(jù)層和算法層兩方面提出了許多行之有效的解決方法。

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

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

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

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

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

1 算法原理及框架

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

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

1)基于不相似性預(yù)測模型的構(gòu)建。

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

2)軟件缺陷預(yù)測。

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

1.1 原型選擇

原型選擇旨在從原始數(shù)據(jù)集中選取具有代表性的樣本作為原型，作為不相似性轉(zhuǎn)換時的參照。為了更好的選取原型，學(xué)者們提出了基于共享最近鄰(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]對比分析了上述原型方法對基于不相似性分類方法性能的影響，實驗結(jié)果表明：RC和KCenters總體表現(xiàn)較好，但RC更便捷。

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

1.2 不相似性轉(zhuǎn)換

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

圖2 不相似性轉(zhuǎn)換

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

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

(1)

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

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

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

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

不相似性轉(zhuǎn)換過程

輸入：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ù)集從原始特征空間到不相似性空間的轉(zhuǎn)換。

1.3 時間復(fù)雜度分析

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

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

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

2)不相似性轉(zhuǎn)換的時間復(fù)雜度。

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

3)缺陷預(yù)測的時間復(fù)雜度。

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

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

2 實驗結(jié)果與分析

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

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ù)和相關(guān)的缺陷數(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 實驗設(shè)置

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

1)軟件缺陷預(yù)測算法。

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

2)性能評估方法。

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

3)性能評價指標(biāo)。

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

2.3 結(jié)果與分析

表2給出了采用DSDPA與原始數(shù)據(jù)上(Org)時，最近鄰(IB1)、決策樹(J48)、神經(jīng)網(wǎng)絡(luò)(MLP)、樸素貝葉斯(NB)、隨機森林(RF)及支持向量機(SVM)6種機器學(xué)習(xí)方法在18個軟件缺陷數(shù)據(jù)集上的預(yù)測性能AUC。由表可見，提出的DSDPA方法能夠有效地改善傳統(tǒng)機器學(xué)習(xí)方法在軟件缺陷數(shù)據(jù)集上的預(yù)測性能，特別是在使用IB1和支持向量機SVM算法進行軟件缺陷缺陷預(yù)測時，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 結(jié)論

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

[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] 馬 櫻. 基于機器學(xué)習(xí)的軟件缺陷預(yù)測技術(shù)研究[D]. 成都. 電子科技大學(xué)，2012.

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