Erstellen von Clustern mit K-Means plus plus Cluster-Algorithmus basierend auf der verbundenen Entfernung

Question

Ich habe eine Gruppe von Knoten (etwa 10K), die miteinander verbunden sind. Ich muss kleine Cluster erstellen (maximal 15 Knoten).

Ich verwende die Verbindungsentfernung, um den Abstand zwischen zwei Knoten (mithilfe des Dijkstra-Algorithmus für den kürzesten Pfad) anstelle der geografischen Entfernung zu finden. Jetzt ist das Problem, dass es dauert mehr als 1 Stunde, um kleine Cluster mit K-means plus plus-Algorithmus zu erstellen. Ich weiß, dass es mehr Zeit braucht, um die kürzeste Entfernung zwischen zwei Knoten zu finden. Wenn ich den kürzesten Pfad zunächst selbst speichern möchte, benötigt es mehr Speicher (ist unmöglich). Kann mir jemand vorschlagen, wie ich das optimieren kann?

Answer 1

Sie müssen den dykstras-Algorithmus für jeden Knoten in Ihrem Diagramm ausführen. Dykstras Algorithmus nimmt O (n^2 * log n) Zeit auf einem dichten Graphen. Was zu O (n^3 * log n) führt, dauert ziemlich lange. Sie könnten den Floyd-Warshall-Algorithmus (https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) verwenden, um diesen in O (n^3) als Vorverarbeitung umzuwandeln und dann diesen Algorithmus zu verwenden, der noch ziemlich lange dauern würde. Das Positive daran ist, dass Sie die kürzesten Wege speicher effizient mit O (n^2) Speicher speichern können.

Es gibt nichts Besseres für das kürzeste Pfadproblem aller Paare bei dichten Graphen.