はじめに

クラスター分析[3,163]は、複数の特性によって決定された個 体間の類似性の指標をもとに、個体の集合をいくつかのグループに分類するた めの手法である。その起源は、生物学の分野での生物分類学であると考えられ る。現在では、データに含まれる構造や関係を明らかにするための手法として 生物学や植物学をはじめ医学、社会科学、地球科学、政治経済学等、様々な分 野で利用されている。工学の分野においても、パターン認識をはじめとして様々 な問題に適用されている。例えば、通信の分野では、クラスタリングはベクト ル量子化と呼ばれ、情報の圧縮のための基本的な手法として使われている [32,107,119]。また、それは、組合せ問題の準最適解を 求めるため[78,141]、あるいは、データベース検索の効率化の ため[160]等にも利用できる。クラスター分析は、「柔らかな情報処 理」を実現する際の基本的な道具として、今後もさらに多くの問題に対して直 接的あるいは補助的に使われると思われる。

本章では、まず、最も簡単なクラスタリングの例としてヒストグラムの分割問題につ いて考察する。これは、例えば、濃淡画像を対象領域と背景に分離するためのしきい 値を選定する問題に応用できる。ここでは、この問題を最尤推定の枠組から考察し、 大津が提案した判別および最小２乗基準に基づくしきい値選定法 [126,127,137]と Kittler らの最小誤差しきい値選定法 [70] を統一的に取り扱えることを示す。これらの手法は、ダイナミッ クプログラミングを用いて多値化（多クラス）の問題へ拡張することができる。それ は、学習用のデータに基づく１次元のデータの最適量子化器の設計法とみなすことが でき、データ圧縮における最も基本的な手法のひとつとなる。第６章では、それをカ ラー画像のデータ圧縮に利用する。

次に、一般の多次元データのクラスタリングのアルゴリズムについて考察する。この 場合のクラスタリングアルゴリズムは、似たもの同士を併合していくつかのグループ にまとめて行く階層的なクラスタリング (hierarchical clustering method) と、似 たものが結果的に同じグループに入るように集合を分割する非階層的クラスタリング (non-hierarchcal clustering method) とに大別して考えることができる。ここでは、 階層的クラスタリングのアルゴリズムをクラスター間の類似度をヒープに蓄えること により高速化する方法を提案する。ヒープを用いることにより、デー タ数 $N$ に対して、$O(N^2)$ の記憶領域が必要となるが、計算時間は従来法の $O(N^3)$ から $O(N^2\log(N))$ に高速化される。そのため従来法に比べより多くの 対象のクラスタリングが可能となる。

最後に、データが逐次的に与えられるような場合のクラスタリングアルゴリズムにつ いて考察する。ここでは、データを１回だけ処理して２乗誤差が最小となるように各 クラスターの代表ベクトルを決定するアルゴリズムを提案する。ここでも、階層的ク ラスタリングの高速化と同様にヒープを用いてアルゴリズムを高速化する。このアル ゴリズムは、例えば、データ圧縮のための適応的ベクトル量子化に応用できる。