张素文第2章聚类分析研讨.pptVIP

此例中 X1，X3，X4 ∈ Z1 X1 X2，X6 ∈ Z2 X6 X5，X7，X8，X9，X10 ∈ Z3 X7 §2.4 分级聚类法 （Hierarchical Clustering Method） （系统聚类法、层次聚类法） 思路：每个样本先自成一类， 然后按距离准则逐步合并，减少类数。 一、算法： 1、N个初始模式本自成一类，即建立N 类： 计算各类之间（即各样本间）的距离，得一N×N维距离矩阵D 0 。标号 0 表示初始状态。 G_Group 2、如在前一步聚类运算中，已求得距离矩阵D n （n为逐次聚类合并的次数），则找出D n 中的最小元素，将其对应的两类合并为一类。由此建立新的分类： 。 3、计算合并后新类别之间的距离，得D n+1 。 4、跳至第2步，重复计算及合并。 结束条件： 取距离阀值T，当D n 的最小分量超过给定值 T 时， 算法停止。所得即为聚类结果。 2 或不设阀值T，一直将全部样本聚成一类为止，输 出聚类的分级树。 类间距离计算准则： H K 最短距离法：如H、K是两个聚类，则两类间的最短距离定义为： ：H类中的某个样本 和K类中的 某个样本 之间的欧氏距离。 ：H类中所有样本与K类中所有 样本之间的最小距离。 其中， 如果K类由I和J两类合并而成，则 得到递推公式： √ H K I J ②最长距离法： 若K类由I、J两类合并而成，则 有： ③ 中间距离法： 介于最长与最短的距离之间。 ④ 重心法： 将每类中包含的样本的数目考虑进去。 ⑤ 类平均距离法： 定义类间距离的方法不同，则分类结果不太一致。实际问题中常用几种不同的方法进行计算，比 较其分类结果，选择一个比较切合实际的分类。 粗略思路 自成一类， 计算两两元素间距离。 最近者合并为一类，再计算所有类两两间的距离。重复此步骤。 最近者的距离比 规定的距离还要远时停止。 或输出分级数 例：给出6个五维模式样本如下，按最小距离准则进行系统聚类分类。阀值为 。 计算各类间欧氏距离： 解：（1）将每一样本看作单独一类，得： …… ； ； 得距离矩阵D 0 : 0 0 0 0 0 0 D 0 ＊ （2）将最小距离 对应的类 和 合并为1类，得新的分类。 计算聚类后的距离矩阵D 1 ： 由D 0 递推出D 1 。 * * 第二章 聚类分析 Clustering §2.1 引言 §2.2 相似性测度和聚类准则 §2.3 基于距离阈值的聚类算法 1. 邻近聚类法 2. 最大最小距离算法 §2.4 分级聚类法 §2.5 动态聚类法 1. K-均值算法（或C－均值算法） 2. ISODATA算法（略提） §2.1 引言 二、说明： （1）“相似性”含义 ：有n个特征值则组成n维向量 ，称为该样本的特征向量。它相当于特征空间中的一个点，以特征空间中点间的距离函数作为模式相似性的测量，以“距离”作为模式分类的依据，距离越小，越“相似”。 一、概念：“物以类聚” 聚类分析：根据模式之间的相似性对模式进行 分类，是一种无导师的学习和分类方法。 ·特征矢量：设一个研究对象n个特征量测值分别为 ，它们构成n维特征矢量x，即 x为原对象的模式 对模式分类识别即对特征矢量分类识别 ·特征空间： 各种不同取值的x的全体构成n维空间，它称为n维特征空间，记为 ·相似性 若两个模式的特征仅存在微小的差别，则称两个模式是相似的。 ·相似性度量 用相似性函数，主要有距离函数 x1亮度 甲类工件 乙类工件 分界线（n≥3时为分界面） 被分类样品 落在那个区域，即被分类于该类。 x2纹理显著性 （2）聚类分析是否有效，与模式特征向量的分布形式有很大关系。对具体对象作聚类分析时，选取的特征向量是否合适非常关键。例：酱油与可乐。 §2.2 相似性测度和聚类准则 一、相似性测度：衡量模式之间相似性的一种尺度。 距离就是一种相似性的测度 。 复习：已知向量 ，则: 1、欧氏距离（Euclid，欧几里德） ——简称距离 设 、 为两个n维模式样本， ， ，则欧氏距离定义为： 距离越小，越相似。 使用时应注意模式各特征分量的量纲： D_Distance ① 各特征向量对应的维上，应取相同量纲，且相同的量纲要取相同的单位；同一向量的某几维是相同的物理量时，量纲相同，应取相同的单位。否则分类发生错误。 b 5,0 d 4,5 c 1,4 a 0,1 1 2 3 4 5 0 1 2 3 4 5 a ② 最好使特征数据标准化，使其与变量的量纲无关。 d 0.4,5 c 0.1,4 a 0,1 1 2 3 4 5 0 1 2 3 4 5 b 0.5,0 c b 5,0 c 1,0.4 d