层次聚类算法课件

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