Vektorquantisierung (k-Means-Problem)

Vector Quantization oder das k-means Problem zielt darauf ab, ein Codebuch C zu finden, das aus k d-dimensionalen Vektoren besteht, für einen gegebenen Datensatz X von d-dimensionalen numerischen Vektoren und einer positiven ganzen Zahl k, so dass die Summe der quadrierten Abstände von jedem Vektor in X zu seinem nächsten Vektor in C minimiert wird. Dieses Problem ist NP-schwer und findet weite Anwendung in Bereichen wie Datenkompression, Clusteranalyse und Merkmalskodierung, was ihm sowohl theoretische als auch praktische Bedeutung verleiht.