Это первый день моего участия в ноябрьском испытании обновлений, подробности о мероприятии:Вызов последнего обновления 2021 г.
Супер подробное и простое для понимания введение в алгоритм min-hash [1]
Супер подробное и простое для понимания введение в алгоритм min-hash [2]
Супер подробное и простое для понимания введение в алгоритм min-hash [3]
Введение в алгоритм LSH
Прежде чем представить алгоритм min-hash, мы должны сначала кратко представить концепцию LSH (Locality Sensitive Hashing).
LSH(Местозависимое хеширование) алгоритмПриблизительный алгоритм поиска ближайшего соседаОдним из самых популярных и наиболее популярных объяснений приближенного поиска ближайшего соседа является поиск целевого объекта, похожего на указанный объект. В основном используется измножествосбор данныхпохожийДанные могут быть специально применены для обнаружения схожести текста, веб-поиска и других областей.
Алгоритм LSH грубо разделен на три шага:
- Shingling: преобразование текстовых документов в представления коллекций (обычно в логические векторы).
- Минимальное хэширование: преобразование многомерного вектора в низкоразмерную хеш-подпись, а затем вычисление сходства хэш-подписи.
- Хеширование с учетом местоположения: сосредоточьтесь на паре хэш-подписей-кандидатов из похожих документов.
(В приведенных выше трех шагах первый шаг Shingling относится к векторизации текста, что является очень большим аспектом, и ряд объяснений будет раскрыт отдельно позже.)
Теперь мы можем знать, что алгоритм min-hash является шагом в алгоритме LSH, и его основная задача состоит в том, чтобы преобразовать входной многомерный вектор (возможно, миллионы измерений или даже больше) в низкоразмерный вектор (размерно уменьшенный вектор). ), называемая цифровой подписью), а затем вычислить подобие низкоразмерного вектора, чтобы снизить вычислительные затраты и повысить эффективность работы.
Зная цель Min-Hash, что нам нужно сосредоточиться на следующем, заключается в том, насколько Мин-хэш достигает вышеупомянутых требований.
Расстояние Жаккара
Не паникуйте, прежде чем мы официально приступим к объяснению алгоритма min-hash, мы должны изучить очень важную концепцию, а именно расстояние Жаккара.
Мы знаем, что существует множество способов измерения сходства двух множеств, таких как евклидово расстояние, косинусное сходство и т. д. Расстояние Жаккрада также является одним из методов измерения сходства множеств.Основная формула выглядит следующим образом:
Здесь мы объявляем понятие «множество» (то есть Ci, Cj в формуле), которое было упомянуто выше, вы можете думать о нем как о столбце в матрице, а строка представляет элементы в наборе (вы может использовать его для представления чего угодно в природе, в любом случае, он должен быть преобразован в логический вектор).
Например:
Понятие расстояния Жаккара, как упоминалось выше, является несложным понятием.
Хотя расстояние Жаккара само по себе является несложным понятием, однако по мере увеличения размерности множества вычислительные затраты на вычисление расстояния Жаккара между множествами также увеличиваются в геометрической прогрессии, поэтому мы должны задуматься над проблемой: как уменьшить сложность операция Тратить?
Помните цель алгоритма min-hash, упомянутого в последнем абзаце предыдущего раздела, да,Алгоритм min-hash представляет собой усовершенствованную версию расстояния Жаккара с функцией уменьшения размерности, улучшенной на основе расстояния Жаккара..
Что ж, с пониманием вышеизложенных понятий теперь мы можем официально приступить к изучению алгоритма min-hash.