Regroupement spectralIl s'agit d'une méthode de clustering basée sur la théorie des graphes. Il divise un graphe non orienté pondéré en deux ou plusieurs sous-graphes optimaux. Les sous-graphes sont similaires en interne et éloignés les uns des autres pour obtenir un clustering. Son essence est de transformer le problème de clustering en problème de partitionnement optimal du graphe. Il s'agit d'un algorithme de clustering point à point.

Comparé aux algorithmes de clustering traditionnels, le clustering spectral a la capacité de regrouper des échantillons dans des espaces de formes arbitraires et de converger vers la solution optimale globale. L'algorithme définit une matrice d'affinité basée sur un échantillon donné, qui est utilisée pour décrire la similarité des points de données appariés, et calcule les valeurs propres et les vecteurs propres de la matrice, et sélectionne les vecteurs propres appropriés pour regrouper différents points de données. Les algorithmes de clustering spectral ont été initialement utilisés dans la vision par ordinateur, la conception VLSI et d’autres domaines, et n’ont pas été utilisés dans l’apprentissage automatique avant 2005.

Caractéristiques du regroupement spectral

Le clustering spectral est un algorithme de clustering largement utilisé. Il présente une plus grande adaptabilité à la distribution des données que l'algorithme K-Means et possède un excellent effet de clustering. Dans le même temps, la quantité de calcul de clustering est plus petite et la mise en œuvre n'est pas compliquée.

Méthode de regroupement spectral

Le clustering consiste à diviser des échantillons en deux ou K parties de manière raisonnable. Du point de vue de la théorie des graphes, le problème de clustering est équivalent au problème de segmentation des graphes.

Étant donné un graphe G = (V, E), où l'ensemble de sommets V représente chaque échantillon et les arêtes pondérées représentent la similarité entre chaque échantillon, le but du clustering spectral est de trouver une méthode de partitionnement raisonnable afin que les poids des arêtes reliant les sous-graphes après partitionnement soient aussi faibles que possible et que les poids des arêtes au sein du même sous-graphe soient aussi élevés que possible.

Sous-mot : clustering

Mots apparentés : théorie des graphes