当前位置: 首页 > news >正文

实用指南:【机器学习基础】机器学习入门核心算法:层次聚类算法(AGNES算法和 DIANA算法)

实用指南:【机器学习基础】机器学习入门核心算法:层次聚类算法(AGNES算法和 DIANA算法)

在这里插入图片描述

一、算法逻辑

层次聚类(Hierarchical Clustering)通过构建树状结构(树状图/Dendrogram)揭示数据内在的层次关系,分为两类:

  1. 凝聚式(Agglomerative)
    • 自底向上:每个样本初始为一个簇 → 迭代合并最近簇 → 最终形成单一簇
    • 流程
      计算距离矩阵 → 合并最近簇 → 更新距离矩阵 → 重复至终止
  2. 分裂式(Divisive)
    • 自顶向下:所有样本初始为一个簇 → 迭代分裂最异质簇 → 直至每个样本一簇
    • 计算复杂度高,较少使用

核心特点

在这里插入图片描述

二、算法原理与数学推导
1. 距离度量

设样本 X = { x 1 , x 2 , . . . , x n } X = \{x_1, x_2, ..., x_n\} X={x1,x2,...,xn}, x i ∈ R d x_i \in \mathbb{R}^d xiRd
常用距离:

2. 簇间距离计算(连接标准)
类型公式特点
单连接 d min ( C i , C j ) = min ⁡ a ∈ C i , b ∈ C j d ( a , b ) d_{\text{min}}(C_i, C_j) = \min_{a \in C_i, b \in C_j} d(a,b) dmin(Ci,Cj)=aCi,bCjmind(a,b)易形成链式结构
全连接 d max ( C i , C j ) = max ⁡ a ∈ C i , b ∈ C j d ( a , b ) d_{\text{max}}(C_i, C_j) = \max_{a \in C_i, b \in C_j} d(a,b) dmax(Ci,Cj)=aCi,bCjmaxd(a,b)对噪声敏感
质心法 d cent ( C i , C j ) = d ( μ i , μ j ) d_{\text{cent}}(C_i, C_j) = d(\mu_i, \mu_j) dcent(Ci,Cj)=d(μi,μj)可能导致逆反(Inversion)

其中 μ i = 1 ∣ C i ∣ ∑ x ∈ C i x \mu_i = \frac{1}{|C_i|}\sum_{x \in C_i} x μi=Ci1xCix 为簇质心, Δ SSE \Delta \text{SSE} ΔSSE 为合并后的簇内平方和增量。

3. 算法伪代码(凝聚式)
输入: 数据集 X, 连接标准
输出: 树状图
1. 初始化 n 个簇,每个簇包含一个样本
2. 计算所有簇对的距离矩阵 D
3.
for k = n to 1:
4. 找到 D 中最小距离的簇对 (C_i, C_j)
5. 合并 C_i 和 C_j 为新簇 C_{
new
}
6. 更新距离矩阵 D(移除 C_i, C_j,添加 C_{
new
}7. 记录合并高度(距离)
8. 生成树状图
三、模型评估
1. 内部评估指标
2. 外部评估指标(已知真实标签)
  • 调整兰德指数(Adjusted Rand Index, ARI)
  • Fowlkes-Mallows Index(FMI)
3. 超参数选择
四、应用案例
1. 生物信息学
2. 文档主题分层
  • 步骤
    1. 文档→TF-IDF向量
    2. 余弦距离 + 平均连接
    3. 切割树状图得到主题层级(如:科技→AI→CV/NLP)
3. 图像分割
  • 流程
    像素→颜色+坐标特征 → Ward法聚类 → 合并相似区域
  • 优势:保留空间连续性
4. 社交网络分析
五、面试题及答案
常见问题
  1. Q: 层次聚类与K-means的本质区别?
    A:

  2. Q: Ward法的目标函数是什么?
    A: 最小化合并后的簇内平方和增量:
    Δ SSE = ∣ C i ∣ ∣ C j ∣ ∣ C i ∣ + ∣ C j ∣ ∥ μ i − μ j ∥ 2 \Delta \text{SSE} = \frac{|C_i||C_j|}{|C_i|+|C_j|} \|\mu_i - \mu_j\|^2 ΔSSE=Ci+CjCi∣∣Cjμiμj2

  3. Q: 何时选择全连接而非单连接?
    A: 当需要紧凑球形簇且数据噪声较少时;单连接易受噪声影响形成链式结构。

  4. Q: 如何处理大规模数据?
    A:

六、相关论文
  1. 奠基性论文

  2. 高效优化

  3. 生物学应用

七、优缺点对比
优点缺点
1. 可视化强(树状图展示层次)1. 计算复杂度高(凝聚式 O ( n 3 ) O(n^3) O(n3)
2. 无需预设聚类数2. 合并/分裂后不可逆
3. 灵活选择距离/连接标准3. 对噪声和离群点敏感(尤其全连接)
4. 适合层次结构数据(如生物分类学)4. 大样本内存消耗大

总结

http://www.hskmm.com/?act=detail&tid=25594

相关文章:

  • CSP-J 第二轮集训 :总结 + 专题细分精讲_from_黄老师
  • ROIR 2024
  • 软件工程第一次随笔 - Nicholas
  • 深入解析:【数据库】关系数据库标准语言-SQL(金仓)下
  • Codeforces Round 1056 (Div. 2) (4/6)
  • 20251006
  • UV使用
  • 动手实验——mybatis generator
  • 学生管理系统面向对象分析报告
  • 荷兰青少年通过Telegram被招募,涉嫌参与俄罗斯支持的黑客活动
  • Moscow International Workshops 2017. Day 4. Lviv NU Contest, GP of Ukraine
  • 小代码使用npm包的方法
  • day18 课程(模块 )
  • Kubernetes(K8s)核心架构解析与实用命令大全 - 教程
  • mzoj 2025/10/6
  • 实验作业1-8 陆绎
  • 全源最短路 Johnson算法
  • 《对象创建的秘密:Java 内存布局、逃逸分析与 TLAB 优化详解》 - 实践
  • go get net/http connections count, using middleware
  • win11开机后卡死,磁盘c盘占用100%,解决方案
  • 跨越国度 解题报告
  • 手写Promise核心代码
  • 手动数据库分库分片策略
  • 大数据分析公司季度业绩与技术进展
  • tmux 终端复用器教程,创建一个持久的会话
  • 理解Transformer中的位置编码
  • 网络风险管理的三大关键洞察
  • 牛客 周赛110 20251007
  • Python列表初始化的陷阱:重复引用的坑
  • MongoDB