2

我最近阅读了k-Means 的 Single Pass Seed Selection Algorithm文章，但并不真正理解该算法，即：

  1. 计算距离矩阵Dist，其中表示从到的Dist (i,j)距离ij
  2. 求Sumv其中th 点到所有其他点Sumv (i)的距离之和。i
  3. 找到是的点i并min (Sumv)设置Index = i
  4. 添加第一个C作为第一个质心
  5. 对于每个点xi，设置为与最近点D (xi)之间的距离xiC
  6. 找到y作为第一个n/k最近点的距离之和Index
  7. 找到唯一的整数i，使得D(x1)^2+D(x2)^2+...+D(xi)^2 >= y > D(x1)^2+D(x2)^2+...+D(x(i-1))^2
  8. 添加xi到C
  9. 重复步骤 5-8 直到k居中

尤其是第 6 步，我们仍然Index一遍又一遍地使用相同（相同的点）还是使用新添加的点C？关于第 8 步，是否i必须大于1？

4

2 回答 2

4

老实说，我不会担心理解那篇论文——它不是很好。

  • 该算法描述不佳。
  • 它实际上不是单次传递，它需要进行 n^2/2 成对计算 + 一次额外的数据传递。
  • 他们没有报告他们的种子选择方案的运行时间，可能是因为做 O(n^2) 工作非常糟糕。
  • 他们正在评估非常简单的数据集，这些数据集没有很多糟糕的解决方案可以让 k-Means 陷入其中。
  • 他们的“更好”性指标之一是在给定种子选择的情况下运行 k-means 需要多少次迭代。虽然这是一个有趣的指标，但他们报告的微小差异毫无意义（k-means++ 播种可能是更多的迭代，但每次迭代完成的工作更少），并且他们不报告运行时间或他们使用的 k-means 算法。

您将从学习和理解他们正在比较的 k-means++ 算法中获得更多好处，并从中阅读一些历史。

如果您真的想了解他们在做什么，我会复习您的 matlab 并阅读他们提供的 matlab 代码。但这并不值得。如果您查看分位数种子选择算法，它们本质上是在做非常相似的事情。它们似乎不是使用到第一个种子的距离来对点进行排序，而是使用成对距离的总和（这意味着它们不需要初始种子，因此不需要唯一的解决方案）。

于 2013-07-03T03:11:58.427 回答
-1

单通道种子选择算法是一种新颖的算法。单次通过意味着无需任何迭代即可选择第一个种子。k-means++ 性能取决于第一个种子。它在 SPSS 中被克服。请浏览同一作者的论文“k-means 的稳健种子选择算法”

约翰·J·路易斯

于 2014-02-12T06:24:53.770 回答