基于線性LTSA算法維數(shù)約減的軟件缺陷預(yù)測研究

王玉紅，范 菁，曲金帥，馮景義

(云南民族大學(xué) 云南省高校信息與通信安全災(zāi)備重點實驗室，云南 昆明650500)

軟件缺陷預(yù)測技術(shù)旨在利用已知的度量元和標簽訓(xùn)練樣本，獲取軟件缺陷分布預(yù)測模型，對未知的軟件模塊進行二值分類(即有缺陷和無缺陷)[1]，預(yù)測出軟件系統(tǒng)中高風險模塊，合理分配軟件測試資源[2].而基于軟件相關(guān)的度量數(shù)據(jù)往往為高維且非線性的流行結(jié)構(gòu)，獲取真實的低維數(shù)據(jù)結(jié)構(gòu)信息，約減數(shù)據(jù)維度已成為軟件缺陷預(yù)測技術(shù)研究的關(guān)鍵.軟件缺陷預(yù)測中多維度量元帶來的“維度災(zāi)難”，會導(dǎo)致軟件缺陷預(yù)測精度降低[4].針對此問題，采用局部切空間排列算法(LTSA，local tangent space alignment)的線性逼近進行數(shù)據(jù)預(yù)處理，除去度量屬性過多造成的冗余數(shù)據(jù)信息，構(gòu)造軟件缺陷分布預(yù)測模型[3-4].

1 線性 LTSA算法描述

LTSA算法有較高的魯棒性，但算法不能得到解析形式的映射函數(shù)，對于新加入的樣本點，需要重新學(xué)習才能映射到低維空間.針對LTSA算法無法直接映射新樣本點坐標的問題，提出一種LTSA算法的線性逼近，為線性局部切空間排列算法，能夠有效學(xué)習出映射空間的基向量，從而將新樣本點投影到低維線性空間.采用較為簡單的線性投影方法，顯著特點是計算復(fù)雜度較低，計算速度快.

線性LTSA算法的主要思想是尋找一個轉(zhuǎn)換矩陣G，將數(shù)據(jù)集X∈RD空間通過映射變換矩陣映射到X∈Rd空間，其中，樣本點個數(shù)為N，且d

Y=GTXHN

.

(1)

其中，HN為中心化矩陣，HN=I-eeT，I為單位矩陣，為元素全1的N維列向量，Y為維數(shù)約簡后的低維數(shù)據(jù)集.

第1步，根據(jù)KNN準則選取鄰域.

選取樣本點xi的k近鄰xij(鄰域包含xi本身)組成鄰域矩陣Xi=(xi1,xi2…,xik)，i=1,2,…,N，j=1,2,…,k，k為近鄰點個數(shù).

第2步，鄰域切空間計算.

在鄰域矩陣Xi上進行PCA降維，求得鄰域內(nèi)的一組正交基Qi，Qi即為XiHk的前d個最大特征值對應(yīng)的特征矢量構(gòu)成的切空間正交基矩陣，將鄰域內(nèi)的樣本點投影到Qi上，獲取鄰域的主要低維流行結(jié)構(gòu)信息.

(2)

Hk為中心化矩陣，Hk=I-eeT/k，I為單位矩陣，e為元素全1的k維列向量.樣本點xi的鄰域嵌入坐標如下.

(3)

第3步，計算全局坐標排列.

以重構(gòu)誤差最小化為約束條件，保持高維原始樣本空間的局部流行結(jié)構(gòu)，重構(gòu)數(shù)據(jù)集的本征結(jié)構(gòu)，進行局部切空間的全局坐標排列，目標函數(shù)如下.

(4)

上述目標函數(shù)最小化解的可轉(zhuǎn)化為求解矩陣廣義特征值問題.

XHNBHNXTα=λXHNXTα

.

(5)

2 軟件缺陷預(yù)測模型

2.1 模型建立

基于線性LTSA算法軟件缺陷預(yù)測模型主要流程如圖1所示.

首先，選取美國航空航天(NASA)的MDP(metric data program)軟件度量項目中的PC4數(shù)據(jù)集，包含1 399條數(shù)據(jù)，每條數(shù)據(jù)由37個屬性描述，并在數(shù)據(jù)末尾處標明了該數(shù)據(jù)的標簽屬性，即有無缺陷.實驗中將有缺陷模塊記為1，無缺陷模塊記為-1.其次，降維后的新數(shù)據(jù)集作為下一步的輸入集.

由于支持向量機(support vector machine，SVM)在高維、小采樣中表現(xiàn)出優(yōu)良的特性，且分類結(jié)果不受少數(shù)離群點決定，所以選用SVM進行二值分類[9,13]，核函數(shù)選擇徑向基核函數(shù)(radial basis function，RBF)，含有的參數(shù)為核函數(shù)參數(shù)δ(g)，為評價離群點帶來的損失，引入了懲罰因子C.

2.2 模型參數(shù)尋優(yōu)

線性LTSA算法需確定鄰域值k和降低維度值d.參考大量文獻并多次實驗后給定k的取值區(qū)間為 [33,38]，遵循d

2.3 模型評價指標

軟件缺陷預(yù)測技術(shù)領(lǐng)域最廣泛應(yīng)用二維混淆矩陣評價模型的預(yù)測能力，是國際上公認的、標準化的研究方法，實驗中SVM分類可以得到每個樣本的標簽信息，即有缺陷1或者無缺陷-1，將1預(yù)測為-1的數(shù)目記為TP，將1預(yù)測為-1的數(shù)目記為FN，將-1預(yù)測為1的數(shù)目記為FP，將-1預(yù)測為1的數(shù)目記為TN，統(tǒng)計得到TP、TN、FP和FN的值.計算得到指標包括準確度、查全率、查準率和F-measure值，本模型主要采用準確度這一評價指標.如表1所示.

表1 混淆矩陣

準確度(Accuracy)表示正確分類的樣本總數(shù)占測試樣本的比例.

(6)

查全率(Recall)表示實際和預(yù)測值都為有缺陷的樣本數(shù)目占實際含缺陷的樣本總數(shù)的比例.

(7)

查準率(Precision)表示實際和預(yù)測值都為有缺陷的樣本數(shù)目占預(yù)測為含缺陷的樣本總數(shù)的比例.

(8)

F-measure值(F值)表示查準率和查全率的調(diào)和平均.

(9)

2.4 軟件缺陷預(yù)測仿真實驗

選用LTSA算法對PC4數(shù)據(jù)集降維，采用網(wǎng)格搜索結(jié)合10折交叉驗證進行實驗.得到準確度隨維度和鄰域的變化，如圖2所示.

實驗結(jié)果證明當k=35，d=16時，評價指標即分類的準確度最高為86.69%，因此模型選取這組參數(shù)值進行軟件缺陷預(yù)測.采用同樣的參數(shù)選取SVM參數(shù)，給定核函數(shù)參數(shù)的取值區(qū)間，步長設(shè)置為0.1，懲罰因子C的取值區(qū)間，步長設(shè)置為0.01.當取34.8，C取0.1時，預(yù)測準確度最高為89.57%.統(tǒng)計各模型預(yù)測的二維混淆矩陣中數(shù)據(jù)結(jié)果，與傳統(tǒng)降維算法模型比較，如表2所示.

表2 不同降維算法的預(yù)測值

選用同樣的數(shù)據(jù)集PC4和PC1，與采用流形學(xué)習[12]中主要的LLE、LLTSA、NPE算法進行數(shù)據(jù)降維處理的實驗及單一的SVM軟件缺陷預(yù)測的評價指標比較，如表3所示.

表3 不同數(shù)據(jù)集預(yù)測結(jié)果準確度 %

由于不同參考文獻中數(shù)據(jù)集的選取都具有隨機性，采用同樣的降維算法預(yù)測得到的結(jié)果會存在一定的差異，所以參考文獻[10]中的實驗結(jié)果有所不同.但該仿真實驗是在同一數(shù)據(jù)集下比較得出的預(yù)測準確度，因此，結(jié)果對比是有效的.

實驗結(jié)果表明，采用LLE算法降維處理對鄰域點數(shù)目的依賴性較大，屬性約減的同時，也除去了數(shù)據(jù)的重要特征.改進LLE算法是在LLE算法的基礎(chǔ)上將KNN中根據(jù)歐氏距離選取領(lǐng)域點改進為取成對距離(Pairwise距離).以上兩種算法預(yù)測結(jié)果并不理想，針對不同的數(shù)據(jù)集，改進LLE算法預(yù)測效果提高的程度不同，說明LLE算法具有不穩(wěn)健的解.采用PCA算法在不同數(shù)據(jù)集上的表現(xiàn)不一致，對于較大的數(shù)據(jù)集，準確度提高了2%，數(shù)據(jù)集較小時，評價指標不會提升.LTSA算法能得到更穩(wěn)定的解，準確度在在兩者數(shù)據(jù)集上分別提高6%和1%左右，線性LTSA算法能在數(shù)據(jù)集維度和鄰域值較小的情況下，達到和LTSA算法近似的結(jié)果，并且該算法可直接映射新的樣本點，得到顯式的映射函數(shù)，不需要重新學(xué)習高維空間的流行結(jié)構(gòu).以下表4比較了LTSA和線性LTSA算法的時間成本耗費.

表4 PC4數(shù)據(jù)集算法的時間成本 s

由此可知，本文算法在軟件缺陷預(yù)測中表現(xiàn)出極大的優(yōu)越性，能在鄰域點數(shù)目較少且維度較低的條件下，直接映射新的樣本點，預(yù)測精度和LTSA算法結(jié)果相近，提高預(yù)測準確度，降低了計算的復(fù)雜度，預(yù)測最優(yōu)準確度的時間消耗從13.726 9 s降低至6.217 8 s，同樣在(k，d)網(wǎng)格參數(shù)為6×6的矩陣尋優(yōu)耗費的時間由267.442 1 s降低至165.98 s，有效提高了軟件缺陷預(yù)測的效率，減少時間成本.

3 結(jié)語

軟件缺陷預(yù)測技術(shù)能夠識別軟件系統(tǒng)中的高風險的模塊，在軟件開發(fā)過程中具有重要的指導(dǎo)意義.本文針對軟件缺陷預(yù)測數(shù)據(jù)集高維、小采樣的特點，采用LTSA算法對數(shù)據(jù)集的冗余特征進行約減.該模型的主要思想是利用局部特征映射的切空間排列，以重構(gòu)誤差最小為約束，求解全局低維坐標表示.實驗結(jié)果表明，本文建立的模型可以利用較少的鄰域點在更低維度的空間求解得到更加穩(wěn)健的特征向量，并有效保留了原本樣本空間的流行幾何結(jié)構(gòu).但實驗各模型并不能有效提高軟件缺陷的預(yù)測精度，下一步，將結(jié)合算法最后線性投影方向，考慮改進線性LTSA算法，提高模型預(yù)測的預(yù)測精度.