Data Clustering: A Review

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

1 Data Clustering: A Review
5.8 Evolutionary Approach for Clustering 発表者：吉村　裕一

2 進化的アプローチ 進化的アプローチは自然進化から考え出された。 進化演算子を用いてデータの適切な解答の集団の数を得る。

3 進化演算子 クラスタリング問題は遺伝子内の染色体として表される。 主な操作演算子 ・選択 ・組み換え ・突然変異
　 主な操作演算子 　　　・選択　・組み換え　・突然変異　　 それぞれの変形は1または多入力で1または多出力を得ることができる。 適応度関数が染色体の次世代への生き残りの可能性を決める。

4 進化的アルゴリズムの例 （1）遺伝的アルゴリズム （GA：genetic algorithm) （2）進化的戦略
(ES: evolutionary strategy) （3）進化的プログラミング （EP: evolutionary programming ）

5 遺伝的アルゴリズム 使用される演算子 1）選択 適応度関数によって選択を行う 2）交差 組み換え演算子の一種 3）突然変異
　　適応度関数によって選択を行う 2）交差 　　組み換え演算子の一種 3）突然変異 　　ランダムに染色体の一部を変える

6 交差・突然変異 染色体Xは5bitのバイナリ表示 ・交差 ・突然変異 01!000 11000 01111 11!111 01111
11111

7 クラスタリングへの適用 N個のオブジェクトをK個のクラスタに分けるとき、K-ary string of length N と表す。
例：101001の二進数の列で表されるA,B,C,D,E,Fがあり、二つ　　　　のクラスタに分割されるとき｛A,C,F}と｛B,D,E}に分けられる。 　　（010110のときも結果は同じになる） K個のクラスタがあるときそれぞれデータのK-partionに一致するようなK!の染色体の種類がある。

8 交差の注意点 二つの良い染色体を交差しても必ずしもよい子孫を得ることができるとは限らない。
例：｛A,B,C}と｛D,E,F}の二つのクラスタに分けられるとき、　　　 染色体は以下の二つが考えられる。 111000 111111 000000 000111 良くない分割になる

9 クラスタリングに使用する様々な交差手法 巡回問題に使用されるpermutation crossover を使用しクラスタリングの問題を解く。 edge-based crossover を使用してクラスタリング問題を解く。 GAとk-means法の併用

10 遺伝的アルゴリズムの問題点 ＧＡの難点は個体数、世代数、交叉や突然変異の確率などのパラメータの一般的手法が確立されていない。
GAだけでなく、進化アルゴリズムの三つの手法はその用途に合わせて各パラメータを人間が経験的に調整する必要があり、その選択によって影響が出る。