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だけでなく、進化アルゴリズムの三つの手法はその用途に合わせて各パラメータを人間が経験的に調整する必要があり、その選択によって影響が出る。