Минимальные хеши: число различных и сходство множеств

Если различаешь оценку мощности и оценку сходства, листай до «Теперь сам».

Как думаешь, можно ли сравнить два списка без их хранения

Два сервиса видели миллионы идентификаторов, многие повторялись. Нужно узнать, сколько различных идентификаторов было вместе и насколько пересекались аудитории. Счётчик событий даст завышенное число, а знакомый HyperLogLog оценивает мощность, но сам по себе не возвращает сходство двух множеств. Минимальные хеши дают другой набор операций и гарантий.

На что это похоже

Представь, что каждому уникальному посетителю выдали случайный билет с числом от нуля до единицы. Чем больше посетителей, тем меньше обычно оказывается десятый по величине снизу билет. Храня только несколько победителей такого розыгрыша, можно судить о размере всей аудитории. Для сходства интересен один общий победитель: он совпадёт у двух аудиторий, если принадлежит их пересечению.

Механизм: порядок вместо частоты

При N независимых непрерывных равномерных билетах k-я порядковая статистика лежит примерно около k/N. Но просто обратить среднее нельзя. Точная несмещённая оценка при N≥k и k>1 использует (k-1)/uₖ. Независимость и непрерывность здесь - идеальная модель; конечный хеш допускает коллизии и требует их учитывать. k=1 в этой формуле не подходит.

Новый элемент добавляется лишь если его хеш входит в нижние k; повтор уже сохранённого элемента отбрасывается. Слияние сводок объединения берёт нижние k из объединения сохранённых пар. Это корректно при общем хеше: элемент, не попавший в нижние k своего исходного набора, не сможет попасть в нижние k объединения. Разные хеши уничтожают общий порядок и делают такое слияние бессмысленным.

Для MinHash вообразим равновероятную перестановку элементов объединения. Самый ранний элемент равновероятно выбирается из A∪B. Минимумы A и B совпадают ровно тогда, когда он лежит в A∩B. Значит вероятность совпадения - отношение размеров. При фиксированном числе независимых перестановок оценкой служит доля совпадений. Пустые множества обрабатываются отдельным договором, а не попыткой взять минимум пустого набора.

Правило

Для объединения KMV нужен единый порядок хешей; для MinHash - единая перестановка внутри одной пары и независимые перестановки между повторами. Один минимум не даёт точного сходства: он даёт один случайный признак совпадения.

Разбор: точная проверка вероятности на маленькой вселенной

from hashlib import blake2b
from itertools import permutations
from fractions import Fraction


def rank(x):
    raw = blake2b(str(x).encode(), digest_size=8).digest()
    return int.from_bytes(raw, "big")


def kmv(items, k):
    # Для учебной ясности используется полная сортировка.
    return sorted(set(items), key=lambda x: (rank(x), x))[:k]


def estimate(summary, k):
    if len(summary) < k:
        return float(len(summary))
    u = (rank(summary[-1]) + 0.5) / 2**64
    return (k - 1) / u


a = {1, 2, 3}
b = {2, 3, 4, 5}
k = 3
left, right = kmv(a, k), kmv(b, k)
merged = kmv(left + right, k)
assert merged == kmv(a | b, k)
assert kmv([1, 2, 2, 2, 3], k) == kmv(a, k)
print("Слияние:", merged)
print("Оценка объединения:", f"{estimate(merged, k):.3f}")
hits = trials = 0
for order in permutations(sorted(a | b)):
    position = {x: i for i, x in enumerate(order)}
    x = min(a, key=position.get)
    y = min(b, key=position.get)
    hits += x == y
    trials += 1
actual = Fraction(hits, trials)
expected = Fraction(len(a & b), len(a | b))
assert actual == expected
print("Перестановок:", trials)
print("Вероятность совпадения:", actual)

Слияние: [2, 4, 5]
Оценка объединения: 3.675
Перестановок: 120
Вероятность совпадения: 2/5

Перебор всех перестановок не применяется к большой аудитории. Здесь он является независимой проверкой равенства вероятностей на маленьком наборе. Доля совпадений получается точно равной Жаккару. Для KMV программа отдельно проверяет сливаемость и нечувствительность к повторам.

Разбор: одинаковый размер не означает сходство

Множества {a,b,c} и {d,e,f} имеют одинаковую мощность, но Жаккар нулевой. Множества {a,b,c} и {a,b,d} также одинакового размера, а Жаккар равен половине. Значит мощность нельзя использовать вместо сходства. И наоборот, оценка Жаккара сама по себе не сообщает число уникальных посетителей: для него нужна мощность или дополнительная сводка.

В идеальной модели увеличение k уменьшает относительный шум KMV примерно как 1/√k. Это плата памятью за точность. У MinHash число независимых повторов играет похожую роль, но наблюдаемая величина и формула ошибки другие: усредняются нули и единицы совпадения.

Что ломается без этого

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

Зачем это в работе

Нужно ежедневно сливать статистику разных узлов и сравнивать аудитории документов. KMV естественно объединяется при общем хеше, MinHash позволяет искать похожие наборы признаков. В отличие от списка всех посетителей сводка мала, но результат статистический. Для решений, где ошибка недопустима, оценку нужно дополнять точной проверкой кандидатов.

Теперь сам

A={1,2,3}, B={2,3,4,5}. Какова вероятность совпадения MinHash в идеальной модели? Что произойдёт, если добавить тысячу повторений двойки?