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

模式识别PatternClassification第七章:聚类分析（集群）模式识别，第七章3基本概念•有师识别：由学习过程和识别过程两部分组成，且用于学习的样本类别是已知的。•无师识别：缺少样本类别的先验知识，在样本类别未知的情况下进行分类（非监督学习方法）•应用：语音识别、图像分割、遥感图像分类、数据挖掘模式识别，第七章4基本概念•聚类（集群）：根据模式之间的相似度（相似程度）对模式进行无师识别的方法•相似度：衡量模式之间相似程度的尺度。•聚类准则：聚类分析的同一类模式相似程度的标准或不同类模式差异程度的标准。聚类效果取决于模式的特征空间中的分布！模式识别，第七章5相似度测量•相似度测量•欧氏距离（衡量两个样本之间的距离）设x１,x２为d维特征空间的模式向量，则欧氏距离直观地反映了两个样本的相似程度221212112121)()(),(ddXXXXXXXXD模式识别，第七章6相似度测量•马氏距离（衡量单个样本与某类样本，或两类样本之间的距离）nkkXn11nkTkkXXn1))((1模式识别，第七章7相似度测量•设x为某样本，则该样本与均值向量为μ，协方差矩阵Σ为的模式类的马氏距离为：•)()(1XXDT模式识别，第七章8相似度测量Ｄ１Ｄ２马氏距离与样本与均值向量之间的距离成正比模式识别，第七章9相似度测量马氏距离与协方差成反比模式识别，第七章10相似度测量•而均值分别为μ1和μ2，协方差为Σ的两模式类的马氏距离为：)()(21121TD模式识别，第七章11聚类准则•聚类准则的类型聚类准则阀值准则函数准则模式识别，第七章12聚类准则•阀值准则根据规定的距离阀值或类别数进行分类•函数准则定义一个准则函数，把聚类分析问题转化为准则函数求极值的问题模式识别，第七章13基于阀值准则的聚类方法•合并聚类法•定义样本间的距离：欧氏距离•定义类与类之间的距离：近点距离（最短距离）远点距离（最长距离）均值距离马氏距离模式识别，第七章14基于阀值准则的聚类方法最近距离模式识别，第七章15基于阀值准则的聚类方法最远距离模式识别，第七章16基于阀值准则的聚类方法均值距离模式识别，第七章17基于阀值准则的聚类方法•合并聚类法•首先假设每个样本自成一类，并计算各类之间的距离。然后将具有最近距离的两类样本合并成一类•重复上述过程，直至合并的类别数等于给定的数目，或各类别间的距离大于某规定的距离阀值为止模式识别，第七章18基于阀值准则的聚类方法•合并聚类法模式识别，第七章19基于阀值准则的聚类方法合并聚类法-聚为3类基于阀值准则的聚类方法合并聚类法-聚为2类模式识别，第七章21基于阀值准则的聚类方法•C-均值算法（动态聚类法）•指定群数C，选取C个代表点作为群的聚类中心。（可选各类的均值位置为聚类中心）•遍历所有的样本，将每个样本归入与之最近的聚类中心所的代表的群（成批样本修正法）•重新计算C个群的中心，将其作为各群新的聚类中心，重复第2步，直至分类结果不变•逐个样本修正法模式识别，第七章22基于阀值准则的聚类方法•C-均值算法模式识别，第七章23基于阀值准则的聚类方法•C-均值算法的局限性•最终的聚类结果依赖于初始类中心的选择•需要事先指定聚类的类别数模式识别，第七章24基于阀值准则的聚类方法•问题：如何确定聚类群数，初始聚类重心？•改进的C-均值算法①首先计算各样本的密度，并将样本按密度顺序排列②给定距离阀值T，挑选出可能的样本作为初始聚类中心应用：1、语音识别2、图像分类模式识别，第七章25基于阀值准则的聚类方法改进的C-均值算法模式识别，第七章26基于阀值准则的聚类方法•理论上可以证明，不论初始类中心如何选择，动态聚类算法总是可以收敛的。模式识别，第七章27基于阀值准则的聚类方法•核函数的聚类算法•样本x与聚类Ki间相似性度量:•样本集Ki={xj(i)}•用一个所谓的“核函数”Ki，如样本集的某种统计量(,)iKx模式识别，第七章28基于阀值准则的聚类方法•核函数的聚类算法模式识别，第七章29基于准则函数的聚类方法•误差平方和准则•定义误差平方和准则函数为：其中C为类别数，为第i类样本，为第i类样本的均值向量,即：CiXXieimXJ12)()(iXim)(1iXXiiXnm模式识别，第七章30基于准则函数的聚类方法•为第i类样本总数•表示样本聚为C个类别（群）后，所有样本到各类中心之间误差的平方和。•当最小时，即是希望的聚类结果。ineJeJ模式识别，第七章31基于准则函数的聚类方法•上述准则函数的值，只有在知道聚类群数，及各样本属于那一群后，才能计算•欲求极小值，用穷举法是行不通的•通常是应用迭代的方法来实现模式识别，第七章32基于准则函数的聚类方法•基本思想：•根据一定的先验知识确定聚类的群数，并粗略找到一个初始划分结果，再由迭代算法得到最优聚类结果。模式识别，第七章33基于准则函数的聚类方法•原理：采用误差平方和准则函数CiXXiCiieimXJJ121)()(1iXXiiXnm模式识别，第七章34基于准则函数的聚类方法•现假定在初始划分后，将中的样本搬到中去•则变为：)(iX)(jXjmXXnnmXmmjXXjjjjj)(111X模式识别，第七章35基于准则函数的聚类方法•则增加到jJ2*1jjjjjmXnnJJ模式识别，第七章36基于准则函数的聚类方法•同理，则减小到iJ21iiiiimXnnJJ模式识别，第七章37基于准则函数的聚类方法•若减小的大于增加的，即•则这次搬动改进了准则函数。2211jjjiiimXnnmXnn模式识别，第七章38其它聚类方法•模糊聚类方法•基于遗传算法的模糊聚类方法•支持向量聚类方法•基于网格的聚类方法•基于密度的方法•神经网络方法模式识别，第七章39模式识别，第七章40