Rubyで書くユークリッド距離とピアソン相関(NArray編)

これまでのコードは標準ライブラリだけで書いてきました．
が，もうちょっと速くできないものかと思い，調べてみたところNArrayというGemがあることがわかりました．
(Rubyの数値計算ではおなじみらしいですね...)
今回はこのNArrayを使って，高速化してみようという話です．

NArrayとは

一言で言うと，行列演算をCで書かれた拡張ライブラリを使って一気に計算してくれるものです．
スピードもさることながら，行列演算をすっきり記述できるのも大きなメリット．
今回は基本的な使い方しかしていませんが，使いこなせばもっと色々できそうです．
詳しくは「Numerical Ruby NArray」や「Ruby Library Report 【第 5 回】数値計算と可視化」を読んでみてください．

では，早速インストール．

% sudo gem install narray

NArray版ユークリッド距離とピアソン相関

母体となる部分は変えずに，NArrayを利用するところだけを書き換えるので，
これまでに作成したRecommenderクラスを継承したFastRecommenderクラスを作ります．
あとは，行列演算しているところを書き換えるだけ．
ちなみにNArray#sumはFloatで返してくれるので，型変換をしなくてもそのまま計算結果が使えます．

require 'rubygems'
require 'narray'
require 'recommender'

module My
  class FastRecommender < Recommender
    def get_euclidean_similarity(critics, person1, person2)
      movies = critics[person1].keys & critics[person2].keys
      return 0 if movies.empty?

      critics_person1 = NArray.to_na(movies.map { |movie| critics[person1][movie] })
      critics_person2 = NArray.to_na(movies.map { |movie| critics[person2][movie] })

      # 映画ごとの批評差を求める
      distances = (critics_person1 - critics_person2) ** 2
      # 批評差の総和を正規化して返す
      normalize(distances.sum)
    end

    private

    #
    # ピアソン相関定義
    #
    def get_pearson(array_x, array_y)
      x = NArray.to_na(array_x)
      y = NArray.to_na(array_y)
      
      n = x.size
      sum_x = x.sum
      sum_y = y.sum
      sum_x_square = (x ** 2).sum
      sum_y_square = (y ** 2).sum
      sum_xy = (x * y).sum

      numerator = sum_xy - (sum_x * sum_y.quo(n))
      denominator = sqrt(
        (sum_x_square - (sum_x ** 2).quo(n)) * (sum_y_square - (sum_y ** 2).quo(n)))
      
      denominator == 0 ? 0 : numerator.quo(denominator)
    end
  end
end

実行結果

まずは，値がこれまでと同じになるか確認してみましょう．

recommender = My::Recommender.new
fast_recommender = My::FastRecommender.new

puts recommender.get_euclidean_similarity(critics, 'Lisa Rose', 'Gene Seymour')
puts fast_recommender.get_euclidean_similarity(critics, 'Lisa Rose', 'Gene Seymour')
puts '-----'
puts recommender.get_pearson_correlation(critics, 'Lisa Rose', 'Gene Seymour')
puts fast_recommender.get_pearson_correlation(critics, 'Lisa Rose', 'Gene Seymour')

いざ，実行!

% ./fast_recommender.rb
0.148148148148148 # ノーマル版ユークリッド距離
0.148148148148148 # NArray版ユークリッド距離
-----
0.39605901719067 # ノーマル版ピアソン相関
0.39605901719067 # NArray版ピアソン相関

大丈夫ですね．

今度はどれくらい速くなったか計ってみます．

require 'benchmark'
Benchmark.bm(16) do |x|
  x.report('normal_euclidean') {
    10000.times { recommender.get_euclidean_similarity(critics, 'Lisa Rose', 'Gene Seymour') }
  }
  x.report('narray_euclidean') {
    10000.times { fast_recommender.get_euclidean_similarity(critics, 'Lisa Rose', 'Gene Seymour') }
  }
  x.report('normal_pearson') {
    10000.times { recommender.get_pearson_correlation(critics, 'Lisa Rose', 'Gene Seymour') }
  }
  x.report('narray_pearson') {
    10000.times { fast_recommender.get_pearson_correlation(critics, 'Lisa Rose', 'Gene Seymour') }
  }
end

いざ，実行!

% ./fast_recommender.rb
                      user     system      total        real
normal_euclidean  1.210000   0.000000   1.210000 (  1.211600) # ノーマル版ユークリッド距離
narray_euclidean  1.060000   0.010000   1.070000 (  1.071124) # NArray版ユークリッド距離
normal_pearson    2.090000   0.010000   2.100000 (  2.102502) # ノーマル版ピアソン相関
narray_pearson    1.280000   0.000000   1.280000 (  1.285789) # NArray版ピアソン相関

ユークリッド距離では13%，ピアソン相関では63%速くなりました．
演算量が増える処理ほど速くなっています．