K-均值的单程种子选择算法

Question

我最近读过K-均值的单程种子选择算法的文章，但并不真正理解算法，即：

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

Answer 1

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

• 该算法描述得很差。
• 它实际上不是一次传递，它需要对n^2/2成对的计算+一次额外的数据传递。
• 他们不报告他们的种子选择方案的运行时，可能是因为做O(n^2)工作非常糟糕。
• 他们正在评估非常简单的数据集，这些数据集对于k方法来说并没有太多糟糕的解决方案。
• 他们衡量“更好”的指标之一是，给定种子选择，运行k-意味着需要多少次迭代。虽然这是一个有趣的指标，但它们报告的微小差异是毫无意义的(k-意思++种子可能是更多的迭代，但每次迭代所做的工作量可能更少)，而且它们不报告运行时间或使用哪个k-均值算法。

你将从学习和理解他们所比较的k均值++算法中获得更多的好处，并从中阅读一些历史。

如果你真的想了解他们在做什么，我会浏览你的matlab并阅读他们提供的matlab代码。但这并不值得。如果你查一查分位数种子选择算法，他们实际上是在做一些非常相似的事情。而不是使用距离到第一个种子排序点，他们似乎是使用配对距离之和(这意味着他们不需要一个初始种子，因此唯一的解决方案)。

Answer 2

单程种子选择算法是一种新型的种子选择算法。单通过意味着无需任何迭代，就可以选择第一个种子。K-意味着++性能取决于第一个种子。这是在SPSS中克服的。请阅读同一作者的论文“k-均值的鲁棒种子选择算法”。

约翰·路易斯