疎行列同士のcos類似度計算では、0以外の要素集合に変換すると超速いことに気付いた(Ruby)

すごく初歩的なことだとは思いますが・・・

疎行列同士のcos類似度を計算して、近いものを選択してくるということに取り組んでいました。約5000要素から成るの疎行列が40000程あります。

約40000の行列の内一つをクエリとして、cos類似度が近いもの上位5個を選択するという処理を何も考えずに行ったところ、約60秒も掛かってしまいました。

そこで、疎行列を以下のように変換しました。

[0,0,2,0,6,0,0,0,0,3,0,0,0]

↓

[
  [2,4,9],
  [2,6,3]
]

変換先は二次元の配列になっており、一次元目には0以外から成る要素のindexが、二次元目には、indexに該当する値が入ります。

この変換を行ったうえで、先ほどと同様の処理を行ってみました。以下Rubyでのコードサンプルです。

# vectorsには上記の変換を行った疎行列が約40000格納される
vectors = Marshal.load(File.read(input))

# クエリの行列
input = vectors[id]

# 類似度が上位5個を保存
max_score = Array.new(5, {score: 0, index: 0})

vectors.each_with_index do |vector, index|
  double = vector[0] & input[0]
  score = 0
  double.each do |s|
    score += vector[1][vector[0].index(s)] * input[1][input[0].index(s)]
  end
  score = score.fdiv(Math.sqrt(input[1].reduce(0){|vec, s| vec += s ** 2} * vector[1].reduce(0){|vec, s| vec += s ** 2}))
  max_score.sort! {|a, b| a[:score] <=> b[:score] }
  if max_score[0][:score] < score
    max_score.shift
    max_score.push({score: score, index: index})
  end
end

# 類似度降順に並び替え
max_score.sort {|a, b| b[:score] <=> a[:score] }

今回の処理は、約0.3秒で終了しました。約200倍速度が改善されました。

MinHashとか使えばもっと早くなりそうなので、今度試してみたいです。