层次聚类改进

一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底向上的还是自顶向下形成的，层次的聚类方法可以进一步分为凝聚的（agglomerative）和分裂的（divisive）层次聚类。

　　（1）凝聚的层次聚类：这种自底向上的策略首先将每个对象作为单独的一个簇，然后和并这些原子簇为越来越大的簇，直到所有的对像都在一个簇中，或者达到某个终止条件。

　　（2）分裂的层次聚类：这种自顶向下的策略与凝聚的层次聚类相反，它首先将所有的对象置于一个簇中。然后逐渐细分为越来越小的簇，直到每个对象在单独的一个簇中，或者达到一个终止条件，例如打到了某个希望的簇数目后者两个簇之间的距离超过了某个阀值。

　　例2 图2－3描述了一个凝聚的层次聚类方法AGNES（Agglomerative NESting）和一个分裂的层次聚类方法DIANA（Divisive Analysis）在一个包含五个对象的数据集合{a,b,c,d,e}上的处理过程。最初,AGNES将每个对象作为一个簇，然后这些簇根据某些准则一步步合并。例如，如果簇C1中的一个对象和簇 C2中的一个对象之间的距离使所有属于不同簇的对象间欧式距离最小的，C1和C2可能被合并。其每个簇可以被簇中所有对象代表，两个簇间的相似度由两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有对象最终合并为一个簇。

　　图2-3 在对象集合(a,b,c,d)上的凝聚与分裂层次聚类

　　在DIANA方法处理过程中，所有的对象都放在一个簇中。根据一些原则（如簇中最邻近的对象的最大欧氏距离），将该簇分裂。簇的分裂过程反复进行，直到最终每个新的簇只包含一个对象。

　　层次聚类方法尽管简单，但经常会遇到合并或分裂点选择的困难。这样的选择是非常关键的，因为一旦一组对象（合并或分裂）完成，它就不能被撤销，下一步的处理将在新完成的簇上进行。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会比较小。但是，已做的处理不能被撤消，聚类之间也不能交换对象。如果在某一步没有很好的选择合并或分裂的决定，可能会导致低质量的聚类结果。而且，这种聚类不具有很好的可伸缩性。因为合并或分裂的决定需要检查和估算