algorithm - 优化 K-means 算法

Question

我正在尝试关注一篇名为 An Optimized Version of K-Means Algorithm 的论文.我对 K-Means 算法如何有想法 works .即，将元组/点分组到簇中并更新质心。

我正在尝试实现上述论文中提到的方法。他们提出的算法是这样的:

所以我的疑惑在第二步。我不明白那里正在做什么!在论文中说，我们根据 e 的值将数据分组到更宽的区间，这样以后我们就可以避免遍历整个数据集。那么，实际上我们如何将它存储在 I (间隔)中？我们应该定义一个多维数组吗？这对我来说没有意义(可能是愚蠢到不明白这个想法)。

接下来我怀疑的是第 5 步。在那里，Cw 据说是该点最近的质心。但是我们如何弄清楚呢？首先，我们会随机指定一个点作为质心。那么，我们是否应该在计算 e 之前循环遍历这些点并找出 Cw(最近的质心)？

下一个疑惑在第6步，我想在我对我之前关于第2步的问题有了想法之后就可以理解了。

最后的疑问是关于Step7。 CjCj' 是什么意思？先前的质心位置与更新后的质心位置之间的距离？

一整天以来，我一直在就此进行头脑 Storm 。任何线索将不胜感激。谢谢

Answer 1

该算法围绕这样一个想法:靠近一个聚类中心并远离所有其他聚类中心的点将坚持该聚类中心。因此，在后续迭代中，不必将这些点与所有聚类中心进行比较。

想象一个点 P 到它指定的集群的距离为 3(即最近的距离)，而所有其他集群至少相距 8 或更远。现在，计算新的聚类中心。假设任何聚类中心移动最多的是 2(即算法中 D 的值，第 7 行)。

您现在可以确定您的点仍然属于同一个集群。如果您考虑最坏的情况，这很容易理解:分配的集群可能已经离开该点，因此最坏的情况下它可能具有 3+2 的新距离。最近的其他集群可能已经朝该点移动，因此它的距离现在可能是 8-2。因此，您不需要更新该点。

这是一张图片:

您的具体问题:

第 2 步:创建稍后放置点的间隔。在第 5 步中，您将创建 e 值。如果 e 为 5，则将该点放入区间 [4, 6)(如果有该区间)。

第 5 步:计算点到所有簇的距离。最近的集群是 Cw。如果下一个最近的簇是 C3，那么 e = C3 - Cw。我称 e 为安全边际。它为您提供了集群在分配可能切换之前可以移动的最大距离。

第 6 步:与第 2 步一起解释。

第 7 步:CjCj' 是 Cj 更新时移动的距离。

第 7 步和第 8 步:这些是作为 for 循环的一部分完成的。 (在第 9 步中，他们说“回到 4”)。

第 9 步:继续循环所有可能改变簇的点。

更一般

此算法假定您知道 k-means。我相信这是一个非常公平的假设。何时终止以及如何初始化算法不是很明确。这两个事实我都认为是常识。

• 通过为每个聚类中心分配一个随机点来初始化聚类中心。存在其他初始化例程。算法不关心这部分算法。
• 当没有更多的标记小于 0 的区间时终止算法。这等同于 k-means 中的正常终止标准:当没有点分配给不同的聚类时停止。