基于未確知聚類的軟件可靠性模型研究

摘 要:軟件可靠性是軟件質量的重要指標之一。傳統的軟件可靠性模型通過一些精確、無歧義的假設，對軟件的可靠性增長行為進行抽象和簡化。將未確知理論與聚類方法結合起來應用于軟件可靠性的研究中，擺脫了對軟件故障過程的各種分布假設，改善了模型應用中的不一致問題。最后通過實例對新算法和傳統算法進行了比較與分析。

關鍵詞:未確知理論; 聚類; 軟件可靠性; 模型

中圖分類號:TP311文獻標志碼:A

文章編號:1001-3695(2009)09-3378-03

doi:10.3969/j.issn.1001-3695.2009.09.050

Research on software reliability model based on unascertained clustering

BAO Guo-min HAN-ke LI Hua-ying2

(1.Management Team of Graduate Student， PLA Academy of Communication Command， Wuhan 430010， China; 2.Institute of China Electronic System Equipment Company，Beijing 100141， China)

Abstract:Software reliability is one of the important indexes of software quality. In traditional software reliability model， the behavior of software reliability growth was abstracted and simplified through some precise and unambiguous assumptions. Software reliability was researched by the way of integrating unascertained theory and clustering， discarding all kinds of assumptions of distribution in software fault process and improving the incongruence of model application to some extent. Finally， the new and traditional arithmetic were compared and analyzed with an example.

Key words:unascertained theory;clustering;software reliability;model

0 引言

軟件平均無故障時間(mean time between failures， MTBF)是指相鄰兩次失效時間間隔的均值。計算軟件MTBF是軟件可靠性研究的重要內容，一般方法是通過建立軟件可靠性模型進行計算。一般步驟是:收集軟件失效的數據，提出軟件可靠性模型，進行軟件MTBF估計及驗證。其做法是:根據軟件可靠性模型和實驗所得到的數據建立聯合密度函數，并運用極大似然或最小二乘法進行參數估計[1]。傳統的軟件可靠性模型一般建立在經典的概率統計基礎之上，通過一些精確、無歧義的假設，對復雜的軟件可靠性增長行為進行抽象和簡化，從而建立預測模型，如J-M模型和S-W模型。假定軟件故障過程服從二項分布，G-O模型假定軟件故障過程服從泊松分布，J-M模型認為失效率按幾何衰減，G-O模型則認為失效率是按指數衰減的。然而，軟件產品不像實體產品受溫度、濕度、磨損及老化的作用，失效率按規律變化，軟件的故障過程不總是服從這些分布，而傳統模型恰恰希望故障過程服從特定的分布，失效率按一定的規律衰減。這樣，只有某一工程項目的故障過程和失效率是按模型假設的規律變化時，模型的精度才會很高，一旦工程項目的故障過程不按這些規律變化時，模型的精度就會變得很糟，此時估計結果難以令人置信[2]。本文給出的用未確知理論和聚類方法結合起來計算軟件MTBF的方法，將擺脫各種對故障過程分布和失效率變化規律的假定，不僅算法簡單而且具有良好的適用性，適用于各種具有不同特性故障過程的工程項目。

1 利用未確知數學計算軟件MTBF

定義[3] 對任意閉區間[a，b]，a=x1

φ(x)=αi x=xi(i=1，2，NA1AD，n)0 其他

且∑ni=1αi=α，0<α≤1，則稱[a，b]和φ(x)構成一個n階未確知有理數，記做[[a，b]，φ(x)]，稱α、[a，b]和φ(x)分別為該未確知有理數的總可信度、取值區間和可信度分布函數。

設A為上式表達的未確知有理數，稱一階未確知有理數

E(A)=[[(1/α)∑ki=1xiαi，(1/α)∑ki=1xiα]，φ(x)]

φ(x)=αi x=xi(i=1，2，NA1AD，n)0 其他

為未確知有理數A的數學期望，也稱E(A)為未確知期望，簡稱期望或均值[3]。

軟件可靠性未確知模型將第i-1次失效為起點到第i次失效發生的時間看做是一個未確知有理數xi，即時刻t的平均失效時間間隔為E(xi)。其中，t是第i-1次失效到第i次失效之間的任意時刻。本文只討論一步預測，那么軟件可靠性未確知模型如下(軟件失效間隔時間分別為xl，x2，…，xn，失效時間分別為tl，t2， …，tn，其中xi=ti-ti-1，i=1，2， …，n，t0=0):

xi={[xmin，xmax]，φ(xi)}

其中:xmin=min(xi-1，xi-2， …，xi-m)，xmax=max(xi-1，xi-2， …，xi-m);m為參與運算的失效數據個數，一個待定常數。對確認測試可取i-1，對可靠性測試筆者認為早期數據對預測未來行為作用很小，現時失效間隔數據比許久之前觀測的失效間隔數值更好地預測未來，m一般取8～10。φ(xi)是xi的可信度密度分布函數。定義φ(xi)，若xj鄰域內xk多，則認為xi取值xj的可信度大;反之認為xi取值xj的可信度很小。其中:j，k=i-m， …，i-1，且j≠k。具體定義為

φ(xi)=ξi/ξx=xi(i=1，2，NA1AD，n)0 其他

其中:ξj表示xj鄰域|xj-xk|≤r中包含xk(j≠k)的個數，ξ=∑i-1j=i-mξj，r為xj的鄰域半徑，可憑經驗由失效數據估計出來，應注意在此過程中r是不斷調整的[4]。xi通過下式求得:

E(xi)=∑i-1j=i-mxjξj/ξ

其中ξ=∑i-1j=i-mξj。xi的數學期望E(xi)為時刻t的MTBF，其中，t是第i-1次失效到第i次失效之間的任一時刻。在穩定使用軟件且不對軟件作任何修改的情況下，軟件的失效強度為一常數，其值為1/MTBF。因此，在相鄰兩次失效時間間隔內，失效強度與MTBF的關系為

E(xi)=MTBF=1/λ

即λ=1/E(xi)

其中，以第i-1次失效為起點到第i次失效發生的時間xi的密度函數為

f(xi)=(1/E(xi))exp{-xi/E(xi)}

分布函數為

F(xi)=1-exp{-xi/E(xi)}

可靠性函數為

R(xi)=exp{-xi/E(xi)}

2 聚類分析基礎

聚類分析是數據挖掘的核心技術，是指按照事物間的相似性對事物進行區分和分類的過程。通過聚類分析，使輸入的一組未分類且事先不知道如何分類以及分成幾類的數據合理劃分數據集，把相似性大的數據聚集為一個族。聚類的標準是使族內相似度盡可能大、族間相似度盡可能小[5，6]。

數據聚類需要解決的問題是將已給定的若干無標記的模式聚集起來使其成為有意義的聚類，之前并不知道數據庫中存在多少類。聚類是要將相近相似的對象聚成一類。其相似程度需要定義一些分類統計量作為分類的衡量指標，常用的分類統計量有距離和相似系數。通常選取距離作為分類標準，一般有明氏距離、馬氏距離等。目前，主要的聚類方法可以分成劃分方法、層次方法、基于密度的方法、基于網格的方法和基于模型的方法。層次聚類方法是聚類分析的一個重要方法，這種方法對給定的數據集合進行層次的分解，根據層次的分解如何形成，又可分為凝聚法(也稱自底向上方法)和分裂法(也稱為從上至下方法)[7，8]。

根據軟件失效數據的趨勢分析和時序特征，選用層次聚類的凝聚法進行同類故障密度的失效數據的聚類，然后對聚類結果用未確知理論分析。該模型以優越的曲線擬合度來精確反映軟件可靠性測試期間的短期可靠性，并在此基礎上選取聚類質心作為新的數據樣本進行軟件可靠性失效時間間隔估計。

凝聚法采用自底向上的策略，首先把每一個對象單獨作為一個聚類，然后根據一定的規則合并成為越來越大的聚類，直到所有的對象都歸入到一個類中或滿足一定的中止條件為止。

2.1 基本概念

定義1 聚類的質心[8]。設G為某類算法下的某一類，Xi(i=1，2，…，m)為該G類下的有限元素，則該G類質心定義為

G=1m∑mi=1Xi

定義2 類間距離[8]。聚類是將最靠近的樣本進行聚類，因此對類間距離的定義是決定聚類效果的關鍵步驟。兩類之間的距離定義為兩類的質心間的距離;類間平均距離定義為兩類中各元素兩兩之間的平均距離;最小距離定義為兩類中最靠近的兩個元素間的距離;最長距離定義為兩個類中最遠的兩個元素間的距離;

2.2 聚類的質量評定指標

定義3 類的內聚度[8]。設類G(d1，d2，…，dn)的平均距離mean_dis=2k(k-1)∑ki=1∑kj=i+1D(di，dj)，則G的內聚度iner(G)=max G/mean_dis。其中，maxG為G內元素之間的最大距離。內聚度的值越大說明聚類內元素的相似性越好，該種聚類效果也就相對地越好。

定義4 類的相異度[8]是指類間最小距離的平均值。當相異度急劇下降時，說明具有不同特征的元素被歸入了相同的一類，則聚類的質量就會下降。

2.3 相似性度量

分層聚類法的基本思想是根據物體的某些屬性把這些物體按類分組，首先將每個樣本當做一類;然后根據樣本之間的相似程度并類，且計算新類與其他類之間的距離;再選相近者并類，每合并一次，便減少一類。這些屬性被稱為聚類過程的相似性度量。在本節中，相似性度量選取故障密度f(xi)，因為f(xi)=λiexp(-λixi)，對于已經發生的觀察數據，λixi=1，所以f(xi)=λiexp(-λixi)=λiexp(-1)。因此，對于已經發生的觀察數據，故障密度f(xi)和失效率λi在分析問題時是等價的。為了分析的方便，稱λi為故障密度，且λi=1/xi;或者只知道ti和fi的情況下，可近似地求出λi=fi/ti，ti是第i聚類的時間片段，fi是該時間片段內的故障數，i=1，2，…。

3 基于未確知聚類的軟件可靠性模型的算法實現

本算法為選取的失效數據為軟件失效時間間隔，以分層聚類的最短距離法進行處理。

a)以各點為一類，計算各點的故障密度，并計算初始類的相異度η0;

b)計算任意類的故障密度的差值，建立相似度矩陣;

c)選取最小故障密度差值，將其兩類合并成一類，并且計算所得新類的合并次數;

d)計算新的聚類下得到新的各類的故障密度;

e)計算新的聚類的相異度Δη;

f)重復b)，直到Δη≥k0×η0，轉g)(k0×η0為聚類中止條件閾值，0

g)運用未確知理論對結果進行分析，計算最后的λi，求出xi=1/λi。

從上面算法實現的步驟可以看出，對于未參與聚類的數據，其在最后結果中將被淘汰;對于某一個結果是通過多次聚類得到的，在最后結果的計算中其權重將被分配得大些。這樣可以很好的避開孤點，同時對于數據密集區域重視，即認為預測值取數據密集區域值的可能性大，取數據稀疏區域值的可能性小，取孤點值的可能性為零。

具體步驟如下:

a)初始化類。init_cluster=(Xi)，計算初始類的相異度Δη=η0/*i=k-m，k-m+1，…，k-1;m為參與運算的故障數，k為預測的第k個故障，即用k前面的m個故障的數據來預測第k個故障的數據初始時每個故障為一類*/

b)while(Δη≤0.2×η0)，轉c);否則，轉h)。

c)計算各類質心的故障密度均值:當k>1時，i=1k∑kj=1λj;當k=1時，i=λi。

d)計算任意兩類質心的故障密度均值的差值Δij=i-j，建立相似度矩陣:

ik-mk-m+1k-m+2NA1ADk-2k-1k-m0Δk-m，k-m+1Δk-m，k-m+2NA1ADΔk-m，k-2Δk-m，k-1k-m+10Δk-m+1，k-m+2NA1ADΔk-m+1，k-2Δk-m+1，k-1k-m+20NA1ADΔk-m+2，k-2Δk-m+2，k-1NA1AD0NA1ADNA1ADk-20Δk-2，k-1k-10

矩陣關于對角線對稱，所以只寫出對角線上半部分。

e)選取最小的Δij，則將第i類和第j類進行合并稱為新的第i類，記住新i類的合并次數，同時去掉第j類。

f)更新聚類:cluster=cluster-{j}。

g)計算更新類后的新的聚類的相異度Δη，轉b)。

h)計算經過聚類的i及其聚類的次數，求出最后的，令λk=，則xk=1/λk=1//*xk為第k-1個失效數據到第k個失效數據的時間間隔*/

4 算法驗證

采用美國海軍艦隊計算機程序設計中心(U.S.Navy Fleet Computer Programming Center)的海軍戰術數據系統NTDS(Naval Tactical Data System)開發過程(前26組數據)和測試過程(27~30組數據)中的錯誤統計數據，對未確知聚類模型短期預測能力進行評價。

針對軟件失效間隔時間序列NTDS，應用傳統軟件可靠性模型G-O模型、J-M模型、未確知模型與未確知聚類模型短期預測能力進行比較。目前已經推薦出幾個有顯著性檢驗的變量標準，在此應用Jasson在1998年提出的度量元(SRE)來度量模型的短期即一步預測能力[11]，期望從模型預計值和實際觀測值的SRE來判斷未確知聚類模型與未確知模型、G-O模型和J-M模型的一步預測能力。計算度量元SRE的公式為

SRE=∑n-1i=1[xr(i+1)-xp(i+1)/xr(i+1)]/(n-1)

使用到ti(i>1)時的失效數據建立模型，計算下一失效間隔時間xi+1和下次出現失效的時間ti+l(i>1)。其中:ti+l=ti+xi+l(i>1)。應注意到在此過程中，用于計算擬合情況時模型參數是不斷進行調整的。其中，xr(i+1)表示實際觀察到的下一失效間隔時間，xp(i+1)表示應用前i個故障數據建立的模型預測的下一失效間隔時間。SRE值越小，說明模型短期預測能力越強，一步向前預測越準確。

對G-O模型、J-M模型、未確知模型和未確知聚類模型分別進行計算:以前i個失效間隔數據為建模數據，預測第i+1個失效的間隔時間。對于NTDS中的數據，則得到27～30個失效數據的一步結果及短期預測能力度量元SRE的值，如表1所示。

比較短期預測能力度量元，SRE(未確知聚類)

未確知聚類模型集中了未確知理論穩健性好和聚類概率密度特性(即認為預測值發生在概率密度大的地方)，該算法由于不對歷史失效數據進行任何人為的假設，更加接近軟件實際故障，具有較高的預計精度，改善了模型應用中的不一致問題。

5 結束語

本文分析了傳統方法計算軟件MTBF的不足及其原因，提出了一種基于未確知數學理論和聚類方法的計算軟件MTBF的新方法。新算法集中了未確知理論和聚類方法的優點，擺脫了對軟件故障過程的各種分布假設，算法簡單、穩健性好，精度較高。因為將未確知理論和聚類方法結合起來用于軟件可靠性的分析、研究中的文獻資料很少，其中還有很多問題值得作進一步的研究。

參考文獻:

[1]董威，毛新軍，陳磊，等.基于agent的軟件可靠性評估系統[J].計算機科學，2000，27(6):28-31.

[2]張永強，孫勝娟.基于未確知理論的軟件可靠性建模[J].軟件學報， 2006，17(8):1681-1687.

[3]劉開第，吳和琴.不確定性信息數學處理及應用[M].北京:科學出版社，1999:43-86.

[4]鮑國民，鄭成文，韓柯.軟件MTBF計算方法研究[J].計算機工程與應用，2008，44(35):37-39.

[5]蔡元翠，陳立潮.聚類算法研究綜述[J]. 科技情報開發與經濟，2007，17(1):145-146.

[6]李朝健，肖建華.常用聚類算法比較分析[J]. 電腦知識與技術，2007(2):471-472.

[7]汪浩，劉超，金茂忠.基于聚類思想的軟件可靠性模型選擇[J].計算機工程與應用，2002，38(21):21-24.

[8]馬颯颯，陳自力，趙守偉.基于聚類的軟件可靠性評估與預測研究[J].計算機應用，2005，25(12):369-371.

[9]UCI KDD archive[EB/OL]. http://kdd.ics.uci.edu.

[10]馮紅偉.數據挖掘技術的研究及應用:基于模式相似性的時間序列數據庫查詢[D]. 西安:西北工業大學，2002.

[11]MICHAEL R L. Handbook of software reliability engineering[M].Columbus:McGraw-Hill Publishing，1995.