Comments 13
сгенерировав много случайных, но различных чисел, и ксорить нашу первую хэшфункцию на эти числа
Если я правильно понял принцип, то много разных хэш-функций нужно для оценки расстояния между векторами в пространстве результатов каждой конкретной функции. Что дает в этом случае xor вектора?
Это просто рандомизация исходной хэш функции — можно еще много подобных методов придумать, например, если есть хорошая хэш функция типа murmur/sha/что-угодно то к ней для рандомизации можно просто добавлять на вход числа от 0 до N, что даст отличный набор разных хэш функций. К ним, как я понимаю, никаких особых требований, кроме того что они должны быть разными, не предъявляется.
набор разных хэш функций
Вот как раз к качеству «разности» и возник вопрос.
Влияние качества хэш функции на результат я сильно не исследовал, так что хорошо ответить наверное не смогу. Я думаю плохие функции увеличивают число 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 расстояние между векторами не используется, там главное то, что два минхеша от разных множеств равны с точно такой же вероятностью, насколько похожи множества, а если они не равны, то сравнивать расстояние особого смысла в этом алгоритме нет.
Если XOR не нравится, там же советуют использовать Universal Hashing вида h(x,a,b) = ((ax+b) mod p) mod m
Да, и в MinHash расстояние между векторами не используется, там главное то, что два минхеша от разных множеств равны с точно такой же вероятностью, насколько похожи множества, а если они не равны, то сравнивать расстояние особого смысла в этом алгоритме нет.
А если брать словные n-граммы в качестве исходных элементов документа, то получим довольно известный алгоритм шинглирования. Кажется, такой подход популярнее для поиска плагиата/сходства.
А почему собственно только минимум? Ведь максимум равноправен, так что можем брать как минимум, так и максимум. По большому счету наши любимые 16-байтные хеши достаточно длинны, чтобы мы могли безболезненно применить над ними перестановку. Всё равно энтропии в слове не хватит для того, чтобы обеспечить такое количество информации на выходе.
На самом деле мы сравниваем хеши а не сами слова просто для того, чтобы убрать артефакт «алфавита», т.е. не придавать больше значения словам начинающимся с буквы А, и т.п.
Хранить в базе мы можем не сами хеши, а их ИД. Уникальных хешей в базе будет не так много — столько сколько уникальных слов в базе. С хешами хешей (вернее групп хешей) сложнее конечно.
Отбор именно минимума по сути дает нам некий псевдослучайный метод отбора заданного количества хешей, с соблюдением условия, что для любого текста список этих случайных хешей будет один и тот-же. Это дает нам возможность сравнивать не всё множество, а только короткую его часть, обеспечивая при этом предсказуемую точность.
Если мы в базе будем хранить ИД слова + ИД хеша (ид хешфункции, т.е. ИД варианта перестановки если мы все хеши делаем перестановкой), то это будет эквивалентно тому, что мы храним всю таблицу хешей.
На самом деле мы сравниваем хеши а не сами слова просто для того, чтобы убрать артефакт «алфавита», т.е. не придавать больше значения словам начинающимся с буквы А, и т.п.
Хранить в базе мы можем не сами хеши, а их ИД. Уникальных хешей в базе будет не так много — столько сколько уникальных слов в базе. С хешами хешей (вернее групп хешей) сложнее конечно.
Отбор именно минимума по сути дает нам некий псевдослучайный метод отбора заданного количества хешей, с соблюдением условия, что для любого текста список этих случайных хешей будет один и тот-же. Это дает нам возможность сравнивать не всё множество, а только короткую его часть, обеспечивая при этом предсказуемую точность.
Если мы в базе будем хранить ИД слова + ИД хеша (ид хешфункции, т.е. ИД варианта перестановки если мы все хеши делаем перестановкой), то это будет эквивалентно тому, что мы храним всю таблицу хешей.
Да, MaxHash наверное будет работать точно так же. Кстати, я только сейчас сообразил, что использовать в качестве множества id слов это была плохая идея. Получается, что все большие тексты будут практически равны, т.к. все они используют наиболее часто встречающиеся слова. Нужно было N-граммы в примере использовать, но они выглядят сложнее…
Вероятно вы не учитываете частотность слов.
Если отбросить «стоп-слова», то качество поиска похожих будет достаточно высоким.
Единственное что — нужно выбирать правильно словарь стоп-слов. Именно под ваши задачи.
Не знаю вашу задачу, но по опыту скажу, что в качестве первого приближения хорошо работает правило — первую треть самых частотных слов генеральной совокупности отправляем в топку.
Если отбросить «стоп-слова», то качество поиска похожих будет достаточно высоким.
Единственное что — нужно выбирать правильно словарь стоп-слов. Именно под ваши задачи.
Не знаю вашу задачу, но по опыту скажу, что в качестве первого приближения хорошо работает правило — первую треть самых частотных слов генеральной совокупности отправляем в топку.
Коллеги, есть задачка: получить от пользователя текст размером 100-1000 знаков и выдать ему в ответ N ранее сохраненных текстов, отсортированных по принципу «похожести». Ближайший аналог — UI задавания вопроса на Quora, когда перед тем, как добавить вопрос она спрашивает: «вот вопросы, похожие на ваш — убедитесь что вы задаёте новый, а не дубль». В идеале оформить в виде самостоятельного модуля с двумя endpoints: в один подаются «старые» тексты с ID, в другой — подается «новый» текст, а в ответ получается список из N «старых» ID. Можете сделать? Вопрос в первую очередь к автору, но вижу и комментаторов с потенциалом к разработке такого решения. Спасибо!
Сделать-то теоретически можно, но есть два больших но — я скорее специалист по «small data» (мобильным технологиям), и я шабашки давно не беру. В принципе задача особо не сложная — самый простой вариант это просто повторить статью и после выборки похожих документов их отсортировать по похожести. Если документов не слишком много, работать будет.
Sign up to leave a comment.
Поиск похожих документов с MinHash + LHS