階層的クラスタリングアルゴリズム

次に、より一般的な多次元のデータのクラスタリングアルゴリズムについて考察する。

多次元データのクラスタリングアルゴリズムは、似たもの同士を併合していくつかの グループにまとめて行く階層的なクラスタリング (hierarchical clustering method) と、似たものが結果的に同じグループに入るように集合を分割する非階層的クラスタ リング (non-hierarchcal clustering method) とに大別して考えることができる。

非階層的クラスタリングの代表例は、k-mean法である。k-mean法は、ある初期分割か らはじめて、ある評価基準の意味で良い分割結果が得られるように対象を分類しなお すことを繰返して、最終的な分割結果を得る。k-mean法およびその改良版はアルゴリ ズムが比較的簡単なため、多くの場面で応用されている。例えば、ベクトル量子化器 の設計法として有名な LBG アルゴリズム [107]でも、k-mean 法が使 われている。しかし、非階層的クラスタリングアルゴリズムは、最終的な分割が初期 分割の影響を受けやすいく、しかも、分割が局所最適な分割になりやすいという欠点 を持っている。

一方、階層的なクラスタリングでは、最初、各対象をばらばらの一つのクラスターと みなして、近いクラスターを次々と統合することによって、最終的な分類結果を得る。 階層的なクラスタリングは、比較的性質の良い分類結果が得られることが知られてい るが、素直にプログラムを作ると最大 $O(N^3)$ の計算時間が必要であり、非階層的 なクラスタリングに比べて、分類対象がかなり少ない場合にしか適用できない。 従って、階層的クラスタリングを実用的な規模の問題に適用するためには、アルゴリ ズムをどうやって高速化するかがキーとなる。

半導体技術の急速な発展と仮想記憶等のソフトウェア技術の進歩により、プログラム で扱える記憶領域はどんどん大きくなってきている。従って、記憶領域がいくらか多 く必要であっても、より高速なアルゴリズムを開発することは意味のあることと考え られる。以下では、そうした観点から、クラスターの統合のために最適なクラスター 対を高速に探すために、ヒープを用いるアルゴリズムを提案する。ヒープにクラスター 対の評価に関する情報を蓄えることによって、必要な記憶領域はデータ数 $N$ に対 して、$O(N^2)$ 必要となるが、計算時間は高々 $O(N^2\log(N))$ で済み、従来法に 比べて、より多くの対象のクラスタリングが可能となる。

次節では、まず、ソーティングの高速化のために、J.Williams [178] に よって発明されたヒープと呼ばれるデータ構造について概観し、次に、それを階層的 クラスタリングの高速化のために利用する方法について考察する [85,94]。さらに、アルゴリズムの高速化の効果を調べる ための簡単な比較実験について述べる。