一種模糊K-means算法在測(cè)試用例集約簡(jiǎn)中的應(yīng)用

余國(guó)清， 周蘭蓉， 羅可

(1. 長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院， 湖南 長(zhǎng)沙 410114；2. 湖南信息職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程學(xué)院， 湖南 長(zhǎng)沙 410200)

?

一種模糊K-means算法在測(cè)試用例集約簡(jiǎn)中的應(yīng)用

余國(guó)清1,2， 周蘭蓉2， 羅可1

(1. 長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院， 湖南 長(zhǎng)沙 410114；2. 湖南信息職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程學(xué)院， 湖南 長(zhǎng)沙 410200)

為了提高軟件測(cè)試用例集約簡(jiǎn)的成效，提出一種基于模糊K-means的軟件測(cè)試集用例約簡(jiǎn)算法，引入模糊劃分思想，結(jié)合測(cè)試需求集，從各個(gè)簇中抽取測(cè)試用例，盡可能地發(fā)現(xiàn)相似的用例.實(shí)驗(yàn)結(jié)果表明：算法能夠最小化約簡(jiǎn)用例集，用例集覆蓋范圍最廣泛，錯(cuò)誤率檢測(cè)較高.

用例約簡(jiǎn); 模糊K-means算法; 復(fù)雜度; 軟件測(cè)試

隨著互聯(lián)網(wǎng)、云計(jì)算等技術(shù)的快速發(fā)展，軟件功能及規(guī)模也迅速增大，程序開發(fā)潛在的錯(cuò)誤和漏洞也逐漸增多[1-3].軟件測(cè)試可以在軟件開發(fā)完成之后，使用控制數(shù)據(jù)、加工數(shù)據(jù)等用例進(jìn)行測(cè)試，發(fā)現(xiàn)軟件存在的錯(cuò)誤，保證軟件的完整性、可靠性和準(zhǔn)確性.但是，大規(guī)模軟件需要設(shè)計(jì)較多的測(cè)試用例，造成人工測(cè)試模式定位難度大、耗費(fèi)時(shí)間較長(zhǎng)，不能夠快速定位和修改軟件錯(cuò)誤[4-5].軟件測(cè)試用例約簡(jiǎn)已經(jīng)成為降低軟件測(cè)試用例數(shù)量和提高測(cè)試成效的關(guān)鍵技術(shù)，許多學(xué)者對(duì)其進(jìn)行了研究[6-11]，引入了集合約簡(jiǎn)、關(guān)聯(lián)規(guī)則、專家數(shù)據(jù)庫等技術(shù)，在保持較高測(cè)試準(zhǔn)確度的條件下，大大減少了用例數(shù)量.軟件測(cè)試用例約簡(jiǎn)仍存在用例集規(guī)模較大、用例重復(fù)出現(xiàn)、錯(cuò)誤定位精確度小等問題.本文引入隸屬度函數(shù)改進(jìn)K-means算法，旨在利用模糊數(shù)學(xué)提高軟件測(cè)試用例劃分的準(zhǔn)確度.

1 背景理論

1.1 軟件測(cè)試用例約簡(jiǎn)

測(cè)試用例需要全覆蓋軟件的每一個(gè)步驟和環(huán)節(jié)，針對(duì)每一行代碼進(jìn)行測(cè)試.軟件測(cè)試用例約簡(jiǎn)是指在用例集T中，尋找一個(gè)最簡(jiǎn)化的子集T′，該子集可以滿足所有的測(cè)試任務(wù).

1.2 模糊K-means算法

K-means算法采用硬聚類劃分思想，劃分過程較為武斷，不能夠充分地考慮測(cè)試用例的多個(gè)屬性，導(dǎo)致聚類結(jié)果與實(shí)際情況存在偏差.因此，為了能夠提高K-means算法的準(zhǔn)確度，假設(shè)軟件測(cè)試用例共有n個(gè)，每一個(gè)測(cè)試用例使用m個(gè)特征進(jìn)行刻畫，則引入了隸屬度函數(shù)，使用隸屬度刻畫測(cè)試用例歸屬，提高數(shù)據(jù)對(duì)象劃分準(zhǔn)確性，易于解釋和描述．軟件測(cè)試用例為

(1)

式(1)中：xi，j表示樣本j的特征i，j=1,2,…,n，i=1,2,…,m.為了能夠更好的保證K-means算法正確執(zhí)行，算法運(yùn)行之前需要對(duì)其檢修歸一化處理，即

(2)

式(2)中： xi，max表示第i個(gè)指標(biāo)特征的最大取值；xi，min表示第i個(gè)指標(biāo)特征的最小取值；ri，j表示歸一化后xi，j的取值.軟件測(cè)試用例集矩陣X歸一化之后為

(3)

軟件測(cè)試用例集X假設(shè)存在C個(gè)類別，則數(shù)據(jù)集X可以使用模糊識(shí)別矩陣進(jìn)行描述，即

(4)

假設(shè)軟件測(cè)試樣本劃分類別h的m個(gè)特征向量值作為K-means算法的中心數(shù)據(jù)，則一個(gè)具有X個(gè)類別的軟件測(cè)試用例集擁有C個(gè)模糊聚類中心，即

(5)

式(5)中：si，h為類別h指標(biāo)i的歸一化特征值，0≤si，h≤1.

為了滿足不同的聚類用戶處理需求，在模糊聚類執(zhí)行過程中，可以針對(duì)不同的劃分設(shè)置不同的特征權(quán)值，以便能夠突出某些特征屬性的貢獻(xiàn)度，即

(6)

模糊K-means算法的目標(biāo)函數(shù)形式為

(7)

2 在測(cè)試用例機(jī)約簡(jiǎn)中的應(yīng)用

在模糊K-means算法中，假設(shè)軟件測(cè)試用例集為T={t1,t2,…,tn}，數(shù)據(jù)集擁有的類別數(shù)目為K個(gè)，mi為第i個(gè)簇的中心，i=1,2,…k.模糊K-means的目標(biāo)函數(shù)為

(8)

式(8)中：b為一個(gè)常數(shù)，可以控制模糊K-means隸屬度.通過對(duì)模糊K-means的隸屬度函數(shù)求導(dǎo)數(shù)，可以獲取模糊K-means算法的最優(yōu)解，最優(yōu)解的求解過程分別為

(9)

(10)

模糊K-means算法使用程序，迭代執(zhí)行最優(yōu)化求解式(9)，(10)，可以針對(duì)軟件測(cè)試用例集進(jìn)行劃分.具體的算法偽代碼流程如下.算法輸入：軟件測(cè)試用例約簡(jiǎn)類簇?cái)?shù)目K，隸屬度控制常數(shù)參數(shù)b，N個(gè)數(shù)據(jù)對(duì)象的軟件測(cè)試用例集.算法輸出：軟件測(cè)試用例約簡(jiǎn)后的K個(gè)簇.算法有以下4個(gè)步驟.

步驟1 隨機(jī)化的將N個(gè)軟件測(cè)試用例分配到K個(gè)簇中，分派每一個(gè)簇的中心特征向量為mi.

步驟2 使用式(10)準(zhǔn)確計(jì)算獲取軟件測(cè)試用例的隸屬度函數(shù).

步驟3 使用式(9)重新計(jì)算軟件測(cè)試用例簇的中心值mi.

步驟4 計(jì)算每一個(gè)數(shù)據(jù)對(duì)象的隸屬度，直到隸屬度不再變化，終止算法運(yùn)行；否則，返回步驟2.

由于在K-means算法基礎(chǔ)上，引入模糊控制b，可以根據(jù)模糊控制因子的取值經(jīng)驗(yàn).當(dāng)b=0.75時(shí)，能夠取得較好的約簡(jiǎn)效果.基于此，可以分析測(cè)試用例的屬性相近程度.

3 實(shí)驗(yàn)結(jié)果分析

3.1 數(shù)據(jù)集

采用SiemensCorporateResearch提供的軟件測(cè)試公共數(shù)據(jù)集，數(shù)據(jù)集1,2,3包含的用例數(shù)為30；數(shù)據(jù)集4,5,6,7包含的用例數(shù)為32.

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

約簡(jiǎn)算法的評(píng)價(jià)標(biāo)準(zhǔn)有算法約簡(jiǎn)率(SR)、軟件錯(cuò)誤檢測(cè)率(FDE)、軟件錯(cuò)誤檢測(cè)丟失率(FL)3個(gè)方法，分別表示為

圖1 3種算法約簡(jiǎn)率Fig.1 Three algorithms reduction rate

其中：|T|為軟件測(cè)試用例集的元素?cái)?shù)；|T′|為約簡(jiǎn)算法約簡(jiǎn)后的軟件測(cè)試用例集中的元素?cái)?shù)；|F|為未約簡(jiǎn)的用例集測(cè)試軟件功能時(shí)檢測(cè)出來的錯(cuò)誤數(shù)；|F′|為約簡(jiǎn)后的用例集檢測(cè)出來的軟件功能錯(cuò)誤數(shù).

3.3 結(jié)果分析

1) 約簡(jiǎn)率比較.3種算法約簡(jiǎn)率，如圖1所示.模糊K-means算法引入了模糊控制因子，可以動(dòng)態(tài)地調(diào)整隸屬度特征權(quán)重，將概率值較為接近的軟件測(cè)試用例劃分到一起，在保證全覆蓋的條件下，可以有效提高K-means算法的約簡(jiǎn)率，降低軟件測(cè)試的復(fù)雜度和工作量.

2) 軟件錯(cuò)誤檢測(cè)率比較.3種算法檢錯(cuò)率，如圖2所示.模糊K均值算法約簡(jiǎn)后的測(cè)試用例能夠檢測(cè)出更多軟件錯(cuò)誤數(shù)，表明文中算法約簡(jiǎn)后的依然可以保持全覆蓋能力.另外兩種算法約簡(jiǎn)后，把一些測(cè)試功能不同的用例劃分到一個(gè)簇中，這樣造成約簡(jiǎn)后的用例無法全覆蓋軟件功能，錯(cuò)誤檢測(cè)率較低.

3) 錯(cuò)誤檢測(cè)丟失率比較.3種算法的錯(cuò)誤檢測(cè)丟失率，如圖3所示.由圖3可知：矩陣行列變換算法、關(guān)聯(lián)模式約簡(jiǎn)算法非常容易將不同覆蓋類型的用例約簡(jiǎn)掉，因此，漏檢率較低，算法約簡(jiǎn)效果不好.

圖2 3種算法檢錯(cuò)率 圖3 3種算法錯(cuò)誤檢測(cè)丟失率Fig.2 Three algorithms error rate Fig.3 Three algorithms error detection loss rate

4 結(jié)束語

在K-means算法中引入了隸屬度函數(shù)，采用模糊數(shù)學(xué)思想提高K-means算法劃分軟件測(cè)試用例集，可以提高用例約簡(jiǎn)數(shù)量，并且保持用例集檢測(cè)軟件錯(cuò)誤的可靠性.未來研究工作包括兩個(gè)關(guān)鍵內(nèi)容：引入模擬退火理論，實(shí)現(xiàn)模糊控制因子的自動(dòng)化確定;針對(duì)軟件測(cè)試用例集進(jìn)行泛化，提高算法的穩(wěn)定性和魯棒性.

[1] KUMAR G,BHATIA P K.Software testing optimization through test suite reduction using fuzzy clustering[J].Csi Transactions on Ict,2013,1(3):253-260.

[2] PAKINAM N B,NAGWA L B,MOHAMED H,et al.Test case generation and test data extraction techniques[J].International Journal of Electrical and Computer Sciences,2011,24(5):112-119.

[3] SUN F,TONG X H,XUE S F.A study of relative redundancy in test-suite reduction while retaining or improving fault-localization effectiveness[C]∥Proceedings of the 2010 ACM Symposium on Applied Computing.[S.l.]:ACM,2010:2229-2236.

[4] HAO D,XIE T,ZHANG L,et al.Test input reduction for result inspection to facilitate fault localization[J].Automated Software Engineering,2010,17(1):5-31.

[5] GONG Hongfang,LI Junyi.Generating test cases of cluster-level based on classes dependencies reduction[J].Jouranl of Central South University: Science and Technology,2010,41(1):238-244.

[6] GU Qing,TANG Bao,CHEN Daoxu.A test suite reduction technique for partial coverage of test requirements[J].Chinese Journal of Computers,2011,34(5):879-888.

[7] CHEN Jing,YANG Meihong,WANG Lu,et al.Regression test case reduction model based on association mode[J].Computer Engineering,2011,37(2):63-65.

[8] ZHOU Chongbo,LOU Jungang,CHENG Long.Test suites reduction based on matrix transformation[J].Application Research of Computer,2013,30(3):779-782.

[9] CHEN Yangmei,DING Xiaoming.Test suite reduction methods based on K-medoids[J].Computer Science,2012,39(6):422-424.

[10] SU Xiaohong,GONG Dandan,WANG Tiantian,et al.Automatic fault localization approach combining test case reduction and joint dependency probabilistic model[J].Journal of Software,2014,25(7):1492-1504.

[11] 劉竹松,陳潔.考慮數(shù)據(jù)不確定性的非均勻挖掘算法[J].華僑大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,37(3):308-311.

(責(zé)任編輯： 陳志賢 英文審校： 吳逢鐵)

FuzzyK-Means Algorithm of Software Testing Using Case Reduction

YU Guoqing1,2, ZHOU Lanrong2, LUO Ke1

(1. Deptment of Computer and Communication Engineering,Changsha University of Science and Technology, Changsha 410114, China;2. School of Computer Engineering, Hunan College of Information Technology, Changsha 410200, China)

To improve the effectiveness of the software test set reduction, a software test set case reduction algorithm based on fuzzyKmeans is proposed. The fuzzy partition idea is introduced. The test suite is extracted from each cluster, finded similar cases. Experimental results showed that the algorithm can minimize the reduction case set, covers the most extensive and highly detect the error rate.

case reduction; fuzzyK-means software testing; complexity; software testing

10.11830/ISSN.1000-5013.201606024

2016-10-20

余國(guó)清(1971-)，男，副教授，主要從事人工智能、智能控制、數(shù)據(jù)挖掘的研究.E-mail:yuguoqing@mail.hniu.cn.

湖南省科學(xué)技術(shù)計(jì)劃項(xiàng)目(2011FJ3086)

TP 311

A

1000-5013(2016)06-0778-04