优化K-means算法

Question

3

我正在尝试跟随一篇名为“优化版K-Means算法”的论文。我已经了解了K-Means算法的工作原理，即将元组/点分组成簇并更新质心。

我正在尝试实现上述论文中提到的方法。他们提出的算法如下：

enter image description here

所以我的疑问在第二步。我不明白那里在做什么！论文中说，我们根据e的值将数据分组到更宽的间隔中，以便稍后我们可以避免迭代整个数据集。那么，我们如何将其存储在那个I（间隔）中？我们应该定义一个多维数组吗？这对我来说没有意义（可能太蠢了，无法理解这个想法）。

我接下来有疑问的是第5步。在那里，Cw被称为该点最近的质心。但是我们如何找出它呢？首先，我们会随机分配一个点作为质心。所以，在计算e之前，我们是否应该循环遍历这些点并找出Cw（最近的质心）？

下一个问题是关于第6步的，我想在弄清楚关于第2步的问题之后就能理解它。

最后一个问题是关于第7步的。CjCj'是什么意思？上一个质心位置到更新后质心位置之间的距离？

整天以来，我一直在为此进行头脑风暴。非常感谢任何线索。谢谢。

- Vpp Man

3个回答

1

如果您坚持使用这个算法，那么以下内容可能就无关紧要了。但是在K-means领域中，最先进的算法是由Ravi Kannan所描述的。

我想在这里说一下，以防其他人尝试实现k-means聚类并来到这个页面。K-means的困难在于初始化。你提到的论文描述了一个运行时间优化，但这个优化并没有改善聚类本身。该算法也仅适用于2D。

现在的最新技术是先运行SVD，然后在维数为k的主子空间中进行聚类。SVD还提供了一个不错的初始化策略。

在k-means中还有其他技巧，比如向量阈值等。Ravi Kannan在youtube上的讲座应该会给你一些提示。

另一个常常有效的简单技巧是所谓的最远优先遍历。

- Stefan Savev

1

第二步：区间是基于距离度量而不是数据坐标。

第五步：这本质上是到第二个最近聚类的距离。

如果您仍然不理解剩下的内容，请让我知道。

- ElKamina

谢谢您的回复。但是很抱歉，我还是没理解它。 - Vpp Man

距离度量意味着我们正在分离距离矩阵吗？根据作者提到的实验，他们使用了宽度为0.1，并且随机生成的点在0和1之间。所以我也这样做了。用0.1定义了宽度，在数据集中创建了N个点，使用Random类。然后将聚类数设置为3。并将数据集中的点分配给随机聚类。 - Vpp Man

请问我们是否应该在考虑循环中的每个点时执行步骤7和8？如果可能的话，提供一个更简单的伪代码将不胜感激。因为我正在尝试实现一个可工作的版本并自行测试以理解它。我的理解是，我们必须重复此过程，直到间隔中没有标记值小于或等于0的点。 - Vpp Man

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Unapiedra · Accepted Answer

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

假设有一个距其分配的聚类中心距离为3的点P（即最近距离），而所有其他聚类中心至少相距8个单位或更多。现在计算新的聚类中心。假设任何聚类中心移动的最大值为2（这是算法第7行中D的值）。

你现在可以确定你的点仍属于同一聚类。如果你考虑最坏情况，这很容易理解：指定的聚类可能已经远离该点，因此最坏情况下它可能有一个新的距离为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中的正常终止准则：当没有点分配给不同的聚类时停止。