层次聚类

评论
35 views

层次聚类（Hierarchical Clustering）是一种聚类分析方法，通过构建层次结构树（树状图，Dendrogram）将样本数据逐渐合并或划分为不同的群组（簇）。层次聚类不同于K-means等非层次的聚类算法，它不需要提前指定簇的数量，而是通过树形结构自底向上或自顶向下地聚类。

层次聚类的两种主要方法：

  1. 凝聚式层次聚类（Agglomerative Hierarchical Clustering）：

  2. 这种方法是自底向上的。它从每个数据点开始，每个数据点作为一个独立的簇。然后，逐步合并相似度最高的两个簇，直到所有数据点都合并成一个簇。

  3. 分裂式层次聚类（Divisive Hierarchical Clustering）：

  4. 这种方法是自顶向下的。它从整个数据集开始，将所有数据视为一个簇，然后根据数据的差异逐步划分为更小的簇，直到每个数据点成为一个单独的簇。

聚类过程：

  • 步骤 1：计算相似度或距离：

  • 聚类方法首先需要计算样本之间的相似度或距离。常见的距离度量方法有：

    • 欧几里得距离（Euclidean Distance）：常用于数值数据。
    • 曼哈顿距离（Manhattan Distance）：适用于离散数据。
    • 余弦相似度：常用于文本数据。

  • 步骤 2：计算簇之间的相似度：

  • 在层次聚类中，两个簇之间的相似度（或距离）可以通过多种方式来定义，常见的定义方式有：

    • 单链接（Single Linkage）：两个簇之间的距离是簇中最靠近的两个点之间的距离。
    • 全链接（Complete Linkage）：两个簇之间的距离是簇中最远的两个点之间的距离。
    • 平均链接（Average Linkage）：两个簇之间的距离是簇中所有点对之间距离的平均值。
    • 质心链接（Centroid Linkage）：计算簇的质心（即簇内所有点的均值），然后测量两个簇之间质心的距离。

  • 步骤 3：合并（凝聚）或划分（分裂）簇：

  • 在每一步，选择最相似（或最接近）的两个簇进行合并或分裂。

  • 凝聚式方法会合并最相似的簇，而分裂式方法会根据某个准则拆分簇。

  • 步骤 4：生成树状图（Dendrogram）：

  • 在每一步聚类过程中，记录簇的合并过程。最终结果是一个树状图，展示了数据点合并的顺序和每次合并时的相似度/距离。

树状图（Dendrogram）

树状图是层次聚类的输出，展示了各个数据点之间逐步合并的过程。它的横轴表示样本数据点或簇，纵轴表示样本之间的距离（或者相似度）。通过树状图，可以清晰地看到样本是如何聚类的，以及在不同的距离阈值下，哪些样本被聚成同一个簇。

如何选择簇数

虽然层次聚类不需要预先指定簇的数量，但在实际应用中，我们通常需要从树状图中选择一个合适的切割阈值，从而决定聚类的数量。常见的方法包括：

  • 距离阈值：选择一个合适的距离阈值来决定合并停止的时刻，通常根据业务需求或领域知识来判断。
  • 肘部法则：类似K-means的肘部法则，可以通过观察树状图中的距离变化来选择一个合理的切割位置。

层次聚类的优缺点

优点：

  1. 不需要预设簇数：

  2. 层次聚类不需要像K-means那样提前指定簇的数量，它可以根据数据的结构自动生成聚类结果。

  3. 能够生成完整的聚类层次结构：

  4. 层次聚类通过树状图能够清楚地展示簇之间的关系及其层次结构，对于探索数据和进行可视化非常有帮助。

  5. 适用于各种类型的数据：

  6. 层次聚类可以灵活地使用不同的距离度量方法，适应不同类型的数据（如数值型、文本型等）。

缺点：

  1. 计算复杂度高：

  2. 层次聚类的计算复杂度较高，尤其是在数据量大的时候。凝聚式层次聚类的时间复杂度是O(n²)，因此在处理大规模数据时，性能可能较差。

  3. 对噪声敏感：

  4. 层次聚类容易受到噪声和离群值的影响，因为每次聚类都是基于最小距离进行的，这可能导致噪声点被错误地合并到簇中。

  5. 无法处理非凸形状的簇：

  6. 层次聚类基于距离度量，对于形状不规则的簇（如非凸形状簇），可能无法获得理想的聚类效果。

  7. 难以调整：

  8. 一旦进行合并或划分，无法撤回或调整结果。与K-means等方法不同，层次聚类没有明确的迭代过程来调整簇的形状。

层次聚类的实现（Python示例）

使用Python的scikit-learn库，可以轻松实现层次聚类。以下是一个使用AgglomerativeClustering的示例：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage

# 创建一些示例数据
X = np.array([[1, 2], [1, 3], [2, 3], [6, 5], [7, 6], [8, 8]])

# 使用凝聚式层次聚类进行聚类
model = AgglomerativeClustering(n_clusters=2)
model.fit(X)

# 打印聚类结果
print("Cluster labels:", model.labels_)

# 生成树状图
Z = linkage(X, 'ward')  # 'ward'是常用的聚类方法
dendrogram(Z)
plt.show()

在这个例子中，我们使用了AgglomerativeClustering类来进行层次聚类，设置簇数为2。接着，我们使用scipy.cluster.hierarchy中的linkage方法生成树状图。

总结

  • 层次聚类是一种基于距离的聚类方法，主要分为凝聚式和分裂式两种方式。
  • 它能够生成层次结构的树状图，展示不同簇之间的关系。
  • 层次聚类不需要提前指定簇的数量，但计算复杂度较高，且容易受到噪声和离群值的影响。
  • 对于小到中等规模的数据，层次聚类是一种直观且有效的聚类方法，特别适合需要可视化聚类过程的场景。