基于模糊聚类算法中FCM算法的.ppt

1、基于模糊聚类算法中FCM算法的改进研究,Yunnan university Department of Computer Science Lei Zhiming 2008-05-13,2020/8/20,目录,聚类分析的介绍 模糊聚类算法 FCM算法的介绍 模糊c均值类型聚类算法研究现状 对FCM算法改进的可行性 对FCM算法改进的想法 参考文献,2020/8/20,聚类分析的介绍,随着数据挖掘研究领域技术的发展,作为数据挖掘主要方法之一的聚类算法,也越来越受到人们的关注。聚类分析是数据挖掘研究和应用中一个重要的部分。 聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每

2、个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。 在多媒体信息检索及数据挖掘的过程中,聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。,2020/8/20,聚类分析的介绍聚类的要求,数据挖掘的聚类一般是针对大数据集而言的,因此在数据挖掘中聚类方法的比较应该满足以下要求: 1）可伸缩性。算法在满足小数据集的同时能否满足大数据集、高复杂性、高增量的要求。 2) 处理不同类型属性的能力。算法在处理数值类型数据的同时能否处理其他的数据类型,如二元类型、分类/标称型、序数型及混合数据类型。 3) 发现任意形状的类。 4) 用于决定输入参数的领域知识最小化

3、。 5) 处理噪声数据的能力。 6) 对输入数据顺序的敏感性。算法能否与输入顺序无关。 7) 处理高维数据的能力。算法在应付低维数据的同时能否处理高维空间的非常稀疏、高度偏斜的数据。,2020/8/20,聚类分析的介绍聚类算法分类,聚类算法的分类有多种标准，其中有按聚类标准，聚类处理的数据类型，聚类尺度，以及聚类分析的思路等。这里我们按照聚类基本思想来划分，将其分为五类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法,如下页图所示。,2020/8/20,聚类分析的介绍聚类算法分类,聚类分类图：,2020/8/20,模糊聚类算法,传统模糊聚类方法分

4、为两类:一类是模糊等价矩阵动态聚类法,另一类是模糊ISODATA聚类方法。第一类分类算法主要有传递闭包法、最大树法、模糊C - 均值法( Fuzzy C - Means,FCM)等。我主要要研究的主要是FCM算法上的改进算法，所以先介绍模糊相似矩阵和模糊等价关系的概念4。,2020/8/20,模糊聚类算法,在上述定义中：由模糊相似关系确定的矩阵是模式相似矩阵, 由模糊等价关系确定的矩阵是模糊等价矩阵。 下面简单说下从模糊相似矩阵出发, 求传递闭包或模糊等价矩阵来进行模糊聚类分析方法的步骤： 确定将要进行聚类分析的对象的统计指标; 为便于比较和分析, 将统计指标的数据标准化, 并将标准化的数据压

5、缩到0,1闭区间,方法如下 其中Xij 是统计指标原始数据, 第j 列 是统计指标原始数据的最小值, 是 统计指标原始数据的最大值。,2020/8/20,模糊聚类算法,计算被分类对象间相似程度的统计量作为矩阵的一个元素, 从而确定U 上的一个相似关系R。计算被分类对象间相似程度的统计量的方法有很多, 常用的有欧式距离法、数量积法、几何平均最小方法、算术平均最小方法、夹角余弦方法等方法。本文在计算被分类对象间相似程度时主要使用夹角余弦方法, 即:,2020/8/20,模糊聚类算法,如果模糊相似关系R 是模糊等价关系, 则可直接进行聚类分析, 否则, 转到下一步; 改造模糊相似关系使其成为模糊等价

6、关系, 方 法是将模糊相似矩阵循环自乘, 如: RR=R2, R2R2 =R4,直到满足R2k=Rk 为止, 则Rk 便是改造R 所得的一个模糊等价关系, 然后在此基础上再进行模糊聚类分析。,2020/8/20,模糊聚类算法,在这里我们给出几个用到的定义： 定义1:设X = ( x1 , x2 , , xn )是来自统计样本的全部对象的集合, 每个xi 有m 个属性, 以( xi1 , xi2 , ,xim )来表示xi 的一个划分,构成n m 矩阵,称为初始数值矩阵。 定义2:对X = (x1 , x2 , , xn )中任意两个不同的对象xi、xj ( ij) ,以rij表示xi 与xj

7、间的相似程度, rij称作相似系数。 定义3:设U、V 为两个论域,若对P ( x, y) U V,指定其对R 的隶属度(或隶属函数)R ( x, y) :U A 0, 1 ,称U、A上的模糊集R 为从U到V 的一个模糊关系。 定义4:设U、A 均为有限论域,则所有的rij构成模糊关系R,用一个矩阵来表示,记作R = ( rij ) n m ,其中,矩阵R 的元素满足: 0ril 1 (0i, j1) ,矩阵R 称Fuzzy(模糊)矩阵。,2020/8/20,FCM算法的介绍,为了优化聚类目标函数，人们提出了现在相当流行和应用广泛的模糊c均值（FCM，Fuzzy c-means）聚类算法。该算

8、法是从硬c均值（HCM,Hard c-means）聚类算法发展而来的。 以下给出FCM算法和HCM算法步骤：,2020/8/20,FCM算法的介绍,2020/8/20,FCM算法的介绍,2020/8/20,FCM算法的介绍,2020/8/20,模糊c均值类型聚类算法研究现状,鉴于模糊c均值聚类算法的高效性和广泛应用，人们在此基础上进行了发展和深化，提出了许多模糊c均值类型的算法。可以从一下三个方面进行描述。 目标函数的演化 算法的实现途径 有效性度量方式,2020/8/20,模糊c均值类型聚类算法研究现状,由模糊聚类的数学模型可以知道，对于一组给定的样本集，模糊聚类分析可以很容易获得它的一个模

9、糊划分：U=uik|1=i=c;1=k=n.但是，要保证划分的有意义，则需要依据为题的需要定义合适的划分准则。 我们可以从五个参量的角度来概述目标函数的演化过程： 1：对模糊划分矩阵U的研究 2：对相似性准则D（.）的研究 3：对聚类原型P的研究 4：对加权指数m的研究 5：对各种数据集X聚类的研究,2020/8/20,模糊c均值类型聚类算法研究现状,有了聚类准则函数，接下来就是如何优化目标函数以获得最佳聚类的问题了，即研究算法的实现途径。现有的实现研究途径主要分为基于交替优化、神经网络和进化运算等三类方法。 1：基于交替优化的实现 2：基于神经网络的实现 3：基于进化计算的实现,2020/8

10、/20,模糊c均值类型聚类算法研究现状,对于给定的数据集，首先判断有无聚类结构，这就属于聚类趋势研究的课题，如果已经确认有聚类结构则需要用算法来确定这些结构，这属于聚类分析研究的课题，得到聚类结构以后，则需要分析聚类结果的合理性，这属于聚类有效性研究的课题。对聚类分析而言，有效性问题又可以转化为最佳类别数c的决策。 历史上有关聚类有效性问题的研究大都是基于HCM,FCM算法的，现有的聚类有效性函数按定义方式分为：基于数据集模糊划分的，基于数据集几何结构的和基于数据集统计信息的三类其理论基础和提点如表所示 ：,2020/8/20,模糊c均值类型聚类算法研究现状,三种聚类有效性函数的特点比较,20

11、20/8/20,对FCM算法改进的可行性,从模糊聚类的现状来看，人们已经提出了许多算法，这就说明了现有算法还存在种种不尽人意的地方。在这种多算法当中，以模糊c均值类型算法理论最为完善，但是该算法仍不失无懈可击的，还遗留有很多问题等待解决。例如：,2020/8/20,2020/8/20,对FCM算法改进的可行性,针对以上的问题，为了晚上现有的FCM类型算法，优化算法准则函数的几个重要参数，扩展算法的应用范围。具体可以 1：优化加权指数m的选择 2：聚类原型参数的最有初始化 3：结合聚类趋势、聚类分析和有效性三种手段构造一套完整的分析方法，不进要回答数据集中的无聚类结构，并确定这些结构，还要分析聚

12、类的结果是否有效。 4：研究针对特殊类型数据的FCM算法，拓展该算法的应用范围。,2020/8/20,对FCM算法改进的想法,针对FCM算法我心里有两种想法， 一种是针对算法本身，对算法的内容进行分析，将其分类，比如对于数据类型的分类，对对应的数据类型运用相应的数据处理的函数，运用c语言中函数重构的性质来进行各个函数的运算。另外就是将聚类算法中的基于密度或者是基于网格的某一种来确定初始聚类核心，或者是可以初始判断聚类核心，从而可以减小模糊聚类的运算次数，从而减小运算量。 另外一种就是感觉现在的FFCM算法还有可以改进的地方，针对现在运用的快速FCM算法进行改进。,2020/8/20,参考文献,

13、【 1 】Scholkopf B ,Smola A ,Muller K. Nonlinear component analysisas a kernel eigenvalue problemJ . Neural Computation ,1999 ,10 (5) :1299 - 1319. 【2】J C Bezdek. A physical interp retation of fuzzy ISODATA J . IEEE Trans, 1976, SMC - 6 (2) : 387390 【3】Bezdek. Pattern Recognition with Fuzzy Objective

14、Function Algorithms. New York: Plenum Press, 1981 【4】张铃,张钹. 模糊商空间理论. 软件学报, 2003,14(4) 【5】高新波，模糊聚类分析及其应用，西安电子科技大学出版社,2020/8/20,THANKS,2020/8/20,基于进化计算的实现,三种模糊聚类实现途径的比较,2020/8/20,基于神经网络的实现,两种聚类神经网络的比较,2020/8/20,对聚类原型P的研究,几种原型的特点比较,2020/8/20,对相似性准则D（.）的研究,常见的距离函数,2020/8/20,对模糊划分矩阵U的研究,四种空间划分概念的比较,距离法,海明距离,欧氏距离,模糊相似矩阵建立方法,相似系数法 -夹角余弦法,最佳分类的确定,在模糊聚类分析中，对于各个不同的0,1，可得到不同的分类，从而形成一种动态聚类图，这对全面了解样本分类情况是比较形象和直观的. 但在许多实际问题中，需要给出样本的一个具体分类，这就提出了如何确定最佳分类的问题.,2020/8/20,设X = (xij)nm为n个元素m个指标的原