数据挖掘与层次聚类 .ppt

* 层次聚类 * 相对互连度(RI) 相对互连性RI{Ci ,Cj} :子簇Ci 和子簇Cj之间绝对互连度关于两个簇间的内部互连度的规范化。 绝对互连度EC{Ci ,Cj} :连接子簇Ci 和子簇Cj 之间的边的权重之和。 内部互连度EC{Ci} :是将簇Ci划分成大致相等的两部分的割边的最小和。 * 层次聚类 * 相对近似度(RC) 相对接近度RC{Ci ,Cj} :子簇Ci 和子簇Cj之间绝对接近度关于两个簇间的内部接近度的规范化。 绝对接近度TC{Ci ,Cj} :连接子簇Ci 和子簇Cj 之间的边的平均权重。 内部接近度TC{Ci} :一个子簇Ci 做最小二分时需要去掉的边的平均权重。 * 层次聚类 * 小结 凝聚层次聚类算法AGENES 分裂层次聚类算法DIANA BIRCH：聚类特征，聚类特征树 ROCK：近邻，链接数 Chameleon：相对互边度，相对接近度 * 层次聚类 * 层次聚类 7.5层次聚类方法 * 层次聚类 * 层次聚类方法概述 层次聚类方法将数据对象组成一棵聚类树。 根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的。 * 层次聚类 * 层次聚类方法概述 凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。 分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。 层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。 * 层次聚类 * 簇间距离 最小距离 * 层次聚类 * 簇间距离 最大距离 * 层次聚类 * 簇间距离 平均距离 * 层次聚类 * 簇间距离 均值距离 ? ? * 层次聚类 * AGNES算法 AGNES(AGglomerative NESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。 两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。 聚类的合并过程反复进行直到所有的对象最终满足簇数目。 * 层次聚类 * AGNES算法 输入：n个对象，终止条件簇的数目k。 输出：k个簇，达到终止条件规定簇数目。 (1)将每个对象当成一个初始簇； (2)REPEAT (3)根据两个簇中最近的数据点找到最近的两个簇； (4)合并两个簇，生成新的簇的集合； (5)UNTIL达到定义的簇的数目； * 层次聚类 * AGNES算法例题 序号 属性1 属性2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5 第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}，由于合并后的簇的数目已经达到了用户输入的终止条件，程序终止。 步骤 最近的簇距离 最近的两个簇 合并后的新簇 1 1 {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}