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

Question

我看到对于 k-means，我们有 Lloyd 算法、Elkan 算法，我们也有 k-means 的分层版本。

对于所有这些算法，我发现 Elkan 的算法可以提高速度。但我想知道的是所有这些 k-means 算法的质量。每次，我们运行这些算法，由于它们的启发式和概率性质，结果都会不同。现在，我的问题是，当谈到像 k-means 这样的聚类算法时，如果我们想在所有这些 k-means 算法之间获得更好的质量结果(如失真较小等)，哪种算法能够给出你的质量更好？有没有可能测量这样的东西？

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)
的质心/均值

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