层次聚类算法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,层次聚类,*,7.5层次聚类方法,11/11/2024,1,层次聚类方法概述,层次聚类方法将数据对象组成一棵聚类树。,根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的。,11/11/2024,2,层次聚类,层次聚类方法概述,凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。,分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。,层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。,11/11/2024,3,层次聚类,簇间距离,最小距离,11/11/2024,4,层次聚类,簇间距离,最大距离,11/11/2024,5,层次聚类,簇间距离,平均距离,11/11/2024,6,层次聚类,簇间距离,均值距离,11/11/2024,7,层次聚类,AGNES算法,AGNES(AGglomerative NESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。,两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。,聚类的合并过程反复进行直到所有的对象最终满足簇数目。,11/11/2024,8,层次聚类,AGNES算法,输入：n个对象，终止条件簇的数目k。,输出：k个簇，达到终止条件规定簇数目。,(1)将每个对象当成一个初始簇；,(2)REPEAT,(3)根据两个簇中最近的数据点找到最近的两个簇；,(4)合并两个簇，生成新的簇的集合；,(5)UNTIL达到定义的簇的数目；,11/11/2024,9,层次聚类,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 1,2,3,4,，,5,6,，,7,8,1 5,6,，,7,8 1,2,3,4,，,5,6,7,8,结束,11/11/2024,10,层次聚类,11/11/2024,11,层次聚类,11/11/2024,12,层次聚类,11/11/2024,13,层次聚类,AGNES特点,AGNES算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤销，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。,11/11/2024,14,层次聚类,DIANA算法,DIANA（Divisive ANAlysis)算法是典型的分裂聚类方法。,在聚类中，用户能定义希望得到的簇数目作为一个结束条件。,11/11/2024,15,层次聚类,算法 DIANA（自顶向下分裂算法）,输入：n个对象，终止条件簇的数目k。,输出：k个簇，达到终止条件规定簇数目。,（1）将所有对象整个当成一个初始簇；,（2）FOR（i=1;ik;i+)DO BEGIN,（3）在所有簇中挑出具有最大直径的簇C；,（4）找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩余的放在old party中；,（5）REPEAT,（6）在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。,（7）UNTIL 没有新的old party的点被分配给splinter group；,（8）splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。,（9）END.,11/11/2024,16,层次聚类,序号属性 1属性 2,111,212,321,422,534,635,744,845,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放到splinter group中，剩余点在old party中。,第2步，在old party里找出到最近的splinter group中的点的距离不大于到old party中最近的点的距离的点，将该点放入splinter group中，该点是2。,第3步，重复第2步的工作，splinter group中放入点3。,第4步，重复第2步的工作，splinter group中放入点4。,第5步，没有在old party中的点放入了splinter group中且达到终止条件（k=2），程序终止。如果没有到终止条件，因该从分裂好的簇中选一个直径最大的簇继续分裂。,步骤具有最大直径的簇splinter groupOld party,11，2，3，4，5，6，7，8 12，3，4，5，6，7，8,21，2，3，4，5，6，7，8 1，23，4，5，6，7，8,31，2，3，4，5，6，7，8 1，2，34，5，6，7，8,41，2，3，4，5，6，7，8 1，2，3，45，6，7，8,51，2，3，4，5，6，7，8 1，2，3，45，6，7，8 终止,11/11/2024,17,层次聚类,层次聚类方法的改进,层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。,改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。,下面介绍3个改进的层次聚类方法BIRTH，ROCK和Chameleon。,11/11/2024,18,层次聚类,BIRCH算法,BIRCH（Balanced Iterative Reducing and Clustering）利用层次方法的平衡迭代归约和聚类,用聚类特征（CF）和聚类特征树来概括聚类描述。,该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。,11/11/2024,19,层次聚类,聚类特征（CF）,CF(Clustering Feature)：包含簇信息的三元组(N,LS,SS)，N：簇的数据点；LS：线性和；SS：平方和,假定在簇C1中有三个点(2,5),(3,2),(4,3),聚类特征是：,CF1=,=,11/11/2024,20,层次聚类,聚类特征树,CF树是一个具有两个参数分支因子B和阈值T的高度平衡树。,分支因子B：非叶节点可以拥有的孩子数,阈值T：叶子节点中的子聚类的最大直径,11/11/2024,21,层次聚类,阶段一：扫描数据库，建立一个初始的CF树，它可以被看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）中时，随着对象的插入，CF树被动态地构造，因此，BIRTH方法对增量或动态聚类也非常有效。,阶段二：采用某个聚类算法对CF树的叶节点进行聚类。在这个阶段可以执行任何聚类算法。,BIRCH算法,11/11/2024,22,层次聚类,ROCK,ROCK(Robust Clustering using linKs,使用连接的鲁棒聚类,大多数聚类算法在进行聚类时只估计点与点之间的相似度，即在每一步中那些最相似的几个点合并到一个簇中。这种“局部”方法很容易导致错误。例如：两个完全不同的簇可能有少数几个点的距离较近，仅仅依据点与点之间的相似度来做出聚类决定就会导致这两个簇合并。,ROCK采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类。,11/11/2024,23,层次聚类,ROCK,两个概念：近邻和链接,近邻：两个点pi和pj是近邻，如果sim(pi,pj)=,sim是相似度函数，是指定的阈值,链接：两个点pi和pj的链接数定义为这两点的共同近邻个数。,由于在确定点对之间的关系时考虑邻近的数据点，因此比只关注相似度的聚类方法更加鲁棒。,11/11/2024,24,层次聚类,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系数，,很容易导致错误。,11/11/2024,25,层次聚类,另一方面，如果考虑链接数，可以成功地把这些事务划分到恰当地簇中。,例如：令=0.5，则C2中的事务,a,b,f与a,b,g的链接数是5,而C2中的事务 a,b,f与C1中的事,务a,b,c之间的链接数是3.,因此，ROCK能够正确地区分出两个不同,的事务簇。,11/11/2024,26,层次聚类,Chameleon,利用动态建模的层次聚类算法。采用动态建模确定簇之间的相似度。,簇之间的相似度依据簇中对象的互连度和簇的邻近度，即如果两个簇的互连性都很高且它们又靠得很近则将其合并。,11/11/2024,27,层次聚类,变色龙算法的聚类步骤,Chameleon 算法首先由数据集构造成一个K-最近邻图Gk,再通过一个图的划分算法将图Gk 划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇；,11/11/2024,28,层次聚类,K最近邻图,Gk 图中的每个点表示数据集中的一个数据点；若数据点ai 到另一个数据点bi 的距离值是所有数据点到数据点bi 的距离值中K个最小值之一,则称数据点ai 是数据点bi 的K-最临近对象，则在这两个点之间加一条带权边,边的权重表示这两个数据点之间的近似度,即它们之间的距离越大,则它们之间的近似度越小,它们之间的边的权重也越小。,11/11/2024,29,层次聚类,割边,图划分算法划分k近邻图，使得割边最小，即簇C划分为两个子簇Ci和Cj时需切断的边的加权和最小。,割边用EC(Ci,Cj)表示，用于评估两个簇之间的绝对互连度。,Chameleon根据每对簇Ci和Cj的相对互连度RI(Ci,Cj)和相对接近度RC(Ci,Cj)来决定它们之间的相似度。,11/11/2024,30,层次聚类,相对互连度(RI),相对互连性RICi,Cj:子簇Ci 和子簇Cj之间绝对互连度关于两个簇间的内部互连度的规范化。,绝对互连度ECCi,Cj:连接子簇Ci 和子簇Cj 之间的边的权重之和。,内部互连度ECCi:是将簇Ci划分成大致相等的两部分的割边的最小和。,11/11/2024,31,层次聚类,相对近似度(RC),相对接近度RCCi,Cj:子簇Ci 和子簇Cj之间绝对接近度关于两个簇间的内部接近度的规范化。,绝对接近度TCCi,Cj:连接子簇Ci 和子簇Cj 之间的边的平均权重。,内部接近度TCCi:一个子簇C