読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

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

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

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

導入

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

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

文脈ベクトルの作り方

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

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

文脈ベクトルの値

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

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

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

簡単な例

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

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

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

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

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

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

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

類似度の計算

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

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

ユークリッド距離などを使う場合もありますが、比較する文脈ベクトルの長さ(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

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

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

類似度の計算例

「ご飯」(v1)について「夕食」(v2)と「布団」(v3)についてどちらが似ているか確認してみます(極端な例ですが)。
コサイン類似度を計算すると以下のようになり、「ご飯」(v1)については「夕食」(v2)のほうが似ていることがわかります。

jaccard(v1, v2) = \frac{2}{9 + 4 - 2} \approx 0.18
jaccard(v1, v3) = 0.0

この方法で似ている単語になるものには対義語も含まれるかもしれないことに注意が必要です。

参考・関連

いろいろな類似度の話。

共起性を測る尺度の話。

知り合いの同様の記事。

より細かい話。

重み付きのベクトルに対するJaccardとDice係数の定義が載っていた本。

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

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

-->