Можете ли вы предложить хорошую реализацию minhash?

Я пытаюсь найти реализацию с открытым исходным кодом minhash, которую я могу использовать для своей работы.

Функциональность, в которой я нуждаюсь, очень проста, учитывая набор в качестве входных данных, реализация должна возвращать свой minhash.

Реализация на python или C предпочтительнее, на случай, если мне нужно взломать ее, чтобы она работала на меня.

Любые указатели будут очень полезны.

С уважением.

Источник

6 ответов

Если вы заинтересованы в изучении алгоритма minhash, вот очень простая реализация с некоторым обсуждением.

Чтобы сгенерировать сигнатуру MinHash для набора, мы создаем вектор длины $N$ в котором все значения установлены в положительную бесконечность. Мы также создаем $N$ функции, которые принимают входное целое число и переставляют это значение. $i^{th}$ функция будет нести полную ответственность за обновление $i^{th}$значение в векторе. Учитывая эти значения, мы можем вычислить подпись minhash набора, передавая каждое значение из набора через каждый из $N$ перестановочные функции. Если на выходе $i^{th}$ функция перестановки ниже, чем $i^{th}$ значение вектора, мы заменим значение с выходом из функции перестановки (именно поэтому хэш известен как "min- hash"). Давайте реализуем это в Python:

from scipy.spatial.distance import cosine
from random import randint
import numpy as np

# specify the length of each minhash vector
N = 128
max_val = (2**32)-1

# create N tuples that will serve as permutation functions
# these permutation values are used to hash all input sets
perms = [ (randint(0,max_val), randint(0,max_val)) for i in range(N)]

# initialize a sample minhash vector of length N
# each record will be represented by its own vec
vec = [float('inf') for i in range(N)]

def minhash(s, prime=4294967311):
  '''
  Given a set `s`, pass each member of the set through all permutation
  functions, and set the `ith` position of `vec` to the `ith` permutation
  function's output if that output is smaller than `vec[i]`.
  '''
  # initialize a minhash of length N with positive infinity values
  vec = [float('inf') for i in range(N)]

  for val in s:

    # ensure s is composed of integers
    if not isinstance(val, int): val = hash(val)

    # loop over each "permutation function"
    for perm_idx, perm_vals in enumerate(perms):
      a, b = perm_vals

      # pass `val` through the `ith` permutation function
      output = (a * val + b) % prime

      # conditionally update the `ith` value of vec
      if vec[perm_idx] > output:
        vec[perm_idx] = output

  # the returned vector represents the minimum hash of the set s
  return vec

Это все, что нужно сделать! Чтобы продемонстрировать, как мы можем использовать эту реализацию, давайте рассмотрим простой пример:

import numpy as np

# specify some input sets
data1 = set(['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',
        'estimating', 'the', 'similarity', 'between', 'datasets'])
data2 = set(['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',
        'estimating', 'the', 'similarity', 'between', 'documents'])

# get the minhash vectors for each input set
vec1 = minhash(data1)
vec2 = minhash(data2)

# divide both vectors by their max values to scale values {0:1}
vec1 = np.array(vec1) / max(vec1)
vec2 = np.array(vec2) / max(vec2)

# measure the similarity between the vectors using cosine similarity
print( ' * similarity:', 1 - cosine(vec1, vec2) )

Это возвращает ~ 0,9 как измерение сходства между этими векторами.

Хотя мы сравниваем только два вектора minhash выше, мы можем сравнивать их намного проще, используя "Locality Sensitive Hash". Для этого мы можем построить словарь, который отображает каждую последовательность векторных компонентов $W$ MinHash на уникальный идентификатор для набора, из которого был построен вектор MinHash. Например, если W = 4 и у нас есть набор S1 из которого мы получаем вектор MinHash [111,512,736,927,817...]мы бы добавили S1 идентификатор каждой последовательности из четырех значений MinHash в этом векторе:

d[111-512-736-927].append('S1')
d[512-736-927-817].append('S1')
...

Как только мы сделаем это для всех наборов, мы сможем проверить каждый ключ в словаре, и если у этого ключа есть несколько различных идентификаторов наборов, у нас есть основания полагать, что эти наборы похожи. Действительно, чем больше раз встречается пара идентификаторов набора в одном значении в словаре, тем больше сходство между двумя наборами. Обрабатывая наши данные таким образом, мы можем уменьшить сложность идентификации всех пар одинаковых наборов примерно до линейного времени!

Источник

Вы должны взглянуть на следующие библиотеки с открытым исходным кодом, по порядку. Все они в Python и показывают, как вы можете рассчитать сходство документов, используя LSH/MinHash:

LSH
LSHHDC: высокочувствительная кластеризация на основе хеширования
MinHash

Источник

Взгляните на библиотеку эскизов. Поддерживает сериализацию и слияние. Он реализован на чистом питоне без внешней зависимости. Версия Go имеет те же функции.

Источник

Я бы предложил вам эту библиотеку, особенно если вам нужна настойчивость. Здесь вы можете использовать Redis для хранения / извлечения всех ваших данных.

У вас есть возможность выбрать базу данных Redis или просто использовать встроенные словари Python в памяти.

Производительность с использованием Redis, по крайней мере, если сервер Redis работает на вашем локальном компьютере, практически идентична тем, которые достигаются с помощью стандартных словарей Python.

Вам нужно только указать словарь конфигурации, такой как

config = {"redis": {"host": 'localhost', "port": '6739', "db": 0}}

и передать его в качестве аргумента LSHash конструктор класса.

Источник

Я думаю, что пакет Python pyminhash делает то, что вам нужно. Он работает с кадрами данных Pandas.

Источник

Библиотека Hash4j от Dynatrace предоставляет Java-реализации MinHash и SuperMinHash . Последний обычно намного быстрее, чем MinHash.

Источник
Другие вопросы по тегам