李敬煒

(南京郵電大學計算機學院，江蘇南京 210023)

0 引言

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

2.2 相似度計算與聚類

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

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

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

2.3 算法流程

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

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

圖1 門檻值選取比較

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

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

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

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

3 實驗與分析

3.1 評測數(shù)據(jù)

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

3.2 評測指標

3.3 評測環(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ù)選擇

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

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

3.5 評測結(jié)果

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

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

4 總結(jié)

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