如前所述，许多聚类算法无法扩展到机器学习中使用的包含数百万个示例的数据集。例如，聚合或分裂型分层聚类算法会查看所有点对，复杂度分别为 \(O(n^2 log(n))\) 和 \(O(n^2)\)。
本课程重点介绍了 K 均值算法，因为它的规模为 \(O(nk)\)，其中 \(k\)是用户选择的集群数量。此算法通过最大限度地缩短每个点与其所在簇的质心之间的距离，将点划分为\(k\) 个簇（如图 1 所示）。
因此，k-means 会有效地将数据视为由多个大致圆形分布组成，并尝试找到与这些分布对应的聚类。但是，现实世界的数据包含离群值和基于密度的集群，并且可能不符合 k 均值的假设。
k-means 聚类算法
该算法会按以下步骤运作：
为 \(k\)提供初始猜测值，稍后可以进行修改。在此示例中，我们选择 \(k = 3\)。
随机选择 \(k\) 质心点。
图 1：初始化时的 K-means。 将每个点分配给最近的质心，以获取 \(k\) 初始集群。
图 2：初始集群。 对于每个簇，请通过计算簇中所有点的平均位置来计算新的质心。图 4 中的箭头显示了质心位置的变化。
图 3：重新计算的质心。 将每个点重新分配给最近的新质心。
图 4：重新分配后的集群。 重复第 4 步和第 5 步，重新计算质心和簇成员资格，直到点不再更改簇。对于大型数据集，您可以在收敛之前根据其他条件停止算法。
由于质心位置最初是随机选择的，因此 k-means 在连续运行时可能会返回截然不同的结果。如需解决此问题，请多次运行 K 均值，然后选择质量指标最佳的结果。（我们将在本课程稍后介绍质量指标。）您需要使用高级版的 K 均值算法来选择更好的初始质心位置。
虽然无需深入了解相关数学知识，但对于好奇的读者来说，k 均值是期望最大化算法的一种特殊情况。请参阅宾夕法尼亚大学的有关该主题的讲义笔记。