Ускоренная реализация LSH (И-ИЛИ) - PullRequest
Новая
       48

Ускоренная реализация LSH (И-ИЛИ)

0 голосов
/ 17 ноября 2018

У меня есть набор данных размером (160000,3200), в котором все элементы равны нулю или единице. Я хочу найти похожих кандидатов. Я хэшировал его (160000,200), используя Minhash, используя один цикл for, и это заняло около двух минут, что меня устраивает. Я реализовал хеширование с учетом локальных особенностей (LSH) с использованием схемы AND-OR, изученной в главе 3 «Анализ массивов массивных данных», чтобы найти пары кандидатов, использующие цикл for в цикле for, но это заняло 30 минут. Я хочу сократить это время. Есть ли более быстрый способ?

Вот как я сделал LSH - длина подписи Minhash (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'

Матрица размера сигнатуры Minhash (160000,200) представляет собой пустой массив. Моя идея состоит в том, что если я могу дешево преобразовать его в массив (160000,40), где каждый элемент нового массива формируется из 5 элементов массива minhash, то, возможно, я могу использовать numpy.unique (), чтобы получить уникальную r_signature для каждого столбца использоваться в качестве ключей для словаря идентификаторов кандидатов. Я новичок в Python, а также кодирование. Я не могу придумать, как оптимизировать его, чтобы он работал быстрее.

Вот ссылка на код, а также данные: https://colab.research.google.com/drive/1HetBrWFRYqwUxn0v7wIwS7COBaNmusfD

Примечание: я заметил, что время, необходимое для части Minhash, линейно увеличивается с данными (в данном случае количество пользователей), тогда как для части LSH оно увеличивается нелинейно (для первых 6,25% это заняло 20,15 секунды и для последних 6,25% это заняло 132,3 секунды). Я думаю, что необходимо оптимизировать эту часть, если это возможно, для правильного масштабирования с данными. Я считаю, что проверка наличия ключа в словаре является частью кода, ответственного за это.

Обновление: я решил эту проблему, избегая проверки наличия ключа в dict, хотя в итоге я дважды использовал цикл for в цикле for. Теперь для 160000 кандидатов требуется 310 секунд, а затраченное время линейно масштабируется с данными. Я обновил соответствующий код в блокноте google-colab.

1 Ответ

0 голосов
/ 11 апреля 2019

Вы пытались использовать библиотеку datasketch ?Имеет реализацию для алгоритмов Minhash и LSH.

...