机器学习--K-Means

K均值聚类

算法过程

  $K-means$ 是 聚类 $clustering$ 算法的一种，就是给你一坨东西，让你给他们分类：

  我们的 $K-means$ 大概是这样一个流程：

1. 第一步随机生成两个点（因为这里我想分两类，你想分几类你就弄几个点），标记为两个聚类中心 $clustercentriod$，像这样：

2. 然后重复以下两个步骤：

   1. 遍历每个点 $x^{(i)}$，分别计算点 $x^{(i)}$ 到两个聚类中心的距离 $d_1$ 和 $d_2$，然后比较大小。并标记这个点为距离更小的那一类

   2. 分别遍历同一类的所有点，计算这些点的几何平均位置，并把聚类中心移动到这个位置

  这样说起来可能很抽象，我们还是用图像来更清晰的表示一下这个过程：

  图画到这里我们就能明显的观察到两个聚类已经被划分好了。

优化目标函数

  像前面介绍的线性回归、逻辑回归、$SVM$ 一样，这里的 $K-means$ 也有一个用于优化的函数：

  $notation$：$c_i$ 表示点 $x_i$ 的类别，${\mu }_k$ 表示聚类中心 $k$，${\mu }_{c_i}$ 表示 $x_i$ 所属的那个聚类中心

$$J(c_1,\cdots ,c_m,{\mu }_1,\cdots ,{\mu }_K)=\frac{1}{m}\sum _{i=1}^m|x_i-{\mu }_{c_i}{|}^2$$

  我们要做的就是：

$$\underset{c,\mu }{\min }J(c_1,\cdots ,c_m,{\mu }_1,\cdots ,{\mu }_K)$$

  看得出来，这就是要最小化所有点 $x_i$ 与其所属的聚类中心 ${\mu }_{x_i}$ 的距离的平方和。

跑$114514$次 $k-means$

  可能你也注意到了，我们如果只跑一遍 $k-means$ 的话可能不会得到一个很好的分类方案，所以我们考虑每次随机初始化聚类中心，然后跑很多遍（取决于你的数据规模和时间）$k-means$，对于每次计算出来的 $c,\mu$ 算出它的 $J(c,\mu )$，然后在其中选择 $J(c,\mu )$ 最小的那个分类方案作为最后的答案。