面向模糊C 均值算法的MAME 聚類有效性指標

唐益明，陳仁好，李冰

（合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥 230601）

在大數(shù)據(jù)時代，數(shù)據(jù)無所不在，如何從海量的數(shù)據(jù)中挖掘出有價值的信息變成了一個重要的問題[1-4]。日常生活中產(chǎn)生的各種數(shù)據(jù)無一不蘊含著各種各樣豐富的信息。生產(chǎn)的數(shù)據(jù)只有經(jīng)過加工和處理，才能夠提煉出真正有價值的信息，其中一個重要的處理機制就是聚類。

聚類將相似性高的數(shù)據(jù)點劃分到同一簇內(nèi)，相似性低的數(shù)據(jù)點分離出去。作為一種無監(jiān)督的機器學(xué)習(xí)方法[5-8]，在對海量的數(shù)據(jù)聚類后，將能提取出有價值的信息。按照是否能將數(shù)據(jù)集中每個樣本只劃分至一個簇，又可分為硬聚類和模糊聚類。硬聚類的“硬”體現(xiàn)在非0 即1。模糊聚類相對于硬聚類而言，其特點體現(xiàn)在“模糊”，通過引入模糊隸屬度的概念[9-11]，對某個對象屬于某一類的不同程度進行刻畫，這使得聚類的結(jié)果更加貼近現(xiàn)實意義。其中，最為廣泛應(yīng)用的是模糊C 均值(fuzzy C-means, FCM)算法[11-14]。FCM 算法把聚類過程轉(zhuǎn)化為帶約束條件的目標函數(shù)優(yōu)化問題，再通過數(shù)學(xué)方法求解，最終可以確定聚類結(jié)果。

在聚類的研究過程中有兩個十分復(fù)雜的問題，一是如何劃分數(shù)據(jù)集才能得到最好的聚類結(jié)果，二是如何確定該數(shù)據(jù)集劃分的類別數(shù)。前者通過聚類算法解決，后者可以通過聚類有效性問題[15-19]來解決。如何確定最佳聚類數(shù)是聚類領(lǐng)域的公認難題。雖然聚類的類別數(shù)可能由用戶的經(jīng)驗或者專家根據(jù)領(lǐng)域的知識進行估計得到，但通常我們難以提前得知真實的聚類數(shù)。

真實世界中的數(shù)據(jù)往往復(fù)雜且多樣，這就要求聚類算法能夠準確地根據(jù)數(shù)據(jù)其內(nèi)部的特征和結(jié)構(gòu)進行聚類。聚類有效性研究就是通過使用聚類有效性指標對聚類結(jié)果進行評估，從而分析出聚類的效果。具體而言，在不同聚類數(shù)的情況下，運行聚類算法，若得到的結(jié)果使得聚類有效性指標函數(shù)下取得最優(yōu)值，則該情況即為最佳聚類數(shù)，該劃分即為最佳劃分。這種研究方法是簡潔而有效的。

當(dāng)前的聚類有效性指標主要涉及3 類[13-15]，即外部有效性、內(nèi)部有效性和相對有效性指標。內(nèi)部有效性指標基于數(shù)據(jù)集的幾何結(jié)構(gòu)信息，從緊致性、分離性、連通性和重疊度等方面對聚類結(jié)果加以評價。外部有效性指標通過將聚類結(jié)果與外部準則相對比來評估聚類效果。相對有效性指標則根據(jù)預(yù)先設(shè)置的評價標準，對取不同參數(shù)的聚類算法進行評估，最終選出較優(yōu)的參數(shù)設(shè)置和聚類模式。此外，還有其他類型的評價指標，比如生物類型指標[20]、關(guān)聯(lián)性指標[21]、基于穩(wěn)定性的指標[22]等，都是為了針對某一特性而研究出來的。

學(xué)者們在內(nèi)部有效性指標的設(shè)計中投入了很多精力，現(xiàn)存的內(nèi)部有效性指標的設(shè)計主要分為以下幾類。第一類是基于幾何結(jié)構(gòu)信息，如Calinski提出的CH 指標[23]、Davies 提出的DB 指標[24]等。CH 指標用類內(nèi)離差矩陣來度量緊密度，用類間離差矩陣來度量分離度。DB 指標用類內(nèi)樣本點到其聚類中心的距離來度量類內(nèi)緊致性，用聚類中心之間的距離來度量類間分離性。第二類基于隸屬度，如Bezdek 提出的用于模糊聚類的有效性指標，分離系數(shù)PC[25]和分離熵PE[26]指標，以及Roubens 提出的標準分離系數(shù)NPC 和NPE[27]指標等。PC 和PE 指標考察的維度是隸屬度信息，并沒有考慮到樣本的結(jié)構(gòu)信息，且PC 指標還有一個缺點，就是單調(diào)變化。為了克服這個缺點，NPC 指標應(yīng)運而生，但其也沒有對樣本信息進行全面的考量。此外，還有一些指標基于數(shù)據(jù)集的結(jié)構(gòu)信息和隸屬度，比如Xie 提出的XBI[28]指標、Fukuyama 提出的FS[29]指標。XBI 指標是一種比值型的指標，但指標的性能不穩(wěn)定。FS 指標是一種求和型指標，這類指標和DB 指標原理相同。在XBI 指標的基礎(chǔ)上，通過在其中引入聚類中心之間的中值距離，Wu 等提出了WLI 指標[30]，在實際中也有不錯的表現(xiàn)。后來還有學(xué)者提出了I指標[31]，其由3 部分信息構(gòu)成，也取得了不俗的效果。

目前來看，現(xiàn)有的面向模糊C 均值算法的內(nèi)部有效性指標尚存在一些比較典型的問題：

1) 對于類內(nèi)緊致性的刻畫不太到位。現(xiàn)有的大多數(shù)指標都是用類內(nèi)距離表示簇內(nèi)的緊致性。類內(nèi)距離越小則認為類內(nèi)緊致性更好。考慮到模糊聚類的特點，其實這個是不夠充分的。大多指標對此都處理得較為簡單。這方面WLI 考慮得稍好，但也沒有考慮整個數(shù)據(jù)集的綜合特征。

2) 對于類間分離性的度量刻畫不夠準確。大多數(shù)有效性指標的處理機制過于簡單、粗糙，比如XBI 采用聚類中心之間的最小距離來刻畫類間分離性，F(xiàn)S 和VCVI 采用聚類中心和平均聚類中心的差值再求和來刻畫。而這種對類間分離性度量的刻畫方式并不準確，需要更為綜合性地考慮。

基于上述原因，本文提出一種新的聚類有效性指標，即考慮最大值和均值的指標（maximummean，MAME）。該指標從類內(nèi)緊致性和類間分離性兩個角度著手設(shè)計。首先，考慮了整個數(shù)據(jù)集的綜合特征，計算分別分為K類和1 類的情況的比值，提出了一個新的模糊緊致性度量表達式。其次，引入最大聚類中心距離和平均聚類中心距離，提出了一個新的分離性度量方法。最后，從模糊緊致性和分離性度量方法出發(fā)，提出了MAME 指標。通過大量的實驗，在多個數(shù)據(jù)集上均驗證了所提指標較以往的聚類有效性指標有明顯的性能改善，特別是面對復(fù)雜多樣的數(shù)據(jù)集時，也能表現(xiàn)良好。這進一步證明了新提出的聚類有效性指標，即MAME 指標的合理性和有效性。

1 相關(guān)工作

近年來，大量的研究致力于設(shè)計有效的模糊聚類有效性指標。它們的目的是通過對聚類結(jié)果進行有效性評估從而能夠更好地進行聚類。這里介紹3 種比較典型的指標。

XBI 指標[28]是目前應(yīng)用較為廣泛的指標之一。XBI 指標將類內(nèi)緊致性與類間分離性的比值作為其結(jié)果，計算方式簡單，且準確率較高。其使用數(shù)據(jù)簇內(nèi)的數(shù)據(jù)點到其聚類中心的距離之和來度量類內(nèi)緊致性，類間分離性由N倍的最小數(shù)據(jù)簇之間的距離來表示。具體公式為

式中：K是數(shù)據(jù)集的類別數(shù)；N是數(shù)據(jù)集中數(shù)據(jù)樣本的個數(shù)；m表 示模糊加權(quán)系數(shù)；xj表示數(shù)據(jù)集中第j個樣本點；vi和vj分 別表示數(shù)據(jù)集的第i個和第j個聚類中心； ∧表示對數(shù)據(jù)集取最小值；vk表示數(shù)據(jù)集的第k個聚類中心；uik表示第i個樣本點屬于第k個聚類中心的隸屬度。XBI 指標不僅考慮了數(shù)據(jù)集內(nèi)部的幾何結(jié)構(gòu)信息，還考慮了模糊隸屬度信息，能較為全面的評價一個聚類算法的優(yōu)劣。但XBI 指標有個缺點，當(dāng)劃分的類的數(shù)量不斷增加時，XBI 指標函數(shù)的值會不斷減小，當(dāng)K無限接近于N時，其值會無限趨向于0，在這種情況下下，該指標就不能有效評價。

WLI指標[30]的具體定義為

其中， ?表示數(shù)據(jù)集取平均值，其他符號（比如K、N等）的定義和前面一樣。并且，

表示兩聚類中心間的距離的中值，而

表示最小的聚類中心間的距離值。為了面對簇中心分布密集的數(shù)據(jù)集時也有不錯的表現(xiàn)，WLI 指標引入了中值距離，但其對于含有噪聲的數(shù)據(jù)集表現(xiàn)依然不佳。

I指標[31]的具體定義為

其中，K是數(shù)據(jù)集的類別數(shù)，且

p是小于1 的任意實數(shù)。該指標由3 部分構(gòu)成，彼此之間相互競爭和制衡，但其十分依賴于初始值的設(shè)定，導(dǎo)致結(jié)果具有很大的不確定性。

根據(jù)以上對于指標的簡要介紹，這里分析其存在的問題。XBI 指標對聚類劃分的質(zhì)量進行了詳細評價，但是當(dāng)聚類數(shù)K非常大并趨向數(shù)據(jù)樣本總數(shù)N時，效果不理想。WLI 指標加入了中值距離，可以防止聚類中心分布較近時指標值大的情況，但是對于噪聲點適應(yīng)性不佳。I指標中隸屬度、聚類中心、兩個集群之間最大分離度三者相互競爭，但是對于密集型簇的效果不明顯，且依賴于初始值的設(shè)定。

表1 是各類指標的優(yōu)缺點匯總。總體而言，對于引言部分提及的2 個問題（即對于類內(nèi)緊致性的刻畫不太到位、對于類間分離性的度量刻畫不夠準確），這些指標都難以有效地解決。

2 新的聚類有效性指標

以往的模糊聚類有效性指標或多或少地會存在一些問題，并不能有效地對聚類結(jié)果進行評估，從而難以有效地指導(dǎo)聚類。例如，CH 指標和DB指標，主要的評判依據(jù)是數(shù)據(jù)集的結(jié)構(gòu)信息，并沒有考慮模糊隸屬度，雖然也可以應(yīng)用于模糊聚類算法中，但其準確性以及使用范圍都大打折扣。這兩個指標在一般數(shù)據(jù)集中表現(xiàn)良好，但是當(dāng)遇到較復(fù)雜的數(shù)據(jù)集，比如噪聲點較多或者是數(shù)據(jù)簇相互之間重疊度較大的時候，得不到較好的結(jié)果。

又例如PE 指標，其僅僅考慮了模糊聚類的隸屬度信息，該指標會隨著聚類數(shù)的變化而單調(diào)變化，雖指標形式簡單，易于計算，但是數(shù)據(jù)集只要稍微復(fù)雜一點，就不能達到理想的效果。作為改進，NPC 與NPE 指標在一定程度上緩解了PC 與PE 指標的單調(diào)性問題，但是最終的聚類評價效果還是不理想。FS、XBI、WLI 等3 種指標都是基于數(shù)據(jù)集的內(nèi)部幾何結(jié)構(gòu)信息與隸屬度信息，相對于其他指標而言，更為全面和綜合，但他們計算量較大，運算較為復(fù)雜。I指標中的3 個因子之間能夠相互協(xié)調(diào)和制衡，但是它過度地依賴于初始值地設(shè)定，導(dǎo)致結(jié)果具有很大的不確定性。

所以這里，我們提出了一個新的聚類有效性評價指標，即MAME 指標。該指標基于類內(nèi)緊致性和類間分離性兩個方面，又綜合考慮了以往指標存在的問題，盡可能地簡化指標的運算復(fù)雜度，使得指標即使處理復(fù)雜數(shù)據(jù)集時也能得到較滿意的效果，能夠更加清晰、準確地評價聚類結(jié)果。

2.1 緊致性度量分析

緊致性用來衡量類中每個數(shù)據(jù)樣本之間的緊密程度，一個好的劃分就要求類內(nèi)的數(shù)據(jù)點盡可能地緊密，而類間的數(shù)據(jù)點盡可能分離。

在參考了WLI、I、XBI 指標中關(guān)于緊致性的度量之后，此處給出新的模糊緊致性度量表達式為

其中，

離開圣保羅后的第二個秋季，明尼十歲了，龜甲已長達十一英寸。泥濘的河岸上有一處麝鼠的洞穴，明尼把自己十磅（英美制質(zhì)量或重量單位，一磅約合0.45千克）重的身子擠了進去。越來越多的鱷龜發(fā)現(xiàn)了這處擁擠的寓所，每一只鱷龜都抓撓洞壁，使洞穴不斷擴大。等最后一只鱷龜進來后，明尼已被一層層地壓在了擠在泥巴里的另外十五只鱷龜?shù)南旅妗＿@樣一支大軍在洞口留下的痕跡泄了密，兩個發(fā)現(xiàn)它們蹤跡的捕龜人挖開了洞穴。

稱為類內(nèi)平方誤差和。這里實際上考慮了分別分為K類和1 類的情況的比值（即EK和E1的比值）。

一般情況下，類內(nèi)誤差平方和通常會隨著K的增加而減小。即當(dāng)類別劃分數(shù)增加時，每類對應(yīng)的類內(nèi)平方誤差和就越小。模糊緊致性衡量的是一個數(shù)據(jù)簇內(nèi)部的數(shù)據(jù)樣本之間的緊湊程度。數(shù)據(jù)簇內(nèi)部的數(shù)據(jù)樣本之間越緊湊，就說明該劃分聚類效果好，所以，一般來講，jzx的值越小越好。

2.2 分離性度量分析

分離性用來衡量每個劃分之間的分離程度，兩個聚類之間的分離性越大說明劃分效果越好。因此，為了提高聚類有效性指標的性能，就需要重新設(shè)計一種新的分離性度量表達式，以便更精準地度量類之間的分離性。

我們提出得到新的分離性度量方法為

式中：N是數(shù)據(jù)集中數(shù)據(jù)樣本的個數(shù)，vi表示第i個聚類中心，同理vj表 示第j個聚類中心； ∨表示對數(shù)據(jù)集取最大值， ?表示對數(shù)據(jù)集取均值。其中，K是為了防止聚類中心之間的最小距離和平均距離太小而導(dǎo)致的指標值過大的情況。

新的分離性度量表達式不僅考慮了數(shù)據(jù)簇中心之間的最大距離，還引入了數(shù)據(jù)簇中心之間的平均距離，使得新提出的聚類有效性指標的性能更加的準確和穩(wěn)定。

2.3 MAME 函數(shù)表達式

根據(jù)前兩節(jié)提出的新的模糊緊致性度量表達式和分離性度量方法，本節(jié)提出一種新的聚類有效性指標，即 MAME 指標。新的聚類有效性指標從分離性和緊致性兩個角度上評估聚類結(jié)果的有效性，具體公式如下：

或者，可以重寫為

式中：p是一個不小于1 的任意實值，這里p取2。緊致性衡量的是數(shù)據(jù)簇內(nèi)部的的緊致程度，即一個簇中所有數(shù)據(jù)樣本的分布是否比較緊密，越緊密則說明該劃分效果較好；分離性衡量的是數(shù)據(jù)集中不同簇之間的分布情況，兩個簇之間相隔的越遠，則越能說明聚類的結(jié)果較優(yōu)。本文中提出的新的聚類有效性指標表現(xiàn)為簇間分離性和簇內(nèi)緊致性的比值，由此分析，當(dāng)聚類數(shù)目確定時，MAME 指標的值越大，則說明聚類的效果越好。

2.4 MAME 計算算法

如下給出MAME 的計算算法。其過程基本為：首先進行FCM 算法的迭代，然后進行MAME公式的計算，并且發(fā)現(xiàn)最大值對應(yīng)的聚類數(shù)，即為本算法對應(yīng)的最優(yōu)聚類數(shù)。

算法1有效性指標MAME 的計算算法

輸入最大迭代次數(shù)M，迭代停止的誤差ε，隸屬度矩陣U=[uij], 最小聚類數(shù)Kmin和最大聚類數(shù)Kmax。

輸出每種聚類數(shù)所對應(yīng)的MAME 指標值。

1）設(shè)定M、 ε 、最大聚類數(shù)Kmax。初始化隸屬度矩陣（注意需要滿足，令初始迭代次數(shù)k=0，Kmin=2，K=Kmin，m=2。

2）更新隸屬度矩陣U：

3）更新聚類中心V：

4）令k=k+1。

6）用式（7）計算緊致性。

7）用式(10)計算分離性。

8）利用式(11)得到MAME 的值。

9）K=K+1。

10）如果K≤Kmax，返回2）。否則，繼續(xù)。

11）找出MAME(K)的最大值，該值對應(yīng)的K即為最優(yōu)劃分數(shù)。

12）結(jié)束。

3 仿真實驗與分析

為了證明新提出的聚類有效性指標MAME指標的合理性和有效性，采用模糊C 均值算法FCM 來進行實現(xiàn)驗證。首先在不同的K值下運行FCM 算法，然后使用指標逐個檢驗聚類結(jié)果，最終選取最優(yōu)指標值所對應(yīng)的K值即為聚類的最優(yōu)劃分數(shù)。在此實驗中，使用的環(huán)境為Intel(R)Core(TM)i5-4200 U CPU @ 1.60 GHz 以及RAM 4.00 GB 和Windows 7 旗艦版，編程軟件采用VC++6.0。

3.1 數(shù)據(jù)集與對比指標

本次實驗挑選了11 個數(shù)據(jù)集，即Flame、Banknote、Habe、Jain、WDBC 和AD1、AD2、AD3、AD4、Data-E6、Data-Fc1。前5 個數(shù)據(jù)集為UCI 數(shù)據(jù)集[32]，來自真實世界的真實數(shù)據(jù)；后6 個數(shù)據(jù)集是人工數(shù)據(jù)集（來自于文獻[30]），分布較復(fù)雜且含有很多噪聲點，可以從不同角度對指標評估。UCI 數(shù)據(jù)集中，F(xiàn)lame 有240 個數(shù)據(jù)樣本，每個數(shù)據(jù)樣本具有2 個屬性，共有2 類；Banknote 是從紙幣鑒別過程中提取出來的數(shù)據(jù)集，數(shù)據(jù)量為1 372，共4 個屬性，分為2 類；Habe 的數(shù)據(jù)量為306，有2 個屬性，分為2 類；Jain 的數(shù)據(jù)量為373，共2 個屬性，分為2 類；WDBC 描述的是乳腺癌診斷的信息，數(shù)據(jù)量為569，共有30 個屬性，分為2 類。在人工數(shù)據(jù)集中，下述4 個數(shù)據(jù)集的數(shù)據(jù)點均有2 個屬性，其中，AD1 的數(shù)據(jù)量為800，分為4 類；AD2 的數(shù)據(jù)量為300，分為3 類；AD3 的數(shù)據(jù)量為300，分為3 類；AD4 的數(shù)據(jù)量為450，分為3 類；而Data-E6 含有8 537 個數(shù)據(jù)樣本，具有2 個屬性，分為4 類；Data-Fc1 含有1 053 個數(shù)據(jù)樣本，具有2 個屬性，分為5 類。

在這些數(shù)據(jù)集上對新提出的指標進行實驗并與多種有效性指標進行比較。采用了9 個具有代表性的指標，分別是CH(+)指標、DB(-)指標、PE(-)指標、NPC(+)指標、NPE(-)指標、FS(-)指標、XBI(-)指標、I指標(+)、WLI(-)指標。這里(+)表示該指標的值越大越好，即最優(yōu)值對應(yīng)最大的值。同時(-)表示指標的值越小越好，即最優(yōu)值對應(yīng)最小的值。

3.2 面向UCI 數(shù)據(jù)集的實驗

由于FCM 聚類算法的初始聚類中心是隨機初始化的，因此可能每次得到的聚類結(jié)果都不一樣，進而導(dǎo)致對于聚類數(shù)K，聚類有效性指標函數(shù)的最優(yōu)值可能也不一樣。所以為了保證實驗結(jié)果的穩(wěn)定性，將每個實驗在不同的K值下重復(fù)運行10 次。每一輪的每一個聚類有效性指標都會記錄一個最大或者最小值，該最大或是最小值所對應(yīng)的K值即為最優(yōu)劃分數(shù)。每一輪結(jié)束后，都會統(tǒng)計出一個最優(yōu)值，10 次實驗結(jié)束后，同一個評價指標會得到10 個極值所對應(yīng)的K值，用K*表示其統(tǒng)計結(jié)果。若同一個指標的10 輪結(jié)果中極值所對應(yīng)的K 值都相同，則說明此指標的穩(wěn)定性較強，正確率較高。

在UCI 數(shù)據(jù)集上實驗的結(jié)果如表2 所示，其中，XY表示K=X的值出現(xiàn)了Y次。

表2 UCI 數(shù)據(jù)集上實驗的結(jié)果Table 2 Results of experiments on UCI datasets

以Flame 為例，其數(shù)據(jù)量為240，具有4 個屬性，共分為2 類。由表2 中數(shù)據(jù)可知，運行了10 次后，PE 指標的結(jié)果中僅出現(xiàn)了一次K為4 是最優(yōu)值的情況，其余的9 次得到的最優(yōu)值均為2；NPE 指標的結(jié)果中，最優(yōu)值均是2；NPC 指標的結(jié)果中，只有一次劃分為2 類，其余均劃分為4 類；FSI 指標的結(jié)果中，有3 次的劃分結(jié)果為2，7 次的劃分結(jié)果為8；XBI 指標的結(jié)果中，最優(yōu)值都是4；CHI 指標的結(jié)果中，最優(yōu)值都是4 類；DB 指標的結(jié)果中，均劃分為4 類；WLI 指標的結(jié)果中，有2 次得到的最優(yōu)值是4，8 次劃分為5 類；I指標的結(jié)果中，9 次劃分為2 類，一次劃分為5 類；在MAME 指標的結(jié)果中，最優(yōu)值均為2。最終選取出現(xiàn)次數(shù)最多的最優(yōu)值所對應(yīng)的K值作為評價指標最終的結(jié)果，見表3。其中，結(jié)果右上角帶“*”的表示本次結(jié)果不是最優(yōu)劃分。Best 列表示數(shù)據(jù)集的真實聚類數(shù)。

表3 UCI 數(shù)據(jù)集上指標得到的最優(yōu)值Table 3 Optimal value of the index on UCI datasets

由表3 中數(shù)據(jù)可知，PE 指標、NPE 指標和MAME指標在數(shù)據(jù)集Flame、Banknote、Habe、Jain 和WDBC 上均得到了正確的聚類結(jié)果；而NPC 指標只在數(shù)據(jù)集Banknote、Habe 和WDBC 上得到了正確的結(jié)果；FSI 指標和XBI 指標在數(shù)據(jù)集Flame、Banknote、Habe、Jain 和WDBC 上劃分錯誤；CH指標僅在數(shù)據(jù)集Banknote 上實現(xiàn)了正確劃分，在其余數(shù)據(jù)集上均判斷錯誤；DBI 指標僅在數(shù)據(jù)集WDBC 上實現(xiàn)了正確劃分，而在其余數(shù)據(jù)集上均判斷錯誤；WLI 指標則在數(shù)據(jù)集Banknote、Habe和WDBC 上實現(xiàn)了正確劃分，而在其余2 個數(shù)據(jù)集上判斷錯誤；I指標僅在數(shù)據(jù)集Flame 上得到了正確劃分，而在其余數(shù)據(jù)集上均判斷錯誤。由此可見，新提出的MAME 指標的正確率為100%，而其他的指標在面對稍微復(fù)雜的數(shù)據(jù)集時，就會出現(xiàn)準確率不高、且不穩(wěn)定的缺點。

每個指標的K從2～10 得到的結(jié)果在Flame數(shù)據(jù)集上的變化情況見圖1。圖1 中，橫坐標表示的是聚類數(shù)K值，縱坐標表示對應(yīng)的評價指標。星標記的是每個指標函數(shù)值的極值所對應(yīng)的最優(yōu)分類數(shù)。由圖可知，只有NPE、PE、I和MAME指標在K為2 時的極值是正確的，其他的指標均有偏差。可以看出，各指標的最優(yōu)值出現(xiàn)的K值不同，且每個指標算法收斂時所取的最優(yōu)值的收斂方向不同，評價函數(shù)在取不同的K值時，都會對應(yīng)一個值。各個指標選取結(jié)果中的最大或最小值來作為這個聚類評價函數(shù)的最優(yōu)值的情況各不相同。例如，CH 指標、NPC 指標、I指標均是取評價函數(shù)結(jié)果中最大值作為最優(yōu)值；其余指標均是取評價函數(shù)結(jié)果中最小值為最優(yōu)值。而新提出的MAME 指標則是取評價函數(shù)結(jié)果中最大值為最優(yōu)值。

圖1 各指標在Flame 數(shù)據(jù)集上的結(jié)果對比Fig.1 Comparison of results for each metric on the Flame dataset

圖1 和表2～3 中的數(shù)據(jù)均清晰地顯示了新提出的聚類有效性指標對于UCI 真實數(shù)據(jù)集表現(xiàn)出了較高的準確率和穩(wěn)定性。

3.3 面向人工數(shù)據(jù)集的實驗

圖2 給出了4 個人工數(shù)據(jù)集AD1～AD4[28]的分布情況，圖3 給出了2 個人工數(shù)據(jù)集E6 和Fc1 的分布情況，人工數(shù)據(jù)集AD1～AD4 以及E6、Fc1 上的實驗結(jié)果如表4 所示，XY表示K=X的值出現(xiàn)了Y次。

圖2 4 個人工數(shù)據(jù)集Fig.2 Four artificial datasets

圖3 人造數(shù)據(jù)集E6 和Fc1 的分布Fig.3 The distribution of artificial datasets E6 and Fc1

表4 人工數(shù)據(jù)集上實驗的結(jié)果Table 4 Results of experiments on artificial datasets

表4 是人工數(shù)據(jù)集AD1～AD4、E6 和Fc1 的運行結(jié)果。Best 列表示數(shù)據(jù)集的真實聚類數(shù)。以AD1 數(shù)據(jù)集為例，AD1 的數(shù)據(jù)量為800，具有2 個屬性，共分為4 類。由表4 中數(shù)據(jù)可知，運行了10 次實驗后，PE 指標的結(jié)果中，得到的最優(yōu)值均為2 類；NPE 指標的結(jié)果中，最優(yōu)值都是2；NPC指標的結(jié)果中，有9 次得到了正確劃分，剩余1 次的最優(yōu)值為2；FS 指標的結(jié)果中，有7 次實現(xiàn)了正確劃分，而3 次得到了最優(yōu)值是2 類；XBI 指標的結(jié)果中，最優(yōu)值都是4 類；CHI 指標的結(jié)果中，最優(yōu)值都是4；DBI 指標的結(jié)果中，最優(yōu)值均為4 類；WLI 指標的結(jié)果中，最優(yōu)值均為4 類；I指標的結(jié)果中，有9 次的最優(yōu)值是4，1 次最優(yōu)值是3 類；而MAME 指標的10 次結(jié)果中，得到的最優(yōu)值都是4 類。最終選取出現(xiàn)次數(shù)最多的最優(yōu)值所對應(yīng)的K值作為評價指標最終的結(jié)果，結(jié)果見表5。其中，結(jié)果右上角帶“*”的表示本次結(jié)果不是最優(yōu)劃分。

表5 人工數(shù)據(jù)集上指標得到的最優(yōu)值Table 5 Optimal values of the indexes on artificial datasets

由表5 中可知，XBI 指標、WLI 指標和MAME指標在數(shù)據(jù)集AD1、AD2、AD3、AD4、E6 和Fc1 上全都實現(xiàn)了正確劃分；DBI 指標在數(shù)據(jù)集AD1、AD2、AD3、AD4 和E6 上實現(xiàn)了正確劃分，僅在Fc1 上沒有實現(xiàn)正確劃分；I指標在數(shù)據(jù)集AD1、AD2、AD3、E6 和Fc1 上實現(xiàn)了正確劃分，僅在AD4 上沒有實現(xiàn)正確劃分；NPC 指標在數(shù)據(jù)集AD1、AD2、AD4 和E6 上實現(xiàn)了正確劃分，而在其余數(shù)據(jù)集上劃分錯誤；PE 指標和NPE 指標在數(shù)據(jù)集AD2、AD4 和E6 上實現(xiàn)了正確劃分，其余數(shù)據(jù)集上判斷錯誤；CHI 指標僅在數(shù)據(jù)集AD1、AD2 和E6 上劃分正確，其余數(shù)據(jù)集上均劃分錯誤；FS 指標僅在數(shù)據(jù)集AD1 和Fc1 上實現(xiàn)了正確劃分，而在其余數(shù)據(jù)集上均判斷錯誤。觀察以上結(jié)果可知，有些指標在面對稍微復(fù)雜的數(shù)據(jù)集時，就會出現(xiàn)準確率不高且不穩(wěn)定的缺點，效果有點差強人意。

每個指標的K從2～10 得到的結(jié)果在AD1數(shù)據(jù)集上的變化情況見圖4。圖4 中，橫坐標表示的是聚類數(shù)K值，縱坐標表示對應(yīng)的評價指標。星標記的是每個指標函數(shù)值的極值所對應(yīng)的最優(yōu)分類數(shù)。除PE、NPE 指標在K為4 時得到的極值是錯誤的外，其他的指標都得到了正確的分類結(jié)果。可以看出，新提出的聚類有效性指標，即MAME 指標在6 個人工數(shù)據(jù)集中都取得了正確的分類結(jié)果。

圖4 各指標在AD1 數(shù)據(jù)集上的結(jié)果對比Fig.4 Comparison of the results of each index on AD1 dataset

觀察表4 和表5 中結(jié)果可知，新提出的MAME聚類有效性指標對于人工數(shù)據(jù)集確實有較高的有準確率和穩(wěn)定性。

此外，我們還將MAME 指標分別與其他指標的實驗結(jié)果進行了克魯斯卡爾-沃利斯檢驗（Kruskal-Wallis test）。該指標用于檢驗MAME 與其他聚類有效性指標是否有顯著性差異，若克魯斯卡爾-沃利斯檢驗的最終值小于0.05，則說明兩指標間存在顯著性差異。表6 列出了MAME 指標與其他指標之間克魯斯卡爾-沃利斯檢驗的最終結(jié)果。例如，MAME 與FSI 指標間的結(jié)果值為1.653 1×10-4，說明兩指標間的差異是顯著的。總體而言，MAME 指標與其他指標之間存在著差異。

表6 MAME 和其他指標之間的Kruskal-Wallis 檢驗結(jié)果Table 6 Final values of Kruskal-Wallis tests between MAME and every other CVI.

4 結(jié)束語

近些年來，隨著聚類技術(shù)的不斷發(fā)展，各種聚類算法層出不窮，如何評價聚類結(jié)果的有效性變成了一個重要的問題。聚類有效性問題就是用來評估聚類結(jié)果以及幫助判別聚類的類別數(shù)的。但現(xiàn)有的聚類有效性指標對于類內(nèi)緊致性的刻畫不太到位、對于類間分離性的度量刻畫不夠準確。

為了解決以上的問題，使聚類有效性問題能更加有效地指導(dǎo)聚類過程，本文提出了一個新的模糊聚類有效性指標，即MAME 指標。針對現(xiàn)有指標對類內(nèi)緊致性刻畫不到位的問題，在考慮了整個數(shù)據(jù)集的綜合特征的基礎(chǔ)上，計算分別分為K類和1 類的情況的比值，提出了一個新的模糊緊致性度量表達式。對于類間分離性度量不準確問題，引入最大聚類中心距離和平均聚類中心距離，提出了一個新的分離性度量方法。最后，基于類內(nèi)緊致性和類間分離性表達式提出了MAME指標。

為了證明新指標的可行性與準確性，在多個真實數(shù)據(jù)集和人工數(shù)據(jù)集上進行了實驗。其結(jié)果均驗證了所提指標較以往的聚類有效性指標有明顯的性能改善，且對不同類型數(shù)據(jù)集的適應(yīng)能力較強，表明新的聚類有效性指標可以更準確地指導(dǎo)聚類過程從而得到最優(yōu)結(jié)果。即使面對復(fù)雜多樣和噪聲點較多的數(shù)據(jù)集時也能得到較滿意的效果，能夠更加清晰、準確地評價聚類結(jié)果，并且適應(yīng)的范圍也比較廣泛，準確性較高。這進一步證明了新提出的聚類有效性指標，即MAME 指標的合理性和有效性。

本文的創(chuàng)新性體現(xiàn)在以下3 個方面：1）考慮了分別分為K類和1 類的情況的比值，提出了一個新的模糊緊致性度量表達式。2）引入最大聚類中心距離和平均聚類中心距離，提出了一個新的分離性度量方法。3）從模糊緊致性度量表達式、分離性度量方法出發(fā)，提出了一個面向模糊聚類的新的聚類有效性指標MAME。

未來，將基于本文提出的MAME 指標去設(shè)計一種新的模糊聚類算法，進一步提升其在發(fā)現(xiàn)最優(yōu)聚類數(shù)方面的能力。進一步將研究適用于多種聚類算法[33-34]的聚類有效性指標。