基础

KMeans

KMeans

算法流程

• 输入：
  • 样本集$D=\{x_1,x_2,…x_m\}$
  • 需要聚成多少类$k$
  • 最大迭代次数$N$
• 输出：
  • $k$个类簇$C=\{C_1,C_2,…C_k\}$
• 流程
  1. 从数据集$D$中随机选择$k$个样本作为初始的质心$\mu=\{\mu_1,\mu_2,…,\mu_k\}$
  2. 将$k$个类簇初始化为$C_t = \varnothing \;\; t =1,2…k$
  3. from n=1 to N：
     1. 对$m$个样本，计算样本$x_i,i=1,…,m$与$k$个质心的距离$d_{ij} = ||x_i - \mu_j||_2^2$。将该样本纳入最小$d_{ij}$对应的质心对应类别$\lambda_i$中，更新$C_{\lambda_i} = C_{\lambda_i} \cup \{x_i\}$
     2. 对$k$个类簇各自的样本重新计算新的质心$\mu_j = \frac{1}{|C_j|}\sum\limits_{x \in C_j}x$
     3. 如果这$k$个质心都没有发生变化，则break
  4. 输出类簇$C$

目标函数

$k$和距离如何确定

• $k$：根据对数据的先验经验选择一个合适的值，如果没有什么先验知识，则通过交叉验证选择一个合适值
• 距离：欧氏距离

优缺点

• 初始k个质心随机选取，太耗时
• 没必要所有距离都计算

KMeans++

改进的地方

• 初始k个质心不再随机选取，改进如下：
  1. 对数据集$D$随机选择第一个点作为第一个质心$\mu_1$
  2. 对$D$中其他点$x_i$，计算它与已选择的质心中最近质心的距离$D(x_i) = arg\;min||x_i- \mu_r||_2^2\;\;r=1,2,…k_{selected}$
  3. 选择一个新的数据点作为新的质心，选择的原则是：$D(x)$较大的点，被选取作为质心的概率较大
  4. 重复2-3步，直到选出$k$个质心
  5. 将这$k$个质心作为初始化质心去进行KMeans计算

elkan KMeans

改进的地方

• 有些样本点到质心的距离不计算，改进如下：
  1. 利用三角形两边之和大于第三边，两边之差小于第三边的性质，减少距离的计算

缺点：

• 如果样本的特征稀疏、有缺失值的时候，不能使用该方法，因为某些距离无法计算

大样本优化MiNi Batch KMeans

改进的地方

• 当样本量或者特征维度特别大时，KMeans算法非常耗时，使用elkan KMeans都还是耗时，此时就是MiNi Batch KMeans，即使用样本集$D$中的一部分Batch size样本进行KMeans，这部分样本通过无放回随机采样
• 一般要对样本集$D$多运行几次MiNi Batch KMeans，选取相对最优类簇

缺点

• 会失去一些精度，需要效率和精度作权衡

总结

• 优点：
  1. 原理简单，收敛快
  2. 可解释强
  3. 仅需对$k$调参
• 缺点：
  1. $k$值不好调参
  2. 对不是凸的数据集难收敛
  3. 如果隐含类别的数据不平衡，则聚类效果不佳
  4. 迭代只是局部最优
  5. 对噪音和异常点敏感

BIRCH

DBSCAN

谱聚类

进阶

实践

疑难

参考

1. K-Means聚类算法原理
2. BIRCH聚类算法原理
3. DBSCAN密度聚类算法
4. 谱聚类（spectral clustering）原理总结