基于改進K-medoids的聚類質量評價指標研究①

鄒臣嵩,段桂芹

1(廣東松山職業技術學院 電氣工程系,韶關 512126)

2(廣東松山職業技術學院 計算機系,韶關 512126)

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

1 研究現狀

1.1 劃分式聚類算法

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

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

1.2 內部評價指標

聚類有效性評價指標是對聚類結果進行優劣判斷的依據,通過比較指標值可以確定最佳聚類劃分和最優聚類數,在對聚類結果進行評估時,內部評價指標在不涉及任何外部信息的條件下,僅依賴數據集自身的特征和度量值,通過計算簇內部平均相似度、簇間平均相似度或整體相似度來評價聚類效果的優劣和判斷簇的最優個數.理想的聚類效果是簇內緊密且簇間分離,因此,常用內部評價指標的主要思想是通過簇內距離和簇間距離的某種形式的比值來度量的.

為便于對各指標和本文算法進行描述,設樣本集合X={x1,x2,…,xi,…,xN},|X|=N,各樣本特征數為p,該樣本集由k個簇構成,即X={C1,C2,…,Ck},每簇樣本數為n,c為樣本集的均值中心,簇中心集合V={v1,v2,…,vk}(k＜N),常見的內部評價指標及其特點如下：

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

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

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

CH 指標將各簇中心點與樣本集的均值中心的距離平方和作為數據集的分離度,將簇中各點與簇中心的距離平方和作為簇內的緊密度,將分離度與緊密度的比值視為CH 的最終指標.該指標越大表示各簇之間分散程度越高,簇內越緊密,聚類結果越優.Milligan 在文獻[12]中,對CH 等評價指標的性能進行了深入探討,實驗結果表明：CH 指標在多數情況下,都要優于其它的指標,但當聚類數趨近于樣本容量N時,各樣本自成一簇,簇中心即為樣本自身,此時簇內距離和約等于0,分母為極小值,CH 指標將趨于最大,此時的聚類評價結果無實際意義.

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

和CH 指標一樣,XB 也是將簇內緊密度與簇間分離度的比值作為指標的表達式,期望在簇內緊密度與簇間分離度之間尋找一個新的平衡點,使其達到一個理想化的極值,從而得到最優的聚類結果.與CH 指標不同是：XB 指標使用最小簇中心距離的平方作為整個樣本集的分離度.

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

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

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

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

2 聚類質量評價模型

聚類質量評價模型由聚類算法和內部評價指標兩部分構成,鑒于K-medoids 算法及其改進算法在初始聚類中心選擇階段存在的問題,以及上述常用內部評價指標存在的缺陷,本文對二者分別進行了改進,具體如下.

2.1 改進K 中心點聚類算法

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

定義1.空間任意兩點間的歐氏距離定義為

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

定義2.數據對象xi的平均距離定義為：xi與全部樣本的距離之和除以樣本集的總個數.

定義3.樣本集的平均距離定義為：各數據對象間的距離總和除以從樣本集中任選兩個對象的所有排列次數.

定義4.數據對象xi的密度定義為：樣本集的平均距離與數據對象xi的平均距離的比值.

定義5.數據對象xi與所屬簇的各數據對象的距離之和為：

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

定義6.簇Ct的簇內距離和矩陣為：

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

定義7.數據對象xi在簇更新過程中被視為簇中心的條件為：

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

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

其中,xtj是第t簇的第j個數據對象,vt是第t簇的中心.

2.2 聚類有效性指標Improve-XB

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

定義9.簇內緊密度(Compactness)定義為：各樣本與所屬簇的中心點的距離平方和.實質為：

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

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

定義11.IXB 指標定義為簇內緊密度與簇間分離度的比值與其倒數之和,即實質為：

定義12.最優聚類數k定義為IXB(k)取最大值時的聚類數目,即：

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

圖1 環狀分布數據集

IXB 指標由兩部分組成：Sep/Comp隨著聚類數k的增加而遞增,Comp/Sep隨著聚類數k的增加而遞減,可以看出,IXB 指標通過制衡Sep/Comp和Comp/Sep之間的關系,確保了最優聚類劃分,IXB 越大,意味著聚類質量越好.

2.3 聚類質量評價模型描述

將改進的K 中心點算法與IXB 指標相結合,構建聚類質量評價模型如圖2所示,模型描述如下：

圖2 聚類質量評價模型

(1)根據式(6)～(8)依次計算整個樣本集的任意兩點間的歐氏距離、各數據對象的平均距離和樣本集的平均距離.

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

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

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

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

(6)使用式(17)計算IXB 指標,對當前聚類結果進行評價,令k=k+1,重復步驟(4),直至k=kmax.

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

2.4 模型的性能分析

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

3 實驗結果與分析

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

表1 實驗數據

3.1 聚類質量評價模型的有效性測試

(1)改進聚類算法的對比測試

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

表2 聚類準確率比較

表3 迭代次數

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

(2)IXB 指標的有效性對比測試

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

3.2 聚類質量評價模型在KDD CUP99 中的應用

本實驗環節選取KDD CUP99[16]訓練集中的17330 條記錄作為訓練數據,從corrected 數據集中隨機抽取11420 條數據作為測試集用于檢驗模型的性能.為提高整體運行效率,在數據預處理方面,首先使用獨熱編碼完成字符數據的格式轉換,再通過屬性簡約法將數據集的41 個特征約簡為15 個[17],最后將數據集歸一化處理,形成新樣本集,KDD CUP99 數據描述如表6.

表5 各內部評價指標聚類數對比

表6 KDD CUP99 數據集

(1)最優k值的獲取

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

(2)IXB 對入侵檢測指標的影響

在驗證IXB 是否有助于提高檢測精度的環節中,將圖3中IXB 緩慢上升至峰值,再從峰值緩慢下降的這一階段所對應的多個連續k值定義為最優聚類數范圍,并對該范圍內的各入侵檢測指標進行對比,由于K 中心點算法的隨機性較強,各項指標與k值之間無明顯規律可循,因此,這里僅對其他三種算法的結果進行統計與分析.

圖3 訓練集的IXB-K 的關系圖

如圖4所示,當聚類數在[26,28]范圍內時,3 種算法的檢測率達到了最大,分別是：92.68%、91.69%、93.2%.

圖4 不同k值的檢測率

從圖5的漏報率對比結果中可以看出：當聚類數在[26,27]范圍內時,文獻[8]和本文算法的漏報率最小,分別是：3.81%、2.86%.

圖5 不同k值的漏報率

圖6的正確分類率結果表明：當聚類數在[27,28]范圍內時,3 種算法的正確分類率達到最大,分別是：94.27%、94.38%、94.78%.從圖4～6 可以看出,IXB 越大,入侵檢測指標越優.綜上所述,本文提出的IXB 能夠合理、客觀地評價聚類結果,能夠準確地反映出聚類質量,可以為無先驗知識樣本集的有效聚類提供重要參考依據.

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

5 結語

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