模式识别-聚类分析(集群)

1、模模式识别式识别Pattern Classification第七章第七章:聚类分析（集群）聚类分析（集群）Applied Pattern Recognition CSE6163基本概念基本概念有师识别：由学习过程和识别过程两部分组成，且用于学习的样本类别是已知的。无师识别：缺少样本类别的先验知识，在样本类别未知的情况下进行分类（非监督学习方法）应用：语音识别、图像分割、遥感图像分类、数据挖掘Applied Pattern Recognition CSE6164基本概念基本概念聚类（集群）：根据模式之间的相似度（相似程度）对模式进行无师识别的方法相似度：衡量模式之间相似程度的尺度。聚类准则：聚类

2、分析的同一类模式相似程度的标准或不同类模式差异程度的标准。聚类效果取决于模式的特征空间中的分布！Applied Pattern Recognition CSE6165相似度测量相似度测量欧氏距离（衡量两个样本之间的距离）设x,x为d维特征空间的模式向量，则欧氏距离 直观地反映了两个样本的相似程度 221212112121)()(),(ddXXXXXXXXDApplied Pattern Recognition CSE6166相似度测量马氏距离（衡量单个样本与某类样本，或两类样本之间的距离） nkkXn11nkTkkXXn1)(1Applied Pattern Recognition CSE61

3、67相似度测量设x为某样本，则该样本与均值向量为，协方差矩阵为的模式类的马氏距离为 ：)()(1XXDTApplied Pattern Recognition CSE6168相似度测量马氏距离与样本与均值向量之间的距离成正比马氏距离与样本与均值向量之间的距离成正比Applied Pattern Recognition CSE6169相似度测量马氏距离与协方差成反比马氏距离与协方差成反比Applied Pattern Recognition CSE61610相似度测量而均值分别为1和2 ，协方差为的两模式类的马氏距离为： )()(21121TDApplied Pattern Recognitio

4、n CSE61611聚类准则 聚类准则的类型 聚类准则阀值准则函数准则Applied Pattern Recognition CSE61612聚类准则 阀值准则 根据规定的距离阀值或类别数进行分类 函数准则 定义一个准则函数，把聚类分析问题转化为准则函数求极值的问题Applied Pattern Recognition CSE61613基于阀值准则的聚类方法合并聚类法定义样本间的距离： 欧氏距离定义类与类之间的距离： 近点距离（最短距离） 远点距离（最长距离） 均值距离 马氏距离Applied Pattern Recognition CSE61614基于阀值准则的聚类方法最近距离最近距离App

5、lied Pattern Recognition CSE61615基于阀值准则的聚类方法最远距离最远距离Applied Pattern Recognition CSE61616基于阀值准则的聚类方法均值距离均值距离Applied Pattern Recognition CSE61617基于阀值准则的聚类方法合并聚类法首先假设每个样本自成一类，并计算各类之间的距离。然后将具有最近距离的两类样本合并成一类重复上述过程，直至合并的类别数等于给定的数目，或各类别间的距离大于某规定的距离阀值为止 Applied Pattern Recognition CSE61618基于阀值准则的聚类方法合并聚类法Ap

6、plied Pattern Recognition CSE61619基于阀值准则的聚类方法合并合并聚类法聚类法-聚为聚为3类类基于阀值准则的聚类方法合并合并聚类法聚类法-聚为聚为2类类Applied Pattern Recognition CSE61621基于阀值准则的聚类方法 C-均值算法（动态聚类法）指定群数C，选取C个代表点作为群的聚类中心。（可选各类的均值位置为聚类中心）遍历所有的样本，将每个样本归入与之最近的聚类中心所的代表的群（成批样本修正法）重新计算C个群的中心，将其作为各群新的聚类中心，重复第2步，直至分类结果不变逐个样本修正法Applied Pattern Recogniti

7、on CSE61622基于阀值准则的聚类方法 C-均值算法Applied Pattern Recognition CSE61623基于阀值准则的聚类方法C-均值算法的局限性最终的聚类结果依赖于初始类中心的选择需要事先指定聚类的类别数Applied Pattern Recognition CSE61624基于阀值准则的聚类方法问题：如何确定聚类群数，初始聚类重心？改进的C-均值算法 首先计算各样本的密度，并将样本按密度顺序排列 给定距离阀值T，挑选出可能的样本作为初始聚类中心 应用：1、语音识别 2、图像分类 Applied Pattern Recognition CSE61625基于阀值准则的

8、聚类方法改进的改进的C-均值算法均值算法Applied Pattern Recognition CSE61626基于阀值准则的聚类方法理论上可以证明，不论初始类中心如何选择，动态聚类算法总是可以收敛的。 Applied Pattern Recognition CSE61627基于阀值准则的聚类方法核函数的聚类算法样本x与聚类Ki间相似性度量:样本集Ki =xj(i)用一个所谓的“核函数”Ki，如样本集的某种统计量( ,)iKxApplied Pattern Recognition CSE61628基于阀值准则的聚类方法核函数的聚类算法Applied Pattern Recognition CS

9、E61629基于准则函数的聚类方法 误差平方和准则 定义误差平方和准则函数为： 其中C为类别数， 为第i类样本， 为第i类样本的均值向量,即： CiXXieimXJ12)()(iXim)(1iXXiiXnmApplied Pattern Recognition CSE61630基于准则函数的聚类方法 为第i类样本总数 表示样本聚为C个类别（群）后，所有样本到各类中心之间误差的平方和。当 最小时，即是希望的聚类结果。ineJeJApplied Pattern Recognition CSE61631基于准则函数的聚类方法上述准则函数的值，只有在知道聚类群数，及各样本属于那一群后，才能计算欲求极小

10、值，用穷举法是行不通的通常是应用迭代的方法来实现 Applied Pattern Recognition CSE61632基于准则函数的聚类方法基本思想：根据一定的先验知识确定聚类的群数，并粗略找到一个初始划分结果，再由迭代算法得到最优聚类结果。 Applied Pattern Recognition CSE61633基于准则函数的聚类方法原理：采用误差平方和准则函数 CiXXiCiieimXJJ121)()(1iXXiiXnmApplied Pattern Recognition CSE61634基于准则函数的聚类方法现假定在初始划分后，将 中的样本 搬到 中去则 变为： )(iX)( jXjmXXnnmXmmjXXjjjjj)(111XApplied Pattern Recognition CSE61635基于准则函数的聚类方法则 增加到jJ2*1jjjjjmXnnJJApplied Pattern Recognition CSE61636基于准则函数的聚类方法同理， 则减小到iJ21iiiiimXnnJJApplied Pattern Recognition CSE61637基于准则函数的聚类方法若减小的大于增加的，即则这次搬动改进了准则函数。2211jjjiiim