码海

# 层次聚类算法

# 基本概念

层次聚类（Hierarchical Clustering）是一种基于层次分解的聚类方法，它通过构建聚类的层次结构来完成聚类过程。根据构建的策略不同，可分为自底向上的凝聚式（Agglomerative）和自顶向下的分裂式（Divisive）两种方法。

# 数学原理

# 1. 距离度量

层次聚类算法需要定义两个簇之间的距离，常用的距离度量方法包括：

  1. 单链接（Single Linkage）

    dmin(Ci,Cj)=minp∈Ci,q∈Cjd(p,q)d_{min}(C_i,C_j) = \min_{p\in C_i,q\in C_j} d(p,q)

  2. 全链接（Complete Linkage）

    dmax(Ci,Cj)=maxp∈Ci,q∈Cjd(p,q)d_{max}(C_i,C_j) = \max_{p\in C_i,q\in C_j} d(p,q)

  3. 平均链接（Average Linkage）

    davg(Ci,Cj)=1∣Ci∣∣Cj∣∑p∈Ci∑q∈Cjd(p,q)d_{avg}(C_i,C_j) = \frac{1}{|C_i||C_j|}\sum_{p\in C_i}\sum_{q\in C_j} d(p,q)

  4. Ward方法

    dward(Ci,Cj)=∣Ci∣∣Cj∣∣Ci∣+∣Cj∣∣∣μi−μj∣∣2d_{ward}(C_i,C_j) = \sqrt{\frac{|C_i||C_j|}{|C_i|+|C_j|}}||\mu_i-\mu_j||_2

其中：

  • CiC_i, CjC_j 表示两个不同的簇
  • pp, qq 表示簇中的数据点
  • μi\mu_i, μj\mu_j 表示簇的质心
  • ∣Ci∣|C_i| 表示簇 CiC_i 中的样本数

# 2. 算法步骤

# 凝聚式层次聚类（自底向上）

  1. 初始化：将每个样本点作为一个簇
  2. 计算距离：计算所有簇之间的距离
  3. 合并：
    • 找到距离最近的两个簇
    • 将它们合并成一个新的簇
  4. 更新：更新新簇与其他簇之间的距离
  5. 重复：重复步骤3-4，直到达到预定的簇数量或满足终止条件

# 分裂式层次聚类（自顶向下）

  1. 初始化：将所有样本放在一个簇中
  2. 分裂：
    • 选择一个簇进行分裂
    • 使用某种算法（如K-means）将该簇分成两个子簇
  3. 重复：重复步骤2，直到每个簇只包含一个样本或达到预定的簇数量

# 优势特点

# 1. 层次结构

  • 可以生成树状图（dendrogram）展示聚类过程
  • 直观显示数据的层次关系
  • 便于确定最佳簇数

# 2. 灵活性

  • 无需预先指定簇的数量
  • 可以选择不同的距离度量方法
  • 适应不同形状的簇

# 3. 确定性

  • 聚类结果稳定
  • 不受初始值影响
  • 结果可解释性强

# 应用场景

  1. 生物信息学

    • 基因表达数据分析
    • 蛋白质结构分类

  2. 文档聚类

    • 文本主题分类
    • 新闻分组

  3. 客户细分

    • 用户行为分析
    • 市场细分

  4. 图像处理

    • 图像分割
    • 目标识别

# 优缺点

# 优点

  1. 层次结构清晰
  2. 不需要预设簇数
  3. 结果稳定且可解释
  4. 适用于发现数据的层次关系

# 缺点

  1. 计算复杂度高（通常为O(n³)）
  2. 存储开销大
  3. 对噪声和异常值敏感
  4. 一旦合并或分裂完成，不能撤销

# 实践建议

# 1. 数据预处理

  • 标准化数据
  • 处理异常值
  • 降维（如果维度过高）

# 2. 距离度量选择

  • 单链接：适合细长形状的簇
  • 全链接：适合紧凑的球形簇
  • 平均链接：一般情况下的折中选择
  • Ward方法：倾向于生成大小相近的簇

# 3. 终止条件设置

  • 根据树状图选择合适的切割点
  • 结合业务需求确定簇的数量
  • 使用评估指标辅助决策

# 4. 结果评估

  • 轮廓系数（Silhouette Coefficient）
  • 调整兰德指数（Adjusted Rand Index）
  • 可视化验证

# 代码实现

from sklearn.cluster import AgglomerativeClustering
import numpy as np

# 创建示例数据
X = np.array([[1, 2], [1, 4], [1, 0],
              [4, 2], [4, 4], [4, 0]])

# 创建聚类器
clustering = AgglomerativeClustering(n_clusters=2)

# 进行聚类
clustering.fit(X)

# 获取聚类标签
labels = clustering.labels_

# 进阶优化

  1. 增量式层次聚类

    • 处理大规模数据集
    • 降低计算复杂度

  2. 约束层次聚类

    • 引入先验知识
    • 添加必连和勿连约束

  3. 集成学习方法

    • 结合多个层次聚类结果
    • 提高聚类稳定性

  4. 并行化实现

    • 利用分布式计算
    • 加速大规模数据处理

← DBSCAN聚类算法 →