截集型特征加权模糊C-均值聚类算法

摘 要:已有的特征加权型模糊C-均值(WFCM)聚类算法可以有效地提取数据的相关特征,WFCM存在的主要问题是收敛速度慢和对噪声敏感。借助模糊集的截集方式对WFCM的隶属度值进行修改,提出截集型特征加权模糊C-均值聚类算法:SWFCM。SWFCM不仅具有良好的特征提取能力,而且具有收敛速度快和对噪声稳健的优点。实验结果表明,SWFCM的总体性能优于原有的WFCM聚类算法和截集模糊C-均值聚类算法。

关键词:特征加权; 稳健聚类; 截集; 特征提取

中图分类号:TP181文献标识码:A

文章编号:1004-373X(2010)08-0123-04

Clustering Algorithm of Sectional Set Feature-weighted Fuzzy C-means

ZHI Xiao-bin, FAN Jiu-lun

(Xi’ an Institute of Post and Telecommunications, Xi’an 710121, China)

Abstract:Although the clustering algorithm offeature-weighted fuzzy C-means(WFCM)can effecively extract the related features of data, it still has some shortages such as slow convergence and sensitive to noise. The clustering algorithm of sectional set feature-weighted fuzzy C-means (SWFCM)is presented by revising the membership function of WFCM by sectional set. In comparison with WFCM, SWFCM not only can extract the features of data set, but also has the advantages of fast convergence and robust to noise. The experimental results show that SWFCM has super performance over original WFCM clustering algorithm and sectional set fuzzy C-means clustering algorithm.

Keywords:feature weighting; robust clustering; sectional set; features extraction

0 引 言

在模糊聚类算法中,模糊C-均值(FCM)聚类算法是最著名和应用最广泛的聚类算法,尽管FCM得到了广泛的应用,却存在如下缺点:收敛速度慢,对噪声敏感,不能自动选取特征。

针对传统聚类算法对数据的各个特征平等对待,不能自动选择数据相关特征的问题,众多学者提出了基于特征加权的聚类算法[1-2]。Wang等人首先[3]提出了特征加权型FCM(WFCM),Hichem等人[4]详细讨论了WFCM聚类算法,通过用类似于FCM聚类算法中隶属函数的求解方法来计算特征权值,并将所得的WFCM算法应用于彩色图像分割和监督分类问题;李洁[5],Hung[6]和陈新泉[7]等人也从不同角度研究了特征加权的FCM聚类算法。由于WFCM算法是在原FCM算法的基础上加入特征权重的迭代计算,这便使得WFCM运行时间比FCM更长,不便于实际应用。另外,实际工程应用过程中不可避免地会出现噪声,但上述的特征加权FCM聚类算法都没有考虑噪声问题,这使得所提算法在实际应用过程中很难达到预期的效果。

为了进一步提高FCM的收敛速度,裴继红等人[8]基于模糊集理论中的截集概念,提出了截集模糊C-均值(SFCM)聚类算法,SFCM符合人类思维的分类习惯,能够极大地提高算法的收敛速度。Yang等人[9]进一步深入分析了SFCM,不仅证明SFCM的收敛性,并且指出SFCM能产生“聚类核”,当选取较大的模糊参数时,SFCM具有良好的对噪声不敏感性。尽管SFCM具有收敛速度快和对噪声不敏感的优点,但SFCM与FCM一样,不能自动选取特征。

鉴于WFCM能够自动选择特征,SFCM收敛速度快并对噪声不敏感,本文考虑将二者的优点相结合,提出截集型WFCM聚类 (或者特征加权型SFCM聚类)。为了方便,本文采用术语:截集型WFCM聚类(SWFCM)。在WFCM算法基础上,用截集思想对WFCM产生的隶属度函数值进行修改。与SFCM和WFCM相比较,SWFCM既具有自动特征选取能力,又具有较快的收敛速度和良好的噪声稳健性,是一个有效的聚类算法。

1 截集FCM算法和特征加权FCM聚类算法

众所周知,对于欧式空间RM数据集X={x1,x2,…,xN},FCM的目标函数为:

ИJFCM(U,V)=∑Ni=1∑Cj=1umijxi-vj2(1)И

满足:

ИАCj=1uij=1,1≤i≤N

uij∈[0,1],1≤i≤N,1≤j≤C

运用拉格朗日乘子法可求得JFCM(U,V)最小化的必要条件为:

Иvj=(∑Ni=1umijxi)/∑Ni=1umij(2)

uij=(1/xi-vj2)/∑cl=1Xi-Vl2(3)

FCM通过交替迭代计算式(2)和式(3)来最小化JFCM(U,V)。

截集FCM(SFCM)的基本思想较为简单,就是在原FCM算法的基础上,在FCM对隶属度的每一次迭代求解过程中加一步对隶属度值的修改:对于给定的0

虽然SFCM是FCM经上述简单改动的算法,但是与FCM相比较,SFCM却具有更快的收敛速度和更好的对噪声稳健性。文献[8]比较了SFCM与FCM的收敛速度;文献[9]详细讨论了SFCM的稳健性,指出SFCM不但能够产生“聚类核”,而且当模糊因子取较大值时,SFCM具有良好的噪声不敏感性。

特征加权FCM(WFCM)有众多版本,这里以Hichem [4]提出的WFCM为基本算法进行讨论。Hichem运用类似FCM中隶属函数的求解方法给出特征加权FCM聚类算法中权函数的一种迭代求解算法,该算法在特征权重的计算过程中赋予不同聚类以不同特征权重,是一种局部特征加权聚类算法。用JWFCM(U,V,W)表示WFCM的目标函数,该算法的目标函数为:

ИJWFCM(U,V,W)=∑Ni=1∑Cj=1∑Mk=1umijwβjkd(xik,vjk)(4)

满足:

ИАCj=1uij=1,uij∈[0,1],1≤i≤N,1≤j≤C

∑Mk=1wjk=1, 1≤j≤C,1≤k≤M

WFCM通过迭代计算式(5)~式(7)来最小化式(4)。

Иvjk=(∑Ni=1umijxik)/∑Ni=1umij(5)

uij=\Mk=1wβjkd(xik,vjk)\〗-1m-1∑Ck=1\Mk=1wβjkd(xik,vlk)\〗-1m-1(6)

wjk = 1∑Ml = 1(Djk/Djl)1β-1(7)И

式中:Djk=∑Ni=1umijd(xik,vjk)。Ы惶娴代优化式(5)~式(7)可实现最小化式(4)。

2 截集型特征加权FCM聚类算法

虽然WFCM具有自动特征选取的优点,但是由于它是在原FCM算法的基础上加了特征权值的迭代计算,所以WFCM的收敛速度较慢,不便于实际应用。而SFCM算法具有收敛速度快和噪声稳健的优点,为此,结合二者的优点,用截集方式对WFCM算法的隶属度值进行修改,提出截集型特征加权FCM(SWFCM)算法。在WFCM算法的基础上,对由式(6)计算所得的隶属度值做如下修改:

对于给定的0

SWFCM算法的描述如下:

(1)选择聚类数C,ε>0,参数β1,参数0

(2) 用式(6)更新隶属度矩阵U′;

(3) 对给定的0

(4) 用式(7)更新特征权矩阵W′;

(5) 用式(5)更新聚类中心矩阵V′,如果V′-V

3 实验结果及分析

为了验证本文提出SWFCM算法的有效性,这里对SFCM,WFCM和SWFCM进行对比仿真实验。在实验中,初始权重取为w(0)jk=1/M,j=1,2,…,C,k=1,2,…,M,最大迭代次数设为200。

3.1 人造数据

人造数据来自文献[10], 记为data1。data1是一个四维空间{X1,X2,X3,X4}中的4类{C1,C2,C3,C4}数据,其中每一类包括100个数据点。类C1和类C2在由特征X1和特征X2构成的子空间中以正态分布的形式形成两类,而特征X3和特征X4是C1和C2的白噪声特征,类C1和类C2在每一维特征上的均值分别为μC1=[0.5,-0.5,0,0]和μC2=[-0.5,-0.5,0,0],标准差为σC1=[0.1,0.2,0.4,0.4]和σC2=[0.1,0.2,0.4,0.4];类似地,类C3和类C4在由特征X2和特征X3构成的子空间以正态分布的形式形成两类,而X1和X4是类C3和类C4的白噪声特征,类C3和类C4在每一维特征上的均值分别为μC3=[0,0.5,0.5,0]和μC4=[0,0.5,-0.5,0],标准差为σC3=[0.4,0.2,0.1,0.4]和σC4=[0.4,0.2,0.1,0.4]。data1在不同特征维数空间上的投影如图1所示。其中图1(a)为data在由特征X1和特征X2构成的子空间中的投影;图1(b)为data1在由特征X2和X3特征构成的子空间中的投影;图1(c)为data1在由特征X1和X3特征构成的子空间中的投影。

图1 在不同特征维数空间中的数据data1

在该实验中,为了测试孤立噪声点对聚类算法的影响,在data1中加入一个孤立噪声点,坐标为(100,100,100,100),所构成的数据记为data2。为避免算法陷入局部极值,用从数据中随机选取聚类中心的方法初始聚类中心100次,三个算法用这相同的100组初始聚类中心各自运行100次选最优结果为最终聚类的结果。在该次实验中,参数Е=0.3,β=3,模糊因子m=5。对加了噪声数据的分类结果如表1所示,用N,T,A分别表示三个算法迭代次数、运行时间和准确率。其中,准确率A定义为A=(∑Cj=1nj)/n( nj表示第jЮ嗾确分类数据的个数)。

由表1可知,WFCM 受噪声影响不能正确选取特征,分类准确率较低,SFCM 和SWFCM受噪声影响较小,准确率都高于WFCM,并且SWFCM能够正确选取数据的相关特征,因此可以获得很高的准确率。

表1 三个算法对data2数据的运行结果

NTA

SFCM150.422 00.780 0

WFCM491.201 00.725 0

SWFCM120.592 00.985 0

3.2 真实数据

Iris数据和Breast-cancer数据来源于UCI repository of machine learning databases[11],数据特性如表2所示。

表2 数据描述

样本数维数类数

Iris15043

Breast-cancer683102

在该实验中,为避免算法陷入局部极值,用从数据中随机选取聚类中心的方法初始聚类中心100次,3个算法用这相同的100组初始聚类中心各自运行100次选最优结果作为最终聚类结果。用N,T,A分别表示3个算法迭代次数、运行时间和准确率,参数α取为0.3,β取值为2,模糊因子m取为2。对Iris数据和Breast-cancer数据的分类结果如表3和表4所示。

表3 三个算法对Iris数据的分类结果

TAN

SFCM50.063 00.893 3

WFCM210.218 00.973 3

SWFCM90.172 00.973 3

由表3可知,尽管WFCM和SWFCM的用时多于SFCM,由于具有自动特征选择能力,WFCM和SWFCM的准确率都高于SFCM;WFCM与SWFCM相比较,SWFCM的迭代次数更少,用时也更少。

表4 三个算法对Breast-cancer数据的分类结果

NTA

SFCM40.156 00.601 8

WFCM290.733 00.787 7

SWFCM70.328 00.944 4

由表4可见,SWFCM的准确率远远高于SFCM和WFCM。从迭代次数和用时来看,WSFCM比WFCM要少得多。

4 结 语

基于特征加权的FCM(WFCM)聚类算法是当前聚类算法研究的热点,WFCM存在的主要缺点是:收敛速度慢,对噪声敏感。考虑到实际工程应用中不可避免会有噪声,所使用的聚类算法必须对噪声不敏感。为此,本文将截集FCM(SFCM)聚类算法和特征加权FCM(WFCM)聚类算法相结合,提出了截集型特征加权模糊C-均值(SWFCM)聚类算法。实验结果表明,SWFCM不仅具有良好的特征选择能力和很强的抗噪声性能,而且具有较高的收敛速度,是一种经济有效、可供选择的聚类算法。

参考文献

[1]CHIEHYUAN Tsai, CHIU Chuang-cheng. Developing a feature weight self-adjustment mechanism for a K-means clustering algorithm[J]. Computational Statistics and Data Analysis, 2008, 52(10): 4658-4672.

[2]JING L, NG M K, HUANG J Z. An Entropy Weighting K-Means Algorithm for Subspace Clustering of High-dimensional Sparse Data[J]. IEEE Trans. on Knowledge and Data Engineering, 2007, 19(8): 1026-1041.

[3]WANG X Z, WANG Y D, WANG L J. Improving fuzzy feature C-means clustering based on feature-weight learning[J]. Pattern Recognition Letters, 2004, 25(10): 1123-1132.

[4]FRIGUIH, NASRAOUI O. Unsupervised learning of pro-totypes and attribute weights[J]. Pattern Recognition, 2004, 37(3): 567-581.

[5]李洁, 高新波, 焦李成. 基于特征加权的模糊聚类新算法[J]. 电子学报, 2006, 34(1): 89-92.

[6]HUNG W L, YANG M S, CHEN D H. Bootstrapping approach to feature-weight selection in fuzzy C-means algorithms with an application in color image segmentation[J]. Pattern Recognition Letters, 2008, 29(9): 1317-1325.

[7]陈新泉. 特征加权的模糊C聚类算法[J]. 计算机工程与设计, 2007, 28(22): 5329-5333.

[8]裴继红, 范九伦, 谢维信. 一种新的高效软聚类算法: 截集模糊C-均值聚类算法[J]. 电子学报,1998, 26(2): 83-86.

[9]YANG Miin-shen, WU Kuo-lung. Alpha-cut implemented fuzzy clustering algorithms and switching regressions[J]. IEEE Trans. on Systems, Man and Cybernetics, Part B, 2008, 38(3): 588-603.

[10]LI Y H, DONG M, HUA J. Localized feature selection for clustering [J]. Pattern Recognition Letters, 2008, 29(1): 10-18.

[11]BLAKE C L, MERZ C J . UCI repository of machine learning Databases[EB/OL]. \. http: //archive. ics. uci. edu/ml/.