Lecture 7: K-Means

• 语言: 英语
• 格式: .pdf
• 来源: funglee.github.io

摘要

文档详细介绍了K-means聚类算法，包括其优化问题、Kernel扩展方法以及层次聚类的实现。内容涵盖了K-means的基本目标、迭代过程、局限性及其改进方法。此外，文档还讨论了如何选择合适的聚类数目K，并提到了使用AIC准则进行评估。K-means算法通过交替优化质心和分配点的过程，旨在最小化总平方误差，尽管其为NP难问题，但通过启发式算法在实践中表现良好。

AI总结

《Lecture 7: K-Means》主要介绍了K-means聚类算法及其相关扩展方法。以下是总结：

### 核心内容

1. **K-means算法概述**
- K-means是一种经典的聚类算法，旨在将数据点划分为K个簇，使得簇内数据点的总距离平方和最小。
- 算法通过迭代优化，交替进行两步：
1. 固定簇中心，将每个数据点分配到最近的簇中心。
2. 固定数据点分配，重新计算每个簇的中心（即簇内数据点的均值）。
- K-means的目标是最小化“损失函数”（总畸变），即所有数据点到其簇中心的欧氏距离平方和：
$$ L(\mu, \mathbf{X}, \mathbf{Z}) = \|\mathbf{X} - \mathbf{Z}\mu\|^2 $$
其中，$\mathbf{X}$是数据矩阵，$\mathbf{Z}$是分配矩阵，$\mu$是簇中心矩阵。

2. **K-means的局限性**
- **硬分配**：每个数据点只能完全属于一个簇，无法表示概率性或部分隶属。
- **对簇形状的敏感性**：K-means假设簇是凸的（圆形或椭圆形），对非凸形状的簇表现不佳。
- **簇大小的均衡性**：当簇大小差异较大时，算法效果可能下降。
- **计算复杂度**：K-means问题是NP难的，但通过启发式算法（如交替优化）可以在实践中获得较好的结果。

3. **扩展方法**
- **核K-means**：通过引入核函数，将数据映射到高维空间，从而能够处理非线性可分的数据，改善了K-means对非凸形状簇的处理能力。
- **层次聚类**：提供了一种灵活的聚类方法，通过构建层次结构（自上而下或自下而上）来划分数据，避免了对K值的严格依赖。

4. **簇数选择与评估**
- 使用AIC（赤池信息准则）来选择最优的簇数K：
$$ AIC = 2L(\hat{\mu}, \mathbf{X}, \hat{\mathbf{Z}}) + K\log D $$
其中，$L$是损失函数，$D$是数据维度。选择使AIC最小的K值以避免过拟合。

### 总结
K-means是一种简单而有效的聚类算法，但在处理复杂数据分布时存在局限性。通过扩展方法（如核K-means和层次聚类），可以克服部分限制。选择合适的簇数和多次运行不同的初始值有助于提高算法的性能和结果的可靠性。