聚类算法之层次聚类（Hierarchical Clustering）

注意：本文引用自专业人工智能社区Venus AI

1. 算法解读：

层次聚类是一种树形方法，旨在建立一个分层的聚类结构。这种结构通常呈现为一个称为“树状图”（Dendrogram）的树形图，其中数据的每一项都位于树的叶子上，然后通过不断地合并或分裂，最终形成一个树形的聚类层次。

2. 步骤和细节：

凝聚型 (Agglomerative):

开始: 每个数据点都是一个聚类，因此有N个聚类（其中N是数据点的数量）。

迭代：在每一步，找到最近的两个聚类并合并它们，因此聚类的数量减少一个。

结束：最后只剩下一个包含所有数据点的聚类。

分裂型 (Divisive):

开始: 所有数据点都属于一个大的聚类。

迭代：在每一步，选择一个聚类并将其分割为两个子聚类。

结束：最后每个数据点都成为自己的聚类。

3. 举例：

假设我们有四种不同的物种：A、B、C和D，我们已经测量了它们在某些条件下的基因表达水平。我们的目标是使用层次聚类来探索这些物种之间的相似性，并了解它们之间的进化关系。

考虑我们有以下物种的基因表达数据：

物种A：[1, 2, 3]

物种B：[2, 3, 4]

物种C：[5, 6, 7]

物种D：[8, 9, 10]

我们希望基于这些基因表达数据来理解这四个物种之间的相似性。

凝聚性的流程如下：

步骤1：开始时，每个物种都被视为一个单独的聚类，即我们有四个聚类：{A}、{B}、{C}和{D}。

步骤2：计算每对聚类之间的距离。在这个例子中，我们可以计算每对物种基因表达数据之间的欧几里得距离。找到距离最近的两个聚类，并将它们合并为一个新的聚类。假设物种A和物种B的距离最近，我们将它们合并为一个新的聚类{A, B}。现在我们有三个聚类：{A, B}、{C}和{D}。

步骤3：继续计算新聚类与其他聚类之间的距离，并合并距离最近的两个聚类。假设{A, B}和{C}之间的距离最近，我们将它们合并为一个新的聚类{A, B, C}。现在我们有两个聚类：{A, B, C}和{D}。

步骤4：最后，我们将剩下的两个聚类{A, B, C}和{D}合并为一个聚类{A, B, C, D}。

通过这个过程，我们构建了一个树状图（Dendrogram），展示了这四个物种之间的相似性和层次结构，从而帮助我们理解它们的进化关系。

分裂性的流程如下：

步骤1：开始时，所有物种都属于一个大的聚类，即我们有一个聚类：{A, B, C, D}。

步骤2：选择一个聚类并将其分裂为两个子聚类。在这个例子中，我们可以使用一种方法（如k-means聚类）来确定如何将大聚类分裂。假设我们将{A, B, C, D}分裂为两个聚类：{A, B}和{C, D}。

步骤3：继续选择一个聚类并将其分裂。例如，我们可以进一步将{A, B}分裂为两个聚类：{A}和{B}，同时，将{C, D}分裂为两个聚类：{C}和{D}。

步骤4：最后，每个物种都成为自己的聚类，即我们得到四个聚类：{A}、{B}、{C}和{D}。

通过这个过程，我们同样构建了一个树状图（Dendrogram），展示了这四个物种之间的相似性和层次结构，帮助我们理解它们的进化关系，但是这次是通过分裂的方式进行的。

代码示例：

我们可以使用Python的scipy库来演示层次聚类的凝聚型和分裂型方法。下面是一个简单的代码示例，展示了如何使用这两种方法进行层次聚类。

我们将演示凝聚型层次聚类：

import numpy as np

from scipy.cluster.hierarchy import dendrogram, linkage, cut_tree

import matplotlib.pyplot as plt

# 定义基因表达数据

data = np.array([

    [1, 2, 3],  # 物种A

    [2, 3, 4],  # 物种B

    [5, 6, 7],  # 物种C

    [8, 9, 10]  # 物种D

])

# 使用“ward”方法进行凝聚型层次聚类

linked = linkage(data, 'ward')

# 绘制树状图

plt.figure(figsize=(10, 7))

dendrogram(linked, labels=['A', 'B', 'C', 'D'])

plt.title('Agglomerative Hierarchical Clustering Dendrogram')

plt.xlabel('Species')

plt.ylabel('Euclidean distances')

plt.show()