MiniBatchKMeans 是如何工作的？

How Does MiniBatchKMeans Works?

Sklearn 实现的许多机器学习算法都支持增量学习，即基于小批量（mini-batch）的训练。这使得当整个数据无法一次性装入内存时，它们依然非常有用。

以下是支持该特性的算法，供你参考：

如果你仔细看，列表里也有 KMeans。作为一种流行的聚类方法，能在需要时对大型数据集运行 KMeans 是件好事。但当我最初了解到 KMeans 可以用小批量的方式实现时，我想知道 KMeans 的批量实现究竟是如何工作的？思考了大约一分钟，我有了点思路，希望在本章中与你分享。

在理解小批量实现之前，我们必须了解常规 KMeans 实现的问题所在。回顾一下，KMeans 的工作流程如下：

• 步骤 1) 初始化质心。
• 步骤 2) 为每个数据点找到最近的质心。
• 步骤 3) 将质心重新赋值为分配到它的数据点的平均值。
• 步骤 4) 重复直至收敛。

在这种实现中，主要的内存瓶颈来自第 3 步。这是因为在这一步中，我们要计算分配给某个质心的所有数据点的平均值，以便移动该质心。

因此，传统上，分配给某个质心的所有数据点都必须在内存中可用，才能对其求平均。

但在我们的场景中，所有数据点并不能一次性装入内存，因此直接求平均行不通。不过，我们可以用下面的方式巧妙地解决这个问题。我们可以利用一个把求和与求平均联系起来的数学性质来跟踪每个质心所分配到的数据点，从而实现 MiniBatchKMeans 的小批量版本，这正是它能够高效实现的关键所在。

我们通过选择一个 k 值——也就是质心数——来开始算法。接下来，我们需要质心的初始位置，于是可以采样 m（m << n）个随机数据点来初始化质心。

现在回顾一下我们上面讨论过的瓶颈——所有数据点都必须在内存中可用才能求平均。因此，为了解决这个问题，我们需要一种方法，在加载并处理每个小批量时，跟踪分配给每个质心的数据点。

我们无法为每个质心维护一个不断增长的数据点列表，因为那最终会占去整个数据集的内存。所以我们可以这样巧妙地实现这一目标。我们可以利用下面这个把求和与求平均联系起来的数学性质：

怎么做呢？你看，在典型的 KMeans 设定中，我们要对分配给某个质心的所有数据点求平均来确定它的新位置。但正如上面所讨论的，我们无法把所有数据点同时放在内存里。那我们不妨在 KMeans 的小批量设定下这么做：对每个质心：

• 我们维护一个“求和向量（sum-vector）”，用于存储分配给该质心的所有数据点向量之和。一开始，它是一个零向量。
• 一个“计数（count）”变量，用于跟踪分配给该质心的数据点数量。一开始，计数为零。

在遍历小批量的过程中：

• 每个质心的“求和向量”会持续累加到目前为止分配给它的所有数据点之和。
• 每个质心的“计数”变量会持续跟踪到目前为止分配给它的数据点数量。
• 在遍历完所有小批量之后，我们可以在求和向量与计数之间做一次标量除法，得到平均向量：
• 这个平均值会精确地告诉我们质心的新位置，就像所有数据点都同时在内存中一样。我们可以重复这一过程直到收敛。此外，在开始下一次 MiniBatchKMeans 的迭代（iteration）之前，我们必须把求和向量重置为零向量、计数重置为零。这就是 KMeans 的小批量版本的实现方式。