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 个带状疱疹组成，我是否可以通过将每个带状疱疹转换成唯一的哈希值然后比较哈希值来提高速度？2) 最初，我有超过 10,000 组要比较，所以我认为我最好将带状疱疹(或散列，取决于对 1 的回答)存储在数据库或酸洗中。这是一个好方法吗？3) 当一个新集被添加到我的工作流中时，我需要根据所有现有集对它进行排名并显示，比方说，最相似的前 10 个。有没有比玩具示例中的方法更好的方法？

Answer 1

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

2) complexity集合的交集和并集近似线性。 Jaccard 在计算上并不昂贵，10,000 组也不是那么(大约 5000 万次¹ 计算)。计算初始结果可能需要一个小时，但不会花费数天。

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

我会说就去做吧。

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

这是一个改编自 concurrent.futures examples 的示例( python 3)。

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