李敬煒

(南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇南京 210023)

0 引言

測試用例[1]的設(shè)計(jì)是整個(gè)測試工作中最重要的一環(huán)，也是整個(gè)測試流程中難度最大的部分，往往是在同一時(shí)間段對(duì)同一對(duì)象設(shè)計(jì)一系列測試用例，通常以中文文本的形式表示。測試用例會(huì)隨著應(yīng)用功能的擴(kuò)展不斷完善，并且在不同的領(lǐng)域有不同的用例，相應(yīng)的側(cè)重點(diǎn)也有所不同。測試用例是由多個(gè)人員共同評(píng)審出的產(chǎn)物，由于編寫習(xí)慣不一樣，因此在更新用例的過程中難免會(huì)有一些相類似的混合在其中。為了提高用例的質(zhì)量，需要對(duì)用例進(jìn)行去重，然而在實(shí)際工作中測試人員往往是通過人工來判斷篩選，效率低下。但是如果直接對(duì)現(xiàn)有測試用例進(jìn)行文本分析會(huì)造成漏刪或誤刪，為此提出先對(duì)測試用例進(jìn)行聚類分析的想法。

傳統(tǒng)聚類方法一般采用批量處理，即每當(dāng)有數(shù)據(jù)增加或更新的時(shí)候，必須對(duì)整個(gè)數(shù)據(jù)集進(jìn)行重新操作[2]，消耗時(shí)間會(huì)隨著數(shù)據(jù)的增加而大幅度地增加，同時(shí)聚類效果也會(huì)有所下降。K-Means[3]聚類方法會(huì)計(jì)算每個(gè)點(diǎn)到質(zhì)心的距離再去分配實(shí)例點(diǎn)，在簇?cái)?shù)量設(shè)置合理的情況下，不易產(chǎn)生小簇，但是K-Means的簇?cái)?shù)量設(shè)置的多少會(huì)影響得到的簇的大小。增量聚類則是對(duì)已有聚類結(jié)果的擴(kuò)充，不僅能夠有效地提高聚類性能，還會(huì)降低計(jì)算時(shí)間復(fù)雜度，且易于聚類結(jié)果的后期維護(hù)，具有代表性的是Single-Pass算法[4]，只需要直接處理小簇即可計(jì)算得到兩個(gè)詞語以上的簇內(nèi)的詞語之間相關(guān)性。本文針對(duì)測試用例數(shù)據(jù)稀疏性大、上下文信息不足等特性，對(duì)已有聚類算法進(jìn)行改進(jìn)，提出一種合適的增量聚類算法T_Single-Pass。

1 相關(guān)工作

聚類主要是將離散的數(shù)據(jù)集依某些特征分別聚集成群，聚類方法大致可分成兩類：階層式與非階層式[5]。階層式將數(shù)據(jù)層層反復(fù)地進(jìn)行分裂或聚合，只需計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的距離。當(dāng)需要某一個(gè)特定范圍的聚類結(jié)果，就必須從頭做起，耗時(shí)較久。非階層式通過一套迭代的數(shù)學(xué)運(yùn)算法，找出最佳的聚類方式，數(shù)據(jù)集僅需處理一次，計(jì)算效率高且復(fù)雜度低[6]，不會(huì)發(fā)生多重隸屬的聚類模糊狀況，聚類獲取出對(duì)象與對(duì)象之間共同描述的問題，使問題與對(duì)象形成父子階層關(guān)系，增量聚類就是非階層式聚類法。

增量聚類的研究可以分為兩類：一類是每次迭代所有數(shù)據(jù)，一類是利用前一次聚類的結(jié)果來劃分一個(gè)數(shù)據(jù)并指向現(xiàn)有的簇。陶舒怡等[7]利用詞項(xiàng)之間的語義信息，計(jì)算新增文本與已有簇之間的相合性實(shí)現(xiàn)增量聚類，但此種方法仍有一定比例的錯(cuò)誤項(xiàng)，需要對(duì)錯(cuò)誤的聚類進(jìn)行再分配。殷風(fēng)景等[8]先進(jìn)行初步聚類，再將初步類與已有類進(jìn)行比較和聚合，避免了聚類結(jié)果由于數(shù)據(jù)順序不同發(fā)生變化，但是需要進(jìn)行多次聚類，隨著數(shù)據(jù)的增加，消耗的時(shí)間成正比增長。Tien等[9]提出了一種基于加權(quán)聚類模型的增量在線多標(biāo)簽分類方法，通過每個(gè)樣本的權(quán)值隨時(shí)間減小的衰退機(jī)制來適應(yīng)數(shù)據(jù)的變化，但是此種方法在大規(guī)模數(shù)據(jù)下可行度并不高。

通過上述對(duì)現(xiàn)有工作的調(diào)研發(fā)現(xiàn)，現(xiàn)有增量聚類算法依然還有以下挑戰(zhàn)：如何有效降低特征維數(shù)，加快運(yùn)行速度，同時(shí)不降低聚類的效果，將新增文本高效的分配到最合適的簇中。

2 算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 字詞權(quán)重計(jì)算與選取

為節(jié)省系統(tǒng)的運(yùn)算時(shí)間，本文僅取出足夠代表文本對(duì)象的關(guān)鍵詞進(jìn)行比較判斷。測試用例文本由動(dòng)詞、名詞和量詞等組成，選取名詞作為一條用例的對(duì)象表示，有的測試用例在進(jìn)行分詞處理后不能很好的判斷詞性。比如“進(jìn)入設(shè)置，設(shè)置頁面中的個(gè)人信息”，根據(jù)語義判斷出“設(shè)置”既有動(dòng)詞也有名詞的詞性。結(jié)合句子的語法結(jié)構(gòu)進(jìn)行詞性判斷，名詞與動(dòng)詞搭配的情況有如下幾種：名詞+動(dòng)詞、名詞+名詞、動(dòng)詞+名詞。測試用例中動(dòng)詞一般都是“打開”“點(diǎn)擊”等，這些動(dòng)詞在初始判斷時(shí)出錯(cuò)的概率幾乎為0，圍繞動(dòng)詞為中心，觀察動(dòng)詞前后字詞的詞性，如果是名詞記為0，動(dòng)詞記為1，其他詞性記為2。以上述例子為例，以標(biāo)點(diǎn)符號(hào)為分割線，標(biāo)記的結(jié)果應(yīng)該是11 | 102200，通過詞性搭配可知第二個(gè)詞并非是動(dòng)詞而是名詞。以此類推，重新判斷出每個(gè)用例中字詞的詞性。

考慮特征詞與出現(xiàn)該詞的用例數(shù)之間的關(guān)系，計(jì)算特征詞在整個(gè)用例集中出現(xiàn)的頻率。由于性能用例中多條用例都會(huì)涉及到“時(shí)間”等字眼，但這些名詞并不能代表用例的核心對(duì)象，為此對(duì)不同位置的對(duì)象賦予不同的加權(quán)值。將用例中的名詞特征項(xiàng)分別用k1、k2、…、kn表示，di=(wi1，wi2，wi3，…，win)表示文本Di中的第i條測試用例，win表示特征項(xiàng)kn在文本Di中的權(quán)重，結(jié)合TF-IDF[10]的計(jì)算思想，提出適合用例特征的計(jì)算方法，計(jì)算公式如(1)所示：

其中，tfin表示在文本Di中特征項(xiàng)kn出現(xiàn)的頻率，N表示所有用例的數(shù)量，mn表示存在特征項(xiàng)kn的用例數(shù)，α表示用例不同位置對(duì)應(yīng)的加權(quán)值，l表示從左至右劃分的用例長度占總長度的比例，分別表示用例的開始、中間、結(jié)束三部分，如果一個(gè)詞被拆分成兩部分，以左邊的為準(zhǔn)進(jìn)行權(quán)值計(jì)算。將計(jì)算的結(jié)果進(jìn)行降序排序，選取排名前三的名詞特征項(xiàng)。

2.2 相似度計(jì)算與聚類

由于在增量聚類的過程中需要反復(fù)計(jì)算與已有簇的相似度，為了減少計(jì)算過程中取近似值產(chǎn)生的誤差，本文采用相對(duì)簡單且可以在較大范圍內(nèi)求取最優(yōu)解的曼哈頓距離公式來計(jì)算，將第一條測試用例中字詞權(quán)重值最高的特征向量作為第一個(gè)簇，并以其為簇的中心。假設(shè)第X條測試用例文本特征項(xiàng)對(duì)應(yīng)的特征向量為Xi=(xi1，xi2，xi3，…，xin)，(i=1，2，3)，已產(chǎn)生的簇中心所在第Y條測試用例特征項(xiàng)對(duì)應(yīng)的特征向量為Y=(y1，y2，y3，…，yn)，特征向量中每個(gè)值表示測試用例中每個(gè)選出的特征項(xiàng)在所有詞中所占的權(quán)值，把未出現(xiàn)的詞設(shè)置為0。通過特征向量中特征項(xiàng)的權(quán)重來計(jì)算與已有簇之間的距離，計(jì)算公式如(2)所示：

測試用例具有階段性，即用例在創(chuàng)建的時(shí)候，同一時(shí)間段編寫的用例中出現(xiàn)同一對(duì)象的可能性較高。結(jié)合用例的這一特性，為了提高劃分到對(duì)應(yīng)聚類類別的準(zhǔn)確度，在計(jì)算新增測試用例與各已知對(duì)象群集的相似度時(shí)，融入創(chuàng)建時(shí)間順序這個(gè)要素來計(jì)算相似度。具體公式如(3)所示：

其中x代表新增用例，c代表已經(jīng)產(chǎn)生的一個(gè)簇中心對(duì)應(yīng)的測試用例，j表示介于x以及c對(duì)應(yīng)的簇中最新的一條測試用例之間所增加的用例數(shù)，前提是最新的一條測試用例要屬于TW，如果不屬于TW，j的值設(shè)為0，TW表示時(shí)間區(qū)間，時(shí)間區(qū)間指的是同時(shí)上傳用例所在的時(shí)間范圍，m為現(xiàn)有用例集中所有的用例數(shù)。在此，score(x)若大于門檻值，則標(biāo)定新增測試用例x存在舊對(duì)象；反之用例中存在新對(duì)象。由公式(3)可知在一個(gè)群集中最新加入的用例與要新增的用例之間增加的用例總數(shù)越多，新增測試用例與該測試對(duì)象群集越疏離、越不相關(guān)。

2.3 算法流程

本文提出的T_Single-Pass算法主要包含了文本預(yù)處理(分詞、詞性劃分)、文本降維、特征選取、相似度計(jì)算等方面。具體步驟如下：

步驟一：采用hanlp對(duì)文本進(jìn)行分詞，通過隱馬爾可夫模型對(duì)詞性進(jìn)行標(biāo)注，結(jié)合句子的語法結(jié)構(gòu)進(jìn)行分析，對(duì)判斷錯(cuò)誤的詞性重新標(biāo)注。選取名詞作為最終的測試對(duì)象集合，通過公式(1)計(jì)算出名詞在用例中的權(quán)重并降序排序，選擇排名前三的詞作為特征詞。

圖1 門檻值選取比較

表1 幾種算法的評(píng)測結(jié)果

步驟二：讀取已有測試用例集中第一條測試用例D1，根據(jù)步驟一計(jì)算結(jié)果選取第一條用例中權(quán)值最高的特征詞當(dāng)作群集C1。

步驟三：當(dāng)用例并非已有用例集中第一條或是屬于新增測試用例時(shí)，所有測試用例文本Di一一與現(xiàn)有的所有群集Ci作相似度的計(jì)算，根據(jù)計(jì)算結(jié)果，判斷與已有對(duì)象群集的相關(guān)性。如果與現(xiàn)有群集有相關(guān)的，分析結(jié)束，將其劃分到最高相似度對(duì)應(yīng)群集中。如果不相關(guān)，重新調(diào)整用例的群集向量進(jìn)行計(jì)算，否則該用例形成一個(gè)新的群集。

步驟四：重復(fù)步驟三，直到?jīng)]有新的用例。

3 實(shí)驗(yàn)與分析

3.1 評(píng)測數(shù)據(jù)

本實(shí)驗(yàn)所用數(shù)據(jù)集是從現(xiàn)有公司獲取的面向安卓系統(tǒng)的性能測試用例集，其中包含1080條測試用例，包含響應(yīng)時(shí)間、啟動(dòng)時(shí)間、滑動(dòng)流暢度、內(nèi)存泄露等方面。用Excel表格進(jìn)行文本表示，文本中每一行代表一個(gè)測試用例，按照創(chuàng)建時(shí)間順序依次排列，本文的測試用例由具有代表性的測試步驟組成。

3.2 評(píng)測指標(biāo)

3.3 評(píng)測環(huán)境

系統(tǒng)環(huán)境：Windows 10；CPU：AMD Ryzen 5 2500U；內(nèi)存：8G；系統(tǒng)類型：64位；編程語言：Java；開發(fā)環(huán)境：Eclipse。

3.4 重要參數(shù)選擇

在計(jì)算文本相似度時(shí)門檻值的設(shè)置也是十分關(guān)鍵的，設(shè)置太高或太低都有可能直接影響最后的聚類效果，太高會(huì)導(dǎo)致聚類類別過細(xì)，太低會(huì)導(dǎo)致聚類類別精確度不高，為了得到更好的相似度計(jì)算結(jié)果，設(shè)置不同的門檻值進(jìn)行比較，實(shí)驗(yàn)數(shù)據(jù)如圖1所示。

由圖1可知，當(dāng)門檻值小于或大于0.5時(shí)，F(xiàn)值均不是最優(yōu)解，所以綜合考慮本文選擇門檻值為0.5進(jìn)行實(shí)驗(yàn)。

3.5 評(píng)測結(jié)果

本文選取K-Means、Single-Pass、T_Single-Pass三種方法進(jìn)行比較。在保證所有條件比如用例數(shù)量、大小等一致的前提下，首先選取前800條測試用例進(jìn)行聚類，接著將剩余的280條用例分成7份，依次在不同的時(shí)間段內(nèi)上傳用例文本，對(duì)新增文本聚類。得出對(duì)應(yīng)的R、P、F指標(biāo)結(jié)果如表1所示。

從實(shí)驗(yàn)數(shù)據(jù)上看，所有的方法都具有不錯(cuò)的聚類分析結(jié)果，Single-Pass算法明顯優(yōu)于K-Means，但是T_Single-Pass具有更好的準(zhǔn)確度。與此同時(shí)，通過KMeans算法產(chǎn)生13個(gè)簇，Single-Pass算法產(chǎn)生15個(gè)簇，本文采用的方法最終產(chǎn)生13個(gè)簇。綜合考慮，本文的改進(jìn)方法在聚類準(zhǔn)確性和簇劃分個(gè)數(shù)判斷效果最佳。

4 總結(jié)

在聚類時(shí)由于測試用例依賴傳輸順序、詞性有歧義等特點(diǎn)，需要對(duì)新增用例重復(fù)比較、判斷、分析，進(jìn)而影響聚類效果。本文在Single-Pass算法基礎(chǔ)上對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，選取對(duì)計(jì)算結(jié)果有意義的詞，結(jié)合時(shí)間概念與曼哈頓距離進(jìn)行文本相似度計(jì)算。實(shí)驗(yàn)表明本文改進(jìn)的方法相比較K-means、Single-Pass等方法在效率和準(zhǔn)確率上有所提升。在之后的應(yīng)用中改變以往的人工篩選用例的方式，能在減少人力消耗的同時(shí)提高測試用例的篩選效率和準(zhǔn)確率。然而現(xiàn)階段在文本聚類分析中仍有一些問題亟待解決，比如如何對(duì)新增文本進(jìn)行數(shù)據(jù)分配，以提高聚類性能等。