K-Means 是聚类算法中应用最广泛的一种算法，它是一种迭代算法。

算法原理

该算法的输入为：

1. 簇的个数 K
2. 训练集

算法原理：

1. 先随机选取 K 个点 作为聚类质心（cluster centroids）。

1. 簇分配：将每一个点分配给离它最近的质心，这样这些点就被初步分成了 K 个簇。用数学表达这个过程就是：对于某个点 ，它所属的簇为（注：双绝对值符号表示两个向量在空间中的距离），或者也可，一般用后者，因为省去了开方这一步。

1. 移动质心：计算每一个簇中所有点的均值，将其作为新的质心。

1. 重复执行 2~3 步直到质心不再改变。下图中黑线是质心的移动轨迹，黑色的叉是质心最终的位置。

优化目标

和之前的监督学习中的算法一样，K-Means 也有损失函数：
所以优化目标为

上面式子中的 表示 所属的簇的质心。
所以，损失函数的含义是：每个点到它所属簇的质心的距离的平方的平均值。
优化目标就是最小化这个平均值，得到每个点所属的簇的编号 ，以及所有质心

:::info 簇分配这一步实际上就是在最小化损失函数。 :::

代码实现

先导包：

import numpy as np
import matplotlib.pyplot as plt

生成测试数据：

dt1 = np.array([2, 2]) + np.random.random((10, 2)) * 2
dt2 = np.array([4, 2.5]) + np.random.random((10, 2)) * 2
dt3 = np.array([3.5, 0]) + np.random.random((10, 2)) * 2
data = np.vstack((dt1, dt2, dt3))

画图观察数据：

plt.scatter(data[:, 0], data[:, 1])
plt.show()

实现 K-Means：

K = 3   # 簇的个数
cluster_no = np.zeros(len(data))   # data 中每个样本所属的簇的编号。先全部初始化为 0
centroid = data[np.random.choice(data.shape[0], K), :]    # 从 data 中随机选取 K 个点作为质心
centroid_history = []   # 用来记录质心的变化历史
while True:
    centroid_history.append(np.array(centroid))
    # 簇分配
    distances = []  # 每个点到 K 个质心的距离的平方
    for ct in centroid:
        dst = np.sum((ct - data) ** 2, axis=1)  # 计算某一个质心 ct 与 data 中所有点的距离的平方
        distances.append(dst)
    distances = np.array(distances)
    cluster_no = np.argmin(distances, axis=0)
    # 移动质心
    for i in range(K):
        dt = data[cluster_no == i]
        if len(data) > 0:
            centroid[i] = np.mean(dt, axis=0)
    # 判断新质心与原来的质心相比，是否有改变，若没有，跳出循环
    if np.all(centroid == centroid_history[-1]):
        break

可视化展示结果：

centroid_history = np.array(centroid_history)
for i in range(K):
    dt = data[cluster_no == i]
    if len(data) > 0:
        plt.scatter(dt[:, 0], dt[:, 1])     # 可视化 data
    plt.plot(centroid_history[:, i, 0], centroid_history[:, i, 1], 'o-', ms=4, color='black', alpha=0.5)    # 可视化质心的变化
plt.scatter(centroid[:, 0], centroid[:, 1], marker='x', s=100, c='black')   # 质心的最终位置
plt.show()

几个问题的处理

1. 有时候可能会出现这种情况：某些簇中一个点都没有。此时可以将该簇的质心直接移除，这样最后得到的簇的个数就会少于 K，而非 K 个。如果非要得到 K 个簇，那就重新初始化这个质心。

2. 随机初始化的质心不同，最后的聚类结果也可能不同，可能会陷入局部最优。解决方案：多运行几次算法，计算每次的 loss，选择 loss 最小的。注：如果 K 比较小（比如为 2 ~ 10），那么这种方法的效果很好，但如果 K 很大（成百上千），使用这种方法可能会有点效果，但并不会改善太多。

超参数的选择

如何选择 K：

• 将数据可视化出来，观察数据，手动选择 K。
• 肘部法则。
• 根据实际业务的需要进行选择。

算法缺点

1. K-Means 算法很容易受到异常值的影响。

2. 对于非球状的数据分布，可能并不适合用 K-Means 算法。例如下面这两张图中，左侧的图是我们想要的分类结果，而右侧是 K-Means 算法分类的结果：

这种数据分布情况用 DBSCAN 算法更适合。