École Nationale Supérieure de
Techniques Avancées

Résumé

Dans ce rapport nous étudions le problème intitulé $K$-clustering (qui consiste à distribuer des points de données dans $K$ clusters avec un coût minimal) et plus particulièrement ses variantes tel que le $K$-clustering de cardinalité contrainte, le $K$-clustering de cardinalité équilibrée et le fair $K$-clustering. Ces variantes découlant du problème initial, permettent de corriger son défaut majeur qui est de produire des clusters vides ou quasiment vides. Le problème $K$-clustering de cardinalité contrainte impose une borne supérieure et inférieure sur la taille des clusters, quant au problème $K$-clustering de cardinalité équilibrée, il impose que la différence entre la taille de deux clusters ne soit d’au plus un. Le problème fair $K$-clustering garantit une distribution équitable pour chaque type d’élément dans chaque cluster. Pour résoudre ces problèmes nous utilisons la structure du fameux algorithme $K$-means, où nous modélisons la phase d’assignation comme un problème de flux de coût minimal. Pour résoudre ce dernier nous créons des graphes adaptés à chaque problème, ces derniers s'appuient sur la création de points fictifs qui permettent d'atteindre la capacité maximale du graphe et ainsi d'imposer des contraintes sur la taille des clusters en contrôlant le flux. Ensuite nous résolvons le problème de flux de coût minimal avec deux méthodes : une résolution successive du plus court chemin, et la deuxième méthode consiste en la résolution d'un programme linéaire. Nous étudions également l'influence du critère d'arrêt et de l'initialisation sur nos algorithmes. Pour finir, nous comparons empiriquement nos méthodes développées avec des méthodes issues de la littérature.