更快地实现LSH (和-OR)

Question

我有一个大小的数据集(1600,3200)，其中所有的元素都是0或1。我想找到类似的候选人。我使用了一个对循环的Minhash (1600,200)，它花了大约两分钟的时间，我对此很满意。我已经实现了对本地敏感的散列(LSH)，使用和-OR模式从“海量数据集的挖掘”第3章中了解到，在for-循环中使用for-循环查找候选对，但花费了30分钟。我想减少这一次。有更快的路吗？

下面是我如何实现LSH签名长度(n) = 200，子签名长度(r) = 5，带数(b) = 40。

bucket-of-ids = 'empty list of dictionaries of 
                 length 40'
for each-user in 160000:
  for each-band in 40:
    r_signature = string(jth 5 elements)
    if r_signature in bucket-of-ids[band]:
       'add id of user to dictionary of band 
        using r_signature as key'
    else :
       'create r_signature as new key and then 
        add user id to it as list of values'

大小最小的散列签名矩阵(1600,200)是一个numpy数组。我的想法是，如果我能够廉价地将其转换为(160040)数组，其中新数组的每个元素都是由最小数组的5个元素组成的，那么也许我可以使用numpy.unique()为每个列获得唯一的r_signature，作为候选it字典的键。我对python和编码都很陌生。我想不出一种方法来优化它，使它运行得更快。

下面是指向代码和数据的链接：https://colab.research.google.com/drive/1HetBrWFRYqwUxn0v7wIwS7COBaNmusfD

注意:我观察到，Minhash部分所花费的时间与数据呈线性增长(本例中为no.of用户)，而对于LSH部分则呈非线性增长(前6.25%则为20.15秒，而最后6.25%则为132.3秒)。我认为有必要优化这个部分，如果可能的话，用数据进行适当的缩放。我认为，检查字典中是否已经存在密钥是负责这一工作的代码的一部分。

更新:我已经解决了这一问题，避免了检查dict中键的存在，虽然我最终在for-循环中使用了for-循环两次。现在，160000名候选人所需时间为310秒，所需时间与数据呈线性关系。我在google笔记本上更新了相应的代码。

Answer 1

你试过使用数据表库吗？它实现了Minhash算法和LSH算法。