聚类分析的介绍
聚类的要求
• 数据挖掘的聚类一般是针对大数据集而言的,因此在数据挖掘 • • • • • • •
中聚类方法的比较应该满足以下要求: 1）可伸缩性。算法在满足小数据集的同时能否满足大数据集、 高复杂性、高增量的要求。 2) 处理不同类型属性的能力。算法在处理数值类型数据的同 时能否处理其他的数据类型,如二元类型、分类/标称型、序数 型及混合数据类型。 3) 发现任意形状的类。 4) 用于决定输入参数的领域知识最小化。 5) 处理噪声数据的能力。 6) 对输入数据顺序的敏感性。算法能否与输入顺序无关。 7) 处理高维数据的能力。算法在应付低维数据的同时能否处 理高维空间的非常稀疏、高度偏斜的数据。
• 常见的距离函数
•
20122012-2-21
参考文献
• 【 1 】 Scholkopf B ,Smola A ,Muller K. Nonlinear • • • •
component analysisas a kernel eigenvalue problem[J ] . 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) : 387～390 387～ 【3】 Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms. New York: Plenum Press, 1981 【4】张铃,张钹. 模糊商空间理论. 软件学报, 2003,14(4) 张铃,张钹. 模糊商空间理论. 软件学报, 【5】高新波，模糊聚类分析及其应用，西安电子科技大 学出版社
•
模糊聚类分析可以很容易获得它的一个模糊划分： U={uik|1<=i<=c;1<=k<=n}.但是，要保证划分的有意义， |1<=i<=c;1<=k<=n}.但是，要保证划分的有意义， 则需要依据为题的需要定义合适的划分准则。 我们可以从五个参量的角度来概述目标函数的演化过程： 1：对模糊划分矩阵U的研究 对模糊划分矩阵U 2：对相似性准则D（.）的研究 对相似性准则D 3：对聚类原型P的研究 对聚类原型P 4：对加权指数m的研究 ：对加权指数m 5：对各种数据集X聚类的研究 ：对各种数据集X
20122012-2-21
模糊聚类算法
• 在这里我们给出几个用到的定义： • 定义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,用 一个矩阵来表示,记作R = ( rij ) n ×m ,其中,矩阵R 的元素 满足: 0≤ril ≤1 (0≤i, j≤1) ,矩阵R 称Fuzzy(模糊)矩阵。
20122012-2-21
20122012-2-21
对FCM算法改进的可行性 FCM算法改进的可行性
针对以上的问题，为了晚上现有的FCM类型算法，优化算 针对以上的问题，为了晚上现有的FCM类型算法，优化算 法准则函数的几个重要参数，扩展算法的应用范围。具体 可以 1：优化加权指数m的选择 ：优化加权指数m 2：聚类原型参数的最有初始化 3：结合聚类趋势、聚类分析和有效性三种手段构造一套 完整的分析方法，不进要回答数据集中的无聚类结构，并 确定这些结构，还要分析聚类的结果是否有效。 4：研究针对特殊类型数据的FCM算法，拓展该算法的应 ：研究针对特殊类型数据的FCM算法，拓展该算法的应 用范围。
20122012-2-21
模糊聚类算法
• ④如果模糊相似关系R 是模糊等价关系, 则可直接 • •
进行聚类分析, 否则, 转到下一步; ⑤改造模糊相似关系使其成为模糊等价关系, 方 法是将模糊相似矩阵循环自乘, 如: R×R=R2, R2×R2 =R4,⋯直到满足R2k=Rk 为止, 则Rk 便是 ⋯ 改造R 所得的一个模糊等价关系, 然后在此基础上 再进行模糊聚类分析。
20122012-2-21
FCM算法的介绍 FCM算法的介绍
• 为了优化聚类目标函数，人们提出了现在
相当流行和应用广泛的模糊c均值（FCM， 相当流行和应用广泛的模糊c均值（FCM， Fuzzy c-means）聚类算法。该算法是从硬 c-means）聚类算法。该算法是从硬 c均值（HCM,Hard c-means）聚类算法发 均值（HCM,Hard c-means）聚类算法发 展而来的。 • 以下给出FCM算法和HCM算法步骤： 以下给出FCM算法和HCM算法步骤：
基于模糊聚类算法中FCM算法 算法 基于模糊聚类算法中 的改进研究
Yunnan university Department of Computer Science Lei Zhiming 2008-052008-05-13
目录
• 聚类分析的介绍 • 模糊聚类算法 • FCM算法的介绍 FCM算法的介绍 • 模糊c均值类型聚类算法研究现状 模糊c • 对FCM算法改进的可行性 FCM算法改进的可行性 • 对FCM算法改进的想法 FCM算法改进的想法 • 参考文献
20122012-2-21
模糊c 模糊c均值类型聚类算法研究现状
• 对于给定的数据集，首先判断有无聚类结构，这就
属于聚类趋势研究的课题，如果已经确认有聚类结 构则需要用算法来确定这些结构，这属于聚类分析 研究的课题，得到聚类结构以后，则需要分析聚类 结果的合理性，这属于聚类有效性研究的课题。对 聚类分析而言，有效性问题又可以转化为最佳类别 数c的决策。 历史上有关聚类有效性问题的研究大都是基于 HCM,FCM算法的，现有的聚类有效性函数按定义 HCM,FCM算法的，现有的聚类有效性函数按定义 方式分为：基于数据集模糊划分的，基于数据集几 何结构的和基于数据集统计信息的三类其理论基础 和提点如表所示 ：
20122012-2-21
THANKS
20122012-2-21
基于进化计算的实现
• 三种模糊聚类实现途径的比较
20122012-2-21
基于神经网络的实现
• 两种聚类神经网络的比较
20122012-2-21
对聚类原型P 对聚类原型P的研究
• 几种原型的特点比较
20122012-2-21
对相似性准则D 对相似性准则D（.）的研究
20122012-2-21
模糊聚类算法
• 在上述定义中： 在上述定义中：由模糊相似关系确定的矩阵是模式相似矩 • • •
阵, 由模糊等价关系确定的矩阵是模糊等价矩阵。 下面简单说下从模糊相似矩阵出发, 求传递闭包或模糊等 价矩阵来进行模糊聚类分析方法的步骤： ①确定将要进行聚类分析的对象的统计指标; ②为便于比较和分析, 将统计指标的数据标准化, 并将标准 化的数据压缩到[0,1]闭区间,方法如下 其中Xij 是统计指标原始数据, 第j 列 是统计指标原始数据的最小值, 是 统计指标原始数据的最大值。
20122012-2-21
对FCM算法改进的想法 FCM算法改进的想法
• 针对FCM算法我心里有两种想法， 针对FCM算法我心里有两种想法， • 一种是针对算法本身，对算法的内容进行分析，
将其分类，比如对于数据类型的分类，对对应的 数据类型运用相应的数据处理的函数，运用c 数据类型运用相应的数据处理的函数，运用c语言 中函数重构的性质来进行各个函数的运算。另外 就是将聚类算法中的基于密度或者是基于网格的 某一种来确定初始聚类核心，或者是可以初始判 断聚类核心，从而可以减小模糊聚类的运算次数， 从而减小运算量。 另外一种就是感觉现在的FFCM算法还有可以改进 另外一种就是感觉现在的FFCM算法还有可以改进 的地方，针对现在运用的快速FCM算法进行改进。 的地方，针对现在运用的快速FCM算法进行改进。
20122012-2-21
模糊c 模糊c均值类型聚类算法研究现状
• 有了聚类准则函数，接下来就是如何优化
目标函数以获得最佳聚类的问题了，即研 究算法的实现途径。现有的实现研究途径 主要分为基于交替优化、神经网络和进化 运算等三类方法。 1：基于交替优化的实现 2：基于神经网络的实现 3：基于进化计算的实现
用，人们在此基础上进行了发展和深化， 提出了许多模糊c 提出了许多模糊c均值类型的算法。可以从 一下三个方面进行描述。 • 目标函数的演化 • 算法的实现途径 • 有效性度量方式
20122012-2-21
模糊c 模糊c均值类型聚类算法研究现状
• 由模糊聚类的数学模型可以知道，对于Байду номын сангаас组给定的样本集，
20122012-2-21
聚类分析的介绍
聚类算法分类 聚类分类图：
20122012-2-21
模糊聚类算法
• 传统模糊聚类方法分为两类:一类是模糊等价矩阵动态聚
类法,另一类是模糊ISODATA聚类方法。第一类分类算法 主要有传递闭包法、最大树法、模糊C - 均值法( Fuzzy C - Means,FCM)等。我主要要研究的主要是FCM算法上的改 进算法，所以先介绍模糊相似矩阵和模糊等价关系的概念 [4]。