Cluster 分类

Cluster Type Description
Well-Separated 簇间完全分离，无重叠。
Center-Based 每个簇由中心点（如均值、中位数）定义，数据点靠近所属簇中心。
Contiguity-Based 基于空间邻近性，形成连通区域。
Density-Based 高密度区域形成簇，低密度区域分隔簇（如DBSCAN）。
Objective Function 通过优化目标函数（如最小化误差平方和）划分簇。

Partitional Clustering

Hierarchical Clustering

  • 聚合式 (Agglomerative): 自底向上，初始每个点为独立簇，逐步合并最近簇。
  • 分裂式 (Divisive): 自顶向下，初始一个簇，逐步分裂为更小簇。

Agglomerative

  • 使用 Distance/Similarity/Proximity Matrix
  • Space: O(n2)O(n^2)
  • Time: O(n3)O(n^3), O(n2log⁡n)O(n^2\log n)
  1. 计算 Proximity Matrix
  2. 循环，直到只剩一个 cluster
    1. 合并两个最近的 cluster
    2. 更新 Proximity Matrix

如何更新 Proximity Matrix?

  1. MIN: 簇间距离取最近点距离，易处理非球形簇但易受噪声影响。
  2. MAX: 取最远点距离，抗噪但易分裂大簇. Biased towards globular clusters
  3. Group Avg: 取所有点对的平均距离，平衡抗噪与形状适应性。Biased towards globular clusters
  4. Distance between Centroids
  5. Ward’s Method: 最小化簇内误差平方和

Divisive: 最小生成树

  1. 构建 MST
    1. 计算点对之间的距离矩阵
    2. 生成 Proximity Graph 的 MST
  2. 分裂 MST
    1. 从 MST 中选出一条边，断开。
    2. 形成的两个连通块对应两个不同的 cluster