Что такое приблизительный поиск ближайшего соседа и каковы обычно используемые методы
Может кратко объяснить примерный поиск ближайшего соседа (5 баллов)
Часто используемые методы (5 баллов)
Приблизительный поиск ближайшего соседа:
НН и ИНС
NN, поиск ближайшего соседа, задача поиска ближайшего соседа
KNN, K-ближайший сосед, k ближайших соседей, найти k лучших элементов данных, ближайших к целевым данным
ANN, Approximate Nearest Neighbor, приблизительный поиск ближайшего соседа, повышение эффективности поиска за счет точности в допустимых пределах
Поиск ближайшего соседа имеет линейную сложность, и метод ANN можно использовать при работе с крупномасштабными данными.
LSH, локально чувствительное хеширование — это тип ANN.
Часто используемые методы:
LSHалгоритм:
Как искать массивные и многомерные данные:
Если данные малоразмерны и малы => найдите их линейным способом.
Данные не только массивные, но и многомерные => требуется уменьшение размерности, а для поиска используется индексация
LSH, хеширование с учетом местоположения, хэширование с учетом местоположения
Нужно найти 1 или несколько похожих данных на определенные данные
Метод поиска ближайшего соседа (ANN, Approximate Nearest Neighbor)
Для извлечения данных используется традиционная HashTable, и подобные данные не могут быть помещены в один и тот же сегмент Bucket, например h=x mod w.
LSH по-прежнему поддерживает отношения смежности после сопоставления смежных данных, то есть поддерживает локальную чувствительность.
Через Hash Function каждое ведро будет попадать в какие-то исходные данные, а данные, принадлежащие одному и тому же ведру, скорее всего, будут соседними (есть и несмежные данные, которые хешируются в одно и то же ведро)
Исходный набор данных разделен на несколько подмножеств, данные в каждом подмножестве, вероятно, будут смежными, а количество элементов в подмножестве невелико.
Удобно для поиска ближайшего соседа => найти соседние элементы в небольшом наборе
MinHashалгоритм:
Расчет сходства документов:
k-шингл, также известный как k-gram, представляет собой строку произвольной длины k в документе. Каждый документ может быть представлен как набор k-шинглов, которые встречаются в документе один или несколько раз.
Например, document="abcdabd", когда набор 2-гонтов равен {ab,bc,cd,da,bd}
Если два документа похожи, то у них будет много одинаковых черепиц.
Чем длиннее текст, тем больше значение К. Ссылка на эмпирическое значение K, краткий текст K = 5, подробный текст K = 10
Сходство Жаккара
Массивные данные, высокая размерность => Когда матрица очень большая, целевому объекту необходимо найти хеш-функцию для вычисления исходного подобия Жаккара, что эквивалентно вычислению матрицы подобия после уменьшения размерности (Входная матрица => Матрица подписи)
Если сходство Jaccard с исходным документом высокое, то вероятность того, что их хэш-значение будет одинаковым, высока.
Если сходство Jaccard с исходным документом низкое, вероятность того, что их хеш-значения различны, высока. MinHashing (минимальный хэш) для подобия Jaccard
Что такое хэш-функция
Первоначальный расчет сходства Жаккара эквивалентен расчету матрицы подобия после уменьшения размерности (Входная матрица => Матрица подписи).
Если сходство Jaccard с исходным документом высокое, то вероятность того, что их хэш-значение будет одинаковым, высока.
Если сходство Jaccard с исходным документом низкое, вероятность того, что их хеш-значения различны, высока. MinHashing (минимальный хэш) для подобия Jaccard
что такое к-гонт
Также известная как k-gram, строка произвольной длины k в документе. Каждый документ может быть представлен как набор k-шинглов, которые встречаются в документе один или несколько раз.
Например, document="abcdabd", когда набор 2-гонтов равен {ab,bc,cd,da,bd}
Если два документа похожи, то у них будет много одинаковых черепиц.
Чем длиннее текст, тем больше значение К. Ссылка на эмпирическое значение K, краткий текст K = 5, подробный текст K = 10
Минимальное значение хэша
Выполнение MinHash
Как сортировать большие данные => место для хранения, время вычислений
=> Существует несколько хэш-функций, получите номер последней строки через хеш i, если элемент в столбце в это время равен 1, а новый номер строки меньше, чем значение M исходной записи, затем обновите значение M
for each hash function hi do
compute hi (r);
for each column c
if c has 1 in row r
for each hash function hi do
if hi (r) is smaller than M(i, c) then
M(i, c) := hi (r);
Для хеш-функции:
h(x)= x mod 5
g(x)=(2x+1) mod 5
Количество строк + 1, каждый раз, когда выполняются операции функций h и g
Если значение в столбце равно 1, проверьте, меньше ли значение, полученное с помощью Hash, и обновите, если оно меньше.
=> Завершите m перестановок вектора-строки с помощью m хеш-функций для индекса строки (решая проблему перестановки вектора-строки)
MinHashLSH
В дополнение к решению проблемы вычисления подобия между Ci и Cj, когда количество данных велико, количество вычислений сходства между ними составляет
Когда количество данных N велико (> 1 миллиона), объем вычислений очень велик.
=> Разделите потенциально похожих пользователей на одну и ту же корзину с высокой вероятностью, чтобы у каждого пользователя было намного меньше «наборов похожих пользователей-кандидатов», что значительно снижает вычислительную сложность.
LSH - приближенное решение для подобия
На базе MinHash вектор Signature разбит на несколько бэндов (бэндов)
Разделите матрицу подписи на b групп, каждая из которых состоит из r строк.
Хэшируйте каждую группу и задайте для каждой группы разные пространства сегментов. Пока два столбца имеют набор одного и того же MinHash, два столбца будут хешированы в одно и то же ведро и станут кандидатами на похожие элементы.
Предположим, что для строки вероятность того, что два столбца имеют одинаковое значение подписи, равна s (сходство двух столбцов).
В определенной полосе вероятность того, что все значения равны, равна
В определенной полосе вероятность того, что значения не совпадают, равна
Два документа имеют b полос, и вероятность того, что эти b полос различаются, равна
В б полосах по крайней мере одна из одинаковых вероятностей
=> Вероятность того, что два столбца являются кандидатами на аналогичную пару, равна
Называемый методом «И затем ИЛИ», он сначала требует, чтобы все соответствующие элементы каждой полосы были одинаковыми, а затем требует, чтобы по крайней мере одна из нескольких полос была одинаковой. Если эти два условия выполняются, может произойти коллизия хэшей.
Предположим, что s=0,8, 20 полос, 5 рядов на полосу, т.е. b=20, r=5.
В определенной полосе вероятность того, что все значения равны, равна
В определенной полосе вероятность того, что значения не совпадают, равна
Вероятность того, что полосы b различны, равна
В б полосах по крайней мере одна из одинаковых вероятностей
Когда s превышает определенный порог, вероятность того, что два пользователя станут кандидатами в пользователи, быстро возрастает и приближается к 1. Этот порог, при котором вероятность изменяется наиболее резко, приблизительно равен
Сходство MinHash с Jaccard
Строки типа C не влияют на расчет результата и могут быть удалены.
P(h(Ci)=h(Cj))=P (после удаления типа C первая строка является типом A)
=Количество строк типа A/Количество всех строк=a/(a+b)
P(h(Ci)=h(Cj))= Jaccard(Ci,Cj)
Используйте вероятность того, что значения MinHash Ci и Cj равны, чтобы оценить их сходство Жаккара
Поток алгоритма SimHash
Алгоритм SimHash:
Шаг 1, установите количество битов SimHash, например 32 бита, вам необходимо всесторонне учитывать стоимость хранения и размер набора данных.
Шаг 2, инициализируйте SimHash, установите каждый бит в 0
Шаг 3, извлеките функции из текста, например, используя 2-Shingles.
"the cat sat on the mat"=>{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
Шаг 4. Используйте традиционную хэш-функцию для вычисления хэш-кода каждого слова.
Например: "th".hash = -502157718, "he".hash = -369049682, ...
Шаг 5, для каждого бита хэш-кода каждого слова, если бит равен 1, прибавьте его вес (обычно частоту появления) к значению соответствующего бита симхэша, в противном случае вычтите его вес
Шаг 6, вычислите окончательный 32-битный SimHash, если бит больше 1, установите его в 1; в противном случае установите его в 0
Как получить отпечаток каждого документа с помощью алгоритма SimHash
Получите отпечаток каждого документа через алгоритм SimHash (отпечаток пальца)
Вычислите расстояние Хэмминга двух отпечатков пальцев документа
Обычно, если расстояние Хэмминга двух документов находится в пределах 3, сходство считается относительно высоким => два документа в основном одинаковы.