层次聚类

层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为凝聚的、分裂的两种方案。

凝聚的层次聚类是一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足，绝大多数层次聚类方法属于这一类，它们只是在簇间相似度的定义上有所不同。
分裂的层次聚类与凝聚的层次聚类相反，采用自顶向下的策略，它首先将所有对象置于同一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件。

层次凝聚的代表。如果簇C1中的一个对象和簇C2中的一个对象之间的距离是所有属于不同簇的对象间欧式距离中最小的，C1和C2可能被合并。这是一种单连接方法，其每个簇可以被簇中的所有对象代表，两个簇之间的相似度由这两个簇中距离最近的数据点对的相似度来确定。

性能：

伪代码：

将每个对象当成一个初始簇

Repeat

….根据两个簇中最近的数据点找到最近的两个簇

….合并两个簇，生成新的簇的集合

Until达到定义的簇的数目

层次分裂的代表。首先将所有的对象初始化到一个簇中，然后根据一些原则（比如最邻近的最大欧式距离），将该簇分类。直到到达用户指定的簇数目或者两个簇之间的距离超过了某个阈值。

缺点是已做的分裂操作不能撤销，类之间不能交换对象。如果在某步没有选择好分裂点，可能会导致低质量的聚类结果。大数据集不太适用。

伪代码：

将所有对象整个当成一个初始簇

For ( i=1;i!=k;i++) Do Begin

….在所有簇中挑选出具有最大直径的簇；（定义：簇的直径为在一个簇中的任意两个数据点都有一个欧氏距离，这些距离中的最大值是簇的直径）

….找出所挑出簇里与其他点平均相异度最大的一个点放入splinter group，剩余的放入old party中。

….Repeat

……..在old party里找出到splinter group中点的最近距离不大于old party中点的最近距离的点，并将该点加入splinter group

….Until 没有新的old party的点被分配给splinter group；

Splinter group 和old party为被选中的簇分裂成的两个簇，与其他簇一起组成新的簇集合

END

cjmcv