模式识别课件-(42)--第二章聚类分析第5节C均值聚类算法.pptVIP

2.1 聚类分析的概念 2.2 模式相似性测度 2.3 类的定义与类间距离 2.4 准则函数 2.5 聚类的算法 谢 谢！ 模式识别 模式识别 模式识别 《模式识别》 Pattern Recognition 主讲：蔡宣平 教授 第二章 聚类分析 * 2·5 聚类的算法 最大最小距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了。因此，这些方法效果一般不会太理想。 第二章 聚类分析 * 2. 确定评估聚类质量的准则函数。 确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，可采用马氏距离，设该类的均矢为 ，协方差阵为 ，则模式 和该类的 与该类均矢 的马氏距离： 距离平方为 3. 确定模式分划及聚类合并或分裂的规则。 2·5 聚类的算法 第二章 聚类分析 * 2.5.4 动态聚类法 建立初始聚类中心，进行初始聚类； 计算模式和类的距离，调整模式的类别； 计算各聚类的参数，删除、合并或分裂一些聚类； 从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止。 第二章 聚类分析 * 2.5.4 动态聚类法 产生初始聚类中心 聚类 检验聚类合理性 待分类模式 分类结果 合理 再迭代/修改参数 不合理 第二章 聚类分析 * 2.5.4 动态聚类法 ⒈ 条件及约定 设待分类的模式特征矢量集为： 类的数目C是事先取定的。 2.5.4 动态聚类法——C-均值法 ⒉ 算法思想 该方法取定 C个类别和选取 C个初始聚类中心，按最小距离原则将各模式分配到 C类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。 第二章 聚类分析 * 2.5.4 动态聚类法——C-均值法 ⒊ 算法原理步骤 ⑴ 任选C个模式特征矢量作为初始聚类中心： , 令 。 ⑵ 将待分类的模式特征矢量集 中的模式逐个按最小距离原则分划给C类中的某一类，即: 如果 则 , 式中 表示 和 的中心 的距离，上角标表示迭代次数。于是产生新聚类 。 第二章 聚类分析 * 2.5.3 动态聚类法——C-均值法 ⒊ 算法原理步骤 (3) 计算重新分类后的各类心 式中 为类 中所含模式的个数。 (4) 如果 ,则结束,否则 ,转至(2)。 第二章 聚类分析 * 选代表点 初始分类 分类合理否 4.动态聚类框图 2.5.3 动态聚类法——C-均值法 最终分类 Y 修改分类 N 第二章 聚类分析 * 例：已知有20个样本，每个样本有2个特征，数据分布如下图,使用C－均值法实现样本分类（C=2）。 样本序号 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 特征x1 0 1 0 1 2 1 2 3 6 7 特征x2 0 0 1 1 1 2 2 2 6 6 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 8 6 7 8 9 7 8 9 8 9 6 7 7 7 7 8 8 8 9 9 第二章 聚类分析 * 第一步：令C=2，选初始聚类中心为 第二章 聚类分析 * * 0 0 0 0 0 ＝ ） ）－（ （ ＝ 第二步： - 1 0 1 0 0 ＝ ） ）－（ （ ＝ - 1 0 0 0 1 ＝ ） ）－（ （ ＝ - 所以 因为 ? - - 第二章 聚类分析 * 0 ) 0 1 ( ) 0 1 ( = - = - , ? - - 所以 因为 同理 , 1 2 , 2 1 ? \ = - - ? \ = - - ＝ ＝ ... ... 20 6 5 20 6 5 都属于 、 、 离计算出来，判断 与第二个聚类中心的距 、 、 同样把所有 因此分为两类： ) ,... , , ( ) 1 ( ), , ( ) 1 ( 20 5 4 2 2 3 1 1 = = 18 , 2 2 1 = = N N G G 二、 一、 第二章 聚类分析 * * 第三步：根据新分成的两类建立新的聚类中心 T G N ) 5 . 0 , 0 ( ) 1 0 ( 2 1 ) 1 0 ( ) 0 0 ( 2 1 ) ( 2 1 1 3 1 ) 1 ( 1 1 = =