层次法优化：单连接算法和BIRCH算法

凝聚的层次聚类方法一般包括以下几个步骤：

（1）初始化：计算包含每对样本间距离（如欧氏距离）的相似矩阵，把每个样本作为一个簇。

（2）选择：使用相似矩阵查找最相似的两个簇（计算两个簇间的距离的规则和方法参见4.2.4小节中式4-11～式4-14）。

（3）更新：将两个簇合并为一个簇，簇的个数通过合并被更新；同时更新相似矩阵，将两个簇的两行（两列）距离用1行（1列）距离替换反映合并操作。

（4）重复：执行步骤2和步骤3。

（5）结束：当所有样本都合并成一个簇或满足指定的簇的数目时，整个过程结束。

实际上，步骤（2）关于两个簇间距离如何计算的选择是各种层次聚类方法不同的关键之一，有些方法只需要距离矩阵，如单连接方法（最近邻方法）、全连接方法（最远邻方法）和平均连接方法等；有些需要距离矩阵和原始的数据矩阵，如重心法和Ward法等。

下面介绍单连接聚类算法的详细过程，这是一个简单的层次聚类方法。

1）单连接算法（single-linkage）

算法基本思想：两个簇之间的距离用从两个簇中抽取的每对样本的最小距离Dmin（ Ci ，Cj） （式4-11）作为距离度量，一旦最近的两个簇的距离超过某个给定的阈值或满足指定的簇的数目，算法结束（图4-6）。

单连接算法中需要调用最小生成树（minimum spanning tree， MST）过程，根据输入的距离相似度矩阵生成最小生成树（图4-7a），当两个簇合并时，将其在树中的距离置为∞，用一个节点代替两个节点及其边。

图4-6　单连接算法

下面用一个例子来展示单连接算法过程。

例4.4：五个样本间的距离如图4-7所示，用单连接算法进行聚类分析并画出树形图。

分析及解：先将五个样本都分别看成是一个簇，图中可以看出，最靠近的两个簇是3和4，因为他们具有最小的簇间距离dist（3，4）=5.0。

第一步：合并簇3和4，得到新簇集合1，2，（34），5，并更新距离矩阵：

dist［1， （34）］=min［dist（1， 3）， dist（1， 4）］=min（20.6， 22.4）=20.6

dist［2， （34）］=min［dist（2， 3）， dist（2， 4）］=min（14.1， 11.2）=11.2

dist［5， （34）］=min［dist（3， 5）， dist（4， 5）］=min（25.0， 25.5）=25.0

原有簇1，2，5间的距离不变，修改后的距离矩阵如图4-7b所示，在四个簇1，2，（34），5中，最靠近的两个簇是1和5，它们具有最小簇间距离dist（1，5）=7.07。

图4-7　单连接算法

第二步：合并簇1和5，得到新簇集合2，（34），（15），并更新距离矩阵：

dist［2， （15）］=min［dist（1， 2）， dist（2， 5）］=min（18.0， 18.0）=18.0

dist［（15）， （34）］=min［dist（1， 3）， dist（1， 4）， dist（3， 5）， dist（4， 5）］=min（20.6，22.4， 25.0， 25.5） =20.6

第三步：上一步中，dist［2， （34）］=11.2最小，因此合并簇2和（34）得到新簇集合（15） ，（234），并更新距离矩阵：

dist［（15） ，（234）］=min［dist（1， 2）， dist（1， 3）， dist（1， 4）， dist（2， 5）， dist（3， 5），dist（4， 5）］=min（18.0， 20.6， 22.4， 25.0， 25.5）=18.0

此时只有两个不同的簇（15）和（234），它们的距离是18.0。

最后再将（15）和（234）合并成一个簇，由此完成了整个聚类过程。

注：这里的终止条件是所有样本被合并为一个簇。此外，也可以指定簇数目或两个簇的距离超过某个给定的阈值作为终止条件。

相应的树形图如图4-7c所示。

2）全连接算法（complete-linkage）

与单连接聚类方式相同，所不同的是簇与簇之间的距离用两簇中样本之间的最大距离Dm aax（ Ci， Cj） （式4-12）作为距离度量时，一旦最近的两个类的距离超过某个任意给定的阈值或满足指定的簇的数目，算法结束。

同样对例4.4用全连接算法聚类，分析过程如下：

第一步：同样合并簇3和4，因为它们是最靠近的，然后修正距离矩阵，此时选择最大距离为距离度量。

dist［1， （34）］=max［dist（1， 3）， dist（1， 4）］=max（20.6， 22.4）=22.4

dist［2， （34）］=max［dist（2， 3）， dist（2， 4）］=max（ 14.1， 11.2）=14.1

dist［5， （34）］=max［dist（3， 5）， dist（4， 5）］=max（25.0， 25.5）=25.5

其余步骤省略，如图4-8中所示。

图4-8　全连接算法

从上面两种算法及实例进一步表明，在实际情况中簇的数目一般根据实际问题来决定，没有一种方法对于任何类型的数据都能得到最佳结果，可以针对不同的可选方法进行试验，并根据选定的准则比较这些算法。

分裂的层次聚类算法通常很少用于日常的应用，因为它们计算复杂度较高。但是，尽管直接应用分裂的层次聚类法在第一次迭代中需要n2次距离计算，但随后分裂的距离个数就较少。

3） BIRCH算法

BIRCH算法是一个综合的层次聚类方法，基本思想是建立一棵树，这棵树能够捕获进行聚类所必需的信息，然后聚类仅在这棵树上进行。其中树中的节点的标记包含了计算距离值所必需的信息。

它引入两个概念用于概括簇描述：簇特征（CF）和簇特征树（CF树）。

对应4.1.2中的定义，先来看一些与BIRCH算法相关概念和符号说明，后面将详细讨论CF树结构。

符号说明4.3（一个簇中的N个d维数据样本）： ｛ ｝（i=1， 2， …， N）。

符号说明4.4（簇的质心0）：

(www.xing528.com)

簇内紧密度（tightness）度量：半径R和直径D。

符号说明4.5（半径R）：数据点到质心的平均距离。

符号说明4.6（直径D）：簇内的两两样本间距离的平均值。

给定两个簇C1和C2：

簇C1具有N1个d维的数据样本：，质心为；簇C2具有N2个d维的数据样本：， …， N1 +N2），质心为02。

两个簇的接近度（closeness）度量：两个簇的质心的欧氏距离D0、两个簇的质心的曼哈顿距离D1、平均簇间距离（average inter-cluster distance） D2、平均簇外距离（average intracluster distance） D3、偏差平均距离（variance increase distance）D4，定义如下：

两个簇的质心的欧氏距离D0：

两个簇的质心的曼哈顿距离D1：

平均簇间距离D2：

平均簇外距离D3：

偏差平均距离D4：

不难看出，D3实际是两个簇合并后的直径D。

定义4.6（簇特征CF）元组：是包含簇信息的三元组（N， LS， SS），N：簇的数据点的数量；LS：所有数据点的线性和，即：所有数据点的平方和，即

定理4.1（CF迭加性）：假设CF1=（N1， LS1， SS1）， CF2=（N2， LS2， SS2）是两个不相交子集的CF向量。这两个簇合并后形成的簇的CF元组为：

CF1 +CF2 =（ N1 + N2， LS1 + LS2 ， SS1 +SS2） 。

从CF的定义和迭加性定理可以看出，簇特征CF是对给定子簇的统计汇总，记录了计算簇和有效利用存储的关键度量，并随着簇的合并进行增量式的计算。

CF向量存储效率高，它占用的空间远远小于簇的所有的数据点，保存了足够的信息可以用于计算所需的任何度量0，R，D，D0，D1，D2，D3，D4，以及常用的质量度量（如，簇的加权总/平均直径）等。

定义4.7（ CF树）：是一棵高度平衡树，其节点是CF元组，具有两个参数：平衡因子B和阈值T。每个非叶节点最多包含B个元组［CFi，childi（其中i=1， 2，…， B），childi是指向第i个子节点的指针，CFi是这个子节点代表的子簇的CF向量。即一个非叶节点实际上由所有元组代表的子簇组成。每个叶节点包含了最多L个元组，形式为［CFi］，i=1，2，…， L。每个叶节点有两个指针：prey和next，通过这两个指针把所有的叶节点连接在一起，以提高搜索效率。叶结点代表的簇由所有元组代表的子簇组成。一个叶结点的所有元组必须满足阈值T：直径（或半径）必须小于T。

树的大小是一个关于T的函数。T越大，树越小。这是因为T越大，反映了簇的松散程度越大，每个簇所包含的数据点就越多，从而整个数据集上的簇的数目就越少，结果CF树的结点减少，所以树就越小。

另外，算法要求每个节点占用的内存空间为一个页面，大小为P。一旦给定了数据空间的维数d，非叶节点和叶节点的元组的大小就可以确定，也就是说B和L由P确定，可以根据性能调节P的大小。

CF树可以随着新数据的插入而动态创建。它的创建方法与B+树很相似。

把一个新数据（entry）插入CF树的算法步骤如下（给定数据为“Ent”） ：

（1）识别合适的叶节点：从根节点开始，自上而下，根据给定的距离函数度量（如，定义的D0， D1， D2， D3， D4）选择最近的子节点。

（2）修改叶节点。当到达某个叶节点时，找到最近的叶子元组，假设为Li。检验：Li能否吸收“Ent”并且不违反阈值T的规定。如果符合阈值的要求，则更新Li的CF向量；否则，为“Ent”新建一个元组，插入叶节点。如果叶节点中没有足够的空间，则分裂叶节点。叶节点分裂时，将最远的一对元组作为种子，按最邻近标准分配剩下的元组。

（3）修改根节点到叶子节点的路径。把元组插入叶节点后，必须更新根节点到叶节点路径上的所有非叶节点的CF信息。如果不存在分裂，则只需把“Ent”的值添加到CF向量中即可。如果存在分裂，则在父节点中加入一个新的非叶子节点元组。如果父节点有足够的空间可以容纳新元组，则只需更新CF向量以反映“Ent”的值，一般地，必须分割父节点直到遇到根节点。如果根节点存在分裂，则树的高度增加1。

（4）合并精化。分裂由页面大小决定，而与数据的聚类属性无关。这将影响聚类的质量，也会减少空间的利用。

简单的附加合并步骤有助于改善以下问题：

假设有一个叶节点存在分裂，分裂在某个非叶节点Nj停止生长。扫描节点Nj以找到两个最近的entry，如果它们不是关于分裂的点对，则将其与两个相应的子节点合并。如果合并子节点后的所有entry一个页面不能装载，那么就需要重新分裂合并的节点。

在重新分裂过程中，假使一个种子entry能“吸纳”足够多的entry填满一个页面，就把剩下的entry放到另一个种子“吸纳”的页面中。总之，如果合并的那些entry能被一个页面容纳下，则释放一个entry空间以备后用，这样可以增加空间利用度，且可以延迟以后的分裂；否则的话，进行重新分裂操作，这样也可以改善在两个最近子节点中的entry分布性能。

BIRCH聚类算法的基本步骤包括：数据载入、CF-树的压缩（可选）、全局聚类以及聚类精华（可选）等四部分（图4-9）。

图4-9　BIRCH算法的基本步骤

图4-10　阶段1的流程图

阶段1扫描数据，根据给定的内存和磁盘回收空间建立初始CF树，放入内存。

下面用图4-10显示阶段1的细节。从一个初始阈值开始，扫描数据，把数据点插入CF树。如果内存不足，则提高阈值，把旧树的叶节点插入新树，重新构建一个较小的CF树。原来的叶节点被重新插入后，从数据打断处继续扫描数据（并插入到新树中）。重建较小的CF树的过程如下：

假设在CF树Ti的每个结点中，其中的entry都连续从0到Nk—1进行标号，其中Nk是该结点中的entry数目。那么一条从根结点中的entry（第一层）到叶结点（第h层）的Path可以唯一地表示成（I1 ， I2 ， … ， Ih—1），其中Ij（j=1，…， h-1）是那条路径上的第j层entry的标号。所以，称是before（或者称是＜）的，如果满足，并且很明显，一个叶子结点对应一条唯一的Path。有了这个Path的定义，可以一条一条Path扫描和释放旧树，同时，创建通过一条一条Path创建新树。新树从NULL开始，而旧的当前Path“OldCurrentPath”从旧树的最左边的Path开始。重建算法：

在新树中创建一条“NewCurrentPath”：加到新树中的结点就如旧树中的一样。

把“OldCurrentPath”中的叶子结点中的entry插入到新树中：根据现有的阈值T，在“OldCurrentPath”中的叶子结点中的entry测试能不能被在新树中的某条路径“NewClosetPath”所“吸收”（根据最近邻原则），如果“NewClosetPath” ＜“ NewCurrentPath”，它就插入到“NewClosetPath”中，在“NewCurrentPath”中的空间就可以备后用；否则的话，它就插入到“NewCurrentPath”中。

释放在“OldCurrentPath”中和“NewCurrentPath”中的空间：一旦在“OldCurrentPath”中的所有叶子中的entry都处理完了，沿“OldCurrentPath”中不必要的结点就释放掉。同样，有可能在沿“NewCurrentPath”中一些结点是空的，因为最初对应这Path的叶子结点中的entry现在被“推前了”（被before中的路径给“吸收”了）。在这种情况下，空结点可以被释放掉。

“OldCurrentPath”设置成下一条路径（如果有的话），转到1进行重复操作。

阶段2是可选的。 目的是尽量缩小在第1阶段的结果和第3阶段的输入之间存在的差异。因为，第3阶段采用的全局或半全局聚类算法在速度和质量上对输入都有着不同的要求。阶段2的工作和阶段1相似，扫描初始CF树，移除孤立点，合并密度较大的簇，从而建立一个更小的CF树。

阶段3：输入顺序引起的不确定情况和页面大小限制引起的分裂对聚类结果的准确性将造成影响，阶段3使用某个全局或半全局聚类算法对叶结点的元组进行聚类，解决这个问题。因为数据点和子簇都可以通过CF向量来描述，目前用于数据点聚类的算法经修改后，可以用于子簇的聚类。例如，已知CF向量，最简单的方法是把中心点作为子簇的代表，把每个子簇作为单个数据点，现有的算法不需要进行任何改动；更精确的方法是把一个具有n个数据点的子簇作为中心点的n次重复，只需要在已有算法中把数量考虑进来即可；考虑到算法的普遍性和精确性，可以把现有的算法直接用于子簇上，因为它们的CF向量已经提供了足够的信息，可以任意计算距离和质量度量。

阶段4是可选的，它的作用是进一步精化聚类的准确性。阶段4把阶段3得到的所有簇的中心点作为种子，把数据点重新分配到最近的中心点上。它保证了相等的数据一定被分配到同一个簇中，而且允许属于同一簇的点可以进行迁移。还可以在阶段4进行孤立点的移除工作。

这些结构辅助聚类方法在大规模数据集中取得较高的速度和可伸缩性。BIRCH算法采用多阶段聚类技术，对增量或动态聚类也非常有效。算法的计算复杂度是O（n），其中n表示样本的数目，算法具有对样本数目的线性伸缩性，及较好的聚类质量。但是其缺点在于如果簇不是球形的，BIRCH不能很好的工作，因为BIRCH用了半径或直径的概念来控制聚类的边界。