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