K-Means 聚类的工作原理 - Amazon SageMaker
Amazon Web Services 文档中描述的 Amazon Web Services 服务或功能可能因区域而异。要查看适用于中国区域的差异,请参阅 中国的 Amazon Web Services 服务入门 (PDF)

本文属于机器翻译版本。若本译文内容与英语原文存在差异,则一律以英文原文为准。

K-Means 聚类的工作原理

K-means 是一种训练模型的算法,可将相似对象组合在一起。k-means 算法通过将输入数据集中的每个观察结果映射到 n 维空间的某个点 (其中 n 是观察结果的属性数量) 来完成此操作。例如,您的数据集可能包含某个特定位置的温度和湿度的观察结果,这些观察结果映射到 2 维空间的某些点 (t, h)。

注意

聚类算法为自主型。在自主学习中,不使用可能与训练数据集中的对象相关联的标签。有关更多信息,请参阅 无监督学习

在 k-means 聚类中,每个聚类都有一个中心。在模型训练期间,k-means 算法使用对应于数据集中每个观察结果的点与聚类中心之间的距离作为聚类的基础。您选择要创建的聚类数量 (k)。

例如,假设您要创建一个可识别手写数字的模型,并且您选择 MNIST 数据集用于训练。该数据集提供了数千个手写数字 (0 到 9) 的图像。在本例中,您可以选择创建 10 个聚类,每个数字 (0、1、...、9) 一个聚类。作为模型训练的一部分,k-means 算法将输入图像划分为 10 个聚类。

MNIST 数据集中的每张图就是一个 28x28 像素的图像,总共 784 像素。每个图像对应于 784 维空间里的一个点,类似于 2 维空间的点 (x, y)。要查找某个点所属的聚类,k-means 算法会查找该点与所有聚类中心之间的距离。然后,它会选择最靠近中心的聚类作为图像所属的聚类。

注意

Amazon SageMaker 使用该算法的自定义版本,您可以选择通过指定额外的聚类中心 (K = k*x) 来提高模型精度,而不是指定算法创建 k 个集群。但是,该算法最终会将其减少为 k 个聚类。

在中 SageMaker,您可以指定创建训练作业时的集群数量。有关更多信息,请参阅 CreateTrainingJob。在请求正文中,您添加 HyperParameters 字符串映射以指定 kextra_center_factor 字符串。

以下简要介绍了 k-means 在模型训练中的 SageMaker工作原理:

  1. 它确定初始 K 个聚类中心。

    注意

    在以下主题中,K 个聚类指的是 k * x,您将在创建模型训练作业时指定其中的 kx

  2. 它将迭代输入训练数据并重新计算聚类中心。

  3. 这样可将生成的聚类数量减少至 k (如果数据科学家已在请求中指定创建 k*x 个聚类)。

下面几节也介绍了数据科学家可能指定的一些参数,这些参数用于配置模型训练作业以作为 HyperParameters 字符串映射的一部分。

步骤 1:确定初始聚类中心

在中使用 k-means 时 SageMaker,初始聚类中心是在随机抽样的小批量中从观测值中选择的。选择下列策略之一来确定这些初始聚类中心的选择方式:

  • 随机方法 – 在您的输入数据集中随机选择 K 个观察数据作为聚类中心。例如,您可以选择一个指向 784 维空间的聚类中心 (对应于 MNIST 训练数据集中的任意 10 个图像)。

  • k-means++ 方法,其工作原理如下所示:

    1. 从一个聚类开始,并确定其中心。您从训练数据集中随机选择一个观察结果,并将对应于该观察结果的点用作聚类中心。例如,在 MNIST 数据集中,随机选择一个手写数字图像。然后,在 784 维空间中选择与该图像对应的点作为聚类中心。这是聚类中心 1。

    2. 确定聚类 2 的中心。从训练数据集的剩余观察结果中随机选择一个观察结果。选择一个不同于之前所选的观察结果。此观察结果对应于远离聚类中心 1 的一个点。以 MNIST 数据集为例,您需要执行以下操作:

      • 对于每张剩余的图像,找出相应点与聚类中心 1 之间的距离。对距离求平方,并分配一个与距离平方成正比的概率。这样一来,不同于之前所选的图像被选作聚类中心 2 的概率更高。

      • 基于上一步中分配的概率,随机选择一个镜像。对应于该图像的点便是聚类中心 2。

    3. 重复步骤 2 找到聚类中心 3。这次,找出剩余图像与聚类中心 2 之间的距离。

    4. 重复该过程,直到您拥有 K 个聚类中心。

要在中训练模型 SageMaker,您需要创建一个训练作业。在请求中,您通过指定以下 HyperParameters 字符串映射来提供配置信息:

  • 要指定待创建的聚类数量,请添加 k 字符串。

  • 为提高准确性,请添加可选的 extra_center_factor 字符串。

  • 要指定希望用于确定初始聚类中心的策略,请添加 init_method 字符串并将其值设置为 randomk-means++

有关 SageMaker k 均值估算器的更多信息,请参阅 Amazon P SageMaker ython SDK 文档中的 K 均值。

现在,您拥有一组初始聚类中心。

步骤 2:迭代训练数据集并计算聚类中心

您在上一步创建的聚类中心大多数是随机的,并且有一些关于训练数据集的考量。在此步骤中,您使用训练数据集将这些中心移向真正的聚类中心。该算法将迭代训练数据集,并重新计算 K 个聚类中心。

  1. 从训练数据集读取小批量观察结果 (从所有记录中随机选择的小型子集),然后执行以下操作。

    注意

    创建模型训练作业时,请在 mini_batch_size 字符串映射的 HyperParameters 字符串中指定批次大小。

    1. 将小批量中的所有观察结果分配到其中一个具有最近聚类中心的聚类。

    2. 计算分配到每个聚类的观察结果的数量。然后,计算每个聚类分配的新点比例。

      例如,考虑以下聚类:

      聚类 c1 = 100 个之前分配的点。您在此步骤中从小批量添加了 25 个点。

      聚类 c2 = 150 个之前分配的点。您在此步骤中从小批量添加了 40 个点。

      聚类 c3 = 450 个之前分配的点。您在此步骤中从小批量添加了 5 个点。

      按如下方式计算分配给每个聚类的新点比例:

      p1 = proportion of points assigned to c1 = 25/(100+25) p2 = proportion of points assigned to c2 = 40/(150+40) p3 = proportion of points assigned to c3 = 5/(450+5)
    3. 计算添加到每个聚类的新点的中心:

      d1 = center of the new points added to cluster 1 d2 = center of the new points added to cluster 2 d3 = center of the new points added to cluster 3
    4. 按如下方式计算加权平均数,以查找更新后的聚类中心:

      Center of cluster 1 = ((1 - p1) * center of cluster 1) + (p1 * d1) Center of cluster 2 = ((1 - p2) * center of cluster 2) + (p2 * d2) Center of cluster 3 = ((1 - p3) * center of cluster 3) + (p3 * d3)
  2. 读取下一个小批量,并重复步骤 1 以重新计算聚类中心。

  3. 有关小批量 k-means 的更多信息,请参阅网络规模 k-means 聚类

步骤 3:将聚类数量从 K 减少至 k

如果该算法创建了 K 个聚类 (K = k*x),其中 x 大于 1,那么这会将 K 个聚类减少至 k 个聚类。(有关更多信息,请参阅之前讨论的 extra_center_factor。) 它通过对 K 个聚类中心应用 Lloyd 的方法(具有 kmeans++ 初始化)来执行此操作。有关 Lloyd 的方法的更多信息,请参阅 k-means 聚类