一種改進的模糊C均值聚類算法簇數(shù)量優(yōu)化研究

徐葉軍

(蘇州工業(yè)園區(qū)服務(wù)外包職業(yè)學(xué)院，江蘇蘇州 215123)

一種改進的模糊C均值聚類算法簇數(shù)量優(yōu)化研究

徐葉軍

(蘇州工業(yè)園區(qū)服務(wù)外包職業(yè)學(xué)院，江蘇蘇州 215123)

聚類分析是無監(jiān)督模式識別領(lǐng)域最重要的研究課題之一。模糊聚類由于建立了從樣本到類別的不確定性描述，能夠更客觀地反映真實的世界。傳統(tǒng)模糊聚類算法無法實現(xiàn)最優(yōu)化配置的聚類個數(shù)自動計算。本文通過采納分層聚類思想，提出了一種能自動、高效確定最佳聚類數(shù)目的新型自適應(yīng)模糊C均值聚類算法——A-FCM算法。數(shù)值實驗表明，與其他通過各種有效性函數(shù)來確定聚類數(shù)目的自適應(yīng)模糊聚類算法相比，A-FCM算法的性能更優(yōu)越。

聚類；分層聚類；模糊聚類；聚類數(shù)；有效性函數(shù)

模糊C均值算法，即FCM[1]，是目前聚類分析領(lǐng)域應(yīng)用最廣泛的算法之一，但與其他聚類算法一樣，該法同樣要求將聚類的數(shù)目當(dāng)成一個初始參數(shù)。因此，如何來確定聚類的最佳數(shù)已成為模糊聚類分析的一大研究話題。目前，用來分析聚類結(jié)果合理性的有效性函數(shù)常常被用來確定聚類的最佳數(shù)。主要的有效性函數(shù)可分為兩大類：一類是通過基于數(shù)據(jù)集而進行的模糊劃分；另一類是通過基于數(shù)據(jù)集而進行的幾何操作。J C Bedzek提出的劃分系數(shù)[2]是衡量模糊聚類有效性的首個有效性函數(shù)，用于測定聚類之間的重疊度。他認為最大指數(shù)值即是最佳聚類數(shù)。C E Shannon提出了分類熵的概念[3]，他認為最小指數(shù)值即是最佳聚類數(shù)。這兩種有效性函數(shù)均具有直觀的幾何意義和可靠的數(shù)學(xué)屬性。但它們的缺陷主要在于它們的單調(diào)趨勢及數(shù)據(jù)本身的某些特征之間缺乏直接關(guān)聯(lián)?；跀?shù)據(jù)集的幾何結(jié)構(gòu)，Xie-Beni在1991年提出了Xie-Beni有效性函數(shù)[4]。Xie-Beni指數(shù)即類間距離的程度與類內(nèi)距離的程度之間相比，最小指數(shù)值即是最佳聚類結(jié)果。研究表明，當(dāng)c→n時，Xie-Beni指數(shù)會單調(diào)遞減至0，以致喪失魯棒性而無法確定聚類的最佳數(shù)。2006年，S H Kwon提出了一種新的有效性函數(shù)，即Vkwon[5]，它是對Xie-Beni有效性函數(shù)的改進，能有效遏制指數(shù)值下降，使其永遠無法為0，最小值數(shù)值是最佳聚類數(shù)。2008年，Bensaid M提出了有效性函數(shù)Vbsand[6]，認為最小數(shù)值是最佳劃分。2009年，Yang Li，F(xiàn)usheng YU提出了L(C)這種新型的有效性函數(shù)，認為最大指數(shù)值是最佳聚類數(shù)。

為了確定最佳聚類數(shù)，目前最新的算法首先設(shè)一系列聚類數(shù)滿足C∈{Cmin，…，Cmax}，然后，根據(jù)數(shù)據(jù)集對{Cmin，…，Cmax}中每個可能的C執(zhí)行FCM算法。最后，利用有效性函數(shù)就可以得出最佳聚類數(shù)。這一方法會導(dǎo)致計算工作復(fù)雜程度高。為了解決這方面的問題，本文引入分層聚類的思想并提出一種新型的自適應(yīng)聚類算法，即A-FCM算法，它能自動確定最佳聚類數(shù)，而且因為分層拆分的緣故，能極大地減少計算工作量。本文對UCI機器學(xué)習(xí)庫里的三組數(shù)據(jù)集進行了實驗，結(jié)果表明在解決最佳聚類數(shù)的確定問題方面，A-FCM算法表現(xiàn)出比其他應(yīng)用諸如Xie-Beni指數(shù)等有效性函數(shù)的算法更好的性能。

1 模糊C-均值算法及主要的有效性函數(shù)

1.1 FCM算法

Dunn[7-8]根據(jù)Ruspini界定的數(shù)據(jù)集的模糊劃分將硬C-均值(HCM)應(yīng)用到模糊情況下。Bezdek將其延用到更一般的情況下，并對模糊聚類進行一般描述。模糊C均值算法的表達公式如下：

(1)

(2)

其中，U={uik};v=(v1,v2,…,vc);m>1,m是模糊加權(quán)指數(shù)，C是目標(biāo)研究的聚類數(shù)，n表示數(shù)據(jù)集大小。Bezdek利用迭代算法求得了方程式(1)的最優(yōu)解。該算法的迭代公式表示為：

該算法具有收斂性，且在解點位置，目標(biāo)函數(shù)獲取到局部最小值。

1.2 主要的有效性函數(shù)

劃分系數(shù)(PC)及分類熵(PE)常被用作有效性函數(shù)，有關(guān)定義如下：

上述兩個有效性函數(shù)都是單調(diào)函數(shù)，對它們的應(yīng)用造成了限制。Xie-Beni有效性函數(shù)定義如下：

(7)

其中，xj(j=1,2,…,n)是數(shù)據(jù)集上的一個模式，vj(j=1,2,…,c)是第j個聚類的原型。

2 新型自適應(yīng)模糊C均值聚類算法(A-FCM)

A-FCM算法綜合了FCM算法以及分層聚類的理念。首先，調(diào)用上文提及的FCM算法將數(shù)據(jù)集劃分為幾個初始聚類，然后開始數(shù)據(jù)分解過程。每次分解過程中，會根據(jù)某些準(zhǔn)則挑選出某個聚類，然后利用FCM算法將其分解成兩個聚類。重復(fù)上述過程直至聚類的數(shù)目達到最大為止。

2.1 聚類分解策略

Ward最小方差法最初被用在分層聚類算法的合并過程方面，通常被稱為“Ward方法”。在算法一開始，數(shù)據(jù)集的每個項目均將被認為是一個聚類，然后，其中的一些聚類合并成一個較大聚類。每次合并過程中，可以計算出從所有數(shù)據(jù)項到它們對應(yīng)的聚類中心的誤差平方和，對象間的距離可通過歐幾里得距離法測得。目標(biāo)函數(shù)即離差平方和函數(shù)。實際上，離差平方和函數(shù)反映的是聚類的緊湊性。因此，每次合并過程中，Ward方法會將在合并后能產(chǎn)生最小聚類方差的兩個聚類進行合并。

在A-FCM算法的聚類分解過程方面，本文采用Ward方法。每次分解過程中，聚類會被分解成能產(chǎn)生最大減量的離差平方和(聚類方差)的兩個聚類，因此，這表明這兩個聚類的緊湊性最差。

聚類運算的分解過程定義如下：

(8)

利用Ward方法挑選出聚類Ci以進行分解，通過分解可以得到最大的δ(Ci)，相關(guān)命題如下：

命題1 對于兩個聚類Ci、Cj，如果δ(Ci)>δ(Cj)，那么較小的聚類方差由分解Ci而產(chǎn)生。

證明 設(shè)Ci的聚類方差為Wi，將Ci分解成兩個聚類后，聚類方差之和為：

同樣，設(shè)Cj的聚類方差為Wj，對Cj進行分解后，聚類方差之和為：

聚類方差的主和為：

由上可知，如果δ(Ci)>δ(Cj)，則Pi

2.2 最佳聚類數(shù)的確定方法

衡量聚類效果的最重要準(zhǔn)則之一是偏差和緊湊性，聚類間的距離應(yīng)盡可能地大，聚類內(nèi)的距離應(yīng)盡可能地小。本文根據(jù)聚類方差提出了一個新標(biāo)準(zhǔn)。

(9)

2.3 算法

給出A-FCM算法的步驟定義如下：

輸入：一個數(shù)據(jù)集D包含n個數(shù)據(jù)項；

C最小：聚類的初始個數(shù)；

C最大：聚類的最大個數(shù)；

輸出：最佳聚類數(shù)及對應(yīng)的聚類；

①調(diào)用FCM(D,Cmin)算法將D分解成Cmin個聚類，設(shè)Csum=Cmin；

④Csum=Csum+1，直到Csum>Cmax；

⑤對于每個Ci，根據(jù)式(9)計算出S(C)；

⑥設(shè)可導(dǎo)致產(chǎn)生S(C)的最大值的數(shù)為Copt=Ci；

⑦返回Copt與Copt這兩個聚類的最佳聚類數(shù)。

3 實驗分析與結(jié)果

本文對A-FCM算法及利用有效性函數(shù)來確定最佳數(shù)的其他算法進行了比較。實驗使用到的3個數(shù)據(jù)集取自UCI數(shù)據(jù)庫[9]。UCI數(shù)據(jù)庫是加州大學(xué)歐文分校(University of CaliforniaIrvine)提出的用于機器學(xué)習(xí)的數(shù)據(jù)庫，這個數(shù)據(jù)庫目前共有187個數(shù)據(jù)集，其數(shù)目還在不斷增加，UCI數(shù)據(jù)集是一個常用的標(biāo)準(zhǔn)測試數(shù)據(jù)集。本實驗主要選用葡萄酒數(shù)據(jù)集,鳶尾屬植物數(shù)據(jù)集與玻璃數(shù)據(jù)集。

實驗過程中，對初始參數(shù)進行了設(shè)定：模糊加權(quán)指數(shù)m=2，最大迭代數(shù)i=50，收斂精確度ε=0.0001，聚類數(shù)范圍為C={2,…,10}。

3.1 葡萄酒數(shù)據(jù)集

葡萄酒數(shù)據(jù)集[9]包含178個事例，每個事例具有13個屬性，每個屬性又有3個類別。

圖1提供了S(C)的指數(shù)值。除了Vpc和Vbsand函數(shù)，大多數(shù)有效性函數(shù)均可獲取到最佳聚類數(shù)。

表1 葡萄酒數(shù)據(jù)集聚類數(shù)的指數(shù)值

圖1 葡萄酒數(shù)據(jù)集S(C)的指數(shù)值

3.2 鳶尾屬植物數(shù)據(jù)集

鳶尾屬植物數(shù)據(jù)集[9]是最為人熟知的，也是模式識別方面應(yīng)用最廣泛的一種數(shù)據(jù)集。它包含3個類別的事例，每個類別有50個事例。每個類別對應(yīng)于一種鳶尾屬植物。其中一個類別與其他兩個呈線性關(guān)系分開，但后者無法呈線性關(guān)系與前者分開。

表2是從聚類數(shù)C=2到C=10的鳶尾屬植物數(shù)據(jù)集方面的A-FCM算法及其他有效性函數(shù)的指數(shù)值。由此可知，由于后者的類別彼此之間無法呈線性關(guān)系分開，大多數(shù)有效性指數(shù)表明C=2便是最佳聚類數(shù)，同時，A-FCM算法可以確定正確的聚類數(shù)C=3。圖2中當(dāng)聚類數(shù)C=3時，A-FCM的方程式(9)的值達到最大，表明這是聚類方差發(fā)生變化的一個轉(zhuǎn)折點。

表2 鳶尾屬植物數(shù)據(jù)集聚類數(shù)的指數(shù)值

圖2 鳶尾屬植物數(shù)據(jù)集Xie-Beni和S(C)的指數(shù)值

3.3 玻璃數(shù)據(jù)集

玻璃數(shù)據(jù)集[9]包含214個事例，每個事例有10個屬性，每個屬性帶7個類別。表3提供了從聚類數(shù)C=2到C=10的玻璃數(shù)據(jù)集方面的A-FCM算法及其他有效性函數(shù)的指數(shù)值。由此可知，A-FCM的指數(shù)可以達到最佳聚類數(shù)，而其他算法方面則存在一些偏差。圖3給出了A-FCM指數(shù)值和Xie-Beni指數(shù)值。

表3 玻璃數(shù)據(jù)集聚類數(shù)的指數(shù)值

圖3 玻璃數(shù)據(jù)集Xie-Beni和S(C)的指數(shù)值

4 結(jié)語

本文提出了自適應(yīng)聚類算法A-FCM算法，通過將FCM算法與分層聚類思想相結(jié)合，A-FCM可以自動確定最佳聚類數(shù)。實驗結(jié)果表明，在確定最佳聚類數(shù)時，A-FCM算法所達到的效果比其他算法更理想。

[1]Bezdek J C.Pattern recognition with fuzzy objective functionalgorithms[M].New York:Plenum,2009:34-60.

[2]Bedzek J C.Cluster validity with fuzzy sets[J].Journal of Cybernetics,2008(3):58-72.

[3]Shannon C E.A mat hematical theory of communication[J].BellSyst Tech,2006(4):379-423.

[4]Xie X L,Beni G.A validity measure for fuzzy clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence,2009(12):841-847.

[5]Kwon S H.Cluster validity index for fuzzy clustering[J].Electronics Letters,2006(8):2176-2177.

[6]Bensaid A M.Validity-Guided(Re) clustering with applications to imgae segmentation[J].IEEE Trans on Fuzzy Systems,2008(9):112-123.

[7]Dunn J C.A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation[J].IEEE Trans. SMC,2005(2):310-313.

[8]Yang Li,Fusheng Yu.A new validity function for fuzzy clustering[J].IEEE Computational Intelligence and Natural Computing,2009(4):462-465.

[9]Asuncion A,Newman D J.UCI Machine learning repository[EB/OL].(2007-12-20)[2016-10-01]. http://www.ics.uci.edu/～mlearn/MLRepository.html.

OptimizationoftheClustersNumberofanImprovedFuzzyC-meansClusteringAlgorithm

XU Ye-jun

(Suzhou Industrial Park Institute of Services Outsourcing,Suzhou Jiangsu 215123,China)

Clustering analysis is one of the most important research topics in the field of unsupervised pattern recognition. Because fuzzy clustering has established the uncertainty description from samples to category, it is able to response to the real world more objectively. Traditional fuzzy clustering algorithm is unable to realize the clustering number automatic calculation with optimization configuration. Through adopting hierarchical clustering method, this article puts forward a kind of new adaptive fuzzy c-means clustering algorithm-A- FCM algorithm, which determines the best clustering number automatically and efficiently. Numerical experiments have shown that being compared to other adaptive fuzzy clustering algorithms which determine the clustering number through a variety of effectiveness functions, this method is superior in performance.

clustering; hierarchical clustering; fuzzy clustering; number of clusters; validity function

TP301.6

A

2095-7602(2017)10-0022-06

2017-04-18

徐葉軍(1980- )，男，講師，碩士研究生，從事計算機應(yīng)用與軟件工程研究。