文档介绍：数据挖掘层次聚类
第1页，共34页，编辑于2022年，星期六
*
层次聚类
*
层次聚类方法概述
层次聚类方法将数据对象组成一棵聚类树。
根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的。
} {1,2,3,4}，{5,6,7,8}结束
第10页，共34页，编辑于2022年，星期六
*
层次聚类
*
第11页，共34页，编辑于2022年，星期六
*
层次聚类
*
第12页，共34页，编辑于2022年，星期六
*
层次聚类
*
第13页，共34页，编辑于2022年，星期六
*
层次聚类
*
AGNES特点
AGNES算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤销，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。
第14页，共34页，编辑于2022年，星期六
*
层次聚类
*
DIANA算法
DIANA（Divisive ANAlysis)算法是典型的分裂聚类方法。
在聚类中，用户能定义希望得到的簇数目作为一个结束条件。
第15页，共34页，编辑于2022年，星期六
算法 DIANA（自顶向下分裂算法）
输入：n个对象，终止条件簇的数目k。
输出：k个簇，达到终止条件规定簇数目。
（1）将所有对象整个当成一个初始簇；
（2） FOR （i=1; i≠k; 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.
第16页，共34页，编辑于2022年，星期六
序号 属性 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+++++5）/7=
类似地，；；；；；；。
找出平均相异度最大的点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 group Old party
1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}
2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8}
3 {1，2，3，4，5，6，7，8} {1，2，3} {4，5，6，7，8}
4 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8}
5 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8} 终止
第17页，共34页，编辑于2022年，星期六
*
层次聚类
*
层次聚类方法的改进
层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。
改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。