Хеширование с учетом местоположения (LSH) — это эффективный метод приблизительного поиска по сходству.,Он широко используется в сценариях, где необходимо обрабатывать крупномасштабные наборы данных. В современном мире, управляемом данными,Эффективный поиск алгоритмов сходства необходим для поддержания деловых операций.,Они лежат в основе технологических стеков многих ведущих компаний.

Основная проблема при поиске по сходству — обработка огромного размера данных. Многие предприятия ежедневно обрабатывают от миллионов до миллиардов точек данных. Например, имея 100 миллионов точек данных, сравнивать их одну за другой очевидно непрактично.

Если пойти еще дальше, предприятиям нужно гораздо больше, чем просто один поиск. Возьмем, к примеру, Google, который обрабатывает более 3,8 миллиона поисковых запросов в минуту. Такая высокая частота запросов на поиск в сочетании с размером точек данных создает огромную техническую проблему.

Кроме того, не были учтены размерность данных или сложность функции сходства. Сочетание этих факторов делает невозможным комплексный поиск больших наборов данных.

Так,Как это сделать в таком невообразимом масштабе?данные Эффективен на съемочной площадкепоиск Шерстяная ткань？Ответ приблизительныйпоиск。проходитьприблизительныйпоиск,Нет необходимости проводить исчерпывающее сравнение каждой пары точек данных. Напротив,Использование технологии LSH,Метод аппроксимации отфильтровывает потенциальные совпадения.,Это значительно уменьшает количество точек данных, которые необходимо детально сравнить.

Таким образом, LSH не только повышает эффективность поиска, но и сохраняет точность результатов поиска, что делает его идеальным решением для поиска по сходству в крупномасштабных наборах данных.

Хеширование с учетом местоположения (LSH)

LSH — это широко используемый метод приближенного ближайшего соседа (ANNS). Он основан на специальной хеш-функции.,Эта функция предназначена для сопоставления похожих элементов в одном хеш-ведре. столкнуться с огромным набором данных,LSH использует хеш-функцию, распределяющую элементы по разным сегментам.,Тем самым упрощая процесс поиска.

Ключевой особенностью алгоритма LSH является то, что он отличается от обычных хеш-функций. Традиционные хэш-функции стремятся свести к минимуму хеш-коллизии, в то время как алгоритм LSH намеренно увеличивает вероятность хеш-коллизий с целью группировки похожих элементов вместе.

«Сравнение хеш-функций：На рисунке выше показаны эффекты двух хэш-функций.。вершина（синий）Хэш-функция стремится минимизировать хеш-коллизии.,Хэш-функция внизу (пурпурный) используется LSH.,Его цель — максимизировать коллизии хешей между похожими элементами.

В LSH похожие векторы имеют тенденцию давать одно и то же значение хеш-функции и поэтому группируются в одну и ту же корзину. Напротив, ожидается, что разнородные векторы не будут относиться к одному и тому же сегменту.

Используйте ЛШруководитьпоиск

Процесс поиска LSH включает в себя следующие три этапа:

1. индексный вектор：первый,Обработка всех векторов с использованием хеш-функции LSH,и индексировать их в соответствующие хеш-корзины.
2. Вектор хэш-запроса：При введении Вектор запросачас,Обработайте его, используя ту же хэш-функцию LSH.
3. сравнение ведер：Затем,провести сравнение расстояния по Хэммингу для идентификации вектора запроса Какие векторы хеш-корзины наиболее близки к。

Эти шаги составляют основу методологии LSH, и эти концепции будут изучены более глубоко и подробно в последующих статьях.

Примерный эффект

Прежде чем углубляться в технологию LSH,Важно осознать,перенести векторы карт в хэш-вектор низкого разрешения,На самом деле это приближение. Этот подход означает, что процедура поиска не может полностью сравнивать каждый вектор.,Поэтому ожидается, что точность поиска снизится.

“Сжатие потенциально очень больших плотных векторов в сильно сжатые двоичные векторы.,Для достижения более высокой скорости поиска. Хотя это сжатие приносит в жертву определенное количество качества.,Но это значительно повышает эффективность поиска.

Выбор метода

Существует несколько реализаций LSH, каждая из которых использует разные методы построения хеша и меры расстояния или сходства. Я не буду здесь вдаваться в подробности, поскольку разные версии подходят для разных сценариев применения.

Двумя наиболее популярными реализациями LSH являются:

• Шардинг документа, MinHashing и Striped LSH：Это более традиционный вариантLSHметод,Подходит для определенных типов наборов данных и запросов.
• Случайная гиперплоскость со скалярным произведением и расстоянием Хэмминга：Этот видметодиспользовать Случайные гиперплоскости для построения хеш-функций,ипроходитьскалярное произведениеи Хэмминграсстояниеизмерить сходство между векторами。

Эта статья будет посвящена представлению метода стохастической гиперплоскости, который не только более широко используется, но и реализован в нескольких популярных библиотеках, таких как Faiss. Этот метод получил широкое внимание как в промышленности, так и в научных кругах благодаря своей высокой эффективности и простоте реализации.

Случайные гиперплоскости

Метод стохастической гиперплоскости, хотя и звучит просто, на самом деле является эффективным методом выполнения приближенного поиска ближайших соседей в многомерных пространствах. Этот подход может быть трудным для понимания, но на следующем примере вы сможете более подробно понять, как он работает.

используется здесьSift1Mданныенаборруководить Пример。Предположим, у нас есть Вектор запросаxq,Цель — получить из массиваxbДо признанияkближайший сосед。

“возвращаться Вектор запросаxqцель триближайший сосед

Создать гиперплоскость

В методе стохастических гиперплоскостей,проходить Постройте гиперплоскость для сегментированияданныеточка。Каждая гиперплоскость определяется вектором нормали, а точкам данных присваивается значение 0 или 1 на основе скалярного произведения с вектором нормали.

“расположен на положительной стороне гиперплоскостиданныеточкараспространятьценить1,Присвойте значение 0 точке данных на отрицательной стороне.

Ключом к определению того, на какой стороне гиперплоскости лежит точка данных, является вектор нормали к гиперплоскости. Результат скалярного произведения показывает, на какой стороне гиперплоскости лежат точки данных. Если два вектора имеют одинаковое направление, результат скалярного произведения положителен. Если они направлены в разные стороны, результат отрицательный.

“Когда вектор нормали гиперплоскости объединяется с другим вектором +ve При скалярном произведении можно считать, что вектор находится перед гиперплоскостью. для создания -ve Для векторов скалярного произведения ситуация прямо противоположная.

В редком случае, когда два вектора совершенно перпендикулярны (на краю гиперплоскости), скалярное произведение равно 0 — классифицируйте этот случай как отрицательный вектор.

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

“Добавление большего количества гиперплоскостей увеличивает объем позиционной информации, хранящейся в двоичном векторе.。

Проводить использует эти гиперплоскости для проецирования векторов в низкомерное пространство, создавая новый хэш-вектор.

На картинке выше,Используются две гиперплоскости.,На самом деле это может занять больше——Эта функцияпроходитьnbitsОпределение параметра。Если используются четыре гиперплоскости,проходить Воляnbitsустановлен на4。

Нормальный вектор Создать гиперплоскость в Python.

nbits = 4  # количество гиперплоскостей
d = 2  # Размеры вектора

import numpy as np
# Создайте набор случайных нормальных векторов
plane_norms = np.random.rand(nbits, d) - .5
plane_norms

array([[-0.26623211,  0.34055181],
       [ 0.3388499 , -0.33368453],
       [ 0.34768572, -0.37184437],
       [-0.11170635, -0.0242341 ]])

проходить np.random.rand Создал группу 0 → 1 Случайно в пределах диапазонаценить。Затемдобавить в-.5сделать массивценить С оригиналомточка (0, 0) как центр. Визуализируйте эти векторы:

“Нормальный вектор, определяющий положение гиперплоскости.,Все с началом координат (0, 0) как центр

хэш-вектор

Учитывая несколько векторов, эти нормальные векторы можно использовать для вычисления их хэшей.

a = np.asarray([1, 2])
b = np.asarray([2, 1])
c = np.asarray([3, 1])

# Вычислить скалярное произведение
a_dot = np.dot(a, plane_norms.T)
b_dot = np.dot(b, plane_norms.T)
c_dot = np.dot(c, plane_norms.T)
a_dot
# array([ 0.41487151, -0.32851916, -0.39600301, -0.16017455])

a_dot = a_dot > 0
b_dot = b_dot > 0
c_dot = c_dot > 0
a_dot

# array([ True, False, False, False])

# Преобразование результата скалярного произведения в двоичное значение
a_dot = a_dot.astype(int)
b_dot = b_dot.astype(int)
c_dot = c_dot.astype(int)
a_dot  # array([1, 0, 0, 0])

b_dot  # array([0, 1, 1, 0])

c_dot  # array([0, 1, 1, 0])

Визуализируя снова, мы получаем три вектора a, b и c и четыре гиперплоскости (перпендикулярно соответствующим нормальным векторам). Взяв значения скалярного произведения +ve и -ve соответственно, мы получаем:

“0Указывает, что вектор находится за плоскостью（-ve скалярное произведение), 1 означает, что вектор находится перед плоскостью (+ve скалярное произведение), объединенное для создания двоичного вектора

LSH использует хэш-вектор для создания сегментов, каждый из которых содержит векторы с одинаковым значением хеш-функции.

vectors = [a_dot, b_dot, c_dot]
buckets = {}
i = 0

for i in range(len(vectors)):
    hash_str = ''.join(vectors[i].astype(str))
    if hash_str not in buckets.keys():
        buckets[hash_str] = []
    buckets[hash_str].append(i)

print(buckets)
# {'1000': [0], '0110': [1, 2]}

Сейчас в процессе поиска,использовать Вектор запроса0111Хэш-значение для быстрого поиска соответствующего сегмента,Затемпроходить Сравнить Хэммингарасстояниечтобы найти ближайшее совпадение。

Используя этот вектор, сравните с каждым сегментом индекс LSH — в этом случае есть только два значения — 1000 и 0110. Используйте расстояние Хэмминга, чтобы найти ближайшее совпадение, которым на самом деле является 0110.

“Хэмминграсстояние,Между первыми двумя векторами имеется четыре несоответствия.,Хэмминграсстояниедля4,Следующие два содержат только одно несоответствие,Хэмминграсстояниедля1

Использование ЛШ Аппроксимация поиска означает, что некоторым качеством поиска можно пожертвовать.,Но это цена за скорость. все сгруппировано по сегментам,Значительно сокращает объем вычислений, необходимых для поиска.

Баланс между качеством и скоростью

При поиске по сходству ключевой задачей является нахождение правильного баланса между качеством и скоростью поиска.

Баланс качества и скорости

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

когда представили Вектор запросаxqи Вычислить его хэшценить（Например0111）час,нашел его с двумя бочками（1000и0110）из Хэмминграсстояниеочень короткий。Этот видметодиз速度非常快,потому чтодляэто займет всего два разарасстояние Расчет завершенпоиск,Но точность сильно снижается,потому чтодлявозможныйвозвращатьсяо70Десять тысяч хешейценитьдля0110образец。

количество ведер

в реальности,еслииспользоватьnbitsценитьдля4,Вы получите 16 возможных ведер:

nbits = 4

# Вычислить количество двоичных комбинаций значений nbits
1 << nbits  # 16

# Распечатайте все возможные сегменты для данного значения nbits.
for i in range(1 << nbits):
    # Получите двоичное представление целого числа, отформатированное в бит nbits.
    b = bin(i)[2:]
    b = '0' * (nbits - len(b)) + b
    print(b, end=' | ')

0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |

Даже при наличии 16 сегментов число сегментов, на которые разделен миллион векторов, по-прежнему очень мало, что приводит к очень неточным выборкам в каждом сегменте.

Увеличить разрешение

Для улучшения качества поиска,Можетпроходить Увеличиватьколичество гиперплоскостей Приходить Увеличиватьразрешение。Больше гиперплоскостей означает бинарные векторы с более высоким разрешением.,Это приводит к более точному векторному представлению.проходитьnbitsзначение для управления этим разрешением。более высокийnbitsценитьпроходить Увеличиватьхэш-векторулучшить разрешениепоисккачество,Но это также может увеличить вычислительные затраты на поиск.

“УвеличиватьnbitsПараметры будут Увеличивать用于构建二进制向量表示изколичество гиперплоскостей

for nbits in [2, 4, 8, 16]:
    print(f"nbits: {nbits}, buckets: {1 << nbits}")

nbits: 2, buckets: 4
nbits: 4, buckets: 16
nbits: 8, buckets: 256
nbits: 16, buckets: 65536

проходить Корректированиеnbitsценить,Можно найти компромисс между качеством и скоростью поиска. в практическом применении,Выберите правильныйnbitsценитьда Достижение эффективного сходствапоискключ。

LSH в Фейссе

Обзор Фаисса

Faiss（Facebook AI Similarity Search) — это платформа с открытым исходным кодом, предназначенная для эффективной реализации поиска по сходству. Он предлагает множество типов индексов, включая IndexLSH, который обсуждался ранее. с учетом местоположения Эффективная реализация (LSH).

Инициализировать индекс LSH

Пример кода для инициализации индекса LSH и добавления данных, установленных в Faiss, выглядит следующим образом:

import faiss

d = wb.shape[1]  # векторные размеры
nbits = 4  # Контролировать разрешение хэш-вектора

# Инициализировать индекс LSH
index = faiss.IndexLSH(d,нбиты)
# Добавить набор данных
index.add(ВБ)

Выполнить поиск

Как только индекс будет готов,Можетиспользоватьindex.search(xq, k)методруководитьпоиск,вxqда Вектор запроса,kданадеятьсявозвращатьсяиз最近匹配数量。

xq0 = xq[0].reshape(1, d)  # Вектор запроса
# поиск ближайших соседей
D, I = index.search(xq0, k=10)
# Возвращает индекс и расстояние до ближайшего соседа
print("Indexes:", I)  # индексная позиция
print("Distances:", D)  # расстояние

Измерение производительности

Используя возвращенный индекс, исходные векторы можно извлечь из набора данных и вычислить их косинусное сходство с вектором запроса.

# Получить исходный вектор
retrieved_vectors = wb[I[0]]
# Вычислить косинусное подобие
cosine_sim = cosine_similarity(retrieved_vectors, xq0)
print("Cosine Similarity:", cosine_sim)

array([[0.7344476 ],
       [0.6316513 ],
       [0.6995599 ],
       [0.20448919],
       [0.3054034 ],
       [0.25432232],
       [0.30497947],
       [0.341374  ],
       [0.6914262 ],
       [0.26704744]], dtype=float32)

из этих исходных векторов,Может ВидетьLSHиндексданетвозвращатьсясвязанные результаты。проходить Измерение Вектор запросаxq0с раньшеkиндивидуальный匹配Из间из余弦相似性Приходитьруководитьэта операция。这индивидуальныйиндекс中有向量应该возвращаться О0.8показатель сходства,Но возвращенный показатель сходства векторов составляет всего 0,2.,Отражает плохую производительность.

Диагностика проблем с производительностью

Если возвращенный показатель сходства низкий, требуется Диагностика. проблем с производительностью。nbitsценить决定了индекс中潜在количество ведер。еслиnbitsустановлен слишком низко,Может привести к тому, что большое количество векторов будет распределено по небольшому количеству сегментов.,Тем самым снижая качество поиска.еслипытаться Воля1Mвекторы Заправлен только16хэш-ведро,Каждое ведро, вероятно, содержит10-100K+векторы。так,При хешировании поискового запроса,это идеально сочетается с этим16одно из ведер——нодаиндекс无法区分被塞进那индивидуальный单индивидуальный桶中из大量向量——У них у всех одинаковоехэш-вектор。МожетпроходитьисследоватьрасстояниеDПриходить确认这一точка：

print(D)
# array([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0.]], dtype=float32)

возвращаться每индивидуальный项目из完美расстояние Фракциядляноль,Хэмминграсстояние Только в идеальном совпадениичасталантдляноль——Это означает, что все этихэш-вектордолженда相同из。если所有из这些向量都возвращатьсяидеальное совпадение,Они оба должны иметь одинаковое значение хеш-функции.。поэтому,Сгенерированный выше индекс не может различить их - что касается индекса LSH.,Они все находятся в одном месте。если Увеличиватьkдовозвращаться一индивидуальный非нольизрасстояниеценить,Должно быть возможно определить, сколько векторов было распределено по одному и тому же хэш-коду.

k = 100
xq0 = xq[0].reshape(1, d)

while True:
    D, I = index.search(xq0, k=k)
    if D.any() != 0:
        print(k)
        break
    k += 100
    
print(D)
print(D[:, 172039:172041])

172100
array([[0., 0., 0., ..., 1., 1., 1.]], dtype=float32)
array([[0., 1.]], dtype=float32)

В одном содержится 172,039векторыиз单индивидуальный桶,это означаетда Отсюда172Kвекторыслучайно выбранныйвпередkиндивидуальныйценить。очевидно,Необходимо уменьшить размер ведра. Для 1 млн образцов,Которыйnbitsценить有足够из桶以实现向量из更稀疏分布,Это вычисляет среднее значение для оценки:

for nbits in [2, 4, 8, 16, 24, 32]:
    buckets = 1 << nbits
    print(f"nbits == {nbits}")
    print(f"{wb.shape[0]} / {buckets} = {wb.shape[0]/buckets}")

nbits == 2
1000000 / 4 = 250000.0
nbits == 4
1000000 / 16 = 62500.0
nbits == 8
1000000 / 256 = 3906.25
nbits == 16
1000000 / 65536 = 15.2587890625
nbits == 24
1000000 / 16777216 = 0.059604644775390625
nbits == 32
1000000 / 4294967296 = 0.00023283064365386963

использоватьnbitsценитьдля16час,Все еще получаю примерно в каждом ведре.15.25векторы——Это выглядит лучше, чем есть на самом деле。Необходимо учитывать, что некоторые сегменты будут намного больше других, поскольку в разных регионах будет больше векторов.на самом деле,nbitsценитьдля24и32возможныйда实现真正有效桶大小из转折точка。

xq0 = xq[0].reshape(1, d)
k = 100

for nbits in [2, 4, 8, 16, 24, 32]:
    index = faiss.IndexLSH(d, nbits)
    index.add(wb)
    D, I = index.search(xq0, k=k)
    cos = cosine_similarity(wb[I[0]], xq0)
    print(np.mean(cos))

0.5424448
0.560827
0.6372647
0.6676912
0.7162514
0.7048228

看起Приходить估计да正确из——вперед100векторыиз整体相似度在每индивидуальныйnbitsценить Увеличивать Извпередвнезапный подъем,Стабилизируйтесь перед точкой.

Поскольку значение nbits увеличивает векторное разрешение, результаты станут более точными.——Может Видеть更大изnbitsценитьчто приводит к более высокому косинусному сходству результатов。

Извлечь двоичный вектор

Faiss позволяет извлекать двоичные представления векторов, что облегчает прямой анализ векторных распределений в сегментах.

# Извлечь двоичный код
arr = faiss.vector_to_array(index.codes)
arr  # array([ 5, 12,  5, ..., 15, 13, 12], dtype=uint8)
arr.shape  # (1000000,)

# Преобразование целого числа в двоичный векторный формат
(((arr[:, None] & (1 << np.arange(nbits)))) > 0).astype(int)

array([[1, 0, 1, 0],
       [0, 0, 1, 1],
       [1, 0, 1, 0],
       ...,
       [1, 1, 1, 1],
       [1, 0, 1, 1],
       [0, 0, 1, 1]])

Этот поток позволяет визуализировать распределение векторов в этих 16 сегментах, показывая наиболее часто используемые сегменты и некоторые пустые сегменты.

“когдаnbits == В 4 часа распределение векторов по разным сегментам

проходить Корректированиеnbitsценить,Можно найти баланс между качеством и скоростью поиска. Используйте ЛШ в Фаиссе,Понимание того, как различные параметры влияют на производительность, имеет решающее значение для оптимизации результатов.

Используйте ЛШ

Хеширование с учетом местоположения (LSH) обеспечивает быстрый механизм индексации.,Хотя он может быть не таким точным, как плоский индекс. На наборе Sift1Mданные,текст постепенно увеличивает размер набора данных,найден вnbitsценитьнастраиватьдля768час,Лучшего запоминания можно достичь, хотя для достижения более высокого запоминания потребуется пожертвовать некоторым временем.

«Напомним и индексный векторное количественное соотношение：Отзыватьдамерапоиск Результат тот же, что ииспользоватьIndexFlatL2руководитьподробныйпоискпоказатели степени соответствия。

Стоит отметить, что,Несмотря на тоиспользоватьnbitsценитьдля768,Скорость поиска LSH лишь немного выше, чем у Flat Index.

«Сравнение времени поиска：Показывает разные размеры индексовиnbitsценить Вниз,Время поиска IndexFlatL2 относительно самого себя меняется при разных условиях.

В практических приложениях более реалистичный целевой показатель полноты составляет около 40 % при сохранении разумного улучшения скорости.。данныеустановить размерипара измеренийLSHоказывает существенное влияние на производительность。随着维度из Увеличивать,Чтобы сохранить точность,возможный需要использовать更高изnbitsценить,Но все же возможно добиться более высокой скорости поиска. Главное — найти правильный баланс для каждого набора вариантов использования. Поиск векторного сходства – это разнообразная область.,Плоская индексация и LSH — лишь два из многих вариантов. Выбор правильной стратегии индексирования требует сочетания экспериментов и опыта.

При поиске по сходству всегда необходимо найти баланс между различными вариантами индексации и настройками параметров.

Подвести итог

Выбор правильного алгоритма поиска по сходству зависит от множества факторов, включая размер и размерность набора данных, требования к производительности поиска и допуск к точности. LSH — один из многих инструментов, который хорошо работает в определенных ситуациях, но для достижения наилучших результатов его, возможно, придется сочетать с другими методами. Помимо LSH, существует множество других алгоритмов, подходящих для эффективного поиска по сходству, например:

• HNSW（Hierarchical Navigable Small Мир): обеспечивает возможность аппроксимации поиска ближайшего соседа в больших наборах данных.
• IVF（Inverted File Индекс): применение кластеризации и индекс уменьшает диапазон поиска и увеличивает скорость поиска.
• PQ（Product Квантование): метод квантования, который делит векторное пространство на более мелкие подпространства для ускорения процесса.

Читателям предлагается экспериментировать и исследовать информацию, представленную в этой статье, чтобы найти алгоритм поиска, который лучше всего соответствует их конкретным потребностям.

ссылка

• locality-sensitive-hashing-random-projection
• https://youtu.be/8bOrMqEdfiQ
• https://youtu.be/ZLfdQq_u7Eo
• Jupyter Notebooks