Regroupement équilibré - Balanced clustering

Le clustering équilibré est un cas particulier de clustering où, au sens strict, la taille des clusters est limitée à ou , où est le nombre de points et est le nombre de clusters. Un algorithme typique est k-means équilibré , qui minimise l' erreur quadratique moyenne (MSE) . Un autre type de clustering équilibré appelé clustering piloté par l'équilibre a une fonction de coût à deux objectifs qui minimise à la fois le déséquilibre et la MSE. Les fonctions de coût typiques sont ratio cut et Ncut. Le clustering équilibré peut être utilisé par exemple dans des scénarios où le fret doit être livré à des emplacements avec des voitures. Il est alors préférable que chaque voiture livre à un nombre égal d'emplacements.

Logiciel

Il existe des implémentations pour les k-moyennes équilibrées et Ncut

Les références

  1. ^ MI Malinen et P. Fränti (août 2014). "K-Moyens équilibrés pour le regroupement". Int. Atelier sur la reconnaissance de modèles structurels, syntaxiques et statistiques (S+SSPR 2014), LNCS 8621 .
  2. ^ L. Hagen et AB Kahng (1992). « Nouvelles méthodes spectrales pour le partitionnement et le regroupement par coupe de ratios ». Transactions IEEE sur la conception assistée par ordinateur .
  3. ^ J. Shi et J. Malik (2000). "Coupes normalisées et segmentation d'images" . Transactions IEEE sur l'analyse des modèles et l'intelligence machine . 22 (8) : 888-905. doi : 10.1109/34.868688 .
  4. ^ MI Malinen et P. Fränti. "Implémentation équilibrée de k-Means" . Université de Finlande orientale.
  5. ^ T. Cour, S. Yu et J. Shi. "Implémentation Ncut" . Université de Pennsylvanie.

MS Levin (2017). "Sur le regroupement équilibré (indices, modèles, exemples)". J. of Communications Technology and Electronics, 62(12): 1506-1515. doi : 10.1134/S1064226917120105