MATLAB实现FCM 聚类算法

《MATLAB实现FCM 聚类算法》由会员分享，可在线阅读，更多相关《MATLAB实现FCM 聚类算法（9页珍藏版）》请在装配图网上搜索。

1、本文在阐述聚类分析方法的基础上重点研究FCM聚类算法。FCM算法是一种基于划分的聚类算法，它的思想是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。第1章概述聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。为获得

2、基于划分聚类分析的全局最优结果，则需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。而模糊C均值(FuzzyC-means,FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数

3、的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-GroupsSumofSquaredError成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn10首先将其推广到加权WGSS函数，后来由Bezdek扩展到加权WGSS的无限族，形成了FCM聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。第2章聚类分析方法2-1聚类分析聚类分析就是根据对象的相似性将其分群，聚类是一种无监督学习方法，它不需要先验的分类知识就能发现数据下的隐藏结构。它的目标是要对一个

4、给定的数据集进行划分，这种划分应满足以下两个特性:类内相似性:属于同一类的数据应尽可能相似。类间相异性：属于不同类的数据应尽可能相异。图2.1是一个简单聚类分析的例子。图2.1聚类分析的例子聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。聚类分析是归纳的，不需要事先确定分类

5、的准则来分析数据对象，不考虑己知的类标记。一般情况下，训练数据中不提供类标记，因为不知道从何开始，聚类可以用于产生这种标记。对象根据最大化类内的相似性，最小化类间的相似性的原则进行聚类或分组，它通过一些计算来把观测进行合理的分类，使得同类的观测比较接近，不同类的观测相差较多。所形成的每个簇可看成一个对象类，由它可以导出规则。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。2-2主要聚类算法的分类聚类方法包含很多类型的算法，主要可以分为划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法等几个大类。（1）划分方法给定一个包含n个对象或数据行的数据集，划分方法将数据集

6、划分为k个子集（划分），其中每个子集均代表一个聚类，即将数据分为k组。这些组满足以下要求：1.每组至少应包含一个对象；2每个对象必须只能属于某一组。后一个要求在一些模糊划分方法中可以放宽。给定需要划分的个数k，一个划分方法首先创建一个初始划分，然后利用循环再定位技术，即通过移动不同划分（组）中的对象来改变划分内容。一个好的划分衡量标准通常是使得同一个组中的对象相近”或彼此相关，而不同组中的对象较远”或彼此不同。为获得基于划分聚类分析的全局最优结果，需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid算

7、法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。（2）层次方法层次方法是通过分解所给定的数据对象集来创建一个层次。根据层次分解形成的方式,可以将层次方法分为自下而上和自上而下两种类型。自下而上的层次方法从每个对象均为一个单独的组开始，逐步将这些（对象）组进行合并，直到这些组位于层次顶端或满足终止条件为止。自上而下层次方法从所有均属于一个组的对象开始,每一次循环将组分解为更小的组，直到每个对象构成一组或满足终止条件为止。（3）基于密度的方法大多

8、数划分方法是基于对象间距离进行聚类的，这类方法仅能发现圆形或球状的聚类而较难发现具有任意形状的聚类。而基于密度概念的聚类方法实际上就是不断增长所获得的聚类，直到“邻近”（数据对象或点）密度超过一定域值（如：一个聚类中的点数，或一个给定半径内必须包含至少的点数）为止。这种方法可以用于消除数据中的噪声（异常数据），以及帮助发现任意形状的聚类。常用的基于密度的方法，如k-最近邻方法是根据某个对象与其相邻的k个对象的距离和来判断其是否为异常数据。（4）基于网格的方法基于网格的方法将对象空间划分为有限数目的单元以形成网格结构，所有聚类操作均是在这一网格结构上进行的。这种方法的主要优点是，由于与数据对象个

9、数无关，而仅与划分对象空间的网格数相关，从而执行时间显得相对较快。基于网格的方法主要包括GRIDCLUS,BANG-CLUSTERYSTING,wavecluster等（5）基于模型的方法基于模型方法就是为每个聚类假设一个模型，然后再去发现符合相应模型的数据对象。一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。它采用了标准的统计方法，并考虑了“噪声”或异常数据，可以自动确定聚类个数，因此可以产生具有鲁棒性的聚类方法。还有一些聚类算法是将几种聚类方法的思想结合在一起的,因此有时很难明确界定一个聚类算法究竟属于哪一个聚类方法类别。此外一些应用也需要将多个聚类技术结合起

10、来才能实现其应用目标。第3章模糊聚类算法3-1模糊理论的概述和发展模糊集的理论是美国加利福尼亚大学的控制论专家扎德（L.A.Zadeh）教授首先提出来的，近年来发展很快。1965年，扎德在信息与控制（InformationandControl）杂志上发表了论文“模糊集合”（FuzzySets）。这标志着模糊理论的产生。与其他科学一样，模糊数学也是由于实践的需要产生的，经典数学是以精确性为特征。但是模糊概念（或现象）处处存在，例如，日常生活中的大、小，快、慢，长、短都无法用具体的尺度衡量都属于模糊概念。模糊数学目前正沿着理论研究和应用研究两个方向迅速发展。理论研究主要是经典数学概念的模糊化。由于

11、模糊集自身的层次结构，使得这种理论研究更加复杂，当然也因而更具吸引力。目前己形成了模糊拓扑、模糊代数、模糊分析、模糊测度及模糊计算机等模糊数学分支。应用研究主要是对模糊性的内在规律的探讨，对模糊逻辑及模糊信息处理技术的研究。模糊数学的应用范围己遍及自然科学与社会科学的几乎所有的领域。特别是在模糊控制、模式识别、聚类分析、系统评价、数据库、系统决策、人工智能及信息处理等方面取得了显著的成就。目前，模糊理论方面的专业学术杂志有：FuzzySetsandSystems(模糊集与系统，国际模糊系统协会会刊，德国承办)，模糊系统与数学(中国模糊系统协会会刊，国防科技大学承办)，FuzzyMath(模糊数

12、学杂志，美国)，BUSEFAL濮糊集及其应用研究快报，法国)，IEEETransactionsonFuzzySystem(IEEE模糊系统，美国电气和电子工程师学会主办)。3-2模糊集合对于一个普通的集合A,空间中任一元素x,要么xA要么x电A,二者必居其一。如果利用特征函数法来描述元素属于集合的程度，则对于集合A,其特征函数a(x)可以标记为：“Ax)=1,xeA0,X电A(3.1)从上式可以看出，对于任意给定的xwX都有唯一确定的特征函数a(X)0,1与之对应，因此可以将集合A表示为：R(x):XT0,1(3.2)A其中A(x)是从X到0,1的一个映射，它唯一确定了集合A。对于模糊集合来说

13、，每一个元素都是以一定的程度属于某个集合，也可以同时以不同的程度隶属于几个集合，那么这种处于中介过渡事物对差异双方所具有的倾向性，通常用隶属度函数(MembershipFunction)来描述。隶属度函数是一个表示元素x隶属于集合A的程度的函数，可以认为隶属度函数是传统集合中特征函数的推广。当特征函数a(x)的值域旬0,1二值扩展到0,1区间时，就描述了一个模糊集合。定义2.1：模糊集合：论域X上的模糊集合A由隶属度“A(x)来表征，其中“;(x)在实轴的闭区间0,1上取值，“A(X)的值反应了X中的元素x对于A的隶属程度。模糊集合完全由隶属度函数所刻画。“A(x)的值越接近1,表示x隶属于A

14、的程度很高；吒(x)值越接近于0,表示x隶属于A的程度很低；当“A(x)的值域为0,1二值时,“A)演化为普通集合的特征函数“a(x),A便演化成一个普通集合A。我们可以认为模糊集合是普通集合的一般化。“一(x)对于任给xX，都有唯一确定的隶属函数0,1与之对应:卩一(x):XT0,1(3.3)A即“A(X)是从X到0,1的一个映射，它唯一确定了模糊集合A。3-3模糊聚类传统的聚类分析是一种硬划分，它把每个待识别的对象严格地划分到某类中，具有“非此即彼”的性质，也就是说对于数据空间中的任何元素，或者属于某一类，或者不属于该类，两者必居且仅居其一，因此这种类别划分的界限是分明的。然而在现实世界中

15、的许多实际问题并没有严格的属性，它们在性态和类属方面存在着中介性，具有亦此亦彼”的性质，那么用传统的聚类分析就无法解决这类问题。扎德提出的模糊集理论为这种软划分提供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。由于模糊聚类得到了样本属于各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流。模糊划分的概念最早由Ruspin于1969年提出的提出，利用这一概念人们提出了多种聚类方法。模糊聚类分析按照聚类过程的不同大致可以分为三大类：(1) 基于模糊关系的分类法其中包括谱系聚类算法(又

16、称系统聚类法)、基于等价关系的聚类算法、基于相似关系的聚类算法和图论聚类算法等等。它是研究比较早的一种方法，但是由于它不能适用于大数据量的情况，所以在实际中的应用并不广泛。文献对这方面的研究进行了综述。(2) 基于目标函数的模糊聚类算法该方法把聚类分析归结成一个带约束的非线性规划问题，通过优化求解获得数据集的最优模糊划分和聚类。该方法设计简单、解决问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于计算机实现。因此，随着计算机的应用和发展，基于目标函数的模糊聚类算法已成为聚类分析研究的主流。(3) 基于神经网络的模糊聚类算法它是兴起比较晚的一种算法，主要是采用竞争学习算

17、法来指导网络的聚类过程，可以解决传统的模糊聚类算法在大数据量时的耗时问题。它现在已经成为聚类分析研究的重要组成部分。文献把改进的模糊聚类算法和径向基函数(RBF)神经网络结合起来建模，得到一种映射能力较强的自组织RBF神经网络。文献将模糊聚类结合多层前馈神经网络(MFN)建立了综合神经网络模型(FCMMFN)。文献利用模糊控制策略将算法与经典的Kohonen算法有机地结合起来，使网络性能到了很大改善。文献将模糊推理规则转化为模糊RBF网络模型。3-4模糊C均值算法模糊C均值(FuzzyC-means,FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊

18、聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-GroupsSumofSquaredError)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn10首先将其推广到加权WGSS函数，后来由Bezdek扩展到加权WGSS的无限族，形成了FCM聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。FCM聚类算法目标函数为：minJ(U,Z)=工N工C(u)md2(x,z)m

19、j=ii=1巧ji(3-4)如果P表示每一个样本xj的维数，X=X1,x2,叮是一个PxN的矩阵；N代表样本数目通常表示图像像素数；C表示聚类数目；纺GU(PxNxC)是矢量x，隶属于第i类的隶属度函数，工满足u.G0,1且i，C=i冒1，(八1,2,)Z二zi今,zc是pxC矩阵，uj和zi更新等式分别为：1u=ij工C(d(x,z)/d(x,z)2/(m-1)k=1jijkz=YN(u)mx/工N(u)m,(i=1,2.C)1，=1，j，=1，(3-5)对于每一个模糊隶属度，由mg(1,2)控制模糊度的权重指数；d2(x,z)=11x-zII为jiji相似性测度。其中：P：数据样本维数(灰

20、度图像时为1)；N：像素点数目；x：像素i特征(灰度图像时，表示灰度值);iC：图像分割类别数；u:像素点i属于第j类的隶属度；ijz:第i类聚类中心。i3-4算法步棸(1) 设置目标函数精度*，模糊指数m(m通常取2)，最大迭代次数T；m(2) 初始化模糊聚类中心(3) 由式(3-5)更新模糊划分矩阵U=u和聚类中心Z=zcij若1J(t)J(t-1)|T则结聚类；否则，tJt+1并转到步;m(5)由U=u得到各像素点分类结果。ij图例：图3.1原图像图3.2读入图像的像素信息后显示出来的灰度图像图3.3将像素按灰度值分类后的中间结果图3.4最终结果，它将图片成功地聚为黑、白、深灰和浅灰四类，并且边界十分清楚。