基于矩陣特征值分析的模糊聚類有效性指標(biāo)

岳士弘，黃 媞，王鵬龍

(天津大學(xué)電氣與自動(dòng)化工程學(xué)院，天津 300072)

基于矩陣特征值分析的模糊聚類有效性指標(biāo)

岳士弘，黃 媞，王鵬龍

(天津大學(xué)電氣與自動(dòng)化工程學(xué)院，天津 300072)

許多有效性指標(biāo)已經(jīng)被提出量化地估計(jì)和評(píng)價(jià)模糊聚類算法對(duì)于給定數(shù)據(jù)集的劃分結(jié)果．但是由于不合理的結(jié)構(gòu)和極大的時(shí)間耗費(fèi)，迄今這些有效性指標(biāo)幾乎都無(wú)法滿足應(yīng)用的一般性需求．為此，提出一個(gè)基于Gerschgorin 圓盤(pán)定律估計(jì)的聚類有效性指標(biāo)來(lái)估計(jì)模糊聚類的類數(shù)．先由模糊聚類劃分的結(jié)果得到一個(gè)相關(guān)性矩陣，接著求出該矩陣的所有特征值和特征向量，然后基于經(jīng)典 Gerschgorin 圓盤(pán)定律估計(jì)最優(yōu)的類數(shù)．為了檢驗(yàn)提出的指標(biāo)在模糊聚類中的有效性，把模糊聚類算法應(yīng)用到帶有不同特征的3個(gè)人工數(shù)據(jù)集和3個(gè)真實(shí)的數(shù)據(jù)集，并比較提出的指標(biāo)和 2個(gè)最常用的模糊聚類有效性指標(biāo)．實(shí)驗(yàn)結(jié)果證明了所提出的有效性指標(biāo)能夠發(fā)現(xiàn)被聚類數(shù)據(jù)集的固有結(jié)構(gòu)，從而得出更加準(zhǔn)確的類數(shù)．

有效性指標(biāo)；Gerschgorin圓盤(pán)；模糊聚類；特征值

聚類分析是一類無(wú)監(jiān)督式的學(xué)習(xí)技術(shù)，目的是把一個(gè)模式集中，具有類似特征的模式劃分到相同類而把不同特征的模式劃分到不同類[1]．聚類分析的一個(gè)關(guān)鍵任務(wù)是量化地評(píng)價(jià)聚類結(jié)果，尤其是確定一個(gè)最優(yōu)的類數(shù)或劃分結(jié)構(gòu)．通常，這種評(píng)價(jià)由一個(gè)或一組聚類有效性指標(biāo)來(lái)完成[2-3]．

大多數(shù)聚類有效性指標(biāo)都是基于 2個(gè)最常用的聚類算法設(shè)計(jì)：硬聚類的 HCM(hard c-means)算法[4]和模糊聚類的FCM(fuzzy c-means)算法[5]．因此有效性指標(biāo)可以進(jìn)一步劃分為2大類：硬聚類指標(biāo)是用來(lái)評(píng)價(jià)和估計(jì)硬聚類算法的聚類結(jié)果；模糊聚類指標(biāo)是使用模糊隸屬度確定模式對(duì)于類的歸屬性．本文聚焦在模糊聚類有效性指標(biāo)的研究．

迄今為止，研究者已經(jīng)提出大量聚類有效性指標(biāo)．2個(gè)最常用的模糊聚類指標(biāo)是 Bezdek[5]提出的信息熵指標(biāo)以及 Xie等[6]提出的分離性指標(biāo)．其次，研究者已經(jīng)提出充分考慮數(shù)據(jù)集結(jié)構(gòu)的聚類有效性指標(biāo)，如 Kim 等[7-8]在分析已有有效性指標(biāo)與數(shù)據(jù)集的關(guān)系后提出一系列新的有效性指標(biāo)．Maulik等[9-11]在提出一個(gè)既適合硬聚類又適合模糊聚類的指標(biāo)后，又研究了該指標(biāo)相對(duì)于不同數(shù)據(jù)結(jié)構(gòu)的變化形式．最近，Yue等[12]提出一個(gè)基于網(wǎng)格距離度量不同類之間分離性的有效性指標(biāo)等，該指標(biāo)可以度量包含任意形狀類的數(shù)據(jù)集的結(jié)構(gòu)．但這些指標(biāo)都是通過(guò)一種迭代的 trial-and-error過(guò)程[13]來(lái)確定數(shù)據(jù)集最佳聚類數(shù)，即這些指標(biāo)都必須使聚類算法遍歷所有可能的類數(shù)實(shí)施聚類，從而確定哪一個(gè)聚類結(jié)果是最優(yōu)的．由于聚類算法必須被反復(fù)履行，因此是極其耗費(fèi)時(shí)間的，這直接導(dǎo)致已有的有效性指標(biāo)無(wú)法應(yīng)用在大多數(shù)工程中．陳黎飛等[14]最近提出一個(gè)基于層次劃分的方法試圖解決這個(gè)問(wèn)題，但這種方法并沒(méi)有根本改變上述問(wèn)題，同時(shí)又產(chǎn)生層次聚類算法參數(shù)過(guò)度敏感的固有問(wèn)題．

本文提出一個(gè)基于Gerschgorin圓盤(pán)定理[15]的有效性指標(biāo)估計(jì)最優(yōu)的類數(shù)．首先，使用一個(gè)充分大的類數(shù)代入 FCM算法對(duì)數(shù)據(jù)集進(jìn)行模糊聚類，接著按照模糊聚類結(jié)果構(gòu)造一個(gè)所有類之間的相關(guān)矩陣；在確定這個(gè)相關(guān)矩陣的 Gerschgorin圓盤(pán)后，把所有的Gerschgorin圓盤(pán)劃分到具有較大特征值和較小特征值的 2個(gè)不同集合；最后，基于 Gerschgorin圓盤(pán)定理提出一個(gè)新的有效性指標(biāo)．該指標(biāo)最少只需要一次聚類就可以得到最優(yōu)的類數(shù)，從根本上改變和克服了已有聚類有效性指標(biāo)遍歷式搜索所有可能類數(shù)所帶來(lái)的低效率，而得到最優(yōu)類數(shù)的正確率并不比已有的有效性指標(biāo)低．為了證明新提出有效性指標(biāo)的價(jià)值，本文在一組具有不同特征的數(shù)據(jù)集中，選擇了3個(gè)具有代表性的模糊有效性指標(biāo)進(jìn)行比較分析：Bezdek[5]提出的信息熵指標(biāo)，Xie等[6]提出的分離性指標(biāo)，Pakhira等[10]提出的可以同時(shí)評(píng)估硬聚類和模糊聚類結(jié)果的有效性指標(biāo)．實(shí)驗(yàn)結(jié)果證明了本文提出指標(biāo)的正確性和高效率．

1 相關(guān)工作

首先說(shuō)明一個(gè)應(yīng)用最廣泛的模糊聚類算法——模糊c-均值(fuzzy c-means，F(xiàn)CM)算法，以及3個(gè)有代表性的模糊聚類有效性指標(biāo)——Bezdek[5]提出的信息熵指標(biāo)，Xie等[6]提出的分離性指標(biāo)，Pakhira等[9]提出的有效性指標(biāo)，說(shuō)明這些指標(biāo)的可應(yīng)用范圍．

1.1 模糊聚類算法

許多聚類算法可以實(shí)施模糊聚類，但是這些算法都源自于Bezdek的FCM算法[5]．由于良好的可理解性和可操作性，F(xiàn)CM 算法仍然是當(dāng)前工程界應(yīng)用最普遍的聚類算法．

給定一個(gè)帶有 n個(gè)目標(biāo)和 c個(gè)類的模式集 X= {xi}，F(xiàn)CM算法的目標(biāo)函數(shù)為

如果m=1且uij的值只取0或者1，則FCM退化為HCM算法．但是 FCM算法的聚類結(jié)果嚴(yán)重依賴參數(shù)c(一個(gè)預(yù)設(shè)或者使用者輸入的類數(shù))．如果c預(yù)先未知導(dǎo)致輸入一個(gè)錯(cuò)誤的類數(shù)，則 FCM 的聚類結(jié)果是不可信甚至是無(wú)意義的．解決這個(gè)問(wèn)題的一個(gè)常用方法就是使用一個(gè)或幾個(gè)聚類有效性指標(biāo)[2-3]來(lái)確定一個(gè)最優(yōu)的類數(shù)．

1.2 3個(gè)有代表性的模糊聚類有效性指標(biāo)

1.2.1 Bezdek的信息熵指標(biāo)

Bezdek提出信息熵指標(biāo)表達(dá)式[5]為

式中a為一個(gè)對(duì)數(shù)函數(shù)的底數(shù)．這個(gè)指標(biāo)是一個(gè)基于信息熵的結(jié)構(gòu)設(shè)計(jì)、基于模糊隸屬度計(jì)算的關(guān)于類數(shù)的函數(shù)關(guān)系．讓類數(shù)從 1遞增到一個(gè)足夠大的整數(shù)，則最優(yōu)的類數(shù)通過(guò)求解VPE的最小值獲得．

1.2.2 Xie等提出的分離性指標(biāo)

Xie和Beni提出的基于分離性的有效性指標(biāo)[6]為

這個(gè)有效性指標(biāo)實(shí)際上是通過(guò)極大化類間距而極小化類內(nèi)距的形式構(gòu)造，最優(yōu)的類數(shù)通過(guò)極小化式(5)中的目標(biāo)函數(shù)來(lái)獲得．

1.2.3 Pakhira等提出的有效性指標(biāo)

Pakhira等[10]提出一個(gè)能同時(shí)評(píng)價(jià)硬聚類和模糊聚類結(jié)果的有效性指標(biāo)，即

式中：v為數(shù)據(jù)集中心；Jc為FCM或HCM算法中目標(biāo)函數(shù)的值；Dc為所有不同聚類原型之間的距離總和，則最優(yōu)的類數(shù)通過(guò)求解VPB的最小值獲得．

從上述說(shuō)明可以觀察到，已有的有效性指標(biāo)都是通過(guò)遍歷所有可能的類數(shù)進(jìn)行聚類，并最終確定哪個(gè)聚類結(jié)果或類數(shù)是最優(yōu)的．因此，必須不斷地對(duì)數(shù)據(jù)集實(shí)施聚類，而在工程實(shí)踐中這基本是不可行的．同時(shí)，如果類數(shù)的范圍選擇不合適，這類指標(biāo)可能根本達(dá)不到任何一個(gè)最優(yōu)值．例如，式(2)和式(3)所對(duì)應(yīng)的指標(biāo)，當(dāng)類數(shù)的取值范圍趨向于無(wú)窮大時(shí)，這2個(gè)指標(biāo)的變化趨勢(shì)趨向于單調(diào)下降[2,13]，這說(shuō)明它們的結(jié)構(gòu)也存在著一定的不合理性．

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

首先基于FCM算法的聚類結(jié)果計(jì)算任何2個(gè)類之間的相關(guān)系數(shù)，使用所有相關(guān)系數(shù)組成一個(gè)相關(guān)矩陣；在計(jì)算相關(guān)矩陣的所有特征值之后，使用Gerschgorin圓盤(pán)定理估計(jì)正確的類數(shù)．

2.1 相關(guān)系數(shù)和相關(guān)矩陣

給定d維數(shù)據(jù)集X′={X1，X2，…，XR，…，Xn}，Xk為一個(gè)數(shù)據(jù)點(diǎn)，Xk=(xk1，…，xkd) ∈Rd，k=1，2，…，n，n為數(shù)據(jù)點(diǎn)的總數(shù)．設(shè)L為FCM算法中設(shè)定的類數(shù)，在實(shí)施 FCM聚類后得到一個(gè)對(duì)X的模糊劃分，用一個(gè)模糊劃分矩陣表示為

根據(jù)式(8)，定義2個(gè)統(tǒng)計(jì)量分別為

這 2個(gè)量分別表示相應(yīng)點(diǎn)(模式)或相應(yīng)類的重要度．假設(shè)某個(gè)聚類算法把數(shù)據(jù)集 X劃分到 L個(gè)類C1，C2，…，CL，因此定義任意 2個(gè)類iC和jC的相關(guān)系數(shù)為

按照式(10)計(jì)算所有類之間的相關(guān)系數(shù)后，得到相關(guān)矩陣

顯然，式(11)所表達(dá)的相關(guān)矩陣是一個(gè)實(shí)對(duì)稱的矩陣，因而必有L個(gè)實(shí)數(shù)特征根．

2.2 Gerschgorin圓盤(pán)定理和估計(jì)原則

λi( i = 1,2,… ,L)是式(11)的L個(gè)依照遞減順序排列的特征值．設(shè)A=(aij)nn×∈R ，稱由不等式

在復(fù)平面上確定的區(qū)域?yàn)榫仃?A的第i個(gè) Gerschgorin圓盤(pán)，并用iG表示，其中

稱為蓋氏圓盤(pán) Gi的半徑，i=1,2,…,n．

定理 1(Gerschgorin圓盤(pán)定理 1)[15].矩陣 A= (aij) ∈Rn×n的一切特征值都在它的n個(gè)蓋氏圓盤(pán)的并集之內(nèi)．

定理1為可視化地觀察Gerschgorin圓盤(pán)分布提供了依據(jù)，更一般地有如下結(jié)論．

定理2(Gerschgorin圓盤(pán)定理2)[15].由矩陣A的所有蓋氏圓盤(pán)組成的連通部分中任取一個(gè)，如果它由k個(gè)蓋氏圓盤(pán)構(gòu)成的，則在這個(gè)連通部分有且僅有 A的k個(gè)特征值．

定理 2說(shuō)明了蓋氏圓盤(pán)集的可分離性．在使用FCM 算法時(shí)，選擇不同的類數(shù)可能導(dǎo)致聚類結(jié)果出現(xiàn)以下3種情況[2,12].

(1) 選擇的類數(shù)比真實(shí)的類數(shù)大．這種情況下，一些原本完整的類不得不被強(qiáng)制分成更多的類，并且往往是樣本數(shù)很少的類．

(2) 選擇的類數(shù)比真實(shí)的類數(shù)?。@種情況下，一些原本分離性很好并屬于不同類的點(diǎn)被不正確地劃分到同一類，一些類的中心不得不位于樣本點(diǎn)很稀疏的位置以使 FCM 的目標(biāo)函數(shù)最小，從而極大地降低類內(nèi)點(diǎn)之間的相似度．

(3) 選擇的類數(shù)等于真實(shí)的類數(shù)．這種情況下，F(xiàn)CM 算法的聚類結(jié)果是最佳的，或者說(shuō)被錯(cuò)誤劃分的數(shù)據(jù)點(diǎn)數(shù)目最少．

根據(jù)相關(guān)矩陣的定義和特征值的計(jì)算過(guò)程可知，特征根的大小反映了所劃分類的類內(nèi)樣本的相似程度．依照Gerschgorin圓盤(pán)定理，如果實(shí)際的類數(shù)是c個(gè)，則其L個(gè)特征值出現(xiàn)的情況為

式中1cλ+到Lλ是(L c- )個(gè)相對(duì)小的特征根．因此，實(shí)際類對(duì)應(yīng)的圓盤(pán)和其他類對(duì)應(yīng)圓盤(pán)可以按照特征值的大小明顯地分開(kāi)．一般地，按照 Gerschgorin圓盤(pán)定理，本文提出指標(biāo)求解最優(yōu)的類數(shù)，即

式中c為一個(gè)整數(shù)，是在閉集合[1, 1]L- 內(nèi)所取的可能的類數(shù)．而式(15)的右邊第 2項(xiàng)是所有特征值的平均．則GDE()c的類數(shù)確定法則為：當(dāng)?shù)?1個(gè)非負(fù)的GDE()c值出現(xiàn)時(shí)所對(duì)應(yīng)的類數(shù)為最優(yōu)的類數(shù)．

3 實(shí) 驗(yàn)

以下把本文提出的基于 Gerschgorin圓盤(pán)估計(jì)的有效性指標(biāo)稱為 GDE指標(biāo)．同時(shí)，稱 Bezdek[5]提出的信息熵指標(biāo)為 VPE，Xie等[6]提出的分離性指標(biāo)為VXB，Pakhira等[9]提出的有效性指標(biāo)為 VPB．GDE被用于評(píng)價(jià)FCM聚類結(jié)果并與VPE、VXB和VPB的結(jié)果做比較．本文使用3個(gè)具有代表性的人工數(shù)據(jù)集和3個(gè)來(lái)自 UCI的真實(shí)數(shù)據(jù)集來(lái)測(cè)試和比較這些有效性指標(biāo)的正確性，具體過(guò)程和結(jié)果描述如下．

3.1 測(cè)試的數(shù)據(jù)集

3個(gè)人工數(shù)據(jù)集都使用 Matlab工具包產(chǎn)生．正確的類標(biāo)號(hào)可以從產(chǎn)生這些數(shù)據(jù)的“randn()”函數(shù)確定．這些類標(biāo)號(hào)用來(lái)評(píng)價(jià)聚類結(jié)果的正確性，而不參加聚類過(guò)程．這 3個(gè)三維的人工數(shù)據(jù)集分別標(biāo)記為數(shù)據(jù)集1、數(shù)據(jù)集2和數(shù)據(jù)集3，圖1(a)～(c)顯示了這3個(gè)數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的分布．

數(shù)據(jù)集1包含6,000個(gè)點(diǎn)，這些點(diǎn)分布在3個(gè)類中，其中一個(gè)是包含 4,000個(gè)點(diǎn)的高密度的類，另外2個(gè)是分別包含1,000個(gè)點(diǎn)的低密度的類，這個(gè)數(shù)據(jù)集被用于模擬包含密度不均勻類的數(shù)據(jù)集(見(jiàn)圖1(a))．?dāng)?shù)據(jù)集2包含5,000個(gè)點(diǎn)的類，其中5個(gè)類是分布在水平方向的非球狀的類，另一個(gè)是沿著豎直方向分布的類(見(jiàn)圖1(b))．?dāng)?shù)據(jù)集3包含6,366個(gè)點(diǎn)，分布在 15個(gè)類中，其中一些類帶有部分交疊(見(jiàn)圖1(c))．

另一方面，本實(shí)驗(yàn)選擇來(lái)自UCI的3個(gè)真實(shí)數(shù)據(jù)集進(jìn)行測(cè)試，具體描述如下．

(1) Iris數(shù)據(jù)集．這是一個(gè)包含150個(gè)樣本并且每個(gè)樣本帶有4個(gè)特征的數(shù)據(jù)集．這150個(gè)樣本均分在3個(gè)類中，每個(gè)類各有50個(gè)樣本，其中2個(gè)類帶有部分交疊而另一個(gè)類獨(dú)立于這2個(gè)類．在過(guò)去的幾十年中，Iris數(shù)據(jù)集是使用最頻繁的用于測(cè)試聚類有效性的數(shù)據(jù)集[16-17]．

圖1 3個(gè)帶有不同特征的人工數(shù)據(jù)集Fig.1 Three artificial datasets with different characteristics

(2)Letter數(shù)據(jù)集．Letter數(shù)據(jù)集包含20,000個(gè)樣本，它們分布在26個(gè)類中(對(duì)應(yīng) 26個(gè)英文字母)，每個(gè)樣本具有 16個(gè)特征．這個(gè)數(shù)據(jù)集不僅僅是一個(gè)高維海量樣本的數(shù)據(jù)集，而且不同類的邊界也具有高度非線性，即不同類的邊界不能用一個(gè)線性的超平面分開(kāi)．

(3)Satim數(shù)據(jù)集．Satim數(shù)據(jù)集是一個(gè)對(duì)觀測(cè)對(duì)象進(jìn)行衛(wèi)星多譜掃描所獲得的數(shù)據(jù)集，所有樣本分布在 6個(gè)類中．每個(gè)樣本有 36個(gè)特征，這個(gè)數(shù)據(jù)集包含6,435個(gè)樣本．

3.2 實(shí)驗(yàn)過(guò)程

首先使用 FCM 算法聚類這 6個(gè)數(shù)據(jù)集．在使用 FCM 算法時(shí)，本文根據(jù)最大隸屬度原則來(lái)判斷每一個(gè)樣本最終所歸屬的類．同時(shí)，由于 FCM 算法的聚類結(jié)果一定程度地依賴于它的初始化過(guò)程，本文選擇不同初始化條件下最優(yōu)(目標(biāo)函數(shù)最小)的聚類結(jié)果作為最終的結(jié)果．3個(gè)有效性指標(biāo)都使用正確性和運(yùn)行時(shí)間 2個(gè)指標(biāo)來(lái)評(píng)價(jià)．這里正確性是指估計(jì)類數(shù)與真實(shí)類數(shù)的一致程度；運(yùn)行時(shí)間是指使用每個(gè)有效性指標(biāo)找到最優(yōu)類數(shù)耗費(fèi)的總時(shí)間[18]，并且GDE和 3個(gè)指標(biāo)最大類數(shù)的上限都取同樣的值以使它們的結(jié)果具有可比性．

為了使用 Gerschgorin圓盤(pán)直觀地分析，首先計(jì)算FCM聚類后每個(gè)聚類結(jié)果的相關(guān)矩陣，接著在上述 6個(gè)數(shù)據(jù)集中分別解出所有的特征值．依照正確的類數(shù)，本實(shí)驗(yàn)測(cè)試了當(dāng)類數(shù)分別大于、小于和等于真實(shí)類數(shù)時(shí)，特征值的大小和分布范圍．計(jì)算相應(yīng)的 Gerschgorin圓盤(pán)半徑，圖 2～圖 7可視化地顯示了這些GDE圓盤(pán)的分布．

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

圖2～圖7顯示的6個(gè)數(shù)據(jù)集的Gerschgorin圓盤(pán)說(shuō)明如下．如果在FCM算法中所取的類數(shù)比真實(shí)的類數(shù)小，則出現(xiàn)半徑較小的圓盤(pán)的數(shù)目少，此時(shí)較大的圓盤(pán)數(shù)目提供了一個(gè)真實(shí)類數(shù)的下界．特別地，對(duì)于數(shù)據(jù)集1和Iris數(shù)據(jù)集，這2個(gè)計(jì)算的圓盤(pán)接近同樣的半徑，無(wú)法取舍．這種情況意味著所取的類數(shù)(c=2)并不足夠大．相反，如果在 FCM 算法中所取類數(shù)比真實(shí)的類數(shù)更大，則許多小半徑的圓盤(pán)出現(xiàn)．這種情況表明一些類是冗余的，一些原本相似度高的完整的類被不正確地劃分成不同類．特別地，當(dāng)數(shù)據(jù)集中所取的類數(shù)等于真實(shí)的類數(shù)時(shí)，出現(xiàn)半徑較小類的數(shù)目是最少的．因此，一個(gè)數(shù)據(jù)集中Gerschgorin圓盤(pán)的分布可以給使用者提供關(guān)于真實(shí)類數(shù)的新信息．

表1顯示了GDE指標(biāo)在6個(gè)數(shù)據(jù)集中計(jì)算出的最優(yōu)類數(shù)，以及與其他3個(gè)已有的有效性指標(biāo)的比較結(jié)果．

圖2 數(shù)據(jù)集1對(duì)應(yīng)Gerschgorin圓盤(pán)分布Fig.2 Distributions of Gerschgorin disks in dataset 1

表1 在6個(gè)測(cè)試的數(shù)據(jù)集中3個(gè)有效性指標(biāo)的準(zhǔn)確性和穩(wěn)定性Tab.1 Correctness and stability of the three validity indices in the six datasets

表1的結(jié)果表明，如果測(cè)試的數(shù)據(jù)集中的類接近球狀，例如數(shù)據(jù)集1、數(shù)據(jù)集 2、Iris數(shù)據(jù)集、Satim數(shù)據(jù)集等，則FCM算法是最有效的．相應(yīng)地，每個(gè)有效性指標(biāo)都近似地判斷出正確的類數(shù)．然而，如果一些類是交疊的，這些指標(biāo)建議的類數(shù)有一些偏差．總體而言，VPB的結(jié)果并不比VXB好，與VPE的正確性基本相同．GDE指標(biāo)比其他3個(gè)指標(biāo)偏差要?。?/p>

不同于Iris、Satim和Cancer數(shù)據(jù)集，Letter數(shù)據(jù)集包含非線性的類．這導(dǎo)致了有效性指標(biāo)在估計(jì)類數(shù)時(shí)出現(xiàn)相當(dāng)大的差別，其本質(zhì)是FCM算法無(wú)論在任何情況下都無(wú)法得到正確的劃分．迄今，還沒(méi)有任何一個(gè)聚類算法能夠正確地劃分 Letter數(shù)據(jù)集中的大多數(shù)樣本．相應(yīng)地，也沒(méi)有任何一個(gè)有效性指標(biāo)能夠判斷出該數(shù)據(jù)集中的類數(shù)[2,16]．有意義的是，GDE指標(biāo)能夠估計(jì)出其正確類數(shù)的上界和下界．這比單純地確定一個(gè)類數(shù)往往更重要．

表 1進(jìn)一步顯示各個(gè)指標(biāo)的耗費(fèi)時(shí)間．GDE的運(yùn)算時(shí)間包括一次使用聚類、計(jì)算相關(guān)矩陣、計(jì)算特征值 3部分．其中實(shí)施 1次聚類是最耗費(fèi)時(shí)間的部分，但對(duì)比已有的有效性指標(biāo)必須遍歷所有可能的類數(shù)，這里的計(jì)算時(shí)間已經(jīng)至少降低 1個(gè)數(shù)量級(jí)．特別地，進(jìn)一步增加所取的類數(shù)，GDE所用的時(shí)間不變，其他3個(gè)指標(biāo)所用的時(shí)間會(huì)線性成比例增長(zhǎng)．

圖3 數(shù)據(jù)集2對(duì)應(yīng)Gerschgorin圓盤(pán)分布Fig.3 Distributions of Gerschgorin disks in dataset 2

圖4 數(shù)據(jù)集3對(duì)應(yīng)Gerschgorin圓盤(pán)分布Fig.4 Distributions of Gerschgorin disks in dataset 3

圖5 Iris數(shù)據(jù)集對(duì)應(yīng)Gerschgorin圓盤(pán)分布Fig.5 Distributions of Gerschgorin disks in Iris dataset

圖6 Satim數(shù)據(jù)集對(duì)應(yīng)Gerschgorin圓盤(pán)分布Fig.6 Distributions of Gerschgorin disks in Satim dataset

圖7 Letter數(shù)據(jù)集對(duì)應(yīng)Gerschgorin圓盤(pán)分布Fig.7 Distributions of Gerschgorin disks in Letter dataset

3.4 一般性分析

本文以一個(gè)包含3個(gè)類的數(shù)據(jù)集為例，對(duì)特征值與數(shù)據(jù)集的類的位置關(guān)系做更為細(xì)致的觀察，如圖 8所示，隨著3個(gè)類之間相對(duì)位置的變化，表2顯示相關(guān)矩陣的相對(duì)特征值也在變化，這里相對(duì)特征值定義為

式中c為在FCM算法中所使用的類數(shù)．相對(duì)特征值使得在不同數(shù)據(jù)集中計(jì)算出的特征值具有了可比性.從相對(duì)特征值的分布可以看出，特征值之間的相對(duì)大小反映了類間距離的變化，特征值越大則一個(gè)類的分離性越好，并且同一個(gè)類的類內(nèi)相似度越高．不同于已有的有效性指標(biāo)分別使用類內(nèi)距和類間距局部度量，GDE可以整體度量類之間的相對(duì)位置．同時(shí)，有充分的理論依據(jù)和泛化能力，這是使用 GDE可以正確判斷類數(shù)的基本動(dòng)機(jī)．

表2 隨著3個(gè)類相對(duì)位置變化特征值的變化Tab.2 Eigenvalue variations of the related matrix with different mutual position variances

圖8 隨3個(gè)類的相對(duì)位置不同相關(guān)矩陣的特征值變化Fig.8 Eigenvalue variance of the related matrix in terms of different mutual positions

4 結(jié) 語(yǔ)

雖然研究者[1,12-13]已經(jīng)提出許多有效性指標(biāo)，但是實(shí)際工程界仍然存在著改善這些有效指標(biāo)效率的迫切需要．本文提出一個(gè)新的聚類有效性指標(biāo)來(lái)解決聚類結(jié)果的評(píng)價(jià)問(wèn)題，這個(gè)新的有效性指標(biāo)評(píng)估任何 2個(gè)類之間的整體分布而不是局部分布．特別地，本文提出的指標(biāo)不是遍歷式地搜索所有可能的類數(shù)，而是在取一個(gè)較大的類數(shù)后，最少僅僅需要一次聚類就可以估計(jì)出最優(yōu)的類數(shù)，從而極大地提高了有效性指標(biāo)的工作效率．理論和實(shí)驗(yàn)結(jié)果都證明了本文提出有效性指標(biāo)是有用的和高效的．

然而，本文提出的有效性指標(biāo)的工作效率必然受到相關(guān)矩陣的定義、計(jì)算方式以及聚類結(jié)果本身正確性的影響．因此本研究?jī)H僅是一個(gè)從根本上提高有效性指標(biāo)效率的初步嘗試，如何更好地構(gòu)造相關(guān)矩陣以及如何選擇適當(dāng)?shù)拈撝祦?lái)確定最終的類數(shù)，仍然有待于進(jìn)一步研究，這些都是將來(lái)進(jìn)一步研究的方向．

［1］ Xu Rui，Wunsch D. Survey of clustering algorithm[J]. IEEE Trans on Neural Network，2005，16(3)：645-678.

［2］ Yue Shihong，Wu T，Liu Zhiqing，et al. Fused multicharacteristic validity index：An application to reconstructed image evaluation in electrical tomography[J]. International Journal of Computational Intelligence Systems，2011，4(5)：1052-1061.

［3］ Bezdek J C，Pal N G. Some new indexes of cluster validity [J]. IEEE Trans on SMC：Cybernetics，1998，28 (3)：301-315.

［4］ MacQueen J B. Some methods for classification and analysis of multivariate observations[C]//The 5th Berkeley Symposium on Mathematical and Probability. Berkeley，USA，1967：281-297.

［5］ Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. New York：Plenum Press，1981.

［6］ Xie X L，Beni G. A validity measure for fuzzy clustering [J]. IEEE Trans on Pattern Anal Mach Intell，1991，13(8)：841-847.

［7］ Kim D J，Park Y W，Park D J. A novel validity index for determination of the optimal number of clusters [J]. IEICE Trans on Inform Syst，2001，84(2)：281-285.

［8］ Kim D J，Lee K H，Lee D. On cluster validity index for estimation of the optimal number of fuzzy clusters [J]. Pattern Recognition，2004，37(10)：2009-2025.

［9］ Maulik U，Bandyopadhyay S. Performance evaluation of some clustering algorithms and validity indices[J]. IEEE Trans on Pattern Anal Mach Intel，2002，24 (12)：1650-1654.

［10］ Pakhira M K，Bandyopadhyay S，Maulik U. Validity index for crisp and fuzzy clusters[J]. Pattern Recognition，2004，37(3)：487-501.

［11］ Liu Ruochen，Sun Xiaojuan，Jiao Licheng，et al. A comparative study of different cluster validity indexes [J]. Transactions of the Institute of Measurement and Control，2012，34(7)：876-890.

［12］ Yue Shihong，Wang J，Wu T，et al. A new separation measure for improving the effectiveness of validity indices [J]. Information Science，2010，180(5)：411-423.

［13］ Cheng Hao，Vu K，Hua K A. Subspace projection：A unified framework for a class of partition-based dimension reduction techniques[J]. Information Sciences，2009，179(9)：1234-1248.

［14］ 陳黎飛，姜青山，王聲瑞. 基于層次劃分的最佳聚類數(shù)確定方法[J]. 軟件學(xué)報(bào)，2008，19(1)：62-72.

Chen Lifei，Jiang Qingshan，Wang Shengrui. A hierarchical method for determining the number of clusters [J]. Journal of Software，2008，19(1)：62-72(in Chinese).

［15］ Watkins D S. Fundamentals of Matrix Computations [M]. USA：John Wiley & Sons，2002.

［16］ Wang J，Chiang J. A cluster validity measure with a hybrid parameter search method for support vector clustering algorithm [J]. Pattern Recognition，2008，41(2)：506-520.

［17］ Yip K Y，Ng M K，Cheung D W. Input validation for semi-supervised clustering [C]//Proceedings of the 6th IEEE ICDM Workshops. Hong Kong，China，2006：479-483.

［18］ Jiang He，Ren Zhilei，Xuan Jifeng，et al. Extracting elite pairwise constraints for clustering[J]. Neurocomputing，2013，99(1)：124-133.

（責(zé)任編輯：孫立華）

Matrix Eigenvalue Analysis-Based Clustering Validity Index

Yue Shihong，Huang Ti，Wang Penglong
(School of Electrical Engineering and Automation，Tianjin University，Tianjin 300072，China)

Many validity indices have been proposed for quantitatively assessing the performance of fuzzy clustering algorithms. But so far these validity indices work with little satisfaction due to their unreasonable structures and low efficiency in applications. In this paper，a Gerschgorin disk estimation-based criterion was proposed to estimate the correct number of clusters. Firstly，a correlation matrix was derived from the fuzzy clustering results，and then the eigenvalue decomposition was performed to obtain all eigenvalues and eigenvectors of the matrix. Finally，based on the classical Gerschgorin disk theorem，the optimal number of clusters was estimated. To validate the proposed criterion in fuzzy clustering，a group of the most used validity indices were applied to three synthetic datasets and three real datasets with different characteristics，and compared with the proposed criterion. The experimental results verify that the proposed criterion can discover the inherit natures among the clustered patterns and suggest more accurate number of clusters.

validity index；Gerschgorin disk；fuzzy cluster；eigenvalue

TK421

A

0493-2137(2014)08-0689-08

10.11784/tdxbz201301016

2013-01-06；

2013-02-01.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61174017).

岳士弘（1964— ），男，博士，教授.

岳士弘，shyue1999@tju.edu.cn.