人工智能 K-均值K-均值

mustang2012 · June 12, 2020 · 10 hits

步骤

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

首先选择 $K$ 个随机的点 ${mu_1,mu_2,cdots,mu_K}inmathbb 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$ 个数 $a_1,a_2,dots,a_k$,则 $a_i$ 被选中的概率为 $P_i=frac{a_i}{sum_j a_j}$;再计算它们的累积概率 $q_i=sum_{j=1}^iP_j$;之后再 $[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$ 作为最后模型的聚类数。

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

No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.