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

基于模糊聚类算法中FCM算法的改进研究 Yunnan university Department of Computer Science Lei Zhiming 2008-05-13 目录 聚类分析的介绍 模糊聚类算法 FCM算法的介绍 模糊c均值类型聚类算法研究现状 对FCM算法改进的可行性 对FCM算法改进的想法 参考文献 聚类分析的介绍 随着数据挖掘研究领域技术的发展,作为数据挖掘主要方法之一的聚类算法,也越来越受到人们的关注。聚类分析是数据挖掘研究和应用中一个重要的部分。。 聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。 在多媒体信息检索及数据挖掘的过程中,聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。 聚类分析的介绍聚类的要求 数据挖掘的聚类一般是针对大数据集而言的,因此在数据挖掘中聚类方法的比较应该满足以下要求: 1）可伸缩性。算法在满足小数据集的同时能否满足大数据集、高复杂性、高增量的要求。 2) 处理不同类型属性的能力。算法在处理数值类型数据的同时能否处理其他的数据类型,如二元类型、分类/标称型、序数型及混合数据类型。 3) 发现任意形状的类。 4) 用于决定输入参数的领域知识最小化。 5) 处理噪声数据的能力。 6) 对输入数据顺序的敏感性。算法能否与输入顺序无关。 7) 处理高维数据的能力。算法在应付低维数据的同时能否处理高维空间的非常稀疏、高度偏斜的数据。 聚类分析的介绍聚类算法分类 聚类算法的分类有多种标准，其中有按聚类标准，聚类处理的数据类型，聚类尺度，以及聚类分析的思路等。这里我们按照聚类基本思想来划分，将其分为五类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法,如下页图所示。 聚类分析的介绍聚类算法分类 聚类分类图： 模糊聚类算法 传统模糊聚类方法分为两类:一类是模糊等价矩阵动态聚类法,另一类是模糊ISODATA聚类方法。第一类分类算法主要有传递闭包法、最大树法、模糊C - 均值法( Fuzzy C - Means,FCM)等。我主要要研究的主要是FCM算法上的改进算法，所以先介绍模糊相似矩阵和模糊等价关系的概念[4]。 模糊聚类算法 在上述定义中：由模糊相似关系确定的矩阵是模式相似矩阵, 由模糊等价关系确定的矩阵是模糊等价矩阵。 下面简单说下从模糊相似矩阵出发, 求传递闭包或模糊等价矩阵来进行模糊聚类分析方法的步骤： ①确定将要进行聚类分析的对象的统计指标; ②为便于比较和分析, 将统计指标的数据标准化, 并将标准化的数据压缩到[0,1]闭区间,方法如下 其中Xij 是统计指标原始数据, 第j 列 是统计指标原始数据的最小值, 是 统计指标原始数据的最大值。 模糊聚类算法 ③计算被分类对象间相似程度的统计量作为矩阵的一个元素, 从而确定U 上的一个相似关系R。计算被分类对象间相似程度的统计量的方法有很多, 常用的有欧式距离法、数量积法、几何平均最小方法、算术平均最小方法、夹角余弦方法等方法。本文在计算被分类对象间相似程度时主要使用夹角余弦方法, 即: 模糊聚类算法 ④如果模糊相似关系R 是模糊等价关系, 则可直接进行聚类分析, 否则, 转到下一步; ⑤改造模糊相似关系使其成为模糊等价关系, 方 法是将模糊相似矩阵循环自乘, 如: R×R=R2, R2×R2 =R4,?直到满足R2k=Rk 为止, 则Rk 便是改造R 所得的一个模糊等价关系, 然后在此基础上再进行模糊聚类分析。 模糊聚类算法 在这里我们给出几个用到的定义： 定义1:设X = ( x1 , x2 , ?, xn )是来自统计样本的全部对象的集合, 每个xi 有m 个属性, 以( xi1 , xi2 , ?,xim )来表示xi 的一个划分,构成n ×m 矩阵,称为初始数值矩阵。 定义2:对X = (x1 , x2 , ?, xn )中任意两个不同的对象xi、xj ( i≠j) ,以rij表示xi 与xj 间的相似程度, 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,用一个矩阵来表示,记作