第7章-聚类分析[2014]

1、模式识别模式识别Pattern Classification第七章第七章:聚类分析（集群）聚类分析（集群）模式识别，第七章3概述概述有师识别由学习过程和识别过程两部分组成，且用于学习的样本类别是已知的。无师识别缺少样本类别的先验知识，在样本类别未知的情况下进行分类（非监督学习方法）应用语音识别、图像分割、遥感图像分类、数据挖掘模式识别，第七章4概述概述类的定义类的定义有很多种，类的划分具有人为规定性，这反映在定义的选取及参数的选择上总的思路是相似的样本归为一类定义之一： 设集合S中任意元素xi与yj间的距离dij有 dij h 其中h为给定的阈值，称S对于阈值h组成一类。模式识别，第七章5概述

2、概述类的定义模式识别，第七章6概述概述聚类（集群）按照一定的分类准则，根据模式之间的相似度（相似的程度）对模式进行分类的方法相似度衡量模式之间相似程度的尺度聚类准则同一类模式相似程度的标准或不同类模式差异程度的标准。模式识别，第七章7概述概述聚类分析的三个基本方向减少数据 许多时候，当数据量N很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类m（mN）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。模式识别，第七章8概述概述聚类分析的三个基本方向假说检验 用聚类分析来验证指定假说的有效性。 例如：考虑这样的假说“大公司在海外投资”。要验证这个假

3、说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个假说。模式识别，第七章9概述概述聚类分析的三个基本方向基于分组的预测 对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，对于一个未知模式，就可以用前面的聚类来确定是哪一类？ 模式识别，第七章10聚类方法的应用商业聚类分析被用来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征。聚类分析是细分市场的有效工具，同时也可用于研究消费者行为，寻找新的潜在市场、选择实验的市场。 模式识别，第七章11聚类方法的应用生物聚类分析被用来动植物分类和对基因进行分类，获取对种群固有结构的认识。

4、地理聚类能够帮助挖掘在地理空间中，地理数据和地理现象的分布规律和相关特性。模式识别，第七章12聚类方法的应用因特网聚类分析被用来在网上信息进行归类，以支持信息检索。电子商务通过分组聚类出具有相似浏览行为的客户，并分析客户的共同特征，可以更好的帮助电子商务的用户了解自己的客户，向客户提供更合适的服务。 模式识别，第七章13概述概述选取不同特征，将得到不同的聚类结果！模式识别，第七章14概述概述下列是一些动物的名称： 羊 （sheep） 狗 （dog） 蓝鲨（blue shark） 蜥蜴 （lizard） 毒蛇（viper） 猫 （cat） 麻雀（sparrow） 海鸥 （seagull） 金鱼（

5、gold fish） 青蛙 （frog）要对这些动物进行分类，则不同的特征有不同的分法模式识别，第七章15概述概述羊, 狗, 猫蓝鲨蜥蜴,毒蛇,麻雀,海鸥,金鱼,青蛙以繁衍后代的方式作为特征哺乳动物非哺乳动物模式识别，第七章16概述概述金鱼蓝鲨羊,狗,猫蜥蜴,毒蛇麻雀,海鸥 青蛙以肺是否存在作为特征无肺有肺模式识别，第七章17概述概述青蛙羊,狗,猫 蜥蜴,毒蛇麻雀,海鸥 金鱼 蓝鲨以生活环境作为特征陆地水里两栖模式识别，第七章18概述概述分类尺度的不同，也将影响聚类结果！模式识别，第七章19概述概述粗聚类是2类，细聚类为4类模式识别，第七章20概述概述聚类效果取决于模式在特征空间中的分布和分类

6、算法关键问题：选择什么特征？以什么为相似度？选择什么样的聚类方法？ 模式识别，第七章21相似性测度用于描述各模式之间特征的相似程度 相似性测度相似性测度距离测度距离测度匹配测度匹配测度相似测度相似测度模式识别，第七章22相似性测度距离测度测度基础：特征向量间的距离欧氏距离（衡量两个样本之间的距离）设x,x为d维特征空间的模式向量，则欧氏距离 直观地反映了两个样本的相似程度 221212112121)()(),(ddXXXXXXXXD模式识别，第七章23相似性测度马氏距离（衡量单个样本与某类样本，或两类样本之间的距离） nkkXn11nkTkkXXn1)(1模式识别，第七章24相似性测度设x为某

7、样本，则该样本与均值向量为，协方差矩阵为的模式类的马氏距离为 ：)()(1XXDT模式识别，第七章25相似性测度马氏距离与样本与均值向量之间的距离成正比马氏距离与样本与均值向量之间的距离成正比模式识别，第七章26相似性测度马氏距离与协方差成反比马氏距离与协方差成反比模式识别，第七章27相似性测度而均值分别为1和2 ，协方差为的两模式类的马氏距离为： )()(21121TD模式识别，第七章28相似性测度相似测度测度基础：特征向量方向的相近程度匹配测度测度基础：特征只有两个状态（0，1）时的相似程度模式识别，第七章29聚类准则 聚类准则的类型 聚类准则阈值准则函数准则模式识别，第七章30聚类准则

8、阈值准则 根据规定的距离阈值或类别数进行分类 函数准则 定义一个准则函数，把聚类分析问题转化为准则函数求极值的问题模式识别，第七章31基于阈值准则的聚类方法合并聚类法定义样本间的距离： 欧氏距离定义类与类之间的距离： 近点距离（最短距离） 远点距离（最长距离） 均值距离 马氏距离模式识别，第七章32基于阈值准则的聚类方法近点距离近点距离模式识别，第七章33基于阈值准则的聚类方法远点距离远点距离模式识别，第七章34基于阈值准则的聚类方法均值距离均值距离模式识别，第七章35基于阈值准则的聚类方法合并聚类法首先假设每个样本自成一类，并计算各类之间的距离。然后将具有最近距离的两类样本合并成一类重复上述

9、过程，直至合并的类别数等于给定的数目，或各类别间的距离大于某规定的距离阈值为止 模式识别，第七章36基于阈值准则的聚类方法合并聚类法模式识别，第七章37基于阈值准则的聚类方法合并合并聚类法聚类法-聚为聚为3类类基于阈值准则的聚类方法合并合并聚类法聚类法-聚为聚为2类类模式识别，第七章39基于阈值准则的聚类方法 C-均值算法（动态聚类法）指定群数C，选取C个代表点作为群的聚类中心。（可选各类的均值位置为聚类中心）遍历所有的样本，将每个样本归入与之最近的聚类中心所的代表的群重新计算C个群的中心，将其作为各群新的聚类中心，重复第2步，直至分类结果（聚类中心）不变模式识别，第七章40基于阈值准则的聚类

10、方法 C-均值算法模式识别，第七章41基于阈值准则的聚类方法C-均值算法的局限性最终的聚类结果依赖于初始类中心的选择需要事先指定聚类的类别数模式识别，第七章42基于阈值准则的聚类方法例：已知有20个样本，每个样本有2个特征，现用C均值算法实现样本分类（C=2）。模式识别，第七章43样本序号样本序号x x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7x x8 8x x9 9x x1010特征特征x x1 10 01 10 01 12 21 12 23 36 67 7特征特征x x2 20 00 01 11 11 12 22 22 26 66 6x11x12x13x

11、14x15x16x17x18x19x2086789789896777788899基于阈值准则的聚类方法模式识别，第七章44模式识别，第七章45基于阈值准则的聚类方法第一步：令C=2，选初始聚类中心为1122(1)(0, 0 );(1)(1, 0 )TTZxZx模式识别，第七章46基于阈值准则的聚类方法模式识别，第七章47模式识别，第七章48模式识别，第七章49模式识别，第七章50模式识别，第七章51模式识别，第七章52模式识别，第七章53基于阈值准则的聚类方法问题：如何确定聚类群数，初始聚类重心？改进的C-均值算法 首先计算各样本的密度，并将样本按密度顺序排列 给定距离阈值T，挑选出可能的样本

12、作为初始聚类中心 应用：1、语音识别 2、图像分类 模式识别，第七章54基于阈值准则的聚类方法改进的改进的C-均值算法均值算法模式识别，第七章55基于阈值准则的聚类方法理论上可以证明，不论初始类中心如何选择，动态聚类算法总是可以收敛的。 模式识别，第七章56基于准则函数的聚类方法 误差平方和准则 定义误差平方和准则函数为： 其中C为类别数， 为第i类样本， 为第i类样本的均值向量,即： CiXXieimXJ12)()(iXim)(1iXXiiXnm模式识别，第七章57基于准则函数的聚类方法 为第i类样本总数 表示样本聚为C个类别（群）后，所有样本到各类中心之间误差的平方和。当 最小时，即是希望

13、的聚类结果。ineJeJ模式识别，第七章58基于准则函数的聚类方法上述准则函数的值，只有在知道聚类群数，及各样本属于那一群后，才能计算欲求极小值，用穷举法是行不通的通常是应用迭代的方法来实现 模式识别，第七章59基于准则函数的聚类方法基本思想：根据一定的先验知识确定聚类的群数，并粗略找到一个初始划分结果，再由迭代算法得到最优聚类结果。 模式识别，第七章60基于准则函数的聚类方法原理：采用误差平方和准则函数 CiXXiCiieimXJJ121)()(1iXXiiXnm模式识别，第七章61基于准则函数的聚类方法现假定在初始划分后，将 中的样本 搬到 中去则 变为： )(iX)( jXjmXXnnmXmmjXXjjjjj)(111X模式识别，第七章