1

我正在编写程序来实现 k-means 聚类。

consider a simple input with 4 vertices a,b,c and d with following edge costs

[vertex1] [vertex2] [edge cost]
a b 1
a c 2
a d 3
b d 4
c d 5

现在我需要让程序运行，直到我得到 2 个集群。

我的疑问是，在计算最小距离的第一步中，它是 a->b（边缘成本 1）。现在我应该将 ab 视为单个集群。如果是这样，ab 到 c 和 d 的距离是多少？

4

1 回答 1

3

K-means 算法的工作原理如下：

  1. 选择 k 个点作为初始质心（因此，K-*）；
  2. 计算所有顶点到所选择的 k 个质心的距离；
  3. 将每个顶点分配给最近的质心；
  4. 通过生成属于质心的所有顶点之间的平均值来重新计算质心的位置（因此，k-means，对每个 k 质心进行一次平均计算）；
  5. 当在 step中没有顶点被分配给另一个质心时，转到 step2并停止- 或者直到您的错误条件得到满足。3

在您的情况下，由于您有一个无向图，因此最好考虑边缘距离来生成每个顶点的坐标，然后应用该算法。

如果您不想执行此初始过程，您可以计算从一个顶点到所有其他可到达顶点的距离，但是您必须为每次迭代都执行此操作——这是相当不必要的开销。

对于您的无向图：

[vertex1] [vertex2] [edge cost]
a b 1
a c 2
a d 3
b d 4
c d 5

距离表将类似于：

     a    b    c    d
a    0    1    2    3
b    1    0   (1)   4
c    2   (1)   0    5
d    3    4    5    0

(1) - b to c = (b to a, a to c) = 3

如果这应该是您的表格，只需在您的图表上应用 Dijkstra 算法，对于每个顶点，并将结果表格视为您的距离表格。

该表将具有最小距离，但是，如果您有任何其他策略来计算它，则完全由您决定如何计算它。

另请注意，如果您的图是有向的，则矩阵将不是对称的，因为在这种情况下是对称的。

于 2012-12-22T16:10:24.063 回答