FCM聚类算文 报告

摘要

本文在阐述聚类分析方法的基础上重点研究FCM聚类算法。FCM算法是一种

基于划分的聚类算法，它的思想是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。

This paper describes the basis of cluster analysis methods and focus on the FCM clustering algorithm. FCM algorithm is a clustering algorithm based on division and the idea is to make it to the same cluster is divided into the biggest similarity between the objects, while the minimum similarity between different clusters. Finally, I realize the implementation of image information of the cluster based on MATLAB.

关键字： FCM 聚类算法 MTALAB

目录

第1章 概述.......................................................1 第2章 聚类分析方法...............................................1 2-1 聚类分析...................................................1 2-2 主要聚类算法的分类.........................................2 第3章 模糊聚类算法...............................................4 3-1 模糊理论的概述和发展.......................................4 3-2 模糊集合...................................................4 3-3 模糊聚类...................................................5 3-4 模糊C均值算法.............................................6 3-5、算法步骤...................................................7 第4章 程序代码...................................................7 第5章 实验结果...................................................10 致谢...............................................................12 参考文献...........................................................12

西安电子科技大学课程设计（论文）

第1章、概述

聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。

为获得基于划分聚类分析的全局最优结果，则需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。

而模糊C均值(Fuzzy C-means, FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn[10]首先将其推广到加权WGSS函数，后来由Bezdek扩展到加权WGSS的无限族，形成了FCM聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。

第2章、聚类分析方法

2-1 聚类分析

聚类分析就是根据对象的相似性将其分群，聚类是一种无监督学习方法，它不需要先验的分类知识就能发现数据下的隐藏结构。它的目标是要对一个给定的数据集进行划分，这种划分应满足以下两个特性：①类内相似性：属于同一类的数据应尽可能相似。②类间相异性：属于不同类的数据应尽可能相异。图2.1是一个简单聚类分析的例子。

1

西安电子科技大学课程设计（论文）

图2.1 聚类分析的例子

聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。

聚类分析是归纳的，不需要事先确定分类的准则来分析数据对象，不考虑己知的类标记。一般情况下，训练数据中不提供类标记，因为不知道从何开始，聚类可以用于产生这种标记。对象根据最大化类内的相似性，最小化类间的相似性的原则进行聚类或分组，它通过一些计算来把观测进行合理的分类，使得同类的观测比较接近，不同类的观测相差较多。所形成的每个簇可看成一个对象类，由它可以导出规则。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。

2-2 主要聚类算法的分类

聚类方法包含很多类型的算法，主要可以分为划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法等几个大类。

2

西安电子科技大学课程设计（论文）

（l） 划分方法

给定一个包含n个对象或数据行的数据集，划分方法将数据集划分为k个子集(划分)，其中每个子集均代表一个聚类，即将数据分为k组。这些组满足以下要求：1.每组至少应包含一个对象；2.每个对象必须只能属于某一组。后一个要求在一些模糊划分方法中可以放宽。

给定需要划分的个数k，一个划分方法首先创建一个初始划分，然后利用循环再定位技术，即通过移动不同划分(组)中的对象来改变划分内容。一个好的划分衡量标准通常是使得同一个组中的对象“相近”或彼此相关，而不同组中的对象“较远”或彼此不同。

为获得基于划分聚类分析的全局最优结果，需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。

（2） 层次方法

层次方法是通过分解所给定的数据对象集来创建一个层次。根据层次分解形成的方式，可以将层次方法分为自下而上和自上而下两种类型。自下而上的层次方法从每个对象均为一个单独的组开始，逐步将这些(对象)组进行合并，直到这些组位于层次顶端或满足终止条件为止。自上而下层次方法从所有均属于一个组的对象开始，每一次循环将组分解为更小的组，直到每个对象构成一组或满足终止条件为止。

（3） 基于密度的方法

大多数划分方法是基于对象间距离进行聚类的，这类方法仅能发现圆形或球状的聚类而较难发现具有任意形状的聚类。而基于密度概念的聚类方法实际上就是不断增长所获得的聚类，直到“邻近”(数据对象或点)密度超过一定域值(如：一个聚类中的点数，或一个给定半径内必须包含至少的点数)为止。这种方法可以用于消除数据中的噪声(异常数据)，以及帮助发现任意形状的聚类。

常用的基于密度的方法，如k-最近邻方法是根据某个对象与其相邻的k个对象的距离和来判断其是否为异常数据。

（4） 基于网格的方法

基于网格的方法将对象空间划分为有限数目的单元以形成网格结构，所有聚类操作均是在这一网格结构上进行的。这种方法的主要优点是，由于与数据对象个数无关，而仅与划分对象空间的网格数相关，从而执行时间显得相对较快。基

3

西安电子科技大学课程设计（论文）

于网格的方法主要包括GRIDCLUS, BANG-CLUSTERY, STING, wave cluster等

（5） 基于模型的方法

基于模型方法就是为每个聚类假设一个模型，然后再去发现符合相应模型的数据对象。一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。它采用了标准的统计方法，并考虑了“噪声”或异常数据，可以自动确定聚类个数，因此可以产生具有鲁棒性的聚类方法。

还有一些聚类算法是将几种聚类方法的思想结合在一起的，因此有时很难明确界定一个聚类算法究竟属于哪一个聚类方法类别。此外一些应用也需要将多个聚类技术结合起来才能实现其应用目标。

第3章、 模糊聚类算法

3-1 模糊理论的概述和发展

模糊集的理论是美国加利福尼亚大学的控制论专家扎德(L.A.Zadeh)教授首先提出来的，近年来发展很快。1965年，扎德在《信息与控制》(Information and Control)杂志上发表了论文“模糊集合”(Fuzzy Sets)。这标志着模糊理论的产生。与其他科学一样，模糊数学也是由于实践的需要产生的，经典数学是以精确性为特征。但是模糊概念(或现象)处处存在，例如，日常生活中的大、小，快、慢，长、短都无法用具体的尺度衡量，都属于模糊概念。

模糊数学目前正沿着理论研究和应用研究两个方向迅速发展。理论研究主要是经典数学概念的模糊化。由于模糊集自身的层次结构，使得这种理论研究更加复杂，当然也因而更具吸引力。目前己形成了模糊拓扑、模糊代数、模糊分析、模糊测度及模糊计算机等模糊数学分支。应用研究主要是对模糊性的内在规律的探讨，对模糊逻辑及模糊信息处理技术的研究。模糊数学的应用范围己遍及自然科学与社会科学的几乎所有的领域。特别是在模糊控制、模式识别、聚类分析、系统评价、数据库、系统决策、人工智能及信息处理等方面取得了显著的成就。

目前，模糊理论方面的专业学术杂志有：Fuzzy Sets and Systems(模糊集与系统，国际模糊系统协会会刊，德国承办)，模糊系统与数学(中国模糊系统协会会刊，国防科技大学承办)，Fuzzy Math(模糊数学杂志，美国)，BUSEFAL(模糊集及其应用研究快报，法国)，IEEE Transactions on Fuzzy System(IEEE模糊系统，美国电气和电子工程师学会主办)。 3-2 模糊集合

对于一个普通的集合A，空间中任一元素x，要么x∈A要么xA，二者必居

4

西安电子科技大学课程设计（论文）

其一。如果利用特征函数法来描述元素属于集合的程度，则对于集合A，其特征函数A(x)可以标记为：

A(x)1,xA0,xA (3.1)

从上式可以看出，对于任意给定的xX都有唯一确定的特征函数

A(x){0,1}与之对应，因此可以将集合A表示为：

A(x)：X{0,1} (3.2)

其中A(x)是从X到{0,1}的一个映射，它唯一确定了集合A。

对于模糊集合来说，每一个元素都是以一定的程度属于某个集合，也可以同时以不同的程度隶属于几个集合，那么这种处于中介过渡事物对差异双方所具有的倾向性，通常用隶属度函数（Membership Function）来描述。隶属度函数是一个表示元素x隶属于集合A的程度的函数，可以认为隶属度函数是传统集合中特征函数的推广。当特征函数A(x)的值域有{0,1}二值扩展到[0,1]区间时，就描述了一个模糊集合。

定义2.1：模糊集合：论域X上的模糊集合A由隶属度(x)来表征，其中

AA(x)在实轴的闭区间[0,1]上取值，(x)的值反应了X中的元素x对于A的

A隶属程度。

模糊集合完全由隶属度函数所刻画。(x)的值越接近1，表示x隶属于AA的程度很高；(x)的值越接近于0，表示x隶属于A的程度很低；当(x)的

AA值域为{0，1}二值时，(x)演化为普通集合的特征函数(x)，A便演化成一

AA个普通集合A。我们可以认为模糊集合是普通集合的一般化。

对于任给xX，都有唯一确定的隶属函数(x)[0,1]与之对应：

AA(x)：X[0,1] (3.3)

A即(x)是从X到[0,1]的一个映射，它唯一确定了模糊集合A。 3-3 模糊聚类

传统的聚类分析是一种硬划分，它把每个待识别的对象严格地划分到某类中，具有“非此即彼”的性质，也就是说对于数据空间中的任何元素，或者属于某一类，或者不属于该类，两者必居且仅居其一，因此这种类别划分的界限是分明的。然而在现实世界中的许多实际问题并没有严格的属性，它们在性态和类属方面存在着中介性，具有“亦此亦彼”的性质，那么用传统的聚类分析就无法解决这类问题。

扎德提出的模糊集理论为这种软划分提供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。由于模糊聚类得到了样本属于各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流。

5

西安电子科技大学课程设计（论文）

模糊划分的概念最早由Ruspin于1969年提出的提出，利用这一概念人们提出了多种聚类方法。模糊聚类分析按照聚类过程的不同大致可以分为三大类：

（l） 基于模糊关系的分类法

其中包括谱系聚类算法(又称系统聚类法)、基于等价关系的聚类算法、基于相似关系的聚类算法和图论聚类算法等等。它是研究比较早的一种方法，但是由于它不能适用于大数据量的情况，所以在实际中的应用并不广泛。文献对这方面的研究进行了综述。

（2） 基于目标函数的模糊聚类算法

该方法把聚类分析归结成一个带约束的非线性规划问题，通过优化求解获得数据集的最优模糊划分和聚类。该方法设计简单、解决问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于计算机实现。因此，随着计算机的应用和发展，基于目标函数的模糊聚类算法已成为聚类分析研究的主流。

（3） 基于神经网络的模糊聚类算法

它是兴起比较晚的一种算法，主要是采用竞争学习算法来指导网络的聚类过程，可以解决传统的模糊聚类算法在大数据量时的耗时问题。它现在已经成为聚类分析研究的重要组成部分。

文献把改进的模糊聚类算法和径向基函数(RBF)神经网络结合起来建模，得到一种映射能力较强的自组织RBF神经网络。文献将模糊聚类结合多层前馈神经网络(MFN)建立了综合神经网络模型(FCMMFN)。文献利用模糊控制策略将算法与经典的Kohonen算法有机地结合起来，使网络性能到了很大改善。文献将模糊推理规则转化为模糊RBF网络模型。 3-4 模糊C均值算法

模糊C均值(Fuzzy C-means, FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn[10]首先将其推广到加权WGSS函数，后来由Bezdek扩展到加权WGSS的无限族，形成了FCM聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。

FCM聚类算法目标函数为： mNCminJmU,Zj1ui1ijd2xj,zi （3-4）

6

西安电子科技大学课程设计（论文）

如果p表示每一个样本

xj的维数，

Xx1,x2,...xj,...xN是一个pN矩阵；N表

j示样本数目，通常表示图像像素数；C表示聚类数目；uijUpNC是矢量x隶

C1u1,j1,2,...,Nu0,1ijuiji类的隶属度函数，满属于第足且i1ij；聚类中心2m1Cdxj,zkdCxj,zip1,zZz,z2,...,zki,...uziC1是矩阵，和更新等式分别为： mmNNzuxjj1uij,i1,2,...Cij1ij （3-5）

ij对于每一个模糊隶属度，由

d2m1,控制模糊度的权重指数；

xj,zixzj为相似性测度。

i其中：

pN

数据样本维数（灰度图像时为1）； 像素点数目；

像素i特征（灰度图像时，表示灰度值）； 图像分割类别数；

像素点i属于第j类的隶属度； 第i类聚类中心。

xiCuijzi3-5、算法步骤

Step1：设置目标函数精度，模糊指数m（m通常取2），最大迭代次数Tm； Step2：初始化模糊聚类中心zi； Step3：由式（3-5）更新模糊划分矩阵Step4：若

JtJt1UuijUuij和聚类中心

Zzc Step3；

或cTm则结束聚类；否则，tt1并转

Step5：由所得得到各像素点分类结果。

第4章、程序代码

function [IX2]=fcm(IM); %IM是输入的源图像 %IX2是分类结果 IM=imread('trees.tif');

IM=IM(:,:,1); figure(1)

imshow(uint8(IM))

[maxX,maxY]=size(IM); IM=double(IM);

IMM=cat(4,IM,IM,IM,IM); %初始化聚类中心（4类） cc1=8;

7

西安电子科技大学课程设计（论文）

cc2=80; cc3=160; cc4=230; ttFcm=0;

while(ttFcm<15) ttFcm=ttFcm+1;

c1=repmat(cc1,maxX,maxY); c2=repmat(cc2,maxX,maxY); c3=repmat(cc3,maxX,maxY); c4=repmat(cc4,maxX,maxY); c=cat(4,c1,c2,c3,c4);

ree=repmat(0.000001,maxX,maxY); ree1=cat(4,ree,ree,ree,ree);

distance=IMM-c;

distance=distance.*distance+ree1;

daoshu=1./distance;

daoshu2=daoshu(:,:,1)+daoshu(:,:,2)+daoshu(:,:,3)+daoshu(:,:,4); %计算隶属度u distance1=distance(:,:,1).*daoshu2; u1=1./distance1;

distance2=distance(:,:,2).*daoshu2;

u2=1./distance2;

distance3=distance(:,:,3).*daoshu2; u3=1./distance3;

distance4=distance(:,:,4).*daoshu2; u4=1./distance4; %计算聚类中心z

ccc1=sum(sum(u1.*u1.*IM))/sum(sum(u1.*u1)); ccc2=sum(sum(u2.*u2.*IM))/sum(sum(u2.*u2)); ccc3=sum(sum(u3.*u3.*IM))/sum(sum(u3.*u3)); ccc4=sum(sum(u4.*u4.*IM))/sum(sum(u4.*u4));

tmpMatrix=[abs(cc1-ccc1)/cc1,abs(cc2-ccc2)/cc2,abs(cc3-ccc3)/cc3,abs(cc4-ccc4)/cc4];

pp=cat(3,u1,u2,u3,u4); for i=1:maxX for j=1:maxY

if max(pp(i,j,:))==u1(i,j) IX(i,j)=1;

elseif max(pp(i,j,:))==u2(i,j)

8

西安电子科技大学课程设计（论文）

IX2(i,j)=2;

elseif max(pp(i,j,:))==u3(i,j) IX2(i,j)=3; else

IX2(i,j)=4; end end end

%判结束条件

if max(tmpMatrix)<0.0001 break; else

cc1=ccc1; cc2=ccc2; cc3=ccc3; cc4=ccc4; end

for i=1:maxX

for j=1:maxY if IX2(i,j)==1 IMMM(i,j)=240; elseif IX2(i,j)==2 IMMM(i,j)=160; elseif IX2(i,j)==3 IMMM(i,j)=80; else

IMMM(i,j)=4; end end end

%显示每次聚类分割结果 figure(2);

imshow(uint8(IMMM)); end

for i=1:maxX

for j=1:maxY

if IX2(i,j)==4

IMMM(i,j)=240; elseif IX2(i,j)==3 IMMM(i,j)=160; elseif IX2(i,j)==2 IMMM(i,j)=80; else

9

西安电子科技大学课程设计（论文）

IMMM(i,j)=8; end end end

%显示最终分类结果 IMMM=uint8(IMMM); figure(3); imshow(IMMM); end

第5章、实验结果

图5.1

10

西安电子科技大学课程设计（论文）

图 5.2

图 5.3

11

西安电子科技大学课程设计（论文）

图 5.4

图5.1是原图像，图5.2是读入图像的像素信息后显示出来的结果，图53是将像素按灰度值分类后的中间结果，图5.4是最终结果，它将图片成功地聚为黑、白、深灰和浅灰四类，并且边界十分清楚。

致谢

在此我非常要感谢的是我的指导老师王爽副教授，同时我还要感谢帮助过我的同学，没有他们的帮助我不可能完成这样顺利，谢谢！

参考文献

[1] 冈萨雷斯.数字图像处理. 电子工业出版社.2003 [2] 边肇琪、张学工. 模式识别. 清华大学出版社.2007

12