洋食の日記

「た・である」調ではなく「です・ます」調で書きはじめれば良かったなと後悔してる人のブログです

RumaleにPower Iterationによる非線形クラスタリングを追加した

はじめに

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つの円をうまくクラスタリングできている。

f:id:yoshoku:20190622084249p:plain

他手法との比較としては、例えば、K-Means法では非線形構造を捉えることができず、半分に真っ二つにしてしまう。

f:id:yoshoku:20190622084454p:plain

Rumaleで実装したPICでは、デフォルトでは類似度にRBFカーネルを用いる。Rumaleで実装したRBFカーネルの式は以下で表される。

 k(\mathbf{x}, \mathbf{y}) = \exp(-\gamma ||\mathbf{x}-\mathbf{y}||^{2})

ハイパーパラメータとして \gammaをもつが、この値をデータに合わせて適切に調整する必要がある。

おわりに

Rumaleのver. 0.12.3では、非線形クラスタリング手法のPower Iteration Clustering(PIC)を実装した。PICは、類似度をもとに低次元表現を求め、その低次元空間でK-Means法を実施することで、非線形クラスタを得る。あわせて、合成データセットを作成するメソッドを追加した。

PICのアルゴリズムでは行列積を繰り返すので、Intel MKLやOpenBLASとともに、Numo::Linalgをインストールすることで高速化ができる。そのあたりはコチラを参考に。

qiita.com