《数据挖掘层次聚类》PPT课件.pptVIP

7 5层次聚类方法 2020 2 9 层次聚类 2 层次聚类方法概述 层次聚类方法将数据对象组成一棵聚类树 根据层次分解是自底向上 合并 还是自顶向下 分裂 进一步分为凝聚的和分裂的 2020 2 9 层次聚类 3 层次聚类方法概述 凝聚的层次聚类 一种自底向上的策略 首先将每个对象作为一个簇 然后合并这些原子簇为越来越大的簇 直到某个终结条件被满足 分裂的层次聚类 采用自顶向下的策略 它首先将所有对象置于一个簇中 然后逐渐细分为越来越小的簇 直到达到了某个终结条件 层次凝聚的代表是AGNES算法 层次分裂的代表是DIANA算法 2020 2 9 层次聚类 4 簇间距离 最小距离 2020 2 9 层次聚类 5 簇间距离 最大距离 2020 2 9 层次聚类 6 簇间距离 平均距离 2020 2 9 层次聚类 7 簇间距离 均值距离 2020 2 9 层次聚类 8 AGNES算法 AGNES AGglomerativeNESting 算法最初将每个对象作为一个簇 然后这些簇根据某些准则被一步步地合并 两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定 聚类的合并过程反复进行直到所有的对象最终满足簇数目 2020 2 9 层次聚类 9 AGNES算法 输入 n个对象 终止条件簇的数目k 输出 k个簇 达到终止条件规定簇数目 1 将每个对象当成一个初始簇 2 REPEAT 3 根据两个簇中最近的数据点找到最近的两个簇 4 合并两个簇 生成新的簇的集合 5 UNTIL达到定义的簇的数目 2020 2 9 层次聚类 10 AGNES算法例题 序号属性1属性2111212321422534635744845 第1步 根据初始簇计算每个簇之间的距离 随机找出距离最小的两个簇 进行合并 最小距离为1 合并后1 2两个点合并为一个簇 第2步 对上一次合并后的簇计算簇间距离 找出距离最近的两个簇进行合并 合并后3 4点成为一簇 第3步 重复第2步的工作 5 6点成为一簇 第4步 重复第2步的工作 7 8点成为一簇 第5步 合并 1 2 3 4 成为一个包含四个点的簇 第6步 合并 5 6 7 8 由于合并后的簇的数目已经达到了用户输入的终止条件 程序终止 步骤最近的簇距离最近的两个簇合并后的新簇11 1 2 1 2 3 4 5 6 7 8 1 3 4 1 2 3 4 5 6 7 8 1 5 6 1 2 3 4 5 6 7 8 1 7 8 1 2 3 4 5 6 7 8 1 1 2 3 4 1 2 3 4 5 6 7 8 1 5 6 7 8 1 2 3 4 5 6 7 8 结束 2020 2 9 层次聚类 11 2020 2 9 层次聚类 12 2020 2 9 层次聚类 13 2020 2 9 层次聚类 14 AGNES特点 AGNES算法比较简单 但经常会遇到合并点选择的困难 假如一旦一组对象被合并 下一步的处理将在新生成的簇上进行 已做处理不能撤销 聚类之间也不能交换对象 如果在某一步没有很好的选择合并的决定 可能会导致低质量的聚类结果 2020 2 9 层次聚类 15 DIANA算法 DIANA DivisiveANAlysis 算法是典型的分裂聚类方法 在聚类中 用户能定义希望得到的簇数目作为一个结束条件 算法DIANA 自顶向下分裂算法 输入 n个对象 终止条件簇的数目k 输出 k个簇 达到终止条件规定簇数目 1 将所有对象整个当成一个初始簇 2 FOR i 1 i k i DOBEGIN 3 在所有簇中挑出具有最大直径的簇C 4 找出C中与其它点平均相异度最大的一个点p并把p放入splintergroup 剩余的放在oldparty中 5 REPEAT 6 在oldparty里找出到最近的splintergroup中的点的距离不大于到oldparty中最近点的距离的点 并将该点加入splintergroup 7 UNTIL没有新的oldparty的点被分配给splintergroup 8 splintergroup和oldparty为被选中的簇分裂成的两个簇 与其它簇一起组成新的簇集合 9 END 序号属性1属性2111212321422534635744845 DIANA算法例题 第1步 找到具有最大直径的簇 对簇中的每个点计算平均相异度 假定采用是欧式距离 1的平均距离 1 1 1 414 3 6 4 24 4 47 5 7 2 96类似地 2的平均距离为2 526 3的平均距离为2 68 4的平均距离为2 18 5的平均距离为2 18 6的平均距离为2 68 7的平均距离为2 526 8的平均距离为2 96 找出平均相异度最大的点1放到splintergroup中 剩余点在oldparty中 第2步 在oldparty里找出到最近的splintergroup中的点的距离不大于到oldparty中最近的点的距离的点 将该点放入splintergroup中 该点是2 第3步 重复第2步的工作 splintergroup中放入点3 第4步 重复第2步的工作 splintergroup中放入点4 第5步 没有在oldparty中的点放入了splintergroup中且达到终止条件 k 2 程序终止 如果没有到终止条件 因该从分裂好的簇中选一个直径最大的簇继续分裂 步骤具有最大直径的簇splintergroupOldparty1 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 2 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 3 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 5 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 终止 2020 2 9 层次聚类 18 层次聚类方法的改进 层次聚类方法尽管简单 但经常会遇到合并或分裂点的选择的困难 改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成 形成多阶段聚类 下面介绍3个改进的层次聚类方法BIRTH ROCK和Chameleon 2020 2 9 层次聚类 19 BIRCH算法 BIRCH BalancedIterativeReducingandClustering 利用层次方法的平衡迭代归约和聚类用聚类特征 CF 和聚类特征树来概括聚类描述 该算法通过聚类特征可以方便地进行中心 半径 直径及类内 类间距离的运算 2020 2 9 层次聚类 20 聚类特征 CF CF ClusteringFeature 包含簇信息的三元组 N LS SS N 簇的数据点 LS 线性和 SS 平方和假定在簇C1中有三个点 2 5 3 2 4 3 聚类特征是 CF1 2020 2 9 层次聚类 21 聚类特征树 CF树是一个具有两个参数分支因子B和阈值T的高度平衡树 分支因子B 非叶节点可以拥有的孩子数阈值T 叶子节点中的子聚类的最大直径 2020 2 9 层次聚类 22 阶段一 扫描数据库 建立一个初始的CF树 它可以被看作一个数据的多层压缩 试图保留数据内在的聚类结构 当一个对象被插入到最近的叶节点 子聚类 中时 随着对象的插入 CF树被动态地构造 因此 BIRTH方法对增量或动态聚类也非常有效 阶段二 采用某个聚类算法对CF树的叶节点进行聚类 在这个阶段可以执行任何聚类算法 BIRCH算法 2020 2 9 层次聚类 23 ROCK ROCK RobustClusteringusinglinKs 使用连接的鲁棒聚类大多数聚类算法在进行聚类时只估计点与点之间的相似度 即在每一步中那些最相似的几个点合并到一个簇中 这种 局部 方法很容易导致错误 例如 两个完全不同的簇可能有少数几个点的距离较近 仅仅依据点与点之间的相似度来做出聚类决定就会导致这两个簇合并 ROCK采用一种比较全局的观点 通过考虑成对点的邻域情况进行聚类 2020 2 9 层次聚类 24 ROCK 两个概念 近邻和链接近邻 两个点pi和pj是近邻 如果sim pi pj sim是相似度函数 是指定的阈值链接 两个点pi和pj的链接数定义为这两点的共同近邻个数 由于在确定点对之间的关系时考虑邻近的数据点 因此比只关注相似度的聚类方法更加鲁棒 ROCK 例 购物篮数据库包含关于商品a b g的事物记录 簇C1涉及商品 a b c d e 簇C2涉及商品 a b f g 假设 只考虑相似度而忽略邻域信息 C1中 a b c 和 b d e 之间的Jaccard系数是0 2而C1中的 a b c 和C2中的 a b f 的Jaccard系数是0 5说明 仅根据Jaccard系数 很容易导致错误 另一方面 如果考虑链接数 可以成功地把这些事务划分到恰当地簇中 例如 令 0 5 则C2中的事务 a b f 与 a b g 的链接数是5而C2中的事务 a b f 与C1中的事务 a b c 之间的链接数是3 因此 ROCK能够正确地区分出两个不同的事务簇 2020 2 9 层次聚类 27 Chameleon 利用动态建模的层次聚类算法 采用动态建模确定簇之间的相似度 簇之间的相似度依据簇中对象的互连度和簇的邻近度 即如果两个簇的互连性都很高且它们又靠得很近则将其合并 2020 2 9 层次聚类 28 变色龙算法的聚类步骤 Chameleon算法首先由数据集构造成一个K 最近邻图Gk 再通过一个图的划分算法将图Gk划分成大量的子图 每个子图代表一个初始子簇 最后用一个凝聚的层次聚类算法反复合并子簇 找到真正的结果簇 2020 2 9 层次聚类 29 K最近邻图 Gk图中的每个点表示数据集中的一个数据点 若数据点ai到另一个数据点bi的距离值是所有数据点到数据点bi的距离值中K个最小值之一 则称数据点ai是数据点bi的K 最临近对象 则在这两个点之间加一条带权边 边的权重表示这两个数据点之间的近似度 即它们之间的距离越大 则它们之间的近似度越小 它们之间的边的权重也越小 2020 2 9 层次聚类 30 割边 图划分算法划分k近邻图 使得割边最小 即簇C划分为两个子簇Ci和Cj时需切断的边的加权和最小 割边用EC Ci Cj 表示 用于评估两个簇之间的绝对互连度 Chameleon根据每对簇Ci和Cj的相对互连度RI Ci Cj 和相对接近度RC Ci Cj 来决定它们之间的相似度 2020 2 9 层次聚类 31 相对互连度 RI 相对互连性RI Ci Cj 子簇Ci和子簇Cj之间绝对互连度关于两个簇间的内部互连度的规范化 绝对互连度EC Ci Cj 连接子簇Ci和子簇Cj之间的边的权重之和 内部互连度EC Ci 是将簇Ci划分成大致相等的两部分的割边的最小和 2020 2 9 层次聚类 32 相对近似