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

模糊C均值聚類(lèi)算法的有效性檢驗(yàn)研究

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

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

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

模糊C均值；聚類(lèi)；有效性；檢驗(yàn)

0 引言

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

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

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

1 模糊C均值聚類(lèi)算法

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

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

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

2 模糊聚類(lèi)有效性檢驗(yàn)

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

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

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

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

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

其定義如下：

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

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

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

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

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

3 小結(jié)

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

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

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

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

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

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

[6] 杜淑穎. 基于大型數(shù)據(jù)集的聚類(lèi)算法研究[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)化問(wèn)題研究[J].系統(tǒng)工程理論與實(shí)踐, 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)資助

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

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