Classification sous contrainte

La façon la plus évidente d'ajouter une notion de localisation spatiale dans un ensemble de données, est d'ajouter des attributs de position pour chacun des objets. Par exemple, pour une image à deux dimensions, ces attributs peuvent être définis comme étant la ligne et la colonne de chaque pixel de l'image. La fonction d(x_i,x_j), calculant la distance entre deux objets, permet alors d'affecter un degré de similarité important aux pixels proches et un degré faible à ceux qui sont éloignés. L'avantage de cette méthode réside dans le fait qu'elle ne requiert pas de modification de l'algorithme de classification utilisé.

On appelle voisin de x_i, l'objet x_j le plus proche de l'objet x_i en termes de distance d_ij dans l'espace en D dimensions (avec i≠j). La technique de duplication proposée consiste en l'augmentation de la taille du vecteur attributs d'un objet en ajoutant un ou plusieurs ensembles d'attributs selon le nombre de voisins considéré (cf. recherche des plus proches voisins). En effet, on affecte à chaque objet, un duplicata des caractéristiques de chacun de ses voisins (au sens de la distance calculée)[2].

Duplication du vecteur attributs d'un objet selon son voisinage.

Cependant, il est aisé de voir que cette approche est souvent impraticable car elle engendre une augmentation importante de la dimension des données et donc un coût non négligeable aussi bien en termes de temps de calcul qu'en termes d'espace mémoire nécessaire à l'exécution des algorithmes de classification utilisés.

Contrairement aux méthodes précédentes qui modifient l'ensemble des données (et plus particulièrement, le vecteur attribut de chaque objet par ajout de nouveaux attributs), certaines méthodes permettent d'intégrer des contraintes de manière moins directe. En effet, il est possible d'incorporer des informations spatiales en modifiant la manière de calculer la distance entre deux objets. Cette approche consiste à modifier la distance originale séparant deux objets par une fonction non-linéaire (une des fonctions les plus souvent utilisées dans la littérature est la fonction exponentielle).

${\displaystyle \mathrm {d_{ij}} ^{*}=d_{ij}[1-exp({{-u_{ij}} \over {W}})]}$

avec d_ij^* représentant la distance modifiée incorporant l'information spatiale (grâce au voisinage de x_i et x_j), d_ij étant la distance originale entre les deux objets, u_ij s'exprimant comme une mesure de distance égale au ratio des distances moyennes des voisins de chacun des objets x_i et x_j, et enfin W étant un poids (de valeur arbitraire ou fixée par l'utilisateur).

Cette méthode permet donc d'associer les caractéristiques des objets aux connaissances a priori afin d'obtenir une unique source d'information. L'objectif est alors de trouver des groupes d'objets de compacité équitable et homogènes.

La dernière catégorie de méthodes intégrant des contraintes globales, et plus particulièrement des informations de voisinage, est celle modifiant la fonction objectif (et donc le critère à optimiser) d'un algorithme de classification quelconque, utilisant une procédure d'optimisation. Afin de prendre en compte les contraintes définies, il est nécessaire de remplacer cette fonction par une somme pondérée de la fonction originale avec l'information de voisinage à disposition.

De manière générale, l'optimisation de la compacité (ou variance) et de la contiguïté des groupes d'objets, nécessite la spécification de l'importance relative des deux objectifs via un paramètre de pondération λ :

${\displaystyle \mathrm {f_{original}} ^{*}=f_{original}+\lambda *{f_{contraintes}}}$

ou encore :

${\displaystyle \mathrm {f_{original}} ^{*}=(1-\lambda )*f_{original}+\lambda *{f_{contraintes}}}$

avec f_original^* la nouvelle fonction objectif (données originales et contraintes), f_original la fonction originale (données originales) et f_contraintes la fonction à optimiser pour l'information a priori (contraintes).

La connaissance à disposition peut également être fournie sous la forme d'information sur les groupes d'objets. Ces contraintes permettent de définir des exigences sur la forme globale, l'orientation ou d'autres caractéristiques des groupes. La capacité minimum ou maximum de ces derniers semble être la caractéristique la plus utilisée dans la littérature :

• Contraintes de capacité minimum : des méthodes permettant d'utiliser des contraintes sur des groupes d'objets ont été développées récemment[3], afin d'éviter d'obtenir des solutions contenant des groupes vides (solution obtenue en particulier, pour l'algorithme des k-moyennes appliqué à des données de dimensions importantes ou lorsque le nombre de groupes défini est grand). Cette approche impose des contraintes sur la structure des groupes. En effet, il est alors possible de spécifier un nombre minimum d'objets pour chaque groupe.
• Contraintes de capacité maximum : afin d'essayer de faire respecter ce genre de contraintes, il est souvent pratique d'utiliser un algorithme de classification non-supervisée du type regroupement hiérarchique. En effet, à partir de la hiérarchie créée, il est possible de sélectionner des groupes d'objets adaptés permettant de faire respecter la contrainte définie.

La connaissance a priori peut également être interprétée comme de l'information dépendante des caractéristiques des objets. Ces contraintes permettent d'orienter la classification des objets selon leurs valeurs pour un attribut donné. Un algorithme de classification hiérarchique contraint et incorporant des contraintes d'attributs a été développé en 1998[4] par Bejar et Cortes.

Les contraintes d'objets définissent des restrictions sur des paires individuelles d'objets. Ce type de connaissance a priori sur les données est généralement fournie sous trois formes :

• les étiquettes de classes,
• le retour d'information,
• les contraintes de comparaison par paires d'objets.

L'étiquetage des objets d'un ensemble de grande dimensions représente une tâche difficile et coûteuse en temps ce qui la rend souvent infaisable. En revanche, il est possible d'étiqueter un sous-ensemble ne contenant que quelques objets. Cette nouvelle source d'information peut alors être utilisée de deux façons différentes :

• identification des groupes obtenus : après avoir appliqué un algorithme de classification non-supervisée, les groupes d'objets obtenus peuvent être identifiés grâce au sous-ensemble d'objets étiquetés au préalable[5]. Pour cela, l'utilisation de règles simples est requise. Parmi ces dernières, le vote majoritaire semble être une bonne alternative puisqu'il permet d'affecter une identité (ou une étiquette) à chaque groupe obtenu,
• initialisation intelligente des algorithmes de partitionnement utilisés : L'initialisation de certains algorithmes de classification non-supervisée est une étape importante et peut se révéler cruciale dans la validation et l'interprétation des résultats de partitionnement obtenus[6]. C'est pourquoi, il semble intéressant d'utiliser l'information contenue dans ces étiquettes de classes afin d'orienter le choix des paramètres initiaux.

Les systèmes de classification interactifs adoptent une approche itérative, dans lesquels le système produit une partition des données puis la présente à un expert afin de l'évaluer et la valider. Cet expert peut alors indiquer clairement les erreurs de partitionnement (induits par le système), puis cette information peut être utilisée lors de l'itération suivante de l'algorithme. Cependant, le désavantage de cette méthode réside dans le fait qu'un expert peut se retrouver en difficulté lors de la validation des résultats si l'ensemble des données est de dimensions importantes.

Contraintes Must-Link et Cannot-Link sur le plan (trois groupes de points de forme gaussienne).

Si l'étiquetage des objets se révèle être une tâche longue et complexe, les contraintes par paires, attestant simplement que deux objets doivent être dans la même classe (Must-Link) ou non (Cannot-Link), sont par contre plus aisées à recueillir auprès d'experts[7]. De plus, cette manière de représenter l'information relationnelle est souvent considérée comme la plus générale, de par le fait qu'elle puisse reprendre une grande partie des contraintes précédemment citées. En effet, les contraintes globales ainsi que les contraintes d'attributs peuvent facilement se mettre sous la forme de contraintes de paires d'objets. Ces contraintes relationnelles peuvent être rangées dans deux catégories :

• les contraintes dures : elles se doivent d'être respectées dans la partition en sortie de l'algorithme,
• les contraintes souples : elles peuvent être ou ne pas être respectées dans la partition en sortie de l'algorithme (elles sont considérées comme des "préférences").

Comme démontré dans ce tableau, les contraintes de comparaison Must-Link définissant une relation d'équivalence entre objets, sont transitives, alors que les contraintes Cannot-Link sont bien symétriques mais non transitives. En effet, il est impossible de prédire la relation liant deux objets x_i et x_k, sachant que les paires de points (x_i,x_j) et (x_j,x_k) sont liées par deux contraintes Cannot-Link indépendantes.