хеширование больших последовательностей чисел, создание наборов хэшей, сохранение и сравнение подобия наборов с использованием 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) 

Таким образом, в этом примере, мы можем видеть, что множество а и б наиболее близки со счетом 0,4.

У меня проблема с дизайном: 1) Поскольку каждый набор будет состоять из ~ 1000 черепиц, я получаю скорость, превращая каждую гальку в уникальный хэш, а затем сравнивая хеши? 2) Первоначально у меня есть более 10 000 наборов для сравнения, поэтому я думаю, что мне намного лучше хранить черепицу (или хеши, в зависимости от ответа на 1) в базе данных или травление. Это хороший подход? 3) Поскольку новый набор добавлен к моему рабочему процессу, мне нужно ранжировать его против всех существующих наборов и отображать, скажем, самые 10 самых похожих. Есть ли лучший подход, чем в примере с игрушкой?

Answer 1

1) Члены набора должны быть хешируемыми, поэтому python уже вычисляет хэши. Хранение наборов хэшей предметов будет дублированным, поэтому нет необходимости делать это.

2) Установленное пересечение и объединение complexity приблизительно линейно. Жаккар не является дорогостоящим по цене, а 10 000 наборов не , что много (около 50 миллионов расчетов). Это, вероятно, займет час, чтобы вычислить ваши первоначальные результаты, но это займет несколько дней.

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 2

1) Это делается в любом случае при построении set().

2) Я не уверен, что вы сможете остаться с python для вашего размера набора данных, поэтому я бы предложил использовать простой (текстовый) формат, чтобы его можно было легко загрузить, например, в C/C++. Вам нужно вообще хранить черепицу? А как их генерировать на лету?

3) Если вам нужно все для сравнения для вашего начального набора данных, то, что-то вроде google-all-pairs или ppjoin, безусловно, поможет. Он работает путем уменьшения набора кандидатов для каждого сравнения с использованием предопределенного порога подобия. Вы можете изменить код, чтобы сохранить индекс для дальнейшего поиска.

Answer 3

Вы определенно должны рассмотреть возможность использования мульти-ядра, как эта проблема очень подходит для этой задачи. Вы можете рассмотреть PyPy, так как я вижу ускорение 2-3X по сравнению с Python 3 для большого сравнения. Затем вы можете проверить part 1: resemblance with the jaccard coefficient для магической реализации на C++, чтобы получить дополнительные ускорения. Это решение C++/OpenMP является самым быстрым, которое я тестировал.