9.2. K均值算法的过程与实现

K均值算法的过程与实现

K均值算法（K-Means）是一种流行的聚类算法。

执行过程

以如下数据集的例子来说明K均值算法的执行过程：

对于如图所示的数据集，使用K均值算法将其分成两类数据。
K均值算法的第一步是在数据集中随机生成两点，称为聚类中心（Cluster Centroid）。（要分为多少类，就要生成多少个聚类中心）
K均值算法是一个迭代算法，每一次迭代过程分为两部分：
1. 簇分配
K均值算法会遍历每一个数据，计算该点与每一个聚类中心的距离，该点会被归属到最近的聚类中心。
2. 移动聚类中心
移动聚类中心到当前集群的平均位置。

之后K均值算法会重复上述两步，直到聚类中心不再移动，此时可以认为聚类已经实现。

实现

算法输入

• 簇的数量： \(K\)
• 训练集: \(\{x^{(1)},x^{(2)},...,x^{(m)} \}\)
  对每一个数据而言，\(x^{(i)}\)都是一个n维的向量。

算法过程

K均值算法首先会随机初始化聚类中心\(μ_i\)：
Repeat{
# 计算每个聚类中心到该点的距离，并返回最近距离的聚类中心标签
for \(i=1\) to \(m\)
\(c^{(i)}\):=index(from 1 to \(K\)) of cluster centroid closest to \(x^{(i)}\) 或者 \(c^{(i)}\):=\(min||x^{(i)}-μ_k||^2\)
# 移动聚类中心
for \(k=1\) to \(K\)
\(μ_k\):=arverage of points assigned to cluster \(k\)
}

如果此时出现所有点都不属于某一个聚类中心的情况，则可以直接移除这个聚类中心，或者重新随机初始化这个聚类中心

代价函数

K-Means算法的代价函数会重点跟踪如下的两个参数的变化规律：
\(c^{(i)}\)：当前每一个样本\(x^{(i)}\)所属的聚类中心\(μ_c^{(i)}\)对应的标签
\(μ_k\): 聚类中心的位置
代价函数以如下形式表示：
\[J(c^{(1)}...c^{(m)},μ_1...μ_K)=\frac{1}{m}∑_{i=1}^{m}||x^{(i)}-μ_c^{(i)}||^2\] 代价函数的目标是找到使得\(J(c^{(1)}...c^{(m)},μ_1...μ_K)\)最小化的\(c^{(1)}...c^{(m)},μ_1...μ_K\)。

重回K-Means算法的执行过程： 计算每个聚类中心到该点的距离，并返回最近距离的聚类中心标签的实质是保持\(μ_1...μ_K\)固定，而找到使得\(J\)最小化的\(c^{(i)}\)。
移动聚类中心的实质是保持\(c^{(1)}...c^{(m)}\)不变，找到使得\(J\)最小化的\(μ_k\)。