Data Clustering: A Review
5.8 Evolutionary Approach for Clustering
発表者:吉村 裕一
進化的アプローチ
• 進化的アプローチは自然進化から考え出
された。
• 進化演算子を用いてデータの適切な解答
の集団の数を得る。
進化演算子
• クラスタリング問題は遺伝子内の染色体として表さ
れる。
主な操作演算子
・選択 ・組み換え ・突然変異
それぞれの変形は1または多入力で1または多出力を
得ることができる。
適応度関数が染色体の次世代への生き残りの可能性
を決める。
進化的アルゴリズムの例
(1)遺伝的アルゴリズム
(GA:genetic algorithm)
(2)進化的戦略
(ES: evolutionary strategy)
(3)進化的プログラミング
(EP: evolutionary programming )
遺伝的アルゴリズム
• 使用される演算子
1)選択
適応度関数によって選択を行う
2)交差
組み換え演算子の一種
3)突然変異
ランダムに染色体の一部を変える
交差・突然変異
• 染色体Xは5bitのバイナリ表示
・交差
01!000
01111
11!111
11000
・突然変異
01111
11111
クラスタリングへの適用
• 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!の染色体の種類がある。
交差の注意点
• 二つの良い染色体を交差しても必ずしもよ
い子孫を得ることができるとは限らない。
例:{A,B,C}と{D,E,F}の二つのクラスタに分けられるとき、
染色体は以下の二つが考えられる。
111000
111111
000111
000000
良くない分割になる
クラスタリングに使用する様々な交差手法
• 巡回問題に使用されるpermutation
crossover を使用しクラスタリングの問題を
解く。
• edge-based crossover を使用してクラスタリ
ング問題を解く。
• GAとk-means法の併用
遺伝的アルゴリズムの問題点
• GAの難点は個体数、世代数、交叉や突然変異の
確率などのパラメータの一般的手法が確立されて
いない。
• GAだけでなく、進化アルゴリズムの三つの手法は
その用途に合わせて各パラメータを人間が経験的
に調整する必要があり、その選択によって影響が
出る。
ダウンロード

yosimura3