K-means 算法

K-means 算法

算法过程描述

1. 随机选取k个点作为簇的中心
2. 对于每一个样本的计算到中心的距离，并将样本分到最近的簇中
3. 更新簇的中心位置
4. 重复上述2-3步，直至簇的中心位置不在发生改变

其中目标函数为
$$J=\sum _{i=1}^N\sum _{k=1}^K{r}_{i,k}||x^i?{\mu }^k|{|}^2$$
其中 r i , k ∈ { 0 , 1 } r_{i,k}\in\{0,1\} ri,k?∈{0,1}表示样本$x_i$是否属于簇$k$

因为如果簇中心位置${\mu }^k$确定，那么$r_{i,k}$也同时将确定，为了优化目标函数，k-means采用迭代求解的方法，首先固定${\mu }^k$，优化$r_{i,k}$；然后固定$r_{i,k}$优化${\mu }^k$。

首先初始化簇中心,固定${\mu }^k$，最小化$J(r_{i,k})$:

分配每个样本点到其最近的中心点所在的簇
$$\begin{gathered} z_i={\arg \min }_{k^{\prime }}\text{dist}(x^i,{\mu }^k) \\ \{\begin{array}{l}{r}_{i,k}=1,k=z_i\\ r_{i,k}=0,k\ne z_i\end{array} \end{gathered}$$
然后固定簇中心${\mu }^k$，最小化$J({\mu }^k)$:
$${\mu }^k=\frac{{\sum }_i{r}_{i,k}{x}^i}{{\sum }_i{r}_{i,k}}$$