Анализ алгоритмов шинлинга и случайной проекции

В предыдущей статье мы обсуждали сходство последовательностей через расстояние Левенштейна и оценивали его при O(m*n). Поскольку мы пытаемся применить этот алгоритм к наборам данных большего размера и масштаба, он становится непрактичным. Варианты использования, которые следует здесь рассмотреть, — это индексация веб-страниц поисковыми системами и плагиат. В поисковых системах важно обнаруживать близкие дубликаты и оценивать их на наличие обновлений страниц, зеркал, спама, фишинговых сайтов и уменьшать количество ошибок сканирования.

Допустим, мы хотим обнаружить строгие дубликаты — в информатике есть очень быстрый метод, с которым мы уже знакомы, — хеширование. Но что, если я хочу обнаружить почти дубликаты? Изменение одного символа полностью изменило бы вывод алгоритма хеширования.

Черепица (Бродер и др., 1997)

Shingling, также называемый w-shingling, представляет собой метод сравнения сходства между двумя последовательностями как перекрывающимися n-граммами в неупорядоченных наборах. Например, последовательность «варианты использования, которые мы будем оценивать» в виде перекрывающихся триграмм будет {«варианты использования, которые мы будем», «варианты, которые мы будем»,…}. Затем мы используем коэффициент Жаккара, чтобы описать разницу между этими двумя наборами, то есть перекрытие двух наборов, нормализованных объединением. Ваш вывод будет ограничен [0,1]

Обратите внимание, что ограничением для сшивания является то, что локальный порядок сохраняется, а глобальный нет. Могут быть случаи, когда элементы в документе перемещаются, а ваше сходство остается таким же, когда вы хотите показать математическую разницу. Время выполнения черепицы составляет O(m+n) по сравнению с O(n*m) для расстояния Левенштейна.

Шаги

  1. Маркировать две входные последовательности
  2. Создайте n-граммы из последовательностей
  3. Вернуть сходство Жаккара между двумя последовательностями

Реализация Python

Я также включил код для подобия Jaccard. Обратите внимание, что вы можете передать ему значение длины n граммов, которые вы хотите создать. Я бы поэкспериментировал между 2 и 5 для последовательностей, которые вы проходите.

Оптимизация: алгоритмы случайной проекции, MinHash

MinHash и локальное хеширование чувствительности — это два способа улучшить анализ различий между двумя последовательностями. Например, использование shingling и Jaccard для сравнения документов в папке имеет верхнюю границу O (N²/2), поскольку нам не нужно сравнивать doc[0] ‹› doc[1] и doc[1] ‹› doc [0], это то же вычисление. MinHash — это приближенный алгоритм для сравнения двух документов, который работает намного быстрее, чем простое сглаживание и сходство Жаккара.

Алгоритм

  1. Создайте подпись MinHash, которая всегда будет одинаковой длины независимо от длины набора.
  2. Случайным образом перемешайте предметы в 2 наборах
  3. Сравните первое значение в каждом наборе: hashed_a[0] == hashed_b[0]

Ключевым моментом здесь является то, что подписи MinHash намного короче, чем количество шинглов в документе. Более интуитивно, мы можем думать о вероятности того, что первый элемент после хэширования будет таким же, как и при разбиении, и получит сходство двух наборов по Жаккару.

Пример

vec_a[3, 10, 7], vec_b[9, 3, 11]

У нас есть один общий элемент, каковы шансы после перетасовки, что «3» будет первым элементом в векторе?

Установите здесь сходство 1/3, а для MinHash это будет количество компонентов, умноженное на вероятность совпадения, что будет таким же, как сходство Жаккара. Мы ожидаем, что сходство MinHash приблизительно соответствует сходству Jaccard.

Рекомендации

Повышение уровня кодирования

Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:

  • 👏 Хлопайте за историю и подписывайтесь на автора 👉
  • 📰 Смотрите больше контента в публикации Level Up Coding
  • 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"

🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу