Clustering spectral évolutif à l'aide de caractéristiques de binage aléatoire

Le regroupement spectral est l'une des approches de clustering les plus efficaces pour capturer les structures de clusters cachées dans les données. Cependant, il ne s'adapte pas bien aux problèmes à grande échelle en raison de sa complexité quadratique dans la construction de graphes de similarité et le calcul de la décomposition spectrale subséquente. Bien que plusieurs méthodes aient été proposées pour accélérer le regroupement spectral, la plupart d'entre elles compromettent une perte considérable d'information dans les données originales afin de réduire les goulets d'étranglement computationnels. Dans cet article, nous présentons une nouvelle méthode de regroupement spectral évolutif utilisant des caractéristiques de binage aléatoire (RB) pour accélérer simultanément la construction du graphe de similarité et la décomposition spectrale. Plus précisément, nous approximons implicitement la matrice de similarité (noyau) du graphe par le produit intérieur d'une grande matrice de caractéristiques creuse générée par RB. Nous introduisons ensuite un solveur SVD (décomposition en valeurs singulières) d'avant-garde pour calculer efficacement les vecteurs propres de cette grande matrice pour le regroupement spectral. En utilisant ces deux éléments clés, nous réduisons le coût computationnel d'une complexité quadratique à une complexité linéaire en fonction du nombre de points de données tout en atteignant une précision similaire. Notre analyse théorique montre que le regroupement spectral via RB converge plus rapidement vers le regroupement spectral exact que l'approximation par caractéristiques aléatoires standard. Des expériences étendues sur 8 benchmarks montrent que notre méthode soit surpasse, soit égale les méthodes d'avant-garde en termes de précision et de temps d'exécution. De plus, notre méthode présente une évolutivité linéaire tant en fonction du nombre d'échantillons de données que du nombre de caractéristiques RB.