机器学习(八)：K-Means聚类原理与实战

声明：未经允许禁止转载与抄袭。

前言

$k$均值（$k$-means）聚类算法是一种经典的无监督聚类算法，本文将深入解析其理论原理，并在真是数据集上进行算法实践，话不多说，请看下文。

算法原理

给定样本集 D = { x 1 , x 2 , … , x m } D=\left\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_m\right\} D={x1​,x2​,…,xm​}，其中每个样本${\mathbf{x}}_i$都由一个向量表示，例如以周志华老师西瓜书中的西瓜数据集为例，每个样本都包含两个属性密度和含糖量，这两个属性值组成的向量便是该样本的向量表示。

$k$均值算法旨在将样本集$D$划分为$k$个簇，即 C = { C 1 , C 2 , … , C k } C=\left\{C_1,C_2,\ldots,C_k\right\} C={C1​,C2​,…,Ck​}，使得每个样本都被划分到与其距离最小的簇中。用数学来刻画就是，$k$均值算法希望能够最小化所划分的$k$个簇的平方误差，即：
$${\text{argmin}}_C\sum _{i=1}^k\sum _{\mathbf{x}\in C_i}{\Vert \mathbf{x}-{\mu }_i\Vert }_2^2$$

其中 ${\mathbf{\mu }}_i=\frac{1}{|C_i|}{\sum }_{\mathbf{x}\in C_{\mathbf{i}}}\mathbf{x}$ 表示簇 $C_i$ 的均值向量，$\mathbf{x}$表示簇$C_i$中的样本。

$k$均值算法事先设定数据集$D$要划分为$k$个簇，初始化时，会先从数据集$D$中随机挑选$k$个样本作为各个簇的初始均值向量（簇中心）。然后遍历所有样本，分别计算各个样本与各个簇中心的距离，并将样本划分到与距离最小的簇中。待到所有样本都划分完毕后，将各个簇样本向量的均值向量作为新的簇均值向量，重复上述的步骤，直到上一轮所有的簇中心均值向量与本轮计算的结果相同为止。该算法的具体算法流程如下：

需要注意的是，实际计算过程中为避免计算时间过长，该算法的终止条件不可能这样严苛。西瓜书中给出了两种方案：

• 设置一个最大轮数。
• 设置均值向量的变化阈值，若新簇中心与旧簇中心之间的距离不超过该阈值即可，而不是严格不变。

对于$k$均值聚类算法而言，数据集的预处理和$k$值的选取同样十分重要，可以参考博客【机器学习】K-means（非常详细），限于篇幅原因，本文就不详细展开。

算法实践

本文在鸢尾花数据集上进行$k$均值聚簇算法的实践。

基于最大轮数终止的$k$均值聚类算法实现如下所示，两个向量之间的距离计算本文采用了余弦距离。

import numpy as np
from scipy.spatial.distance import cdist


class KMeansModel:
    def rand_pick(self, x, k):
        """
        随机选取k个簇中心
        """
        n = x.shape[0]
        indices = np.random.choice(n, k, replace=False)
        return x[indices]

    def calculate_distance(self, x, centers):
        """
        计算簇中心与数据样本之间的余弦距离
        centers: 簇中心数据 (k, d)
        x: 样本 (N, d)
        """
        return cdist(x, centers, metric="cosine")

    def get_centers(self, k, x, y):
        """
        根据计算结果重新计算簇中心
        y: 根据距离将数据集划分的标签数组 (N)
        """
        centers = np.zeros((k, x.shape[1]))
        for label in range(k):
            centers[label] = np.mean(x[y == label], axis=0)
        return centers

    def get_label(self, dis):
        """
        根据距离矩阵将每个样本划分到距离最小的簇中心
        """
        return np.argmin(dis, axis=-1)

    def cluster(self, x, k, times):
        """
        进行KMeans聚类
        x: 数据样本 (N, d)
        k: 类别数
        tims: 迭代次数
        """
        # 随机选取k个作为初始簇中心
        centers = self.rand_pick(x, k)
        for _ in range(times):
            # 计算各个样本到簇中心的距离
            dis = self.calculate_distance(x, centers)
            # 根据距离矩阵将样本进行划分
            y = self.get_label(dis)
            # 重新计算新的簇中心
            centers = self.get_centers(k, x, y)
        return y

在鸢尾花数据集上，设置的实验参数为$k=3$，$times=500$，即将整个数据集聚为$3$个簇，算法迭代$500$轮终止。

算法额外对比了基于sklearn库实现的$k$均值聚簇算法的效果，为更直观的展示，本文对数据集进行PCA降维，下图从左到右分别是真实标签、本文模型的聚类结果、基于sklearn算法的聚类结果。从结果可以看出，本文实现的模型在鸢尾花数据集上效果还是不错的。

结语

以上便是本文的全部内容，如果感觉不错可以支持一下，若有任何问题敬请批评指正。