クラスター解析のアルゴリズムについて

例えば僕の研究だと粒子が沢山あって気液平衡の相共存状態ならば当然のことながら気体部分と液体部分が識別されるべきである。それはどのように判別したらよいであろうか?
例えば、粒子同士がある距離以内であったらその部分は液体、孤立してる粒子は気体というふうに液体クラスターを識別していくことを考えよう。
これを数理的に考えるにはネットワークを考えるのが良い。頂点が沢山あり、その頂点同士が線(非有向成分)で結ばれているというモデルである。データとしては2つの頂点が結ばれているということを表すデータが辺の数だけあるとなっている。(これは同値類解析と同じ問題と思って良いのですよね…?)






それではどうやってつながっている頂点同士を把握すれば良いのか考えよう。

まずすべての頂点に1,2,3...と順番をつけて名前をふる。またグループ番号を名前と同じものにする。最初はすべての頂点は孤立したグループとなっているが、順々にペア同士を繋げていく。基本的にグループ内頂点の最小番号をグループ番号とすることをゴールとする。

次に頂点ペアを順に見ていく。両方の頂点についてグループ番号をみる。グループ番号の頂点をみてまたそのグループ番号をみる。これを繰り返し続けていってグループ番号=名前の頂点まで飛ぶ。そしたらその頂点の名前をペア同士で比べて、順番の早い方をとって頂点ペア両方のグループ番号をそれに書き換える。

最後にまたすべての頂点を順番の早い方から順にみていく。各頂点でグループ番号をみて、先程のようにその頂点に飛んで、その頂点のグループ番号の頂点に飛んで…を繰り返し、たどりついた頂点の名前にもとの頂点のグループ番号を書き換える。

これで終了のようです。お疲れ様でした。グループ番号がクラスター(同値類)を識別する番号になります。





頂点に対してつながってる点が列挙されている場合でも似たように書く事ができます。割愛しますが。