数据挖掘层次聚类课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,层次聚类,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,7.5,层次聚类方法,7.5层次聚类方法,2024/10/1,层次聚类,2,层次聚类方法概述,层次聚类方法将数据对象组成一棵聚类树。,根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的。,2022/10/10层次聚类2层次聚类方法概述层次聚类方法将,2024/10/1,层次聚类,3,层次聚类方法概述,凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。,分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。,层次凝聚的代表是,AGNES,算法。层次分裂的代表是,DIANA,算法。,2022/10/10层次聚类3层次聚类方法概述凝聚的层次聚类,2024/10/1,层次聚类,4,簇间距离,最小距离,2022/10/10层次聚类4簇间距离最小距离,2024/10/1,层次聚类,5,簇间距离,最大距离,2022/10/10层次聚类5簇间距离最大距离,2024/10/1,层次聚类,6,簇间距离,平均距离,2022/10/10层次聚类6簇间距离平均距离,2024/10/1,层次聚类,7,簇间距离,均值距离,2022/10/10层次聚类7簇间距离均值距离,2024/10/1,层次聚类,8,AGNES,算法,AGNES(AGglomerative NESting),算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。,两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。,聚类的合并过程反复进行直到所有的对象最终满足簇数目。,2022/10/10层次聚类8AGNES算法AGNES(AG,2024/10/1,层次聚类,9,AGNES,算法,输入：,n,个对象，终止条件簇的数目,k,。,输出：,k,个簇，达到终止条件规定簇数目。,(1),将每个对象当成一个初始簇；,(2)REPEAT,(3),根据两个簇中最近的数据点找到最近的两个簇；,(4),合并两个簇，生成新的簇的集合；,(5)UNTIL,达到定义的簇的数目；,2022/10/10层次聚类9AGNES算法输入：n个对象，,2024/10/1,层次聚类,10,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,结束,2022/10/10层次聚类10AGNES算法例题序号,2024/10/1,层次聚类,11,2022/10/10层次聚类11,2024/10/1,层次聚类,12,2022/10/10层次聚类12,2024/10/1,层次聚类,13,2022/10/10层次聚类13,2024/10/1,层次聚类,14,AGNES,特点,AGNES,算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤销，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。,2022/10/10层次聚类14AGNES特点AGNES算法,2024/10/1,层次聚类,15,DIANA,算法,DIANA,（,Divisive ANAlysis),算法是典型的分裂聚类方法。,在聚类中，用户能定义希望得到的簇数目作为一个结束条件。,2022/10/10层次聚类15DIANA算法DIANA（D,算法,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.,算法 DIANA（自顶向下分裂算法）,序号属性,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,终止,序号属性 1属性 2DIANA算法例题第1步，找到具有,2024/10/1,层次聚类,18,层次聚类方法的改进,层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。,改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。,下面介绍,3,个改进的层次聚类方法,BIRTH,，,ROCK,和,Chameleon,。,2022/10/10层次聚类18层次聚类方法的改进层次聚类方,2024/10/1,层次聚类,19,BIRCH,算法,BIRCH,（,Balanced Iterative Reducing and Clustering,）利用层次方法的平衡迭代归约和聚类,用聚类特征（,CF,）和聚类特征树来概括聚类描述。,该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。,2022/10/10层次聚类19BIRCH算法BIRCH（,2024/10/1,层次聚类,20,聚类特征（CF）,CF(Clustering Feature),：包含簇信息的三元组,(N,LS,SS),，,N,：簇的数据点；,LS,：线性和；,SS,：平方和,假定在簇,C1,中有三个点,(2,5),(3,2),(4,3),聚类特征是：,CF1=,=,2022/10/10层次聚类20聚类特征（CF）CF(Clu,2024/10/1,层次聚类,21,聚类特征,树,CF,树是一个具有两个参数分支因子,B,和阈值,T,的高度平衡树。,分支因子,B,：非叶节点可以拥有的孩子数,阈值,T,：叶子节点中的子聚类的最大直径,2022/10/10层次聚类21聚类特征树CF树是一个具有两,2024/10/1,层次聚类,22,阶段一：扫描数据库，建立一个初始的,CF,树，它可以被看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）中时，随着对象的插入，,CF,树被动态地构造，因此，,BIRTH,方法对增量或动态聚类也非常有效。,阶段二：采用某个聚类算法对,CF,树的叶节点进行聚类。在这个阶段可以执行任何聚类算法。,BIRCH,算法,2022/10/10层次聚类22 阶段一：扫描数据库，建立一,2024/10/1,层次聚类,23,ROCK,ROCK(Robust Clustering using linKs,使用连接的鲁棒聚类,大多数聚类算法在进行聚类时只估计点与点之间的相似度，即在每一步中那些最相似的几个点合并到一个簇中。这种“局部”方法很容易导致错误。例如：两个完全不同的簇可能有少数几个点的距离较近，仅仅依据点与点之间的相似度来做出聚类决定就会导致这两个簇合并。,ROCK,采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类。,2022/10/10层次聚类23ROCKROCK(Robus,2024/10/1,层次聚类,24,ROCK,两个概念：近邻和链接,近邻：两个点,pi,和,pj,是近邻，如果,sim(pi,pj)=,sim,是相似度函数，,是指定的阈值,链接：两个点,pi,和,pj,的链接数定义为这两点的共同近邻个数。,由于在确定点对之间的关系时考虑邻近的数据点，因此比只关注相似度的聚类方法更加鲁棒。,2022/10/10层次聚类24ROCK两个概念：近邻和链接,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