Data Clustering: A Review

Presentation on theme: "Data Clustering: A Review"— Presentation transcript:

1 Data Clustering: A Review
A.K. Jain, M.N. Murty, P.J. Flynn 院生ゼミ ‘04年6月1日（火曜日） 新納浩幸

2 本日の私の担当 第5章： 5.7 Artificial Neural Networks for Clustering
ニューラルネットワーク（ＮＮ）を 用いたクラスタリング

3 ＡＮＮ （あるいは NN ） Artificial Neural Network の略． NN と略すことも多い．
この30年間，ＮＮ を識別やクラスタリングに 用いる研究が活発に行われてきた． ポイントとなる重要な特徴 （１） NN は数値ベクトルを扱う．結果，パターンは数値 ベクトルで表現しなければならない． （２） NN は並列かつ分散型の構成をもつ （３） NN はノード間の適切な重みを学習する． 重みの学習によって，パターンの正規化と 特徴選択を行っているとみなせる

4 ＮＮ（for 識別） 入力、 出力 となるような関数 f を推定する学習方法 訓練データ 特徴
＊関数の表現形式がネットワークの重みなので、具体的な 関数の形はわからない ＊ 関数自体の表現力は高く、どんな関数でも表現できる ＊ 分類問題の解決は１つの応用、他、様々な応用がある ＊ 多くの研究成果があるがまだ未知な部分も多い

5 関数の表現形式 入力ユニット j から 中間ユニット k への重み 中間ユニット i から 出力ユニット j への重み
から中間層の各ユニットの 入出力をつくり、そこから をつくる。結局、関数を作っている。 入力ユニット j から 中間ユニット k への重み 中間ユニット i から 出力ユニット j への重み

6 ＮＮ（for クラスタリング） （１） SOM を例にして， 入力例，，，動物が13次元のベクトルで表現されている

7 ＮＮ（for クラスタリング） （２） 出力 似ているものが集まった形で平面状にマップされる

8 ＮＮ（for クラスタリング） （３）

9 競合学習 パターンが Ｎ 次元ベクトルとすると， 出力層の各ノードはＮ次元ベクトルに対応している．
入力パターンに対して最も距離の近い出力層のパターンが 選ばれ，その近傍が入力パターンに近づくように更新される

10 代表的な NN の例 ＬＶＱ （Learning Vector Quantization: ベクトル量子化）
SOM （Self-Organizing Map: 自己組織化マップ） ART （Adaptive Resonance Theory model ） ほとんど同じ手法 ネットワークは単一層の構成 入力層から入るパターンが出力層で想起される 入力層と出力層の間の重みが学習

11 クラスタリングとの関係 学習，重みの更新の方法，が古典的なクラスタリング手法 と非常に似ている．
K-means と LVQ との関係 [Pal el al. ’93] ART モデルの学習アルゴリズムは leader クラスタリング アルゴリズムとの関係 [Moor ’98]

12 SOM 多次元のベクトルの集合を直感的にわかりやすい 2次元上の点にマップする． LVQ や 音声認識で成功した 欠点
＊初期の重みが適切に選ばれないと部分的に最適な 分割しか得られない． ＊収束の条件が，さまざまなパラメータで制御される． そのため，ある入力に対して異なる繰り返し回数では 出力が異なる． Stability (安定性) 問題

13 安定性と柔軟性 システムが安定 訓練データ内のパターンは，ある繰り返し回数 以上の学習に対しては，同じ識別結果になる
Plasticity (柔軟性) の問題，とも関連深い 新しいデータに対して適応力がある 安定性は，繰り返しに従って，学習の割合が ０ になることを 意味し，これは柔軟性に影響を与える．

14 ＡＲＴ モデル 安定かつ柔軟である 欠点 ＊データの与えられる順序に依存して出力が変化する
＊ART によって作られたクラスターの大きさと数は Vigilance threshold の値に依存する 新しいパターンを既存のクラスのメンバーにするか そのパターンで新しいクラスターを作成するかを 決めるための値

15 その他 SOM と ART は Hypersoherical cluster を探すには 安定 [Hertz et al. ’91]
Hyperellipsoidal cluster を取り出すために，正規化した マハラノビス汎距離を使った2階層のネットワークが提案 されている [Mao and Jain ’94] NN は出力のノード数（クラスの数）を固定している