我正在编写实现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
现在我需要让程序运行，直到得到两个集群。
我的疑问是，在计算最小距离的第一步，它是a->b（边缘成本1）现在我应该把ab看作一个簇。如果是这样，ab到c和d的距离是多少？
最佳答案
k-means算法的工作原理如下：
选择k点作为初始质心（因此，k-*）；
计算从所有顶点到k个选择的质心的距离；
将每个顶点指定给最近的质心；
通过生成属于质心的所有顶点之间的平均值，重新计算质心的位置（因此，k-means，k个质心中每个顶点的一个平均值计算）；
转到步骤2并在步骤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算法，并考虑你的距离表的结果。
这个表有最小的距离，但是，如果你有任何其他的策略来计算它，完全取决于你如何计算它。
还要注意，如果图是有向的，那么矩阵就不会是对称的，在本例中就是这样。
关于algorithm - k表示聚类样本数据，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14004264/