DAY9: 非階層的クラスタリングの3つの手法
Pythonの有名な機械学習用ライブラリであるscikit-learnには様々なアルゴリズムが実装されており、ユーザーは実際に実装しなくても簡単にアルゴリズムを呼び出せるようになっている。とはいえ、原理すら知らずに使うのは危険であり、また自分の目的に適した手法を選択するためにも原理の理解は避けて通れない。今回はscikit-learnに実装されている中から、K-Means, DBSCAN, Mean-shiftの三つの手法を簡単にまとめておくことにする。
なおどのようなアルゴリズムが存在するのか、の一覧はCluster analysis - Wikipedia, the free encyclopediaによくまとまっている。scikit-learnの一覧ページ（2.3. Clustering — scikit-learn 0.17.1 documentation）も参考になるだろう。
1. K-Means
まずは大人気のK-Means...と思ったが大人気のアルゴリズムで情報に溢れているのでここでは説明しない。いつかこのアルゴリズムの背景にある、正規分布の混合分布の話をできればと思う。
2. DBSCAN
気を取り直してDBSCAN選手。
正式名称はDensity-based spatial clustering of applications with noiseであり、密度に基づいたクラスタリングを行ってくれる。applications with noiseとはどのクラスタにも属さない点（ノイズ）を認める、ということだ。
これによって何ができるのかは実際のクラスタリング結果を見てもらった方が分かりやすいだろう。
このように一定以上の密度を持つ連なった領域を一つのクラスタとみなす。灰色の点がどのクラスタにも属さないノイズである。
メリットとしては
ということがあげられる。
一方のデメリットとしては、密度を閾値としてクラスタリングを行うため、
という点がある。
原理
一定の密度以上のつながった領域を一つのクラスタとみなす、というイメージができていればアルゴリズムの原理を理解するのはさほど難しくない。原理および擬似コードはDBSCAN - Wikipedia, the free encyclopediaに分かりやすく説明されている。
クラスタリングの閾値となる密度を定義するため、初期パラメータとしてepsとmin_samplesの2つを指定する。epsが周りの点を探すための半径、min_samplesがcore-pointとみなすための最小の点数である。min-samplesはクラスタとみなすための最小の点数、という意味ではないのだが、最悪そのような理解でDBSCANを使ってもそこまで失敗しないだろう。
もう少し踏み込んだ理解をするためには、core-point, directly-reachable, reachableという概念を知る必要がある。
- 点pがcore-pointであるとは、pから半径epsの超球の中に他の点がmin_samples以上存在するということで、このときpはそれらの点へdirectly-reachableであるという。
- 点qが点pからreachableであるとは、pからqまでdirectly-reachableの関係を推移して到達できる。ということである。
ここで注意したいのがpからqに(directly-)reachableであるからといって、その逆が成り立つとは限らない（対称でない）ということ。
この図でいえば、AからB(C)はreachableであるが、その逆は成り立たない。なぜならcore-pointでない点（B, C）からは一本もdirect-reachableな関係が成り立たないからである。(directly-reachableが矢印で表現されている)
したがって対称性を持たせるためにreachableからもうひとつ上のconnectedという概念を導入する。
- 点pと点qがconnectdであるとは、ある点oが存在して、oからp,qともにreachableである。
こうして定義されたconnectedという関係が成り立つ最大の集合をクラスターとして定義する。
擬似コードはwikipediaのものを参考にされたい。計算量は単純な実装だとになる。ある点pに対して、そのneighborhoodを探索するという行為は高々2回（1回目は起点として呼ばれ、noise判定されたのち、2回目に他の点のneighborhoodとしてクラスタに追加された際）しか行われないからだ。neighborhoodの探索を効率良くやることで
に下げられるようだが、良く分からなかったので今回はパスにしよう。
3. Mean-shift
最後はMean-shift選手。
これもDBSCANと同じく密度を基準に行うクラスタリングであるが、先ほどは一定の密度以上の連続した領域を一つのクラスタとみなしていたのに対し、Mean-shiftでは密度の局所極大値を検出し、局所極大点をベースとしてクラスタを作る、という点が異なる。
DBSCANに対するメリットとしては
- 一定の密度を閾値としない
ということがあげられるだろうか。
原理
scikit-learnで実装されているのは次のような単純な反復による局所極大値検出である。
- 初期値から半径bandwidthの円内にある点の平均座標を求める。
- その平均へ円の中心を移動する
したがってこのアルゴリズムのパラメタは円の半径bandwidthのみということになる。Mean-shiftという名の通り、平均(mean)への移動(shift)を繰り返すことで局所極大値を検出していく。検出された局所極大値の数がそのままクラスタの個数になり、それぞれの点のラベリングは、それぞれの点を初期値とした場合にどの点に収束するかによって行われる。
とはいえ初期値として全てのデータ点を選んで収束するまで試す、というのは少々効率が悪く、そこを効率化してくれるパラメタがseeds、またはbin_seedingだ。seedsとして初期点集合を自分で与えるか、bin_seeding=Trueとして、初期点集合をscikit-learnに自動で選んでもらう、という方法がある。bin_seeding=Trueとした場合は、データ点をbandwidthに基づくサイズのグリッドに切り分け、それぞれから代表点を選んでくれるようだ。
初期点を選抜した場合に、選ばれなかった点のラベルがどうなるかはコードを深追いしていないので分からなかった。おそらく最も近いseedと同じにする、などの仕組みだと思うが、興味がある方はgithubに公開されているコードを追ってみるのも良いだろう。
以上がscikit-learnに実装されている代表的な非階層的クラスタリングの概要になる。次回はこれらの手法を実際のデータに対して適用してみよう。
