劉來權(quán)，陳 燕，雷燕瑞

模糊C均值聚類算法的有效性檢驗研究

劉來權(quán)，陳 燕，雷燕瑞

(海南軟件職業(yè)技術(shù)學(xué)院，海南 瓊海 571400)

模糊C均值（Fuzzy C-means，F(xiàn)CM）聚類算法是聚類算法中的經(jīng)典算法，此算法引入了隸屬度及模糊度的概念，應(yīng)用范圍及應(yīng)用行業(yè)也更為廣泛。FCM聚類算法的聚類劃分受到數(shù)據(jù)分布的影響較大，模糊度參數(shù)的選擇很容易影響聚類算法的聚類結(jié)果，且易陷入局部極值的問題。因此研究FCM聚類算法的有效性檢驗方法則具有非常意義。

模糊C均值；聚類；有效性；檢驗

0 引言

隨著信息化技術(shù)的發(fā)展，各方收集的數(shù)據(jù)也隨之呈級數(shù)級增加，數(shù)據(jù)已經(jīng)在我們的日常生活中無處不在，國際數(shù)據(jù)公司（IDC）預(yù)測2020年全球?qū)碛?5ZB（35*10億TB）的數(shù)據(jù)[1]，如果靠人工的方式處理這些數(shù)據(jù)顯然不現(xiàn)實，聚類則是進(jìn)行數(shù)據(jù)挖掘中常用的數(shù)據(jù)分析方法[2]，數(shù)據(jù)的聚類算法研究也一直是一個非常重要的研究內(nèi)容。

傳統(tǒng)的聚類算法嚴(yán)格將劃分對象歸屬于某一類，劃分界限涇渭分明，具有“非此即彼”的特點[3]。而現(xiàn)實世界中的有些對象無法進(jìn)行這么明顯的劃分，更適合按照特征進(jìn)行隸屬度的劃分。1965年，美國的數(shù)學(xué)家L.A.Zadeh發(fā)表了《模糊集（Fuzzy Sets）》，第一次將模糊性與數(shù)學(xué)聯(lián)系在一起[4]。以此為起點，有科學(xué)家不斷將模糊劃分的概念應(yīng)用于數(shù)據(jù)挖掘中，人們開始用模糊的劃分方法來處理聚類問題，因模糊劃分的中介性，能更加客觀的反應(yīng)現(xiàn)實世界的問題，因此成為研究的主流方向[5]，目前也是最廣泛應(yīng)用的聚類算法之一。

模糊聚類算法屬于無監(jiān)督的算法，一般用于分類算法的評價方法不適合評價模糊聚類算法。目前，有關(guān)聚類有效性檢驗的研究也有很多。

1 模糊C均值聚類算法

對于一個包含n個樣本的數(shù)據(jù)集合X=｛x1,x2……,xn｝，樣本xk∈X,k=1,2,……,n 。聚類過程將其劃分為c類，得到劃分矩陣U(X)，用U=■uik■c*n則表示樣本對類別的隸屬度矩陣，uik則

模糊C-均值聚類算法的基本思想是：表示的是數(shù)據(jù)集合X的第k個樣本數(shù)據(jù)xk對第i類的隸屬度，V=｛vi｝,i=1,2,……,c 則表示的是各個類別的聚類中心[6]。FCM算法定義數(shù)據(jù)集合X中樣本與聚類中心的誤差平方為[7]：

Dunn對每個樣本點跟每個聚類中心的距離用隸屬度平方加權(quán)，得到聚類內(nèi)的加權(quán)平方和目標(biāo)函數(shù)：

2 模糊聚類有效性檢驗

聚類算法是沒有先行經(jīng)驗的算法，當(dāng)確定聚類算法的選擇之后，那么對于數(shù)據(jù)集該劃分為多少類較為合理，對聚類的結(jié)果又該如何評價其優(yōu)劣性，這就是聚類的有效性問題。雖然在一些應(yīng)用中，聚類數(shù)可以通過用戶的經(jīng)驗和領(lǐng)域知識進(jìn)行估計，但一般情況下，聚類數(shù)是無法預(yù)先知道的，評價聚類質(zhì)量并確定最佳聚類數(shù)是一項困難的工作。

聚類算法是沒有先行經(jīng)驗的算法，因此待聚類的數(shù)據(jù)對象沒有任何相關(guān)的屬性標(biāo)簽，因此對于聚類結(jié)果的優(yōu)劣性是沒有辦法直觀評價的。聚類時對于同一種聚類算法，也會因出示聚類中心的選取以及聚類數(shù)目的設(shè)置不同，而產(chǎn)生不同的聚類結(jié)果。因此，評價聚類算法的劃分結(jié)果并非易事，那么研究聚類的有效性檢驗問題就是非常關(guān)鍵的一步。

對于聚類算法的有效性研究，可以將其分為三類，第一類是僅考慮數(shù)據(jù)集集合結(jié)構(gòu)信息的聚類有效性指標(biāo)、第二類是僅考慮隸屬度的聚類有效性指

標(biāo)，第三類是僅考慮隸屬度的聚類有效性指標(biāo)、第四類是同時考慮數(shù)據(jù)集集合結(jié)構(gòu)信息和隸屬度的聚類有效性指標(biāo)。由于待聚類數(shù)據(jù)的多樣性特點，單一的評價方式不可能解決不同情況的聚類有效性問題，本文介紹給予幾何結(jié)構(gòu)的聚類有效性指標(biāo)。

2.11991年Xie-Beni提出的有效性指標(biāo)xieV[9]

其定義如下：

Vxie是聚類后類內(nèi)部緊湊度以及類和類之間離散度的比例，公式(6)的分子用來衡量類內(nèi)部的緊湊度，此值小則緊湊度高。Vxie(U,V,c)則是在類內(nèi)部的緊湊度與類和類之間的分離度之間尋求一個平衡點，如果聚類可以使其值達(dá)到最小，則能夠獲得較好的聚類效果。

2.22011年Zalik K. R.和Zalik B. 提出的有效性指標(biāo)SV指標(biāo)[10]

SV指標(biāo)不同于xieV，它使用最鄰近的距離估計聚類的離散性，用邊界點到每個類的聚類中心的距離表示類和類之間的緊致性。SV指標(biāo)定義如下：

Zalik K.R.和Zalik B.隨后提出了SV指標(biāo)的模糊表達(dá)，用于模糊聚類的有效性檢驗。

關(guān)于聚類的有效性指標(biāo)，有很多學(xué)者提出的各種指標(biāo)，比如還有2001年Halkidi和Vazirgiannisp[11]提出的S_Dbw指標(biāo)，2006年楊善林[12]提出的距離代價函數(shù)等。

3 小結(jié)

聚類是數(shù)據(jù)挖掘和人工智能方面使用非常廣泛的方法之一，而聚類的目標(biāo)是盡可能使得同一類內(nèi)部緊致，而類和類之間盡可能離散。模糊聚類算法則同時使用模糊度和隸屬度的方法，可使得聚類的樣本同時隸屬于兩個或多個類，很大程度增強(qiáng)了模糊聚類的使用范圍。雖然模糊聚類算法應(yīng)用范圍廣，應(yīng)用領(lǐng)域也多，但如何評估模糊聚類的有效性也是需要解決的問題。

[1] Gantz J, Reinsel D.Extracting value from chaos[J]. IDCiView, 2011: 1-12.

[2] 樸尚哲. 模糊C均值算法的聚類有效性評價[J]. 模式識別與人工智能, 2015(5): 452-461.

[3] 謝桂林, 詹志強(qiáng), 李凱. 基于聚類的因子分解機(jī)推薦算法研究[J]. 軟件, 2016(10): 113-117.

[4] Zadeh L A. Fuzzy sets[J]. Information and Control, 8(1965): 338-353.

[5] 孔攀. 模糊聚類分析及其有效性研究[D]. 西南大學(xué). 重慶: 8-10.

[6] 杜淑穎. 基于大型數(shù)據(jù)集的聚類算法研究[J]. 軟件, 2016, (01): 132-135+138.

[7] Dunn J C．A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well Separated Clusters[J]. Journal of Cybernetics, 1974, 3(3): 32-57.

[8] Pal N R, Bezdek J C. On Cluster Validity for the Fuzzy C-means Model. IEEE Trans on Fuzzy Systems, 1995, 3(3): 370-379.

[9] Xie X L. Beni G.A validity meansure for fuzzy clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1992. 16(9): 954-960.

[10] Zalik K. R., Zalik B. Validity index for clusters of different sizes and densities[J]. Pattern Recognition Letters, 2011, 32(2): 221-234.

[11] Halkidi M., Vazirgiannis M.Clustering validity assessment: Finding the optimal partitioning of a data set[C]. IEEE International Conference on Data Mining(ICDM), 2001: 187-194.

[12] 楊善林, 李永森. K-means算法中的k值優(yōu)化問題研究[J].系統(tǒng)工程理論與實踐, 2006, 26(2): 97-101.

Research on the Validity of Fuzzy C Mean Clustering Algorithm

LIU Lai-quan, CHEN Yan, LEI Yan-rui
(Hainan College of Software Technology, Qionghai 571400, China)

Fuzzy C-means (FCM) clustering algorithm is a classical algorithm in the clustering algorithm, this algorithm introduces the concept of membership and fuzzy degree, the scope of application and the application of the industry is also more extensive C-means. The clustering of FCM clustering algorithm has a great influence on the data distribution, and the selection of fuzzy parameters can easily affect the clustering results of clustering algorithm, and it is easy to fall into the local extremum problem. Therefore, it is of great significance to study the validity of FCM clustering algorithm.

FCM; Clustering; Validity; Test

TP3-0

A

10.3969/j.issn.1003-6970.2017.02.004

海南省自然科學(xué)基金(No.20156232)資助

劉來權(quán)(1979-)，男，副教授，主要研究方向：項目管理、算法、多媒體應(yīng)用；陳燕(1978-)，女，講師，主要研究方向：多媒體應(yīng)用，算法等；雷燕瑞(1980-)，女，副教授，主要研究方向：算法、數(shù)據(jù)庫應(yīng)用、程序開發(fā)、職業(yè)教育。

本文著錄格式劉來權(quán)，陳燕，雷燕瑞. 模糊C均值聚類算法的有效性檢驗研究[J]. 軟件，2017，38（2）：16-18