Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de Lloyd-Max
Résumé
En algorithmique et en traitement du signal, l’algorithme de Lloyd-Max est un algorithme qui permet de construire le quantifieur scalaire optimal. C'est donc une méthode pour quantifier un signal en une dimension de manière à minimiser la distorsion, mesurée par l'erreur quadratique moyenne.
L'optimalité du quantifieur est assurée par deux conditions sur les niveaux de reconstruction et de décision, découvertes par Lloyd en 1957. Il fournit aussi un algorithme, qui permet de construire itérativement le quantifieur optimal. L'algorithme peut être étendu à la quantification de vecteurs (algorithme de Linde-Buzo-Gray).
L'algorithme fut développé par Lloyd en 1957, mais n'a pas été publié en revue scientifique. Il fut présenté à l'Institut de Statistiques Mathématiques et la seule version imprimée est un mémorandum technique des laboratoires Bell. L'algorithme resta donc peu connu pendant plusieurs années. Les résultats exposés dans le mémorandum furent redécouverts indépendamment par plusieurs chercheurs. Cependant toutes ces redécouvertes utilisèrent des dérivations différentes de celle utilisée par Lloyd, indispensable pour l'extension du théorème à la quantification de vecteurs et pour plusieurs procédures d'optimisation de quantificateurs.
L'algorithme fut notamment redécouvert par Joel Max en 1960.
L'algorithme est initialisé par k points de l'espace d'entrée. Il itère ensuite la procédure suivante:
calculer le diagramme de Voronoï des k points
intégrer chaque cellule de Voronoï de manière à en déterminer le centroïde
chacun des k points est alors déplacé sur les centroïdes
L'algorithme diffère de l'algorithme des k-moyennes au sens où ce dernier agit sur des données discrètes (par exemple un ensemble de points d'un espace vectoriel) alors que l'algorithme de Lloyd-Max peut être appliqué à des données continues (par exemple une densité).
Un quantifieur scalaire peut se définir comme un ensemble d'intervalles de l'espace de départ, , où les sont appelés niveaux de décision.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.