5.3.2.1　DIANA算法基本思想

分裂层次聚类是自顶向下的策略，与凝聚层次聚类不同，它首先将所有对象放在一个簇中，然后慢慢地细分为越来越小的簇，直到每个对象自行形成一簇，或者直达满足其他的一个终结条件。

DIANA算法是分裂聚类的典型代表算法。

初始时，DIANA将所有样本点归为同一类簇，然后根据某种准则进行逐渐分裂。两簇之间的相似度是由不同簇中的两个数据点距离最相近的相似度来定义的。此外当两个簇距离超过用户给定的阈值时聚类分裂过程就会终止。聚类的分裂过程反复进行直到最终满足簇数目。

例如类簇C中两个样本点a和b之间的距离是类簇C中所有样本点间距离最远的一对，那么样本点a和b将分裂成两个簇C1和C2，并且先前类簇C中其他样本点根据与a和b之间的距离，分别纳入簇C1和C2中。

5.3.2.2　DIANA算法描述

算法：DIANA算法

输入：n个对象，终止条件簇的数目k

输出：k个类簇集合

步骤：

（1）将所有样本点归并成一个初始簇；

（2）重复；

（3）在所有簇中挑出具有最大直径的簇C；

（4）找出C中与其他点平均相异度最大的一个点a，并把a放入分裂出来的新类簇C1中，剩余的放在原始类簇C中；

（5）重复；(www.daowen.com)

（6）原始类簇C中找出到新类簇C1最近且比到原始类簇C的距离小的样本点，将该样本点分配到新类簇C1中；

（7）直到没有原始类簇C的样本点被分配到新类簇C1中；

（8）原始类簇C被分裂为两个类簇C1和C2，与其他类簇一起组成新的类簇集合；

（9）END。

5.3.2.3　层次聚类算法的分类

在凝聚和分裂的层次聚类之间，我们又依据计算簇间的距离的不同，分为下面的几类方法。

（1）单连锁（single linkage），又称最近邻（nearest neighbor）方法，指两个不一样的簇之间任意两点之间的最近距离。这里的距离是表示两个簇的相异度，所以距离越近，两个簇相似度越大。这种方法最善于处理非椭圆结构，却对于噪声和孤立点特别的敏感，取出距离很远的两个类之中出现一个孤立点时，这个点就很有可能把两类合并在一起。距离公式如式（5.2.9）所示。

（2）全连锁（comlpete linkage），又称最远邻（furthest neighbor）方法。指两个不一样的簇中任意的两点之间的最远的距离。它面对噪声和孤立点很不敏感，趋向于寻求某一些紧凑的分类，但是，有可能使比较大的簇破裂。距离公式如式（5.2.10）所示。

（3）组平均方法（group average linkage），定义距离为数据两两距离的平均值。这个方法倾向于合并差异小的两个类，产生的聚类具有相对的健壮性。距离公式如式（5.2.11）所示。

（4）平均值方法（centroid linkage），先计算各个类的平均值，然后定义平均值之差为两类的距离。距离公式如式（5.2.12）所示。

其中Ci，Cj是两个类，｜a－a′｜为对象a和a′之间的距离，ni，nj分别为Ci，Cj的对象个数，mi，mj分别为类Ci，Cj的平均值。

5.3.2.4　层次聚类方法存在的不足

在凝聚的层次聚类方法和分裂的层次聚类的所有方法中，都需要用户提供所希望所得到的聚类终止条件簇的数目k和阈值作为聚类分析的终止条件，但是对于复杂的数据来说这个是很难事先判定的。尽管层次聚类的方法实现的很简单，但是偶尔会遇见合并或分裂点的抉择的困难。这样的抉择是特别关键的，因为只要其中的两个对象被合并或者分裂，接下来的处理将只能在新生成的簇中完成。已形成的处理就不能被撤销，两个聚类之间也不能交换对象。如果在某个阶段没有选择合并或分裂的决策，就非常可能会导致不高质量的聚类结果，而且这种聚类方法不具有特别好的可伸缩性，因为它们合并或分裂的决策需要经过检测和估算大量的对象或簇。

层次聚类算法由于要使用距离矩阵，所以它的时间和空间复杂性都很高o（n2），几乎不能在大数据集上使用。层次聚类算法只处理符合某静态模型的簇，忽略了不同簇间的信息而且忽略了簇间的互连性（互连性指的是簇间距离较近数据对的多少）和近似度（近似度指的是簇间对数据对的相似度）。