K-means ,FCM聚类.ppt

K-Means Fuzzy C-Means 报告人：马宝秋 聚类（Clustering） “物以类聚，人以群分” 是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息 聚类（Clustering） 聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（Subset），这样让在同一个子集中的成员对象都有相似的一些属性 其他分析算法的一个预处理步骤 在这一过程中没有监督，因此是一种无监督的分类 聚类（Clustering） 聚类分析的算法可以分为： 划分法（分割式）（Partitioning Methods） 层次法（阶层式）（Hierarchical Methods） 基于密度的方法（Density-based Methods） 基于网格的方法（Grid-based Methods） 基于模型的方法（Model-Based Methods） 聚类（Clustering）-层次法 这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止 聚类（Clustering）-基于密度的方法 基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的 这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点 聚类（Clustering）-基于网格的方法 这种方法首先将数据空间划分成为有限个单元（Cell）的网格结构,所有的处理都是以单个的单元为对象的 这么处理的一个突出的优点就是处理速度很快 聚类（Clustering）-基于模型的方法 基于模型的方法给每一个聚类假定一个模型，然后去寻找能个很好的满足这个模型的数据集 它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的 聚类（Clustering）-划分法 给定一个有N个元组或者纪录的数据集，构造K （ K N）个分组，每一个分组就代表一个聚类 （1）每一个分组至少包含一个数据纪录 （这个要求在某些模糊聚类算法中可以放宽） （2）每一个数据纪录属于且仅属于一个分组 聚类（Clustering）-划分法 对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好 而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好 聚类（Clustering）-划分法 使用这个基本思想的算法有： Vehicle Example Vehicle Clusterings Terminology K-Means聚类法（C-Means） K-means的归属矩阵 K-means实现步骤 K-means实现步骤 （4）式如何得来？ 设定聚类数目K，最大执行步骤tmax，一个很小的容忍误差ε0 决定聚类中心起始位置Cj(0)，0 j ≤ K for t=1,......,tmax （A）for j=1,......,N （i）计算各数据点到聚类中心的距离 （ii）计算数据点属于哪一聚类（隶属度矩阵） （B）更新聚类中心 （C）计算收敛准则，若 成立则停止运算，否则进行下一轮迭代 使用K-Means聚类法 使用K-Means聚类法 Cluster 形状以类圆形为主 使用K-Means聚类法 Fuzzy C-Means聚类法 Fuzzy C-Means聚类法 与K-Means不同点 参数m Bezdek和Hathaway 等人从算法的收敛性角度着手得出m的取值要大于n/(n-2),其中n为待分析样本的数目 Pal和Bezdek等人从聚类有效性角度得出m的取值范围为[1.5, 2.5] Cheung和Chen从汉字识别的应用背景得出的最佳取值应在1.25～1.75之间 高新波等和刘宜平等分别提出了基于模糊决策的m值优选方法 这些有关m的取值方法,实际上都可以看成是对分类结果的评价问题 Fuzzy C-means 实现步骤 Fuzzy C-Means实现步骤 The membership matrix W : 设定聚类数目K，最大执行步骤tmax，一个很小的容忍误差ε0 决定聚类中心起始位置Cj(0)，0 j ≤ K for t=1,......,tmax （A）for j=1,......,N ,计算隶属度矩阵 （B）for i=1,......,K,更新聚类中心点. （C）计算收敛准则，若 成立则停止运算，否则进行下一轮迭代 使用Fuzzy C-Means聚类法 同样地需事先确定聚类的数目 与K-Means聚类法最大的差异在于Fuzzy C-Means聚类法加入了模糊的概念，使得每一输入向量不再仅隶属于某一特定的聚类，而是以其隶属程度来表现（Sof