Quantification vectorielle (problème k-moyennes)

La quantification vectorielle, ou le problème des k-moyennes, vise à trouver un codebook C composé de k vecteurs d-dimensionnels pour un ensemble de données X donné de vecteurs numériques d-dimensionnels et d'un entier positif k, de manière à minimiser la somme des carrés des distances entre chaque vecteur de X et son vecteur le plus proche dans C. Ce problème est NP-difficile et trouve de nombreuses applications dans des domaines tels que la compression de données, l'analyse de clusters et l'encodage de caractéristiques, ce qui en fait une question d'une importance théorique et pratique considérable.