[工学]16 聚类分析.ppt

聚 类 分 析 一 简介 聚类分析是无监督学习的重要方法之一，是寻找处理客观分类的方法。 聚类分析历史很短（30多年），没有形成合适的模型，不论是聚类统计量或聚类方法都没有定型，但是大量事实证明，他是一种行之有效的方法。 二 聚类统计量 聚类统计量可分为距离和相似系数两类。 设有n个样品x1，x2，…，xn, 每个样品都有m个指标， 用一个m维向量表示，记 xi=(xi1, xi2, …, xim)T, i=1,2,…,m (1) 距离距离统计量 绝对值距离： 欧氏距离： Minkowski距离： 马氏距离： （2） 相似系数 相关系数： 其中 是第i个样品的各指标的平均值和样本离差。 夹角余铉： 指数相似系数： 设X＝{x1, x2, …, xn}是样本集，G1, G2, … , Gg是X的非空子集， 且满足条件 则称G1, G2, … , Gg 是X的一个分类。 用D (p, q) 表示类Gp 和类Gq之间的和距离，且设它们的样本数分别为s和t，均值为 。d (xi , yj) 表示xi 与 yj的距离。 （3）类与类之间的距离 三 系统聚类法 基本思想： 假定n个样本各自成一类 选择距离最近的两类并成一新类 计算新类与其他类的距离 重复(2)(3)，直到所有的样本聚成一类 系统聚类法的聚合过程可用一种叫做聚类图(或谱系图)的图形表示出来 算法步骤 (1)每个样本作一类， 选择样本间距离计算公式计算d (xi, xj), 记做dij, 得矩阵 (2) 在D (0)各元素中找出最小者(对角线除外)， 设为di1, dj1,则将类Gi1, Gj1合并成新类Gn+1, 同时去掉类Gi1, Gj1，共剩下n-1类。 (3) 选择类间距离计算公式计算新类与剩余各类得距离，原剩余类间得距离不变，得矩阵D (1). (4) 重复(2) (3) 两步， 直到剩下得类数为1或者距离高于临界值为止。 (5) 画出聚类图 (6) 确定分类数以及类。 例1：设X={(5,5), (1,5), (4,5), (4.5, 5), (5,1), (4.7, 1)},试对X作聚类分析。 解: (1)让X中6个样本各成一类，按殴氏距离计算出距离矩阵。 (2) 合并G5和G6得G7，按距离最短公式D(i,7)=min(di5 , di6)计算类间距离得 四 逐步聚类法（动态聚类法） 系统聚类法得优缺点： 分类准确，客观 当样本数大时，计算距离很费事 改进办法：逐步聚类法 先选取若干个凝聚点 将样本初始分类 根据某些准则调整分类 重复上述过程，直到分类稳定为止 确定初始分类: 确定初始凝聚点 凭经验：经验选取初始凝聚点 重心法：先将样本粗糙分类，计算每一类得重心，以这些重心为凝聚点 密度法：先任取两个正数c1和c2(c1c2),以每个样本的数值点为球心，以c1为半径作小球，落在球内(包括球面)的样本个数称为此样本的密度。选择密度最大的那个样本作为第一凝聚点，再考虑密度次大的样本点，如果它与第一凝聚点的距离小于c2，则舍去该点，否则选为第二凝聚点。依次计算每一新的侯选凝聚点与已选的凝聚点的距离，距离不小于c2 的作为新的凝聚。一般地，取c2＝2c1。 调整分类 调整分类可采用按批调整法。根据初始分类，计算出各类的重心，以这些重心作新的凝聚点。再根据已定义的样本间距离对各样本按最近凝聚点归类，算出新类的重心作为新的凝聚点。反复几次，直到新的凝聚点都与前一次的老凝聚点重合为止。 例2：从21家工厂中抽取同类产品，每个产品测了两个指标，分别记做xi1, xi2, i=1,2,…,21.其数据如下表所示： 试对上述产品作聚类分析 解：取c1=2, c2=4, 以xi为圆心，以2 为半径作圆，得到各样本得密度如下表： 以密度最大的点x13为第一凝聚点。密度次之为x9 ,x18 , x19 ，他们与的殴氏距离为d9,13=9.064, d18,13=54, d19,13=3.614, d9,18=6. 714, 故取x9 ,x18 为第二和第三凝聚点。密度为2且与x13 , x9, x18 距离大于4的点是x2 ,x3 ,x4, 取x2为第四凝聚点，又x3 ,x4与x2的距离均小于4，且密度大于1又与前面四个凝聚点的距离大于4的点没有。 密度为0 的又与前面四个凝聚点的距离大于4 的点是x21，便取x21为第五凝聚点。 当上述五个凝聚点确定后，将每个样本按殴氏距离向最近的凝聚点归类，初始分类便确定为{x1, x2, x3, x4}, {x5, x6, x7,