尹世莊，王 韜，謝方方，劉麗君，曲 直，張 斌

(1.陸軍工程大學(xué)石家莊校區(qū), 石家莊 050003；2.陸軍工程大學(xué), 南京 210000)

聚類是一種無監(jiān)督的學(xué)習(xí)方法，訓(xùn)練樣本沒有標(biāo)簽，其聚類結(jié)果的好壞難以直接評判[1]。聚類有效性分析主要是研究如何評價得到的不同聚類結(jié)果[2]。目前主要有調(diào)整蘭德系數(shù)、互信息評分[3]。針對二進(jìn)制協(xié)議聚類效果評估的研究還比較少，對于未知二進(jìn)制協(xié)議來說，由于其結(jié)果正確性無法評判，不能以正確率、識別率、誤識別率[4]等指標(biāo)進(jìn)行評價。為了解決這一問題，可采用聚類性能度量中的“內(nèi)部指標(biāo)”(internal index)進(jìn)行評判。常用的內(nèi)部指標(biāo)有：DB指數(shù)(Davies-Bouldin Index,DBI);Dunn指數(shù)(Dunn Index,DI)，這兩個指數(shù)在一定程度上分別反映了簇內(nèi)距離和簇間距離[5]。顯然，DBI越小越好，DI越大越好。本文采用輪廓系數(shù)和調(diào)整互信息對未知二進(jìn)制的聚類效果進(jìn)行評價，調(diào)整互信息對聚類結(jié)果的簇內(nèi)距離進(jìn)行評估，輪廓系數(shù)對整體的聚類效果進(jìn)行評估。

1 相關(guān)理論和方法

1.1 聚類性能度量

聚類性能度量也稱為聚類的有效性指標(biāo)，用來評估聚類結(jié)果的好壞。從提高聚類精度的角度出發(fā)，如果確定了所需要的性能度量，那么我們就可以將該性能度量引入聚類過程中的優(yōu)化函數(shù)，得到更加符合需求的結(jié)果。一般來說聚類性能度量可分為兩類，分別為外部指標(biāo)和內(nèi)部指標(biāo)。外部指標(biāo)將聚類結(jié)果與某個外部模型進(jìn)行比較，內(nèi)部指標(biāo)則是直接分析聚類結(jié)果的本身特性。我們研究的是未知二進(jìn)制協(xié)議，因而采用內(nèi)部指標(biāo)。內(nèi)部指標(biāo)常用的有DB指數(shù)和Dunn指數(shù)[6]。DB指數(shù)簡稱DBI，Dunn指數(shù)簡稱DI。分別表示如下；

(1)

(2)

式(1)、(2)中：avg(Ci)代表簇C中所有樣本的平均距離；dcen(μi,μj)代表簇Ci和Cj簇的中心點之間的距離；diam(Cl)代表簇C內(nèi)所有樣本之間的最大距離；dijmin代表兩個簇Ci和Cj之間最近的樣本的距離。

本文采用調(diào)整互信息來衡量數(shù)據(jù)幀之間的相似程度，評估方案中調(diào)整互信息值計算的關(guān)鍵代碼如表1所示，部分代碼省略。labels_true表示獲得的第一個聚類中心，labels_pred代表需要分類的數(shù)據(jù)集，依次計算每一條數(shù)據(jù)和聚類中心的調(diào)整互信息值。其余聚類中心的計算方法與之相同。

表1 計算調(diào)整互信息值

1.2 調(diào)整互信息

互信息[7](Mutual Information，MI)是反映兩個隨機(jī)變量之間相互依賴程度的一種量度，也稱為轉(zhuǎn)移信息(trans information)。是度量兩個事件集合之間的相關(guān)性(mutual dependence)的一種指標(biāo)[8]。如果對數(shù)以2 為基底，互信息的單位是bit。與相關(guān)系數(shù)不同的是它的一般性更強(qiáng)，不僅僅適用于實值隨機(jī)變量。其計算方法如下：

(3)

p(x,y)是X和Y的聯(lián)合概率密度函數(shù)，p(x)和p(y)分別為X和Y的邊緣概率密度函數(shù)[9]。

從直觀上看，互信息代表X和Y之間重疊的信息，也就是說，當(dāng)知道X或者Y之中任意一個時，另外一個變量的不確定性減少的程度。

調(diào)整互信息AMI[10](Adjust Mutual Information)是互信息的一種改進(jìn)，它能夠更好地反映數(shù)據(jù)分布的吻合程度[11]。

(4)

式(4)中：H(U)和H(V)表示對應(yīng)樣本的邊緣熵值；E|MI|表示互信息的期望值。

MI取值范圍為[0,1]，但是對于隨機(jī)結(jié)果，MI并不能保證分?jǐn)?shù)接近零。為了解決這一問題，我們引入調(diào)整互信息(Adjust Mutual Information)。調(diào)整互信息是互信息的一種改進(jìn)，能夠更好地反映數(shù)據(jù)分布的吻合程度。MI取值范圍為[0,1]，AMI取值范圍為[-1,1]，它們都是值越大意味著聚類結(jié)果與真實情況越接近。

為了檢驗二進(jìn)制協(xié)議的簇內(nèi)聚類效果，引入調(diào)整互信息，用來衡量兩個數(shù)據(jù)分布的吻合程度，它具有更高的區(qū)分度：AMI取值范圍為[-1,1]，負(fù)數(shù)代表結(jié)果不好，越接近于1越好。

1.3 輪廓系數(shù)

輪廓系數(shù)[12](silhouette coefficient)使用數(shù)據(jù)集中對象之間的相似性度量來評估聚類的質(zhì)量，是簇的密集與分散程度的評價指標(biāo)。輪廓系數(shù)適用于實際類別信息未知的情況。其計算公式如下：

(5)

式(5)中：a為該數(shù)據(jù)幀與簇內(nèi)其他數(shù)據(jù)幀的平均距離；b為該數(shù)據(jù)幀與距離它最近的另一個簇中樣本的平均距離。

輪廓系數(shù)S的取值范圍為[-1,1]，S值越大，聚類結(jié)果越合理。如果輪廓系數(shù)S=-1，則表明該數(shù)據(jù)幀應(yīng)該被分到其他的類；如果S接近0，則表明該數(shù)據(jù)幀在兩個類的交叉點上。對全部樣本的輪廓系數(shù)求平均值就可以得到聚類結(jié)果整體輪廓系數(shù)sk，即：

(6)

sk的取值范圍為[-1,1]，sk值越大，聚類效果越好。

2 聚類效果評估

2.1 K-means改進(jìn)算法聚類模型

為實現(xiàn)對未知二進(jìn)制協(xié)議的高效聚類，提出了一種基于改進(jìn)K-means算法的未知二進(jìn)制協(xié)議聚類方法，協(xié)議是否已知并不影響聚類的準(zhǔn)確度，為了更好地檢驗聚類效果，故采用已知二進(jìn)制協(xié)議代替未知協(xié)議。并且研究對象是已經(jīng)做了初步切分，協(xié)議頭部位置確定的比特流(以下均稱為未知二進(jìn)制協(xié)議比特流)。以未知二進(jìn)制協(xié)議比特流為輸入，輸出二進(jìn)制協(xié)議子集。主要分為3個階段：預(yù)處理、確定k值與聚類中心、使用pearson距離的K-means聚類，主要流程如圖1所示。首先對數(shù)據(jù)進(jìn)行預(yù)處理，針對二進(jìn)制協(xié)議的特性，選取了4 bit作為處理單位；處理數(shù)據(jù)時采用最短數(shù)據(jù)作為依據(jù)進(jìn)行切割；將每一個單位作為一個特征，得到一個n×m的二維矩陣。再采用DCBP算法、誤差平方、進(jìn)行k值和聚類中心的提取，最后采用改進(jìn)距離函數(shù)的K-means算法對數(shù)據(jù)進(jìn)行聚類，將未知二進(jìn)制協(xié)議劃分為二進(jìn)制協(xié)議子集。在改進(jìn)算法中采用Pearson相關(guān)性距離作為度量，通過這些改進(jìn)來提高聚類精度。

圖1 未知二級制比特流聚類實現(xiàn)流程框圖

2.2 基于互信息的聚類效果評估

為了檢驗二進(jìn)制協(xié)議比特流的簇內(nèi)聚類效果，采用調(diào)整互信息來衡量兩條數(shù)據(jù)報文分布的相似程度。調(diào)整互信息具有更高的區(qū)分度，在聚類結(jié)果隨機(jī)產(chǎn)生的情況下，它的值接近零。AMI取值范圍為[-1,1]，負(fù)數(shù)代表數(shù)據(jù)報文之間負(fù)相關(guān)，越接近于1，兩個數(shù)據(jù)報文分布越相近。

定義1類簇的平均調(diào)整互信息值f。是指某一聚類中心點到其他樣本之間的調(diào)整互信息值之和除以樣本數(shù)n，fmin是指判斷是否屬于該中心點類簇的最小調(diào)整互信息值。

(7)

(8)

在某一類簇中，樣本與中心點數(shù)據(jù)分布的吻合程度越高，調(diào)整互信息值越大。設(shè)定評價閾值fmin，若樣本的調(diào)整互信息值大于評價閾值，則判定該樣本屬于該類簇。在該類簇的所有樣本中，正確判定屬于該類簇的樣本量越大，表示該類簇的聚類效果越好。本文使用正確識別率對結(jié)果進(jìn)行評價。正確識別率[13]是正確識別的目標(biāo)類和非目標(biāo)類之和除以總數(shù)。其公式為：

(9)

本文提出了一種使用調(diào)整互信息的聚類結(jié)果評價方案，算法的計算步驟如表2所示。

表2 調(diào)整互信息聚類效果評估算法

2.3 基于輪廓系數(shù)的聚類效果評估

對聚類效果評估，其實質(zhì)是對聚類簇進(jìn)行評估。對簇的評估通常從簇內(nèi)和簇間兩個方面進(jìn)行,當(dāng)簇內(nèi)距離最小和簇間距離最大時，聚類效果最好。簇的凝聚度 (cohesion) 和簇的分離度(separation) 分別對應(yīng)簇內(nèi)的緊密程度和簇間的相異程度。Kaufman等[14]提出的輪廓系數(shù)結(jié)合了凝聚度和分離度。輪廓系數(shù)可以對聚類結(jié)果的整體有效性進(jìn)行分析，相關(guān)研究可參見文獻(xiàn)[15]。

基于輪廓系數(shù)的聚類效果評估流程如圖2所示。

圖2 輪廓系數(shù)聚類結(jié)果評估流程框圖

根據(jù)不同的數(shù)據(jù)集，在設(shè)定分類數(shù)K后，以sk表示聚類輪廓系數(shù)。分別采用傳統(tǒng)K-means算法、Agnes算法、改進(jìn)K-means 3種不同算法對相同的數(shù)據(jù)集進(jìn)行聚類。通過sk對聚類結(jié)果進(jìn)行有效性分析，找到準(zhǔn)確率較高的方法。部分關(guān)鍵代碼如表3所示。

表3 輪廓系數(shù)評估不同算法的整體聚類效果

3 實驗結(jié)果與分析

實驗數(shù)據(jù)集由真實網(wǎng)絡(luò)環(huán)境獲取，協(xié)議是否已知并不影響聚類的準(zhǔn)確度，為了更好地檢驗聚類效果，本文采用已知二進(jìn)制協(xié)議代替未知協(xié)議。分別用P1、P2、P3、P4和P5 代表采集的四種未知二進(jìn)制協(xié)議比特流子集：ARP、DNS、ICMP、TCP和SMB，樣本量均別為150條。不失一般性，假定所有協(xié)議已近做了初步切分，數(shù)據(jù)報文均從對應(yīng)協(xié)議頭部開始并且包含數(shù)據(jù)部分。取最短數(shù)據(jù)報文長度144 bit。

為了更好地分析輪廓系數(shù)的評估效果，將測試數(shù)據(jù)分為4組：第一組P1、P2；第二組P1、P2、P3 ；第三組P1、P2、P3、P4；第四組P1、P2、P3、P4、P5。

分別用3種算法對第四組數(shù)據(jù)進(jìn)行聚類，最終的聚類結(jié)果分布如圖3、圖4、圖5所示。

3.1 互信息效果評估結(jié)果與分析

為驗證互信息效果評估的有效性，采用改進(jìn)的K-means算法對第四組數(shù)據(jù)集進(jìn)行聚類。通過實驗得到五類聚類結(jié)果和5個最終的聚類中心。按照調(diào)整互信息聚類效果評估算法計算得到各類簇的調(diào)整互信息值以及判定屬于類簇的樣本編號。將得到的結(jié)果以樣本編號為X軸，到對應(yīng)聚類中心的調(diào)整互信息值為Y軸作圖，分析聚類效果的好壞。經(jīng)過多個數(shù)據(jù)集大量聚類及評估實驗進(jìn)行總結(jié)和比較，可以得出當(dāng)該類簇中的樣本判定的準(zhǔn)確率大于90%，則認(rèn)為聚類效果質(zhì)量較高。

圖3 k=5 傳統(tǒng)K-means聚類結(jié)果分布曲線

圖4 k=5 AGNES聚類結(jié)果分布曲線

圖5 k=5 改進(jìn)算法聚類結(jié)果分布曲線

計算第一個聚類中心與所有樣本的調(diào)整互信息值，得到的結(jié)果如圖6(a)所示。圖6中x軸是協(xié)議編號，y軸是樣本與中心的AMI值，反映的是樣本隨編號的AMI值分布情況。利用第2節(jié)定義的公式計算得到fmin=0.269 5，篩選出符合第一個聚類中心條件的樣本分布如圖6(b)所示。共計150條數(shù)據(jù)幀被判定為屬于該簇。其中全部數(shù)據(jù)幀判定準(zhǔn)確，該類簇中的樣本正確識別率為100%。

圖6 第一個中心互信息效果評估曲線

計算第二個聚類中心與所有樣本的調(diào)整互信息值，得到的結(jié)果如圖7(a)所示。利用第2節(jié)定義的公式計算得到fmin=0.260 0，篩選出符合第二個聚類中心條件的樣本分布如圖7(b)所示。共計147條數(shù)據(jù)幀被判定為屬于該簇。其中全部數(shù)據(jù)幀判定準(zhǔn)確，該類簇中的樣本正確識別率為99%。

計算第三個聚類中心與所有樣本的調(diào)整互信息值，得到的結(jié)果如圖8(a)所示。利用第2節(jié)定義的公式計算得到fmin=0.384 8，篩選出符合第三個聚類中心條件的樣本分布如圖8(b)所示。共計 142條數(shù)據(jù)幀被判定為屬于該簇。其中全部數(shù)據(jù)幀判定準(zhǔn)確，該類簇中的樣本正確識別率為100%。

圖8 第三個中心互信息效果評估曲線

計算第四個聚類中心與所有樣本的調(diào)整互信息值，得到的結(jié)果如圖9(a)所示。利用第2節(jié)定義的公式計算得到fmin=0.053 6，篩選出符合第四個聚類中心條件的樣本分布如圖9(b)所示。共計152條數(shù)據(jù)幀被判定為屬于該簇。其中117條數(shù)據(jù)幀準(zhǔn)確，該類簇中的樣本正確識別率為91%。

圖9 第四個中心互信息效果評估曲線

計算第五個聚類中心與所有樣本的調(diào)整互信息值，得到的結(jié)果如圖10(a)所示。利用第2節(jié)定義的公式計算得到fmin=0.270 6，篩選出符合第五個聚類中心條件的樣本分布如圖10(b)所示。共計 150條數(shù)據(jù)幀被判定為屬于該簇。其中全部數(shù)據(jù)幀判定準(zhǔn)確，該類簇中的樣本正確識別率為100%。

圖10 第五個中心互信息效果評估曲線

由于采用已知協(xié)議代替未知協(xié)議，當(dāng)k=5時，采用改進(jìn)的K-means算法對第四組數(shù)據(jù)集進(jìn)行聚類，計算得聚類準(zhǔn)確率為98.9%，評估方案正確識別率為97.8%?；谡{(diào)整互信息的聚類效果評估如表4所示，表4中每列數(shù)據(jù)分別表示聚類后每一種協(xié)議所包含的報文條數(shù)、調(diào)整互信息評估后被判定仍然屬于該類的報文條數(shù)以及該類簇中的樣本被判定為屬于該簇的百分比。從數(shù)據(jù)來看，聚類結(jié)果符合評估標(biāo)準(zhǔn)、結(jié)果較好。

表4 k=5時聚類結(jié)果與評估結(jié)果

3.2 輪廓系數(shù)效果評估結(jié)果與分析

實驗數(shù)據(jù)包括第一、第二、第三、第四數(shù)據(jù)集，對四個數(shù)據(jù)集采用傳統(tǒng)K-means算法、Agnes算法、改進(jìn)的K-means算法進(jìn)行聚類。將實驗得到聚類結(jié)果應(yīng)用于測試輪廓系數(shù)效果評估的有效性。分別計算每種聚類結(jié)果的輪廓系數(shù)，如表5所示。由于是使用的已知協(xié)議類型的數(shù)據(jù)作為未知協(xié)議，因此可以使用精確率進(jìn)行評價。

表5 K取不同值時不同算法輪廓系數(shù)

如圖11所示，改進(jìn)K-means算法和Agnes算法的聚類效果優(yōu)于傳統(tǒng)K-means。

圖11 K取不同值時3種算法輪廓系數(shù)曲線

表6是采用3種算法分別對4組數(shù)據(jù)進(jìn)行聚類后所得聚類結(jié)果的精確率。從數(shù)據(jù)來看改進(jìn)K-means算法和Agnes算法的聚類效果大致相當(dāng)，優(yōu)于傳統(tǒng)K-means算法。這與輪廓系數(shù)的評估結(jié)果是相一致的，因此把輪廓系數(shù)作為對聚類結(jié)果整體有效性的評估方法是可行的。

表6 3種不同算法聚類結(jié)果精確率

通過對實驗結(jié)果的分析可以看出,采用互信息和輪廓系數(shù)作為二進(jìn)制協(xié)議聚類結(jié)果評估的手段是有效的,能夠?qū)ξ粗M(jìn)制協(xié)議的聚類結(jié)果進(jìn)行篩選，找到符合條件的解。

4 結(jié)論

未知數(shù)據(jù)，由于數(shù)據(jù)特征未知，只能通過“內(nèi)部指標(biāo)”衡量，一般是通過簇內(nèi)距離和簇間距離兩個方面進(jìn)行評估。當(dāng)簇內(nèi)距離最小和簇間距離最大時聚類效果最優(yōu),本文引入調(diào)整互信息和輪廓系數(shù)兩種參數(shù)，分別對聚類的簇內(nèi)聚類效果和整體聚類效果進(jìn)行評估。并以真實數(shù)據(jù)集驗證了評估的有效性。與傳統(tǒng)評估方法相比，由于采用的是K-means聚類產(chǎn)生的聚類中心，因此評估方法的時間復(fù)雜度是O(nt)，優(yōu)于傳統(tǒng)評估方法。

實驗發(fā)現(xiàn)聚類過程中類簇數(shù)目直接影響聚類的精確度。如何確定符合所需粒度的聚類簇需要進(jìn)一步研究。