K-means是聚类分析中广泛使用的方法。在我的理解中，这种方法不需要任何假设，即给我一个数据集和一个预先指定数量的集群，k，我只是应用这个算法来最小化平方误差（SSE）的总和，集群内的平方错误。
所以k-means本质上是一个优化问题。
我阅读了一些关于 k-means 缺点的材料。他们中的大多数人说：
如果违反这 3 个假设中的任何一个，则 k-means 将失败。
我无法理解这句话背后的逻辑。我认为 k-means 方法基本上没有任何假设，它只是最小化 SSE，所以我看不出最小化 SSE 和这 3 个“假设”之间的联系。
多么棒的问题——这是一个展示如何检查任何统计方法的缺点和假设的机会。即：编一些数据，在上面试试算法！
我们将考虑您的两个假设，并看看当这些假设被打破时 k-means 算法会发生什么。我们将坚持使用二维数据，因为它很容易可视化。（非常感谢维度的诅咒，添加额外的维度可能会使这些问题更加严重，而不是更少）。我们将使用统计编程语言 R：您可以在此处找到完整的代码（以及此处的博客形式的帖子）。
首先，一个类比。想象一下有人提出以下观点：
我阅读了一些关于线性回归缺点的材料——它期望线性趋势，残差是正态分布的，并且没有异常值。但所有线性回归所做的都是最小化预测线的平方误差之和 (SSE)。这是一个无论曲线形状或残差分布如何都可以解决的优化问题。因此，线性回归不需要任何假设即可工作。
嗯，是的，线性回归通过最小化残差平方和来工作。但这本身并不是回归的目标：我们要做的是画一条线，作为基于x的y的可靠、无偏预测器。高斯-马尔可夫定理告诉我们，最小化 SSE 可以实现该目标——但该定理依赖于一些非常具体的假设。如果这些假设被打破，您仍然可以最小化 SSE，但它可能不会任何事物。想象一下，“你通过踩踏板来开车：驾驶本质上是一个‘踩踏板的过程’。油箱里有多少油都可以踩下踏板，所以即使油箱没了，你也可以踩下踏板开着车。”
但谈话很便宜。让我们看看冷硬的数据。或者实际上，虚构的数据。
这实际上是我最喜欢的虚构数据：Anscombe 的四重奏。由统计学家弗朗西斯·安斯科姆（Francis Anscombe）于 1973 年创建，这个令人愉快的混合物说明了盲目相信统计方法的愚蠢。每个数据集具有相同的线性回归斜率、截距、p 值和- 但乍一看，我们可以看到其中只有一个I适合线性回归。在II中，它暗示了错误的形状，在III中，它被一个异常值扭曲了——而在IV中，显然根本没有趋势！
有人可以说“线性回归在这些情况下仍然有效，因为它可以最小化残差的平方和。” 但这是一场多么惨烈的胜利！线性回归总是会画一条线，但如果它是一条毫无意义的线，谁在乎呢？
所以现在我们看到，仅仅因为可以执行优化并不意味着我们正在实现我们的目标。我们看到，组成数据并将其可视化是检查模型假设的好方法。坚持这种直觉，我们马上就会需要它。
您认为 k-means 算法可以在非球形集群上正常工作。像……这样的非球形星团？
也许这不是您所期望的——但它是构建集群的一种完全合理的方式。看着这张图片，我们人类立即识别出两组自然的点——没有弄错它们。那么让我们看看 k-means 是如何做的：分配以颜色显示，估算中心显示为 X。
嗯，这是不对的。K-means 试图在一个圆孔中安装一个方形钉- 试图找到周围有整齐球体的漂亮中心 - 但它失败了。是的，它仍然在最小化集群内的平方和——但就像上面 Anscombe 的四重奏一样，这是一场代价高昂的胜利！
你可能会说“这不是一个公平的例子......没有任何聚类方法可以正确找到那么奇怪的聚类。” 不对！尝试单链接 层次聚类：
搞定了！这是因为单链接层次聚类对此数据集做出了正确的假设。（还有另一类失败的情况）。
你可能会说“这是一个单一的、极端的、病态的案例。” 但事实并非如此！例如，您可以将外部组设为半圆形而不是圆形，并且您会看到 k-means 仍然做得很糟糕（并且层次聚类仍然做得很好）。我可以很容易地想出其他有问题的情况，而这只是二维的。当您对 16 维数据进行聚类时，可能会出现各种问题。
最后，我应该指出，k-means 仍然可以挽救！如果您首先将数据转换为极坐标，则聚类现在可以工作：
这就是为什么理解一个方法背后的假设是必不可少的：它不仅仅告诉你一个方法什么时候有缺点，它告诉你如何解决它们。
如果集群的点数不均匀怎么办——这是否也会破坏 k-means 聚类？好吧，考虑这组大小为 20、100、500 的集群。我已经从多元高斯生成了每个集群：
这看起来像 k-means 可能会找到那些集群，对吧？一切似乎都生成了整齐有序的组。所以让我们试试k-means：
哎哟。这里发生的事情有点微妙。在寻求最小化集群内平方和的过程中，k-means 算法为更大的集群提供了更多的“权重”。在实践中，这意味着很高兴让那个小集群最终远离任何中心，而它使用这些中心来“分裂”一个更大的集群。
如果你稍微玩一下这些例子（这里是 R 代码！），你会发现你可以构建更多的场景，其中 k-means 会出现令人尴尬的错误。
数学民间传说中有一个迷人的结构，由Wolpert 和 Macready形式化，称为“没有免费午餐定理”。这可能是我在机器学习哲学中最喜欢的定理，我很高兴有机会提出它（我有没有提到我喜欢这个问题？）基本思想（非严格）表述为：“当在所有可能的情况下进行平均时，每种算法的表现都一样好。”
听起来违反直觉？考虑到对于算法有效的每一种情况，我都可以构建一个它严重失败的情况。线性回归假设您的数据沿着一条线下降 - 但如果它遵循正弦波怎么办？t 检验假设每个样本都来自正态分布：如果你加入异常值怎么办？任何梯度上升算法都可能陷入局部最大值，任何监督分类都可能陷入过度拟合。
这是什么意思？这意味着假设是您的力量的来源！当 Netflix 向您推荐电影时，假设您喜欢一部电影，您会喜欢类似的电影（反之亦然）。想象一个不真实的世界，你的品味完全随机——随意地散布在流派、演员和导演中。他们的推荐算法会非常失败。说“好吧，它仍在最小化一些预期的平方误差，所以算法仍在工作”是否有意义？如果不对用户的口味做出一些假设，您就无法做出推荐算法——就像您无法在不对这些集群的性质做出一些假设的情况下做出聚类算法一样。
所以不要只接受这些缺点。了解它们，以便它们可以告知您对算法的选择。了解它们，以便您可以调整算法并转换数据以解决它们。爱他们，因为如果你的模型永远不会错，那就意味着它永远不会正确。
虽然我非常喜欢David Robinson 的回答，但这里有一些对 k-means 的额外批评。
在统一数据上运行 k-means，你仍然会得到集群！它不会告诉您数据何时不聚集，并且可以通过这种方式将您的研究带入死胡同。
重新调整数据集将完全改变结果。虽然这本身并不坏，但没有意识到您必须花额外的注意力来扩展数据是不好的。缩放因子是 k-means 中的额外隐藏参数，“默认”为 1，因此很容易被忽略，但具有重大影响（当然，这也适用于许多其他算法）。
这可能就是您所说的“所有变量都具有相同的方差”。除了理想情况下，您还会在适当时考虑非线性缩放。
另请注意，将每个轴缩放为具有单位方差只是一种启发式方法。这并不能确保 k-means 有效。缩放取决于数据集的含义。如果您有多个集群，您会希望每个集群（独立地）在每个变量中都具有相同的方差。
这是 k-means无法聚类的数据集的经典反例。两个轴在每个集群中都是独立同分布的，因此在一维中执行此操作就足够了。但是集群有不同的方差，因此 k-means 会错误地拆分它们。
我不认为你的观点涵盖了这个 k-means 的反例：
然而，k-means 仍然严重失败（如果我将较大集群的方差增加到 0.5 以上，情况会变得更糟）但是：失败的不是算法。这是假设，不成立。K-means 运行良好，只是优化了错误的标准。
下面是经典 A3 数据集上 10 次 k-means 运行中最好的。这是一个合成数据集，专为 k-means 设计。50 个簇，每个簇都呈高斯形状，分离得相当好。然而，只有 k-means++ 和 100 次迭代，我确实得到了预期的结果......（以下是常规 k-means 的 10 次迭代，用于说明）。
您会很快在此数据集中找到许多集群，其中 k-means 未能找到正确的结构。例如在右下角，一个集群被分成三个部分。但是没有办法，k-means 会将这些质心之一移动到数据集的一个完全不同的位置——它被困在一个局部最小值中（这已经是 10 次运行中最好的一次了！）
在这个数据集中有很多这样的局部最小值。很多时候，当你从同一个集群中获取两个样本时，它会卡在这个集群保持分裂的最小值，而另外两个集群则合并了。并非总是如此，但经常如此。所以你需要大量的迭代才能有一个幸运的选择。通过 100 次 k-means 迭代，我仍然计算出 6 个错误，并且通过 1000 次迭代，我将其减少到 4 个错误。K-means++ 通过对随机样本进行加权的方式，在这个数据集上效果更好。
虽然您可以对二进制数据（或 one-hot 编码的分类数据）运行 k-means，但结果将不再是二进制的。所以你确实得到了一个结果，但你最终可能无法解释它，因为它的数据类型与你的原始数据不同。
这基本上已经存在于上述答案中，用线性回归很好地证明了这一点。在某些用例中，k-means 非常有意义。当 Lloyd 必须解码 PCM 信号时，他确实知道不同音调的数量，并且最小二乘误差可以最大限度地减少解码错误的机会。在图像的颜色量化中，您也可以在减少调色板时最大限度地减少颜色误差。但是根据您的数据，平方偏差的总和是否是一个有意义的最小化标准？
在上面的反例中，方差不值得最小化，因为它取决于集群。相反，高斯混合模型应该适合数据，如下图所示：
（但这也不是最终的方法。构造不满足“混合 k 高斯分布”假设的数据同样容易，例如，通过添加大量背景噪声）
总而言之，在你的数据上使用 k-means 太容易了，但还是会得到一个结果（这几乎是随机的，但你不会注意到）。我认为如果您不了解您的数据，最好有一种可能会失败的方法......
如果您想要 k-means 的理论模型，请将其视为量化方法，而不是聚类算法。
如果您将每个对象替换为其最近的质心，则 k-means 的目标 - 最小化平方误差 - 是一个合理的选择。（如果您检查组原始数据恕我直言，它的意义要小得多。）
有很好的用例。我想到了 Lloyd 的原始 PCM 用例，例如颜色量化（维基百科）。如果要将图像减少为 k 种颜色，则确实希望将每个像素替换为最近的质心。最小化平方颜色偏差然后确实种颜色的图像逼近中的 L2 最优性。
这种量化可能与线性回归示例非常相似。线性回归找到最好的线性模型。并且 k-means （有时）找到多维数据集的k 值的最佳缩减。其中“最佳”是最小二乘误差。
恕我直言，k-means 是一种很好的量化算法（请参见本文中的第一张图片 - 如果您想将数据集近似为两个点，这是一个合理的选择！）。如果您想像发现结构那样进行聚类分析，那么 k-means 恕我直言不是最佳选择。当没有集群时，它倾向于集群，并且它无法识别您在数据中看到的各种结构。
精美印刷品：所有图像均使用ELKI生成。数据是使用.xml数据生成格式生成的，但它们太基础了，不值得分享。
从逻辑上讲，K-means 的缺点是：
但是 K-means 比我们通常认为的要好。在对其他聚类方法（光谱、密度……）和 LDA 在现实生活中一百万个文本的文本分类中进行测试后，我变得非常热衷于它：例如，K-means 的准确度比 LDA 好得多（88% vs 59%）。其他一些聚类方法也不错，但 K-means 接近顶部……而且在复杂性方面更实惠。
我从来没有读过关于在广泛的问题上普遍更好的聚类方法。也不是说 K-means 普遍更好，只是据我所知没有普遍的聚类超级英雄。许多文章，许多方法，并不是真正的革命（以我个人有限的测试经验）。
K-means 的逻辑缺陷通常很明显的主要原因是 2D 平面中的聚类点是机器学习中很少做的事情。几何直觉中的许多东西在 2D、3D 中是正确的......在相当高维或抽象向量空间（如词袋、变量向量......）中无关紧要
线性可分性： 您很少需要处理现实生活数据中的圆形集群。最好假设它们在这些情况下不存在。允许您的算法搜索它们将允许它在噪声中找到奇怪的圆形簇。K-means 中的线性假设通常使其更加稳健。
集群数量： 通常没有您希望看到的真正理想的集群数量。以文本分类为例，可能有 100 个类别，105、110……这都是相当主观的。指定集群的数量就等同于指定一个全局粒度。无论如何，所有聚类方法都需要粒度规范。
全球最大值： 我认为这是一个真正的问题。真正的抽象 K-means 将包括找到 SOD 的全局最小值，基本上是 NP-Hard。只有劳埃德是负担得起的，而且……非常不完美。我们确实已经看到，接近真正的最小值（由于复制）明显提高了结果的质量。K-means 的复制是一种改进，但不是完美的解决方案。对于一个大数据集，您需要复制有很小的机会找到真正的最小值。其他方法，如“用贪婪搜索完成”（在 Matlab 中提出）在大数据集中的成本是天文数字。
但是所有的聚类算法都有这样的局限性。例如在光谱聚类中：你找不到真正的特征向量，只有近似值。
对于相同的计算时间，一个相当优化的 LDA 库的效果不如我们自制的（不是完美优化的）K-means。从那以后，我的想法有点不同了。
我想在@DavidRobinson 的回答中补充一点，即聚类到最小的总聚类方差实际上是一个组合优化问题，其中 k-Means 只是一种技术——考虑到后者的“单次”、局部“最陡下降”性质，一个也很糟糕。此外，试图通过以某种方式（但很快！）找出集群种子应该在哪里来显着改善“裸骨”k-Means，从一开始就注定要失败：因为种子影响（剧烈！）最终集群，它相当于在实际计算之前“知道”最佳值是什么。
然而，作为大多数优化问题，它可能仍然适用于一些严肃的优化技术。其中一个非常符合问题的结构（正如 NFL 所要求的那样！），它肯定会在结果中显示出来。我不想在这里做任何广告（它会 - 并且正确地 - 反对礼仪），所以如果你有兴趣，只需在这里阅读并做出你自己的判断。
话虽如此，我同意@ttnphns 的观点，即 k-Means 肯定不能识别高斯混合——这两个问题的成本函数完全不同。事实证明，找到最佳拟合（就给定数据的模型概率而言）高斯混合也是一个组合优化问题 - 并且也存在一种严肃的优化技术。再一次，没有广告：你可以在这里得出你自己的结论——我只想说那里讨论的算法确实可以正确识别像@DavidRobinson 帖子中的最后一张图像这样的集群。它甚至正确地（即以数学上明确定义的方式）解决了长期存在的异常值问题，即不属于任何集群的数据点，因为它们完全是随机的（众所周知，它们完全破坏了k-Means）。这是通过让一个额外的均匀分布与高斯分布竞争来完成的......而出色的结果是，在均匀分布的数据上，它确实报告那里没有任何东西（我从未在其他任何地方看到过）。
现在显然，根据 NFL，并且正如您正确指出的那样，即使是具有异常值识别的全局最优高斯混合也确实依赖于先前的假设 - 即数据确实是正态分布的。不过幸运的是，由于大数定律，许多自然现象确实符合这一假设。
免责声明：深表歉意，我写了上面的两篇论文，以及他们讨论的算法。
PS 我曾经在一次会议上遇到过 Macready - 一个非常聪明和好人！