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