python - 根据相似项目的数量有效地对集合进行分组

Question

我有一个表单集列表

animals[0] = {'cat', 'cow', 'dog'}
animals[1] = {'cat', 'cow', 'pig'}
animals[2] = {'cat', 'dog', 'fish'}
animals[3] = {'tiger', 'fish', 'pig'}
animals[4] = {'dog', 'fish', 'pig'}

如何将至少包含 2 个相似项的集合分组？为简单起见，我将使用一个 dict，其键是重叠集合的第一个元素，并且不关心属于该键的某些项目是否少于 2 个相似项目。例如，

g['cat'] = [0,1,2]
g['fish'] = [2,3,4]

因为列表 0 和 1 具有重叠项 cat 和 cow，而列表 0 和 2 具有重叠项 cat 和 dog。然而，列表 1 和 2 只有重叠项 cat 但仍包含在字典中。一种简单的蛮力方法是遍历整个列表并检查每个列表与其他所有列表。

for i,x in enumerate(animals):
    for j,y in enumerate(animals):

        intersection = x & y
        if(len(intersection)>=2):
            dict[list(intersection)[0]].append(j)

但是如果我有一个非常大的列表，这会非常耗时，所以我想学习一种更好的方法来做到这一点。如果谁有什么功能可以推荐。

Answer 1

使用余弦相似度的解决方案

关于稀疏矩阵

如果您谈论的是大型数据集，您应该考虑使用 sparse matrix .特别是，我将要描述的技术可以很好地缩放并且可以与 MapReduce 一起使用。 - 类似框架。

因此，在继续之前，我会将您提供的示例转换为稀疏矩阵。以下方法绝不是最快的方法，通常它取决于您的数据是如何生成的，例如，如果您已经有一套完整的数据集，或者您正在处理在流上工作的在线算法。

关于未知完整集的注释

如果您正在处理一个未知完整集，这是处理在线算法时的常见问题，您可以尝试创建一个哈希函数系列来将您的 key 映射到N 并逐渐和哈希函数，直到您有足够低的误报率(键映射到另一个键的存储桶)。

将集合转换为稀疏矩阵

我们现在继续assuming您有一个名为 all_the_animals 的有序完整集，它允许您将无序集映射到 N。

animals = [{'cat', 'cow', 'dog'},
{'cat', 'cow', 'pig'},
{'cat', 'dog', 'fish'},
{'tiger', 'fish', 'pig'},
{'dog', 'fish', 'pig'}]

all_the_animals = ['cat', 'cow', 'dog', 'pig', 'fish', 'tiger']

实际转化:

import scipy.sparse as sparse

def binarise(sets, full_set):
    """Return sparse binary matrix of given sets."""
    return sparse.csr_matrix([[x in s for x in full_set] for s in sets])

因此，要获得稀疏矩阵，您需要运行:

sparse_matrix = binarise(animals, all_the_animals)

使用余弦相似度

获得稀疏矩阵后，您可以继续使用 cosine similarity来自 sklearn ，它被定义为:

from sklearn.metrics.pairwise import cosine_similarity
similarities = cosine_similarity(sparse_matrix)

可视化余弦相似度

使用seaborn.heatmap 获得的相似度矩阵看起来像:

import matplotlib.pyplot as plt
import seaborn
seaborn.heatmap(s, annot=True, cmap="YlGnBu")
plt.show()

阈值

现在您可以选择相似度阈值。例如，在您的问题中，您要求 2/3 的元素是共同的:

threshold = 2/3

使用 numpy.where你可以执行:

import numpy as np
similar = np.where(similarities >= threshold)

获得:

(array([0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4]),
 array([0, 1, 2, 0, 1, 0, 2, 4, 3, 4, 2, 3, 4]))

提取相似组

现在我们有了一组 similar_animals 我们可以运行:

similar_sets = [(i, similar[1][similar[0]==i]) for i in np.unique(similar[0]))]

结果如下:

[(0, array([0, 1, 2])),
 (1, array([0, 1])),
 (2, array([0, 2, 4])),
 (3, array([3, 4])),
 (4, array([2, 3, 4]))]

要可视化结果，您可以使用有序集来获取动物名称:

similar_animal_sets = [(all_the_animals[i], similar_set) for i, similar_set in similar_sets]

哪些输出:

[('cat', array([0, 1, 2])),
 ('cow', array([0, 1])),
 ('dog', array([0, 2, 4])),
 ('pig', array([3, 4])),
 ('fish', array([2, 3, 4]))]