模式识别原理绪论聚类分析.ppt

当m=2时，明氏距离为欧氏距离。 n维模式样本向量Xi、Xj间的明氏距离表示为 ： 式中， xik、xjk分别表示Xi和Xj的第k个分量。 街坊 欧氏 3. 明氏距离( Minkowaki ) 当m=1时： 称为“街坊”距离 (“City block”distance)。 当k=2时：图示 4．汉明(Hamming)距离 设Xi、Xj 为n维二值（1或－1）模式样本向量，则 两个模式向量的各分量取值均不同：Dh(Xi, Xj)=n； 全相同： Dh(Xi, Xj)=0 式中， xik、xjk分别表示Xi和Xj的第k个分量。 汉明距离： 5．角度相似性函数 是模式向量Xi，Xj之间夹角的余弦。 6．Tanimoto测度 用于0，1二值特征的情况， 相似性测度函数的共同点都涉及到把两个相比较的向量Xi，Xj的分量值组合起来，但怎样组合并无普遍有效的方法，对具体的模式分类，需视情况作适当选择。 聚类准则：根据相似性测度确定的，衡量模式之间是否相似的标 准。即把不同模式聚为一类还是归为不同类的准则。 确定聚类准则的两种方式： 1. 阈值准则：根据规定的距离阈值进行分类的准则。 2. 函数准则：利用聚类准则函数进行分类的准则。 聚类准则函数：在聚类分析中，表示模式类间相似或差异性 的函数。 它应是模式样本集{X }和模式类别 的函数。可使聚类分析转化为寻找准则函数极值的最优化问题。一种常用的指标是误差平方之和。 2.2.2 聚类准则 聚类准则函数： 式中：c为聚类类别的数目， 为属于 集的样本的均值向量， 为 中样本数目。 J代表了分属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。 适用范围： 适用于各类样本密集且数目相差不多，而不同类间的样本又明显分开的情况。 例1： 类内误差平方和很 小，类间距离很远。 可得到最好的结果。 类长轴两端距离中心很远，J值较大，结果不易令人满意。 错误分类 例2：另一种情况 有时可能把样本数目多的一类分拆为二，造成错误聚类。 原因：这样分开，J值会更小。 正确分类 2.3 基于距离阈值的聚类算法 1. 问题：有N个待分类的模式 ，要求按距离阈值T分类到以 为聚类中心的模式类中。 2. 算法描述 ① 任取样本Xi 作为第一个聚类中心的初始值，如令Z1 = X1 。 ② 计算样本X2 到Z1 的欧氏距离 ， 若 ，定义一新的聚类中心Z2 = X2 ； 否则 X2 ∈以Z1为中心的聚类。 (T_threshold ) 2.3.1 近邻聚类法 ……依此类推，直到将所有的N个样本都进行分类。 ③ 假设已有聚类中心Z1、Z2，计算 和 ， 若 且 ，则建立第三个聚类中心Z3 = X3； 否则X3∈离Z1和Z2中最近者（最近邻的聚类中心）。 3. 算法特点 2）优点：计算简单。（一种虽粗糙但快速的方法） 1）局限性：很大程度上依赖于第一个聚类中心的位置选择、待 分类模式样本的排列次序、距离阈值T的大小以及样本分布 的几何性质等。 用先验知识指导阈值T 和起始点Z1的选择，可获得合理的聚类结果。否则只能选择不同的初值重复试探，并对聚类结果进行验算，根据一定的评价标准，得出合理的聚类结果。 对结果验算，类内各样本点间距离方差之和太大 减小T，修改中心Z。 4．算法讨论 2.3.2 最大最小距离算法（小中取大距离算法 ） 1. 问题：已知N个待分类的模式 ， 分类到聚类中心 对应的类别中 。 2. 算法描述 ① 选任意一模式样本做为第一聚类中心Z1。 ② 选择离Z1距离最远的样本作为第二聚类中心Z2。 ③ 逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算 min( Di1 , Di2 )，i=1，…，N （N个最小距离） ⑥ 将样本