面向模糊C 均值算法的MAME 聚類有效性指標(biāo)

唐益明，陳仁好，李冰

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

WLI指標(biāo)[30]的具體定義為

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

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

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

I指標(biāo)[31]的具體定義為

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

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

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

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

2 新的聚類有效性指標(biāo)

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

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

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

2.1 緊致性度量分析

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

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

其中，

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

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

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

2.2 分離性度量分析

分離性用來(lái)衡量每個(gè)劃分之間的分離程度，兩個(gè)聚類之間的分離性越大說(shuō)明劃分效果越好。因此，為了提高聚類有效性指標(biāo)的性能，就需要重新設(shè)計(jì)一種新的分離性度量表達(dá)式，以便更精準(zhǔn)地度量類之間的分離性。

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

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

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

2.3 MAME 函數(shù)表達(dá)式

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

或者，可以重寫為

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

2.4 MAME 計(jì)算算法

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

算法1有效性指標(biāo)MAME 的計(jì)算算法

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

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

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

2）更新隸屬度矩陣U：

3）更新聚類中心V：

4）令k=k+1。

6）用式（7）計(jì)算緊致性。

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

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

9）K=K+1。

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

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

12）結(jié)束。

3 仿真實(shí)驗(yàn)與分析

為了證明新提出的聚類有效性指標(biāo)MAME指標(biāo)的合理性和有效性，采用模糊C 均值算法FCM 來(lái)進(jìn)行實(shí)現(xiàn)驗(yàn)證。首先在不同的K值下運(yùn)行FCM 算法，然后使用指標(biāo)逐個(gè)檢驗(yàn)聚類結(jié)果，最終選取最優(yōu)指標(biāo)值所對(duì)應(yīng)的K值即為聚類的最優(yōu)劃分?jǐn)?shù)。在此實(shí)驗(yàn)中，使用的環(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ù)集與對(duì)比指標(biāo)

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

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

3.2 面向UCI 數(shù)據(jù)集的實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

圖2 4 個(gè)人工數(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ù)集上實(shí)驗(yàn)的結(jié)果Table 4 Results of experiments on artificial datasets

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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