ベクトル量子化（k-平均問題）

ベクトル量子化、またはk-means問題は、与えられたd次元の数値ベクトルからなるデータセットXと正の整数kに対して、k個のd次元ベクトルからなるコードブックCを見つけることを目指しています。このとき、X内の各ベクトルとC内の最も近いベクトルとの距離の二乗和が最小になるようにします。この問題はNP困難であり、データ圧縮、クラスタ分析、特徴量エンコーディングなどの分野で広く応用されており、理論的にも実践的にも重要な意味を持っています。