評価基準に沿って導出したbottom-up mergingによる手法

次に、各項目を一つのクラスターに対応させた $M$ 個のクラスターから始めて、クラ スター数が $K$ になるまで、次々と二つのクラスターを統合し、新しいクラスターを つくる bottom-up merging による階層的な手法を問題の評価基準に沿って導出する。

項目を $\{C_1^{(p)},\ldots,C_p^{(p)}\}$ の $p (K \le p \le M)$ 個のクラスターに分割 する場合、問題の評価基準(5.2)は、

$$f(C_1^{(p)},\ldots,C_p^{(p)}) = \sum_{k=1}^p w(\bigcup_{i \in C_k^{(p)}} \mbox{\boldmath$x$}_i)$$ (264)

と書ける。ここで、$C_k^{(p)}$ は、$p$ 個に分割したときの第 $k (1 \le k \le p)$ 番目のクラスターに属する項目の集合を表す。この時、第 $k$ クラスターの評 価値は第 $k$クラスターに属する項目の該当ベクトルの要素ごとのORを取ったベクト ルの $1$ の個数によって決まる。従って、第$k$クラスターを代表するベクトルを

$$\mbox{\boldmath$r$}_k^{(p)}=\bigcup_{i \in C_k{(p)}} \mbox{\boldmath$x$}_i$$ (265)

とすると、(5.3)式の右辺は

$$\sum_{k=1}^p w(\mbox{\boldmath$r$}_k^{(p)})$$ (266)

と書ける。このクラスター代表ベクトルは、会議の関係者がそのクラスターに関係し ているかどうかを示す該当ベクトルである。

最終的評価値(5.2)を小さくするためには、クラスターを統合する時、 統合後の評価値を最小にする、つまり、統合の前と後の評価値の差を最大にするクラ スターの対を統合すればよい。

統合前のクラスターを $\{C_1^{(p)},\ldots,C_p^{(p)}\}$, $(K \le p \le M)$ とし、 クラスター $C_i^{(p)}$ と $C_j^{(p)}$, $(i<j)$ を統合する場合を考える。統合 前の評価値は(5.5)で与えられ、統合後の評価値は、

$$\sum_{k=1}^{i-1} w(\mbox{\boldmath$r$}_k^{(p)}) + \sum_{k... ...(\mbox{\boldmath$r$}_i^{(p)} \cup \mbox{\boldmath$r$}_j^{(p)})$$ (267)

と書ける。ただし、 $\mbox{\boldmath$x$} \cup \mbox{\boldmath$y$}$ はベクトル $\mbox{\boldmath$x$}$ と $\mbox{\boldmath$y$}$ の要 素ごとのORを取ることを表す。

従って、統合前と統合後の評価値の差は、

$$w(\mbox{\boldmath$r$}_i^{(p)}) + w(\mbox{\boldmath$r$}_j^{(... ...(\mbox{\boldmath$r$}_i^{(p)} \cap \mbox{\boldmath$r$}_j^{(p)})$$ (268)

となる。ただし、 $\mbox{\boldmath$x$} \cap \mbox{\boldmath$y$}$ はベクトル $\mbox{\boldmath$x$}$ と $\mbox{\boldmath$y$}$ の要素 ごとのAND（論理積）を取ることを表す。すなわち、二つのクラスター間の評価測度 として、

$$m(\mbox{\boldmath$r$}_i^{(p)},\mbox{\boldmath$r$}_j^{(p)}) = w(\mbox{\boldmath$r$}_i^{(p)} \cap \mbox{\boldmath$r$}_j^{(p)})$$ (269)

が導かれる。この測度 $m$ は Russell と Rao の Matching Coefficient $R$ [3] と

$$R = m / N$$ (270)

なる関係がある。従って、$m$ を最大とするクラスター対を統合することはクラスター 代表ベクトル間の Russell と Rao の Matching Coefficient $R$ を最大とするクラ スター対を統合することと等価になる。ただし、評価基準から自然に導かれた測度 $m$ には両方のクラスターにまたがって関係する人の数という論理的な意味があり、 問題とのつながりが明白である。

また、$C_i^{(p)}$ と $C_j^{(p)}$ の統合によって新しく作られるクラスターの代 表ベクトル $r_{i+j}$は、上述の議論から、

$$\mbox{\boldmath$r$}_{i+j}^{(p-1)} = \mbox{\boldmath$r$}_i^{(p)} \cup \mbox{\boldmath$r$}_j^{(p)}$$ (271)

となり、統合前のクラスターの代表ベクトルの要素ごとの OR を取ったベクトルによっ て簡単に表せる。それ以外のクラスターの代表ベクトルは、変わらず、

$$\mbox{\boldmath$r$}_s^{(p-1)} = \mbox{\boldmath$r$}_s^{(p)} \ \ \ (s \ne i,j)$$ (272)

である。

階層的クラスタリング手法には、二つのクラスター間の測度をどう定めるかによって 多くの変種が存在する[3]。例えば、Single Linkage法では、最も似た 二つのベクトルを各クラスターの代表ベクトルとして、それらの間に定義された測度 を二つのクラスター間の測度と定義している。これに対し、ここで提案した手法では、 評価基準から各クラスターの代表ベクトルおよびクラスター間の測度 $m$ が一意に 定まりそれぞれ明確な論理的意味を持っている。

測度 $m$は離散的な値を取るため値が等しい（タイの）場合の処理方法を考えておく ことは重要である。トップダウンに何等かの距離（メトリック）を導入した場合には、 これは非常に難しい問題であるが、日程表作成問題では、題意から簡単なheuristics が考えられる。延べ出席日数を最小とするためには、各クラスターに関係する人の数 を少なくする必要がある。従って、タイの場合には、統合後のクラスターに関係する 人の数の少ないクラスター対を統合すればよい。統合後のクラスター対に関係する人 の数は、二つのクラスター代表ベクトルの要素ごとの OR を取ったベクトルの $1$ の 個数に他ならない。それは、測度 $m$ の計算と同時に計算できる。従って、タイの 場合の処理を加えても計算量はほとんど変わらない。

実際のアルゴリズムでは、クラスターの統合を定数時間で実行するため、各クラスター をそのクラスターに属する項目のダブルリンクドリストで表現している。