层次聚类算法.ppt
《层次聚类算法.ppt》由会员分享,可在线阅读,更多相关《层次聚类算法.ppt(34页珍藏版)》请在三一文库上搜索。
1、7.5层次聚类方法,2019/6/3,层次聚类,2,层次聚类方法概述,层次聚类方法将数据对象组成一棵聚类树。 根据层次分解是自底向上(合并)还是自顶向下(分裂),进一步分为凝聚的和分裂的。,2019/6/3,层次聚类,3,层次聚类方法概述,凝聚的层次聚类:一种自底向上的策略,首先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到某个终结条件被满足。 分裂的层次聚类:采用自顶向下的策略,它首先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇,直到达到了某个终结条件。 层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。,2019/6/3,层次聚类,4,簇间距离,最小距离,
2、2019/6/3,层次聚类,5,簇间距离,最大距离,2019/6/3,层次聚类,6,簇间距离,平均距离,2019/6/3,层次聚类,7,簇间距离,均值距离,2019/6/3,层次聚类,8,AGNES算法,AGNES(AGglomerative NESting)算法最初将每个对象作为一个簇,然后这些簇根据某些准则被一步步地合并。 两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。 聚类的合并过程反复进行直到所有的对象最终满足簇数目。,2019/6/3,层次聚类,9,AGNES算法,输入:n个对象,终止条件簇的数目k。 输出:k个簇,达到终止条件规定簇数目。 (1)将每个对象当成一
3、个初始簇; (2)REPEAT (3)根据两个簇中最近的数据点找到最近的两个簇; (4)合并两个簇,生成新的簇的集合; (5)UNTIL达到定义的簇的数目;,2019/6/3,层次聚类,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
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结束,2019/6/3,层次聚类,11,2019/6/3,层次聚类,12,2019/6
5、/3,层次聚类,13,2019/6/3,层次聚类,14,AGNES特点,AGNES算法比较简单,但经常会遇到合并点选择的困难。假如一旦一组对象被合并,下一步的处理将在新生成的簇上进行。已做处理不能撤销,聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定,可能会导致低质量的聚类结果。,2019/6/3,层次聚类,15,DIANA算法,DIANA(Divisive ANAlysis)算法是典型的分裂聚类方法。 在聚类中,用户能定义希望得到的簇数目作为一个结束条件。,算法 DIANA(自顶向下分裂算法) 输入:n个对象,终止条件簇的数目k。 输出:k个簇,达到终止条件规定簇数目。 (1)将
6、所有对象整个当成一个初始簇; (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为
7、被选中的簇分裂成的两个簇,与其它簇一起组成新的簇集合。 (9) END.,序号 属性 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,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放到spl
8、inter 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 g
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 层次 算法
链接地址:https://www.31doc.com/p-2903331.html