模糊C均值聚类算法的改进研究.pdf

第10卷第3期Vol.10No.3
淮阴师范学院学报(自然科学)
2011年6月JOURNALOFHUAIYINTEACHERSCOLLEGE(NaturalScience)Jun.2011

模糊C均值聚类算法的改进研究
贾丙静,王传安,宋雪亚

(安徽科技学院理学院,安徽风阳233100)

摘要:模糊C均值聚类算法(FCM)是一种比较有代表性的模糊聚类算法,主要是通过迭代
更新聚类中心和隶属度矩阵,使目标函数值达到最小.FCM算法还有很多缺陷和不足,其中最
主要的就是选取不同的初始中心,会得到不同的聚类结果,影响到聚类的稳定性和准确率.本
文对要聚类的数据集采用数据分区技术进行预处理,根据物质质心的定义及质心运动原理,计
算每个数据分区的质心做为FCM聚类的初始聚类中心.实验结果表明,改进后的算法FCM能
够降低迭代次数和运行时间,得到比较稳定的聚类结果.
关键词:模糊C均值聚类算法;数据分区;质心
中图分类号:O159文献标识码:A文章编号:1671-6876(2011)03-0226-04

0引言

随着计算机、通信和网络技术的发展,人们被海量信息淹没的同时又面临着知识的贫乏,因此,开始
思考采用一定的方法从蕴含着丰富信息的数据中抽取感兴趣的知识和信息,包括有效的、新颖的、潜在
有用的概念、规律和模式等,这就是数据挖掘.在数据挖掘技术中,聚类分析是其中最主要的研究课题之
一,其主要功能是根据对象的属性,将大规模的数据集合分为由类似的对象组成的多个类.其中,类内具
有最大的相似性,类间具有最小的相似性.
目前,常用的聚类分析方法有划分的方法、层次的方法、基于密度的方法、基于网格的方法、基于模
型的方法和模糊聚类方法.由于在现实生活中,很多对象没有严格的属性,不能把它绝对的划分到某个
类别中,因此,模糊聚类分析成为聚类的研究主流,它得到的是样本属于某个类别的不确定程度,更能客
观的反映真实的世界.模糊C均值聚类算法(FCM)是一种代表性的模糊聚类算法[1,2],但是FCM还有很
多缺陷和不足,其中最主要的就是算法的性能依赖于初始中心的选择,选取不同的初始中心,会得到不
同的聚类结果,影响到聚类的稳定性和准确率.针对上述问题,我们首先对要聚类的数据采用数据分区
技术进行预处理,然后根据物质质心的定义及质心运动原理,计算每个数据分区的质心做为FCM聚类
的初始聚类中心,降低FCM对初始中心的依赖性.
1经典FCM算法

在非监督模式识别领域,FCM聚类算法是应用最广泛的算法之一.Dunn在Ruspini提出模糊划分概
念的基础上,改进传统的硬C均值聚类算法,把其推广到模糊情形,形成FCM算法.Bezdek在其提出的
FCM算法的基础上推广到更一般的形式,就形成了我们今天所看到的经典FCM算法.经典FCM算法的
基本思想是:随机初始化若干个聚类中心,计算样本中的每个数据对聚类中心的隶属度,构成隶属度矩
阵,然后通过若干次的迭代更新聚类中心和隶属度矩阵,使目标函数值达到最小.目标函数如下:
nc
m2
Jm(U,V)=uijdij(1)
j∑=1i∑=1
假设待聚类数据集合X中含有n个对象,其中,m是模糊加权指数,控制算法的柔性,m>1;c表示

收稿日期:2011-02-22
基金项目:安徽省自然科学基金资助项目(KJ2011Z070)
作者简介:贾丙静(1982-),女,山东曹县人,助教,硕士,研究方向为Web日志挖掘等.
第3期贾丙静等:模糊C均值聚类算法的改进研究227

分类数;uij∈[0,1]表示第i个样本点xi属于第j个分类的隶属度;dij表示样本点xi与聚类中心vj的欧

几里德距离V;=狖vi狚(i=1,2,c,)表示聚类中心矩阵,U=狖uij狚表示隶属度矩阵,其中隶属度值uij具
有如下的约束条件:
c

uij=1,i=1,2,3,n,(2)
j∑=1
n

0<uij<n,j=1,2,3,c,(3)
i∑=1

在迭代求Jm(U,V)最小值过程中,可通过(4)、(5)不断的更新隶属度和聚类中心矩阵.
隶属度更新公式为:
1
uij=c(4)
2/(m-1)
(dij/dkj)
k∑=1
聚类中心更新公式为:
n
m
uijxi
i∑=1
vj=n(5)
m
uij
i∑=1
2改进FCM算法

2.1数据分区
在海量高维数据中,统计数据在每一维上的分布特性,根据它的分布特性,可将数据划分为若干个
分布均匀的区域[3-5].划分的基本过程如下:首先,从采集的大量数据中选取一个子数据集做为样本数
据.然后,用直方图分析子数据集中每一维上的分布密度.直方图是表示数据分布变化情况的一种统计
工具,是由若干个高度不等的矩形组成,横轴表示数据类型,纵轴表示分布情况.绘制直方图之前,要统
计数据点中的最大值