K-Means 聚类

问题

给定m个无标签的数据点，将它们分成k个聚类，使得同一聚类内的点相似度高，不同聚类间的点相似度低

算法步骤

K-Means算法

1. 随机初始化k个聚类中心${\mu }_1,{\mu }_2,\dots ,{\mu }_k$

2. 重复以下步骤直到收敛：

   聚类分配步骤：

   $$c^{(i)}=\arg \underset{j}{\min }\Vert x^{(i)}-{\mu }_j{\Vert }^2$$

   聚类中心更新步骤：

   $${\mu }_j=\frac{1}{|S_j|}\sum _{i\in S_j}{x}^{(i)}$$

   其中$S_j=\{i:c^{(i)}=j\}$

代价函数（失真函数）

$$J(c^{(1)},\dots ,c^{(m)},{\mu }_1,\dots ,{\mu }_k)=\frac{1}{m}\sum _{i=1}^m\Vert x^{(i)}-{\mu }_{c^{(i)}}{\Vert }^2$$

目标：最小化所有数据点到其对应聚类中心的平方距离之和

优化

随机初始化

推荐方法：

1. 随机选择k个训练样本
2. 将聚类中心设置为这k个样本的位置

注意：应保证$k<m$

解决局部最优问题

多次随机初始化：

1. 进行50-1000次不同的随机初始化
2. 对每次初始化运行K-means算法
3. 选择代价函数J最小的结果

选择聚类数K——肘部方法 (Elbow Method)

1. 绘制不同K值对应的代价函数J
2. 寻找曲线的”肘部”（斜率显著变化的点）
3. 选择肘部对应的K值

局限性：很多时候肘部不明显