Utilisateur:INFO EB04 2016/Brouillon

En intelligence artificielle, la classification guidée par des contraintes par paires (en anglais Pairwise Constrained clustering) est un ensemble de méthodes d'apprentissage semi-supervisé et un sous-ensemble des algorithmes de classification sous contraintes.

Définition

La classification guidée par des contraintes par paires est une classification utilisant une série de contraintes de liaisons (en anglais Must-Link ou ML^[1]), une série de contraintes de non-liaisons (en anglais Cannot-Link ou CL^[1]) ou les deux en même temps lors du déroulement de l’algorithme de classification sur un jeu de données $X$ .

Représentation de contraintes par paires

Une paire est un couple de données $\{x_{i},x_{j}\}$ $\subseteq X$ définissant 2 ensembles tels que:

$\{x_{i},x_{j}\}\in CL$ , $x_{i}$ et $x_{j}$ ne pouvant appartenir au même cluster
$\{x_{i},x_{j}\}\in ML$ , $x_{i}$ et $x_{j}$ devant appartenir au même cluster

Les contraintes de liaisons permettent d'associer deux données à une même classe alors que les contraintes de non-liaisons interdisent à deux données d'appartenir à une même classe.

Le respect de ces contraintes est plus ou moins suivi par les algorithmes de classification. Certains algorithmes cherchent une classe permettant de respecter toutes les contraintes, tandis que d'autres vont minimiser les violations de contraintes s'il n'existe aucune classe pouvant les respecter.

Algorithme de classification par paires

L'algorithme utilisé pour la classification par paires est le partitionnement K-moyennes, auquel on inclut les contraintes de liaisons et de non-liaisons. Pour cela, il existe plusieurs moyens de les introduire.

Algorithme K-Moyennes contraint par les centres

Afin d'implémenter ces contraintes, l'une des méthodes est la mise en place de centres forcés respectant ces contraintes. Ces centres forcés ne pourront changer au cours de l'algorithme, même en cas d'aberration. Cette étape n'intervient dans l'algorithme K-moyennes que lors de l'assignation d'un point à un centre.

Le pseudo-code présenté ci-dessous permet d'implémenter ces contraintes dans l'affection d'un point à un centre.

La première étape consiste à définir un jeu de données X ainsi qu'un ensemble de classes $C$ :

  $X$   $\leftarrow$  Jeu de données
  $C$   $\leftarrow$  Classes

Ensuite, on va forcer les points qui subissent une contrainte à un certain centre :

 Pour chaque paire  $\{x_{i},x_{j}\}$  de  $X$  
    Si  $\{x_{i},x_{j}\}\in ML$ 
        Alors
         $x_{i}$  et  $x_{j}$  sont associés à la même classe  $C_{k}$ 
    FinSi
    Si  $\{x_{i},x_{j}\}\in CL$ 
        Alors
         $x_{i}$  et  $x_{j}$  ne peuvent être associés à la même classe  $C_{k}$ 
    FinSi
FinPour

Enfin, on assigne à chaque point une classe tout en vérifiant les contraintes $ML$ et $CL$ :

 Pour chaque point  $x$  de  $X$ 
    Si  $x$  est soumis à une contrainte
        Alors
         $x$  est associé à la classe précédemment calculée
        Sinon
        Calculer la distance entre  $x$  et chaque centre de  $C$  et on assigne  $x$  au centre le plus proche
    FinSi
FinPour

Illustration de l'algorithme K-Moyennes contraint par les centres.

Sur cette illustration, on peut voir que les points $X5,X7,X8$ ont une contrainte $ML$ et appartiennent bien à la même classe. Les points $X5$ et $X10$ sont contraints par une $CL$ , ils n'appartiennent pas à la même classe, même si $X10$ est bien plus proche du centre $C1$ que du centre $C2$ .

Algorithme K-Moyennes contraint étendu

L'algorithme K-Moyennes contraint étendu est une version améliorée de l'algorithme K-Moyennes contraint par les centres. À la différence de ce dernier, les points faisant partie d'une paire de contrainte (Must-Link ou Cannot-Link) ne sont pas associés de manière définitive à un centre de classe tout au long de l'algorithme. Ils peuvent changer de centre de classe tout en respectant leurs contraintes.

Le pseudo-code présenté ci-dessous permet d'implémenter l'algorithme des K-Moyennes contraint étendu.

La première étape consiste à définir un jeu de données $X$ , un ensemble de classes $C$ ainsi que deux ensembles correspondant respectivement aux paires sous contraintes $ML$ et $CL$ :

  $X$   $\leftarrow$  Jeu de données
 $C$   $\leftarrow$  Classes
 $ML$   $\leftarrow$  Ensemble de paires Must-Link 
 $CL$   $\leftarrow$  Ensemble de paires Cannot-Link

Il convient ensuite de forcer les points qui subissent une contrainte à un certain centre :

Pour chaque point  $x$  du jeu de données  $X$ 
    Pour chaque paire  $\{x_{i},x_{j}\}$  de  $ML$ 
        Si il existe un point  $p$  de  $X$  autre que  $x$  soumis à une contrainte  $ML$ 
            Alors
            Vérifier que  $p$  s'est déjà vu affecté un centre pour cette itération
            Si c'est le cas
                Alors
                 $x$  est associé à la même classe que  $p$  
            FinSi
        FinSi
    FinPour 
    Si  $x$  n'est pas affecté à une classe
        Alors
        Pour chaque paire  $\{x_{i},x_{j}\}$  de  $CL$ 
            Créer un vecteur  $C'$  contenant les centres de  $C$  privé de ceux auxquels  $x$  ne peut être affecté
        FinPour
        Pour chaque centre  $c'$  de  $C'$ 
            Calculer la distance entre  $c'$  et le point  $x$ 
            Affecter à  $x$  la classe dont le centre est le plus proche
        FinPour 
    FinSi
FinPour

Illustration du respect de la contrainte Must-Link à une itération donnée sur le point X2	Illustration du respect de la contrainte Cannot-Link à une itération donnée sur le point X4

L'animation de gauche représente le traitement du point $X2$ au cours d'une itération. Il est soumis à une contrainte Must-Link avec $X1$ et $X3$ . Le premier étant plus proche du centre $C3$ , il a été attribué à la classe n°3. Par conséquent son voisin de droite $X2$ se retrouve associé à la classe n°3 alors qu'il est plus proche du centre de la classe n°2.

Sur l'animation de droite, on constate cette fois-ci que le point $X4$ se retrouve associé à la classe n°1 alors qu'il est plus proche du centre $C2$ de la classe n°2. Notre point est en effet soumis à une contrainte Cannot-Link avec le point $X3$ . Ce dernier étant associé à la classe n°2, le point $X4$ ne peut y être associé également.

Algorithme K-Moyennes basé distance

L'algorithme K-Moyennes basé distance n'utilise que des points de $X$ pour définir ces centres, appelé ici médians. Sur le principe de l'algorithme des K-médianes, l'algorithme K-Moyennes basé distance calcule la matrice distance entre chaque points du jeu de donnée. Cela permet d'éviter les nombreux calculs de distance lors de la recherche de centre le plus proche.

Les centres des classes ne peuvent alors pas être des points quelconques. L'algorithme utilise alors les points comme médians de classe.

Le pseudo-code présenté ci-dessous permet d'implémenter l'algorithme des K-Moyennes basé distance.

La première étape consiste à définir un jeu de données $X$ ainsi que deux ensembles correspondant respectivement aux paires sous contraintes $ML$ et $CL$ :

  $X$   $\leftarrow$  Jeu de données
 $ML$   $\leftarrow$  Ensemble de paires Must-Link 
 $CL$   $\leftarrow$  Ensemble de paires Cannot-Link 
 $K$   $\leftarrow$  Nombre de médians

Pour chaque couple du jeu de données
     $D(i,j)$   $\leftarrow$  distance entre  $x_{i}$  et  $x_{j}$ (pondérée entre 0 et 1)
FinPour 
Pour chaque paire  $\{x_{i},x_{j}\}$  de  $ML$ 
     $D(i,j)$   $\leftarrow$  0
FinPour
     
Pour chaque paire  $\{x_{i},x_{j}\}$  de  $CL$ 
     $D(i,j)$   $\leftarrow$   $\inf$ 
FinPour

Enfin, on choisit k-points pour définir les médians en respectant les contraintes $ML$ et $CL$ puis on peut procéder à l'assignation de la façon suivante :

 Tant que il n'y a pas de convergence
    Alors
    Chaque point est assigné à la classe dont le médian est le plus proche
    Les nouveaux médians sont calculés en respectant  $ML$  et  $CL$ 
FinTantQue

Illustration de l'algorithme K-Moyennes basé distance

Comme on peut le voir ci-dessus, au début de l'itération, les médians sont choisis parmi les points du jeu de donnée, tout en respectant les contraintes $ML$ et $CL$ . Après l'assignation de tous les points aux classes, le nouveau médian est calculé comme étant le point le plus proche de la moyenne de tous les points appartenant à la classe.

Algorithme de partitionnement spectral

L'algorithme de partitionnement spectral classique ne prend pas en compte les contraintes par paires. Pour y remédier, des modifications doivent être apporté à l'algorithme de base.

On utilise ce type de partitionnement lorsque nous disposons d'un jeu de données non linéairement séparable et il est particulièrement efficace pour un jeu de donnée à forte connexité. Dans un tel cas, il est nécessaire de changer repère afin de pouvoir classifier chaque données.

Prise en compte des contraintes^[2]

La première étape consiste à créer la matrice de similarité $S$ telle que définie dans l'algorithme de partitionnement spectral. On considère $k$ comme le nombre de classe.

On définit également une matrice d'adjacence $Q$ tel que $q_{ij}=s(x_{i},x_{j})$ . C'est cette matrice qui permettra la prise en compte des contraintes par paires, en plaçant la valeur $w_{ij}=1$ pour $\{x_{i},x_{j}\}\in ML$ et $q_{ij}=0$ ou $q_{i,j}=-1$ (selon les conventions d'écritures) pour $\{x_{i},x_{j}\}\in CL$ .

Il convient alors de construire une nouvelle matrice de similarité $S'$ telle que $S'=\alpha .S+(1-\alpha ).Q$ où $\alpha$ va permettre de pondérer le respect des contraintes contenues dans la matrice $Q$ .

On peut ensuite calculer un Lagrangien $L$ tel que $L=D^{-1/2}.S'.D^{1/2}$ , avec $D$ la matrice degré. Nous pouvons ainsi calculer les vecteurs propres et on extrait les $k$ vecteurs propres stockés dans un vecteur $V$ .

On normalise en ligne ce vecteur pour obtenir le vecteur $U$ . Enfin, on applique l'algorithme K-moyennes avec comme paramètres $U$ et $k$ .

Sélection des contraintes^[3]

Les contraintes doivent être choisies selon leurs utilités. En effet, une mauvaise sélection des contraintes détériore le partitionnement. Et à contrario, une bonne sélection améliore le résultat. Deux mesures permettent de qualifier cette utilité :

l'informativité qui mesure la quantité d'information apportée
la cohérence qui compare les contraintes entre elle.

Propagation automatique des contraintes^[3]

Une fois ces contraintes définies et implémentées, il est possible de les propager automatiquement. En effet, certaines combinaisons entre les $ML$ et les $CL$ permettent d'obtenir de nouvelles contraintes. Pour un jeu de donnée composé de 3 points :

Deux contraintes $ML$ induisent une troisième contrainte $ML$
Une contrainte $ML$ et une contrainte $CL$ induisent une contrainte $CL$
Deux contraintes $CL$ induisent une contrainte $ML$ si il n'y a que deux classes, sinon on ne peut rien en déduire

Contrainte actuel	Propagation de la contrainte

Notes et références

↑ ^{a et b} Kiri Wagstaf, Claire Cardie, Seth Rogers et Stefan Schroedl, « Constrained K-means Clustering with Background Knowledge », Proceedings of the Eighteenth International Conference on Machine Learning,‎ 2001, p. 577-584
↑ (en) Guillaume Wacquet, Emilie Poisson Caillault, Denis Hamad et Pierre Hébert, « Constrained spectral embedding for K-way data clustering », Pattern Recognition Letters,‎ juillet 2013
↑ ^{a et b} N Voiron, A Benoit, A Filip, P Lambert, B Ionescu. Clustering Spectral semi-supervisé avec propagation des contraintes par paires. 12 ème Conférence en Recherche d’Information et Applications - CORIA, Mars 2015, Paris, France.

[:0-1] {a et b} Kiri Wagstaf, Claire Cardie, Seth Rogers et Stefan Schroedl, « Constrained K-means Clustering with Background Knowledge », Proceedings of the Eighteenth International Conference on Machine Learning,‎ 2001, p. 577-584

[2] (en) Guillaume Wacquet, Emilie Poisson Caillault, Denis Hamad et Pierre Hébert, « Constrained spectral embedding for K-way data clustering », Pattern Recognition Letters,‎ juillet 2013

[:1-3] {a et b} N Voiron, A Benoit, A Filip, P Lambert, B Ionescu. Clustering Spectral semi-supervisé avec propagation des contraintes par paires. 12 ème Conférence en Recherche d’Information et Applications - CORIA, Mars 2015, Paris, France.

[1]

[2]

[3]