10

さまざまな長さの 2 つのリスト間の類似性を計算したいと思います。

例えば：

listA = ['apple', 'orange', 'apple', 'apple', 'banana', 'orange'] # (length = 6)
listB = ['apple', 'orange', 'grapefruit', 'apple'] # (length = 4)

ご覧のとおり、1 つの項目がリストに複数回表示されることがあり、長さはさまざまなサイズです。

各項目の頻度を比較することはすでに考えましたが、それは各リストのサイズを網羅していません (単純に 2 倍のリストは別のリストと似ているはずですが、完全に似ているわけではありません)。

例2:

listA = ['apple', 'apple', 'orange', 'orange']
listB = ['apple', 'orange']
similarity(listA, listB) # should NOT equal 1

したがって、基本的には、リストのサイズと、リスト内のアイテムの分布を含めたいと考えています。

何か案は？

4

3 に答える 3

30

collections.Counter()おそらく使用します。これらは、データ型の用語で言えば、マルチセットまたはバッグです。

from collections import Counter

counterA = Counter(listA)
counterB = Counter(listB)

これで、エントリまたは頻度でこれらを比較できます。

>>> counterA
Counter({'apple': 3, 'orange': 2, 'banana': 1})
>>> counterB
Counter({'apple': 2, 'orange': 1, 'grapefruit': 1})
>>> counterA - counterB
Counter({'orange': 1, 'apple': 1, 'banana': 1})
>>> counterB - counterA
Counter({'grapefruit': 1})

次を使用してコサイン類似度を計算できます。

import math

def counter_cosine_similarity(c1, c2):
    terms = set(c1).union(c2)
    dotprod = sum(c1.get(k, 0) * c2.get(k, 0) for k in terms)
    magA = math.sqrt(sum(c1.get(k, 0)**2 for k in terms))
    magB = math.sqrt(sum(c2.get(k, 0)**2 for k in terms))
    return dotprod / (magA * magB)

これにより、次のことが得られます。

>>> counter_cosine_similarity(counterA, counterB)
0.8728715609439696

その値が 1 に近いほど、2 つのリストは類似しています。

コサイン類似度は、計算できるスコアの1 つです。リストの長さが気になる場合は、別のものを計算できます。そのスコアを 0.0 から 1.0 の間に保持する場合、2 つの値を乗算して最終スコアを -1.0 から 1.0 にすることができます。

たとえば、相対的な長さを考慮するには、次を使用できます。

def length_similarity(c1, c2):
    lenc1 = sum(c1.itervalues())
    lenc2 = sum(c2.itervalues())
    return min(lenc1, lenc2) / float(max(lenc1, lenc2))

次に、リストを入力として受け取る関数に結合します。

def similarity_score(l1, l2):
    c1, c2 = Counter(l1), Counter(l2)
    return length_similarity(c1, c2) * counter_cosine_similarity(c1, c2)

2 つのリストの例では、次のようになります。

>>> similarity_score(['apple', 'orange', 'apple', 'apple', 'banana', 'orange'], ['apple', 'orange', 'grapefruit', 'apple'])
0.5819143739626463
>>> similarity_score(['apple', 'apple', 'orange', 'orange'], ['apple', 'orange'])
0.4999999999999999

必要に応じて他のメトリックを混在させることができます。

于 2013-02-06T02:00:29.320 に答える
1

理論的な観点から：コサイン類似度を調べることをお勧めします http://en.wikipedia.org/wiki/Cosine_similarity

スキームに合わせて変更する必要があるかもしれませんが、コサインの類似性のアイデアは素晴らしいものです。

于 2013-02-06T02:10:26.210 に答える
0

あなたが探しているのは、配列内の反転の数を数えることだと思います

于 2013-02-06T08:08:46.723 に答える