集合とかベクトルの類似度の計算のメモ

↑この辺りの記事を見て、集合とかベクトルの類似度の計算の記事を下書きのまま放置していたことを思い出したので書き上げた。

類似度の計算のコードを書いたのでそれを載せるだけにしようかと思ったのですが、知っている人にしか伝わりそうにないので自然言語処理でよく使う話の概要だけでも書いときます。

導入

自然言語処理の分野では単語の意味を比較するときに、ある単語の周り(文脈)に出てきた単語のベクトル(文脈ベクトル)の類似度を計算することがある。
これは「ある単語の意味はその周囲に出現する単語によって特徴づけられている」という仮説に基づいていて、文脈ベクトルが似ていれば似たような意味、似たような状況で使われる単語が多いということが言えるからである。

Distributional semantics - Wikipedia, the free encyclopedia

以下のように「ご飯」などの食べ物系の単語の周りには「食べる」という単語が出てきやすい、という例で納得してもらえるとありがたい。

帰宅してご飯食べて風呂った

2011-12-12 21:49:42 via twicca

生協のカレーに飽きたから晩ご飯は家で食べよう

2011-05-13 18:47:47 via Tween

文脈ベクトルの作り方

文脈ベクトルの作り方には様々なやり方があるらしいですが、メインではないのであまり触れない。
基本的にはテキストデータの中で、対象とする単語の周りnの範囲(文脈窓)に登場した単語を対象とする。
ツイッターなどの短い文の場合には1文や1ツイートまるごとを対象にしてもいいかもしれない。

この時品詞による限定や係り受け関係による限定などを行うこともある。

文脈ベクトルの値

文脈窓に出現した単語についてどのような値を持たせるのかというのも様々なやり方がある。

一番単純には出現頻度を使えば良い。
これに対しても確率値にしたり、対数をとったりいろいろな工夫が考えられる。

またPMI(Pointwise Mutual Information)などのより共起性を考慮したものを使っている場合もある。

Pointwise mutual information - Wikipedia, the free encyclopedia

簡単な例

先ほど例として上げたツイート内すべてを文脈とし、名詞と動詞の原形のみを数えた場合「ご飯」の文脈ベクトル(頻度)は以下のようになる。

v1 = {'帰宅': 1, '風呂': 1, '生': 1, '協': 1, '晩': 1, '家': 1, '食べる': 2, '飽きる': 1, 'する': 1}

データ量が圧倒的に少ないですが「食べる」や「飽きる」など「ご飯」に関係ありそうな単語が含まれてることはわかると思います。

帰宅してご飯食べて風呂った

2011-12-12 21:49:42 via twicca

生協のカレーに飽きたから晩ご飯は家で食べよう

2011-05-13 18:47:47 via Tween

同様に「夕食」についてもベクトルを作っておきます。

v2 = {'帰宅': 1, '思う': 1, '食べる': 1, 'おかず': 1}

帰宅して遅い夕食なう

2012-07-14 23:16:28 via twicca

夕食を食べようと思ったらおかずがなかった……

2012-06-27 22:12:28 via twicca

同様に「布団」についてもベクトルを作っておきます。

v3 = {'部屋': 1, '人': 1, '寝る': 2, 'いる': 1, '明らか': 1, '携帯': 1, 'いじる': 1, '原因': 1, '一つ': 1}

@Scaled_Wurm 「布団がない部屋に人が寝ている」

2012-07-02 15:12:39 via web to @Scaled_Wurm

明らかに布団で携帯いじってんのが寝れない原因の一つですよね

2012-03-06 01:51:49 via twicca

類似度の計算

ようやくメインの話です。

上で定めた文脈ベクトルについて類似度の計算を行います。

ユークリッド距離などを使う場合もありますが、比較する文脈ベクトルの長さ(0でない要素の数)が違いすぎると悪影響があるとかないとか。

以下に類似度として使われるものの一部をあげます。

集合に対するもの

それぞれある要素が含まれるかどうかでしか考えない。
基本的には次に紹介する数値に対する類似度のほうが頻度の違いを考慮しているためよさそう。

以下の3つの尺度の分子は共通の要素の数であり、分母が微妙に違うだけである。
Jaccard係数は2つの集合を合わせた集合の要素数、Dice係数は2つの集合の大きさの平均、Simpson係数は小さい方の集合の要素数が分母となっている。

2つの集合を ${X, Y}$ とする。

Jaccard係数

$\frac{|X \cap Y|}{|X \cup Y|}$

def jaccard(v1, v2):
    numerator = sum([c in v2 for c in v1])
    denominator = len(v1) + len(v2) - numerator
    return float(numerator) / denominator if denominator != 0 else 0

Dice係数

$\frac{2 \times |X \cap Y|}{|X| + |Y|}$

def dice(v1, v2):
    numerator = sum([c in v2 for c in v1])
    denominator = len(v1) + len(v2)
    return 2 * float(numerator) / denominator if denominator != 0 else 0

Simpson係数

$\frac{|X \cap Y|}{\min(|X|, \,|Y|)}$

def simpson(v1, v2):
    numerator = sum([c in v2 for c in v1])
    denominator = min(len(v1), len(v2))
    return float(numerator) / denominator if denominator != 0 else 0

数値ベクトルに対するもの

Jaccard係数とDice係数について数値を考慮した場合の式が以下の本に載っていたのでついでに載せておきます。
他の本ではあまり見かけないので、一般的な式かどうかはわかりません……。

Speech and Language Processing: International Version: an Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition

作者: Dan Jurafsky,James H. Martin
出版社/メーカー: Pearson
発売日: 2008/04/29
メディア: ペーパーバック
クリック: 14回
この商品を含むブログ (2件) を見る

2つのベクトルを $x, y}$ とします。

コサイン類似度

$\frac{x \cdot y}{|x|\,|y|}$

import math
def cos(v1, v2):
    numerator = sum([v1[c] * v2[c] for c in v1 if c in v2])
    square = lambda x: x * x
    denominator =  math.sqrt(sum(map(square, v1.values())) * sum(map(square, v2.values())))
    return float(numerator) / denominator if denominator != 0 else 0

追記:2013-12-29
リスト内包表記を使ったほうが速いです

import math
def cos(v1, v2):
    numerator = sum([v1[c] * v2[c] for c in v1 if c in v2])
    denominator =  math.sqrt(sum([v * v for v in v1.values()]) * sum([v * v for v in v2.values()]))
    return float(numerator) / denominator if denominator != 0 else 0

Jaccard係数(重み付き)

$\frac{\sum_i \min(x_i, \ y_i)}{\sum_i \max(x_i, \ y_i)}$

def jaccard_weight(v1, v2):
    numerator = 0
    denominator = 0
    
    keys = set(v1.keys())
    keys.update(v2.keys())
    
    for k in keys:
        f1 = v1.get(k, 0)
        f2 = v2.get(k, 0)
        numerator += min(f1, f2)
        denominator += max(f1, f2)
    return float(numerator) / denominator if denominator != 0 else 0

Dice係数(重み付き)

$\frac{2 \times \sum_i \min(x_i, \ y_i)}{\sum_i x_i + y_i}$

def dice_weight(v1, v2):
    numerator = 0
    denominator = 0
    
    keys = set(v1.keys())
    keys.update(v2.keys())
    
    for k in keys:
        f1 = v1.get(k, 0)
        f2 = v2.get(k, 0)
        numerator += min(f1, f2)
        denominator += f1 + f2
    return 2 * float(numerator) / denominator if denominator != 0 else 0