хеширане на големи поредици от числа, създаване на набори от хешове, съхраняване и сравняване на сходството на набори с помощта на 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 форматът не е много добър, вие сте създали аналог на deserializer, някои описания на формата могат да бъдат намерени тук. Трябва да направите най-малко две сортировки - една на характерните честоти, една на дължините на записа. - 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
С ~100K артикула, други решения вършат работа вместо мен. Ще потърся допълнително, ако моят набор от данни се разшири до размера, който споменахте. - person Gökhan Sever; 03.12.2015

arrow_upward
1
arrow_downward

Определено трябва да обмислите използването на многоядрени процесори, тъй като този проблем е много подходящ за тази задача. Може да помислите за PyPy, тъй като виждам 2-3 пъти ускорение в сравнение с Python 3 за голямо сравнение. След това можете да разгледате част 1: прилика с коефициента на jaccard за магическа реализация на C++, за да получите допълнителна скорост- UPS. Това C++ / OpenMP решение е най-бързото, което съм тествал досега.

person Gökhan Sever    schedule 30.11.2015