はじめに
Rumaleに、Power Iteration Clustering(PIC)を追加した。PICは、データ間の類似度をもとにクラスタリングする。類似度に、例えばRBFカーネルを選択すると、非線形なデータ分布構造を捉えたクラスタリングができる。
rumale | RubyGems.org | your community gem host
PICはSpectral Clusteringの一種とみなせる。データ間の類似度を保存した低次元表現をもとめ、その低次元空間でK-means法を実行することでクラスタリングをおこなう。低次元表現は、正規化した類似度行列の固有ベクトルから得られるが、このときベキ乗法(power method)を用いて固有ベクトルを求める(ことからpower iteration clusteringと呼ぶのだろう)。求める固有ベクトルは最大の固有値に対応するものだけである。シンプルなアルゴリズムで、非線形クラスタリングを実現できることから、Rumaleでも実装した。
使い方
Rumaleはgemコマンドでインストールできる。Numo::NArrayに依存している。データのplotにNumo::Gnuplotを使いたいので、これもインストールする。※別途gnuplotをインストールする必要がある
$ brew install gnuplot $ gem install rumale numo-gnuplot
オマケというか、ver. 0.12.3から合成データセットを作成するメソッドを追加した。コレをクラスタリングしてプロットする。
require 'rumale' require 'numo/gnuplot' # 合成テストデータを作成する. samples, labels = Rumale::Dataset.make_circles(500, factor: 0.4, noise: 0.05, random_seed: 1) # samples, labels = Rumale::Dataset.make_moons(500, noise: 0.05, random_seed: 1) # Power Iteration Clusteringでクラスタリングする. # 類似度にはRBFカーネルを用いる. gammaはRBFカーネルのパラメータで調整が必要となる. # ※独自の類似度を与えることもできる. pic = Rumale::Clustering::PowerIteration.new(n_clusters: 2, gamma: 32.0, random_seed: 1) clabels = pic.fit_predict(samples) # 結果をGnuplotで出力する. x = samples[true, 0] y = samples[true, 1] plots = clabels.to_a.uniq.sort.map { |l| [x[clabels.eq(l)], y[clabels.eq(l)], t: l.to_s] } Numo.gnuplot do set(terminal: 'png') set(output: 'circles.png') unset(:xtics) unset(:ytics) unset(:border) plot(*plots) end
これを実行すると以下の画像を得られる。2つの円をうまくクラスタリングできている。
他手法との比較としては、例えば、K-Means法では非線形構造を捉えることができず、半分に真っ二つにしてしまう。
Rumaleで実装したPICでは、デフォルトでは類似度にRBFカーネルを用いる。Rumaleで実装したRBFカーネルの式は以下で表される。
ハイパーパラメータとしてをもつが、この値をデータに合わせて適切に調整する必要がある。
おわりに
Rumaleのver. 0.12.3では、非線形クラスタリング手法のPower Iteration Clustering(PIC)を実装した。PICは、類似度をもとに低次元表現を求め、その低次元空間でK-Means法を実施することで、非線形なクラスタを得る。あわせて、合成データセットを作成するメソッドを追加した。
PICのアルゴリズムでは行列積を繰り返すので、Intel MKLやOpenBLASとともに、Numo::Linalgをインストールすることで高速化ができる。そのあたりはコチラを参考に。