Поиск ближайших соседей с помощью иерархического маленького мира — различия между версиями
Marsermd (обсуждение | вклад) |
Marsermd (обсуждение | вклад) (→См. также) |
||
Строка 114: | Строка 114: | ||
== См. также == | == См. также == | ||
[[Метрический классификатор и метод ближайших соседей]]<br /> | [[Метрический классификатор и метод ближайших соседей]]<br /> | ||
− | |||
== Примечания == | == Примечания == | ||
== Источники информации == | == Источники информации == | ||
[https://en.wikipedia.org/wiki/Small-world_network Статья на википедии о маленьких мирах] | [https://en.wikipedia.org/wiki/Small-world_network Статья на википедии о маленьких мирах] |
Версия 00:41, 2 марта 2019
Иерархический маленький мир (англ. Hierarchical Navigable Small World) — структура данных, позволяющая эффективно находить K почти что ближайших соседей. По своей концепции напоминает список с пропусками.
Содержание
Маленький мир
![](/wiki/images/thumb/2/27/SmallWorld_Greedy.png/500px-SmallWorld_Greedy.png)
Маленький мир (англ. Small World) — граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально
. Но при этом средняя степень вершины мала.Для маленького мира на точках в Евклидовом пространстве жадный поиск 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)
Жадно ищем ближайшего соседа на каждом уровне, кроме 0. Когда находим, спускаемся через него на уровень ниже. На нулевом уровне жадно ищем 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. Жадно ищем 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, {}})
Применение
См. также
Метрический классификатор и метод ближайших соседей