Clustering spectrale à grande échelle basée sur les coordonnées de diffusion sur des graphes bipartites fondés sur des points de référence

Le clustering spectral a suscité un grand intérêt en raison de sa capacité à séparer des variétés non convexes et non intersectantes, mais sa complexité computationnelle élevée a considérablement limité son application. Inspirés par le cadre de co-clustering document-terme proposé par Dhillon (2001), nous proposons une approche de clustering spectral à échelle scalable basée sur des points de repère (landmarks), dans laquelle nous construisons d'abord un graphe biparti à partir de l'ensemble de points de repère sélectionnés et des données données, puis appliquons un processus de diffusion sur ce graphe afin d'obtenir une famille de coordonnées de diffusion utilisées pour le clustering. Nous démontrons que notre algorithme peut être mis en œuvre à l’aide d’opérations très efficaces sur la matrice d’affinité entre les données données et les points de repère sélectionnés, ce qui le rend capable de traiter de grandes quantités de données. Enfin, nous illustrons les performances excellentes de notre méthode en la comparant aux algorithmes scalables les plus récents sur plusieurs jeux de données standards.