K-均值

步骤

K-均值是最普及的聚类算法，它接受一个未标记的数据集$D={x^{(1)},x^{(2)},\cdots,x^{(m)}}$，然后将数据聚类成不同的组。

首先选择$K$个随机的点${\mu_1,\mu_2,\cdots,\mu_K}\in\mathbb R^n$作为聚类中心(cluster centroids)，也就是聚类的簇(cluster)数；

然后，我们将样本点进行聚类，让样本点找到离自己最近的聚类中心，用$c^{(i)}=k$表示将$x^{(i)}$样本被分到了$k$类，则

$$c^{(i)}:=\min_k||x^{(i)}-\mu_k||^2$$

在分类好了之后，计算第$k$个簇中的$s$个样本点的均值，并令其为新的聚类中心：

$$\mu_k:=\frac{1}{s}\sum_{c_i=k}x^{(i)}$$

然后对$\mu_k$不断迭代，直至收敛。

代价函数

K-均值最小化问题，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和，因此 K-均值的代价函数（又称畸变函数 Distortion function）为：

$$J(c^{(1)},\dots,c^{(m)},\mu_{1},\dots,\mu_{k})=\frac{1}{m}\sum_{i=1}^m||x^{(i)}-\mu_{c^{(i)}}||^2$$

其中$\mu_{c^{(i)}}$为离$x^{(i)}$点最近的聚类中心，这一种常见的衡量聚类模型的指标，也被称作均方差 MSE(Mean of Squared Error) 。

优化目标为：

$$\min_{c^{(1)},\dots,c^{(m)}\\\mu_{1},\dots,\mu_{k}}J(c^{(1)},\dots,c^{(m)},\mu_{1},\dots,\mu_{k})$$

在每次进行$c^{(i)}$和$\mu_k$的迭代时，代价函数都减小，如果代价函数增大了，那就出错了。

随机初始化

在进行K-均值聚类时，首先需要随机初始化所有的$K$个聚类中心点。在随机初始化时，首先需要选择聚类中心点数量$K<m$；之后，随机选择$K$个样本点，令$K$个聚类中心分别与这$K$个训练实例相等。

K-均值的一个问题在于，在选择特殊的初始样本点时，它有可能会停留在一个局部最小值处，可能是一个奇怪的位置。为了解决这个问题，我们通常需要多次运行K-均值算法，每一次都重新进行随机初始化，最后再比较多次运行K-均值的结果，选择代价函数最小的结果。这种方法在$K$较小的时候还是可行的，但是如果$K$较大，这么做可能不会有太大的改善。

K-means++

K-means++算法改进了K-均值算法中选择初始的聚类中心的方式，具体步骤如下：

• 随机选取一个样本点作为聚类中心$\mu_1$；

• 计算每个其余的样本点距离当前聚类中心的距离并找到最距离$D(x^{(i)})$：

  $$D(x^{(i)})=\min\{dist(x^{(i)},\mu_1),dist(x^{(i)},\mu_2),\dots,dist(x^{(i)},\mu_k)\}$$

  则$x^{(i)}$被选作下一个聚类中心的概率$P(x^{(i)})$为：

  $$P(x^{(i)})=\frac{D(x^{(i)})}{\sum_{j=1}^mD(x^{(j)})}$$

  最后用轮盘法选择出下一个聚类中心。

• 重复上一步，直至选择出$K$个聚类中心。

轮盘法是一种随机选择的算法，通俗点说，就是越大的数字被选中的概率越大。

假设有$k$个数$a1,a_2,\dots,a_k$，则$a_i$被选中的概率为$P_i=\frac{a_i}{\sum_j a_j}$；再计算它们的累积概率$q_i=\sum{j=1}^iPj$；之后再$[0,1]$上随机生成一个伪随机数$r$。当$q{i-1}<r<q_i$时，$a_i$就被选出来了。

K的选择

在上述过程中$K$的数量时已经给定的，但要是未知的该怎么办呢？

我们可以通过肘部法则(elbow method)来帮助我们确定聚类中心的个数：从$K=1$开始进行聚类并且求出代价函数，之后令$K:=K+1$继续计算，循环到一定数目的时候，画出如下的图：

选择转折较大聚类数$K$为最后的聚类数。换句话说，在每次增加$K$时，找到使$J(c^{(i)},\mu_k)$变化最大的$K$作为最后模型的聚类数。

当然这种方法只是为聚类数的选择做一个参考，实际的选择还是需要多方考虑参能做最后的确定。