K-means聚類算法在回歸測(cè)試用例選擇中的應(yīng)用

1、基于判別型半監(jiān)督K-means聚類方法的回歸測(cè)試用例選擇技術(shù)程雪梅【摘要】回歸測(cè)試的目的是保證修改過(guò)后的軟件沒(méi)有引入新的錯(cuò)誤。但是隨著軟件的演化，回歸測(cè)試用例集不斷增大，為了控制成本，回歸測(cè)試用例選擇技術(shù)應(yīng)運(yùn)而生。近年來(lái)，聚類分析技術(shù)被運(yùn)用到回歸測(cè)試用例選擇問(wèn)題中。其基本思想為：根據(jù)測(cè)試用例的歷史執(zhí)行剖面進(jìn)行聚類，將具有相似的函數(shù)覆蓋、能夠發(fā)現(xiàn)相同故障的測(cè)試用例聚為一個(gè)簇。然后通過(guò)取樣策略從每一簇中選出一定比例的測(cè)試用例組成新的測(cè)試用例集。將半監(jiān)督學(xué)習(xí)引入到聚類技術(shù)中，提出了判別型半監(jiān)督K-means 聚類方法(Discriminative Semi-supervised K-means ,簡(jiǎn)

2、稱DSKM),該方法通過(guò)從回歸測(cè)試的歷史執(zhí)行記錄中挖掘出隱藏的成對(duì)約束信息，同時(shí)利 用大量的無(wú)標(biāo)簽樣本和少量的有標(biāo)簽樣本進(jìn)行學(xué)習(xí)，從而優(yōu)化聚類的結(jié)果，進(jìn)一步優(yōu)化測(cè)試用例選擇的結(jié)果。通過(guò)實(shí)驗(yàn)，發(fā)現(xiàn)相對(duì)于普通的K-means算法，DSKM方法在保持較高的召回率和代碼覆蓋率的前提下，準(zhǔn)確率和約簡(jiǎn)率都有明顯的提高?！娟P(guān)鍵詞】回歸測(cè)試測(cè)試用例選擇 K-means算法成對(duì)約束線性判別分析1引言在軟件開發(fā)的過(guò)程中，軟件系統(tǒng)及其環(huán)境在不斷地進(jìn)行變化。增強(qiáng)功能、糾正錯(cuò)誤、新增或者刪除功能，都需要修改代碼并觸發(fā)軟件的演化。為了確保演化后的軟件能夠正確運(yùn)行并且新的改變沒(méi)有引入新的錯(cuò)誤，必須對(duì)軟件進(jìn)行回歸測(cè)試1。統(tǒng)計(jì)

3、數(shù)據(jù)表明，回歸測(cè)試開銷一般占整個(gè)軟件測(cè)試預(yù)算的80%以上，占整個(gè)軟件維護(hù)預(yù)算的 50%以上，因此有效的回歸測(cè)試是非常重要的2。然而，隨著軟件的不斷演化，測(cè)試用例集不斷增大，由于資源有 限，幾乎不可能運(yùn)行所有的測(cè)試用例。為了提高回歸測(cè)試的運(yùn)行效率，許多策略被提出，其中最主要的一種技術(shù)是回歸測(cè)試用例選擇技術(shù)3 (Regression Test Case Selection簡(jiǎn)稱RTS。近年來(lái)，數(shù)據(jù)挖掘中的聚類技術(shù)被用于解決回歸測(cè)試用例選擇問(wèn)題。其基本思想是：根據(jù)測(cè)試用例的歷史執(zhí)行剖面進(jìn)行聚類，將具有相似的函數(shù)覆蓋、能夠發(fā)現(xiàn)相同故障的測(cè)試用例聚為一個(gè)簇。同一簇中的測(cè)試用例具有相似的行為，而不同簇中的測(cè)

4、試用例的行為差異較大。若一個(gè)測(cè)試用例能檢測(cè)某一故障，則屬于同一簇的其他測(cè)試用例通常也能檢測(cè)到這一故障1。在回歸測(cè)試時(shí)，只需從每一簇中選取一定比例的測(cè)試用例組成新的測(cè)試用例集，新 測(cè)試用例集的精度和覆蓋率在很大程度上依賴于聚類結(jié)果，而聚類結(jié)果依賴于聚類算法的選取。傳統(tǒng)的K-means聚類算法是無(wú)監(jiān)督的，對(duì)選取的K值和初始的簇中心都非常敏感，可能會(huì)產(chǎn)生局部最優(yōu)的聚類結(jié)果，從而導(dǎo)致選擇出的測(cè)試用例無(wú)法滿足較高的準(zhǔn)確率和覆蓋率。 為了優(yōu)化聚類結(jié)果，論文提出一種判別型半監(jiān)督K-means聚類方法(DiscriminativeSemi-supervised K-means ,簡(jiǎn)稱DSKM),將半監(jiān)督聚類運(yùn)

5、用到回歸測(cè)試用例選擇中。在保證測(cè)試用例覆蓋率的同時(shí)，減少測(cè)試用例，從而縮減回歸測(cè)試的成本，提高回歸測(cè)試的效率。論文第1部分介紹了研究背景， 提出研究的問(wèn)題。第2部分對(duì)目前該領(lǐng)域的相關(guān)研究進(jìn) 行總結(jié)。第3部分對(duì)論文提出的方法進(jìn)行了介紹。第4部分通過(guò)設(shè)計(jì)和執(zhí)行實(shí)驗(yàn)，驗(yàn)證提出的方法。第5部分對(duì)論文進(jìn)行總結(jié)，提出未來(lái)工作。2相關(guān)工作針對(duì)RTS問(wèn)題的研究，眾多研究人員提出了很多的解決方案4。Rothermel和Harrolad首次對(duì)RTS問(wèn)題進(jìn)行了總結(jié)并提出一種統(tǒng)一評(píng)估框架3, 5,隨后提出一種基于控制流圖的 RT誠(chéng)術(shù)并開發(fā)出 DejaVu工具。Beydeda和Gruhn基于Rothermel等人 的研

6、究工作，通過(guò)將黑盒測(cè)試中的數(shù)據(jù)流信息添加到類控制流圖來(lái)對(duì)面向?qū)ο蟪绦蜻M(jìn)行測(cè) i6。Harrold和Sofia提出了一種適用于單元測(cè)試階段的增量數(shù)據(jù)流分析法7。Gupta等人基于數(shù)據(jù)流分析法，應(yīng)用程序切片技術(shù)識(shí)別出與代碼修改存在依賴關(guān)系的 定義使用對(duì)(Definition-Use Pair) 8, 9,該方法在執(zhí)行時(shí)間和存儲(chǔ)空間上均具有一定優(yōu)勢(shì)。H. K. N. Leung等人則在軟件集成的回歸測(cè)試中引入防火墻”技術(shù)11。近年來(lái)，隨著計(jì)算機(jī)軟硬件性能的不斷提高，有不少學(xué)者將聚類技術(shù)用于RTS問(wèn)題。Dickinson等人提出基于執(zhí)行剖面聚類的測(cè)試用例選擇，挖掘出測(cè)試用例之間隱藏的聯(lián)系 10。Mas

7、ri等人進(jìn)行了一項(xiàng)實(shí)證研究，用來(lái)驗(yàn)證聚類過(guò)濾技術(shù)的有效性11。Zhang等人在Rothermel的基礎(chǔ)上，通過(guò)對(duì)遍歷測(cè)試修改的執(zhí)行剖面進(jìn)行聚類，增強(qiáng)了安全選擇技術(shù)1。Shin等人提出了基于聚類的測(cè)試用例優(yōu)先級(jí)技術(shù)，用來(lái)減少成對(duì)比較的數(shù)量12。C. Songyu等人率先將半監(jiān)督聚類運(yùn)用到回歸測(cè)試用例選擇的問(wèn)題上，利用測(cè)試用例的函數(shù)覆蓋信息對(duì)測(cè)試用例進(jìn)行聚類，從而減少測(cè)試用例13。使用聚類技術(shù)解決 RTS問(wèn)題，可以在保證測(cè)試用例的錯(cuò)誤檢測(cè)能力和覆蓋率的前提下， 提高測(cè)試用例的約簡(jiǎn)率1,14。但目前已有的方法大部分都是非監(jiān)督的，利用無(wú)標(biāo)簽數(shù)據(jù)進(jìn)行訓(xùn)練和組織數(shù)據(jù)，聚類的結(jié)果依賴于目標(biāo)函數(shù)的設(shè)定和參數(shù)的

8、輸入，而這些參數(shù)往往是需要人工設(shè)置的。由于軟件系統(tǒng)的復(fù)雜性和多樣性，在參數(shù)設(shè)置方面比較困難，獲得的聚類效果也難以得到保證。尹學(xué)松等人提出了基于成對(duì)約束的判別型半監(jiān)督聚類分析方法15。論文將這種聚類方法 用于解決回歸測(cè)試用例選擇問(wèn)題，可以優(yōu)化回歸測(cè)試用例選擇的結(jié)果。3基于DSKM的測(cè)試用例選擇方法隨著數(shù)據(jù)挖掘技術(shù)在軟件測(cè)試中的應(yīng)用，基于聚類的測(cè)試用例選擇技術(shù)被證明能夠有效地減少測(cè)試用例1, 13, 14, 16, 17。聚類的目標(biāo)是將能夠發(fā)現(xiàn)相同故障、覆蓋到相似函數(shù)的測(cè)試用例聚到同一簇中。然而，簡(jiǎn)單的聚類算法結(jié)果并不是滿意的，論文使用了DSKM方法對(duì)聚類結(jié)果進(jìn)行優(yōu)化。 一方面保證測(cè)試用例的錯(cuò)誤檢

9、測(cè)能力和覆蓋率，另一方面，提高測(cè)試用例選擇的準(zhǔn)確率和約簡(jiǎn)率。3.1 整體流程基于DSKM的測(cè)試用例選擇方法主要包括數(shù)據(jù)提取、約束推導(dǎo)、數(shù)據(jù)降維、數(shù)據(jù)聚類、 用例取樣五個(gè)部分，如圖 3-1所示。DSKM方法首先通過(guò)分析測(cè)試用例對(duì)函數(shù)的覆蓋情況得 到原始數(shù)據(jù)集，即測(cè)試用例與其覆蓋函數(shù)的二進(jìn)制向量組成的二維表。然后將從測(cè)試用例執(zhí)行歷史記錄中挖掘出的成對(duì)約束作為輸入，使用SSDR (Semi-Supervised DimensionalityReduction)算法18得到投影矩陣，在投影空間內(nèi)對(duì)原始數(shù)據(jù)聚類得到聚類標(biāo)號(hào)。接著再將聚類標(biāo)號(hào)作為輸入，利用線性判別分析( Linear Discrimina

10、nt Analysis ,簡(jiǎn)稱LDA)選擇子空間， 在子空間上對(duì)數(shù)據(jù)集進(jìn)行投影，得到新的數(shù)據(jù)集，即降維過(guò)后的二維表。最后使用K-means 算法對(duì)新的數(shù)據(jù)集進(jìn)行聚類，將測(cè)試用例聚為 K簇，使用自適應(yīng)的取樣策略從每一簇中選出一定比率的測(cè)試用例組成新的測(cè)試用例集。該方法結(jié)合SSDRT法和LDA方法對(duì)聚類結(jié)果進(jìn)行優(yōu)化。3.2 數(shù)據(jù)提取本階段進(jìn)行原始數(shù)據(jù)集收集。在測(cè)試用例執(zhí)行過(guò)程中， 其執(zhí)行結(jié)果會(huì)被記錄。 使用代碼覆蓋率分析工具對(duì)每個(gè)測(cè)試用例的代碼覆蓋情況進(jìn)行分析。使用一個(gè)二進(jìn)制向量表示測(cè)試用例的函數(shù)覆蓋，每一位都記錄對(duì)應(yīng)函數(shù)在測(cè)試用例執(zhí)行過(guò)程中是否被覆蓋，如果某個(gè)函數(shù)被覆蓋，該位被置為1,否則，置為

11、0。最終得到測(cè)試用例與其覆蓋的函數(shù)組成的二維表，即 原始數(shù)據(jù)集。得到的原始數(shù)據(jù)集表示為 X=,其中X【表示測(cè)試用例i對(duì)應(yīng)的函數(shù) 覆蓋的二進(jìn)制向量，每個(gè) 由代表一個(gè)數(shù)據(jù)對(duì)象3.3 約束推導(dǎo)在半監(jiān)督聚得到原始數(shù)據(jù)集 X以后，使用測(cè)試用例執(zhí)行歷史記錄推導(dǎo)出成對(duì)約束信息。論文使用兩種類型的成對(duì)約類中，通過(guò)數(shù)據(jù)標(biāo)簽或者數(shù)據(jù)間的約束的形式使用有限的監(jiān)督。束(Pairwise Constraints)來(lái)表示測(cè)試用例之間的約束關(guān)系18。1) Must-link :兩個(gè)測(cè)試用例必須在同一簇中。2) Cannot-link :兩個(gè)測(cè)試用例必須在不同的簇中。經(jīng)過(guò)約束推導(dǎo)，得到約束集M和C。M代表Must-link約

12、束集，C代表Cannot-link約束集。3.4數(shù)據(jù)降維在對(duì)測(cè)試用例進(jìn)行聚類以前，結(jié)合SSDR方法和LDA方法對(duì)提取的數(shù)據(jù)集進(jìn)行降維處理。首先，利用SSDR方法求出投影矩陣 W,在投影空間內(nèi)對(duì)數(shù)據(jù)集聚類得到聚類標(biāo)號(hào)。然后利用LDA方法選擇子空間。在子空間上對(duì)數(shù)據(jù)集進(jìn)行投影，得到新的數(shù)據(jù)集，即降維過(guò)后的 二維表。SSDR(Semi-Supervised Dimensionality Reduction )將原始數(shù)據(jù)集X、約束集M和C作為輸入，利用 SSDRM法18生成變換矩陣W =然后使用 W矩陣將原始數(shù)據(jù)集 X轉(zhuǎn)換為低維度數(shù)據(jù)集Y =其中的=WT%i，y可以在保持原始數(shù)據(jù)集 x的數(shù)據(jù)結(jié)構(gòu)不變的

13、同時(shí)具有更適合的距離空間。新的距離空間的數(shù)據(jù)對(duì)象更適合用于聚類。SSDRB法通過(guò)公式1求解W矩陣，所求 W矩陣為使目標(biāo)函數(shù)(2)最大化的 W的值，其中臚修二1公式1公式1中，口表示數(shù)據(jù)集X中所有數(shù)據(jù)對(duì)象的數(shù)量，制1表示屬于Cannot-link約束集中 的數(shù)據(jù)對(duì)象的數(shù)量，表示屬于Must-link約束集中的數(shù)據(jù)對(duì)象的數(shù)量。第一項(xiàng)表示所有數(shù)據(jù)對(duì)象的平均平方距離，第二項(xiàng)和第三項(xiàng)表示包含在成對(duì)約束集中的所有數(shù)據(jù)對(duì)象的平均平方距離。為了得到的最大值，盡可能使包含在Cannot-link約束集中的數(shù)據(jù)實(shí)例的平均平方距離最大，同時(shí)包含在Must-link約束集中的數(shù)據(jù)實(shí)例的平均平方距離最小。通過(guò)公式1,將

14、Cannot-link約束集中數(shù)據(jù)實(shí)例間的距離增大，同時(shí)將 Must-link約束集中的數(shù)據(jù)實(shí)例間的 距離減小，從而保證屬于Must-link約束集中的測(cè)試用例被聚到同一簇中，而屬于Cannot-link約束集中的測(cè)試用例被聚到不同簇中。在上式中，使用了兩個(gè)參數(shù) a和&用來(lái)平衡約束的權(quán)重，a與3的比值會(huì)影響到聚類的結(jié)果。經(jīng)過(guò)SSDR方法求出投影矩陣 W以后，利用 W矩陣將原始數(shù)據(jù)集 X投影到低維空間， 得到數(shù)據(jù)集Y,并使用傳統(tǒng)的K-means聚類算法對(duì)數(shù)據(jù)集 Y進(jìn)行聚類，得到每個(gè)測(cè)試用例的 聚類標(biāo)號(hào)組成的向量 Labels,便于下一步使用 LDA選擇子空間。LDA （ Linear D

15、iscriminant Analysis）LDA的目的是最大化類間距離，最小化類內(nèi)距離。使用SSDR方法后得到的聚類標(biāo)號(hào)向量Labels和數(shù)據(jù)集Y作為L(zhǎng)DA方法的輸入，進(jìn)行有監(jiān)督的維數(shù)約簡(jiǎn)處理，得到降維過(guò)后的 新數(shù)據(jù)集X',用于下一步K-means聚類算法的輸入。LDA是監(jiān)督維數(shù)約減方法， 它尋找一個(gè)最優(yōu)的投影方向，使得在投影空間中的不同類數(shù)據(jù)對(duì)象之間距離遠(yuǎn)，而相同類數(shù)據(jù)對(duì)象之間距離近。LDA的目標(biāo)函數(shù)如下：VTSbW叫林=aigmaxr公式2公式2中類間散布矩陣 &和類內(nèi)散布矩陣 %可以分別表示如下： £公式3L$二22（看-呵一呵）?。﹋=i（=1公式4公式3和公

16、式4中，L是類數(shù)，m是全部樣本的均值，步:是第i類樣本均值，%是第 :類樣本數(shù)。3.5 聚類原始數(shù)據(jù)集X進(jìn)行降維處理得到新數(shù)據(jù)集X'后，使用K-means算法對(duì)X聚類。得到測(cè)試用例的K個(gè)聚類。K-means聚類算法的典型步驟如下19:1） 初始化：在多維空間中放置K個(gè)初始點(diǎn)，代表每個(gè)簇的中心點(diǎn)。初始化中心點(diǎn)的不同直接影響到測(cè)試用例選擇的結(jié)果，所以最好的選擇就是兩兩中心點(diǎn)的距離盡量遠(yuǎn)。2） 聚類：根據(jù)數(shù)據(jù)對(duì)象的均值，將每個(gè)數(shù)據(jù)對(duì)象放置到其最相似的簇中。3） 更新：當(dāng)有新的數(shù)據(jù)對(duì)象加入分組中后，對(duì)分組的中心點(diǎn)進(jìn)行更新。4） 循環(huán)：重復(fù)聚類和更新的步驟直到每個(gè)簇的中心點(diǎn)不再明顯改變o3.6

17、用例取樣經(jīng)過(guò)k-means算法聚類以后，原測(cè)試用例集被聚到 K個(gè)簇中。最后從每一簇中選出測(cè)試 用例建立新的回歸測(cè)試用例集。取樣策略有很多種，常見(jiàn)的有自適應(yīng)取樣策略10, 20、動(dòng)態(tài)取樣策略21、隨機(jī)取樣策略16等。本文選擇自適應(yīng)取樣策略，首先按照一定比例，如 10%,從每一簇中隨機(jī)選取少量測(cè)試用例，每一簇中至少選出一個(gè)測(cè)試用例，如果某個(gè)測(cè)試 用例覆蓋了修改的函數(shù)，則直接將其放到新的測(cè)試用例集中。如果選出的測(cè)試用例為可以發(fā)現(xiàn)故障的測(cè)試用例，則與其在同一簇中的全部測(cè)試用例將被選出來(lái)組成新的測(cè)試用例集。4實(shí)驗(yàn)為了驗(yàn)證所提出的方法，進(jìn)行了大量的實(shí)驗(yàn)探究。并對(duì) DSKM方法和k-means算法進(jìn)行了 對(duì)

18、比，以驗(yàn)證 DSKM方法的有效性。4.1實(shí)驗(yàn)對(duì)象論文選用Xml-security項(xiàng)目和Junit項(xiàng)目作為實(shí)驗(yàn)對(duì)象。Xml-security項(xiàng)目和Junit項(xiàng)目者B是Java開源項(xiàng)目。表格4-1中列出了每個(gè)項(xiàng)目對(duì)應(yīng)的版本數(shù)量、類文件數(shù)量、函數(shù)數(shù)量、指令數(shù)量和測(cè)試用例的數(shù)量。對(duì)于每個(gè)實(shí)驗(yàn)對(duì)象，下載的最新版本為正確的基礎(chǔ)版本。依次將實(shí)驗(yàn)對(duì)象的歷史版本中的Bug添加到基礎(chǔ)版本中，每次添加一個(gè) Bug,形成多個(gè)修改版。將測(cè)試用例在各個(gè)修改版本上運(yùn)行并記錄運(yùn)行結(jié)果。執(zhí)行此操作是因?yàn)椴荒苤苯訌南螺d的實(shí)驗(yàn)對(duì)象中得到測(cè)試用例執(zhí)行結(jié)果記錄，實(shí)際應(yīng)用中，可以直接使用測(cè)試用例的執(zhí)行結(jié)果記錄。表格4 -1Program

19、VersionsClassesMethodsInstructionsTest casesXml-security16333243055058117Junit202351450184571594.2實(shí)驗(yàn)步驟實(shí)驗(yàn)主要分為五個(gè)基本步驟。原始數(shù)據(jù)提取利用eclipse工具在實(shí)驗(yàn)對(duì)象的各修改版本上執(zhí)行測(cè)試用例集，使用 eclemma工具收集 各測(cè)試用例的覆蓋信息。需要記錄三類信息：1）測(cè)試用例集在實(shí)驗(yàn)對(duì)象的各修改版本上的總的函數(shù)覆蓋率。2）測(cè)試用例集中每個(gè)測(cè)試用例的函數(shù)覆蓋信息，形成函數(shù)覆蓋的二進(jìn)制向量。3）測(cè)試用例集中每個(gè)測(cè)試用例在實(shí)驗(yàn)對(duì)象的每個(gè)修改版本上的執(zhí)行結(jié)果，如果與基礎(chǔ)版本的執(zhí)行結(jié)果相同，則代

20、表通過(guò)，如果不同，則為失敗。記錄失敗測(cè)試用例的序號(hào)和對(duì)應(yīng)的版本號(hào)，用于下一步中提取成對(duì)約束。約束推導(dǎo)一個(gè)失敗的測(cè)試用例至少可以檢測(cè)到一個(gè)bug,某些失敗的測(cè)試用例在多個(gè)修改版本都能檢測(cè)到bug。建立測(cè)試用例和版本之間的映射關(guān)系。丫（0代表測(cè)試用例工能夠檢測(cè)到bug的版本集合，用重合度CD表示兩個(gè)測(cè)試用例 x1和x2發(fā)現(xiàn)相同bug的比率，CD定義如下13:公式1V&J和不能同時(shí)為0,即兩個(gè)通過(guò)的測(cè)試用例不計(jì)算重合度。根據(jù) CD的值，建 立 Must-link 和 Cannot-link 約束集。1 ） Must-link ：如果 （1, 2） TM 則,和.屬于 must-link 約束

21、集。TM 為 must-link 約束的閾值，定義為兩個(gè)值，TM=100%和TM=50%。2 ） Cannot-link ：如果皿抵） = 0, 則工二和工屬于cannot-link約束集。即&和如沒(méi)有 檢測(cè)到相同的bug。不難看出不同的約束定義會(huì)推導(dǎo)出不同的成對(duì)約束，也會(huì)影響到聚類的結(jié)果，進(jìn)而影響到測(cè)試用例選擇的結(jié)果。數(shù)據(jù)降維推導(dǎo)出成對(duì)約束以后，使用 SSDR方法得到權(quán)值矩陣 W,然后利用權(quán)值矩陣 W將原始 數(shù)據(jù)集X映射為Y, 二產(chǎn)/。在X中每個(gè)元素的值為1或者0,代表函數(shù)是否被覆蓋。 經(jīng) 過(guò)數(shù)據(jù)轉(zhuǎn)換以后，每個(gè)元素的值都是一個(gè)浮點(diǎn)數(shù)， 向量的大小比以前更小。 使用MATLAB工 具編

22、程實(shí)現(xiàn)SSDR方法，得到經(jīng)過(guò)SSDR方法處理過(guò)后的數(shù)據(jù)集 Y。然后，使用K-means算法對(duì)經(jīng)過(guò)SSDRB法處理以后得到的數(shù)據(jù)集Y進(jìn)行聚類，得到每個(gè)測(cè)試用例對(duì)應(yīng)的類標(biāo)號(hào)，用 Labels向量表示。將類標(biāo)號(hào)向量Labels和數(shù)據(jù)集Y作為L(zhǎng)DA方法的輸入，完成對(duì)數(shù)據(jù)的有監(jiān)督的維數(shù)約簡(jiǎn)。使用MATLAB工具編程實(shí)現(xiàn)LDA方法，得到最終用于聚類的新數(shù)據(jù)集X'。聚類使用SSDRT法和LDA方法對(duì)數(shù)據(jù)集進(jìn)行降維以后，使用K-means算法對(duì)上面形成的新的數(shù)據(jù)集X進(jìn)行聚類，得到聚類的結(jié)果。在這一步中，論文使用Rapidminer工具的K-means 算法。根據(jù)實(shí)驗(yàn)對(duì)象的大小設(shè)置初始K值，執(zhí)行聚類過(guò)程

23、。取樣對(duì)測(cè)試用例聚類結(jié)束以后，使用自適應(yīng)的取樣策略選取測(cè)試用例。從每個(gè)簇中選取p%的測(cè)試用例，p值通過(guò)項(xiàng)目的規(guī)模大小調(diào)整。對(duì)選出的新的測(cè)試用例集計(jì)算覆蓋率，如果覆蓋率接近或者等于原始測(cè)試用例集在歷史版本上的覆蓋率，則停止，返回新的測(cè)試用例集； 否則，返回聚類步驟，調(diào)整 K值。3 .3評(píng)估度量為了評(píng)估論文提出的方法的有效性，采用的評(píng)測(cè)指標(biāo)包括召回率、準(zhǔn)確率、約簡(jiǎn)率以及覆蓋率比。設(shè)T為原測(cè)試用例集的測(cè)試用例數(shù)量，寫為原測(cè)試用例集中能夠發(fā)現(xiàn)故障的用例t數(shù)量，c解為原測(cè)試用例集對(duì)應(yīng)的代碼覆蓋率。,為選出的測(cè)試用例集的測(cè)試用例數(shù)量，*T為選出的測(cè)試用例集中能夠發(fā)現(xiàn)故障的用例數(shù)量，。譏，為選出的測(cè)試用例集

24、對(duì)應(yīng)的代F碼覆蓋率。召回率Recall被認(rèn)為是測(cè)試用例選擇的完整性度量，定義為Recal.1=171/117y|o Recall值越大，代表更強(qiáng)的錯(cuò)誤檢測(cè)能力。準(zhǔn)確率Precision被認(rèn)為是測(cè)試用例選擇的準(zhǔn)確性程度，定義為Precision = 7p/TfoPrecision值越大，代表更少的測(cè)試資源浪費(fèi)。約簡(jiǎn)率Reduction用來(lái)衡量測(cè)試用例集約簡(jiǎn)的程度，定義為 Reduction T-r/ToReduction值越大，代表約簡(jiǎn)程度越大。 覆蓋率比Coverage用來(lái)衡量測(cè)試用例選擇出的新的測(cè)試用例集的函數(shù)覆蓋情況，定義為ConeeT'age = |Cot?f|/|Cov|o C

25、overage值越大，代表代碼覆蓋越完整。4 .4結(jié)果分析通過(guò)對(duì)Junit項(xiàng)目和Xml-security項(xiàng)目進(jìn)行實(shí)驗(yàn)， 實(shí)驗(yàn)結(jié)果如圖4-1、圖4-2和圖4-3。圖 中TM為Must-link約束的閾值，定義為兩個(gè)值，TM=100%和TM=50%。SSDR-使用SSDR處理以后對(duì)數(shù)據(jù)進(jìn)行聚類的K值。P為最后取樣策略中的比率值，如果某簇中僅含一個(gè)測(cè)試用例，則直接選出該測(cè)試用例。Recall、precision > reduction > coverage分別為最終測(cè)試用例junitP-Precision(Junit)選擇結(jié)果的召回率、準(zhǔn)確率、約簡(jiǎn)率和覆蓋率比。Xml-securityP

26、-Precision(X ml-security)nKHbrnxppE-K-meansDSPC-KM0.230.220.21 D0.20.19J- K-meansDSPC-KMJ0.18-O18口O2030P(%)40500.17102030P(%)4050P-Reduction(X ml-security)5 5 40/0OnutcuaeRP-Reduction(Junit)40500.35 - -K K-means DSPC-KM1020300.50.450.40.351020-K-means-DSPC-KM304050P(%)P(%)P-Coverage(X ml-security)ac

27、eR&easr evoc0.92P-Coverage&Recall(Junit)K-meansDSPC-KMea«pevoc6 9 5 8L901-80o o十一+-K-meansb DSPC-KM0.84 十-0.82 -=1020304050P(%)0.750.71020304050P(%)圖4-1 P值對(duì)選擇結(jié)果的影響圖 4-1 表示了 P 值又precision > reduction > coverage 結(jié)果的影響。 Coverage 的值隨著 P值增大而增大，precision和reduction的值隨著P的增大而減小。從結(jié)果中可以看出，相對(duì)

28、于K-means方法，DSKM方法在在保持甚至提高覆蓋率的前提下，準(zhǔn)確率和約簡(jiǎn)率都有明顯的提高。K-Precision(Junit)K-Precision(X ml-security)0.24n or SIC er p0 .4.OD S P C- KIJ20304050600.220.20.180.161020二 K-meansDSPC-KM304050K-Reduction(X ml-security)6 5 5o5oonurcuaeRK-Reduction(Junit)K-means DSPC-KM/3o o nutcuaeK-means一 DSPC-KM30405060KK-Covera

29、ge(Junit)0.11020304050Kea«pevoc8,o7664-K-meansDSPC-KM10.950.90.850.80.750.7K-Coverage(X ml-security)K-meansDSPC-KM30405060K2030405060圖4-2 K值對(duì)選擇結(jié)果的影響圖4-2表示了 K-means聚類步驟中設(shè)置的 K值又precision > reduction > coverage結(jié)果的 影響。在保持甚至提高覆蓋率的前提下，當(dāng)K值較小或者較大時(shí)，DSKM方法對(duì)應(yīng)的準(zhǔn)確率和約簡(jiǎn)率明顯優(yōu)于 K-means方法。1 0.95 0.9 0.85 0.

30、8 0.75 0.7 0.65 0.6 0.55 0.5 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.050tj0.051 0.95 - 0.9 - 0.85 0.8 - 0.75 - 0.7 0.65 0.6 0.55 -0.51 0.45 -0.4 - 0.35 -0.3 0.25 -0.2 0.15 二 0.1 口0.05 -0 - 601 0.95 0.9 0.85 0.8 0.75 0.7 0.650.6 0.550.5 0.450.4 0.350.3 0.250.2 0.150.1 0.050a la500.0120a：_ PrecisionRedu

31、ctionCoverageRecall1001 f- 0.95 4 0.9 - 0.85 - 0.8 -0.75 -0.7 -0.65 -0.60.550.5 -0.45 -0.4 -0.35，0.3 -0.25 -0.2 -0.15 M0.10.05 -00.050.0120a：6560SSDR-K(Junit)PrecisionReduction Coverage Recall日707580SSDR-KTM(Junit) PrecisionReductionCoverageRecall708090100TM ( %)_ PrecisionReductionCoverage Recall10

32、0SSDR-K(X mi-security)E.1 0.95 0.9 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5 0.450.4s0.35 -0.3 -0.25 -0.2舊0.15 -0.10.05 -0t601 0.95 0.9 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5 0.450.4丫0.35 、0.3 0.25 0.2四5060Precision-ReductionCoverage Recall65707580SSDR-KTM(Xmi-security)'一 PrecisionReductionCoverageRecall

33、708090由100TM ( %)圖4-3 a和0的比值、SSDR-KF口 TM的值對(duì)選擇結(jié)果的影響圖4-3表示了針對(duì) DSKM方法，”和3的比值、SSDR-魅口 TM的值對(duì)Recall、precision >reduction > coverage的值的影響。在一定閾值內(nèi)，當(dāng) a和3的比值越大，SSDR-K值越大時(shí)， 準(zhǔn)確率、約簡(jiǎn)率和覆蓋率的結(jié)果更優(yōu)。TM的值越大，即對(duì)于 Mus-link約束集定義越嚴(yán)格，在保證覆蓋率的前提下，準(zhǔn)確率、約簡(jiǎn)率的結(jié)果更優(yōu)。從實(shí)驗(yàn)的結(jié)果可以得出以下結(jié)論： 1）對(duì)于普通的K-means算法，DSKM方法在保持較 高的召回率和代碼覆蓋率的前提下，準(zhǔn)確率和

34、約簡(jiǎn)率都有明顯的提高。2）約束的定義會(huì)對(duì)聚類的結(jié)果產(chǎn)生影響， 從而影響測(cè)試用例選擇的結(jié)果。 通常TM定義越嚴(yán)格則聚類的效果越 好。5總結(jié)與展望論文將判別型半監(jiān)督 K-means聚類方法（DSKM）應(yīng)用到回歸測(cè)試用例選擇中。該方法 首先利用回歸測(cè)試歷史執(zhí)行信息找出隱藏的成對(duì)約束信息。然后利用SSDR方法和LDA方法對(duì)原始數(shù)據(jù)進(jìn)行降維，優(yōu)化后的數(shù)據(jù)在距離度量上更加適合聚類分析，從而提高了k-means算法的精度。通過(guò)實(shí)驗(yàn)，說(shuō)明了 DSKM方法在大多數(shù)情況下可以優(yōu)化回歸測(cè)試用例選擇的結(jié) 果。實(shí)驗(yàn)結(jié)果還表明約束定義越嚴(yán)格，回歸測(cè)試用例選擇的結(jié)果越優(yōu)。由于基于半監(jiān)督聚類技術(shù)的回歸測(cè)試用例選擇問(wèn)題較為新穎

35、，還有過(guò)很多后續(xù)的工作可以進(jìn)行擴(kuò)展。例如如何構(gòu)造高質(zhì)量的約束，降低“噪音”對(duì)聚類結(jié)果的影響。本實(shí)驗(yàn)采取歐氏距離對(duì)樣本之間的距離進(jìn)行度量，在后續(xù)工作中可以采用不同的距離度量方法進(jìn)行實(shí)驗(yàn)對(duì)比。這些都是論文的下一步工作。參考文獻(xiàn)1 Z. Chen, C. Zhenyu, Z. Zhihong, Y Shali, Z. Jinyu, and X. Baowen, "An Improved Regression Test Selection Technique by Clustering Execution Profiles," Proceedings of the Tenth In

36、ternational Conference on Quality Software (QSIC 2010), pp. 171-9, 2010 2010.2 H. K. N. Leung and L. White, "Insights into regression testing software testing," in Software Maintenance, 1989., Proceedings., Conference on , 1989, pp. 60-69.3 G. Rothermel and M. J. Harrold, "Analyzing r

37、egression test selection techniques," Software Engineering, IEEE Transactions on, vol. 22, pp. 529-551, 1996.4 章曉芳，陳林，徐寶文，and聶長(zhǎng)海，"測(cè)試用例集約簡(jiǎn)問(wèn)題研究及其進(jìn)展，"計(jì)算機(jī)科學(xué)與探索，pp. 235-247, 2008.5 G. Rothermel and M. J. Harrold, "A framework for evaluating regression test selection techniques,"

38、in Software Engineering, 1994. Proceedings. ICSE-16., 16th International Conference on, 1994, pp. 201-210.6 S. Beydeda and V. Gruhn, "Integrating white- and black-box techniques for class-level regression testing," in Computer Software and Applications Conference, 2001. COMPSAC 2001. 25th

39、Annual International , 2001, pp. 357-362.7 M. J. Harrold and M. L. Souffa, "An incremental approach to unit testing during maintenance," in Software Maintenance, 1988., Proceedings of the Conference on , 1988, pp. 362-367.8 R. Gupta, M. J. Harrold, and M. L. Soffa, "An approach to reg

40、ression testing using slicing," in Software Maintenance, 1992. Proceerdings., Conference on ,1992, pp. 299-308.9 R. Gupta, M. J. Harrold, and M. L. Soffa, "Program slicing-based regression testing techniques," Journal of Software Testing Verification and Reliability, vol. 6, pp. 83-11

41、1, 1996.10 W. Dickinson, D. Leon, and A. Fodgurski, "Finding failures by cluster analysis of execution profiles," in Software Engineering, 2001. ICSE 2001. Proceedings of the 23rd International Conference on, 2001, pp. 339-348.11 W. Masri, A. Podgurski, and D. Leon, "An empirical stud

42、y of test case filtering techniques based on exercising information flows," Software Engineering, IEEE Transactions on, vol. 33, pp. 454-477, 2007.12 S. Yoo, M. Harman, P Tonella, and A. Susi, "Clustering test cases to achieve effective and scalable prioritisation incorporating expert know

43、ledge," in Proceedings of the eighteenth international symposium on Software testing and analysis , 2009, pp. 201-212.13 C. Songyu, C. Zhenyu, Z. Zhihong, X. Baowen, and F. Yang, "Using semi-supervised clustering to improve regression test selection techniques," Proceedings 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation (ICST 2011), pp. 1-10, 2011 2011.14 S. Parsa, A. Khalilian, and Y. Fazlalizadeh, "A new algorithm to T