机器学习：基于层次的聚类算法

尽管基于划分的聚类算法能够实现把数据集划分成指定数量的簇，但是在某些情况下，需要把数据集划分成不同层上的簇：比如，作为一家公司的人力资源部经理，你可以把所有的雇员组织成较大的簇，如主管、经理和职员；然后你可以进一步划分为较小的簇，例如，职员簇可以进一步划分为子簇：高级职员，一般职员和实习人员。所有的这些簇形成了层次结构，可以很容易地对各层次上的数据进行汇总或者特征化。

另外，使用基于划分的聚类算法（K-means，CLARA等）的一个问题是，需要指定一个划分簇的数量K。然而在实践中，簇的数量K往往没有办法提前确定，或者随着关注的数据特征不同，想要的K值也随之变化。对于分布如下的数据：

直观来看，上图中展示的数据划分为2个簇或4个簇都是合理的，甚至，如果上面每一个圈的内部包含的是大量数据形成的数据集，那么也许分成16个簇才是所需要的。

所以，讨论数据集应该聚类成多少个簇，通常是在讨论我们在什么尺度上关注这个数据集。层次聚类算法相比划分聚类算法的优点之一是可以在不同的尺度上（层次）展示数据集的聚类情况。

基于层次的聚类算法（Hierarchical Clustering）可以是凝聚的（Agglomerative）或者分裂的（Divisive），取决于层次的划分是“自底向上”还是“自顶向下”。

• 自顶向下： 它把所有对象至于一个簇中开始，该簇是层次结构的根。然后，它把根上的簇划分为多个较小的子簇，并且递归地把这次簇划分成更小的簇，直到满足终止条件。常见的自顶向下的算法有K-means层次聚类算法。
• 自底向上：把数据集中的每个对象最为一个簇开始，迭代地把簇合并成为更大的簇，直到最终形成一个大簇，或者满足某个终止条件。基于自底向上算法有凝聚算法、BIRCH算法、CURE算法、变色龙算法等。

自顶向下算法

Hierarchical K-means算法

Hierarchical K-means算法是“自顶向下”的层次聚类算法，用到了基于划分的聚类算法那K-means，算法思路如下：

1. 首先，把原始数据集放到一个簇C，这个簇形成了层次结构的最顶层；
2. 使用K-means算法把簇C划分成指定的K个子簇C_i，i = 1,2,…,k，形成一个新的层；
3. 对于步骤2所生成的K个簇，递归使用K-means算法划分成更小的子簇，直到每个簇不能再划分（只包含一个数据对象）或者满足设定的终止条件。

如下图，展示了一组数据进行了二次K-means算法的过程

Hierarchical K-means算法一个很大的问题是，一旦两个点在最开始被划分到了不同的簇，即使这两个点距离很近，在后面的过程中也不会被聚类到一起。

对于以上的例子，红色椭圆框中的对象聚类成一个簇可能是更优的聚类结果，但是由于橙色对象和绿色对象在第一次K-means就被划分到不同的簇，之后也不再可能被聚类到同一个簇。

自底向上算法

Agglomerative Clustering算法

相比于Hierarchical K-means算法存在的问题，Agglomerative Clustering算法能够保证距离近的对象能够被聚类到一个簇中，该算法采用的“自底向上”聚类的思路。

算法思路，对于数据集D，D={x_1,x_2,…,x_n}：

1. 将数据集中的每个对象生成一个簇，得到簇列表C，C={c_1,c_2,…,c_n} a) 每个簇只包含一个数据对象：c_i={x_i}；
2. 重复如下步骤，直到C中只有一个簇： a) 从C中的簇中找到两个“距离”最近的两个簇：min⁡〖D(c_i,c_j)〗； b) 合并簇c_i和cj，形成新的簇c(i+j)； c) 从C中删除簇c_i和cj，添加簇c(i+j)

簇间距离计算

在上面描述的算法中涉及到计算两个簇之间的距离，对于簇C_1和C_2，计算〖D(C_1,C〗_2)，有以下几种计算方式：

单连锁（Single link）

两个簇之间最近的两个点的距离作为簇之间的距离，该方式的缺陷是受噪点影响大，容易产生长条状的簇。

全连锁（Complete link）

两个簇之间最远的两个点的距离作为簇之间的距离，采用该距离计算方式得到的聚类比较紧凑。

平均连锁（Average link）

两个簇之间两两点之间距离的平均值，该方式可以有效地排除噪点的影响。

Agglomerative算法示例

对于如下数据：

1. 将A到F六个点，分别生成6个簇；

找到当前簇中距离最短的两个点，这里我们使用单连锁的方式来计算距离，发现A点和B点距离最短，将A和B组成一个新的簇，此时簇列表中包含五个簇，分别是{A，B}，{C}，{D}，{E}，{F}，如下图所示；

2 . 找到当前簇中距离最短的两个点，这里我们使用单连锁的方式来计算距离，发现A点和B点距离最短，将A和B组成一个新的簇，此时簇列表中包含五个簇，分别是{A，B}，{C}，{D}，{E}，{F}，如下图所示；

3 . 重复步骤二、发现{C}和{D}的距离最短，连接之，然后是簇{C,D}和簇{E}距离最短，依次类推，直到最后只剩下一个簇，得到如下所示的示意图：

4 .此时原始数据的聚类关系是按照层次来组织的，选取一个簇间距离的阈值，可以得到一个聚类结果，比如在如下红色虚线的阈值下，数据被划分为两个簇：簇{A，B，C，D，E}和簇{F}

Agglomerative聚类算法的优点是能够根据需要在不同的尺度上展示对应的聚类结果，缺点同Hierarchical K-means算法一样，一旦两个距离相近的点被划分到不同的簇，之后也不再可能被聚类到同一个簇，即无法撤销先前步骤的工作。另外，Agglomerative性能较低，并且因为聚类层次信息需要存储在内存中，内存消耗大，不适用于大量级的数据聚类，下面介绍一种针对大数据量级的聚类算法BIRCH。

BIRCH算法

BIRCH算法的全称是Balanced Iterative Reducing and Clustering using Hierarchies，它使用聚类特征来表示一个簇，使用聚类特征树（CF-树）来表示聚类的层次结构，算法思路也是“自底向上”的。

BIRCH算法相比Agglomerative凝聚算法具有如下特点：

• 解决了Agglomerative算法不能撤销先前步骤的工作的缺陷；
• CF-树只存储原始数据的特征信息，并不需要存储原始数据信息，内存开销上更优；
• BIRCH算法只需要遍历一遍原始数据，而Agglomerative算法在每次迭代都需要遍历一遍数据，所以BIRCH在性能也优于Agglomerative；
• 支持对流数据的聚类，BIRCH一开始并不需要所有的数据；

首先介绍几个基本的概念，给定簇C={x1,x(2,) 〖…,x〗_n}，其中x_i代表一个数据点，可以是一维、二维或者多维数据，下面公式中x_i的计算均为向量计算。

质心，代表这个簇的中心：

簇半径，簇中所有点到质心的平均距离：

簇直径，簇中所有数据点之间的平均距离；

BIRCH算法的核心是构建CF-树（Clustering Feature Tree），而CF-树种每个节点代表一个簇的抽象特征，包含三个数据：

• n表示簇中数据个数；
• LS是n个点的线性和（即

）；

• SS是n个数据点的平方和（即

）；

聚类特征是可加的，也就是说，对于两个不想交的簇C_1和C_2，其聚类特征分别为〖CF〗_1=<n_1,〖LS〗_1,〖SS〗_1>和〖CF〗_2=<n_2,〖LS〗_2,〖SS〗_2>，合并C_1和C_2后的簇的聚类特征是：

〖CF〗_1+〖CF〗_2=<n_1+n_2,〖LS〗_1 〖+LS〗_2,〖SS〗_1+〖SS〗_2>

CF-树的结构类似于一棵B-树，它有两个参数：内部节点平衡因子（即每个节点允许的子节点数）B，叶节点平衡因子（即最终叶子节点允许的最大叶子数）L，簇半径阈值T。树中每个节点最多包含B个孩子节点，记为（CF_i，child_i），其中i≤i≤B，例如，一棵高度为3，B为2，L为3的一棵CF树的例子如图所示：

构造CF-树的步骤如下：

1. 从根节点开始，自上而下选择最近的孩子节点；
2. 到达叶子节点后，检查距离其最近的CF能否吸收此数据点： a) 是，更新CF值 b) 否，创建一个新的CF节点，检查该节点能否加入到当前叶子节点 i. 能，添加到当前叶子节点； ii. 否，分裂最远的一对CF节点，按最近距离重新分配其它节点；
3. 更新每个非叶子节点的CF信息，如果分裂节点，在父节点中插入新的CF节点，直到root；

对于上图所示的CF-树，假设现在添加一个新的簇CF_12，这个簇距离CF_8最近，但是不满足被吸收的条件（CF_8和CF_12之间的距离大于了阈值），加入过程如下：

①用CF_8跟CF_1和CF_2比较距离，发现离CF_1更近；找到CF_1的子节点CF_3和CF_4；

②同步骤1，找到CF_3的子节点，发现为叶子节点4：{ CF_6,CF_7,CF_8}；

③尝试把CF_12加入到叶子节点4，此时节点4的数量为4，超过了我们设定的L值3，所以现在需要分离节点4，将CF_8和CF_12分到一个新的叶子节点，然后剩下CF_6和CF_7；

④同时在节点2中加入一个新的非叶子节点，此时节点2的数量为3，大于我们设定的B值2，进一步拆分节点2为两个新的非叶子节点；

⑤同步骤4，知道所有的节点都满足CF-树种B=2，L=3的约束；

⑥更新所有CF节点对应的特征值，得到如下的新CF-树：

BIRCH算法的主流程如下：

CURE算法

CURE（Clustering Using Representatives）是一种针对大型数据库的高效的聚类算法。基于划分的传统的聚类算法得到的是球状的，相等大小的聚类，对异常数据比较脆弱。CURE采用了用多个点代表一个簇的方法，可以较好的处理以上问题。并且在处理大数据量的时候采用了随机取样，分区的方法，来提高其效率，使得其可以高效的处理大量数据。

我们先看一下基于划分聚类算法的缺陷：

如上图所示，基于划分的聚类算法比如Hierarchical K-means聚类算法，不能够很好地区分尺寸差距大的簇，原因是K-means算法基于“质心”加一定“半径”对数据进行划分，导致最后聚类的簇近似“圆形”。

再看一下其他聚类算法在聚类结果上可能存在的问题：

上面（b）图使用的是基于“平均连锁”或者基于“质心”的簇间距离计算方式得到的聚类结果，可以看出，聚类结果同基于划分的聚类算法相似、最后聚类的结果呈“圆形”，不能够准确地识别条形的数据；（c）图使用的是基于“单连锁”的簇间距离计算策略，由“单连锁”的定义可知，对于（c）图中最左边两个由一条细线相连的两个簇，会被聚类成一个簇，这也不是我们想要的。

CURE算法核心的思想是使用一定数量的“分散的”点（scattered points）来代表一个簇（cluster），而不像是其他层次聚类算法中，只使用一个点，使得CURE算法有如下优势：

• 准确地识别任意形状的簇；
• 准确地识别尺寸差距大的簇；
• 很好地处理“噪点”

所以，CURE算法很好地解决了上面提到的聚类结果的缺陷，CURE算法主流程如下：

Pass 1

1. 从总数据中随机选取一个样本；
2. 利用层次聚类算法把这个样本聚类，形成最初的簇C_i,(i=1,2,…,n)；
3. 选取“代表点”（representative pionts）;

①对于每个簇，选取代表点（比如4个），这些点尽量分散;

②按照固定的比例α（比如20%），把每个样本点向簇的“质心”收缩，生成代表点

;

Pass 2

重新扫描所有的数据， 把它放到 “最近的簇”对于点p，使用如下公式，找到距离p最近的簇：

简单来讲，点p到簇C_i的距离为点p到簇C_i的四个“代表点

中最近的点之间的距离。

收缩系数α的取值不同，聚类结果也相应不同。当α趋于0时，所有的“代表点”都汇聚到质心，算法退化为基于“质心”的聚类；当α趋于1时，“代表点”完全没有收缩，算法退化为基于“全连接”的聚类，因此α值需要要根据数据特征灵活选取，才能得到更好的聚类结果：

Chameleon变色龙算法

1.kNN图算法，参数k=1,2,3,4… 。以k为1为例，一次处理每一个点，每个点找一个最近的邻居链接起来，得到一个kNN图。

2.整体算法步骤为：

1) 创建kNN图；

2) 使用最大流算法或者最小割算法，将kNN图分隔成小图；

3) 将小簇进行和并，合并条件是RC*RI大于某个值，RC和RI的一个基本思想是，点之间的链接越多，这些点越可能连接成一个簇，C表示一个簇，是点的集合，｜Ｃ｜是集合的大小，即点的个数,EC(A,B)表示两个簇之间的边的数量。

层次聚类算法对比

参考文献：

Jiawei Han & Micheline Kamber & Jian Pei. 数据挖掘概念与技术（第三版）[M]，2012，297-305.

Ian H. Witten & Eibe Frank & Mark A. Hall. 数据挖掘使用机器学习工具与技术[M]，2014,58-60.

Tian Zhang & Raghu Ramakrishnan & Miron Livny. BIRCH: An Efficient Data Clustering Method For Very Large Databases [J]，1996

Sudipto Guha & Rajeev Rastogi & Kyuseok Shim. CURE: An Efficient Clustering Algorithm for Large Databases [J]，1998