Ultra-skalierte spektrale Clustering und Ensemble-Clustering

Dieses Papier konzentriert sich auf die Skalierbarkeit und Robustheit des spektralen Clusterns für extrem große Datensätze mit begrenzten Ressourcen. Es werden zwei neue Algorithmen vorgeschlagen, nämlich ultra-skaliertes spektrales Clustern (U-SPEC) und ultra-skalierte Ensemble-Clustern (U-SENC). Im U-SPEC wird eine hybride Strategie zur Auswahl von Repräsentanten und eine schnelle Approximationsmethode für die K-nächsten Repräsentanten vorgeschlagen, um eine dünnbesetzte Ähnlichkeitsuntermatrix zu konstruieren. Durch die Interpretation der dünnbesetzten Unter matrix als bipartiten Graphen wird anschließend der Transfer-Cut verwendet, um den Graphen effizient zu partitionieren und das Clusternergebnis zu erhalten. Im U-SENC werden mehrere U-SPEC-Clusterer in ein Ensemble-Clustern-Framework integriert, um die Robustheit von U-SPEC zu verbessern, während gleichzeitig hohe Effizienz gewährleistet bleibt. Basierend auf der Erzeugung von Ensembles durch mehrere U-SPECs wird ein neuer bipartiter Graph zwischen Objekten und Basisclustern konstruiert und dann effizient partitioniert, um das konsensbasierte Clusternergebnis zu erzielen. Es ist erwähnenswert, dass sowohl U-SPEC als auch U-SENC nahezu lineare Zeit- und Speicherkomplexität haben und in der Lage sind, nichtlinear trennbare Datensätze im Zehnmillionenbereich auf einem PC mit 64 GB Arbeitsspeicher robust und effizient zu partitionieren. Experimente an verschiedenen großen Datensätzen haben die Skalierbarkeit und Robustheit unserer Algorithmen demonstriert. Der MATLAB-Code sowie die experimentellen Daten sind unter https://www.researchgate.net/publication/330760669 verfügbar.