類似係数(Jaccard/Simpson/Dice)をPythonで求める

語が2つ与えられた時に、どのくらい似ているのか計量評価したいといった目的のために類似指数というのが存在します。

今回は、よく知られていて、かつ、実装の簡単な

  • Jaccard 係数
  • Simpson 係数
  • Dice 係数

を Python で実装します。

これら3つの係数は、0から1までの値を取り、1に近づくほど類似し、0に近づくほど類似していないことを表します。

Jaccard 係数

Jaccard index, Jaccard similarity coefficient などとも呼ばれます。

次の式で表されます。

|X∩Y| / |X∪Y|
  • xとYが完全一致

の場合に1となります。

def jaccard(x, y):
    """
    Jaccard index
    Jaccard similarity coefficient
    https://en.wikipedia.org/wiki/Jaccard_index
    """
    x = frozenset(x)
    y = frozenset(y)
    return len(x & y) / float(len(x | y))

Simpson 係数

overlap coefficient, Szymkiewicz-Simpson coefficient などとも呼ばれます。

次の式で表されます。

|X∩Y| / min(|X|, |Y|)
  • XとYが完全一致
  • XがYの部分集合(またはその逆)

の場合に1となります。

def overlap(x, y):
    """
    overlap coefficient
    Szymkiewicz-Simpson coefficient)
    https://en.wikipedia.org/wiki/Overlap_coefficient
    """
    x = frozenset(x)
    y = frozenset(y)
    return len(x & y) / float(min(map(len, (x, y))))

Dice 係数

Dice’s coefficient/Sørensen-Dice coefficient などとも呼ばれます。
次の式で表されます。

2 * |X∩Y| / (|X| + |Y|)

xとYが完全一致

の場合に1となります。

三角不等式を満たさないため、

def dice(x, y):
    """
    Dice's coefficient
    Sørensen-Dice coefficient
    https://en.wikipedia.org/wiki/Dice%27s_coefficient
    """
    x = frozenset(x)
    y = frozenset(y)
    return 2 * len(x & y) / float(sum(map(len, (x, y))))

計算してみる

  • night
  • nacht
  • nuit

の3語に対して、各組み合わせの類似係数を求めてみましょう。

#!/usr/bin/env python
# vim: set fileencoding=utf8 :

def jaccard(x, y):
    """
    Jaccard index
    Jaccard similarity coefficient
    https://en.wikipedia.org/wiki/Jaccard_index
    """
    x = frozenset(x)
    y = frozenset(y)
    return len(x & y) / float(len(x | y))

def overlap(x, y):
    """
    overlap coefficient
    Szymkiewicz-Simpson coefficient)
    https://en.wikipedia.org/wiki/Overlap_coefficient
    """
    x = frozenset(x)
    y = frozenset(y)
    return len(x & y) / float(min(map(len, (x, y))))

def dice(x, y):
    """
    Dice's coefficient
    Sørensen-Dice coefficient
    https://en.wikipedia.org/wiki/Dice%27s_coefficient
    """
    x = frozenset(x)
    y = frozenset(y)
    return 2 * len(x & y) / float(sum(map(len, (x, y))))

a = 'night'
b = 'nacht'
c = 'nuit'

for x, y in ((a,b), (a,c), (b, c)):
    print "similarity between [%s] and [%s]" % (x, y)
    print "Jaccard:", jaccard(x, y)
    print "overlap:", overlap(x, y)
    print "dice:", dice(x, y)

実行してみると、次のような結果となりました。

similarity between [night] and [nacht]
Jaccard: 0.428571428571
overlap: 0.6
dice: 0.6
similarity between [night] and [nuit]
Jaccard: 0.5
overlap: 0.75
dice: 0.666666666667
similarity between [nacht] and [nuit]
Jaccard: 0.285714285714
overlap: 0.5
dice: 0.444444444444

その他

今回は類似指数を「語」を対象にしましたが、2つのベクトル間の類似性を求めるなど、広い意味での類似性の抽出に利用出来ます。

関連リンク

Advertisements
Posted in algorithm, nlp, Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 4 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 5 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 5 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 10 months ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago
%d bloggers like this: