Partitionnement spectral

En informatique théorique, le partitionnement spectral ou spectral clustering en anglais, est un type de partitionnement de données prenant en compte les propriétés spectrales de l'entrée. Le partitionnement spectral utilise le plus souvent les vecteurs propres d'une matrice de similarités. Par rapport à des algorithmes classiques comme celui des k-moyennes, cette technique offre l'avantage de classer des ensembles de données de structure « non-globulaire », dans un espace de représentation adéquat. Ce partitionnement est notamment utilisé en intelligence artificielle, où le terme classification spectrale renvoie au fait de faire de la classification non-supervisée en utilisant ce type de partitionnement. Le partitionnement spectral est une méthode de partitionnement en K groupes reposant sur la minimisation d'un critère de type « coupe » (coupe simple à K=2, ou coupe multiple à K≥2). Ces deux mesures expriment la cohésion interne des groupes, relativement à leur dissociation les uns des autres. Elles sont directement fonctions d'une matrice de similarités entre objets, notée S. Étant donné un ensemble de N objets, il est possible d'obtenir une représentation détaillée de cet ensemble sous la forme d'un graphe pondéré (cf. théorie des graphes), noté G(V,E,S). V désigne l'ensemble des N nœuds du graphe, correspondant aux objets ; E est l'ensemble des arcs inter-nœuds et S est la matrice de poids des arcs (matrice de similarités), symétrique et non négative (Sij indiquant la similarité entre les objets xi et xj). thumb|center|upright=1.5|Exemple de graphe pondéré des données (en rouge, la coupe du graphe souhaitée). Dans le but de résoudre le problème d'optimisation du critère de coupe défini précédemment, le partionnement spectral s'appuie sur l'utilisation du spectre de la matrice de similarités des données en vue du partitionnement de l'ensemble des objets dans un espace de plus faible dimension. On a alors un problème de partitionnement de graphe pour lequel les nœuds d'un même groupe sont similaires et les nœuds appartenant à des groupes différents sont dissimilaires.