如何确定多少个簇？聚类算法中选择正确簇数量的三种方法

聚类是一种无监督机器学习方法，可以从数据本身中识别出相似的数据点。对于一些聚类算法，例如 K-means，需要事先知道有多少个聚类。如果错误地指定了簇的数量，则结果的效果就会变得很差（参见图 1）。

这种情况下，s 变为负数，接近 -1。

在许多情况下，不知道数据中有多少个簇。但是弄清楚有多少簇可能是我们首先要执行聚类操作的原因。如果有数据集相关的领域内知识可能有助于确定簇的数量。但是这假设需要知道目标类（或至少有多少类），而在无监督学习中无法确认，所以我们需要一种方法，它可以在不依赖目标变量的情况下告诉我们簇的数量。

确定正确的簇数量的一种可能的解决方案是暴力测试的方法。我们尝试不同数量的簇的聚类算法。然后找到最优的聚类结果，但是这种方式的需要花费大量的资源。在本文中，我们首先介绍两个流行的指标来评估簇质量。然后介绍了三种方法来找到最佳簇数量：

• 肘部法 The elbow method

• 轮廓系数的优化 The optimization of the silhouette coefficient

• 间隔量统计 The gap statistic

聚类结果的质量

在使用不同的方法来确定最佳聚类数之前，首先要了解如何定量评估聚类结果的质量。想象以下场景，相同的数据集分为三个簇（参见图 2）。左侧的聚类定义良好，而右侧的聚类识别不佳。

这是为什么？聚类的目标是对聚类中的数据点进行分组，以便 (1) 聚类内的点尽可能相似，(2) 属于不同聚类的点尽可能不同。这意味着，在理想的聚类中，簇内的变化很小，而簇间的变化很大。因此，一个好的聚类质量度量应该能够定量地总结（1）和/或（2）。

一种这样的质量指标是inertia（惯性）。这被计算为数据点与其所属聚类中心之间的平方距离之和。inertia量化了簇内的变化。

另一个流行的指标是silhouette coefficient（轮廓系数），它试图总结簇内和簇间的变化。在每个数据点，我们计算到该数据点所属的聚类中心的距离（称为a），以及到次优聚类中心的距离（称为b）。在这里，次好的簇是指不是当前数据点簇的最接近的簇。然后基于这两个距离 a 和 b，该数据点的轮廓 s 计算为 s=(b-a)/max(a,b)。

在理想聚类下，距离 a 与距离

一旦在所有数据点计算 s，s 的平均值就确定了轮廓系数。可以为每个簇单独计算轮廓系数，也可以为所有数据点计算轮廓系数。接近 1 的轮廓系数表明聚类算法能够将数据划分为分离良好的聚类。

肘部法则

inertia是簇数 k 的递减函数。它的下降速度在最佳聚类数 K 上下是不同的。当 kK 时，inertia下降很慢。因此，通过在 k 范围内绘制inertia，可以确定曲线在 K 处弯曲或弯头的位置。图 4 显示了图 1 中示例的惯性图。我们可以清楚地看到弯曲或弯头， 在 k = 6。所以我将inertia翻译成了惯性是非常贴切的。

这种方法有些主观，因为不同的人可能会在不同的位置识别肘部。在我们图 4 的示例中，有些人可能会争辩说 k=4 是肘部。此外，肘部可能并不总是很明显，我们将在后面看到。

肘部法的用例可以在自然语言问题中看到，以使用 KNIME 分析平台确定社交网络中的最佳主题数量。由于没有 KNIME 节点来计算inertia，因此在此示例中使用 Java Snippet 节点来计算inertia。这是用于计算inertia的代码片段。

// Initializing the sum of squares
out_sum_squares = 0.0;
/*
The first half of columns belong to features of the origin.
The second half of columns belong to features of the terminus.
The groups of columns have to be in the same order.
*/
int col_count = getColumnCount();
int no_dimensions = col_count / 2;

// Loop over the feature columns
for(int i=0; i < no_dimensions; i++){
/*
Checking if the feature i from the origin and
the feature i from the terminus (i.e., i+no_dimensions)
are not missing, and have similar column names
  */
if(!isMissing(i) && isType(i, tDouble)
  && !isMissing(i+no_dimensions) &&
  isType(i+no_dimensions, tDouble) &&
  getColumnName(i+no_dimensions).contains(getColumnName(i))){
  // Calculating the squared distance and adding it to the sum
  out_sum_squares += Math.pow(getCell(i, tDouble) -
  getCell(i+no_dimensions, tDouble), 2);
  }
}

轮廓系数法

轮廓系数可以提供更客观的方法来确定最佳聚类数。这是通过简单地计算 k 范围内的轮廓系数并将峰值识别为最佳 K 来完成的。在 k 范围内执行 K-Means 聚类，找到产生最大轮廓系数的最佳 K，并根据优化的 K 将数据点分配给聚类。图 5 显示了我们提供的示例数据中的轮廓系数图示例 如图 1 所示，轮廓系数在 k=6 处达到峰值，因此确定为最佳 K。

间隔量统计

为了讨论差距统计，让我们考虑一个没有任何聚类的随机数据集的聚类。假设一个随机数据集被聚类为 k 个聚类，并根据生成的聚类计算惯性（参见图 6）。尽管缺乏基本的组织，但随着 k 的增加，簇的随机数据会产生稳步下降的惯性（惯性的复数）。这是因为聚类中心越多，数据点到聚类中心的距离越小就会产生惯性的衰减。正如在图 4 中已经看到的，在具有簇组织的数据集中，无论 k 是否低于或高于最佳簇数 K，惯性的减少率都会有所不同。将观察数据和随机数据的惯性绘制在一起时差异变得明显（参见图 7）。间隔量统计是通过比较来自（希望）聚类数据集和覆盖数据空间中相同范围的相应随机数据集的惯性来计算的。

图 6：均匀分布的随机数据聚集成 k=4（左）、6（中）和 15（右）簇。

图 7：原始数据（来自图 1）与 k 范围内的随机数据的惯性如何降低。

在实际计算间隔统计量时，会生成一些随机样本，然后在 k 的范围内进行聚类，并记录由此产生的惯性。这允许随机情况下的一些惯性。原始数据集也在k的范围内聚集，产生一系列惯性。k 个簇的间隙统计量计算为

其中 Wk(i) 是来自第 i 个随机样本 (i=1,2,…,B) 的惯性，具有 k 个簇，Wk 是来自原始数据的惯性具有 k 个簇，将其标准差计算为

然后找到最优K作为满足条件的最小k

间隔量统计的计算涉及模拟，所以这里在 R 中计算间隙统计信息。特别是调用clusGap()函数计算不同k处的gap统计量，maxSE()返回满足上述条件的最优K。图 8 显示了图 1 中示例数据集的间隙统计图，基于每个 k 处的 B=100 次迭代。红线代表满足上述条件的最优 K。

需要注意的是，由间隔量统计方法确定的最优 K 可能不一致。例如，当间隔量统计方法多次应用于演示数据时，得到的最优 K 可能不同（见图 9）。

MNIST 手写数字数据示例

现在让我们在具有簇组织的真实数据集上检查上述三种方法。MNIST 数据集由 0 到 9 的手写数字的灰度图像组成。在这个例子中，我们使用了 n=1797 个 8x8 像素的图像。图 10 显示了数据集的一些示例。

上述三种方法用于确定最佳聚类数。由于该数据集中有 10 个不同的数字，因此可以合理地假设有 10 个聚类，每个聚类对应一个数字。然而人们可能有多种书写数字的方式，实际上簇的数量不一定是 10。数据的 2D 散点图（通过 tSNE 投影到 2D 空间，参见图 11）显示一些簇可能与其他簇很好地分离，而一些 簇可能接触或重叠。

肘部法的结果尚无定论，因为图中没有明显的肘部（图 12，左）。而 图中有一些微妙的弯曲（例如，9、12、20、24 等等），并且可以选择其中任何一个作为聚类的数量。

图 12：根据数字数据生成的肘部图（左）和轮廓系数图（右）。

图 13：根据 B=100 次迭代从数字数据生成的间隔量统计图。最佳 k=12 用红线表示。

轮廓系数在 k=12 处有一个峰值（图 12，右）。根据间隔量统计方法，k=12也被确定为最佳聚类数（图13）。我们可以直观地比较 k=9（根据肘部方法最佳）和 k=12（根据轮廓和间隙统计方法最佳）的 k-Means 聚类（参见图 14）。

图 14：在 k=9 和 k=12 的数字数据中发现的 K-Means 聚类， t-SNE 投影到 2D 空间。

总结

本文展示了选择最佳聚类数的三种不同方法，即肘部法、轮廓系数和间隔量统计量。虽然肘部图的解释相当主观，但轮廓系数和间隙统计方法都可以精确地确定聚类的数量。但是间隔量统计涉及模拟，它可能并不总是产生相同的结果。

与许多机器学习方法一样，此处描述的方法并非在所有场景中都能正常工作。由于这些方法量化了聚类中心和数据点之间的距离，因此它们适用于寻找凸聚类，例如在 K-Means 聚类中找到的聚类的数量。

引用

Robert Tibshirani, Guenther Walther, Trevor Hastie. Estimating the number of  clusters in a data set via the gap statistic. Journal of the Royal  Statistical Society, Series B, 63: 411–423 (2001).

作者：Satoru Hayasaka