聚类算法之层次聚类

层次聚类简介

层次聚类算法(Hierarchical Clustering)将数据集划分为一层一层的clusters,后面一层生成的clusters基于前面一层的结果。层次聚类算法一般分为两类:

  • Divisive 层次聚类:又称自顶向下(top-down)的层次聚类,最开始所有的对象均属于一个cluster,每次按一定的准则将某个cluster 划分为多个cluster,如此往复,直至每个对象均是一个cluster。
  • Agglomerative 层次聚类:又称自底向上(bottom-up)的层次聚类,每一个对象最开始都是一个cluster,每次按一定的准则将最相近的两个cluster合并生成一个新的cluster,如此往复,直至最终所有的对象都属于一个cluster。

下图直观的给出了层次聚类的思想以及以上两种聚类策略的异同:

层次聚类算法是一种贪心算法(greedy algorithm),因其每一次合并或划分都是基于某种局部最优的选择。

自顶向下的层次聚类算法(Divisive)

Hierarchical K-means算法

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

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

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

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

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

Bisecting k-means聚类算法,即二分k均值算法,是分层聚类(Hierarchical clustering)的一种。更多关于二分k均值法,可以查看聚类算法之K-Means及其变种

自底向上的层次聚类算法(Agglomerative)

层次聚类的合并算法通过计算两类数据点间的相似性,对所有数据点中最为相似的两个数据点进行组合,并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性,距离越小,相似度越高。并将距离最近的两个数据点或类别进行组合,生成聚类树。

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

Agglomerative算法示例

对于如下数据:

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

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

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

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

对象之间的距离衡量

衡量两个对象之间的距离的方式有多种,对于数值类型(Numerical)的数据,常用的距离衡量准则有 Euclidean 距离Manhattan 距离Chebyshev 距离Minkowski 距离等等。

更多信息可查看常见相似度计算方法回顾

Cluster 之间的距离衡量

除了需要衡量对象之间的距离之外,层次聚类算法还需要衡量cluster之间的距离,常见的cluster之间的衡量方法有 Single-link 方法、Complete-link 方法、UPGMA(Unweighted Pair Group Method using arithmetic Averages)方法、WPGMA(Weighted Pair Group Method using arithmetic Averages)方法、Centroid 方法(又称 UPGMC,Unweighted Pair Group Method using Centroids)、Median 方法(又称 WPGMC,weighted Pair Group Method using Centroids)、Ward 方法。前面四种方法是基于图的,因为在这些方法里面,cluster是由样本点或一些子cluster(这些样本点或子cluster之间的距离关系被记录下来,可认为是图的连通边)所表示的;后三种方法是基于几何方法的(因而其对象间的距离计算方式一般选用 Euclidean 距离),因为它们都是用一个中心点来代表一个cluster。

假设$C_i$和$C_j$为两个cluster,则前四种方法定义的$C_i$和$C_j$之间的距离如下表所示:

方法定义
Single-link$D(C_i, C_j) = \min_{x \in C_i, y \in C_j } d(x, y)$
Complete-link$D(C_i, C_j) = \max_{x \in C_i, y \in C_j } d(x, y)$
UPGMA$D(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_ { x \in C_i,  y \in C_j}  d(x, y)$
WPGMA省略

简单的理解:

  • Single Linkage:方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。
  • Complete Linkage:Complete Linkage的计算方法与Single Linkage相反,将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。Complete Linkage的问题也与Single Linkage相反,两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。
  • Average Linkage:Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大,但结果比前两种方法更合理。

其中 Single-link 定义两个 cluster 之间的距离为两个 cluster 之间距离最近的两个对象间的距离,这样在聚类的过程中就可能出现链式效应,即有可能聚出长条形状的 cluster;而 Complete-link 则定义两个 cluster 之间的距离为两个 cluster 之间距离最远的两个对象间的距离,这样虽然避免了链式效应,但其对异常样本点(不符合数据集的整体分布的噪声点)却非常敏感,容易产生不合理的聚类;UPGMA 正好是 Single-link 和 Complete-link 的一个折中,其定义两个 cluster 之间的距离为两个 cluster 之间两个对象间的距离的平均值;而 WPGMA 则计算的是两个 cluster 之间两个对象之间的距离的加权平均值,加权的目的是为了使两个 cluster 对距离的计算的影响在同一层次上,而不受 cluster 大小的影响(其计算方法这里没有给出,因为在运行层次聚类算法时,我们并不会直接通过样本点之间的距离之间计算两个 cluster 之间的距离,而是通过已有的 cluster 之间的距离来计算合并后的新的 cluster 和剩余cluster 之间的距离,这种计算方法将由下一部分中的 Lance-Williams 方法给出)。

Centroid/UPGMC方法给每一个cluster 计算一个质心,两个 cluster 之间的距离即为对应的两个质心之间的距离,一般计算方法如下:

$$D_{UPGMC}(C_i,C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i, y \in C_j}d(x, y) – \frac{1}{2{|C_i |}^2}\sum_{x, y\in C_i}  d(x,y) – \frac{1}{2{|{C_j}|}^2} \sum_{x,y \in C_j}d(x, y)$$

当上式中的d(x,y)为平方 Euclidean 距离时,$D_{UPGMC}(C_i, C_j)$为$C_i$和$C_j$的中心点(每个 cluster 内所有样本点之间的平均值)之间的平方 Euclidean 距离。

Median/WPGMC 方法为每个 cluster 计算质心时,引入了权重。

Ward方法提出的动机是最小化每次合并时的信息损失,具体地,其对每一个 cluster 定义了一个 ESS (Error Sum of Squares)量作为衡量信息损失的准则,cluster C 的 ESS 定义如下:

${ESS}(C) = \sum_{x \in C} (x- m_x)^{T}(x – m_x)$

其中$m_x$为 C 中样本点的均值。可以看到 ESS 衡量的是一个 cluster 内的样本点的聚合程度,样本点越聚合,ESS 的值越小。Ward 方法则是希望找到一种合并方式,使得合并后产生的新的一系列的 cluster 的 ESS 之和相对于合并前的 cluster 的 ESS 之和的增长最小。

常用Agglomerative算法

Lance-Williams 方法

在 Agglomerative 层次聚类算法中,一个迭代过程通常包含将两个cluster合并为一个新的cluster,然后再计算这个新的 cluster 与其他当前未被合并的cluster之间的距离,而 Lance-Williams方法提供了一个通项公式,使得其对不同的 cluster 距离衡量方法都适用。具体地,对于三个 cluster $C_k$,$C_i$和$C_j$, Lance-Williams 给出的$C_k$与$C_i$和$C_j$合并后的新cluster之间的距离的计算方法如下式所示:

$$D(C_k, C_i \cup C_j) = \alpha_i D(C_k, C_i) + \alpha_j D(C_k, C_j) + \beta D(C_i, C_j) +  \gamma | D(C_k, C_i) – D(C_k, C_j)|$$

其中,$\alpha_i, \alpha_j,\beta, \gamma$均为参数,随cluster之间的距离计算方法的不同而不同,具体总结为下表(注:$n_i$为cluster $C_i$中的样本点的个数):

方法参数$\alpha_i$参数$\alpha_j$参数$\beta$参数$\gamma$
Single-link1/21/20-1/2
Complete-link1/21/201/2
UPGMA$n_i/(n_i + n_j)$$n_j/(n_i + n_j)$00
WPGMA1/21/200
UPGMC$n_i/(n_i + n_j)$$n_j/(n_i + n_j)$$n_{i}n_{j}/(n_i + n_j)^2$0
WPGMC1/21/21/40
Ward$(n_k + n_i)/(n_i + n_j + n_k)$$(n_k + n_j)/(n_i + n_j + n_k)$$n_k/(n_i + n_j + n_k)$0

其中 Ward 方法的参数仅适用于当样本点之间的距离衡量准则为平方 Euclidean 距离时,其他方法的参数适用范围则没有限制。

Naive 算法

给定数据集$X = (x_1, x_2,…,x_n)$,Agglomerative 层次聚类最简单的实现方法分为以下几步:

  1. 初始时每个样本为一个 cluster,计算距离矩阵 D,其中元素$D_{ij}$为样本点$x_i$和$x_j$之间的距离
  2. 遍历距离矩阵 D,找出其中的最小距离(对角线上的除外),并由此得到拥有最小距离的两个 cluster 的编号,将这两个 cluster 合并为一个新的 cluster 并依据 Lance-Williams 方法更新距离矩阵 D (删除这两个 cluster 对应的行和列,并把由新 cluster 所算出来的距离向量插入 D 中),存储本次合并的相关信息
  3. 重复 2 的过程,直至最终只剩下一个 cluster。

当然,其中的一些细节这里都没有给出,比如,我们需要设计一些合适的数据结构来存储层次聚类的过程,以便于我们可以根据距离阈值或期待的聚类个数得到对应的聚类结果。可以看到,该 Naive 算法的时间复杂度为$O(n^3)$(由于每次合并两个 cluster 时都要遍历大小为$O(n^2)$的距离矩阵来搜索最小距离,而这样的操作需要进行 n-1 次),空间复杂度为$O(n^2)$(由于要存储距离矩阵)。

当然,还有一些更高效的算法,它们用到了特殊设计的数据结构或者一些图论算法,是的时间复杂度降低到$(n^2)$更低,例如 SLINK 算法(Single-link 方法),CLINK 算法(Complete-link 方法),BIRCH 算法(适用于 Euclidean 距离准则)等等。

利用 Scipy 实现层次聚类

1、生成测试数据

SciPy 里面进行层次聚类非常简单,直接调用 linkage 函数,一行代码即可搞定:

以上即进行了一次cluster间距离衡量方法为Ward、样本间距离衡量准则为Euclidean距离的Agglomerative层次聚类,其中method参数可以为’single’、’complete’、’average’、’weighted’、’centroid’、’median’、’ward’中的一种,分别对应我们前面讲到的 Single-link、Complete-link、UPGMA、WPGMA、UPGMC、WPGMC、Ward 方法,而样本间的距离衡量准则也可以由 metric 参数调整。

linkage 函数的返回值 Z 为一个维度(n-1)*4的矩阵,记录的是层次聚类每一次的合并信息,里面的 4 个值分别对应合并的两个cluster的序号、两个cluster之间的距离以及本次合并后产生的新的 cluster 所包含的样本点的个数。

3、画出树形图

SciPy 中给出了根据层次聚类的结果 Z 绘制树形图的函数dendrogram,我们由此画出本次实验中的最后 20 次的合并过程。

得到的树形图如下所示:

可以看到,该树形图的最后两次合并相比之前合并过程的合并距离要大得多,由此可以说明最后两次合并是不合理的;因而对于本数据集,该算法可以很好地区分出 3 个 cluster(和实际相符),分别在上图中由三种颜色所表示。

4、获取聚类结果

在得到了层次聚类的过程信息 Z 后,我们可以使用 fcluster 函数来获取聚类结果。可以从两个维度来得到距离的结果,一个是指定临界距离 d,得到在该距离以下的未合并的所有 cluster 作为聚类结果;另一个是指定 cluster 的数量 k,函数会返回最后的 k 个 cluster 作为聚类结果。使用哪个维度由参数 criterion 决定,对应的临界距离或聚类的数量则由参数 t 所记录。fcluster 函数的结果为一个一维数组,记录每个样本的类别信息。

上图的聚类结果和实际的数据分布基本一致,但有几点值得注意,一是在聚类之前我们没法知道合理的聚类的数目或者最大的距离临界值,只有在得到全部的层次聚类信息并对其进行分析后我们才能预估出一个较为合理的数值;二是本次实验的数据集比较简单,所以聚类的结果较好,但对于复杂的数据集(比如非凸的、噪声点比较多的数据集),层次聚类算法有其局限性。

5、比较不同方法下的聚类结果

最后,我们对同一份样本集进行了 cluster 间距离衡量准则分别为 Single-link、Complete-link、UPGMA(Average)和 Ward 的 Agglomerative 层次聚类,取聚类数目为 3,代码如下:

可以得到 4 种方法下的聚类结果如图所示:

在上面的过程中,我们还为每一种聚类产生的结果计算了一个用于评估聚类结果与样本的真实类之间的相近程度的AMI(Adjust Mutual Information)量,该量越接近于 1 则说明聚类算法产生的类越接近于真实情况。程序的打印结果如下:

从上面的图和 AMI 量的表现来看,Single-link 方法下的层次聚类结果最差,它几乎将所有的点都聚为一个 cluster,而其他两个 cluster 则都仅包含个别稍微有点偏离中心的样本点,这充分体现了 Single-link 方法下的“链式效应”,也体现了 Agglomerative 算法的一个特点,即“赢者通吃”(rich getting richer): Agglomerative 算法倾向于聚出不均匀的类,尺寸大的类倾向于变得更大,对于 Single-link 和 UPGMA(Average) 方法尤其如此。由于本次实验的样本集较为理想,因此除了 Single-link 之外的其他方法都表现地还可以,但当样本集变复杂时,上述“赢者通吃” 的特点会显现出来。

利用 Sklearn 实现层次聚类

除了Scipy外,scikit-learn也提供了层次聚类的方法sklearn.cluster.AgglomerativeClustering,使用示例:

参考链接:

微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

机器学习在旅游与酒店个性化的研究

当我们访问Netflix、 YouTube 或Amazon时,我们认为个性化推荐是理所当然的。这些服务已经探索

机器学习: 商业与数据科学之间的桥梁

每次我们谈论自动驾驶汽车、聊天机器人、 AlphaGo 或者预测分析,都会涉及到一些机器学习技术的实现。在公众

Python检验数据是否正态分布

判断数据是否符合正态分布,比如使用3-sigma判断数据异常前,首先需要确定的是数据是否符合正态分布。今天一起

发表评论

电子邮件地址不会被公开。 必填项已用*标注