K-means一族聚类算法

无监督算法简介

如上图所示，众所周知，机器学习分为有监督、无监督和强化学习三大块，其中聚类和降维都属于无监督学习。其实如果仔细想一下，聚类也可以某些时候也可以用来降维。常用的聚类算法有：K-means、Mean shift、DBSCAN、GMM、Hierarchical clustering等。下面将详细介绍K-means算法。

K-means

1. 聚类相关算法简介

输入: 集合$S=\{x_1,x_2,...,x_n\}$S={x1​,x2​,...,xn​}, 距离度量函数$d(x_i,x_j)$d(xi​,xj​), 聚类的数目k;
输出: 数据的k个聚类

方法1. K-means: 寻找k个中心点$c_1,c_2,...,c_k$c1​,c2​,...,ck​,使得
$min\sum_{i=1}^nmin_{j\in\{1,...,k\}}d^2\{x_i,c_j\}$min∑i=1n​minj∈{1,...,k}​d2{xi​,cj​}最小.
minimize the sum of squared distance from each item to its nearest averaged center.

方法2. K-median: 寻找k个中心点$c_1,c_2,...,c_k$c1​,c2​,...,ck​,使得
$min\sum_{i=1}^nmin_{j\in\{1,...,k\}}d\{x_i,c_j\}$min∑i=1n​minj∈{1,...,k}​d{xi​,cj​}最小.
minimize the sum of distance from each item to its nearest median (sum of distance !! not sum of squared distance.

方法3. K-center: 寻找k个中心点$c_1,c_2,...,c_k$c1​,c2​,...,ck​,使得
$min(max_{i\in\{1,...,n\}}min_{j\in\{1,...,k\}}d^2\{x_i,c_j\})$min(maxi∈{1,...,n}​minj∈{1,...,k}​d2{xi​,cj​})最小.
minimize the maximum distance from each item to its nearest cluster centers (maximum distance !! not sum of distance.

2. K-means算法(Lloyd’s method)

选取k个初始聚类中心（作为初始cluster）；
repeat:
1)对每个样本点，计算得到距其最近的质心，将其类别标为该质心所对应的cluster；(这一步其实是ＥＭ算法的Ｅ操作)
2)重新计算k个cluser对应的质心（ＥＭ算法的M操作）；
until 聚类中心不再发生变化

3. 随机初始化聚类中心（random initializing）

4. 启发式最远初始化聚类中心 (furthest initializing heuristic)

5. K-means++ 初始化

6. 拓展

参考

[1]https://en.wikipedia.org/wiki/Metric_k-center