agnes算法4-5PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,AGNES算法,10.3层次聚类方法,2,层次聚类,AGNES,方法,凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，逐步合并，直到某个终结条件被满足。,层次凝聚的代表是,AGNES,算法,3,AGNES,算法,AGNES(Agglomerative NESting),算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并，使用单链接方法。,两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。此外当两个簇最近距离超过用户给定的阈值时聚类过程就会终止。,聚类的合并过程反复进行直到所有的对象最终满足簇数目。,AGNES,算法,例如，如果簇,C1,中的一个对象和簇,C2,中的一个对象之间的距离是所属不同簇的对象间欧式距离中最小的，则,C1,和,C2,可能被合并。,两个簇之间的相似度计算公式为：dist(m1,m2,m3,m4)=min(dist(m1,m3),dist(m1,m4),dist(m2,m3),dist(m2,m4)。,4,4/19/2025,5,簇间距离,最小距离,6,AGNES,算法,输入：,n,个对象，终止条件簇的数目,k,。,输出：,k,个簇，达到终止条件规定簇数目。,(1),将每个对象当成一个初始簇；,(2),重复；,(3),根据两个簇中最近的数据点找到最近的两个簇；,(4),合并两个簇，生成新的簇的集合；,(5),直到达到定义的簇的数目；,7,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,结束,AGNES,算法缺点,（1）简单，但遇到合并点选择困难的情况。,（2）一旦一组对象被合并，,下一步的处理将在新生成的簇上进行，已做处理不能撤销，聚类之间也不能交换对象。,（3）算法的复杂度为O(n的平方)，不适合大数据集计算。,8,4/19/2025,9,4/19/2025,10,4/19/2025,11,4/19/2025,12,4/19/2025,13,4/19/2025,14,4/19/2025,15,4/19/2025,运行结果,16,4/19/2025,17,4/19/2025,层次聚类其它算法,1.,分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。层次分裂的代表是,DIANA,算法。,2.BIRCH,算法：聚类特征，聚类特征树,3.ROCK,：近邻，链接数,4.Chameleon,：相对互边度，相对接近度,18,4/19/2025,DIANA,算法,DIANA,（,Divisive ANAlysis),算法是典型的分裂聚类方法。,在聚类中，用户能定义希望得到的簇数目作为一个结束条件。,19,算法,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.,20,4/19/2025,序号属性,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,终止,21,4/19/2025,层次聚类方法的改进,层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。,改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。,下面介绍,1,个改进的层次聚类方法,BIRTH,。,22,23,BIRCH,算法,BIRCH,（,Balanced Iterative Reducing and Clustering,）利用层次方法的平衡迭代归约和聚类,用聚类特征（,CF,）和聚类特征树来概括聚类描述。,该算法通过聚类特征可以方便地进行形心,X0,、半径,R,、直径,D,。,聚类特征（CF）,CF(Clustering Feature),：包含簇信息的三元组,(N,LS,SS),，,N,：簇的数据点；,LS,：,n,个点的线性和；,SS,：数据点的平方和,例如：,簇C1中有三个数据点：（2,3），（4,5），（5,6），则CF1=3，（2+4+5,3+5+6），（22+42+52,32+52+62）=3，（11,14），（45,70），同样的，簇C2的CF2=4，（40,42），（100,101），那么，由簇C1和簇C2合并而来的簇C3的聚类特征CF3计算如下：,CF3=3+4,（11+40,14+42），（45+100,70+101）=7，（51,56），（145,171）,24,聚类特征,树,CF,树是一个具有两个参数分支因子,B,和阈值,T,的高度平衡树。,分支因子,B,：非叶节点可以拥有的孩子数。,阈值,T,：叶子节点中的子聚类的最大直径。,这两个参数影响结果数的大小。,25,阶段一：扫描数据库，建立一个初始的,CF,树，它可以被看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）中时，随着对象的插入，,CF,树被动态地构造，因此，,BIRTH,方法对增量或动态聚类也非常有效。,阶段二：采用某个聚类算法对,CF,树的叶节点进行聚类，把稀疏的簇当做离群点删除，而把稠密的簇合并为更大的簇，在这个阶段可以执行任何聚类算法。,BIRCH,算法,26,BIRCH,优点,1.,节省内在。叶子节点放在磁盘分区上，非叶子节点仅仅是存储了一个CF值，外加指向父节点和孩子节点的指针。,2.,快。合并两个两簇只需要两个CF算术相加即可；计算两个簇的距离只需要用到(N,LS,SS)这三个值足矣。,3.,一遍扫描数据库即可建立B树。,4.,由于B树是高度平衡的，所以在树上进行插入或查找操作很快。,27,4/19/2025,BIRCH,缺点,1.,结果依赖于数据点的插入顺序。本属于同一个簇的点可能由于插入顺序相差很远而分到不同的簇中，即使同一个点在不同的时刻被插入，也会被分到不同的簇中。,2.,对非球状的簇聚类效果不好。这取决于簇直径和簇间距离的计算方法。,3.,对高维数据聚类效果不好。,4.,由于每个节点只能包含一定数目的子节点，最后得出来的簇可能和自然簇相差很大。,28,4/19/2025,29,THANKS,