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 ～5.5　Fuzzy Clustering～ 院生ゼミ ‘04年5月18日（火曜日） 谷津 哲平

2 Fuzzy Clustering Fuzzy Clustering の概念
伝統的なクラスタリング手法では，パーティションを発生させる.　　　　　⇒各パターン（個体）は唯一の１個のクラスタに属する ファジィクラスタリングでは，帰属度関数（membership function）を使って,　各パターンを全てのクラスタに関連付ける　 Zadeh [1965]

3 Hard vs. Fuzzy Y X 3 2 5 １ 4 7 9 8 6 H2 H1 Hard Clustering

4 Hard vs. Fuzzy F1 Y X 3 2 5 １ 4 7 9 8 6 F2 H2 H1 Fuzzy Clustering

5 Membership value 帰属度（メンバシップ値） ↓ （ i, μi） ： （ i 番目の個体, その帰属度 )
・各クラスタへの帰属性の度合い ・各個体において,全てのクラスタに対する帰属度の合計は「１」 ↓　（ i, μi） ：　（ i 番目の個体, その帰属度 ) F1 = { (1,0.9), (2,0.8), (3,0.7), (4,0.6), (5,0.55), (6,0.2) , (7,0.2), (8,0.0), (9,0.0)} F2 = { (1,0.0), (2,0.0), (3,0.0), (4,0.1), (5,0.15), (6,0.4) , (7,0.35), (8,1.0), (9,0.9)}

6 Membership value F1 Y X 3 2 5 １ 4 7 9 8 6 F2 Fuzzy Clustering 0.2 0.35
0.0 0.6 0.1 0.0 1.0 0.9 0.0 0.0 0.9 0.2 0.4 0.8 0.0 0.55 0.15 Fuzzy Clustering 帰属度の最も大きい値のクラスタに属させることでハードに変換できる 例）　ある個体 ｘi がクラスタ ｃk に属するなら uik=１，属さないなら uik=０

7 Fuzzy Clustering Algorithm
評価関数 N:個体数　K:クラスタ数　 U ： 帰属度行列．N × K の行列 uij ：U の要素．個体 ｘi のクラスタ ｃｊ に対する帰属度を表す xi : i 番目の個体　 ck : k 番目のファジィクラスタ中心　

8 Fuzzy Clustering Algorithm
Step1　帰属度行列 U によって，ファジィパーティションの 初期値を選ぶ Step2　U を使って評価関数の値を求める Step3　U の著しい変化がなくなるまで，Step2を繰り返す E2の値を小さくしていく N:個体数　K:クラスタ数　U:帰属度行列　ｘ：個体　c:クラスタ中心

9 Fuzzy c-means (FCM) ＜FCM＞ 1961 Ruspini : fuzzy set theory を初めて適用
1981 Bezdek : FCMアルゴリズムの一般化 1992 Dave : fuzzy c-shell と 楕円境界の検出の提示 ＜FCM＞ ・最もポピュラーなファジィクラスタリング手法 ・hard k-means よりも局所的な最小値を避けることが優れている ・二乗エラー基準の局所的な最小値に集めることができる