FCM聚类算法

课程设计报告设计题目：FCM聚类算法学院：电子工程学院专业：智能科学与技术班级：*********学号：&&&&&&&&姓名：^^^^^^电子邮件：$$$$$$$$$$$$$$$$$日期：2011年12月成绩：指导教师：()()()摘要本文在阐述聚类分析方法的基础上重点研究FCM聚类算法。FCM算法是一种基于划分的聚类算法，它的思想是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。ThispaperdescribesthebasisofclusteranalysismethodsandfocusontheFCMclusteringalgorithm.FCMalgorithmisaclusteringalgorithmbasedondivisionandtheideaistomakeittothesameclusterisdividedintothebiggestsimilaritybetweentheobjects,whiletheminimumsimilaritybetweendifferentclusters.Finally,IrealizetheimplementationofimageinformationoftheclusterbasedonMATLAB.关键字：FCM聚类算法MTALAB目录第1章概述.......................................................1第2章聚类分析方法...............................................12-1聚类分析...................................................12-2主要聚类算法的分类.........................................2第3章模糊聚类算法...............................................43-1模糊理论的概述和发展.......................................43-2模糊集合...................................................43-3模糊聚类...................................................53-4模糊C均值算法.............................................63-5、算法步骤...................................................7第4章程序代码...................................................7第5章实验结果...................................................10致谢...............................................................12参考文献...........................................................12西安电子科技大学课程设计（论文）1第1章、概述聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。为获得基于划分聚类分析的全局最优结果，则需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。而模糊C均值(FuzzyC-means,FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-GroupsSumofSquaredError)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn[10]首先将其推广到加权WGSS函数，后来由Bezdek扩展到加权WGSS的无限族，形成了FCM聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。第2章、聚类分析方法2-1聚类分析聚类分析就是根据对象的相似性将其分群，聚类是一种无监督学习方法，它不需要先验的分类知识就能发现数据下的隐藏结构。它的目标是要对一个给定的数据集进行划分，这种划分应满足以下两个特性：①类内相似性：属于同一类的数据应尽可能相似。②类间相异性：属于不同类的数据应尽可能相异。图2.1是一个简单聚类分析的例子。西安电子科技大学课程设计（论文）2图2.1聚类分析的例子聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。聚类分析是归纳的，不需要事先确定分类的准则来分析数据对象，不考虑己知的类标记。一般情况下，训练数据中不提供类标记，因为不知道从何开始，聚类可以用于产生这种标记。对象根据最大化类内的相似性，最小化类间的相似性的原则进行聚类或分组，它通过一些计算来把观测进行合理的分类，使得同类的观测比较接近，不同类的观测相差较多。所形成的每个簇可看成一个对象类，由它可以导出规则。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。2-2主要聚类算法的分类聚类方法包含很多类型的算法，主要可以分为划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法等几个大类。西安电子科技大学课程设计（论文）3（l）划分方法给定一个包含n个对象或数据行的数据集，划分方法将数据集划分为k个子集(划分)，其中每个子集均代表一个聚类，即将数据分为k组。这些组满足以下要求：1.每组至少应包含一个对象；2.每个对象必须只能属于某一组。后一个要求在一些模糊划分方法中可以放宽。给定需要划分的个数k，一个划分方法首先创建一个初始划分，然后利用循环再定位技术，即通过移动不同划分(组)中的对象来改变划分内容。一个好的划分衡量标准通常是使得同一个组中的对象“相近”或彼此相关，而不同组中的对象“较远”或彼此不同。为获得基于划分聚类分析的全局最优结果，需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。（2）层次方法层次方法是通过分解所给定的数据对象集来创建一个层次。根据层次分解形成的方式，可以将层次方法分为自下而上和自上而下两种类型。自下而上的层次方法从每个对象均为一个单独的组开始，逐步将这些(对象)组进行合并，直到这些组位于层次顶端或满足终止条件为止。自上而下层次方法从所有均属于一个组的对象开始，每一次循环将组分解为更小的组，直到每个对象构成一组或满足终止条件为止。（3）基于密度的方法大多数划分方法是基于对象间距离进行聚类的，这类方法仅能发现圆形或球状的聚类而较难发现具有任意形状的聚类。而基于密度概念的聚类方法实际上就是不断增长所获得的聚类，直到“邻近”(数据对象或点)密度超过一定域值(如：一个聚类中的点数，或一个给定半径内必须包含至少的点数)为止。这种方法可以用于消除数据中的噪声(异常数据)，以及帮助发现任意形状的聚类。常用的基于密度的方法，如k-最近邻方法是根据某个对象与其相邻的k个对象的距离和来判断其是否为异常数据。（4）基于网格的方法基于网格的方法将对象空间划分为有限数目的单元以形成网格结构，所有聚类操作均是在这一网格结构上进行的。这种方法的主要优点是，由于与数据对象个数无关，而仅与划分对象空间的网格数相关，从而执行时间显得相对较快。基西安电子科技大学课程设计（论文）4于网格的方法主要包括GRIDCLUS,BANG-CLUSTERY,STING,wavecluster等（5）基于模型的方法基于模型方法就是为每个聚类假设一个模型，然后再去发现符合相应模型的数据对象。一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。它采用了标准的统计方法，并考虑了“噪声”或异常数据，可以自动确定聚类个数，因此可以产生具有鲁棒性的聚类方法。还有一些聚类算法是将几种聚类方法的思想结合在一起的，因此有时很难明确界定一个聚类算法究竟属于哪一个聚类方法类别。此外一些应用也需要将多个聚类技术结合起来才能实现其应用目标。第3章、模糊聚类算法3-1模糊理论的概述和发展模糊集的理论是美国加利福尼亚大学的控制论专家扎德(L.A.Zadeh)教授首先提出来的，近年来发展很快。1965年，扎德在《信息与控制》(InformationandControl)杂志上发表了论文“模糊集合”(FuzzySets)。这标志着模糊理论的产生。与其他科学一样，模糊数学也是由于实践的需要产生的，经典数学是以精确性为特征。但是模糊概念(或现象)处处存在，例如，日常生活中的大、小，快、慢，长、短都无法用具体的尺度衡量，都属于模糊概念。模糊数学目前正沿着理论研究和应用研究两个方向迅速发展。理论研究主要是经典数学概念的模糊化。由于模糊集自身的层次结构，使得这种理论研究更加复杂，当然也因而更具吸引力。目前己形成了模糊拓扑、模糊代数、模糊分析、模糊测度及模糊计算机等模糊数学分支。应用研究主要是对模糊性的内在规律的探讨，对模糊逻辑及模糊信息处理技术的研究。模糊数学的应用范围己遍及自然科学与社会科学的几乎所有的领域。特别是在模糊控制、模式识别、聚类分析、系统评价、数据库、系统决策、人工智能及信息处理等方面取得了显著的成就。目前，模糊理论方面的专业学术杂志有：FuzzySetsandSystems(模糊集与系统，国际模糊系统协会会刊，德国承办)，模糊系统与数学(中国模糊系统协会会刊，国防科技大学承办)，FuzzyMath(模糊数学杂志，美国)，BUSEFAL(模糊集及其应用研究快报，法国)，IEEETransactionsonFuzzySystem(IEEE模糊系统，美国电气和电子工程师学会主办)。3-2模糊集合对于一个普通的集合A，空间中任一元素x，要么x∈A要么xA，二者必居西安电子科技大学课程设计（论文）5其一。如果利用特征函数法来描述元素属于集合的程度，则对于集合A，其特征函数()Ax可以标记为：1,()0,AxAxxA(3.1)从上式可以看出，对于任意给定的xX都有唯一确定的特征函数(){0,1}Ax与之对应，因此可以将集合A表示为：(){0,1}AxX：(3.2)其中()Ax是从X到{0,