Алгоритм MinHash за 30 минут: сжимаем миллиарды векторов до коротких сигнатур

Алгоритм MinHash отвечает на конкретный вопрос: как транслировать разреженные бинарные (состоящие из нулей и единиц) векторы большой размерности в целочисленные векторы многократно меньшей размерности, сохранив информацию для оценки похожести. Результат называется сигнатурой (signature). Она уже не несёт геометрической информации исходного вектора, зато позволяет приблизительно вычислить коэффициент Жаккара, меру пересечения двух множеств. Размерность сигнатуры произвольная, но чем она длиннее, тем точнее оценка. Ниже разберём алгоритм на четырёх векторах размерности 20 с сигнатурой длиной 3. Такой масштаб помещается в голову, а принцип переносится на реальные данные с размерностями в 40 и 140 тысяч.

Что понадобится?

• Любой язык программирования или даже таблица: алгоритм MinHash реализуется буквально на бумаге.
• Четыре бинарных вектора размерности 20 (даны ниже).
• Три случайные перестановки (permutations) чисел от 1 до 20.
• Около 30 минут на разбор и ручной прогон.
• Для продакшена: семейство хэш-функций вместо готовых перестановок (экономит память и процессорное время).

Пошаговая инструкция: три шага алгоритма MinHash

Алгоритм состоит ровно из трёх действий. Разберём каждое.

Шаг 1. Генерируем вспомогательные последовательности

Каждая последовательность это числа от 1 до 20, перемешанные случайным образом. Их называют перестановками (permutations), потому что это буквально перестановка индексов. Число последовательностей равно желаемой длине сигнатуры. Нам нужна сигнатура длиной 3, значит генерируем три перестановки:

P1: 14  3 19  7  2 11 20  5 16  8  1 12 18  4  9 15  6 13 10 17
P2:  5 12  8 19  1 15  3 11 20  7 14  2 16  9 18  4 10 13  6 17
P3: 18  7 11  2 20  5 14  9  1 16  3 12  8 19  6 15 10  4 17 13

В реальном коде вместо хранения перестановок применяют хэш-функции. Каждая функция детерминированно отображает индекс в число, заменяя массив в памяти одним вызовом. Суть та же, реализация компактнее.

Шаг 2. Накладываем перестановку на вектор как битовую маску

Возьмём вектор V1:

V1: 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0

Единицы стоят в позициях 2, 5, 8, 12, 15, 18. Выписываем значения из первой перестановки P1 для этих позиций:

• Позиция 2 → значение 3
• Позиция 5 → значение 2
• Позиция 8 → значение 5
• Позиция 12 → значение 12
• Позиция 15 → значение 9
• Позиция 18 → значение 13

Получаем набор: 3, 2, 5, 12, 9, 13.

Шаг 3. Берём минимум и записываем в сигнатуру

Отсюда и название MinHash: из полученного набора забираем минимальное значение.

min(3, 2, 5, 12, 9, 13) = 2

Число 2 становится первым элементом сигнатуры вектора V1. Повторяем шаги 2 и 3 для каждой перестановки и каждого вектора. Четыре вектора, три перестановки, двенадцать проходов.

Итоговые сигнатуры:

• V1: [2, 1, 4]
• V2: [2, 1, 6]
• V3: [7, 3, 2]
• V4: [1, 8, 1]

Два похожих вектора (V1 и V2, различающиеся только в разрядах 18 и 19) получили сигнатуры, совпадающие на двух из трёх позиций. Непохожие векторы не совпали ни в одной.

Что делать с этим прямо сейчас?

ML-практику и разработчику. Возьмите четыре вектора из примера, прогоните алгоритм MinHash руками или в Jupyter-ноутбуке. Потом увеличьте размерность до 1 000, длину сигнатуры до 50 и посмотрите, как падает ошибка оценки Жаккара. Это займёт вечер и даст интуицию, которую не заменят десять прочитанных статей.

Автору и контент-маркетологу. MinHash используется внутри систем поиска дубликатов текстов. Если ваш контент проверяют на уникальность, велика вероятность, что под капотом работает именно этот или родственный алгоритм. Понимание принципа помогает осмыслить, почему переставленные абзацы всё равно ловятся как дубликаты.

Предпринимателю. Если у вас в продукте есть задача быстрого поиска похожих объектов (товаров, профилей, документов) среди миллионов записей, MinHash и его развитие LSH дают способ сравнивать не каждый с каждым, а кластеризовать кандидатов по сигнатурам. Реализации есть в открытых библиотеках на Python: datasketch, а также в Spark MLlib.

Разобраться в MinHash стоит не ради экзамена, а ради одного навыка: видеть, как из трёх простых шагов рождается инструмент, который держит на себе поиск дубликатов в системах с миллиардами документов.