如前所述，许多聚类算法无法扩展到数据集 通常有数百万个样本。例如： 凝聚式层次聚类算法或分裂式层次聚类算法会关注 这些点的复杂程度 \(O(n^2 log(n))\) 和 \(O(n^2)\)，
本课程重点介绍 k-means，因为它会随着 \(O(nk)\)进行扩缩，其中 \(k\) 是用户选择的集群数量。此算法将数据点 \(k\) 聚类分析法 聚类形心（参见图 1）。
因此，k-means 可将数据视为由大量大致的 循环分布，并尝试找到 分发。但实际数据包含离群值和基于密度的聚类 并且可能与 k-means 基础的假设不匹配。
k-means 聚类算法
算法遵循以下步骤：
提供 \(k\)的初始猜测，稍后可进行修改。为此 我们选择 \(k = 3\)。
随机选择 \(k\) 形心。
图 1：初始化时的 k-means。 将每个点分配到最近的形心，以获取初始聚类。 \(k\)
图 2：初始集群。 对于每个聚类，通过取各聚类的平均值 集群中的所有点图 4 中的箭头显示了 形心位置。
图 3：重新计算的形心。 将每个点重新分配到最近的新形心。
图 4：重新分配后的集群。 重复第 4 步和第 5 步，重新计算形心和聚类成员资格，直到 不再改变聚类。对于大型数据集，您可以 在根据其他条件收敛前停止算法。
由于形心位置最初是随机选择的，因此 k-means 可以 在连续运行中返回显著不同的结果。解决这一问题 多次运行 k-means 并选择质量最佳的结果 指标。（我们将在本课程稍后的部分中介绍质量指标。）您需要 高级版本的 k-means 选择更好的初始形心位置。
虽然没有必要深入了解数学， 但有趣的是，k-means 是一种 期望最大化算法。请参阅 UPenn 的关于该主题的讲座笔记。