Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

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

疎行列同士の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とか使えばもっと早くなりそうなので、今度試してみたいです。

EastResident
webの会社でアドテクエンジニア?やってます。しばらくはGCP中心に書く予定。
https://eastresident.hatenablog.com
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away