遺伝的アルゴリズムでクラスタリング（GA-clustering）
はじめに
この記事では遺伝的アルゴリズム（Genetic Algorithm; GA）を用いてクラスタリングを行う GA-clustering についてまとめます．
以下の論文を参考にして書いています．この記事になにかおかしい点があれば，この論文を参照してください．
U.Maulik, S.Bandyopadhyay, Genetic algorithm-based clustering technique, Pattern Recog. 33 (2000) 1455–1465
CiteSeerXで読めます (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.1878&rep=rep1&type=pdf)．
また，関連手法としてもっとうまい手法もあります（が，とりあえずはこれを紹介させて欲しい）．
GA-clustering とは
GA-clusteringとは，遺伝的アルゴリズムと K-means 法を組み合わせたクラスタリング手法です．
K-means 法の，局所最適解にハマってしまうことがあるという欠点を，遺伝的アルゴリズムで補おうというアイディアです．
K-means 法
Wikipedia 参照
GA-clustering の流れ
おおまかな流れは基本的な遺伝的アルゴリズムと同じで，初期集団を生成してから評価→選択→交叉→突然変異を終了条件を満たすまで繰り返します．
各個体は，すべてのクラスタの重心を並べた配列とします．
以下，各操作の中身を見ていきます．
初期集団の生成
クラスタリングしたいデータを 個のクラスタにランダムに割り振って，それぞれのクラスタの重心を計算し，個体を生成します．
これを集団の個体数 だけ繰り返し，初期集団とします．
個体の評価
適応度を計算する前に，K-means 法を1ステップ分だけ実行して重心を更新しておきます．
クラスタリングの評価基準として，各クラスタ内の各点と重心の距離の和を定義します．
各クラスタを ，その重心を
とすると，
$$ \mathscr{M}(C_1, C_2, \ldots, C_K) = \sum_{i = 1}^{K} \sum_{\boldsymbol{x}_i \in C_i} || \boldsymbol{x}_i - \boldsymbol{z}_i || $$
はクラスタ
の重心です．
この が小さいほど良いクラスタが得られたと考えます．
したがって，適応度は とします．
選択
ルーレット選択です．
交叉
交叉率 で二点交叉を適用します．
突然変異
突然変異率は とします．
突然変異を， を遺伝子の位置（座標），
を
の一様乱数として，
$$ \begin{align} v \pm 2 \delta v, ~( v \neq 0 ) \\ v \pm 2 \delta, ~( v = 0 )~ \end{align} $$
と定義します． は等確率でどちらかが選ばれます．
実装
ここに置いときます．
わりと汚いですけど，勘弁してくださいな．
（ちなみに，plotのところはmarker_zを使ってあげるとスッキリ書けます．でも，いろいろ試したけど色が気に食わなかったので......）
試しにクラスタリング
適当にデータを作ってクラスタリングしてみました．
個体数200，世代数200，交叉率0.9，突然変異率0.001です．
左が元のデータ，真ん中が GA-clustering によるクラスタリング，右が K-means 法によるクラスタリングです．
K-means 法より GA-clustering のほうが良さげな感じ出てますね．
何回か実行してみるとK-means 法でもいい感じの結果は出ますが，GAの方はほぼ毎回いい感じになるはずです．
