２乗誤差

今、クラスター数を $L$ とし、ベクトルの集合 $\{\mbox{\boldmath$x$}_i\vert i=1,\ldots,N\}$ がす でに $L$ 個のクラスター $\{C_l\vert l=1,\ldots,L\}$ にクラスタリングされていると する。また、各クラスターに割当てられたベクトルの数を $N_l (l=1,\ldots,L)$、 各クラスターの代表ベクトル（平均ベクトル）を

$$\bar{\mbox{\boldmath$x$}}_l = \frac{1}{N_l} \sum_{i \in C_l} \mbox{\boldmath$x$}_i$$ (193)

とする。

ベクトル $\mbox{\boldmath$x$}$ を新しく第 $l$ クラスターに追加した場合の２乗誤差の増加は、

$$\bigtriangleup S = \frac{N_l}{N_l + 1} (\mbox{\boldmath$x$}... ...th$x$}}_l)'(\mbox{\boldmath$x$} - \bar{\mbox{\boldmath$x$}}_l)$$ (194)

となる。このとき、クラスター $C_l$ の代表ベクトルは，

$$\bar{\mbox{\boldmath$x$}}_l^{new} = \frac{1}{N_l + 1} (N_l \bar{\mbox{\boldmath$x$}}_l^{old} + \mbox{\boldmath$x$})$$ (195)

のように更新される。

一方、クラスター $C_p$ と $C_q$ を統合し、データとして追加されるベクトル $\mbox{\boldmath$x$}$ のみを含むクラスターを新たに作った場合の２乗誤差の増加は、

$$\bigtriangleup S = \frac{N_p N_q}{N_p + N_q} (\bar{\mbox{\b... ...q)'(\bar{\mbox{\boldmath$x$}}_p - \bar{\mbox{\boldmath$x$}}_q)$$ (196)

となる。このとき、クラスター $C_p$ と $C_q$ の統合によって得られたクラスター $C_{p+q}$ の代表ベクトルは、

$$\bar{\mbox{\boldmath$x$}}_{p+q} = \frac{1}{N_p + N_q} (N_p \bar{\mbox{\boldmath$x$}}_p + N_q \bar{\mbox{\boldmath$x$}}_q)$$ (197)

となり、新しく作られるクラスター $C_{new}$ の代表ベクトルは、明らかに、

$$\bar{\mbox{\boldmath$x$}}_{new} = \mbox{\boldmath$x$}$$ (198)

である。

従って、データが与えられたら $\bigtriangleup S$ が最も小さくなるような更 新方法を探して、代表ベクトルを更新すれば、 逐次クラスタリングアルゴリズムが実現できる。

この時、毎回、$L(L-1)/2$ の全てのクラスター対の組合せに対して、どのクラスター 対を統合すれば最も２乗誤差の増加が少ないかを調べるのでは効率的でない。これは、 階層的なクラスタリングの高速化 [85,94]と同様に、クラスター 対を統合することによる２乗誤差の増加量をヒープ [178] として蓄えて、 それを更新することにより高速化することができる。