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

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

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,其中您在创建模型训练作业时指定 k x。

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

  3. 它将生成的聚类减少到 k(如果数据科学家在请求中指定创建 k*x 聚类)。

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

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

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

  • 随机方法 —在输入数据集中随机选择 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-means 评估程序的更多信息,请参阅 文档中的 Amazon SageMaker Python SDK K-means。

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

步骤 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:将集群数量从 减少Kk

如果算法创建了 K 个聚类 —(K = k*x),其中 x 大于 —1,则它将 K 个聚类减少为 k 个聚类。(有关更多信息,请参阅前面讨论extra_center_factor的。) 它通过将 Lloyd 的 方法与kmeans++初始化一起应用于 K 个聚类中心来执行此操作。有关 Lloyd 的方法的更多信息,请参阅 k-means 聚类.