Skalierbare Spektrale Clustering-Verfahren unter Verwendung von Random-Binning-Features

Das spektrale Clustern ist einer der effektivsten Ansätze, um verborgene Clusterstrukturen in den Daten zu erfassen. Allerdings skaliert es aufgrund seiner quadratischen Komplexität bei der Konstruktion von Ähnlichkeitsgraphen und der anschließenden Eigenwertzerlegung nicht gut für große Probleme. Obwohl eine Reihe von Methoden vorgeschlagen wurden, um das spektrale Clustern zu beschleunigen, opfern die meisten von ihnen erhebliche Informationsverluste in den ursprünglichen Daten, um rechnerische Engpässe zu reduzieren. In dieser Arbeit stellen wir eine neuartige, skalierbare Methode des spektralen Clusterns vor, die Random Binning Features (RB) verwendet, um sowohl die Konstruktion von Ähnlichkeitsgraphen als auch die Eigenwertzerlegung gleichzeitig zu beschleunigen.Speziell approximieren wir die Graph-Ähnlichkeit (Kernel)-Matrix implizit durch das Skalarprodukt einer großen dünnen Merkmalsmatrix, die durch RB generiert wird. Anschließend führen wir einen modernen SVD-Löser ein, um die Eigenvektoren dieser großen Matrix effektiv für das spektrale Clustern zu berechnen. Mit diesen beiden Bausteinen reduzieren wir den Rechenaufwand von quadratisch auf linear in Bezug auf die Anzahl der Datensätze, wobei wir eine ähnliche Genauigkeit erreichen. Unsere theoretische Analyse zeigt, dass das spektrale Clustern über RB schneller zur exakten spektralen Clusteranalyse konvergiert als die Standardmethode der Random Feature-Approximation.Ausführliche Experimente an 8 Benchmarks zeigen, dass die vorgeschlagene Methode entweder besser oder vergleichbar mit den Stand-of-the-Art-Methoden in Bezug auf Genauigkeit und Laufzeit performt. Darüber hinaus zeigt unsere Methode lineare Skalierbarkeit sowohl in Bezug auf die Anzahl der Datensamples als auch auf die Anzahl der RB-Merkmale.