хеширование больших последовательностей чисел, создание наборов хэшей, хранение и сравнение сходства наборов с использованием python

Я пытаюсь найти лучший способ сравнить большие наборы числовых последовательностей с другими большими наборами, чтобы ранжировать их друг против друга. Может быть, следующий игрушечный пример проясняет проблему, где списки 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 наиболее похожих. Есть ли лучший подход, чем тот, что в игрушечном примере?


python set hash similarity
person Luis Miguel    schedule 29.11.2015    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

2) сложность множества пересечения и объединения приблизительно линейна. Jaccard не слишком дорог в вычислительном отношении, а 10 000 наборов не так уж много (около 50 миллионов1 вычислений). Вычисление первоначальных результатов, вероятно, займет час, но не дни.

3) Когда у вас есть все ваши комбинации, ранжирование другого набора по вашим существующим результатам означает выполнение всего 10 000 дополнительных сравнений. Я не могу придумать более простой способ, чем этот.

Я бы сказал, просто сделай это.

Если вы хотите работать быстрее, вы сможете достаточно легко использовать многопроцессорный подход с этим набором данных. (Каждое вычисление не зависит от других, поэтому все они могут выполняться параллельно).

Вот пример, адаптированный из concurrent.futures примеров (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
person Seth    schedule 29.11.2015
comment
Есть ли какое-либо преимущество использования параллельного модуля над многопроцессорностью для этой проблемы? - person Gökhan Sever; 30.11.2015

arrow_upward
1
arrow_downward

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

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

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

person liborm    schedule 29.11.2015
comment
@GökhanSever формат не очень приятный, вы создали аналог десериализатор, некоторое описание формата можно найти здесь. Нужно сделать как минимум две сортировки - одну по частотам признаков, другую по длинам записей. - person liborm; 01.12.2015
comment
это кажется не очень практичным в использовании, учитывая эти дополнительные шаги. - person Gökhan Sever; 02.12.2015
comment
@GökhanSever зависит от размера вашего набора данных. Около 10 миллионов элементов любое решение O (n ^ 2) гораздо менее практично, чем две сортировки и двоичная запись. - person liborm; 03.12.2015
comment
С ~ 100 000 элементов другие решения делают эту работу за меня. Я посмотрю дальше, если мой набор данных достигнет указанного вами размера. - person Gökhan Sever; 03.12.2015

arrow_upward
1
arrow_downward

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

person Gökhan Sever    schedule 30.11.2015