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

劉來權，陳 燕，雷燕瑞

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

劉來權，陳 燕，雷燕瑞

(海南軟件職業技術學院，海南 瓊海 571400)

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

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

0 引言

隨著信息化技術的發展，各方收集的數據也隨之呈級數級增加，數據已經在我們的日常生活中無處不在，國際數據公司（IDC）預測2020年全球將擁有35ZB（35*10億TB）的數據[1]，如果靠人工的方式處理這些數據顯然不現實，聚類則是進行數據挖掘中常用的數據分析方法[2]，數據的聚類算法研究也一直是一個非常重要的研究內容。

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

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

1 模糊C均值聚類算法

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

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

Dunn對每個樣本點跟每個聚類中心的距離用隸屬度平方加權，得到聚類內的加權平方和目標函數：

2 模糊聚類有效性檢驗

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

聚類算法是沒有先行經驗的算法，因此待聚類的數據對象沒有任何相關的屬性標簽，因此對于聚類結果的優劣性是沒有辦法直觀評價的。聚類時對于同一種聚類算法，也會因出示聚類中心的選取以及聚類數目的設置不同，而產生不同的聚類結果。因此，評價聚類算法的劃分結果并非易事，那么研究聚類的有效性檢驗問題就是非常關鍵的一步。

對于聚類算法的有效性研究，可以將其分為三類，第一類是僅考慮數據集集合結構信息的聚類有效性指標、第二類是僅考慮隸屬度的聚類有效性指

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

2.11991年Xie-Beni提出的有效性指標xieV[9]

其定義如下：

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

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

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

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

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

3 小結

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

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

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

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

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

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

[6] 杜淑穎. 基于大型數據集的聚類算法研究[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值優化問題研究[J].系統工程理論與實踐, 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

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

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

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