Требуется разъяснение о мин / сим-хешировании + LSH

Question

У меня есть разумное понимание методики обнаружения похожих документов, состоящей в том, чтобы сначала вычислить их сигнатуры minhash (из их черепицы или n-грамм), а затем использовать алгоритм на основе LSH для их эффективной кластеризации (то есть избежать квадратичной сложности, которая могла бы влечет за собой наивный попарный исчерпывающий поиск).

Я пытаюсь соединить три различных алгоритма, которые, я думаю, все связаны с этой структурой minhash + LSH, но неочевидными способами:

(1) Алгоритм, описанный в разделе 3.4.3 главы 3 книги "Добыча массивных наборов данных" (Раджараман и Уллман), который, по-видимому, является каноническим описанием хинширования

(2) Простая статья Simhashing Райана Моултона

(3) так называемый алгоритм SimHash Чарикара, описанный в этой статье

Я нахожу это запутанным, потому что я предполагаю, что хотя (2) используется термин "simhashing", на самом деле он выполняет minhashing таким же образом, как (1), но с принципиальным отличием в том, что кластер может быть представлен только одной сигнатурой (могут быть задействованы даже сложные множественные хеш-функции), в то время как два документа имеют больше шансов быть похожими с (1), потому что подписи могут сталкиваться в нескольких "полосах". (3) кажется совершенно другим зверем в том смысле, что сигнатуры сравниваются с точки зрения их расстояния Хэмминга, а метод LSH подразумевает многократную сортировку сигнатур, а не их объединение. Я также видел (где-то еще), что этот последний метод может включать в себя понятие взвешивания, которое может быть использовано, чтобы сделать больший акцент на определенных частях документа и которое, по-видимому, отсутствует в (1) и (2).

Итак, наконец, два моих вопроса:

(а) Есть ли (удовлетворительный) способ преодоления этих трех алгоритмов?

(б) Есть ли способ импортировать это понятие взвешивания из (3) в (1)?

Answer 1

Статья 2 на самом деле обсуждает minhash, но ошибочно называет это simhash. Вероятно, поэтому он сейчас удален (он здесь заархивирован). Также, что сбивает с толку, речь идет о "объединении" нескольких мини-хешей, что, как вы правильно заметили, снижает вероятность нахождения двух похожих документов. Кажется, предписывает подход, который дает только одну "полосу", которая даст очень плохие результаты.

Могут ли алгоритмы быть соединены / объединены?

Возможно нет. Чтобы понять почему, вы должны понимать, каковы свойства различных хешей и как они используются, чтобы избежать n² сравнений между документами.

Свойства minhash и simhash:

По сути, minhash генерирует несколько хешей для каждого документа, и при наличии двух одинаковых документов вполне вероятно, что подмножество этих хешей будет идентичным. Simhash генерирует по одному хешу для каждого документа, и там, где есть два одинаковых документа, вполне вероятно, что их симши будут одинаковыми (с небольшим расстоянием Хэмминга).

Как они решают проблему n²:

С помощью minhash вы индексируете все хэши для документов, которые их содержат; таким образом, если вы храните 100 хешей для каждого документа, то для каждого нового входящего документа вам нужно просмотреть каждый из его 100 хешей в индексе и найти все документы, которые разделяют как минимум (например, 50%) из них. Это может означать создание больших временных списков, так как сотни тысяч документов могут иметь хотя бы один хэш.

В simhash есть умный метод хранения хеша каждого документа в нескольких перестановках в нескольких отсортированных таблицах, так что любой подобный хеш может достигать определенного расстояния Хемминга (3, 4, 5, возможно, до 6 или 7 в зависимости от размера хеша и структура таблицы) гарантированно находится поблизости хотя бы в одной из этих таблиц, отличающихся только младшими битами. Это делает поиск похожих документов эффективным, но ограничивает поиск только очень похожих документов.

Поскольку использование minhash и simhash очень разные, я не вижу способа их объединить / объединить. Теоретически у вас может быть minhash, который генерирует 1-битные хеши и объединяет их в нечто вроде simhash, но я не вижу в этом никакой выгоды.

Можно ли использовать взвешивание в minhash?

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

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

Это не так элегантно, как то, как это делает simhash: фактически вы просто создаете побитовое взвешенное среднее всех хэшей отдельных объектов, затем округляете каждый бит до 1 или до 0. Но это вполне работоспособно.