2012年7月11日水曜日

文章のコサイン類似度

文章間の類似度を測るには色々な方法があるが、ここではbag-of-wordsなる単語ベクトル同士のコサイン類似度(cosine similarity)を計算するカンタンな例を記しておく。


まずコサイン類似度であるが、要はベクトル同士のなす角の大きさをコサインで表現し、1に近ければなす角度が小さいので2つのベクトルはお互いに似ているし、0に近ければぜんぜん似てない、ということである。


bag-of-wordsというのは形態素解析された(単語に分割された)文に含まれる単語を要素とするベクトルである。例えば、以下の文章の場合は、


文1:「人生で起こることは、すべて、皿の上でも起こる」 (三谷幸喜)


文ベクトル1 = ("人生", "で", "起こる", "こと", "は", "、", "すべて", "、", "皿", "の", "上", "で", "も", "起こる", "。")


といった具合である。実際には「で」とか「は」とか「の」とか「、」とかこういう類のものはあまり参考にならないことが多いので排除して


v1 = ("人生",  "起こる", "こと",  "すべて", "皿",  "上")


といった形にしてから類似度を計算するのが好ましいだろう。(単語の選定はtf-idf等を参考にしたりする)
さて、次の文章と先の文章のコサイン類似度を計算することを考える。


文2:「もうすぐ、あなたの人生の上に起こる、驚くべきこと

v2 = ("もうすぐ", "あなた", "人生", "上", "起こる", "驚く", "べき", "こと")

次に、文ベクトル1と文ベクトル2は次元が違うので、次元をそろえた表現ベクトルを用意する。例えば両文に登場した単語("人生",  "起こる", "こと",  "すべて", "皿",  "上", "もうすぐ", "あなた",  "驚く", "べき")の有無を1or0で表現したベクトルを作る。


v1' = (1, 1, 1, 1, 1, 1, 0, 0, 0, 0)

v2' = (1, 1, 1, 0, 0, 1, 1, 1, 1, 1)

このとき

Cosine Similarity = v1'・v2' / (|v1'|*|v2'|) = 4 / (sqrt(6) * sqrt(8)

= 0.58

とざっくり計算できる。この方法では類似度は相対的に判断するしかなさそうだが、0.5を越えればいくらか文章間に共通性はありそうである。かなり簡易な指標だが、重要度に応じて単語に重み付けを行う等、他の技と組み合わせるとより威力を発揮する。

コサイン類似度を返す超シンプルpythonコード例:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import mecabsplitter as splitter
import math, sys

def cossimilarity(s1, s2):
        w1 = splitter.wordsvector(s1)
        w2 = splitter.wordsvector(s2)
        intersec = set(w1).intersection(set(w2))
        return len(intersec)/math.sqrt(len(w1))/math.sqrt(len(w2))

if __name__ == '__main__':
        argvs = sys.argv
        argc = len(argvs)
        if (argc < 2):
                print 'Script needs at least 2 sentences for maximum cosine similarity calculation'
        
        s0 = argvs[1].decode('utf-8')
        maxcossim = 0
        for arg in argvs[2:]:
                s = arg.decode('utf-8')        
                cossim = cossimilarity(s0, s)
                print cossim
                if (cossim > maxcossim):
                        maxcossim = cossim
                        
        print maxcossim

形態素解析ライブラリmecabを使って文章を単語に分割し、特定の種類の単語だけベクトルに入れて返すmecabsplitter.py:

#!/usr/bin/python
# -*- coding: utf-8 -*-

#http://mecab.googlecode.com/svn/trunk/mecab/doc/posid.html

import MeCab

filteredPOS = [10, 11, 12, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]

def wordsvector(sentence):
        sentence = sentence.encode('utf-8')
        words = []
        tagger = MeCab.Tagger('')
        node = tagger.parseToNode(sentence)
        while node:
                # It is possible to filter out words based on posid
                if node.posid in filteredPOS:
                        words.append(node.surface)
                        #print node.surface + ' posid: ' + str(node.posid)
                node = node.next             
        
        return words
        
def featurevector(sentence):
        words = wordsvector(sentence)
        return dict([(w, 1) for w in words])

これをコマンドラインで実行した結果:

$ python cosinesimilarity.py "疲れた脳を職場でリフレッシュする方法" "疲れている脳が職場でリフレッシュする方法を探す目的"
0.816496580928

となり、まぁお互い似てる的なノリになる。
機会があればベクトル空間モデルのdimension reductionについてまた書こう。

0 件のコメント:

コメントを投稿