一种加权模糊C均值聚类算法及其在图像分割中的应用

薛艳锋　刘继华　高永强　高志娥　武彩红

(吕梁学院计算机科学与技术系　山西 吕梁 033000)



一种加权模糊C均值聚类算法及其在图像分割中的应用

薛艳锋刘继华高永强高志娥武彩红

(吕梁学院计算机科学与技术系山西 吕梁 033000)

摘要现有的加权模糊C均值聚类算法中，属性加权是一个不断迭代、重复计算的过程，费时费力。针对这种情况，提出Fisher线性判别率进行属性加权。算法首先直接计算每一维属性对模糊聚类的贡献度，其次对所有属性的贡献度进行归一化处理然后加权聚类。在人工和实际数据集所做实验表明：该算法在提高聚类速度的同时，聚类效果上也优于其他同类加权模糊C均值聚类算法。

关键词模糊C均值聚类Fisher线性判别率属性加权分配系数划分熵隶属度彩色图像分割颜色空间

0引言

数据聚类是通过分类的方法把相似的数据元素分成不同的子集，让在同一个子集中的数据元素具有相似的属性，不同子集中的数据元素具有相异的属性的过程[1]。依据数据聚类的方式，可以将数据聚类分为硬聚类和模糊聚类(也称为软聚类)两种。在硬聚类中，数据元素被划分成不同的类，其中每个数据元素只能属于同一个类；在模糊聚类中，数据元素可以属于多个类，且每个数据元素都与每个类存在着对应的隶属度以表明数据元素和一个特定的类之间的关联强度。就模糊方法而言，在不同聚类中的隶属度是相互关联的，同时硬聚类也可以看成是模糊聚类的一个特例[2]。

模糊C-均值聚类(FCM)算法应用最广，它的模糊性允许一个数据元素属于2个或2个以上的聚类(通过隶属度体现)。然后不断优化各个数据元素的隶属度以及聚类中心达到数据聚类效果最优的目的[3,4]。具体做法是将一组有限的数据元素集合X={x1,…,xn,…,xN}聚集为C个模糊聚类并使目标函数最小化：

(1)

其中：m为模糊器，它能影响每个数据隶属度的模糊性；unc是数据元素xn与第c个聚类相对应的隶属度；‖xn-vc‖2为数据元素xn与对应的聚类中心vc之间的欧式距离。每个数据元素包含D个属性F={f1,…,fd,…,fD}，即每个数据元素可表示为xn=(xn1,…,xnd,…,xnD)，其中xnd是数据元素xn在d维属性上的映射。隶属度unc以及聚类中心vc的迭代公式如下：

(2)

(3)

终止条件为：

(4)

其中，ε为终止准则；k为迭代次数。详细步骤如下：

(1) 初始化U=[unc]矩阵，U(0);

(2) 在第k次迭代时，通过U(k)计算聚类中心V(k)=[vc]，如式(3)；

(3) 更新U(k)为U(k+1)，如式(2)；

(4) 如果‖U(k+1)-U(k)‖<ε,算法结束，否则，跳转至第(2)步；

由于各个属性对聚类的贡献程度不等，所以需要为各个属性赋予对应的权重[5-8]，文献[9]采用的Bootstrap方法证明了属性加权对聚类效果作用明显。

Bootstrap方法需要重复选取不断调整属性权重直到聚类结束，或者需要通过计算大量的属性加权最后求取平均值。本文采用基于Fisher线性判别率的方法无需迭代直接计算各属性权重，在减少迭代次数的基础上提高了聚类效果。

1基于Fisher准则的属性加权模糊C均值聚类

1.1Fisher线性判别率

Fisher准则[10]的基本方法是，对于一个包含N个D维数据元素的集合Ω，假设有N1个数据元素属于子集Ω1，N2个数据元素属于子集Ω2。为了在投影方向y=WTX上使两个子集的数据元素分得更开，每一个子集的数据元素聚得更紧，需要寻找W向量，使得Fisher准则函数J(W)值尽可能大。

(5)

(6)

(7)

(8)

(9)

Jfisher就是Fisher线性判别率，值越大，说明该维属性对聚类的影响越明显，应该赋予更大的加权系数。

1.2基于Fisher准则的属性加权模糊C均值聚类

本文所提算法就是把Fisher线性判别率准则运用于模糊C均值聚类算法，步骤如下：

(1) 选取一个整数c(2≤c≤N-1)和一个阈值ε(ε=1e-5)。初始化模糊划分矩阵U，得到取值为0到1的矩阵隶属度元素。

(2) 依据式(3)计算vc(1≤c≤C)。

(3) 通过模糊划分矩阵U的最大值，指派对应数据元素属于C个聚类中的某一类。其次，通过Fisher线性判别率计算各个属性分量在聚类中的贡献度Jfisher，进而计算出各个属性权重W′：

(10)

(4) 依据公式：

(11)

(12)

更新模糊划分矩阵U。

(5) 计算目标函数

(13)

(6) 如果相邻两次的差值小于阈值ε，算法结束，否则，转到第(2)步。

2实验结果

2.1度量标准

聚类有效性函数[11]主要从不同方面衡量聚类的效果。近来十几年，出现了诸多的聚类有效性函数作为度量标准，其中最重要的两种度量标准分别针对数据元素集合的模糊划分以及数据元素集合的几何结构。

针对数据元素集合模糊划分标准的主要思想是：划分的模糊度越小，聚类效果越好。这类度量标准的两个代表函数分别是分配系数Vpc[12]以及划分熵Vpe[11]：

(14)

(15)

2.2实验1人造数据集

图1　″○″代表第一聚类以及″*″代表第二聚类

聚类算法FCMBFWFCMFFWFCM迭代次数15.72096.56015.340分配系数(PC)0.7710.7890.837划分熵(PE)0.5300.4940.393目标函数(OF)139.688139.482113.050聚类中心距离误差0.5870.7060.483最后属性加权(0.50,0.50)(0.40,0.60)(0.06,0.94)

图2　″○″代表第一聚类以及″*″代表第二聚类

聚类算法FCMBFWFCMFFWFCM迭代次数17.28099.12013.500分配系数(PC)0.7450.7630.828划分熵(PE)0.5770.5480.419目标函数(OF)121.141120.04490.397聚类中心距离误差0.2690.3970.334最后属性加权(0.50,0.50)(0.41,0.59)(0.07,0.93)

2.3实验2标准数据集

继续选择两个著名的真实数据集Iris和Wine进行测试，情况描述见表3所示。

表3　两类真实数据集

通过与上述两种算法的比较，我们得到实验结果如表4、表5所示。从表4中，可以清楚地看到：在迭代次数、分配系数(PC)、划分熵(PE)度量标准上，本文所提算法都取得最好的效果。而在目标函数(OF)度量标准上，本文所提方法略逊于BFWFCM算法，但优于MFC算法。从表5中，可以清楚地看到：在迭代次数上，本文所提算法略逊于MFC算法，但明显优于BFWFCM算法；在分配系数(PC)、划分熵(PE)度量标准上，本文所提方法略优于上述两种算法。而在目标函数(OF)度量标准上，本文所提算法显著优于其他两个算法，得到最好的聚类效果。

表4　Iris数据集的聚类结果比较

表5　Wine数据集的聚类结果比较

2.4实验3属性加权测试集

这个实验主要用来测试描述每个数据元素的属性在聚类中的贡献度，依据属性加权显示。文献[6]提出一种基于高斯混合分布的属性加权测试集，每一个属性加权测试集包含50个数据元素，每一数据元素有5个属性组成，其中2个属性相关，与剩余3个属性无关。两个属性的相关值通过K(K=2)分量高斯混合模型(参数：均值分别为μ1=(0,0),μ2=(0,3)，协方差矩阵都等于2维单位矩阵，即∑1=∑2=I2)得到。剩余三个属性的相关值通过随机变量(参数：均值为0，方差为1)得到。图3描述了这两个相关属性的分布情况。

图3　″*″代表第一聚类数据元素以及″○″代表第二聚类数据元素

3种算法分别对这个属性加权测试集进行聚类，聚类效果见表6所示。需要补充的是：在最后的属性加权里，两个相关属性加权在前，三个无关属性在后。

表6　属性加权测试集的聚类结果比较

这部分只针对属性加权的结果。由图3可知：第一相关属性在聚类上不起作用，相反，第二相关属性在聚类上起决定性作用。就这点而言，本文方法产生的加权结果表现最为突出。后三个无关属性与第一相关属性作用相同，所以加权也应该相同且接近为0。同时不难发现，FCM算法、BFWFCM算法得到的属性加权不符合实际。其他四个度量标准在此不在赘述。

通过以上三个实验结果可以看出，在上表所列的四个衡量系数以及属性加权上，本文所提算法总体上要显著优于模糊C均值聚类算法以及文献[9]提出的加权模糊C均值聚类算法。

2.5实验4彩色图像集

本文所提的属性加权聚类算法中，参数设置如下：(1) 模糊度系数m=2；(2) 终止准则ε=0.00001；(3) 采取文献[9]设置的参数系数。在图像树中，c=3；在图像裤子中，c=4，以及在图像衣服中，c=3；(4) 设置Bootstrap方法中的B=200。此外，本文还选取了另外一幅图像，奶牛作为实验图像，它取c=3，如图7所示。通常，原始图像的表达空间是RGB颜色空间，但是在许多彩色图像的应用领域研究表明[13]：跟RGB彩色空间相比，把图像映射到CIELAB彩色空间更有利于对图像进行处理。最后，这些图像的分割结果分别见图4-图7所示。

图4　树

图5　裤子

图6　衣服

图7　奶牛

从图4实验结果明显看出，Bootstrap方法把天空分割成两部分，而把目标对象与土坡当成同一对象进行了分割。而本文所提方法与经典FCM方法却分别把天空，树(目标对象)，土坡分别分割出来，但就目标对象(树)而言，本文所提算法得到了目标对象更加具体，即树干和树枝有更加明显的区分。

从图5的实验结果可以明显看出，Bootstrap方法把裤子上的小黑色区域分割成两部分，不符合原图像。而本文所提方法与经典FCM方法效果相当。

从图6的实验结果可以明显看出，Bootstrap方法没能把上面腰部那条红色的带子分割成功。而本文所提方法与经典FCM方法却能清楚地分割成功，但从颜色深浅来说，本文方法明显优于经典FCM方法。

从图7的实验结果可以明显看出，经典FCM方法把奶牛与自己在草地的影子分割为一个整体，这明显是不准确的。而Bootstrap方法与本文所提方法却清楚地把奶牛分割成一个完整的整体。但是，Bootstrap方法由于受到光照的影响，把奶牛大腿部分的阴影部分分割到背景上去，而本文所提方法分割得到的奶牛更完整一些，说明光照对本文所提算法的分割影响较小。同时，通过图7与图4-图6的比较可知，这幅图像的像素点总数平均是它们的9倍左右，同时仍然取得明显的效果，说明本文所提算法在图像的扩展方面也具有良好的性能。此外，从实验过程中发现，Bootstrap方法分割图像所耗时间远远大于经典FCM算法与本文所提算法，即时间复杂度较大，但它不是本文讨论的重点，所以这里不再赘述。

3结语

由实验结果可知，本文所提算法在保证模糊C均值聚类算法优点的同时，提高了聚类效果与图像分割的效果。今后将继续研究模糊聚类在图像分割中的应用，同时着重挖掘图像的属性信息，比如考虑图像的空间信息、多张图像的共有属性等。

参考文献

[1] 常茜茜,张月琴.一种基于划分的混合数据聚类算法[J].计算机应用与软件,2014,31(6):154-157.

[2] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.

[3] 李丽娟,唐文纪.基于人工免疫网络和模糊C-均值聚类的入侵检测方法[J].计算机应用与软件,2011,28(3):282-284,299.

[4] 陈志飞,时宏伟,吕学斌,等.基于均值漂移和模糊C均值聚类的图像分割算法[J].计算机应用与软件,2013,30(11):13-17.

[5] Huang J Z,Ng M K,Hongqiang R,et al.Automated variable weighting in k-means type clustering[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2005,27(5):657-668.

[6] Tsai C Y,Chiu C C.Developing a feature weight self-adjustment mechanism for a K-means clustering algorithm[J].Computational Statistics & Data Analysis,2008,52(10):4658-4672.

[7] Lim Y B,Park Y J,Huh M H.D-optimality criterion for weighting variables in K-means clustering[J].Journal of the Korean Statistical Society,2009,38(4):391-396.

[8] Liping J,Ng M K,Huang J Z.An Entropy Weighting K-means Algorithm for Subspace Clustering of High-Dimensional Sparse Data[J].Knowledge and Data Engineering,IEEE Transactions on,2007,19(8):1026-1041.

[9] 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.

[10] 边肇祺,张学工.模式识别[M].2版.北京:清华大学出版社,2000:87-90.

[11] Wang X,Wang Y,Wang L.Improving fuzzy c-means clustering based on feature-weight learning[J].Pattern Recognition Letters,2004,25(10):1123-1132.

[12] Bezdek J C.Cluster Validity with Fuzzy Sets[J].Journal of Cybernetics,1973,3(3):58-73.

[13] Kim D,Lee K,Lee D.A novel initialization scheme for the fuzzy c-means algorithm for color clustering[J].Pattern Recognition Letters,2004,25(2):227-237.

收稿日期：2015-01-21。吕梁学院校内自然科学基金项目(zrxn 201308)。薛艳锋，讲师，主研领域：数据挖掘。刘继华，副教授。高永强，讲师。高志娥，助教。武彩红，助教。

中图分类号TP311

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.07.062

A WEIGHTED FUZZY C-MEANS CLUSTERING ALGORITHM AND ITS APPLICATION IN IMAGE SEGMENTATION

Xue YanfengLiu JihuaGao YongqiangGao ZhieWu Caihong

(DepartmentofComputerScienceandTechnology,LvliangUniversity,Lvliang033000,Shanxi,China)

AbstractIn existing weighted fuzzy C-means clustering algorithm, attribute weighting is a process of ongoing iteration and repeated calculation, which is time-consuming and laborious. In view of this situation, we proposed to use Fisher linear discriminant rate in attribute weighting. First, the algorithm calculates directly the contribution degree of every dimension attribute on fuzzy clustering; secondly it makes the normalisation processing on the contribution degrees of all attributes followed by weighted clustering. The experiments carried out on artificial and real datasets show that while improving the clustering speed, the method has the superiority over other similar weighted fuzzy C-means clustering algorithm in terms of clustering effect.

KeywordsFuzzy C-means clusteringFisher’s linear discriminantAttribute weightingDistribution coefficient partitionEntropyDegree of membershipColour image segmentationColour spaces