Divide-and-Conquer-basierte Large-Scale Spektrale Clusterverfahren

Spektrale Clustering ist eine der beliebtesten Clustering-Methoden. Allerdings war es lange Zeit schwierig, die Effizienz und Effektivität des spektralen Clusterings bei großen Datenmengen unter begrenzten Rechenressourcen angemessen zu gewährleisten. In dieser Arbeit schlagen wir eine auf Divide-and-Conquer basierende Methode für das große spektrale Clustering vor, um ein gutes Gleichgewicht zwischen Effizienz und Effektivität zu erzielen. Im Rahmen dieser Methode wurde ein Divide-and-Conquer-basierter Algorithmus zur Landmarkenauswahl sowie ein neuer Ansatz zur approximativen Ähnlichkeitsmatrix entwickelt, um eine dünnbesetzte Ähnlichkeitsmatrix mit geringer Berechnungskomplexität zu konstruieren. Anschließend können die Clustering-Ergebnisse durch einen bipartiten Graphenpartitionierungsprozess schnell berechnet werden. Die vorgeschlagene Methode erreicht eine niedrigere Berechnungskomplexität als die meisten existierenden Methoden für großes spektrales Clustering. Experimentelle Ergebnisse anhand von zehn großen Datensätzen haben die Effizienz und Effektivität der vorgeschlagenen Methode nachgewiesen. Der MATLAB-Code der vorgeschlagenen Methode und die experimentellen Datensätze sind unter https://github.com/Li-Hongmin/MyPaperWithCode verfügbar.