Classification sous contraintes/Les différents types de contraintes

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Matrice de données, de dimensions NxD

On considère disposer d'un ensemble de données X structurée et constituée de N objets, chaque objet étant décrit par D attributs (ou caractéristiques). La formule utilisée dans les sections suivantes pour le calcul des distances entre objets est définie de la manière suivante :

$d(x_{i},x_{j})={\sqrt {(x_{i1}-x_{j1})^{2}+...+(x_{iN}-x_{jN})^{2}}}$

Cette distance est donc égale à la norme du vecteur résultant de la soustraction de x_i et x_j, et peut s'écrire d(x_i,x_j) = d_ij.

Contraintes globales

Ajout d'attributs de position

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é.

Duplication des voisins

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. 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, les duplicatas de chacun de ses voisins (au sens de la distance calculée). 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.

Modification du calcul de distance

Contrairement aux méthodes précédentes qui modifient l’ensemble des données (et plus particulièrement, le vecteur attribut de chaque objet), 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 (la fonction la plus utilisée dans la littérature est bien souvent l'exponentielle).

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

avec d_ij^* représentant la distance modifiée incorporant l'information de voisinage, d_ij étant la distance originale entre les objets x_i et x_j, 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ène.

Modification de la fonction objective

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 objective (et donc le critère à optimiser) d'un algorithme de classification quelconque. 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 λ.

Contraintes de groupes

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 usité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, 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.

Contraintes d'attributs

La connaissance a priori peut également être interprétée comme de l'information dépendante des caractéristiques des objets.

Contraintes d'objets

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.

Étiquetage partiel

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. Pour cela, l’utilisation de règle simple est requise. Le vote majoritaire permet donc 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. 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.

Retour d'information

Les systèmes de classification intéractifs 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.

Relation entre paires d'objets

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. 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.