PowerPoint プレゼンテーション

Data Clustering: A Review
A.K. Jain, M.N. Murty, P.J. Flynn
～5.5 Fuzzy Clustering～
院生ゼミ ‘04年5月18日（火曜日）
谷津哲平
Fuzzy Clustering
Fuzzy Clustering の概念
伝統的なクラスタリング手法では，パーティションを発生させる.
⇒各パターン（個体）は唯一の１個のクラスタに属する
ファジィクラスタリングでは，帰属度関数（membership function）を
使って, 各パターンを全てのクラスタに関連付ける
Zadeh [1965]
Hard vs. Fuzzy
Y
7
3
4
１
2
8
9
6
5
H1
H1 = { 1, 2, 3, 4, 5}
H2 = { 6, 7, 8, 9}
H2
Hard Clustering
X
Hard vs. Fuzzy
Y
F1
7
3
F2
4
１
2
9
6
5
H1
8
H2
Fuzzy Clustering
X
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)}
Membership value
Y
F1
帰属度（メンバシップ値）
7
3
F2
4
１
2
8
9
6
5
・各クラスタへの帰属性の度合い
H2
・各個体において,全てのクラスタ
に対する帰属度の合計は「１」
H1
X
↓ （ 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)}
Membership value
Y
F1
0.2
0.3
0.6
3
0.9
１
0.8 0.0
0.0
8
0.1
0.2
0.55
5
F2
0.0
4
0.0
2
70.35
6
0.4
1.0
0.0
9
0.9
0.15
Fuzzy Clustering
帰属度の最も大きい値のクラスタに属させることでハードに変換できる
X
例）ある個体ｘi がクラスタｃk に属するなら uik=１，属さないなら uik=０
Fuzzy Clustering Algorithm
評価関数
N:個体数 K:クラスタ数
U ：帰属度行列．N × K の行列
uij ：U の要素．個体ｘi のクラスタｃｊに対する帰属度を表す
xi : i 番目の個体
ck : k 番目のファジィクラスタ中心
Fuzzy Clustering Algorithm
Step1 帰属度行列 U によって，ファジィパーティションの
初期値を選ぶ
Step2 U を使って評価関数の値を求める
Step3 U の著しい変化がなくなるまで，Step2を繰り返す
E2の値を小さくしていく
N:個体数 K:クラスタ数 U:帰属度行列ｘ：個体 c:クラスタ中心
Fuzzy c-means (FCM)
1961 Ruspini : fuzzy set theory を初めて適用
1981 Bezdek : FCMアルゴリズムの一般化
1992 Dave : fuzzy c-shell と楕円境界の検出の提示
＜FCM＞
・最もポピュラーなファジィクラスタリング手法
・hard k-means よりも局所的な最小値を避けることが優れている
・二乗エラー基準の局所的な最小値に集めることができる

Download Report