Techniques d'Optimisation Multi-Objectif avec les Algorithmes Évolutionnaires, et Application pour un Meilleur Clustering des Données

Ce texte est mon projet de fin d'année (2022). Les résultats cités à la fin de la section 7 sont ceux publiés par les auteurs de MOCLE.

Résumé

Ce qui fait la beauté des sciences des données, c'est de trouver des approches ou des solutions simples à des problèmes pratiques, qu'on prend au préalable le soin de modéliser, comme sous forme de fonction-objectif pour les problèmes d'optimisation.

Pour les cas les plus simples, c'est-à-dire des problèmes disposant d'une seule fonction-objectif, des algorithmes très performants existent déjà, comme les algorithmes de descente de gradient, le simplexe, le branch and bound…

Mais en raison de la nature multi-objectif de la plupart des problèmes pratiques, l'Optimisation Multi-Objectif s'impose comme un domaine de recherche très important. Autrement dit, dans la plupart des problèmes du monde réel, il ne s'agit pas d'optimiser suivant un seul critère, mais d'optimiser simultanément suivant plusieurs critères, qui sont souvent contradictoires. Ce qui implique généralement de devoir trouver un compromis entre les exigences techniques et les objectifs de coût.

De la même manière, chaque méthode de clustering conventionnelle n'optimise qu'un seul critère de regroupement (compacité, connexité, densité…) et ne retrouve donc qu'un seul type de clusters. Mais de nombreux jeux de données du monde réel ont une structure hétérogène, où chaque groupe répond à un critère différent, et peuvent même présenter plusieurs structures pertinentes à la fois.

Ainsi, pour l'Optimisation Multi-Objectif, la tâche sera d'abord de :

• se renseigner sur la modélisation des problèmes multi-objectif et des techniques d'Optimisation Multi-Objectif existantes, surtout les approches Pareto ;
• comprendre le concept des algorithmes évolutionnaires et comment ils sont utilisés pour résoudre des problèmes multi-objectif suivant les approches Pareto.

Et en ce qui concerne le clustering, il sera question de :

• effectuer une recherche complète des outils qui servent à réaliser le clustering de nos jours, que ce soit les méthodes standard de hard ou de soft clustering, mais aussi celles avancées telles que les ensembles de clustering ;
• savoir dans quelle mesure traduire les problèmes de clustering en problèmes multi-objectif ;
• se documenter sur comment ces derniers sont résolus avec l'apport des algorithmes évolutionnaires.

Pour, en fin de compte, présenter comment MOCLE arrive à combiner ces grandes lignes dans le but de réaliser de manière efficace le clustering des données.

Le Problème d'Optimisation

Définition

Un problème d'optimisation est défini par :

• un espace de recherche (de décision), constitué de l'ensemble des solutions ou configurations. Chaque solution est constituée des différentes valeurs prises par les variables de décision, qui peuvent être sous forme scalaire ou vectorielle ;
• une ou plusieurs fonction(s) dite(s) objectif(s), à optimiser (minimiser ou maximiser) ;
• un ensemble de contraintes à respecter.

Un Exemple : Le Plan de Production

L'entreprise mx, spécialisée dans la fabrication de matériel informatique, propose à son catalogue d'ordinateurs des centaines de modèles. Pour simplifier, on ne s'intéresse ici qu'à deux types d'ordinateurs : le MX1 et le MX2. Chacun d'eux comporte un processeur (le même) mais les deux modèles diffèrent en particulier par le nombre de barrettes mémoire. Plus précisément, le MX1 comporte 2 barrettes alors que le MX2 en comporte 6.

Le marché pour ces composants est tel qu'on ne peut espérer acheter auprès des fournisseurs habituels plus de 10 000 processeurs pour le trimestre à venir et plus de 48 000 barrettes.

Une autre limitation risque d'intervenir sur la production. L'assemblage est caractérisé, en particulier, par une opération délicate, qui pour le MX1 est de 3 minutes alors que pour le MX2 elle n'est que d'une minute ; on ne dispose a priori pour l'assemblage de ces deux types de machines que de 24 000 minutes pour le trimestre à venir.

Enfin, compte tenu des conditions actuelles du marché, on peut espérer retirer un profit de 400 euros sur le MX1 et de 800 euros sur le MX2.

Le problème est de déterminer les quantités de chacun des deux types d'ordinateurs à fabriquer de manière à obtenir le plus grand profit possible.

Modélisation et Résolution

Les variables de décision. Les décisions concernent les quantités à fabriquer, ce qui se représente naturellement par deux nombres positifs, x₁ pour le MX1 et x₂ pour le MX2.

Les contraintes. La première porte sur la limitation du nombre de processeurs disponibles : chaque machine utilise un processeur et on peut en disposer de 10 000. On doit donc imposer : x₁ + x₂ ≤ 10 000. De même, le nombre de barrettes est limité. Compte tenu du nombre de barrettes dans chacun des 2 ordinateurs et du nombre de barrettes disponibles, cette contrainte se traduit par : 2x₁ + 6x₂ ≤ 48 000. Enfin, la contrainte portant sur le temps d'assemblage s'écrit : 3x₁ + x₂ ≤ 24 000.

L'ensemble des décisions possibles est donc caractérisé par l'ensemble des valeurs de x₁ et x₂ vérifiant :

La fonction-objectif. On souhaite maximiser le profit, qui est représenté par : 400x₁ + 800x₂.

Modélisation complète :

Le modèle ainsi obtenu est un exemple de problème de programmation linéaire, à fonction-objectif unique. Sa solution optimale est x₁ = 3 000 et x₂ = 7 000, pour un profit de 6 800 000 euros. Si cela avait été un problème multi-objectif, on aurait eu au moins deux fonctions-objectif.

Les Bases de l'Optimisation Multi-Objectif

Dans le cas de l'Optimisation Multi-Objectif, la notion de solution optimale unique disparaît au profit de la notion d'ensemble de solutions Pareto-optimales.

Les problèmes d'Optimisation Multi-Objectif ont la particularité d'être beaucoup plus difficiles à traiter que leur équivalent mono-objectif. La difficulté réside dans l'absence d'une relation d'ordre total entre les solutions. Une solution peut être meilleure qu'une autre sur certains objectifs et moins bonne sur les autres. Donc il n'existe généralement pas une solution unique qui satisfasse l'ensemble des fonctions-objectif.

Il existe deux classifications différentes des approches de ce type de problèmes. Le premier classement adopte un point de vue décideur : les approches sont classées en fonction de l'usage que l'on désire en faire. Le deuxième classement adopte un point de vue concepteur : les approches sont triées selon leur façon de traiter les fonctions-objectif.

Classification Point de Vue du Décideur

1. Les approches a priori : le décideur intervient en amont du processus d'optimisation, pour définir la fonction d'agrégation modélisant le compromis que l'on désire faire entre les différents objectifs. Dans ce cas le décideur est supposé connaître a priori le poids de chaque objectif afin de les mélanger dans une fonction unique. Cela revient à résoudre un problème mono-objectif. Cependant, dans la plupart des cas, le décideur ne peut pas exprimer clairement sa fonction d'utilité, parce que les différents objectifs sont non commensurables (exprimés dans des unités différentes).
2. Les approches interactives : elles combinent de manière cyclique et incrémentale les processus de décision et d'optimisation : le décideur intervient de manière à modifier certaines variables ou contraintes afin de diriger le processus d'optimisation. Le décideur modifie ainsi interactivement le compromis entre ses préférences et les résultats. Cette approche permet donc de bien prendre en compte les préférences du décideur, mais nécessite sa présence tout au long du processus de recherche.
3. Les approches a posteriori : elles cherchent à fournir au décideur un ensemble de bonnes solutions bien réparties. Il peut ensuite, au regard de l'ensemble des solutions, sélectionner celle qui lui semble la plus appropriée. Ainsi, il n'est plus nécessaire de modéliser les préférences du décideur (ce qui peut s'avérer difficile), mais il faut en contrepartie fournir un ensemble de solutions, ce qui pourrait être difficile et requérir un temps de calcul important (mais ne nécessite pas la présence du décideur).

Classification Point de Vue du Concepteur

Ce classement adopte un point de vue plus théorique, articulé autour des notions d'agrégation et d'optimum de Pareto. Les approches utilisées pour la résolution de problèmes multi-objectif peuvent être classées en deux catégories.

Les Approches Non Pareto

Elles ne traitent pas le problème comme un véritable problème multi-objectif. Elles cherchent à ramener le problème initial à un ou plusieurs problèmes mono-objectif. La question est d'abord de savoir comment fusionner les différentes fonctions-objectif quand on a recours aux algorithmes génétiques, puisqu'en fin de compte, on calcule la fitness suivant une seule formule.

• La méthode de la somme pondérée : dans cette méthode, on devra procéder à une combinaison des différentes fonctions-objectif afin d'avoir une expression de fonction unique, sur la base de laquelle on pourra calculer la fitness des individus. C'est la plus connue des approches non Pareto. Mais avant, il faudra veiller à mettre les valeurs de toutes les fonctions-objectif à la même échelle. Dans le cas de deux fonctions-objectif, on peut écrire :
  J = w₁ · OBJ₁ + w₂ · OBJ₂ = w₁ · OBJ₁ + (1 − w₁) · OBJ₂

  avec OBJ₁ et OBJ₂ les deux fonctions-objectif, pondérées de w₁ et w₂ ; J est la fonction-objectif finale qu'on aura à utiliser. Bien que la méthode de la somme pondérée soit simple et facile à utiliser, elle présente deux problèmes inhérents. Premièrement, il est difficile de choisir des pondérations pour des objectifs qui ont des ordres de grandeur différents ; par conséquent, il y aura un biais dans la recherche d'une solution de compromis. Deuxièmement, si le front de Pareto n'est pas convexe, aucun jeu de pondérations ne permet d'atteindre les solutions situées dans ses parties non convexes.

• La méthode du critère global : elle est utilisée pour transformer l'optimisation de plusieurs objectifs en l'optimisation d'un seul, en minimisant la distance entre le vecteur des objectifs et un point de référence. Le point de référence est une solution idéale.
• La méthode des ε-contraintes : elle optimise un seul objectif tandis que les autres objectifs sont transformés en contraintes. Le vecteur ε fixe la limite (limite supérieure en cas de minimisation) de chacun de ces objectifs. Pour un vecteur ε donné, cette méthode trouve une solution optimale ; en changeant ε, nous pouvons obtenir plusieurs solutions optimales. L'inconvénient de cette méthode est qu'il n'y a pas de solution réalisable pour certains vecteurs ε.
• La méthode lexicographique : les décideurs sont invités à classer les fonctions-objectif par ordre d'importance. Le processus d'optimisation se fait individuellement sur chaque objectif suivant cet ordre. Après avoir optimisé l'objectif le plus important (le premier objectif), si une seule solution est renvoyée, alors cette solution est la solution optimale. Sinon, l'optimisation se poursuit sur le deuxième objectif, avec de nouvelles contraintes issues de la solution obtenue à partir du premier objectif. Ce cycle se poursuit jusqu'au dernier objectif.

Les Approches Pareto

Elles ne transforment pas les objectifs du problème : ceux-ci sont traités sans aucune distinction pendant la résolution. Autrement dit, on calculera la fitness suivant toutes les fonctions-objectif. Pour chacune des solutions retenues, il sera alors impossible d'améliorer l'un des objectifs sans en dégrader au moins un autre. De manière précise, on aura pour but d'optimiser k fonctions-objectif simultanément.

• Les k fonctions-objectif peuvent être toutes de maximisation, toutes de minimisation, ou une combinaison des deux.
• Les fonctions-objectif peuvent être linéaires ou non linéaires, continues ou discrètes.
• La fonction-objectif est une application du vecteur des variables de décision vers le vecteur des objectifs.

Il s'agira donc de trouver le vecteur x = [x₁, x₂, …, x_N] des variables de décision de sorte qu'il satisfasse :

• les m contraintes d'inégalité : g_i(x) ≥ 0, i = 1, 2, …, m ;
• les p contraintes d'égalité : h_j(x) = 0, j = 1, 2, …, p ;

(définissant les limites du domaine réalisable) tout en optimisant le vecteur de fonctions f(x) = [f₁(x), f₂(x), …, f_k(x)]. On se retrouve alors avec une large gamme de solutions, et la tâche sera de définir une relation d'ordre entre ces éléments. La plus célèbre et la plus utilisée est la dominance au sens de Pareto.

Dominance et Front de Pareto

• Notion de dominance : on dit qu'une solution x domine une solution y si elle est au moins aussi bonne suivant toutes les fonctions-objectif, et strictement meilleure suivant au moins l'une d'entre elles. Dans le cas où on uniformise toutes les fonctions-objectif sous forme de problèmes de minimisation, cela s'écrit :
  • ∀ i ∈ {1, 2, …, k}, f_i(x) ≤ f_i(y)
  • ∃ i ∈ {1, 2, …, k}, f_i(x) < f_i(y)
• Notion de non-dominance : dans un ensemble de solutions donné (par exemple une population), une solution x est dite non dominée s'il n'existe aucune autre solution de cet ensemble qui la domine.
• Optimum de Pareto : une solution x* est dite Pareto-optimale si et seulement s'il n'y a pas de x qui la domine (avec x parcourant les solutions réalisables). Une solution Pareto-optimale est donc non dominée dans tout ensemble qui la contient ; la réciproque est fausse. Lorsque les points de Pareto sont tracés dans l'espace des objectifs, les solutions non dominées dessinent le front de Pareto.

Points importants pour la détermination de la solution optimale de Pareto :

• Point d'ancrage : désigne la meilleure solution pour une fonction-objectif prise isolément. Les points d'ancrage constituent les extrémités du front de Pareto. Ce sont les deux points verts extrêmes sur le schéma.
• Point utopie (ou point idéal) : point obtenu par la meilleure valeur d'une fonction-objectif et la meilleure valeur de l'autre fonction-objectif. C'est la croix sur le schéma. Il n'est en général pas réalisable, mais il sera déterminant dans notre quête de la solution optimale.
• Point optimal : tous les points du front sont Pareto-optimaux ; si on doit n'en retenir qu'un, une règle courante est de prendre le point du front qui minimise sa distance euclidienne au point utopie. C'est le point cerclé sur le schéma.

Mais déjà, comment génère-t-on cet ensemble de solutions ?

Les Algorithmes Évolutionnaires

Les algorithmes évolutionnaires sont une famille d'algorithmes dont le principe s'inspire de la théorie de l'évolution pour résoudre des problèmes divers. Ce sont donc des méthodes de calcul inspirées du fonctionnement des êtres vivants dans la nature. C'est l'une des méthodes nous offrant une large gamme de solutions optimales ou plus ou moins optimales, selon les cas.

L'idée est de faire évoluer un ensemble de solutions à un problème donné, dans l'optique de trouver les meilleurs résultats. Ce sont des algorithmes dits stochastiques, car ils utilisent itérativement des processus aléatoires.

Les Grandes Familles

• Algorithmes génétiques : c'est le type le plus populaire. On cherche la solution d'un problème sous la forme d'une liste de nombres (traditionnellement binaires). Cependant, les meilleures représentations sont généralement celles qui reflètent vraiment le problème à résoudre, par exemple celles décimales ou les chaînes de caractères.
• Programmation génétique : ici, les solutions se présentent sous la forme de programmes informatiques et leur fitness est déterminée par leur capacité à résoudre un problème de calcul. Il en existe de nombreuses variantes.
• Programmation évolutive : semblable à la programmation génétique, mais la structure du programme est fixe et ses paramètres numériques peuvent évoluer.
• Stratégies d'évolution : fonctionnent avec des vecteurs de nombres réels comme représentations de solutions et utilisent généralement des taux de mutation auto-adaptatifs.
• Évolution différentielle : basée sur les différences vectorielles et convient donc principalement aux problèmes d'optimisation numérique.
• Neuroévolution : semblable à la programmation génétique, mais les génomes représentent des réseaux de neurones artificiels en décrivant la structure et les poids de connexion. L'encodage du génome peut être direct ou indirect.
• Systèmes de classeurs (learning classifier systems) : ici, la solution est un ensemble de classeurs (règles ou conditions). Un LCS de type Michigan évolue au niveau des classeurs individuels alors qu'un LCS de type Pittsburgh utilise des populations d'ensembles de classeurs.

Les Quatre Étapes

• Initialisation : il s'agit de se pencher d'abord sur comment représenter un individu (une potentielle solution), et ensuite sur le calcul de sa fitness en se basant sur la fonction-objectif, afin de générer une population sous forme de liste [individu → fitness].
• Sélection : choisir dans la population les individus qui serviront de parents, en favorisant ceux de meilleure fitness ; c'est l'étape où la fonction-objectif oriente la recherche. Les méthodes sont diverses : la sélection par tournoi (on tire quelques individus au hasard et on garde le meilleur), la roue de la fortune (probabilité proportionnelle à la fitness), la sélection par rang… Les parents sont ensuite appariés en couples.
• Croisement (crossover) : croiser les génomes de chaque couple de parents, pour en créer un ou plusieurs nouveaux individus : le(s) fils.
• Mutation : centrée sur l'individu, elle sert juste à modifier ses gènes suivant des seuils de probabilité donnés.

Suivant ces principes, il est évident qu'on est dans le cas d'une recherche approchée. L'efficacité des algorithmes génétiques repose sur un équilibre : la sélection concentre la recherche autour des meilleurs individus (intensification), tandis que l'initialisation aléatoire, le croisement et la mutation maintiennent des individus différents dans la population (diversification). Sans cette diversité, la population converge prématurément vers un optimum local.

Schéma Général

Construction et évaluation d'une population initiale (initialisation)
Jusqu'à atteindre un critère d'arrêt :
    sélection d'une partie de la population,
    croisement des individus sélectionnés,
    mutation de la descendance,
    calcul de la fitness de chaque individu,
    mise à jour de la population avec les nouveaux individus.

Convergence

L'avantage avec ce type d'algorithmes, c'est qu'on a la garantie d'avoir une solution à la fin. Ensuite, le point qu'on peut discuter, c'est celui de l'optimalité de la solution. Mais le fait est que, plus on laisse l'algorithme tourner, plus on aura de chances de tomber sur une bonne et meilleure solution au fil des itérations. Après, compte tenu de la complexité du problème, il faudra faire un compromis entre les ressources qu'on y alloue et le niveau d'optimalité voulu.

Les Algorithmes Évolutionnaires dans l'Optimisation Multi-Objectif

Les algorithmes évolutionnaires étant basés sur une population, il est facile de les étendre pour gérer plusieurs objectifs. Au contraire, les méthodes traditionnelles de recherche et d'optimisation telles que la descente de gradient sont difficiles à exploiter dans le cas des problèmes multi-objectif, puisqu'elles traitent généralement une fonction unique et également une solution unique.

À cause de l'intérêt croissant accordé au multi-objectif, les chercheurs ont également développé de nouveaux algorithmes évolutionnaires adaptés à la résolution de ces problèmes.

NSGA (Non-Dominated Sorting Genetic Algorithm)

On fait déjà l'association du non-dominated avec la non-dominance au sens de Pareto. En effet, c'est une méthode de résolution de problèmes multi-objectif basée sur les algorithmes évolutionnaires.

L'algorithme utilise le processus évolutionnaire classique, avec ses opérateurs de sélection, de croisement génétique et de mutation génétique. La différence est dans la sélection : la population est d'abord triée en fronts successifs selon la dominance au sens de Pareto, et la fitness d'un individu dépend de son front. Ensuite, au sein de chaque front, la similarité entre les membres est évaluée et la fitness des individus trop proches les uns des autres est réduite (fitness sharing), pour promouvoir un front diversifié de solutions non dominées.

NSGA-II

C'est une version améliorée de NSGA. Les individus sont classés et sélectionnés par fronts. Ce faisant, il arrivera des situations où un front devra être divisé parce que tous les individus ne sont pas autorisés à survivre. Dans ce front de division, les solutions sont sélectionnées en fonction de la distance d'encombrement (crowding distance). Son algorithme se présente comme suit :

1. Initialisation de la population : initialiser la population en fonction de la plage du problème et de la (des) contrainte(s).
2. Tri non dominé (non-dominated sorting) : processus de tri basé sur des critères de non-domination des individus, qui seront ensuite classés sur plusieurs fronts selon leur rang dans le tri. Le premier front est constitué des individus non dominés dans la population actuelle, et les individus du second front ne sont dominés que par les individus du premier front. L'objectif est que le front 1 converge vers le front de Pareto. Ensuite, en termes de classement, les individus du premier front occupent le rang 1, ceux du second le rang 2 et ainsi de suite. On calcule pour chaque individu p :
   • le domination count n_p, symbolisant le nombre d'individus (solutions) qui dominent le p actuel (le n_p de tous les individus du premier front est de 0) ;
   • S_p, l'ensemble des solutions dominées par l'individu p.

3. Tri basé sur la distance de surpeuplement ou d'encombrement (crowding distance) : la valeur de la distance d'encombrement d'une solution fournit une estimation de la densité des solutions entourant cette solution. Pour chaque objectif, c'est la distance entre ses deux solutions voisines, normalisée par l'étendue de l'objectif ; on somme ces valeurs sur tous les objectifs. Elle est calculée au sein d'un même front, et les deux solutions extrêmes du front reçoivent une distance infinie, ce qui garantit leur conservation. Ainsi, pour la sélection, chaque individu est caractérisé par deux attributs : son rang de non-domination et sa distance d'encombrement. Le tri favorise les distances élevées, c'est-à-dire les individus des régions les moins peuplées, ce qui pousse vers une répartition uniforme des solutions le long du front. Toutefois le rang nd prime sur le rang cd.

   NB : la crowding distance entre deux individus de fronts différents n'existe pas. Lire cd pour crowding distance et nd pour rang de non-domination (non-domination rank).

4. Sélection : la sélection des individus s'effectue à l'aide d'une sélection par tournoi binaire avec l'opérateur crowded-comparison ≺_n.
5. Opérateurs génétiques : les opérateurs génétiques tels que le croisement binaire simulé et une mutation polynomiale sont utilisés.
6. Remplacement (élitisme) : la population des descendants et la population de la génération actuelle sont réunies, puis retriées ; on garde les N meilleurs individus (par rang, puis par distance d'encombrement). Et on reprend le processus pendant un nombre de générations fixé en paramètre de l'algorithme.

Les Techniques de Clustering

Les algorithmes de clustering font partie des méthodes d'apprentissage non supervisé, permettant à la machine d'apprendre elle-même des données que l'humain lui fournit. Ils repèrent les similarités dans ces données pour pouvoir ensuite les structurer. Et étudier les similarités entre les individus d'un jeu de données rend possible leur division en différents groupes : ce partitionnement des individus est appelé clustering.

Pour chaque méthode, il est important de choisir comment mesurer la similarité de deux individus, qu'on peut représenter sous forme de deux points de l'espace des réels en dimension d. Là interviennent les fonctions de distance (ex. la distance euclidienne).

On classe les méthodes de clustering en deux grandes catégories : le hard clustering et le soft clustering. La différence entre les deux est que le hard clustering ne permet à un point d'appartenir qu'à un seul cluster, alors que le soft clustering autorise un même point à appartenir à plus d'un cluster.

Le Hard Clustering

Les méthodes de hard clustering sont les plus utilisées, et on classe les méthodes de clustering en 4 catégories selon ce qu'elles considèrent comme un cluster :

Centroid-based (les méthodes centroïdes). Dans ce type de méthode de regroupement, chaque cluster est référencé par un vecteur de valeurs, qu'est le centroïde. Ensuite, on calcule la distance entre le point d'entrée et chacun des centroïdes. Chaque objet fera partie du cluster dont le centroïde est le plus proche, comparé aux autres clusters, mais la principale contrainte de ce type d'algorithmes est que le nombre de clusters doit être prédéfini.

Ex. K-Means : la méthode centroïde la plus classique est la méthode des K-Means. Elle ne nécessite qu'un seul choix de départ : k, le nombre de clusters voulus.

1. On initialise l'algorithme avec k points au hasard parmi les n individus.
2. Ces k points représentent alors les k clusters. Ensuite, on associe chacun des (n − k) points restants à la « classe-point » qui lui est la plus proche. À la fin de cette étape, chaque classe est caractérisée par la moyenne des valeurs de chacun de ses individus. On a k moyennes pour k classes.
3. La troisième étape consiste à évaluer la distance de chaque individu à chacune des k moyennes. Certains individus peuvent ici changer de classe. À la fin de cette étape, on actualise les k moyennes. Et on réitère les étapes, jusqu'à ce qu'il y ait convergence, pour obtenir nos k clusters finaux.

Ces classes finales dépendent souvent beaucoup des k individus choisis pour l'initialisation. C'est pourquoi certaines implémentations de K-Means itèrent plusieurs fois le processus avec des initialisations différentes, dans le but de garder la partition qui minimise le plus la variance intra-classe (somme des carrés des distances entre les individus d'une classe et son centroïde).

Basé sur la densité. Ces algorithmes génèrent des grappes en fonction de la forte densité des membres d'un dataset à un emplacement déterminé. Ils utilisent une notion de distance et un seuil de densité pour regrouper les membres en clusters. Ces types de processus peuvent être moins performants lorsque les clusters ont des densités très différentes.

Ex. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) : en plus de former des classes d'individus, l'algorithme repère par la même occasion les valeurs hors du commun, que l'on qualifie de bruit.

Entrées :

• ε : la distance maximale qui peut définir deux individus comme voisins ;
• minPts : le nombre minimum de points requis pour qu'une région soit considérée comme dense.

Sorties : clusters avec densité (+ bruit). Chaque point est soit :

• point central d'un cluster : a au moins minPts points dans son voisinage ;
• point frontière : n'est pas un point central, mais a au moins 1 point central dans son voisinage. Autrement dit, il fait partie d'un cluster bien donné ;
• point de bruit : n'est ni un point central, ni un point frontière.

Étapes :

Choisir un point non visité → est-ce un point central ?
    Si oui → créer un cluster et l'étendre de proche en proche
             à tous les points atteignables depuis ses points centraux
    Si non → le marquer provisoirement comme bruit
             (il pourra devenir point frontière d'un cluster voisin)
Répéter l'opération jusqu'à avoir visité tous les points.
Les points restés marqués comme bruit sont éliminés.

Pour pallier le principal inconvénient de DBSCAN, qu'est le choix de ε (et son incapacité à trouver des clusters de densités différentes), a été conçu HDBSCAN (Hierarchical DBSCAN), qui construit une hiérarchie de clusters sur toutes les valeurs de densité puis en extrait les plus stables.

Basé sur la connectivité (les méthodes hiérarchiques). Elles forment pas à pas des connexions entre individus, pour les méthodes de clustering hiérarchique ascendantes. Pour les méthodes de clustering hiérarchique descendantes, elles cassent les groupes en plusieurs (en partant du groupe initial contenant tous les individus). Dans le premier type, chaque objet est lié à ses voisins, et les clusters sont définis en regroupant les voisins les plus proches en fonction du degré de cette relation et de la distance qui les sépare. La fonction de distance entre deux groupes varie selon le critère de liaison choisi (liaison simple, liaison complète, liaison moyenne, critère de Ward). On utilise le dendrogramme pour mettre les clusters en évidence.

Distribution-based (les méthodes basées sur une distribution). Cette méthodologie regroupe des objets dont les valeurs semblent provenir d'une même distribution de probabilité, par exemple une gaussienne (mélange de gaussiennes ajusté par l'algorithme EM). En raison de sa nature probabiliste, ce processus nécessite un modèle bien défini pour une bonne adéquation avec des données réelles. Notons que ces méthodes produisent en réalité des probabilités d'appartenance : elles relèvent du soft clustering, qu'on durcit en affectant chaque point à la distribution la plus probable.

Le Soft Clustering

Il existe différentes approches qui peuvent être considérées comme du soft clustering. La plus connue est le fuzzy clustering.

Fuzzy C-Means (Bezdek, 1981), ou Soft K-Means (en raison de sa similarité avec K-Means). Cette méthode phare du fuzzy clustering consiste à affecter des objets à des clusters avec des degrés d'appartenance, en fonction des dissemblances entre chaque objet et tous les prototypes, allant dans l'intervalle unitaire.

Par exemple, pour le hard clustering avec K-Means, un individu peut être classé comme étant d'une seule origine (représentée comme une classe) : français ou britannique. Mais une personne peut aussi être française et britannique (fuzzy clustering). Ici, la personne peut être française dans une certaine mesure et britannique dans une certaine mesure. Au lieu que la personne appartienne à britannique [britannique = 1] et pas à la classe français [français = 0], elle peut appartenir à français [français = 0,5] et aussi à britannique [britannique = 0,5].

Ces valeurs sont comprises entre 0 et 1 ; dans Fuzzy C-Means, elles sont contraintes à totaliser 1 pour chaque individu (c'est la variante possibiliste, Possibilistic C-Means, qui relâche cette contrainte). Principe :

• Choisir un certain nombre de clusters.
• Choisir le paramètre de flou m > 1 (souvent m = 2 ; plus m est grand, plus les appartenances sont partagées) et ε, le seuil de convergence.
• Attribuer des coefficients au hasard à chaque point pour appartenir aux clusters.
• Répéter ces deux sous-étapes jusqu'à ce que l'algorithme converge (la différence de coefficients entre deux itérations est en dessous de ε) :
  • calculer le centre de chaque cluster ;
  • pour chaque point, calculer ses coefficients d'appartenance aux clusters.

Les Méthodes Avancées de Clustering

Dans le chapitre précédent, on remarque que quasiment tous les algorithmes de clustering existants fonctionnent sur un critère de regroupement, c'est-à-dire la sélection d'une structure (ou d'un modèle) pour représenter les clusters, correspondant le mieux à l'ensemble des données analysées. Et par exemple, les algorithmes qui recherchent des clusters compacts, comme K-Means, sont biaisés vers des données à caractère sphérique.

Ce qui rend le clustering encore plus compliqué est que les mêmes données peuvent avoir plus d'une structure pertinente, chacune représentant une interprétation différente des données. Chacune de ces structures peut être en accord avec une définition de cluster ou un certain critère de regroupement. Hormis la robustesse, qui représente un de leurs défis majeurs, les techniques de clustering font face à de nombreux autres défis et difficultés tels que la prédiction du bon nombre de clusters, le passage à l'échelle, le choix de la bonne mesure de similarité et l'identification des points bruités.

Afin de résoudre ce problème, une combinaison de résultats de clustering est considérée comme une bonne alternative. Ce qui nous offrira en sortie différentes structures. S'ensuivra alors une étape de validation pour sélectionner la structure qui correspond le mieux aux données. Encore faudra-t-il prendre en compte le biais des méthodes de validation. Et quand on parle déjà de différentes conformations, on peut commencer par établir un lien avec la notion de multi-objectif. Deux approches existent pour y pallier.

Principe des Ensembles de Clustering

Cette méthode à fonction-objectif unique vise à combiner plusieurs modèles de hard clustering, pour la génération de plusieurs partitions d'individus, chacune issue d'un clustering bien précis, et leur combinaison pour générer une partition consensus via une fonction de consensus. Un ensemble aura un caractère homogène si toutes les partitions de base sont générées par le même algorithme de clustering, sinon il aura un caractère hétérogène.

Rappel : une partition d'un ensemble E est une famille de parties non vides de E, disjointes deux à deux, et dont la réunion est l'ensemble E.

Le plus connu est l'ensemble de Strehl et Ghosh, qui sera détaillé ci-après. Prenons un dataset de I points P = {P₁, P₂, …, P_I}, avec i = 1…I. Un ensemble combine J clusterings, et est représenté par Π = {π₁, π₂, …, π_J}. Chaque clustering π_j (solution de clustering) est simplement une partition de l'ensemble des données P en K_j clusters disjoints d'instances, avec j = 1…J. Chaque π_j contient K_j groupes et est représenté comme π_j = {G₁^j, G₂^j, …, G_Kj^j}, avec G désignant les groupes ou les clusters, k = 1…K_j.

Formulation et Codage des Partitions

Chez Strehl et Ghosh, la recherche de la partition consensus est considérée comme un problème d'optimisation combinatoire : trouver la partition qui partage le plus d'information mutuelle avec les partitions de base. Strehl et Ghosh le résolvent par des heuristiques (les fonctions de consensus ci-dessous) ; l'approche combinatoire se prête aussi à l'appel aux algorithmes génétiques pour la résolution, comme chez Luo, Jing et Xie (2006).

Modélisation des individus. On a P = {P₁, P₂, …, P_n} l'ensemble des points du dataset, qui seront partitionnés différemment par clustering. C'est à la forme de chacune de ces partitions qu'on s'intéresse : ce qui va représenter les individus. Ex. : supposons un dataset de 8 points P₁, …, P₈. Vu qu'une partition est le résultat d'un clustering, supposons que ce dernier a généré 3 classes telles que : P₁ → classe 1, P₂ → classe 3, P₃ → classe 1, P₄ → classe 3, P₅ → classe 2, P₆ → classe 3, P₇ → classe 2, P₈ → classe 3. Cet individu X_j sera représenté comme :

Une telle modélisation nous permettra d'introduire facilement des opérations classiques concernant les algorithmes génétiques au sein de la population.

Calcul de la fitness :

NMI étant une mesure de l'information mutuelle partagée entre deux clusterings (deux individus), à maximiser. On peut donc penser à la génération de nouveaux clusterings à partir de ceux existants afin de créer une population dense capable de fournir de bons résultats à partir des croisements. Ceci est appliqué lorsque le nombre de partitions de base est inférieur à 20, afin de densifier la population. Ce choix s'appuie sur les travaux de Luo, Jing et Xie (2006), révélant que les AG ne génèrent de bons résultats que si ce nombre est supérieur ou égal à 20.

Les Fonctions de Consensus

Tous ces groupes seront combinés à l'aide d'une fonction de consensus Γ, pour atteindre une partition plus représentative. Comme exemples, nous avons :

• CSPA (Cluster-based Similarity Partitioning Algorithm) : CSPA construit une nouvelle matrice de similarité, selon les partitions de base. Les entrées de cette matrice désignent la fraction de partitions dans lesquelles deux objets sont affectés au même cluster. La matrice est ensuite utilisée pour regrouper les objets avec n'importe quel algorithme de clustering basé sur la similarité, produisant la partition consensus.
• HGPA (Hyper-Graph Partitioning Algorithm) : dans l'algorithme HGPA, la combinaison est traitée comme un problème de partitionnement d'un hypergraphe. Les clusters des partitions de base sont représentés sous forme d'hyperarêtes ; l'hypergraphe est ensuite partitionné en coupant un nombre minimal d'hyperarêtes.
• MCLA (Meta-Clustering Algorithm) : les clusters des partitions de base sont eux-mêmes regroupés en méta-clusters, puis chaque objet est affecté au méta-cluster où il est le plus représenté. C'est l'opérateur qu'utilise MOCLE.

Le fonctionnement des fonctions de consensus peut toujours amener à repenser le processus de génération de l'ensemble lui-même. Il existe à cet effet une autre méthode d'ensemble de clusterings, basée sur le partitionnement de graphes, qu'est HBGF (Fern et Brodley, 2004), qui modélise objets et clusters comme les deux côtés d'un graphe biparti.

NB : CSPA, HGPA et MCLA font partie de la famille des méthodes hypergraphiques. Mais plus généralement, l'approche des fonctions de consensus est formée de six familles d'algorithmes : les méthodes hypergraphiques, les approches de vote, les méthodes de théorie de l'information, les méthodes basées sur la co-association, les modèles de mélange, les algorithmes évolutionnaires.

Limites d'un ensemble de clustering :

• les partitions de base de mauvaise qualité, si elles sont nombreuses, dégradent la partition consensus, même si quelques-unes sont excellentes ; de même, un cluster de qualité présent dans une seule partition de base est « écrasé » par les autres, si bien que le consensus ne peut pas être une structure hétérogène ;
• le résultat dépend d'un réglage fin des paramètres, et le nombre de clusters doit souvent être fourni à l'avance ;
• une seule partition consensus sera retenue, et la recherche d'une seule structure limite la quantité de connaissances qui pourraient être obtenues.

Le Clustering Multi-Objectif

Le multi-objectif est souvent préféré car il considère différents aspects d'un ensemble de données, sous forme de divers objectifs. NSGA et NSGA-II étant déjà présentés, il faut garder à l'esprit que les objectifs doivent être en conflit : minimiser l'inertie intra-classe et maximiser l'inertie inter-classes ne suffit pas, puisqu'à k fixé les deux reviennent au même (l'inertie totale est constante).

MOCK (Multi-Objective Clustering with automatic K-determination), d'autre part, est un algorithme basé sur Pareto et l'algorithme évolutionnaire PESA-II, capable d'optimiser simultanément deux critères de clustering complémentaires que sont la déviation globale et la connectivité. Ces deux critères tirent le nombre de clusters dans des sens opposés, ce qui évite les solutions triviales. De plus, pour obtenir la meilleure solution de compromis du front de Pareto, MOCK compare la forme du front obtenu à celle de fronts de contrôle calculés sur des données aléatoires.

La vraie problématique est : comment, avec un unique clustering, générer assez de groupes et y faire des choix ? Bien vrai, avec NSGA on diversifie la population, mais le problème est-il vraiment abordé sous le bon angle ?

MOCLE : Un Ensemble de Clustering Multi-Objectif

MOCLE se définit en anglais comme Multi-Objective Clustering Ensemble. MOCLE combine les deux approches de clustering avancé, ce qui contribue à atténuer leurs propres limites :

• il cherche non pas une, mais plusieurs partitions consensus, et le croisement qui les produit peut utiliser n'importe quelle fonction de consensus applicable à une paire de partitions ;
• ensuite, il combine des paires de partitions, de manière itérative, dans un processus d'optimisation, au lieu de la combinaison habituelle de toutes les partitions en même temps. Cette combinaison/sélection itérative des partitions évite l'influence négative des partitions de base de mauvaise qualité, qui peuvent diminuer la qualité des résultats des ensembles traditionnels.

Population Initiale et Opérateurs Génétiques

Population initiale. On a P = {P₁, P₂, …, P_I} l'ensemble des points du dataset de taille I, qui seront partitionnés différemment par différentes méthodes de clustering, chacune avec plusieurs réglages (en particulier plusieurs valeurs de k). Toutes ces partitions résultantes seront placées dans un ensemble. Un ensemble issu de J clusterings sera de la forme Π = {π₁, π₂, …, π_J}, avec j = 1…J. C'est cet ensemble qui constitue la population initiale.

Récapitulation :

• chaque partition π_j est partitionnée en K_j groupes G tels que π_j = {G₁^j, G₂^j, …, G_Kj^j} ;
• chaque individu dans notre algorithme sera une partition π_j.

NB : plus les algorithmes sont diversifiés (des algorithmes qui cherchent des clusters compacts à côté d'algorithmes qui cherchent des clusters connexes), plus les chances de produire un ensemble de clusters diversifié sont élevées. Et par conséquent, MOCLE recevra autant d'informations que possible pour trouver le plus grand nombre de structures existantes possible.

Crossover et mutation. MOCLE contient un opérateur de croisement spécial qui, avec la population initiale, est responsable de l'aspect d'ensemble de la technique. Cet opérateur trouve le consensus entre deux partitions parentes. Toute méthode d'ensemble de clustering existante pouvant être appliquée à une paire de partitions peut être utilisée comme opérateur de croisement (les auteurs utilisent MCLA).

Tout d'abord, en utilisant un tournoi binaire, deux parents sont sélectionnés pour être combinés : π_a et π_b, respectivement avec un nombre K_a et K_b de clusters. Cela donne lieu à une partition résultante π_c (partition consensus) comptant au plus K_c clusters, K_c étant tiré aléatoirement dans l'intervalle de variation des nombres de clusters des parents : K_c ∈ [min(K_a, K_b), max(K_a, K_b)].

Les partitions consensus, générées à chaque itération, sont également considérées dans les combinaisons suivantes. Cette combinaison itérative évite l'influence négative des partitions non représentatives de la réalité. Ces partitions de mauvaise qualité sont progressivement éliminées, tandis que les meilleures partitions et les bonnes combinaisons sont conservées pour une combinaison ultérieure.

Jusque-là, tous les groupes, autant qu'ils sont, sont effectivement des clusters, et faire une mutation génétique signifierait qu'on devra introduire des points quelconques dans un groupe donné : ce qui ne refléterait plus la réalité. Alors que MOCLE cherche avant tout à générer un ensemble concis de solutions représentatives du front de Pareto. Pour cela, il n'y a pas d'opérateur de mutation, et l'espace de recherche reste restreint aux partitions de base et à leurs combinaisons.

Mais Quand Introduit-on le Clustering Multi-Objectif ?

Jusque-là, on utilise une méthode de clustering d'ensemble. La modélisation des individus étant parfaitement faite, en suivant cette lancée, on devrait utiliser une fonction-objectif basée sur un score se calculant par la mesure des informations mutuelles partagées entre deux clusterings, donc à fonction-objectif unique, les clusters étant issus de hard clusterings.

De l'autre côté, le clustering multi-objectif, même avec peu de clusters, se focalise sur la bonne sélection de ceux-ci. Il les embarque dans un problème multi-objectif en évaluant chaque partition suivant plusieurs indices de validation à la fois. Ce qui l'illustre, c'est que dans le clustering d'ensemble on s'est limité à une seule mesure (la NMI), tandis que MOCLE reprend les deux fonctions-objectif de MOCK, à minimiser toutes les deux, et laisse NSGA-II (ou SPEA) faire le tri suivant ces deux critères :

• la déviation globale : la somme des distances entre chaque objet et le centre de son cluster. Elle est biaisée vers les clusters sphériques et s'améliore quand le nombre de clusters augmente ;
• la connectivité : elle mesure à quel point les objets voisins sont placés dans le même cluster (pénalité pour chaque objet dont l'un des L plus proches voisins est dans un autre cluster). Elle détecte des clusters de forme quelconque, mais gère mal les clusters qui se chevauchent, et s'améliore quand le nombre de clusters diminue.

Chacune compense la tendance de l'autre à faire varier le nombre de clusters, ce qui évite la convergence vers des solutions triviales. Sauf qu'avec ce dernier, plus il aurait eu de partitions candidates de qualité, plus l'algorithme serait efficace.

Solution : on arrive donc au point où on va juste transmettre la large gamme de partitions générée par la méthode d'ensemble de clusterings au problème de clustering multi-objectif, qui manquait justement d'un ensemble de solutions pertinentes. Et de là, faire des compromis sur le front de Pareto dans le cadre multi-objectif : le résultat n'est pas une partition, mais un petit ensemble de partitions, chacune représentant une région du front, entre lesquelles l'expert du domaine choisit.

Résultats Publiés par les Auteurs

Faceli, de Carvalho et de Souto (2007) évaluent MOCLE sur cinq jeux de données ayant chacun une ou plusieurs structures connues E_j : un jeu artificiel (ds2c2sc13, 588 points, trois structures emboîtées à 2, 5 et 13 clusters), deux jeux de référence de l'UCI (glass, iris) et deux jeux d'expression génique (leukemia, lung). La population initiale vient de K-Means, liaison moyenne, liaison simple et SNN. La qualité est mesurée par l'indice de Rand corrigé (CR) entre chaque structure connue et la partition la plus proche dans l'ensemble de solutions (1 : correspondance parfaite ; 0 : partition aléatoire), en moyenne sur 30 exécutions pour les méthodes non déterministes (KM, MOCK, ES et MOCLE ; AL, SL et SNN n'ont qu'un seul jeu de solutions). KM, AL, SL et SNN sont les algorithmes individuels, MK est MOCK (front complet), ES l'ensemble de Strehl et Ghosh, MN et MS sont MOCLE avec NSGA-II et avec SPEA.

Aucun algorithme individuel n'est bon partout : pour chaque structure, c'est un algorithme différent qui fait le meilleur score. MOCLE, sans qu'on ait eu à choisir d'algorithme, égale ou dépasse le meilleur algorithme individuel dans 60 % des cas, MOCK dans 70 % et ES dans 80 %, d'après les auteurs. Il manque toutefois nettement le meilleur sur deux structures : E3 de ds2c2sc13 (0,78 contre 1 pour SNN) et E1 de leukemia (0,28 contre 0,68 pour K-Means). Son ensemble de solutions est aussi bien plus concis que le front de MOCK (sur ds2c2sc13 : 114 partitions initiales, 81 dans le front de MOCK, 30 pour MOCLE ; sur iris : 20, 69 et 7) et stable d'une exécution à l'autre.

Conclusion

Les théorèmes du no free lunch (Wolpert et Macready, 1997) disent qu'en moyenne sur l'ensemble des problèmes possibles, aucune méthode d'optimisation ne fait mieux qu'une autre ; chacune n'est bonne que sur une classe de problèmes bien précise.

Au vu de tout ce qui précède, MOCLE est une belle représentation du fait que plusieurs méthodes préexistantes peuvent concourir, dans le but d'en fournir une meilleure, résolvant le mieux un problème : ici celui du clustering. Il s'agit notamment de la méthode d'ensemble de clusterings, qui se base sur les techniques de hard clustering existantes et sur une fonction de consensus pour fournir un lot diversifié de solutions de clustering, utilisables par le clustering multi-objectif, qui lui traite en détail la procédure de validation, avec deux indices de validation complémentaires et un algorithme comme NSGA-II adoptant non seulement la philosophie des algorithmes génétiques, mais aussi l'optimisation au sens de Pareto.

Bibliographie

1. Optimisation multi-objectif et problèmes d'optimisation multi-objectifs
2. Overview and simple applications
3. A Hands On Intro To Multi Objective Optimisation
4. Review of Multiobjective methods
5. Optimum de Pareto
6. Evolutionary Algorithm (Wikipédia)
7. Genetic Algorithms and Multi-Objective Optimisation
8. Comparison between GA, NSGA and NSGA II
9. Multiobjective optimization of cluster measures in Microarray Cancer data using Genetic Algorithm Based Fuzzy Clustering (PDF)
10. Clustering Algorithms
11. Unsupervised soft clustering methods
12. Exploring Clustering Algorithms: Explanation and Use Cases
13. GA and K-means for clustering
14. Clustering ensemble method
15. A Weighted Consensus Function to Combine Soft Clusterings
16. Consensus functions for cluster ensembles
17. Multi-objective clustering
18. Multi-objective clustering
19. Multiobjective clustering algorithm for complex data
20. K. Faceli, A. C. P. L. F. de Carvalho, M. C. P. de Souto, « Multi-objective clustering ensemble », International Journal of Hybrid Intelligent Systems, vol. 4, n° 3, p. 145–156, 2007.
21. MOCLE Implementation (GitHub)
22. N. Srinivas, K. Deb, « Multiobjective optimization using nondominated sorting in genetic algorithms », Evolutionary Computation, vol. 2, n° 3, p. 221–248, 1994.
23. K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, « A fast and elitist multiobjective genetic algorithm: NSGA-II », IEEE Transactions on Evolutionary Computation, vol. 6, n° 2, p. 182–197, 2002.
24. E. Zitzler, L. Thiele, « Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach », IEEE Transactions on Evolutionary Computation, vol. 3, n° 4, p. 257–271, 1999.
25. J. Handl, J. Knowles, « An evolutionary approach to multiobjective clustering », IEEE Transactions on Evolutionary Computation, vol. 11, n° 1, p. 56–76, 2007.
26. A. Strehl, J. Ghosh, « Cluster ensembles – a knowledge reuse framework for combining multiple partitions », Journal of Machine Learning Research, vol. 3, p. 583–617, 2002.
27. X. Z. Fern, C. E. Brodley, « Solving cluster ensemble problems by bipartite graph partitioning », Proceedings of the 21st International Conference on Machine Learning (ICML), 2004.
28. H. Luo, F. Jing, X. Xie, « Combining multiple clusterings using information theory based genetic algorithm », Proceedings of the International Conference on Computational Intelligence and Security, vol. 1, p. 84–89, 2006.
29. M. H. C. Law, A. P. Topchy, A. K. Jain, « Multiobjective data clustering », Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2004.
30. D. H. Wolpert, W. G. Macready, « No free lunch theorems for optimization », IEEE Transactions on Evolutionary Computation, vol. 1, n° 1, p. 67–82, 1997.
31. J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, 1981.

Illustrations : toutes les figures sont redessinées en SVG d'après celles du rapport (données synthétiques ou jeu de données iris, algorithmes réimplémentés pour la grille de comparaison et pour Fuzzy C-Means). Les deux schémas de NSGA-II sont redessinés d'après Deb et al. (2002).