kansiho's memo

ruby, python, javascript. Rails, wordpress, OpenCV, heroku...

文章類似度判定アルゴリズムとrubyでの実装例(1)n-gram, Jaccard Similarity

n-gram

n-gramは、フランス語や日本語や大阪弁といった、人が自然に使う言語「自然言語」で記述された文章の特徴を定量的に分析するために開発された手法。「N文字インデックス法」ともいう。

ある文章の中に、ある文字の並びが何回出現したか、をカウントするもの。

この方法のメリットは、言語に依存しないところ(たとえば形態素解析なら、言語ごとの特徴をあらかじめ入れたMeCabのような解析器がいる)。

n-gramのnは、文字を切り出す、決まった数を表す。たとえば「吾輩は猫である」。 3-gramなら

我輩は
 輩は猫
  は猫で
   猫であ
    である

というように、5個の3-gramになる。 この時、出来上がった3文字をそれぞれセグメントと呼び、3文字ずつの集合を、3-gram分布という。

今回の解析対象は7文字であったので、7-(n-1) = 7-2 = 5 個のセグメントをもつ3-gramp分布ができた。

このように先頭から一個ずつ切り出していくわけなので、N-gram では一方の文書から要素を取得して、それぞれの要素がもう一方の文書にあるかを調べるための計算量は O(n2) となる。

Ruby で実装(n=3のTrigram)

String クラスのオープンクラスとして作った。もっと短くできるのではあるけど…わかりやすさ重視で。

class String
  def trigram
    segments = []
    seg_count = self.size - 2 # 3gram なので2を引けばいい
    seg_count.times do |i|
      segments.push(self.chars[i, 3].join)
    end
    return segments
  end
end

str = '我輩は猫であるー!'
print str.trigram

実行結果は以下のようになる。

f:id:serendipity4u:20170801220456p:plain (ちなみにRuby on Railsアプリに組み込む場合、config/initializers/string.rb がオープンクラスを置くのにおすすめな場所だそうです。)

類似度を計算してみる

さっきのメソッドを使って、3-gramで、二つの文章の類似度を計算してみる。 3-gramの場合、重複するセグメントの数を、セグメントの全体数で割ったものが類似度になる。

str1 = '我輩は猫であるー!'
str2 = '我輩は猫になりたい'

で比較してみようとおもう。

class String
  def trigram
    segments = []
    seg_count = self.size - 2 # 3gram なので2を引けばいい
    seg_count.times do |i|
      segments.push(self.chars[i, 3].join)
    end
    return segments
  end
end

str1 = '我輩は猫であるー!'
str2 = '我輩は猫になりたい'

print 'str1'
print str1.trigram

print 'str2'
print str2.trigram

def calc_similarity(str1, str2)
  duplicate_num = (str1.trigram & str2.trigram).size
  sum_num = (str1.trigram + str2.trigram).uniq.size
  return (duplicate_num.to_f/sum_num.to_f)
end

print "\n類似度:" , calc_similarity(str1, str2)

わーい!類似度0.1666666666666666だ〜!

となるのもつかの間。 もっと高くてよくないか、という思いが…。

語尾だとか、「我輩は猫」という漱石の言い回しのニュアンスを引いているところだとか。n-gramは、前述した通り、言語に依存しないのが良いところだけれど、実際は「我輩」「猫」といった名詞レベルの特徴語を考えた方が直感的な類似度に近づくわけで…。

こういうのを、どしたらいいかなあというのを今後書いてみたいと思う。

Jaccard Similarity

ついでに、集合間の類似度である Jaccard 係数というものをメモしておく。 これは共通要素の割合を求めるもので、文章間で使う時には、

(文1 と文 2 両方に共通する単語の数)/(文 1 と文 2 の重複を取り除いたときの単語の数)

と単語単位で考える。

ではどう単語に分割するか…

wordnetなど色々ありますが、今回はMeCabでやります

こちらを参考にMacにインストー

qiita.com

railsアプリで使えるようにするためにMeCabバインディングのための gem nattoを追加。

pry(main)> mecab = Natto::MeCab.new
=> #<Natto::MeCab:0x007f86d876cd50 @model=#<FFI::Pointer address=0x007f86de378ea0>, @tagger=#<FFI::Pointer address=0x007f86de37ac80>, @lattice=#<FFI::Pointer address=0x007f86de379bf0>, @libpath="/usr/local/mecab/lib/libmecab.dylib", @options={}, @dicts=[#<Natto::DictionaryInfo:0x007f86d876c1e8 @filepath="/usr/local/mecab/lib/mecab/dic/ipadic/sys.dic", charset=utf8, type=0>], @version=0.996>
[5] pry(main)> puts mecab.parse("我輩は猫である") 
我輩  名詞,一般,*,*,*,*,我輩,ワガハイ,ワガハイ
は 助詞,係助詞,*,*,*,*,は,ハ,ワ
猫 名詞,一般,*,*,*,*,猫,ネコ,ネコ
で 助動詞,*,*,*,特殊・ダ,連用形,だ,デ,デ
ある  助動詞,*,*,*,五段・ラ行アル,基本形,ある,アル,アル
EOS
=> nil

これで単語単位で区切れるようになった。

参考

はじめてのAIプログラミング―C言語で作る人工知能と人工無能

はじめてのAIプログラミング―C言語で作る人工知能と人工無能

d.hatena.ne.jp

gihyo.jp

全文検索 - Wikipedia

https://www.ipsj.or.jp/award/9faeag0000004f4v-att/L-029.pdf

http://www.ipsj.or.jp/sig/os/index.php?plugin=attach&refer=ComSys2015%20%A5%DD%A5%B9%A5%BF%A1%BC%A5%BB%A5%C3%A5%B7%A5%E7%A5%F3&openfile=ComSys_2015_poster_2.pdf

https://kaigi.org/jsai/webprogram/2011/pdf/157.pdf