我正在尝试关注一篇名为 An Optimized Version of K-Means Algorithm 的论文.我对 K-Means 算法如何有想法 works .即,将元组/点分组到簇中并更新质心。
我正在尝试实现上述论文中提到的方法。他们提出的算法是这样的:
所以我的疑惑在第二步。我不明白那里正在做什么!在论文中说,我们根据 e
的值将数据分组到更宽的区间,这样以后我们就可以避免遍历整个数据集。那么,实际上我们如何将它存储在 I
(间隔)中?我们应该定义一个多维数组吗?这对我来说没有意义(可能是愚蠢到不明白这个想法)。
接下来我怀疑的是第 5 步。在那里,Cw
据说是该点最近的质心。但是我们如何弄清楚呢?首先,我们会随机指定一个点作为质心。那么,我们是否应该在计算 e
之前循环遍历这些点并找出 Cw
(最近的质心)?
下一个疑惑在第6步,我想在我对我之前关于第2步的问题有了想法之后就可以理解了。
最后的疑问是关于Step7。 CjCj'
是什么意思?先前的质心位置与更新后的质心位置之间的距离?
一整天以来,我一直在就此进行头脑 Storm 。任何线索将不胜感激。谢谢
最佳答案
该算法围绕这样一个想法:靠近一个聚类中心并远离所有其他聚类中心的点将坚持该聚类中心。因此,在后续迭代中,不必将这些点与所有聚类中心进行比较。
想象一个点 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 中的正常终止标准:当没有点分配给不同的聚类时停止。
关于algorithm - 优化 K-means 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27044146/