关于不同k-means算法的质量问题

Question

我看到k-means有Lloyd算法、Elkan算法和分层版本的k-means。

对于所有这些算法，我发现Elkan算法可以提供更快的速度。但我想知道的是，所有这些k-means算法的质量如何。每次运行这些算法，由于它们的启发式和概率性质，结果都会不同。现在，我的问题是，当涉及到像k-means这样的聚类算法时，如果我们想在所有这些k-means算法之间获得更好的质量结果（比如更少的失真等），哪种算法能够给出更好的质量？是否可能测量这种事情？

- Karl

Answer 1

更好的解决方案通常是具有更好（较低）J（x，c）值的方案，其中：

J(x,c) = 1/|x| * Sum(distance(x(i),c(centroid(i)))) for each i in [1,|x|]

位置：

• x 是样本列表
• |x| 是 x 的大小（元素数）
• [1,|x|] 表示从 1 到 |x|（包括两端）的所有数字
• c 是聚类的质心（或均值）列表，即对于 k 个聚类，|c| = k
• distance(a,b)（有时记作 ||a-b||）是从“点” a 到“点” b 的距离（在欧几里得二维空间中，它是 sqrt((a.x-b.x)^2 + (a.y-b.y)^2)）
• centroid(i) - 距离 x(i) 最近的质心/均值

请注意，这种方法不需要切换到监督技术，并且可以完全自动化！

- amit

---

由于很多寻找解决方案的方法都从随机初始化开始，这可能会极大地影响解决方案的质量，因此值得在适度的运行次数内取平均值（和方差）来确定准确的功效。 - Ben Allison

Answer 2

据我理解，您需要一些带有标签的数据来交叉验证您的聚类算法。

- Evgeny Lazin

---

聚类是一种无监督学习技术，你说的交叉验证是什么？由于您不知道标签的真实值，这不是一个有监督的分类问题。我需要了解更多上下文才能提供更准确的翻译。 - amit

您可以随时手动标记一些数据，对该数据运行聚类算法，然后将原始标签与算法输出进行比较。 - Evgeny Lazin

然后它被称为“测试集”和“训练集”，而不是交叉验证。这也不是解决方案，因为这并不意味着要评估算法在一般情况下的表现如何（根据我对问题的理解），它旨在为特定问题选择最佳聚类，因为聚类算法是启发式的，所以两次运行可能会生成不同的结果，并且您需要为此特定实例选择更好的结果。 - amit

Answer 3

两个月亮数据集的病理情况怎么样？无监督的k-means会失败得很惨。我知道的一种高质量方法采用更概率化的方法，使用相互信息和组合优化。基本上，你把聚类问题转化为找到两个簇的最佳[簇]子集的问题。

你可以在这里找到相关论文（第42页）和相应的Matlab代码（检查两个月亮的情况）。如果你对C++高性能实现感兴趣，并且速度提高了30倍以上，那么你可以在这里找到它HPSFO。

- SkyWalker

---

虽然信息丰富，但它并没有回答这个问题：“在所有这些k-means算法之间，哪种算法能够为您提供更好的质量？是否可能测量这样的事情？” - amit

Answer 4

为了比较质量，您应该拥有一个标记数据集，并通过一些标准（如NMI）来衡量结果。

- xueliang liu