python - 使用 python 对大量数字序列进行哈希处理、创建哈希集、存储和比较集合的相似性

Question

我正在尝试找到将大型数字序列集与其他大型集进行比较的最佳方法，以便对它们进行相互排名。也许下面的玩具示例可以澄清这个问题，其中列表 a、b 和 c 代表时间序列中尺寸为 3 的木瓦。

a = [(1,2,3),(2,3,4),(3,4,5)]
b = [(1,2,3),(2,3,4),(3,4,7),(4,7,8)]
c = [(1,2,3),(2,3,5)]

set_a, set_b, set_c  = set(a), set(b), set(c)

jaccard_ab = float(len(set_a.intersection(set_b)))/float(len(set_a.union(set_b)))
jaccard_bc = float(len(set_b.intersection(set_c)))/float(len(set_b.union(set_c)))
jaccard_ac = float(len(set_a.intersection(se t_c)))/float(len(set_a.union(set_c)))

这些集合之间的相似之处是:

jaccard_ab, jaccard_bc, jaccard_ac
(0.4, 0.2, 0.25)

因此，在这个示例中，我们可以看到集合 a 和 b 最为相似，得分为 0.4。

我遇到一个设计问题: 1)由于每组将由约 1000 个 shingles 组成，我是否可以通过将每个 shingles 转换为唯一的哈希值然后比较哈希值来提高速度？ 2)最初，我有超过 10,000 组要比较，所以我认为将木瓦(或哈希值，取决于 1 的答案)存储在数据库或酸洗中会更好。这是一个好方法吗？ 3) 当一个新集合添加到我的工作流程中时，我需要根据所有现有集合对其进行排名，并显示最相似的前 10 个集合。有没有比玩具示例中的方法更好的方法？

Answer 1

1) 集合的成员必须是可散列的，因此 python 已经在计算散列了。存储项目的哈希集将是重复的工作，因此没有必要这样做。

2) complexity集合的交集和并集近似线性。 Jaccard 的计算价格并不昂贵，而且 10,000 套并不算多(大约 5000 万¹ 计算)。计算初始结果可能需要一个小时，但不会花费几天的时间。

3) 获得所有组合后，根据现有结果对另一组进行排名意味着只需再进行 10,000 次比较。我想不出比这更简单的方法了。

我想说就这么做吧。

如果您想更快，那么您应该能够相当轻松地对此数据集使用多处理方法。 (每个计算都独立于其他计算，因此它们都可以并行运行)。

这是改编自 concurrent.futures examples 的示例(Python3)。

import concurrent.futures

data = [
    {(1, 2, 3), (2, 3, 4), (3, 4, 5), ...},
    {(12, 13, 14), (15, 16, 17), ...},
    ...
]

def jaccard(A, B):
    return len(A & B) / len(A | B) 

with concurrent.futures.ProcessPoolExecutor(max_workers=4) as executor:
    futures = {executor.submit(jaccard, *sets): sets
               for sets in combinations(data, 2)}

    for future in concurrent.futures.as_completed(futures):
        jaccard_index = future.result()
        print(jaccard_index) # write output to a file or database here

---

[1]:

>>> from itertools import combinations
>>> print(sum(1 for i in combinations(range(10000), 2)))
49995000