基于互信息和輪廓系數(shù)的聚類結(jié)果評(píng)估方法

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

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

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

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

1.1 聚類性能度量

聚類性能度量也稱為聚類的有效性指標(biāo)，用來(lái)評(píng)估聚類結(jié)果的好壞。從提高聚類精度的角度出發(fā)，如果確定了所需要的性能度量，那么我們就可以將該性能度量引入聚類過(guò)程中的優(yōu)化函數(shù)，得到更加符合需求的結(jié)果。一般來(lái)說(shuō)聚類性能度量可分為兩類，分別為外部指標(biāo)和內(nèi)部指標(biāo)。外部指標(biāo)將聚類結(jié)果與某個(gè)外部模型進(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ù)簡(jiǎn)稱DBI，Dunn指數(shù)簡(jiǎn)稱DI。分別表示如下；

(1)

(2)

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

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

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

1.2 調(diào)整互信息

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

(3)

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

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

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

(4)

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

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

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

1.3 輪廓系數(shù)

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

(5)

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

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

(6)

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

2 聚類效果評(píng)估

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

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

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

2.2 基于互信息的聚類效果評(píng)估

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

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

(7)

(8)

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

(9)

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

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

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

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

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

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

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

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

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

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

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

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

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

為驗(yàn)證互信息效果評(píng)估的有效性，采用改進(jìn)的K-means算法對(duì)第四組數(shù)據(jù)集進(jìn)行聚類。通過(guò)實(shí)驗(yàn)得到五類聚類結(jié)果和5個(gè)最終的聚類中心。按照調(diào)整互信息聚類效果評(píng)估算法計(jì)算得到各類簇的調(diào)整互信息值以及判定屬于類簇的樣本編號(hào)。將得到的結(jié)果以樣本編號(hào)為X軸，到對(duì)應(yīng)聚類中心的調(diào)整互信息值為Y軸作圖，分析聚類效果的好壞。經(jīng)過(guò)多個(gè)數(shù)據(jù)集大量聚類及評(píng)估實(shí)驗(yàn)進(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é)果分布曲線

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

圖6 第一個(gè)中心互信息效果評(píng)估曲線

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

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

圖8 第三個(gè)中心互信息效果評(píng)估曲線

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

圖9 第四個(gè)中心互信息效果評(píng)估曲線

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

圖10 第五個(gè)中心互信息效果評(píng)估曲線

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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