agnes算法4-5

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