Супер подробное и простое для понимания введение в алгоритм min-hash [3]

машинное обучение

Это 4-й день моего участия в ноябрьском испытании обновлений.Подробности о событии:Вызов последнего обновления 2021 г.

Супер подробное и простое для понимания введение в алгоритм min-hash [1]

Супер подробное и простое для понимания введение в алгоритм min-hash [2]

Супер подробное и простое для понимания введение в алгоритм min-hash [3]

минимальная хэш-операция

представьте примитивный набор, по которому нам нужно сравнитьсостоит из столбцовматрица, преобразовать эту матрицуПеремешать по очередиОтсортируйте P раз и после каждой перетасовки найдитеПервыйИндекс строки со значением 1 заполняется новым набором (каждый исходный набор имеет свой собственный новый набор), и этот новый набор является хэш-подписью исходного набора. Формула выражается следующим образом:

sig(Ci)=PКусокCiПервое значение после каждого перемешивания столбца равно1значение индекса строки(3)sig(C_i)=P количество столбцов C_i после каждого перетасовки значения индекса строки первого значения 1 \tag 3

Описанная выше операция является минимальной операцией хеширования, возможно, вы все еще немного запутались, ничего страшного, давайте рассмотрим пример.

(пример источника нижеStanford University)

  1. Предположим, что есть три (5,) примитивных множества Ci, которые необходимо сравнить, сначала объедините их в матрицу (5, 3) по столбцам, где Ri представляет номер строки:
  1. Предположим, мы хотим уменьшить размерность до 3-х измерений, то есть уменьшить исходное множество Ci до (3,), затем установить P до 3, то есть выполнить три перетасовки строк:
第一次排序中，我们仍按(12345)的行顺序排序，此时C1的第一个1出现在R1，于是我们将1添加到原始集合C1的数字签名S1中。其他两个集合同理。

第二次排序中，我们按照(54321)的行顺序排序，此时C1的第一个1出现在R4，于是我们再将4添加到原始集合C1的数字签名S1中。其他两个集合同理。

第三次排序操作同第一、二次操作。
  1. Наконец, мы вычисляем коэффициент Жакарра цифровой подписи Si, полученный после операции минимального хеширования над Ci, чтобы получить сходство между наборами (Col_Col — коэффициент Жаккара исходного набора, Sig-Sig — коэффициент Жаккара хеш-подписи, That есть минимальный хеш-коэффициент исходного набора):

Должно быть легко обнаружить, что коэффициент Жаккара и коэффициент минимального хеширования набора, который мы рассчитали в приведенном выше примере, можно назвать только относительно близкими, но не полностью согласованными. Это связано с тем, что размеры трех исходных наборов в этом примере невелики, всего 5 измерений.В практических приложениях наборы, с которыми мы сталкиваемся, обычно имеют миллионы или десятки миллионов измерений.С макро- или статистической точки зрения, коэффициент min-hash равен коэффициенту Жаккара. Это приводит к вопросу, оставшемуся от предыдущего раздела:Как вы думаете, почему расстояние Жаккара между множествами после завершения операции минимального хеширования остается таким же, как расстояние Жаккара между исходными множествами?Для этого вопроса мы доказываем следующее:

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

Теперь рассмотрим только наборы C1 и C2, тогда каждая строка одного и того же набора этих двух столбцов будет иметь следующие три случая:

  1. И C1, и C2 имеют значение 1 в этой строке, и мы подсчитываем, сколько раз это происходит, как X
  2. Один из C1 и C2 имеет значение 1 в этой строке, а другой имеет значение 0. Запишем количество раз этой ситуации как Y
  3. Значение C1 и C2 равно 0, количество повторений этой ситуации записывается как Z.

Очевидно, что в первом случае X представляет собой пересечение множеств C1 и C2, а X+Y представляет собой объединение C1 и C2,

То есть Jaccard(C1,C2) = X/(X+Y) в это время

Затем вычислите min-hash(C1,C2), который равен P[min-hash(C1)=min-hash(C2)]. После того, как случайные строки зашифрованы, просмотрите сверху вниз, вероятность встретить строку X до встречи с строкой Y равна X/(X+Y), то есть вероятность того, что min-hash(C1)=min-hash(C2) равно X/(X+Y).

Почему мы рассчитываем «вероятность попадания в строку X до попадания в строку Y», сканируя сверху вниз? Помните, что мы добавляли к хеш-подписи исходного набора?

(Приведенное выше доказательство относится кStanford UniversityиЭта статья Дестар)

Доказательство немного непонятно, и в преподавании PPT Стэнфордского университета даже прямо используется «неожиданное свойство» для описания этого свойства. Хотя у него есть определенные требования к запасу знаний по теории вероятностей, я считаю, что вы должны быть в состоянии понять это после небольшого размышления.Если у вас есть какие-либо вопросы, вы можете оставить сообщение в области комментариев или напрямую написать мне.

Что ж, это конец нашего объяснения алгоритма min-hash...? нисколько.Помните, для чего мы использовали алгоритм min-hash? Уменьшение размерности! И в чем здесь цель уменьшения размерности? Уменьшите вычислительную сложность!Однако теперь мы столкнулись с проблемой: после перетасовки матрицы получается хэш-подпись для уменьшения размерности, а затем вычисление сходства действительно снижает вычислительную сложность, ноПеретасовка матрицы сама по себе является довольно затратной в вычислительном отношении операцией!

Поэтому в следующем разделе мы представим алгоритм min-hash в реальном практическом применении! Не думайте, что этот раздел напрасный (не учите зря), и алгоритм min-hash в практическом применении тоже основан на знаниях из этого раздела. До встречи в следующем разделе!

Категории