![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
小澤?
情報理論と統計力学に基づく新しいクラスタリングアルゴリズムを導出し、これはスケールを組み込んだ唯一のアルゴリズムである。
また、クラスタリングにクラスタ独立性という新しい概念を導入する。
クラスタ中心は熱力学的自由エネルギーの局所極小値に対応し、これは1パラメータ非線形写像の固定点として同定される。
このアルゴリズムは、系を融解してスケール空間にクラスタの木を生成することで機能する。
融解はまた、クラスター密度、クラスターの大きさ、楕円体の形や向きのばらつきに対して鈍感である。
このアルゴリズムを、シミュレーションデータと、作物識別のための12の属性を持つ農業用地の合成開口レーダー画像の両方でテストし、成功した。
1.はじめに
クラスタリングは、観測データの分布に関する先験的知識が利用できない多くのアプリケーションで見られる重要な問題である(Duda and Hart 1973; Jain and Dubes 1988)。
簡単に言うと、与えられたデータセットをいくつかのコンパクトなグループに分割することが目的である。
各グループは、測定値中の明確なカテゴリの存在を示す。様々な分野で探索的データ分析に広く使用されている。
そのため、文献は長年にわたって多くの異なる分野に広がっている。それぞれの貢献を個別に引用することはほとんど不可能である。
初期のアルゴリズムの一つはLloyd(1982)によって考案され、後にLindeら(1980)によってベクトル量子化のために拡張された。
パターン認識では、ISODATAアルゴリズム(Ball and Hall 1967)とその逐次版である k-meansクラスタリング・アルゴリズムがある。
その逐次版であるk-meansクラスタリング・アルゴリズムが広く使われてきた。
他のアルゴリズムとしては、ファジィ技法（Ruspini 1969; Bezdek 1981; Gath and Geva 1989; Rose et al. 1990）や、凝集法や分割法（Wishart 1969参照）などの階層技法がある。
しかし、これらのアルゴリズムにはいくつかの難点がある：
(a)初期化に非常に敏感であること、(b)データに重複したクラスタが含まれる場合、性能が低いこと、(c)クラスタ形状、クラスタ密度、クラスタサイズのばらつきを扱えないこと。
最も緊急な問題は、クラスタの妥当性基準がないことである（Ekzdek 1981）。
すべてのアルゴリズムは、データに自然なクラスターが存在しない場合でもクラスターを作成する傾向がある。
本論文では、クラスタリング問題の基本的な見方を検討し、情報理論と統計力学に基づいた新しいアルゴリズムを導き出す。
我々はクラスタリングを熱力学的系の加熱と同定し、スケール空間における階層的クラスタリングを生じさせる。
融解はまた、クラスタ密度、クラスタサイズ、クラスタ形状（楕円体）のばらつきを説明することができる。
このアルゴリズムは、シミュレーションデータと、作物識別のための12の属性を持つ農地の合成開口レーダー（SAR）画像の両方でテストされ、成功を収めた（Wong et al.1992; Wong and Posner 1992）。
この論文の主な貢献は、情報理論、熱力学、非線形力学からの学際的アプローチが、効果的なクラスタリングと関連する最適化問題に適切な定式化を提供できることである。
2.スケールとクラスターの独立性
直感的には、クラスターの数はデータを見るスケールによって変わる。非常に粗いスケールでは、データセット全体がクラスターとなるが、非常に細かいスケールでは、すべてのデータがそれ自体クラスターとなる。スケール空間の考え方は古くからあるが（Gabor 1946; Koenderink 1984）、他のクラスタリング手法ではスケールは利用されていない。
Wong（1992）は 「クラスターの独立性 」という概念を導入した。これを説明するために、複数の人が同じデータとクラスターに関する同じルールを与えられた状況を考えてみよう。
それぞれが、クラスターが見つかったらやめるように言われる。もし彼らがコミュニケーションを取らなければ、クラスターの割り当てが独立していることは明らかである。
クラスターが本当に存在するのであれば、その情報はデータ自体に存在するはずである。
スケールの概念は、クラスター中心に近いデータ点はより多くの情報を与え、遠いデータ点はより少ない情報を与えることを意味する。
これは、データ点がクラスターの位置を明らかにするコストを割り当てることで実現できる。
クラスタを頑健にするためには、情報をデータ間で分散させる必要がある。
全データ点からのクラスター決定への寄与を確率分布として扱うと、この確率分布は線形コスト制約の下でエントロピーが最大になるように選択されるべきであることを意味する Uaynes 1957）。
