agnes算法4-5省名师优质课获奖课件市赛课一等奖课件.ppt

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