ヒープを用いた階層的クラスタリングアルゴリズム

階層的なクラスタリングでは、各階層で評価値が最小のクラスター対を見つけて、そ れらを統合することを繰返し、最終的な分類結果を得る。ある階層でのクラスターの 数を $n$ とすると、単純な探索方法では評価値が最小のクラスター対を見つけるた めに$O(n(n-1)/2)$ の手間が必要となる。ここでは、各クラスター対の評価をヒープ に蓄えることによりこの手間を減らすことを考える。

今、各クラスター対の評価値を蓄えたヒープがすでに作られているとすると、最小の 評価値を持つクラスター対は、ヒープの第1番目の要素 $H[1]$ に対応するクラスター 対である。従って、最小の評価値を持つクラスター対を見つける手間はかからない。 また、各階層でのクラスター対の統合によって影響を受ける評価値は、統合されるク ラスターに関係するもののみであるから、ヒープはクラスタリングの前に一度作れば、 あとは、各階層で統合されるクラスターに関係する要素のみを修正すればよいことに なる。ただし、統合によって影響を受けるクラスター対の評価値を修正するためには、 各クラスター対の評価値がヒープのどの要素に蓄えられているかの情報とヒープの各 要素がどのクラスター対の評価値を蓄えているかの情報が必要となる。ここでは、そ うした情報を配列 Where および Pair に蓄えることにする。