Поиск похожих документов с MinHash + LHS

В этой публикации я расскажу о том, как можно находить похожие документы с помощью MinHash + Locality Sensitive Hashing. Описание LHS и Minhash в «Википедии» изобилует ужасающим количеством формул. На самом деле все довольно просто.

1. Выделение признаков


Выделение признаков

Под документом в этой статье я понимаю обычный текст, но в общем случае это может быть любым массивом байт. Штука в том, что для сравнения любого документа с помощью MinHash его необходимо сначала преобразовать в множество элементов.

Для текстов неплохо подойдет преобразование в множество ID слов. Скажем, «мама мыла раму» -> [1, 2, 3], а «мама мыла» -> [1, 2].

Похожесть этих множеств равна 2/3, где 2 — количество похожих элементов, а 3 — общее количество разных слов.

Также можно разбить эти тексты на N-граммы, например, «мама мыла раму» разбивается на триграммы «мам, ама, ма_, а_м, ...», что даст похожесть 7/12.

2. Создание сигнатуры с MinHash


MinHash

Капитан очевидность говорит нам, что MinHash — это минимальный хэш из всех хэшей нашего множества. Скажем, если у нас есть простая случайная хэшфункция f(v) = v, то наши множества ID слов [1, 2, 3] и [1, 2] преобразуются в множество хэшей [1078, 2573, 7113] и [1078, 2573], и для каждого множества минхэш равен 1078. Вроде несложно.

Вероятность того, что минимальные хэши для двух множеств совпадут, весьма точно равна похожести этих двух множеств. Доказывать я это не хочу, т.к. у меня аллергия на формулы, но это очень важно.

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

Для закрепления результата мы можем взять много разных хэш-функций и для каждой из них найти минхэш. Довольно просто можно получить много разных хэш-функций, сгенерировав много случайных, но различных чисел, и ксорить нашу первую хэшфункцию на эти числа. Скажем, сгенерируем совершенно случайные числа 700 и 7000, что даст нам две дополнительные хэш-функции. Тогда минхэши для [1, 2, 3] будут (1078, 2573, 7113) -> 1078, (1674, 2225, 6517) -> 1674, (8046, 4437, 145) -> 145, а для [1, 2] минхеши, она же сигнатура будет равна (1078, 2573) -> 1078, (1674, 2225) -> 1674, (8046, 4437) -> 4437. Как видно, первые две пары минхэшей совпадают, из чего очень грубо можно предположить, что похожесть исходных множеств равна 2/3. Понятно, что чем больше хешфункций, тем точнее можно определить похожесть исходных множеств.

3. Создание ключей с Locality Sensitive Hashing


LHS

Мы теперь можем определить, насколько похожи документы используя только их сигнатуры (N значений минхэшей), но что нужно писать в хранилище key-value для возможности выборки по всем более-менее похожим документам? Если использовать целые сигнатуры в качестве ключей, то мы сделаем выборку только по практически идентичным документам, т.к. вероятность того что N минхешей совпадет равна s^N где s — одинаковость документов.

Решение простое — допустим наши сигнатуры состоят из 100 чисел, мы можем разбить ее на несколько частей (скажем, 10 частей по 10 чисел), после чего все эти части сделать ключами целой сигнатуры.

Вот и все, теперь для определения того что у нас в базе уже есть похожий документ. Нужно получить его сигнатуру из 100 минхешей, разбить на десять ключей и для всех соответствующих им полных сигнатур вычислить ее похожесть (количество совпадающих минхешей).

Для десяти ключей с десятью элементами в каждом вероятность выборки документа в зависимости от похожести документа будет такая:

1-(1-s^r)^b
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 13

    0
    сгенерировав много случайных, но различных чисел, и ксорить нашу первую хэшфункцию на эти числа

    Если я правильно понял принцип, то много разных хэш-функций нужно для оценки расстояния между векторами в пространстве результатов каждой конкретной функции. Что дает в этом случае xor вектора?
      0
      Это просто рандомизация исходной хэш функции — можно еще много подобных методов придумать, например, если есть хорошая хэш функция типа murmur/sha/что-угодно то к ней для рандомизации можно просто добавлять на вход числа от 0 до N, что даст отличный набор разных хэш функций. К ним, как я понимаю, никаких особых требований, кроме того что они должны быть разными, не предъявляется.
        0
        набор разных хэш функций

        Вот как раз к качеству «разности» и возник вопрос.
          0
          Влияние качества хэш функции на результат я сильно не исследовал, так что хорошо ответить наверное не смогу. Я думаю плохие функции увеличивают число false positive попаданий на последнем этапе, но если первая функция хорошая (скажем, murmur/cityhash) то XOR со случайным числом должен дать хороший результат, по крайней мере вот тут так говорят stackoverflow.com/questions/19701052/how-many-hash-functions-are-required-in-a-minhash-algorithm
          Если XOR не нравится, там же советуют использовать Universal Hashing вида h(x,a,b) = ((ax+b) mod p) mod m

          Да, и в MinHash расстояние между векторами не используется, там главное то, что два минхеша от разных множеств равны с точно такой же вероятностью, насколько похожи множества, а если они не равны, то сравнивать расстояние особого смысла в этом алгоритме нет.
      0
      А если брать словные n-граммы в качестве исходных элементов документа, то получим довольно известный алгоритм шинглирования. Кажется, такой подход популярнее для поиска плагиата/сходства.
        0
        Да, это довольно просто и работает неплохо. Я аж одно предложение про это написал. Я еще подумал, что еще лучше может работать не набор ID слов, а их пары (вроде 1,2 2,3) чтобы как-то сохранять порядок слов в тексте.
        0
        Капитан очевидность говорит нам, что MinHash — это минимальный хэш из всех хэшей нашего множества. Скажем, если у нас есть хэшфункция, которая возвращает значение на входе, то множество ID слов [1, 2, 3] преобразуется в множество хэшей [1, 2, 3] где минимальный хэш равен 1, а минимальный хэш для [1, 2] очевидно тоже даст единицу. Вроде несложно.

        Вот этот кусок статьи очень труден для понимания. Пришлось перечитать 4 (!) раза, хотя, вроде, не много текста. Главную проблему создали вот эти слова: «есть хэшфункция, которая возвращает значение на входе». Добавьте псевдокод для этого (hash(x) = x) или перефразируйте может.
          0
          Спасибо, попробовал написать по-другому. Пытался обойтись без формул, даже тривиальных, что вышло не совсем хорошо.
          0
          А почему собственно только минимум? Ведь максимум равноправен, так что можем брать как минимум, так и максимум. По большому счету наши любимые 16-байтные хеши достаточно длинны, чтобы мы могли безболезненно применить над ними перестановку. Всё равно энтропии в слове не хватит для того, чтобы обеспечить такое количество информации на выходе.

          На самом деле мы сравниваем хеши а не сами слова просто для того, чтобы убрать артефакт «алфавита», т.е. не придавать больше значения словам начинающимся с буквы А, и т.п.

          Хранить в базе мы можем не сами хеши, а их ИД. Уникальных хешей в базе будет не так много — столько сколько уникальных слов в базе. С хешами хешей (вернее групп хешей) сложнее конечно.

          Отбор именно минимума по сути дает нам некий псевдослучайный метод отбора заданного количества хешей, с соблюдением условия, что для любого текста список этих случайных хешей будет один и тот-же. Это дает нам возможность сравнивать не всё множество, а только короткую его часть, обеспечивая при этом предсказуемую точность.

          Если мы в базе будем хранить ИД слова + ИД хеша (ид хешфункции, т.е. ИД варианта перестановки если мы все хеши делаем перестановкой), то это будет эквивалентно тому, что мы храним всю таблицу хешей.
            0
            Да, MaxHash наверное будет работать точно так же. Кстати, я только сейчас сообразил, что использовать в качестве множества id слов это была плохая идея. Получается, что все большие тексты будут практически равны, т.к. все они используют наиболее часто встречающиеся слова. Нужно было N-граммы в примере использовать, но они выглядят сложнее…
              0
              Вероятно вы не учитываете частотность слов.
              Если отбросить «стоп-слова», то качество поиска похожих будет достаточно высоким.
              Единственное что — нужно выбирать правильно словарь стоп-слов. Именно под ваши задачи.
              Не знаю вашу задачу, но по опыту скажу, что в качестве первого приближения хорошо работает правило — первую треть самых частотных слов генеральной совокупности отправляем в топку.
              0
              Коллеги, есть задачка: получить от пользователя текст размером 100-1000 знаков и выдать ему в ответ N ранее сохраненных текстов, отсортированных по принципу «похожести». Ближайший аналог — UI задавания вопроса на Quora, когда перед тем, как добавить вопрос она спрашивает: «вот вопросы, похожие на ваш — убедитесь что вы задаёте новый, а не дубль». В идеале оформить в виде самостоятельного модуля с двумя endpoints: в один подаются «старые» тексты с ID, в другой — подается «новый» текст, а в ответ получается список из N «старых» ID. Можете сделать? Вопрос в первую очередь к автору, но вижу и комментаторов с потенциалом к разработке такого решения. Спасибо!
                0
                Сделать-то теоретически можно, но есть два больших но — я скорее специалист по «small data» (мобильным технологиям), и я шабашки давно не беру. В принципе задача особо не сложная — самый простой вариант это просто повторить статью и после выборки похожих документов их отсортировать по похожести. Если документов не слишком много, работать будет.

              Only users with full accounts can post comments. Log in, please.