Großskalige spektrale Clustering mit Diffusionskoordinaten auf auf Markerpunkten basierenden bipartiten Graphen

Spektrale Clustering hat erhebliche Aufmerksamkeit erhalten, da sie in der Lage ist, nicht-konvexe, sich nicht schneidende Mannigfaltigkeiten zu trennen, doch ihre hohe rechnerische Komplexität hat ihre Anwendbarkeit erheblich eingeschränkt. Ausgehend vom Dokument-Begriff-Co-Clustering-Framework von Dhillon (2001) schlagen wir einen auf Markierungspunkten basierenden skalierbaren Ansatz für spektrale Clustering vor, bei dem wir zunächst auf der Grundlage der ausgewählten Markierungspunkte und der gegebenen Daten einen bipartiten Graphen aufbauen und anschließend einen Diffusionsprozess darauf durchführen, um eine Familie von Diffusionskoordinaten für die Clustering-Aufgabe zu gewinnen. Wir zeigen, dass unser vorgeschlagener Algorithmus auf sehr effizienten Operationen auf der Affinitätsmatrix zwischen den gegebenen Daten und den ausgewählten Markierungspunkten basiert, wodurch die Verarbeitung großer Datensätze möglich wird. Schließlich demonstrieren wir die hervorragende Leistung unseres Verfahrens durch Vergleiche mit aktuellen skalierbaren Algorithmen an mehreren Benchmark-Datensätzen.