趙慧珍，劉付顯，李龍躍

(空軍工程大學 防空反導學院，陜西 西安 710051)

Parzen窗確定系數(shù)的協(xié)同模糊C均值算法

趙慧珍，劉付顯，李龍躍

(空軍工程大學 防空反導學院，陜西 西安 710051)

協(xié)同模糊C均值(collaboration fuzzy C-means，CFC)算法的協(xié)同系數(shù)通常根據(jù)經(jīng)驗人工設定，且在協(xié)同過程中保持不變，不能充分利用數(shù)據(jù)子集之間的協(xié)同關系，算法精度有限。提出Parzen窗確定系數(shù)的協(xié)同模糊C均值(βp-CFC)算法。用模糊C均值(fuzzy C-means，F(xiàn)CM)算法求出各數(shù)據(jù)子集的隸屬度和聚類中心，再用Parzen窗求出各子集在聚類中心處的密度，根據(jù)子集間密度的相關性設定變化的協(xié)同系數(shù)，利用變化的協(xié)同系數(shù)進行協(xié)同聚類。以Matlab為平臺，對βp-CFC算法進行了實驗，算法聚類準確率可達到80.34%，比模糊C均值算法、固定系數(shù)的CFC算法的準確率分別高出11.80%和3.94%。實驗證明，βp-CFC算法較為合理，聚類性能較好。

Parzen窗；密度；模糊C均值；協(xié)同系數(shù)

0 引 言

聚類算法是數(shù)據(jù)挖掘領域的重要數(shù)據(jù)分析方法之一，其原理是利用數(shù)據(jù)集中對象的相似性形成有限個簇，簇間對象相似性盡可能低，簇內對象相似性盡可能高[1]。常用相似性度量指標有歐式距離、馬氏距離、切比雪夫距離等。眾多聚類算法中，模糊C均值[2-3](fuzzy C-Means, FCM)算法作為對經(jīng)典C均值算法的擴展[4]，在數(shù)據(jù)挖掘、模式識別等領域有著廣泛研究和應用。

協(xié)同模糊聚類最早在文獻[5]中提出，算法利用同一對象在不同數(shù)據(jù)子集中的信息，即數(shù)據(jù)子集之間的協(xié)同作用，得到更精確的隸屬度矩陣，從而提高聚類性能。協(xié)同模糊C均值(collaborative fuzzy C-means, CFC)[5-6]算法是在FCM[7]的基礎上提出來的，是關于協(xié)同模糊聚類最先進的方法之一。如何合理地對數(shù)據(jù)子集之間的協(xié)同關系進行量化，并以協(xié)同系數(shù)的方式表現(xiàn)出來是CFC算法的關鍵[8-9]。通常協(xié)同系數(shù)根據(jù)經(jīng)驗人工設定，且在整個協(xié)同過程中保持不變，不能充分描述數(shù)據(jù)子集之間的協(xié)同關系[10-11]。針對這種情況，本文提出Parzen窗確定系數(shù)的協(xié)同模糊C均值(βp-CFC)算法。首先，利用FCM求出各數(shù)據(jù)子集的隸屬度矩陣和聚類中心；其次，利用Parzen窗求出各數(shù)據(jù)子集在聚類中心處的密度；再其次，根據(jù)子集間密度的相關性設定變化的協(xié)同系數(shù)；最后，用變化的協(xié)同系數(shù)進行協(xié)同聚類。變化的協(xié)同系數(shù)能夠更加充分地描述數(shù)據(jù)子集之間的協(xié)同關系，從而提高聚類精確度。

1 Parzen窗與協(xié)同模糊C均值算法

1.1 Parzen窗密度估計

Parzen窗密度估計是一種非參數(shù)估計方法，能夠很好地利用一組樣本對總體概率密度進行估計，從而描述一維或者多維數(shù)據(jù)的分布狀態(tài)[1]。以方窗為例，窗函數(shù)定義為

(1)

(1)式中，μj為第j維的坐標，當|μj|<0.5(j=1,2,3,…,d)時，窗函數(shù)φ(μ)值取1，否則取0。易知，φ(μ)是以原點為中心、以1為邊長的的超立方體。落入超立方體內的樣本數(shù)為

(2)

(2)式中：xi為樣本點；x為待估計密度處；hN為方窗窗寬。根據(jù)落入窗內的樣本點，估計樣本在x處的密度為

(3)

(3)式中：N為樣本總數(shù)；VN為方窗體積。(3)式為Parzen窗概率密度估計的基本公式。Parzen窗有多種核函數(shù)，只需滿足條件

(4)

本文所用核函數(shù)為描述正態(tài)窗的高斯函數(shù)，表示為

(5)

1.2 協(xié)同模糊C均值算法

假設數(shù)據(jù)集X含有N個對象X={x1,…,xN}，任一對象xj為d維向量，代表著d個特征，即xj=[xj1,…,xjd]T∈Rd，利用FCM算法將其聚為c類，則需要目標函數(shù)J取得最小值[12-14]，表示為

‖xj-vi‖2

(6)

(6)式中：m是模糊指數(shù)，表示隸屬度的模糊程度，通常取m=2；xj(j=1,…,N)為待聚類的對象；vi=[vi1,…,vid]T∈Rd(i=1,2,…,c)為第i個聚類中心；‖xj-vi‖為對象與聚類中心之間的距離范數(shù)，通常采用歐式距離；uij為隸屬度矩陣元素，代表第j個對象屬于第i個聚類的程度，隸屬度矩陣U的表現(xiàn)形式及其元素uij需滿足的約束條件為

U=[uij]c×N

(7)

最優(yōu)化隸屬度矩陣元素urs(r=1,2,…,c;s=1,2,…,N)通過迭代(8)式獲得。

(8)

最優(yōu)化聚類中心vrt(r=1,2,…,c;t=1,2,…,d)通過迭代(9)式獲得。

(9)

(10)

(11)

(12)

CFC算法能夠利用數(shù)據(jù)子集之間的協(xié)同關系，提高聚類性能，但算法的協(xié)同系數(shù)一般根據(jù)經(jīng)驗人工設定且保持不變，不能充分描述子集間的協(xié)同關系。

2 βp-CFC算法

協(xié)同系數(shù)β需要反映數(shù)據(jù)子集之間的協(xié)同關系，β越大，協(xié)同數(shù)據(jù)子集對待處理數(shù)據(jù)子集的影響越大。數(shù)據(jù)子集由在相同特征集下定義的對象組成，相同特征在不同數(shù)據(jù)子集中的分布具有一定的密度相似性，密度相似性越高，相互之間的協(xié)同影響越大，反之，影響越小。βp-CFC算法基于Parzen窗密度估計原理，分別估計各數(shù)據(jù)子集在聚類中心處的密度，再根據(jù)密度相關性設定變化的協(xié)同系數(shù)β，密度相似性越高，β越大。

(13)

對于第k個聚類中心vk[ii]，落入以vk[ii]為中心的正態(tài)窗內的對象數(shù)為

(14)

(14)式中，窗長度hN取值為

(15)

(15)式中：N=N[ii]，N是數(shù)據(jù)子集中對象的個數(shù)；h1為可調節(jié)的參數(shù)，能夠調節(jié)窗口大小。根據(jù)落入窗內的數(shù)據(jù)點，估計在vk[ii]處的密度為

(16)

(16)式中，VN為窗的體積。且對于同一數(shù)據(jù)子集，對象數(shù)量N與窗體積VN為固定值。數(shù)據(jù)子集D[ii]中各聚類的密度函數(shù)為

(17)

數(shù)據(jù)子集D[jj]與D[ii]密度的相關系數(shù)為

(18)

(18)式中：cov(P[ii],P[jj])=E[(P[ii]-E(P[ii]))(P[jj]-E(P[jj]))]表示子集P[ii]，P[jj]間的協(xié)方差；A[P[ii]]=E(P[ii]-E(P[ii]))2表示子集自身方差。令

K[ii]=[k(v1[ii]),k(v2[ii]),…,k(vc[ii])]T

(19)

則

(20)

簡化(18)式得

(21)

由(21)式可知，相關系數(shù)可通過計算落入正態(tài)窗內的對象個數(shù)得到。顯然，子集間的相互協(xié)同作用越強，相關系數(shù)越大，反之，相關系數(shù)越小。令

β[ii|jj]=β[jj|ii]=ρ[ii|jj]

(22)

則數(shù)據(jù)子集D[jj]與D[ii]的相關性越大，二者協(xié)同作用越強，協(xié)同系數(shù)β[ii|jj]越大；子集間相關性越小，協(xié)同作用越弱，協(xié)同系數(shù)β[ii|jj]越小。故協(xié)同系數(shù)能夠充分描述數(shù)據(jù)子集之間的協(xié)同關系。

從圖4可見，含鈦高爐渣的雜質CaO、MgO、Fe、Al2O3脫除率隨著反應時間的延長逐漸增大，但時間超過6 h時，TiO2損失率明顯提高，因此，合適的反應時間為6 h。

βp-CFC算法利用變化的協(xié)同系數(shù)進行聚類，迭代(23)式與(24)式得到隸屬度矩陣與聚類中心分別表示為

(23)

(24)

βp-CFC算法的具體步驟如下。

1)拆分數(shù)據(jù)子集；

2)利用FCM算法計算每個數(shù)據(jù)子集的隸屬度矩陣U[ii]和聚類中心V[ii]；

3)數(shù)據(jù)子集間類別匹配；

4)根據(jù)(21)式計算各子集間相關系數(shù)；

5)根據(jù)(22)式計算各子集間協(xié)同系數(shù)β[ii|jj]；

6)分別根據(jù)(23)式和(24)式計算協(xié)同隸屬度矩陣和協(xié)同聚類中心；

7) 輸出聚類結果。

βp-CFC算法流程如圖1所示。

圖1 βp-CFC算法流程Fig.1 Flow chart of βK-CFC algorithm

3 實驗分析

為驗證βp-CFC算法協(xié)同系數(shù)的有效性及聚類性能，本文進行了2組實驗。第1組是聚類準確性分析，利用加州大學(university of California Lrvine, UCI)數(shù)據(jù)庫中的Wine數(shù)據(jù)集[12-13]，分別以不同且固定的β值和βp-CFC算法得到的變化的β值進行聚類，并將聚類結果與UCI提供的標準結果進行比較；第2組是聚類指標分析，利用人工數(shù)據(jù)集Dataset，分別以βp-CFC算法和FCM算法進行聚類，并用系數(shù)(partition coefficient，PC)，分離熵(classification entropy, CE)，SC指標(partition index，SC)，S指標(separation index，S)，XB 指標(Xie and Beni’s index，XB)，DI指標(Dunn’s index，DI)這6項指標對聚類結果進行評價[14]。

3.1 聚類準確性分析

利用UCI數(shù)據(jù)庫中的真實數(shù)據(jù)集Wine進行實驗。Wine數(shù)據(jù)集描述了178個對象的13種特征，這些對象可被聚為3類。UCI同時提供了準確的聚類結果用于對比分析。

將數(shù)據(jù)集拆分為4個數(shù)據(jù)子集，每個數(shù)據(jù)子集均由從原始數(shù)據(jù)中抽取的6組特征組成，如表1所示。

根據(jù)第2節(jié)所述求得協(xié)同系數(shù)β，見表2。因為只考慮子集之間的協(xié)同作用，故令子集與自身的協(xié)同系數(shù)為0。

表1 數(shù)據(jù)子集所包含的特征

表2 數(shù)據(jù)子集之間的協(xié)同系數(shù)

根據(jù)協(xié)同系數(shù)β，迭代(23)式與(24)式，求得隸屬度矩陣和聚類中心，判定對象屬于隸屬度最大的一類，從而聚類。為對比分析，設β分別取固定值0.2，0.4，0.6，0.8，并在同一數(shù)據(jù)集中進行實驗。將5組實驗得到的聚類結果與UCI提供的標準聚類比較，得到如表3所示結果。由表3可見，βp-CFC算法得到的聚類正確率最高。當β取不同的固定值時，聚類效果差異較大，但CFC算法總體性能優(yōu)于FCM算法。

表3 β取不同值時得到的聚類結果

根據(jù)特征12和特征13可視化聚類結果。作為對比，UCI提供的標準結果，βp-CFC算法得到的聚類結果及協(xié)同系數(shù)取固定值0.8時的聚類結果分別如圖2—圖4所示，其中，圖3和圖4中的圓圈內的點表示錯誤聚類的點。顯然，與標準結果相比較，固定協(xié)同系數(shù)得到的聚類錯分點較多，本文算法得到的錯分點相對較少。

圖2 標準聚類Fig.2 Standard clustering result

圖3 βp-CFC得到的聚類Fig.3 Clustering result gained by βP-CFC

圖4 β=0.8時得到的聚類Fig.4 Clustering result when β=0.8

3.2 聚類指標分析

聚類有效性評價方法有多種，本文選取了常用的幾種評價方法用于實驗[15-16]，從多角度描述聚類結果。

1) PC指標。PC是僅考慮隸屬度的聚類有效性指標，如(25)式，其取值為[0,1]。PC指標形式簡單，易于計算。

(25)

PC的值越大，意味著聚類性能越好。

2)CE指標。CE也僅度量隸屬度信息，如(26)式，其取值為[0,logaC]，并隨著聚類數(shù)的增加而單調變化。

(26)

CE的值越大，意味著聚類性能越好。

3)SC指標。SC同時考慮了數(shù)據(jù)集幾何結構信息和隸屬度信息2個方面，采用緊致性度量和分離性度量的比值形式，如(27)式，其中，緊致性是指類內各樣本與聚類中心的距離之和；分離性是指所有聚類中心距離之和。

(27)

SC的值越小，意味著聚類性能越好。

4)S指標。與SC相反，S利用最小距離分離度來衡量隸屬度的有效性，表示為

(28)

S的值越小，意味著聚類性能越好。

5)XB 指標。XB也同時考慮了數(shù)據(jù)集幾何結構信息和隸屬度信息2個方面，是一個比值型模糊聚類有效性指標，表示為

(29)

XB的值越小，意味著聚類性能越好。

6)DI指標。DI指標考慮了數(shù)據(jù)集幾何結構信息，如(30)式，其最初目的是為了衡量分離性較好的聚類，而這類聚類通常模糊性較小，故DI的衡量過程有些類似硬聚類性能的衡量。

(30)

DI的值越小，意味著聚類性能越好。

文章利用人工數(shù)據(jù)集Dataset進行實驗，數(shù)據(jù)集共有2 000個對象，6種特征，可被分為3類。對數(shù)據(jù)集分別利用βp-CFC算法和FCM算法進行實驗，并利用上文所述聚類指標進行評價，對比得到如表4所示的結果。表4中評價依據(jù)里的“↑”表示指標越大，聚類性能越好；“↓”表示指標越小，聚類性能越好。

表4 聚類指標

由表4可知，PC，CE，SC，S和XB這5個指標顯示，βp-CFC算法不劣于甚至明顯優(yōu)于FCM算法。這5種指標均考慮的是聚類幾何結構信息和隸屬度信息中的1個方面甚至2個方面，而文中模糊協(xié)同聚類是根據(jù)點間距離，即聚類幾何結構信息得到的隸屬度信息進行劃分的，顯然βp-CFC算法優(yōu)于FCM算法。DI指標雖然考慮了數(shù)據(jù)集的幾何結構信息，但其最初目的是為了衡量分離性較好的聚類，而這類聚類通常模糊性較小，故DI的衡量過程有些類似硬聚類性能的衡量，βp-CFC算法根據(jù)數(shù)據(jù)子集之間的協(xié)同性進一步描述數(shù)據(jù)的模糊性，故在DI指標上βp-CFC算法性能略遜于FCM算法。總體而言，βp-CFC算法優(yōu)于FCM算法。

4 結 論

本文利用Parzen窗密度估計算法，分別估計各數(shù)據(jù)子集的密度，根據(jù)密度相關性得到變化的協(xié)同系數(shù)β，且密度相似性越高，β值越大，能夠充分描述數(shù)據(jù)子集之間的協(xié)同關系，提高協(xié)同聚類算法的性能。

[1] 邊肇祺,張學工.模式識別[M]. 3版. 北京：清華大學出版社，2010：274-295. BIAN Z Q, ZHANG X G. Pattern Recognition[M]. 3rd ed.Beijing: Press of Tsinghua University,2010:274-295.

[2] BEZDEk J C.Pattern recognition with fuzzy objective function algorithms[M].New York:Plenum Press,1981.

[3] 楊漫，蘇亞坤．采用模糊C-均值聚類的自適應圖像分割算法[J]．重慶理工大學學報：自然科學版，2015，29(6):94-99． YANG Man，SU Yakun．Adaptive Algorithm Based on Fuzzy C-Means for Image Segmentaion[J]．Journal of Chongqing University of Technology：Natural Science Edition，2015，29(6):94-99．

[4] JAIN A K. Data clustering: 50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[5] PEDRYCZ Witold.Collaborative fuzzy clustering[J].Pattern Recognition Letters, 2002,23(14):1675-1686.

[6] PEDRYCZ W, RAI P. Collaborative clustering with the use of fuzzy C-means and its quantification [J]. Fuzzy Sets and Systems, 2008,159(18): 2399-2427.

[7] COLETTA L F S.Collaborative fuzzy clustering algorithms: some refinements and design guidelines[J].IEEE Transactions on Fuzzy Systems, 2012, 20(3):444-462.

[8] 孫延維,彭智明,李健波. 基于粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法[J]. 重慶郵電大學學報：自然科學版,2015,27(5):660-666. SUN Yanwei, PENG Zhiming, LI Jianbo. Community detection algorithm based on particle swarm optimization and fuzzy clustering [J].Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition, 2015,27(5):660-666.

[9] ZARINBAL M,ZARANDI M H F, TURKSEN I B.Relative entropy collaborative fuzzy clustering method[J].Pattern Recognition,2014,8(3):338-353.

[10] PATERLINI S,KRINK T.Differential evolution and particle swarm optimization in partitional clustering[J]. Computational Statistics and Data Anlysis, 2006,50(5):1220-1247.

[11] 高翠芳,黃珊維,沈莞薔,等. 基于信息熵加權的協(xié)同聚類改進算法[J]. 計算機應用研究,2015,32(4):1016-1018，1023. GAO Cuifang,HUANG Shanwei,SHEN Wanqiang, et al. Improved collaborative clustering algorithm based on entropy weight[J]. Application Research of Computers, 2015,32(4): 1016-1018，1023.

[12] KARTHI R, ARUMUGAM S, RAMESHKUMAR K. Comparative evaluation of particle swarm optimization algorithms for data clustering using real world data sets[J]. IJCSNS International Journal of Computer Science and Network Security, 2008,8(1):203-212.

[13] 毛韶陽,李肯立.K-means初始聚類中心優(yōu)化算法研究[J].重慶郵電大學學報：自然科學版,2007,19(4):422-425. MAO Shaoyang, LI Kenli. Research on K-means initial clustering center optimal algorithm[J]. Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition, 2007, 19(4):422-425.

[14] 陳小輝,張功萱. 基于信息熵的符號屬性精確賦權聚類方法[J]. 重慶郵電大學學報：自然科學版,2014,26(6):850-855. CHEN Xiaohui, ZHANG Gongxuan.Symbol property accurate weight clustering method based on information entropy[J].Journal of Chongqing University of Posts and Telecommunications ：Natural Science Edition, 2014,26(6):850-855.

[15] 符保龍, 張愛科. 基于均值密度中心估計的k-means聚類文本挖掘方法[J]. 重慶郵電大學學報：自然科學版, 2014, 26(1): 111-115. FU Baolong, ZHANG Aike. K-means clustering text mining method using center estimation based on mean density[J]. Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition, 2014, 26(1): 111-115.

[16] 周開樂,楊善林,丁帥,羅賀.聚類有效性研究綜述[J].系統(tǒng)工程理論與實踐,2014,34(9):2417-2431. ZHOU Kaile, YANG Shanlin, DING Shuai, et al. On cluster validation[J].Systems Engineering-Theory & Practice, 2014,34(9):2417-2431.

(編輯：王敏琦)

Novel collaboration fuzzy C-means algorithm with Parzen window determined collaboration coefficient

ZHAO Huizhen, LIU Fuxian, LI Longyue

(School of Air and Missile Defense, Air Force Engineering University, Xi’an 710051, P.R.China)

Collaboration fuzzy C-means algorithm (CFC) can improve the performance of fuzzy C-means algorithm by using the collaborative relationship between the sub data sets. But the collaboration coefficient of CFC, in an inadequate using of the collaborative relationship, is always determined by priori knowledge and remains constant during collaboration stages. In order to circumvent this limitation, a novel collaboration fuzzy C-means algorithm with Parzen window determined collaboration coefficient(βp-CFC) was developed. First, fuzzy partition matrix and cluster prototypes of every sub data sets are computed by fuzzy C-means algorithm (FCM)，for the further computing of collaboration coefficient. Second, density of the cluster prototypes is gained by Parzen window method. Third, collaborative coefficient is dynamically adjusted by the correlation of density. Last, objects are clustered with dynamical collaborative coefficient. The algorithm is tested on the matlab platform, achieving a high accuracy of 80.34%, higher than FCM and CFC with 11.80% and 3.94%, respectively. Examples are provided to demonstrate the rationality of collaboration coefficient and the better performance of CFC.

Parzen window；density；fuzzy C-means algorithm；collaborative coefficient

10.3979/j.issn.1673-825X.2017.02.020

2016-01-21

2016-10-12 通訊作者：趙慧珍 happy100zhao90@163.com

TP391.3

A

1673-825X(2017)02-0272-07

趙慧珍(1990-),女，山東單縣人，博士研究生，主要研究方向為數(shù)據(jù)挖掘。E-mail:happy100zhao90@163.com。