今、クラスター数を とし、ベクトルの集合
がす
でに
個のクラスター
にクラスタリングされていると
する。また、各クラスターに割当てられたベクトルの数を
、
各クラスターの代表ベクトル(平均ベクトル)を
![]() |
(193) |
ベクトル
を新しく第
クラスターに追加した場合の2乗誤差の増加は、
![]() |
(194) |
![]() |
(195) |
一方、クラスター と
を統合し、データとして追加されるベクトル
のみを含むクラスターを新たに作った場合の2乗誤差の増加は、
![]() |
(196) |
![]() |
(197) |
![]() |
(198) |
従って、データが与えられたら
が最も小さくなるような更
新方法を探して、代表ベクトルを更新すれば、
逐次クラスタリングアルゴリズムが実現できる。
この時、毎回、 の全てのクラスター対の組合せに対して、どのクラスター
対を統合すれば最も2乗誤差の増加が少ないかを調べるのでは効率的でない。これは、
階層的なクラスタリングの高速化 [85,94]と同様に、クラスター
対を統合することによる2乗誤差の増加量をヒープ [178] として蓄えて、
それを更新することにより高速化することができる。