使用基于连接距离的K-means plus plus聚类算法创建聚类

我有一组相互连接的节点（大约10K）。我必须创建小群集（最多15个节点）。使用基于连接距离的K-means plus plus聚类算法创建聚类

我使用连接距离来查找两个节点之间的距离（使用Dijkstra最短路径算法）而不是地理空间距离。现在的问题是，使用K-means plus plus算法创建小群集需要花费1个多小时。我知道它需要更多时间来找到两个节点之间的最短距离。如果我想最初存储所有最短路径，它需要更多的内存（这是不可能的）。任何人都可以建议我如何优化这个？

来源

2016-11-23 Nagaveer Gowda

对不起，我没有得到。在K-Means中，必须为两个节点（质心和节点本身）设置一个距离，以知道该节点本身分配了哪个集群。现在。 Dijkstra算法？什么是最短路径？ –

使用Dijkstra的我得到质心和节点本身之间的最短路径（来自连接图）。 –

是一个“真实”质心，还是您将质心本身设置为离它最近的节点？ –

您必须为图中的每个节点运行dykstras算法。 Dykstras算法在密集图上需要O（n^2 * log n）时间。其结果为O（n^3 * log n），这需要很长的时间。你可以使用Floyd-Warshall（https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm）算法将它变成O（n^3）作为预处理，然后使用这个算法，这个算法仍然需要很长时间。这样做的好处是，您可以使用O（n^2）内存来有效存储最短路径内存。

密集图上的全对最短路径问题没有什么更好的了。

来源

2016-11-23 11:51:35

使用基于连接距离的K-means plus plus聚类算法创建聚类

回答

相关问题