algorithm - k-Means 的单遍种子选择算法

Question

我最近阅读了 Single Pass Seed Selection Algorithm for k-Means文章，但没有真正理解算法，也就是:

1. 计算距离矩阵Dist，其中Dist (i,j)表示从i到j的距离>/li>
2. 找到 Sumv，其中 Sumv (i) 是从第 i 点到所有其他点的距离之和。
3. 找到 i 点，它是 min (Sumv) 并设置 Index = i
4. 将 First 添加到 C 作为第一个质心
5. 对于每个点 xi，将 D (xi) 设置为 xi 和 C< 中最近点之间的距离
6. 找到 y 作为距离 Index 的前 n/k 个最近点的距离总和
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？

Answer 1

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

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

通过学习和理解他们所比较的 k-means++ 算法，并从中阅读一些历史，您将受益匪浅。

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