基于改進(jìn)K-medoids的聚類質(zhì)量評(píng)價(jià)指標(biāo)研究①

鄒臣嵩,段桂芹

1(廣東松山職業(yè)技術(shù)學(xué)院 電氣工程系,韶關(guān) 512126)

2(廣東松山職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系,韶關(guān) 512126)

聚類是在沒有任何先驗(yàn)知識(shí)的指導(dǎo)下,從樣本集合中挖掘出潛在的相似模式,并將其劃分成多個(gè)組或簇的過(guò)程,其目的是使得簇內(nèi)相似度高,而簇間相似度低,數(shù)據(jù)對(duì)象的簇可以看做隱含的類,聚類可以自動(dòng)地發(fā)現(xiàn)這些類.由于在聚類過(guò)程中并沒有提供類的標(biāo)號(hào)信息,因此,聚類又被稱做無(wú)監(jiān)督學(xué)習(xí),對(duì)于無(wú)先驗(yàn)知識(shí)的樣本來(lái)說(shuō),如何對(duì)其聚類結(jié)果進(jìn)行有效評(píng)價(jià)是國(guó)內(nèi)外的研究熱點(diǎn),許多經(jīng)典的內(nèi)部聚類評(píng)價(jià)指標(biāo)先后被提出,如CH,I,DB,SD,BWP 等,然而這些指標(biāo)可能會(huì)受噪聲等異常的影響,因此,如何改進(jìn)或設(shè)計(jì)出更為科學(xué)合理的評(píng)價(jià)指標(biāo)是聚類評(píng)價(jià)領(lǐng)域的一個(gè)重要研究方向.此外,聚類結(jié)果評(píng)價(jià)除了和有效性指標(biāo)本身有關(guān),還與所采用的聚類算法密不可分,研究表明,沒有任何一種聚類算法可以得到所有數(shù)據(jù)集的最優(yōu)劃分[1],而應(yīng)用范圍較廣的K-means、K-medoids 及其衍生算法[2]在實(shí)際應(yīng)用中又存在一定的不足.為此,本文對(duì)常用聚類評(píng)價(jià)指標(biāo)進(jìn)行了對(duì)比分析,提出了一個(gè)新的評(píng)價(jià)指標(biāo),并對(duì)K-medoids 算法進(jìn)行了改進(jìn),在此基礎(chǔ)上,設(shè)計(jì)了聚類質(zhì)量評(píng)價(jià)模型,先后采用UCI 數(shù)據(jù)集和KDD CUP99數(shù)據(jù)集對(duì)新模型進(jìn)行了驗(yàn)證,實(shí)驗(yàn)結(jié)果表明,新評(píng)價(jià)指標(biāo)的聚類數(shù)正確率明顯高于其他四種常用指標(biāo),聚類質(zhì)量評(píng)價(jià)模型可以給出精準(zhǔn)的聚類數(shù)范圍.

1 研究現(xiàn)狀

1.1 劃分式聚類算法

劃分式聚類算法[3]在運(yùn)算前需要人工預(yù)定義聚類數(shù)k,再通過(guò)反復(fù)迭代更新各簇中心,不斷優(yōu)化(降低)目標(biāo)函數(shù)值,逐漸逼近最優(yōu)解,完成最終聚類,Kmeans 和K-medoids 是兩種典型的劃分式聚類算法.Kmeans 算法的簇中心是通過(guò)計(jì)算一個(gè)簇中對(duì)象的平均值來(lái)獲取,它根據(jù)數(shù)據(jù)對(duì)象與簇中心的距離完成"粗聚類",再通過(guò)反復(fù)迭代,將樣本從當(dāng)前簇劃分至另一個(gè)更合適的簇來(lái)逐步提高聚類質(zhì)量,其核心思想是找出k個(gè)簇中心,使得每個(gè)數(shù)據(jù)點(diǎn)到其最近的簇中心的平方距離和被最小化.該方法描述容易、實(shí)現(xiàn)簡(jiǎn)單快速,是目前研究最多的聚類方法,文獻(xiàn)[4-6]從初始簇中心的選擇、對(duì)象的劃分、相似度的計(jì)算方法、簇中心的計(jì)算方法等方面對(duì)該經(jīng)典算法進(jìn)行了改進(jìn),使其適用于不同的聚類任務(wù),但在使用中存在一些不足：簇的個(gè)數(shù)難以確定;聚類結(jié)果對(duì)初始值的選擇較敏感;算法容易陷入局部最優(yōu)值;對(duì)噪音和異常數(shù)據(jù)敏感;不能用于發(fā)現(xiàn)非凸形狀的簇,或具有各種不同規(guī)模的簇.

當(dāng)樣本中存在一個(gè)或多個(gè)極值對(duì)象時(shí),采用均值算法會(huì)顯著地扭曲數(shù)據(jù)的分布,而平方誤差函數(shù)的使用會(huì)進(jìn)一步地?cái)U(kuò)大這一影響,針對(duì)這一問(wèn)題,Kmedoids 通過(guò)試圖最小化所有對(duì)象與其所屬簇的中心點(diǎn)之間的絕對(duì)誤差之和的方式找出簇中心點(diǎn).典型基于中心的劃分方法有PAM、CLARA 和CLARANS[7],雖然K-medoids[8]算法對(duì)噪聲和異常數(shù)據(jù)的敏感程度有所改善,但仍依賴于初始類簇中心的隨機(jī)選擇,且更新類簇中心時(shí)采用全局最優(yōu)搜索,故耗時(shí)較多.文獻(xiàn)[9]提出一種快速K-medoids 算法,從初始聚類中心選擇、類簇中心更新方法兩方面對(duì)PAM 算法進(jìn)行改進(jìn),基本思想是：首先計(jì)算數(shù)據(jù)集中每個(gè)樣本的密度,選擇前k個(gè)位于樣本分布密集區(qū)域的樣本為初始聚類中心,再將其余樣本分配到距離最近的類簇中心,產(chǎn)生初始聚類結(jié)果;然后,在每個(gè)類簇內(nèi)部找一個(gè)新中心,使該簇非中心樣本到中心樣本距離之和最小,進(jìn)而得到k個(gè)新中心;最后按距離最近原則,重新分配所有非中心樣本到最近類簇中心,如果本次迭代所得聚類結(jié)果與前一次不同,則轉(zhuǎn)至下一次迭代,否則算法停止.在實(shí)際應(yīng)用中,該算法的初始中心在一定程度上存在過(guò)于集中的可能,因此,從樣本的空間結(jié)構(gòu)來(lái)看,各中心點(diǎn)的分散程度不高,代表性依然不足.

1.2 內(nèi)部評(píng)價(jià)指標(biāo)

聚類有效性評(píng)價(jià)指標(biāo)是對(duì)聚類結(jié)果進(jìn)行優(yōu)劣判斷的依據(jù),通過(guò)比較指標(biāo)值可以確定最佳聚類劃分和最優(yōu)聚類數(shù),在對(duì)聚類結(jié)果進(jìn)行評(píng)估時(shí),內(nèi)部評(píng)價(jià)指標(biāo)在不涉及任何外部信息的條件下,僅依賴數(shù)據(jù)集自身的特征和度量值,通過(guò)計(jì)算簇內(nèi)部平均相似度、簇間平均相似度或整體相似度來(lái)評(píng)價(jià)聚類效果的優(yōu)劣和判斷簇的最優(yōu)個(gè)數(shù).理想的聚類效果是簇內(nèi)緊密且簇間分離,因此,常用內(nèi)部評(píng)價(jià)指標(biāo)的主要思想是通過(guò)簇內(nèi)距離和簇間距離的某種形式的比值來(lái)度量的.

為便于對(duì)各指標(biāo)和本文算法進(jìn)行描述,設(shè)樣本集合X={x1,x2,…,xi,…,xN},|X|=N,各樣本特征數(shù)為p,該樣本集由k個(gè)簇構(gòu)成,即X={C1,C2,…,Ck},每簇樣本數(shù)為n,c為樣本集的均值中心,簇中心集合V={v1,v2,…,vk}(k＜N),常見的內(nèi)部評(píng)價(jià)指標(biāo)及其特點(diǎn)如下：

(1)DB 指標(biāo)(Davies-Bouldin Index)[10]

DB 指標(biāo)將相鄰兩簇的簇中各樣本與簇中心的平均距離之和作為簇內(nèi)距離,將相鄰兩簇的簇中心間的距離作為簇間距離,取二者比值最大者作為該簇的相似度,再對(duì)所有簇的相似度取平均值得到樣本集的DB 指標(biāo).可以看出,該指標(biāo)越小意味著各簇間的相似度越低,從而對(duì)應(yīng)更佳的聚類結(jié)果.DB 指標(biāo)適合評(píng)價(jià)"簇內(nèi)緊湊,簇間遠(yuǎn)離"的數(shù)據(jù)集,但當(dāng)數(shù)據(jù)集的重疊度較大(如：當(dāng)遇到環(huán)狀分布數(shù)據(jù)時(shí)),由于各簇的中心點(diǎn)重疊,因此DB 指標(biāo)很難對(duì)其形成正確的聚類評(píng)價(jià).

(2)CH 指標(biāo)(Calinski-Harabasz)[11]

CH 指標(biāo)將各簇中心點(diǎn)與樣本集的均值中心的距離平方和作為數(shù)據(jù)集的分離度,將簇中各點(diǎn)與簇中心的距離平方和作為簇內(nèi)的緊密度,將分離度與緊密度的比值視為CH 的最終指標(biāo).該指標(biāo)越大表示各簇之間分散程度越高,簇內(nèi)越緊密,聚類結(jié)果越優(yōu).Milligan 在文獻(xiàn)[12]中,對(duì)CH 等評(píng)價(jià)指標(biāo)的性能進(jìn)行了深入探討,實(shí)驗(yàn)結(jié)果表明：CH 指標(biāo)在多數(shù)情況下,都要優(yōu)于其它的指標(biāo),但當(dāng)聚類數(shù)趨近于樣本容量N時(shí),各樣本自成一簇,簇中心即為樣本自身,此時(shí)簇內(nèi)距離和約等于0,分母為極小值,CH 指標(biāo)將趨于最大,此時(shí)的聚類評(píng)價(jià)結(jié)果無(wú)實(shí)際意義.

(3)XB 指標(biāo)(Xie-Beni)[13]

和CH 指標(biāo)一樣,XB 也是將簇內(nèi)緊密度與簇間分離度的比值作為指標(biāo)的表達(dá)式,期望在簇內(nèi)緊密度與簇間分離度之間尋找一個(gè)新的平衡點(diǎn),使其達(dá)到一個(gè)理想化的極值,從而得到最優(yōu)的聚類結(jié)果.與CH 指標(biāo)不同是：XB 指標(biāo)使用最小簇中心距離的平方作為整個(gè)樣本集的分離度.

(4)Sil 指標(biāo)(Silhouette-Coefficient)[14]

式中,a(x)是樣本x所屬簇的簇內(nèi)凝聚程度,用x與其同一個(gè)簇內(nèi)的所有元素距離的平均值來(lái)表示,凝聚度a(x)定義為：

式中,b(x)是樣本x與其他簇的簇間分離程度,用x與其它簇之間平均距離的最小值來(lái)表示,分離度b(x)定義為：

從式(4)可以看出,當(dāng)簇內(nèi)距離減小,簇間距離增大時(shí),Sil 指標(biāo)值增大,聚類結(jié)果趨于理想,因此,要取得最佳聚類,就需要減少簇內(nèi)各點(diǎn)之間的距離,同時(shí)增大簇間的距離.然而,與CH 指標(biāo)類似,當(dāng)數(shù)據(jù)接近散點(diǎn)狀分布時(shí),聚類結(jié)果并不理想,此外,當(dāng)數(shù)據(jù)成條狀分布的時(shí),各簇中心非常接近,且聚類結(jié)果非常理想,但Sil 指標(biāo)此時(shí)最小,并不能對(duì)聚類結(jié)果做出客觀的評(píng)價(jià).

2 聚類質(zhì)量評(píng)價(jià)模型

聚類質(zhì)量評(píng)價(jià)模型由聚類算法和內(nèi)部評(píng)價(jià)指標(biāo)兩部分構(gòu)成,鑒于K-medoids 算法及其改進(jìn)算法在初始聚類中心選擇階段存在的問(wèn)題,以及上述常用內(nèi)部評(píng)價(jià)指標(biāo)存在的缺陷,本文對(duì)二者分別進(jìn)行了改進(jìn),具體如下.

2.1 改進(jìn)K 中心點(diǎn)聚類算法

本文在文獻(xiàn)[7,8]的基礎(chǔ)上,選取被其他樣本緊密圍繞且相對(duì)分散的數(shù)據(jù)對(duì)象作為初始聚類中心,使得中心點(diǎn)在確保自身密度較大的同時(shí)還具備良好的獨(dú)立性.基本思路是：首先通過(guò)計(jì)算樣本集中各樣本間的距離得到樣本集的距離矩陣;將樣本集與各樣本的平均距離的比值作為樣本的密度,選取密度值最高的α個(gè)樣本存入高密度點(diǎn)集合H中,α表示候選代表點(diǎn)在樣本集中所占的比例,該值可由用戶指定,本文實(shí)驗(yàn)環(huán)節(jié)中的α值為30%;從集合H中選取相對(duì)分散且具有較高密度的初始中心存入集合V,即V={v1,v2,…,vk}.最后,借鑒文獻(xiàn)[7]的算法,將各樣本按最小距離分配至相應(yīng)簇中,重復(fù)這一過(guò)程,直至準(zhǔn)則函數(shù)收斂,本文算法的定義和公式如下.

定義1.空間任意兩點(diǎn)間的歐氏距離定義為

其中,i=1,2,…,N;j=1,2,…,N

定義2.數(shù)據(jù)對(duì)象xi的平均距離定義為：xi與全部樣本的距離之和除以樣本集的總個(gè)數(shù).

定義3.樣本集的平均距離定義為：各數(shù)據(jù)對(duì)象間的距離總和除以從樣本集中任選兩個(gè)對(duì)象的所有排列次數(shù).

定義4.數(shù)據(jù)對(duì)象xi的密度定義為：樣本集的平均距離與數(shù)據(jù)對(duì)象xi的平均距離的比值.

定義5.數(shù)據(jù)對(duì)象xi與所屬簇的各數(shù)據(jù)對(duì)象的距離之和為：

其中,xi,xj∈Ct,t=1,2,…,k

定義6.簇Ct的簇內(nèi)距離和矩陣為：

其中,t=1,2,…,k

定義7.數(shù)據(jù)對(duì)象xi在簇更新過(guò)程中被視為簇中心的條件為：

其中,xi∈Ct,t=1,2,…,k

定義8.聚類誤差平方和E的定義為

其中,xtj是第t簇的第j個(gè)數(shù)據(jù)對(duì)象,vt是第t簇的中心.

2.2 聚類有效性指標(biāo)Improve-XB

在對(duì)無(wú)先驗(yàn)知識(shí)樣本的聚類結(jié)果進(jìn)行評(píng)價(jià)時(shí),通常將“簇內(nèi)緊密,簇間分離”作為內(nèi)部評(píng)價(jià)的重要標(biāo)準(zhǔn),文獻(xiàn)[11]和文獻(xiàn)[13]將各簇中心之間的距離作為簇間距離,可能會(huì)出現(xiàn)因簇中心重疊而導(dǎo)致聚類評(píng)價(jià)結(jié)果失效等問(wèn)題,為此本文提出：使用兩個(gè)簇的最近邊界點(diǎn)間的距離取代簇中心之間的距離,為了便于分析,以圖1所示的人工數(shù)據(jù)集進(jìn)行說(shuō)明,該數(shù)據(jù)集由三個(gè)環(huán)形結(jié)構(gòu)的簇構(gòu)成,各簇中心極為接近,從DB、XB 指標(biāo)公式可知,在計(jì)算該數(shù)據(jù)集的簇間距離時(shí),由于簇中心點(diǎn)趨于重疊,必然會(huì)出現(xiàn)簇間距離近似于0 的情況,當(dāng)以"簇內(nèi)緊密,簇間分離"作為評(píng)判依據(jù)時(shí),意味著此時(shí)簇間的相似度極高,從聚類劃分的角度來(lái)看,應(yīng)將二者合并為一簇以提高聚類質(zhì)量,而事實(shí)上,這種錯(cuò)誤的劃分將導(dǎo)致圖1的最終聚類全部合并為一個(gè)簇,這顯然與真實(shí)的結(jié)果有著明顯偏差.而本文使用簇間最近邊界點(diǎn)間的距離表示簇間距離,則可以從幾何特征上確保各簇的結(jié)構(gòu)差異性,進(jìn)而避免簇間距離為0 現(xiàn)象的發(fā)生,最大程度地反映出簇間的相似程度,克服了環(huán)狀中心點(diǎn)因重疊而導(dǎo)致的聚類結(jié)果合并等問(wèn)題,新指標(biāo)IXB 定義及公式如下.

定義9.簇內(nèi)緊密度(Compactness)定義為：各樣本與所屬簇的中心點(diǎn)的距離平方和.實(shí)質(zhì)為：

定義10.簇間分離度(Separation)定義為：簇間最鄰近邊界點(diǎn)的距離平方和與簇內(nèi)樣本個(gè)數(shù)的乘積.

其中,xi和xj是簇Ci和Cj之間距離最近的邊界點(diǎn).

定義11.IXB 指標(biāo)定義為簇內(nèi)緊密度與簇間分離度的比值與其倒數(shù)之和,即實(shí)質(zhì)為：

定義12.最優(yōu)聚類數(shù)k定義為IXB(k)取最大值時(shí)的聚類數(shù)目,即：

其中,kmin=2,kmax采用文獻(xiàn)[15]的AP 算法得到.

圖1 環(huán)狀分布數(shù)據(jù)集

IXB 指標(biāo)由兩部分組成：Sep/Comp隨著聚類數(shù)k的增加而遞增,Comp/Sep隨著聚類數(shù)k的增加而遞減,可以看出,IXB 指標(biāo)通過(guò)制衡Sep/Comp和Comp/Sep之間的關(guān)系,確保了最優(yōu)聚類劃分,IXB 越大,意味著聚類質(zhì)量越好.

2.3 聚類質(zhì)量評(píng)價(jià)模型描述

將改進(jìn)的K 中心點(diǎn)算法與IXB 指標(biāo)相結(jié)合,構(gòu)建聚類質(zhì)量評(píng)價(jià)模型如圖2所示,模型描述如下：

圖2 聚類質(zhì)量評(píng)價(jià)模型

(1)根據(jù)式(6)～(8)依次計(jì)算整個(gè)樣本集的任意兩點(diǎn)間的歐氏距離、各數(shù)據(jù)對(duì)象的平均距離和樣本集的平均距離.

(2)根據(jù)式(10)計(jì)算各數(shù)據(jù)對(duì)象的密度,選取密度值最高的α個(gè)樣本存入候選初始中心集合H中,令k=2.

(3)根據(jù)式(6)將集合H中相距最遠(yuǎn)的兩個(gè)高密度點(diǎn)v1和v2存入初始中心集合V中.

(4)從H中選擇滿足與v1、v2距離乘積最大的v3,將其存儲(chǔ)至V中.依次類推,得到相對(duì)分散且具有較高密度的初始中心集合V,V={v1,v2,…,vk}.

(5)在更新簇中心階段,根據(jù)式(11)、式(12)得到簇內(nèi)距離和矩陣,根據(jù)式(13)選出新的簇中心,沿用文獻(xiàn)[7]的算法,將各樣本按最小距離分配至相應(yīng)簇中,重復(fù)這一過(guò)程,直至準(zhǔn)則函數(shù)式(14)收斂.

(6)使用式(17)計(jì)算IXB 指標(biāo),對(duì)當(dāng)前聚類結(jié)果進(jìn)行評(píng)價(jià),令k=k+1,重復(fù)步驟(4),直至k=kmax.

(7)使用式(18),將IXB 取最大值時(shí)的k值作為最優(yōu)聚類數(shù).

2.4 模型的性能分析

本文算法將樣本集與各樣本的平均距離比值作為樣本的密度,將高密度點(diǎn)視為候選簇中心,確保了聚類中心的代表性,使用最大乘積法對(duì)高密度點(diǎn)進(jìn)行二次篩選,增強(qiáng)了候選簇中心在空間上的離散程度,使得聚類中心兼具代表性和分散性,提高了逼近全局最優(yōu)解的概率,這樣選擇的初始聚類中心更符合樣本的分布特征,甚至有可能位于真實(shí)的簇中心,因此,所得到的初步聚類劃分與樣本的真實(shí)分布更加接近.在聚類結(jié)果評(píng)價(jià)方面,通過(guò)將簇間最鄰近邊界點(diǎn)的距離平方和與簇內(nèi)樣本個(gè)數(shù)的乘積作為簇間分離度,在簇內(nèi)緊密度與簇間分離度之間尋找一個(gè)新的平衡點(diǎn),從而得到一個(gè)理想化的極值,通過(guò)搜索該極值,即可有效地完成最優(yōu)聚類劃分,確定最優(yōu)聚類數(shù)目k,從而得到更好的聚類結(jié)果,從整體上提升無(wú)先驗(yàn)知識(shí)樣本的檢測(cè)率和分類正確率等評(píng)價(jià)指標(biāo).

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

實(shí)驗(yàn)分為兩個(gè)部分,第一部分對(duì)聚類質(zhì)量評(píng)價(jià)模型的有效性進(jìn)行了驗(yàn)證：首先選用表1中的UCI 數(shù)據(jù)集對(duì)本文算法和其他改進(jìn)算法的準(zhǔn)確率、迭代次數(shù)、總耗時(shí)進(jìn)行了對(duì)比測(cè)試,然后使用本文算法依次結(jié)合IXB 及其它4 個(gè)評(píng)價(jià)指標(biāo)完成了聚類數(shù)對(duì)比測(cè)試;第二部分將模型應(yīng)用于數(shù)據(jù)集KDD CUP99,從檢測(cè)率、分類正確率、漏報(bào)率三個(gè)方面驗(yàn)證模型的實(shí)用性.本文實(shí)驗(yàn)環(huán)境：Intel(R)Core(TM)i3-3240 CPU @3.40 GHz,8 GB 內(nèi)存,Win10 專業(yè)版,實(shí)驗(yàn)平臺(tái)Matlab 2011b.

表1 實(shí)驗(yàn)數(shù)據(jù)

3.1 聚類質(zhì)量評(píng)價(jià)模型的有效性測(cè)試

(1)改進(jìn)聚類算法的對(duì)比測(cè)試

從表2～表4的實(shí)驗(yàn)對(duì)比結(jié)果可以看出,改進(jìn)聚類算法的聚類準(zhǔn)確率、迭代次數(shù)和總耗時(shí)全部?jī)?yōu)于其他四種算法,主要原因在于K 中心點(diǎn)的初始中心隨機(jī)分布令迭代次數(shù)與總耗時(shí)同時(shí)增加,而文獻(xiàn)[7]的初始中心點(diǎn)過(guò)于集中,文獻(xiàn)[8]的初始中心雖然具有一定的分散性,但每次迭代都將簇平均值作為簇中心,個(gè)別維度存在受異常數(shù)據(jù)影響的隱患,因此,本文算法的整體耗時(shí)要低于文獻(xiàn)[7,8]算法.需要特別指出的是,由于本文算法的初始聚類中心同時(shí)兼具代表性和分散性,不僅提高了聚類準(zhǔn)確率,同時(shí)還降低了算法后期的迭代次數(shù),因此,對(duì)算法的運(yùn)算效率的提升產(chǎn)生了正向的推動(dòng)作用.

表2 聚類準(zhǔn)確率比較

表3 迭代次數(shù)

表4 聚類總耗時(shí)(單位：s)

(2)IXB 指標(biāo)的有效性對(duì)比測(cè)試

觀察表5可知,IXB 在5 個(gè)UCI 數(shù)據(jù)集上的聚類數(shù)正確率為80%,而DB、CH、XB 和Sil 指標(biāo)依次為40%,60%,40%,60%,IXB 指標(biāo)的聚類數(shù)正確率明顯高于其他四種指標(biāo).

3.2 聚類質(zhì)量評(píng)價(jià)模型在KDD CUP99 中的應(yīng)用

本實(shí)驗(yàn)環(huán)節(jié)選取KDD CUP99[16]訓(xùn)練集中的17330 條記錄作為訓(xùn)練數(shù)據(jù),從corrected 數(shù)據(jù)集中隨機(jī)抽取11420 條數(shù)據(jù)作為測(cè)試集用于檢驗(yàn)?zāi)Ｐ偷男阅?為提高整體運(yùn)行效率,在數(shù)據(jù)預(yù)處理方面,首先使用獨(dú)熱編碼完成字符數(shù)據(jù)的格式轉(zhuǎn)換,再通過(guò)屬性簡(jiǎn)約法將數(shù)據(jù)集的41 個(gè)特征約簡(jiǎn)為15 個(gè)[17],最后將數(shù)據(jù)集歸一化處理,形成新樣本集,KDD CUP99 數(shù)據(jù)描述如表6.

表5 各內(nèi)部評(píng)價(jià)指標(biāo)聚類數(shù)對(duì)比

表6 KDD CUP99 數(shù)據(jù)集

(1)最優(yōu)k值的獲取

借鑒文獻(xiàn)[15],使用AP 算法對(duì)樣本集完成"粗聚類"得到訓(xùn)練集的最大聚類數(shù)kmax=29,如圖3所示,在訓(xùn)練過(guò)程中,當(dāng)15≤k≤20 時(shí),K 中心點(diǎn)算法的IXB 增幅較大,當(dāng)k=20 時(shí),IXB 達(dá)到峰值,此后,隨著k值的不斷增大,IXB 總體呈下降趨勢(shì);文獻(xiàn)[8],文獻(xiàn)[9]和本文算法的IXB 隨著k值的不斷增大而緩慢增加,當(dāng)25≤k≤28 時(shí),三種算法的IXB 依次達(dá)到峰值,此后隨著k值的再次增大,IXB 緩慢下降.由定義11 可知,當(dāng)IXB 最大時(shí)k值即為最優(yōu),因此,三種算法使用IXB 得到訓(xùn)練集的最優(yōu)k值分別為：k文獻(xiàn)[8]=26,k文獻(xiàn)[9]=28,k本文算法=28.

(2)IXB 對(duì)入侵檢測(cè)指標(biāo)的影響

在驗(yàn)證IXB 是否有助于提高檢測(cè)精度的環(huán)節(jié)中,將圖3中IXB 緩慢上升至峰值,再?gòu)姆逯稻徛陆档倪@一階段所對(duì)應(yīng)的多個(gè)連續(xù)k值定義為最優(yōu)聚類數(shù)范圍,并對(duì)該范圍內(nèi)的各入侵檢測(cè)指標(biāo)進(jìn)行對(duì)比,由于K 中心點(diǎn)算法的隨機(jī)性較強(qiáng),各項(xiàng)指標(biāo)與k值之間無(wú)明顯規(guī)律可循,因此,這里僅對(duì)其他三種算法的結(jié)果進(jìn)行統(tǒng)計(jì)與分析.

圖3 訓(xùn)練集的IXB-K 的關(guān)系圖

如圖4所示,當(dāng)聚類數(shù)在[26,28]范圍內(nèi)時(shí),3 種算法的檢測(cè)率達(dá)到了最大,分別是：92.68%、91.69%、93.2%.

圖4 不同k值的檢測(cè)率

從圖5的漏報(bào)率對(duì)比結(jié)果中可以看出：當(dāng)聚類數(shù)在[26,27]范圍內(nèi)時(shí),文獻(xiàn)[8]和本文算法的漏報(bào)率最小,分別是：3.81%、2.86%.

圖5 不同k值的漏報(bào)率

圖6的正確分類率結(jié)果表明：當(dāng)聚類數(shù)在[27,28]范圍內(nèi)時(shí),3 種算法的正確分類率達(dá)到最大,分別是：94.27%、94.38%、94.78%.從圖4～6 可以看出,IXB 越大,入侵檢測(cè)指標(biāo)越優(yōu).綜上所述,本文提出的IXB 能夠合理、客觀地評(píng)價(jià)聚類結(jié)果,能夠準(zhǔn)確地反映出聚類質(zhì)量,可以為無(wú)先驗(yàn)知識(shí)樣本集的有效聚類提供重要參考依據(jù).

圖6 不同k值的分類正確率

5 結(jié)語(yǔ)

針對(duì)K 中心點(diǎn)算法的初始聚類中心代表性不足,穩(wěn)定性差等問(wèn)題,提出了一種改進(jìn)的K 中心點(diǎn)算法,將樣本集與樣本的各自平均距離比值作為樣本的密度參數(shù),采用最大距離乘積法選擇密度較大且距離較遠(yuǎn)的k個(gè)樣本作為初始聚類中心,兼顧聚類中心的代表性和分散性.針對(duì)常用內(nèi)部評(píng)價(jià)指標(biāo)在聚類評(píng)價(jià)中的局限性,提出將簇間邊界最近點(diǎn)的距離平方作為整個(gè)樣本集的分離度,定義了以簇內(nèi)緊密度與簇間分離度的比值與其倒數(shù)之和為度量值的內(nèi)部評(píng)價(jià)指標(biāo)IXB,結(jié)合改進(jìn)的K 中心點(diǎn)算法設(shè)計(jì)了聚類質(zhì)量評(píng)價(jià)模型.在UCI 數(shù)據(jù)集的測(cè)試表明,IXB 指標(biāo)的聚類數(shù)正確率明顯高于其他四種常用指標(biāo),在KDD CUP99 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明,本文提出的聚類質(zhì)量評(píng)價(jià)模型可以給出精準(zhǔn)的聚類數(shù)范圍,能夠在保持較低漏報(bào)率的同時(shí),有效提高入侵檢測(cè)率和分類正確率.