K-Means

  • Partitional Clustering
  • 每一个 cluster 与一个 centroid 相联系，每一个点分配到其最近的 centroid
  • KK 是超参数
算法流程
  1. 选定初始的 KK 个点作为 centroid
  2. 循环，直到 KK 个 centroid 不再发生变化
    1. 把所有点分配到这 KK 个 cluster
    2. 重新计算 KK 个 centroid

O(n×K×I×d)O(n×K×I×d)，其中 nn 为数据量，KK 为簇数，II 为迭代次数，dd 为特征数。

我们用平均距离衡量 K-Means 算法的优劣：

SSE=∑i=1K∑x∈Cidist2(x,mi) SSE=\sum_{i=1}^K \sum_{x \in C_i} \text{dist}^2(x, m_i)

局限性

  1. 对初始中心的选取很敏感
  2. 需要预先指定 KK
  3. 可能出现空聚类

针对这些问题，我们可以作出一些改进：

  1. 多运行几次算法，增加找到最优解的概率
  2. 用 Hierarchical Clustering 优化初始点的选取
  3. K-Means 算出多于 KK 个 centroid，再从其中选出 KK 个
  4. 后处理
  5. Bisecting K-Means

空聚类的处理

  1. 将距离所有簇中心最远的样本点选为空簇的新中心。该点对当前聚类的误差（SSE）贡献最大，重新分配它有助于优化整体聚类效果。
  2. 从SSE（误差平方和）最高的非空簇中选择一个点，将其作为空簇的新中心。该簇的误差较大，说明其内部数据分布分散，分裂或调整其中心可能改善聚类质量。
  3. If there are several empty clusters, the above can be repeated several times.

增量法更新

  • 不会产生空簇

前、后处理

前处理：

  • Normalization
  • 去除异常值

后处理：

  • 去除小聚类（可能由异常值组成）
  • 分裂稀疏、分散的聚类
  • 合并close, 紧密的聚类
  • 使用 ISODATA