岳士弘，黃 媞，王鵬龍

(天津大學電氣與自動化工程學院，天津 300072)

基于矩陣特征值分析的模糊聚類有效性指標

岳士弘，黃 媞，王鵬龍

(天津大學電氣與自動化工程學院，天津 300072)

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

有效性指標；Gerschgorin圓盤；模糊聚類；特征值

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

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

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

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

1 相關(guān)工作

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

1.1 模糊聚類算法

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

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

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

1.2 3個有代表性的模糊聚類有效性指標

1.2.1 Bezdek的信息熵指標

Bezdek提出信息熵指標表達式[5]為

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

1.2.2 Xie等提出的分離性指標

Xie和Beni提出的基于分離性的有效性指標[6]為

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

1.2.3 Pakhira等提出的有效性指標

Pakhira等[10]提出一個能同時評價硬聚類和模糊聚類結(jié)果的有效性指標，即

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

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

2 新的聚類有效性指標

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

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

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

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

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

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

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

2.2 Gerschgorin圓盤定理和估計原則

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

在復平面上確定的區(qū)域為矩陣 A的第i個 Gerschgorin圓盤，并用iG表示，其中

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

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

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

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

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

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

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

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

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

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

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

3 實 驗

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

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

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

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

另一方面，本實驗選擇來自UCI的3個真實數(shù)據(jù)集進行測試，具體描述如下．

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

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

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

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

3.2 實驗過程

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

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

3.3 實驗結(jié)果分析

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

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

圖2 數(shù)據(jù)集1對應Gerschgorin圓盤分布Fig.2 Distributions of Gerschgorin disks in dataset 1

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

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

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

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

圖3 數(shù)據(jù)集2對應Gerschgorin圓盤分布Fig.3 Distributions of Gerschgorin disks in dataset 2

圖4 數(shù)據(jù)集3對應Gerschgorin圓盤分布Fig.4 Distributions of Gerschgorin disks in dataset 3

圖5 Iris數(shù)據(jù)集對應Gerschgorin圓盤分布Fig.5 Distributions of Gerschgorin disks in Iris dataset

圖6 Satim數(shù)據(jù)集對應Gerschgorin圓盤分布Fig.6 Distributions of Gerschgorin disks in Satim dataset

圖7 Letter數(shù)據(jù)集對應Gerschgorin圓盤分布Fig.7 Distributions of Gerschgorin disks in Letter dataset

3.4 一般性分析

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

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

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

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

4 結(jié) 語

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

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

［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]. 軟件學報，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.

（責任編輯：孫立華）

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.

國家自然科學基金資助項目(61174017).

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

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