1

リストがあります：list = ['item1', 'item2', 'item3', 'item4']

すべてのアイテムの類似性を比較したい。

item2とitem3が似ている場合、結果は次のようになります。list = ['item1', 'item2', 'item4']

編集：

紛らわしい質問で申し訳ありません。

リスト項目はトリグラムのセットです。リスト内の類似アイテムを削除したい。

list = [('very','beauty','place'),('very','good','place'),('another','trigram','item')]

そのリスト内のすべてのペアアイテムのジャカード類似度を計算し、ペアアイテムのジャカードスコア> 0.4の場合、類似と呼びます。この例では、item1 と item2 は類似しています。私が望む最後の出力は次のとおりです。

list = [('very','beauty','place'),('another','trigram','item')]

これは、jaccard スコアを計算する方法です。

def compute_jaccard_index(set_1, set_2):
   n = len(set_1.intersection(set_2))
   return n / float(len(set_1) + len(set_2) - n)
4

4 に答える 4

2

これは、単純な等値比較の代わりに類似関数がある場合に機能します。

itemsToRemove = []
n = len(list)
for i in range(n):
  for j in range(i+1,n):
      if(similarTest(list[i], list[j]):
        itemsToRemove.append(list[i])
        break
return [item for item in list if item not in itemsToRemove]

もちろん、他の人が示唆しているように、実際に同一のアイテムを削除しようとしている場合は、セットがうまく機能します.

于 2013-09-16T19:01:00.590 に答える
2

このソリューションは、フィルタリングせずにすべてのペアを調べるまで、2 つの要素のペアを調べ続けます。同じペアを何度も何度も調べ続けるため、効果的な解決策ではありません。また、可能な推移性も利用しません。しかし、それは始まりです。

>>> from itertools import combinations
>>> def filterSimilar (d):
        while True:
            filteredOne = False
            for s, t in combinations(d, 2):
                if isSimilar(s, t):
                    d.remove(t)
                    filteredOne = True
                    break
            if not filteredOne:
                break
>>> d = ['asdf', 'asxf', 'foo', 'bar', 'baz']   
>>> filterSimilar(d)
>>> d
['asdf', 'foo', 'bar']

可能な実装例isSimilarは、2 つの文字列間のレーベンシュタイン距離を使用する次のとおりです。

def levenshteinDistance (s, t):
    if len(s) == 0:
        return len(t)
    if len(t) == 0:
        return len(s)
    return min(levenshteinDistance(s[:-1], t) + 1, levenshteinDistance(s, t[:-1]) + 1, levenshteinDistance(s[:-1], t[:-1]) + (0 if s[-1] == t[-1] else 1))

def isSimilar (s, t):
    return levenshteinDistance(s, t) < 2

(この例で使用したレーベンシュタイン距離は、推移的な比較の例ではないことに注意してください)

関数を使用するcompute_jaccard_indexと、isSimilar関数は次のようになります。

def isSimilar (s, t):
    return compute_jaccard_index(s, t) > .4

そして、あなたのサンプルデータで使用されます:

>>> lst = [{'very','beauty','place'},{'very','good','place'},{'another','trigram','item'}]
>>> filterSimilar(lst)
>>> lst
[{'very', 'beauty', 'place'}, {'item', 'trigram', 'another'}]
于 2013-09-16T19:08:28.867 に答える