我有一个列表:list = ['item1', 'item2', 'item3', 'item4']
我想比较所有元素的相似度。
如果 item2 和 item3 相似，结果变成 list = ['item1', 'item2', 'item4']
编辑:
抱歉我的问题。
列表项是一组三元组。我想删除列表中的相似项。
list = [('very','beauty','place'),('very','good','place'),('another','trigram','item')]
通过计算 jaccard 相似度，该列表中的每个 pairs-item，如果 pairs-item 的 jaccard 分数 > 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)
此解决方案将继续查看两个元素的对，直到查看所有对而不过滤任何元素。这不是一个有效的解决方案，因为它会一遍又一遍地继续查看相同的对，而且它也没有利用可能的传递性。但这是一个开始。
>>> 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 的可能示例实现如下，它使用两个字符串之间的 Levenshtein 距离:
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
(请注意，我在这个例子中使用的 Levenshtein 距离不是传递比较的例子)
使用您的 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'}]