模式识别讲义--聚类分析.ppt

聚类分析（Clustering Analysis） 分类与聚类的区别 分类：用已知类别的样本训练集来设计分类器（监督学习） 聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习） 聚类分析 解决主要问题 1.如何评价样本间的类似程度； 2.如何根据样本间的类似程度聚类。 特征量的类型 1.物理量：反映实际物理或几何意义，如重量 2.次序量：只反映次序关系，如产品等级等 3.名义量：只用数字代表各种状态，如性别编码 方法有效性 1.特征选取不当 2.特征选取不足 3.特征选取过多 4.量纲选取不当 模式相似性测度 距离测度：以两个矢量矢端的距离为基础 1.欧式距离：(Euclidean) 2.绝对值距离：（Manhattan） 3.切氏距离：（Chebyshev） 距离测度 4.明氏距离：（Minkowski） 5.马氏距离（Mahalanobis） 类的定义 1.集合S中任意两个元素xi,xj的距离dij满足如下条件之一，则S对于阈值h组成一类，h为阈值。 2.集合S中元素满足对于任一xi,存在xj的距离dij满足dij ≤h，则S对于阈值h组成一类，h为阈值。 3.若将集合任意分为两类S1，S2，这两类间的距离D(S1,S2）满足D(S1,S2)≤h，则称S对于阈值h组成一类。 类间距离定义 最短距离：两类中相距最近的两样品间的距离 最长距离 ：两类中相距最远的两个样本间的距离。 中间距离：设ω1类和ω2 ω3类间的最短距离为d12，最长距离为d13， ω2 ω3类的长度为d23， 则中间距离为： 类间距离定义（续） 类间距离定义（续） 平均距离：两类中各个元素两两之间的距离平方相加后取平均值 类间距离定义（续） 离差平方和：设N个样品原分q类，则第i类离差平方和为 离差平方和增量：设样本已分成ωp,ωq两类，若把ωp,ωq合为ωr类，则定义离差平方 聚类的准则函数—类内距离 聚类的准则函数—类间距离 基于类内、类间距离准则 聚类的技术方案 根据相似性阈值和最小距离原则的简单聚类 确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，都大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则将其分划到某一类中。 按最小距离原则不断进行两类合并的方法 首先视各模式自成一类，然后将距离最小的两类合并成一类，不断地重复这个过程，直到成为两类为止。 依据准则函数动态聚类法 设定一些分类的控制参数，定义一个能表征聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。 根据相似性阈值和最小距离原则的简单聚类 l．条件及约定 待分类的模式集为{X1,X2,…,XN}，选定类内距离门限T。 2．算法思想 计算模式特征矢量到聚类中心的距离并和门限T比较，决定归属哪类或作为新的一类中心。通常采用欧氏距离。 3.算法步骤 (1)取任意的一个模式作为聚类中心。ω1，中心z1=x1 (2)计算下一模式x2到z1的距离d21，if d21T 建立新类ω2，中心为z2=x2 ；否则x2属于ω1 。 (3)设有z1,z2,…, zk,计算未定类别xi到zj(j=1,…,k)的距离dij， if dijT 建立新类ωk+1，中心为zk+1=xi ；否则如果 dil= min[dij],j=1,2,…,k,则xi属于ωl。未结束，返回（3）。 最大最小距离算法 1．条件及约定 待分类的模式特征矢量集为{Xl,X2…,XN}，选定比例系数θ 2．基本思想 在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。通常使用欧氏距离。 3.算法步骤 (1)取任意的一个模式作为第一类聚类中心。ω1，中心z1=x1 (2)选取距z1最远的特征矢量最为第二个聚类中心z2。 (3)计算未作为聚类中心的各模式Xi与z1，z2的距离，求最小值.。 (4) 最大最小距离算法 (5)设存在k个聚类中心，计算未作为聚类中心的各模式Xi到各聚类中心的距离dij，并算出 (6)将各模式特征矢量按最小距离的原则分到各类中去。 系统聚类(谱系聚类法) 1．条件及约定 设待分类的模式特征矢量集为{Xl，X2…，XN}，Gi(k)表示第 k次合并时的第i类。 2．基本思想 首先视N个模式各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。 3.算法步骤 (1)初始分类。令k=0，