Выбор между SimHash и MinHash для производственной системы
Я знаком с техниками LSH (локально-чувствительное хеширование) SimHash и MinHash. SimHash использует косинусное сходство с реальными данными. MinHash вычисляет сходство сходства по двоичным векторам. Но я не могу решить, какой из них будет лучше использовать.
Я создаю бэкэнд-систему для веб-сайта, чтобы найти почти дубликаты полуструктурированных текстовых данных. Например, каждая запись будет иметь название, местоположение и краткое текстовое описание (<500 слов).
Если не учитывать конкретную языковую реализацию, какой алгоритм будет наилучшим для производственной системы с нуля?
2 ответа
Simhash is faster (very fast) and typically requires less storage, but imposes a strict limitation on how dissimilar two documents can be and still be detected as duplicates. If you are using a 64-bit simhash (a common choice), and depending on how many permuted tables you are capable of storing, you might be limited to hamming distances of as low as 3 or possibly as high as 6 or 7. Those are small hamming distances! You'll be limited to detecting documents that are mostly identical, and even then you may need to do some careful tuning of what features you choose to go into the simhash and what weightings you give to them.
Генерирование симашей запатентовано Google, хотя на практике они позволяют по крайней мере некоммерческое использование.
Minhash использует больше памяти, поскольку вы, как правило, сохраняете 50-400 хешей для каждого документа, и он не так эффективен с точки зрения использования процессора, как simhash, но он позволяет вам находить довольно отдаленные сходства, например, приблизительное сходство до 5%, если вы хочу. Это также немного легче понять, чем simhash, особенно с точки зрения работы таблиц. Это довольно просто реализовать, как правило, с использованием шинглинга, и не требует большой настройки, чтобы получить хорошие результаты. Это (насколько мне известно) не запатентовано.
Если вы имеете дело с большими данными, наиболее ресурсоемкая часть подхода minhash, вероятно, будет после того, как вы сгенерировали minheshes для своего документа, когда вы просматриваете свою таблицу, чтобы найти другие документы, которые разделяют некоторые из ее хэши. Там могут быть десятки или сотни тысяч документов, которые разделяют по крайней мере один хэш, и вам нужно просмотреть все эти, чтобы найти те немногие, которые разделяют, например, минимум половину его хешей. Симхаш здесь намного быстрее.
Как отмечает Отмар в своем комментарии ниже, есть оптимизации minhash, которые позволяют вам достичь той же точности при оценке сходства с меньшим количеством хешей на документ. Это может существенно уменьшить количество прополки, которую вы должны сделать.
Редактировать:
Я сейчас попробовал суперминхэш. Это довольно быстро, хотя моя реализация minhash, использующая одну хеш-функцию плюс битовые преобразования для получения всех остальных хешей, была быстрее для моих целей. Он предлагает более точные оценки jaccard, примерно на 15% лучше в некоторых ситуациях, которые я тестировал (хотя почти нет разницы в других). Это должно означать, что вам нужно примерно на треть меньше хешей для достижения той же точности. Хранение меньшего количества хэшей в вашей таблице означает, что для выявления почти дубликатов требуется меньше "прополки", что обеспечивает значительное ускорение. Я не знаю ни одного патента на superminhash. Спасибо, Отмар!
Эта статья может дать вам некоторые идеи о двух алгоритмах.