5.2.2  层次聚类算法

层次聚类算法分为凝聚层次聚类算法和分裂层次聚类算法。凝聚层次聚类认为每一个对象是一个簇，遵循自下而上的原则逐步归并簇，继而构成很大的簇，反复这一过程直到图像中所有的对象都在同一个簇中或满足某一约束条件时，该算法结束。分裂层次聚类的过程与凝聚层次聚类的过程相反，分裂层次聚类认为图像中所有的对象已经在一个簇中，遵循自上而下的原则逐渐将图像中的对象从一个簇中划分为越来越小的簇，反复这一过程直到图像中每一个对象被分为单独的一簇或满足某一约束条件时，该算法结束。经常使用的层次聚类算法有BIRCH算法、ROCK算法、CURE算法、Chameleon算法等。BIRCH算法通过扫描数据来建立一个有关聚类结构的CF树，并对此CF树的叶节点进行聚类；ROCK算法根据相似度阈值与共同邻域的基本概念计算出图像的相似度矩阵，接着从图像的相似度矩阵中构建一个稀疏图，并对该稀疏图进行聚类；CURE算法依据收缩因子的值调整每个簇的大小和形状，从而形成不同类型的簇而完成聚类；Chameleon算法依据若图像中存在两个簇之间相似性以及互联性高度相关的对象，则动态地合并这两个簇，重复上述过程直到不能合并为止，该算法结束。

层次聚类算法虽然易处理不同粒度水平上的数据，但是该算法的结束条件模糊；其扩展性不良，因而要求预先算出图像中大部分的簇才可完成合并或分裂操作；并且该算法的归并或割裂簇的处理是不可修正的，因此该算法聚类质量较低。