使用 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) 在构造 set().

时，无论如何这都是在内部完成的

2) 对于数据集的大小，我不确定您能否继续使用 python，所以我建议使用一些简单的（文本）格式，这样可以很容易例如在 C/C++ 中加载。你需要储存带状疱疹吗？如何即时生成它们？

3) 如果您需要对初始数据集进行全面比较，google-all-pairs or ppjoin 之类的东西肯定会有所帮助。它通过使用预定义的相似性阈值减少每次比较的候选集来工作。您可以修改代码以保留索引以供进一步搜索。

Answer 2

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

Answer 3

你绝对应该考虑使用多核，因为这个问题非常适合这个任务。您可能会考虑使用 PyPy，因为我看到与 Python 3 相比，大型集比较有 2-3 倍的加速。然后你可能会检查 part 1: resemblance with the jaccard coefficient 一个神奇的 C++ 实现以获得进一步的加速。这个 C++ / OpenMP 解决方案是我测试过的最快的解决方案。

使用 python 散列大量数字序列，创建散列集，存储和比较集的相似性

hashing large sequences of numbers, creating sets of hashes, storing, and comparing similarity of sets using python

python

hash

set

similarity