最後に、データが逐次的に得られるような状況でのクラスタリングのアルゴリズムに ついて考察する。多次元のベクトルデータが逐次的にしか得られないような場合に、 データを次々と処理してその時点で最良のクラスタリング結果を求めたいとする。こ のようなアルゴリズムは、例えば、ベクトルデータの情報圧縮のための適応的ベクト ル量子化等に応用できる。
ベクトル量子化[32]では、各ベクトルをどの代表ベクトルで代表させるか をコードとして記述することによりベクトル集合を情報圧縮する。現在、ベクトル量 子化は音声信号や画像の情報圧縮のための基本的な手法として利用されている。ベク トル量子化器を設計する場合には、代表ベクトルをどう選ぶか（コードブックの設計） と与えられたベクトルをどの代表ベクトルに符号化するか（量子化）の問題を考える 必要がある。コードブックの設計は，一般に学習データのクラスタリングにより求め られる。コードブックの設計アルゴリズムとしては，Linde ら[107]の提案 した k-means法 [3,163]に基づくLBGアルゴリズムが最も有名である．
一般にベクトル量子化を用いて情報圧縮する場合には、ある学習サンプルに対してコー ドブックをあらかじめ設計しておき、新たに入って来たベクトルをそのベクトル量子 化器で量子化する。画像圧縮の場合には、画像を小ブロックに分割し、各ブロックを ひとつのベクトルとみなしてベクトル量子化する。ベクトル集合の構造は画像ごとに かなり異なるため、あらかじめ全ての画像に対して好ましいコードブックを設計する ことはむずかしい。従って、画像ごとにコードブックを設計しなおして、そのコード ブックを用いてベクトル量子化する必要がある。実用的には、各画像に対してコード ブックの設計を高速に行なう必要がある。しかし、LBGアルゴリズムは基本的に k-means 法であり、データを繰返し処理して代表ベクトルを見つける手法であるため かなりの処理時間が必要となる．
ここでは、データを一回だけ処理して２乗誤差が最小となるように代表ベクトルを決 定するクラスタリングアルゴリズムを示す[91]。