4

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

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

4

4 回答 4

4

更好的解决方案通常是具有更好（更低）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)（有时表示为 ||ab|| 是“点”a 到“点”b 之间的距离（在欧几里得二维空间中sqrt((a.x-b.x)^2 + (a.y-b.y)^2)）
  • centroid(i) - 最接近的质心/平均值x(i)

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

于 2012-12-13T08:40:32.377 回答
1

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

于 2012-12-13T07:39:23.473 回答
1

两个月亮数据集的病态案例怎么样？无监督的 k-means 会严重失败。我知道的一种高质量方法采用了一种使用互信息和组合优化的概率更高的方法。基本上，您将聚类问题转换为在两个聚类的情况下找到完整点集的最佳 [聚类] 子集的问题。

您可以在此处找到相关论文（第 42 页）并在此处找到相应的Matlab 代码（查看两​​个月亮案例）。如果您对加速超过 30 倍的 C++ 高性能实现感兴趣，那么您可以在 HPSFO找到它。

于 2012-12-13T09:55:54.573 回答
0

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

于 2012-12-14T16:55:18.700 回答