---

---

1. 运行聚类算法

在机器学习中，有时会遇到可能包含数百万个示例的数据集。ML算法必须有效地扩展到这些大型数据集。但是，许多聚类算法无法扩展，因为它们需要计算所有成对点之间的相似度。 这意味着它们的运行时间随样本数量的平方增加，表示为 O ( n 2 ) O(n^2) O(n2)。 例如，聚集（agglomerative）或分裂的层次聚类（divide hierarchical clustering）算法查看所有成对的点，并且分别具有 O ( n 2 l o g ( n ) ) O(n^2log(n)) O(n2log(n)) 和 O ( n 2 ) O(n^2) O(n2) 的复杂度。

本课程着重于 k-means，因为它的复杂度为 O ( n k ) O(nk) O(nk)，其中 k k k 是簇数。k-means 组通过最小化点与其簇中心之间的距离将其分成 k k k 个簇（如下图1所示）。 聚类中心是聚类中所有点的平均值。

如图所示，k-means 可以找到大致的圆形簇。从概念上讲，这意味着 k-means 有效地将数据视为由多个大致圆形的分布组成，并尝试查找与这些分布相对应的聚类。实际上，数据包含异常值，可能不适合这种模型。

在运行 k-means 之前，必须选择集群数 k k k。最初，从猜测 k k k 开始。稍后，讨论如何优化 k k k。

1.1 K-means 流程

要将数据聚类为 k k k 个聚类，k-means遵循以下步骤：

【Step One】

该算法为每个聚类随机选择一个聚类中心。在此示例中，选择 k = 3 k=3 k=3 ，因此该算法随机选择3个聚类中心。

【Step Two】

该算法将每个点分配给最接近的聚类中心，以获得 k k k 个初始聚类。

【Step Three】

对于每个聚类，该算法通过获取聚类中所有点的平均值来重新计算聚类中心。 聚类中心的变化在图3中用箭头显示。 由于聚类中心发生变化，因此算法会将点重新分配给最近的聚类中心。 图4显示了重新分配后的新集群。

【Step Four】

该算法重复计算聚类中心并分配点，直到点停止更改聚类为止。对大型数据集进行聚类时，可以在达到收敛之前停止算法，而应使用其他条件。

1.2 K-means 证明

给定 n n n 个分配给 k k k 个聚类的示例，最小化示例与其聚类中心的距离之和。

• 当第 n n n 个示例分配给第 k k k 个集群时， A n k = 1 A_{nk}=1 Ank​=1，否则返回 0 0 0；
• θ k θ_k θk​ 是簇 k k k 的质心。

我们要最小化以下表达式：

其中，

为了使关于聚类中心 θ k θ_k θk​ 的表达式最小化，对 θ k θ_k θk​ 求导数并将其等于 0 0 0。

分子是簇中所有示例聚类中心距离的总和。分母是集群中示例的数量。因此，聚类中心 θ k θ_k θk​ 是簇中示例聚类中心距离的平均值。由此证明。

由于聚类中心位置最初是随机选择的，因此 k-means 可以在连续运行中返回明显不同的结果。要解决此问题，请多次运行k-means，然后选择质量最佳的结果。另一种解决方法是需要使用k-means的改进版本（k-means++）来选择更好的初始聚类中心位置。

---

2. 解释结果并调整聚类

由于聚类是无监督的，因此没有真实标签可用于验证结果。缺乏真实标签会使评估质量复杂化。此外，现实世界的数据集通常不会像图1所示的数据集那样落入示例的明显的聚类簇中。

可悲的是，现实世界的数据看起来更像图2，这使得很难直观地评估聚类质量。

下面的流程图总结了如何检查聚类的质量。

2.1 Step One: Quality of Clustering

检查群集的质量不是一个严格的过程，因为聚类缺乏真实标签。可以反复应用以下准则，以提高集群的质量。

首先，执行视觉检查，以确保群集看起来像预期的一样，并且认为相似的示例确实出现在同一群集中。然后按照以下各节所述检查这些常用指标：

• 簇基数（Cluster cardinality）；
• 簇大小（Cluster magnitude）；
• 下游系统性能（Performance of downstream system）

注：虽然存在其他几个评估群集质量的指标，但这三个指标是常用且有益的。

2.1.1 簇基数

簇基数是每个簇的示例数。绘制所有聚类的簇基数，并调查属于主要异常值的聚类。例如，在图2中，调查聚类5。

2.1.2 簇大小

簇大小是所有示例到聚类中心的距离之和。与基数相似，检查整个集群的大小如何变化，并调查异常。 例如，在图3中，调查聚类0。

2.1.3 簇基数与簇大小

注意，较高的簇基数往往会导致较高的聚类数量，这在直观上是有意义的。当基数相对于其他聚类与大小不相关时，聚类是异常的。通过绘制幅度对基数来查找异常簇。 例如，在图4中，将一条线插入群集度量标准将显示聚类0是异常的。

【Performance of Downstream System】

由于聚类输出通常用于下游ML系统中，因此请在更改聚类过程时检查下游系统的性能是否得到改善。 对下游性能的影响为聚类质量提供了真实的测试。缺点是该检查执行起来很复杂。

【Questions to Investigate If Problems are Found】

如果发现问题，请检查数据准备和相似性度量，并向自己询问以下问题：

• 数据是否按比例缩放？
• 相似性指标正确吗？
• 算法是否对数据执行语义上有意义的操作？
• 算法的假设是否与数据匹配？

2.2 Step Two: Performance of the Similarity Measure

聚类算法仅与相似性度量一样好。确保相似性度量返回明智的结果，最简单的检查是识别与其他对或多或少相似的示例对。然后，为每对示例计算相似度。确保更多相似示例的相似性度量高于相似程度较低的示例的相似性度量。

用于抽查相似性度量的示例应代表数据集。确保相似性度量适用于所有示例。仔细的验证可确保相似性度量（无论是手动还是监督）在整个数据集中都是一致的。如果对某些示例的相似性度量不一致，则这些示例将不会与相似示例聚类。

如果发现相似性度量不准确的示例，则相似度度量可能无法捕获区分这些示例的特征数据。尝试使用相似性度量，并确定是否获得更准确的相似性。

2.3 Step Three: Optimum Number of Clusters

k-means 要求事先确定簇数 k k k。 如何确定 k k k 的最佳值？尝试运行算法逐渐增加 k k k，并记下j聚类数量的总和。 随着 k k k 的增加，簇变得更小，总距离减小。将该距离与簇数作图。

如图4所示，在一定的 k k k 下，损失随 k k k 的增加而逐渐减少。从数学上讲，这大约是坡度超过 − 1 ( θ > 135 ° ) -1(θ>135°) −1(θ>135°) 的 k k k。 该指南并没有指出最佳 k k k 的确切值，而只是指出了一个近似值。 对于所示的图，最佳 k k k 约为11（elbow method）。如果更喜欢使用粒状簇（granular clusters），则可以使用该图作为指导来选择更大的 k k k。

---

3. k-Means 算的优缺点

3.1 优点

【k-means Generalization】

当簇具有不同的密度和大小时会发生什么？ 看一下图1。将左侧的直观群集与右侧k均值实际找到的群集进行比较。 比较显示了k均值如何在某些数据集上偶然发现。

要聚类如图1所示的自然不平衡聚类，可以调整（泛化） k-means。在图2中，这些线显示了将k均值推广为以下形式后的聚类边界：

• 左图：无概括，导致不直观的群集边界。
• 中心图：允许使用不同的群集宽度，从而产生更直观的不同大小的群集。
• 右图：除了不同的簇宽度以外，每个尺寸还允许不同的宽度，从而形成椭圆形而不是球形簇，从而改善了结果。
  

3.2 缺点

• Choosing k k k manually.
  如“解释结果”中所述，使用“损失与群集”图找到最佳值（k）。
• Being dependent on initial values.
  对于较低的 k k k，可以通过以不同的初始值运行k-means数次并选择最佳结果来减轻这种依赖性。随着 k k k 的增加，需要k-means的高级版本来选择更好的初始聚类中心值（称为k-means种子）。有关 k-means seeding 的完整讨论，可参考 M. Emre Celebi 等人的论文《A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm》。
• Clustering data of varying sizes and density.
  k-means 聚类数据困难，因为聚类的大小和密度各不相同。
• Clustering outliers.
  聚类中心可能被异常值拖拽，或者异常值可能会得到自己的簇，而不是被忽略。在聚类之前考虑删除或剪切离群值。
• Scaling with number of dimensions.
  随着维数的增加，基于距离的相似性度量会收敛到任何给定示例之间的恒定值。 通过在特征数据上使用PCA或通过使用“谱聚类（spectral clustering）”来修改聚类算法来降低维数，如下所述。

3.3 维数和谱聚类的诅咒

这些图显示了标准差与示例之间的平均距离之比如何随维数的增加而减小。这种收敛意味着k均值在区分示例方面变得不太有效。高维数据的负面影响称为维数诅咒（ curse of dimensionality）。

谱聚类通过在算法中添加预聚类步骤来避免维数的诅咒：

• 通过使用PCA减少要特征数据的维数。
• 将所有数据点投影到低维子空间中。
• 通过使用选择的算法将数据聚集在此子空间中。

因此，谱聚类不是单独的聚类算法，而是可与任何聚类算法一起使用的预聚类步骤。谱聚类的细节很复杂，可参考 Ulrike von Luxburg 撰写的《A Tutorial on Spectral Clustering》 。

---