Поиск ближайших соседей с помощью иерархического маленького мира — различия между версиями
Marsermd (обсуждение | вклад) |
Marsermd (обсуждение | вклад) (→Маленький мир) |
||
Строка 43: | Строка 43: | ||
'''return''' k ближайших к q вершин из W | '''return''' k ближайших к q вершин из W | ||
+ | Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. <br/> | ||
Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает. | Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает. | ||
Версия 01:46, 2 марта 2019
Иерархический маленький мир (англ. Hierarchical Navigable Small World[1]) — структура данных, позволяющая эффективно находить K почти что ближайших соседей.
Ключевая особенность -- вероятностная эвристика для создания соединений на большие расстояния.
По своей концепции напоминает список с пропусками.
Содержание
Применение
Представим себе ситуацию:
- У социальной сети есть 10¹¹ пользовательских фотографий с отмеченными лицами на них.
- По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека.
Возможный процесс:
- Обучаем FaceNet[2] выдавать 128-мерные вектора по изображению лица, т.ч. у фотографий одного человека похожие значения векторов.
- Добавляем 10¹¹ векторов в иерархический маленький мир.
- При добавлении новой фотографии, вычисляем соответствующий лицу вектор
- Ищем K его ближайших соседей.
- Классифицируем лицо использованием ядер сглаживания.
- Если пользователь подтвердил нашу догадку, добавляем этот вектор в иерархический маленький мир.
Маленький мир
![](/wiki/images/thumb/2/27/SmallWorld_Greedy.png/500px-SmallWorld_Greedy.png)
Маленький мир[3] (англ. Small World[4]) — граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально . Но при этом средняя степень вершины мала.
Для маленького мира на точках в Евклидовом пространстве жадный поиск K ближайших соседей будет выглядеть так:
knn(V, E, request, m, k): W =// Ближайшие к q вершины. C = // Вершины, которые предстоит посетить. V = // Посещённые вершины. for i = 1 to m C = С v G TN = // Ближайшие вершины в этом проходе. while true u = {q1 | q2 C, |q - q1| <= |q - q2|} // Ближайшая к q вершина из C C = C u if u дальше чем k-й элемент W break for e: (u, e) in G if e V C = C e V = V e TN = TN e W = W TN return k ближайших к q вершин из W
Расстояние между вершинами графа может измеряться различными метриками.
Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает.
Описание структуры
Иерархический Маленький мир (англ. Hierarchical Navigable Small World) — слоистая структура графов. На нулевом слое представлены все N вершин из исходной выборки. Вершина, присутствующая на уровне L так же присутствует на уровне L + 1 с вероятностью P. Т.е. кол-во слоёв растет как
. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за .![]() Иерархический маленький мир. Источник |
Операции над структурой
Поиск ближайших соседей в слое
Жадно идём по уровню в сторону запроса.
searchLayer(q, ep, ef, layer): // Входные данные: иерархия графов hnsw, запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer. // Возвращает: ef ближайших соседей q в слое layer. W =// Ближайшие к q вершины. C = // Вершины, которые предстоит посетить. V = // Посещённые вершины. while C != u = {q1 | q2 C, |q - q1| <= |q - q2|} // Ближайшая к q вершина из C. f = {q1 | q2 W, |q - q1| >= |q - q2|} // Самая дальняя от q вершина из W. if |u - q| > |f - q| break // Мы в локальном минимуме. for e : (u, e) in G if e V V = V e f = {q1 | q2 W, |q - q1| >= |q - q2|} // Самая дальняя от q вершина из W. if |e - q| < |f - q| or |W| < ef C = C e W = W e if |W| > ef W = W \ f return W
Поиск ближайших соседей во всей структуре
![](/wiki/images/b/be/HnswSearch.png)
- Идём с верхнего уровня до первого:
- Жадно ищем ближайшую к q вершину на текущем уровне.
- Спускаемся в соответствующую соседу вершине на уровень ниже.
- На нулевом уровне жадно ищем k ближайших соседей.
knn(hnsw, q, k, ef): // Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей K, количество кандидатов при поиске ef // Возвращает: k ближайших соседей q W =// ближайшие к q вершины mL = |hnsw| - 1 ep = v hnsw[mL] for level = mL to 1 W = searchLayer(hnsw, q, ep, ef=1, level) // На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. ep = W W = searchLayer(hnsw, q, ep, ef, lc=0) return k ближайших к q вершин из W
Вставка элемента
- Случайным образом выбираем максимальный слой, на котором будет представлена q.
- На каждом уровне, где будет представлена q, сверху вниз:
- Жадно ищем M ближайших к q вершин.
- Добавляем связи q с ними.
- Удаляем лишние связи у новообразовавшихся соседей.
insert(hnsw, q, m, mMax, ef, mL): // Входные данные: иерархия графов hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины // на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. // Возвращает: hnsw с вставленным элементом q. W =// ближайшие к q вершины mL = |hnsw| - 1 ep = v hnsw[mL] qL = -ln(rand(eps, 1.0)) * mL // Верхний слой для вершины q. for level = mL to qL + 1 W = searchLayer(q, ep, ef=1, level) ep = W for level = min(mL, qL) to 0 W = searchLayer(q, ep, ef, level) neighbours = M ближайших к q вершин из W for n neighbours: hnsw[level] = hnsw[level] (n, q) hnsw[level] = hnsw[level] (q, n) nNeighbours = {v| (v, n) in hnsw[level]} // Убираем лишние связи, если требуется. if nNeighbours.Count() > mMax // Самая дальняя от n вершина, смежняя с ней. v = {q1 | (q2, n) nNeighbours & q2 hnsw[level], |q - q1| >= |q - q2|} hnsw[level] = hnsw[level] (n, v) hnsw[level] = hnsw[level] (v, n) ep = W if qL > mL for level = mL to qL hnsw.append({q, {}})
Практическое использование
В библиотеке Hnswlib[5] есть реализация иерархического маленького мира. Эта библиотека написана на C++, с биндингами на python.
Пример использования:
import hnswlib import numpy as np dim = 128 num_elements = 10000 # Создаём тестовые данные. data = np.float32(np.random.random((num_elements, dim))) data_labels = np.arange(num_elements) # Создаём иерархический маленький мир в L2. # Возможные метрики — l2, cosine, ip (L2, косинус угла между векторами, скалярное произведение). p = hnswlib.Index(space = 'l2', dim = dim) # Инициализируем структуру. p.init_index(max_elements = num_elements, ef_construction = 200, M = 16) # Добавляем данные (можно вызывать много раз). p.add_items(data, data_labels) # Настраиваем качество, выставляя ef: p.set_ef(50) # ef должно быть > k # Делаем запрос. # k - количество юлижайших вершин labels, distances = p.knn_query(data, k = 1)
См. также
Метрический классификатор и метод ближайших соседей
Список с пропусками
Примечания
Поиск знаменитостей на фотографии с помощью иерархического маленького мира