"文章の類似度によるレコメンド"をRubyで実現しようとして、色々探しました。実現できそうなGemがいくつか見つかったので試してみたのですが、いずれも問題があって使用を断念しました。なので自分で実装します。
類似度計算のアルゴリズムとしては、TF-IDF Cos類似度推定法を用います。
全体の流れ
- 文章を分かち書き
- 名詞と形容詞以外を除外
- TFIDFの低い単語を除外
- 重複なし単語リストを作成
- 各文章をベクトル化
- 入力文章のベクトルとCos類似度の高いベクトルを持つ文章を探す
目的
具体的な作業目標としては、特定の文章 1件を入力値として与えた場合に、その文章と類似度が高い文章を数件レコメンドしてくれる装置を作成することです。以下のようなイメージでしょうか。
この文章(id = 1)に似ている文章をお勧めして下さい。
↓
その文章(id = 1)と似ているのは、これ(id = 48)と、これ(id = 330)と、 これ(id = 518)ですね。
入力データ
今回は、2chから引っ張ってきたSS(ショートストーリー:二次創作の短編小説のようなもの)を検証データとして用います。アイドルマスターシンデレラガールズ(以下、モバマス)のSSを1000件収集し、一つのテキストファイルとして保存しました。一行に一件のSSが保存されています。SSの文字数は1000～100万文字と、様々です。
形態素解析による文章の分かち書き
日本語を自然言語処理するには、文章を分かち書きする必要があります。以下のような感じです。
"じゃあ、午後もプロデュース活動、頑張りましょう！"
↓
"じゃあ 、 午後 も プロデュース 活動 、 頑張り ましょ う ！"
さらに、文章の特徴づけにおいて意味を持たない部分を取り除くことで、パフォーマンスの向上を試みます。今回は、名詞と形容詞以外の品詞を除外しています。最終的には以下のように文章が分解されます。
"じゃあ 、 午後 も プロデュース 活動 、 頑張り ましょ う ！"
↓
"午後 プロデュース 活動"
分かち書きにはmecabとrubyのmecabバインディングであるnattoを用います。mecab及びnattoのインストールに関して今回は扱いません。以下のような記事を参考にしてください。
それでは、検証データであるSS 1000件を分かち書きしていきます。
require 'natto'
# owakatiメソッドは、inputファイルを読み込み、分かち書きしたうえでoutputファイルに書き出す
def owakati(input, output)
nm = Natto::MeCab.new
open(output, 'w') do |wf|
open_each_ss(input) do |row|
row.split('。').each do |words|
nm.parse(words) do |n|
wf.write(n.surface + ' ') if(n.feature.match(/名詞/) || n.feature.match(/形容詞/))
end
end
wf.write "\n"
end
end
end
owakati('mobamasu_ss', 'wakati_mobamasu_ss')
これで、1000件全てのSSが分かち書きされた状態のファイル "wakati_mobamasu_ss" が作成されました。
出現回数が低い単語を除外
先ほど作成した "wakati_mobamasu_ss" をこのまま使ってもレコメンドシステムは作成できますが、扱う単語数が多すぎるので処理時間が膨大になってしまいます。そこで、それぞれの文章において出現回数が少ない単語を取り除きます。一つの文章の中で100回以上出現する単語もあれば、1回しか出現しない単語もあるわけです。そういった、出現回数が極端に少ない単語は、各文章を特徴づける上で意味を持たないと見なして除外します。
今回は、各文章において出現回数が5回以下の単語を除外します。
def open_each_ss(file)
open(file) do |f|
f.each do |row|
begin
yield row
rescue
p 'invalid string'
end
end
end
end
f = open('wakati_mobamasu_ss_modify', 'w')
open_each_ss('wakati_mobamasu_ss') do ||
array = ss.strip.split(' ')
array.uniq.each do |word|
if array.count(word) < 6
array.delete(word)
end
end
f.puts array.join(' ')
end
f.close
これで、1000件全てのSSが分かち書きされ、なおかつ出現回数が5回以下の単語が除外された状態のファイル "wakati_mobamasu_ss_modify" が作成されました。
重複なし単語リストの生成
次に、SS 1000件全てにおける、重複なしの単語リストを作成します。これは、各文章ごとではなく、1000件全てにおけるリストであることに注意してください。
def open_each_ss(file)
open(file) do |f|
f.each do |row|
begin
yield row
rescue
p 'invalid string'
end
end
end
end
# リストは一次元の配列に格納していく
uniq_word_list = []
f = open('uniq_word_list', 'w')
open_each_ss('wakati_mobamasu_ss_modify') do |ss|
array = ss.strip.split(' ')
array.uniq.each do |word|
if !uniq_list.include?(word)
uniq_list << word
end
end
end
# 各単語をスペース区切りで出力
f.write uniq_list.join(' ')
f.close
これで、全文章における重複なし単語リストである "uniq_word_list" ファイルが作成されました。
各SSの特徴量を表すベクトルを生成
それぞれのSSが、先ほど作成した重複なし単語リストの各単語を、いくつ含んでいるのかを表すベクトルを生成します。今回の例だと、作成した重複なし単語数は約9000単語だったので、9000の要素を持ったベクトルを、各SSごとに生成します。視覚化すると、以下のような感じです。
0 0 0 5 0 3 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 ・・・・・・・(9000要素)
実際にベクトルを作成していきます。
def open_each_ss(file)
open(file) do |f|
f.each do |row|
begin
yield row
rescue
p 'invalid string'
end
end
end
end
uniq_word_list = open("uniq_word_list").read.split(' ')
vec = []
count = 0
open_each_ss('wakati_mobamasu_ss_modify') do |ss|
vec[count] = []
uniq_word_list.each do |word|
words = ss.split(' ')
vec[count] << words.count(word)
end
count += 1
end
# 今回はオブジェクトをダンプして保存
dumped_vec = Marshal.dump vec
File.open("vec.dat", "w") {|f| f.write(dumped_vec) }
ここでは、、各SSの特徴量を持つベクトルが、9000(約) × 1000の二次元配列として生成され、生成されたオブジェクトを "vec.dat" というファイル名でダンプしています。
レコメンドさせてみる
それでは実際にレコメンドさせてみます。以下の例では、656番目のSSと類似度が高いSSを、上位三件表示させています。656に特に意味はありません。適当に選んだ数字です。
require 'matrix'
def open_each_ss(file)
open(file) do |f|
f.each do |row|
begin
yield row
rescue
p 'invalid string'
end
end
end
end
data = File.read("vec.dat")
vectors = Marshal.load data
# 656番目のSSベクトルデータを格納
ss_655_vec = Vector.elements(vectors[655])
max_score = Array.new(3, {score: 0, index: 0})
vectors.each_with_index do |vector, index|
# ベクトルの内積の和を計算し保存
score = ss_655_vec.inner_product(Vector.elements(vector)).fdiv(ss_655_vec.norm * Vector.elements(vector).norm)
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
# 結果を出力
p max_score
結果が以下のように出力されました。
[
{:score=>0.6198680933892068, :index=>519},
{:score=>0.7774411942445159, :index=>225},
{:score=>1.0, :index=>655}
]
656番目のSS(index = 655)と最も類似度が高いのは、当然自分自身です。完全一致なのでscoreが1.0となっています。続いて、226番目(index = 225)、520番目(index = 519)のSSが類似度が高いという結果が出ています。ここで出てきたSSのタイトルを調べると、以下のようになっていました。
index = 655 のタイトル: 幸子「スカイダイビングの次はブラックホールダイビングですって！？」
index = 225 のタイトル: 幸子｢ボクはカワイイ！｣
index = 520 のタイトル: モバP「幸子に新作ゲームを体験してもらう」
いずれも "幸子"というキャラクターがメインのSSであることが、タイトルから伺えます。
同じように、index = 349に対して類似度の高いSSを表示させたところ、以下のようになりました。
[
{:score=>0.7774623545604544, :index=>191},
{:score=>0.7913256530566651, :index=>635},
{:score=>0.9999999999999998, :index=>349}]
index = 349 のタイトル: 美希「お昼寝してたら……いっぱい汚されちゃったの」
index = 635 のタイトル: 美希「あっ！蚊！」ﾊﾟｼｯ
index = 191 のタイトル: P「俺のおにぎり知らないか？」 美希「え？」
こちらは、3つとも"美希"というキャラクターがメインのSSでした。
以上の結果から、"類似度の高い文章をレコメンドする" という目標は、概ね達成できたと言えそうです。
(追記)
行列計算を大幅に短縮する方法に気付いたので、別記事に概要を書きました。
疎行列同士のcos類似度計算では、0以外の要素集合に変換すると超速いことに気付いた
処理速度を改善する
前項までで、類似したSSをレコメンドすることに成功しました。しかし、上記の処理が終了するまでには、約3.7秒かかりました。これではとても実用には耐えません。そこで、処理速度の改善を試みます。
今回は、拡張配列クラスであるNArrayを使います(参考1)。
require 'matrix'
def open_each_ss(file)
open(file) do |f|
f.each do |row|
begin
yield row
rescue
p 'invalid string'
end
end
end
end
data = File.read("vec.dat")
vectors = Marshal.load data
ss_655_vec = NVector[vectors[655]].flatten
max_score = Array.new(3, {score: 0, index: 0})
vectors.each_with_index do |vector, index|
nvector = NVector[vector].flatten
score = (nvector * ss_655_vec).fdiv(Math.sqrt((nvector ** 2) * (ss_655_vec ** 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
p max_score
これで処理が終了するまでの時間を計測したところ、0.71秒となりました。処理速度を 約5倍まで向上させることができました。
最後に
自分は自然言語処理に関しては素人同然なので、至らない部分が多くあったと思います。今回、1000件の文書において類似度によるレコメンドを選択するのに、一回当たり0.7秒の処理時間がかかりました。1000件程度ならこの処理速度で問題ありませんが、文書数が膨大になると、このプログラムでは処理しきれません。何らかの次元削減アルゴリズムを組み込んだり、ベクトル演算の過程を工夫する必要がありそうです。というか、お勧めのGemとかあったら教えてください・・・