RubyでKL展開

RubyでKL展開をやってみました。KL展開とは、元のパターン分布の特徴をできるだけ保持したまま次元削減を行う手法のことで、今回書いたのは2次元のデータを1次元に落とす例です。

ソースコード

2次元から1次元用に書いてしまったので、それ以外の場合への応用はコードを書き直す必要があります。

require 'matrix'
require 'open3'

# 適当なデータを生成する
def generate(num)
  x = num.times.map { |n| n.to_f + rand(0.0..5.0) }
  y = num.times.map { |n| (1.0/2.0) * n + rand(10.0..30.0) }
  x.zip y
end
patterns = generate(100).map { |x| Matrix[x] }

# 平均ベクトル m
m = patterns.inject(Matrix[[0, 0]]) { |sum, x| sum + x }
  .map { |e| e / patterns.size.to_f }

# 共分散行列 Σ
sigma = patterns.inject(Matrix.zero(2)) do |sum, x|
  sum + ((x - m).transpose * (x - m))
end * (1.0 / patterns.size.to_f)

# Σの上位ひとつの固有値に対する正規直交固有ベクトル
u = sigma.eigensystem.eigenvector_matrix.row(0).normalize

Open3.popen3('gnuplot') do |gp_in, gp_out, gp_err|
  output_file = "./kl_expansion.gif"
  gp_in.puts "set terminal gif animate optimize size 480, 450"
  gp_in.puts "set output '#{output_file}'"
  gp_in.puts "set xrange [0:110]"
  gp_in.puts "set yrange [0:110]"

  patterns.size.times do |i|
    plot = "plot "

    # 得られた1次元空間の軸を表示(青い線)
    plot << "#{u[0] / u[1]}*x notitle lw 2 lc rgb 'blue',\\\n"

    # 全てのパターン(赤い点)
    plot << "'-' notitle pt 7 ps 1 lc rgb 'red'\n"
    patterns.map(&:to_a).flatten(1).each_with_index do |(x1, x2), j|
      if j < i
        mat_a = Matrix[[u[1]], [u[0]]]
        y = mat_a * mat_a.transpose * Matrix[[x1], [x2]]
        plot << "#{y[0, 0]} #{y[1, 0]}\n"
      else
        plot << "#{x1} #{x2}\n"
      end
    end
    plot << "e\n"
    gp_in.puts plot.gsub(/,\\\n$/, "")
  end

  gp_in.puts "set output"
  gp_in.puts "exit"
  gp_in.close
end

処理の流れ

まず初めに適当な2次元上のデータを生成します。

そして、そのパターン集合から平均ベクトルと共分散行列を計算し、今回は1次元への変換なので共分散行列の上位ひとつの固有値に対応する正規直交固有ベクトルを求めます。すると、そのベクトルを列とする行列が変換行列となります。

プロットはなんとなくアニメーションにしたかったので、gemは使わず直接gnuplotを叩く感じにしました。(gemの方ではアニメーションがうまくいかなかったので…)その処理については以下のページを参考にさせていただきました。
GnuplotをRubyから操作

実行結果

図1に示すように、赤い点が元のパターンの集合で、青い線がその集合の分散最大基準によって求められた1次元空間の軸です。実行すると図2のように、元の点を新しい軸上に移していく過程のgifが出力されます。

$ ruby main.rb

 

図1 元のデータ(赤い点)と得られた軸(青い線)

 

 

図2 元のデータが変換される様子 

おわりに

元のデータ生成が適当過ぎてあまりいい例とは言えないかもしれませんが、一応期待通りの結果が得られました。

参考文献

石井健一郎・前田英作・上田修功・村瀬洋 (1998) 『わかりやすいパターン認識』 オーム社