Поиск ближайших соседей с помощью иерархического маленького мира — различия между версиями
Marsermd (обсуждение | вклад) (→Маленький мир) |
Marsermd (обсуждение | вклад) (→Маленький мир) |
||
Строка 8: | Строка 8: | ||
Для маленького мира на точках в Евклидовом пространстве, жадный поиск K ближайших соседей будет выглядеть так: | Для маленького мира на точках в Евклидовом пространстве, жадный поиск K ближайших соседей будет выглядеть так: | ||
− | '''knn'''( | + | '''knn'''(V, E, request, m, k)''':''' |
W = <tex>\emptyset</tex> <font color="green">// ближайшие к q вершины </font> | W = <tex>\emptyset</tex> <font color="green">// ближайшие к q вершины </font> | ||
C = <tex>\emptyset</tex> <font color="green">// вершины, которые предстоит посетить </font> | C = <tex>\emptyset</tex> <font color="green">// вершины, которые предстоит посетить </font> | ||
V = <tex>\emptyset</tex> <font color="green">// посещённые вершины </font> | V = <tex>\emptyset</tex> <font color="green">// посещённые вершины </font> | ||
'''for''' i = 1 '''to''' m | '''for''' i = 1 '''to''' m | ||
− | C = С <tex>\bigcup</tex> | + | C = С <tex>\bigcup</tex> random_v v <tex>\in</tex> G |
TN = <tex>\emptyset</tex> <font color="green">// ближайшие вершины в этом проходе</font> | TN = <tex>\emptyset</tex> <font color="green">// ближайшие вершины в этом проходе</font> | ||
'''while''' ''true'' | '''while''' ''true'' |
Версия 23:37, 1 марта 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 = С random_v v G TN = // ближайшие вершины в этом проходе while true u = {q1 | q2 C, |q - q1| < |q - q2|} C = C u if u дальше чем k-й элемент W break for e : смежные с u вершины if e V C = C e V = V e TN = TN e W = W TN return k первых вершин из W
Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает.
Описание структуры
Иерархический Маленький мир (англ. Hierarchical Navigable Small World) — слоистая структура графов. На нулевом слое представлены все N вершин из исходной выборки. Вершина, присутствующая на уровне L так же присутствует на уровне L + 1 с вероятностью P. Т.е. кол-во слоёв растет как
. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за .![]() Иерархический маленький мир. Источник |
Операции над структурой
Поиск ближайших соседей в слое
Жадно идём по уровню в сторону запроса.
searchLayer(q, ep, ef, layer): // Входные данные: запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer // Возвращает: ef ближайших соседей q в слое layer candidates = new TreeSet(ep) // Вершины упорядочены по возрастанию расстояния до q. result = new TreeSet(ep) visited = new HashSet(ep) while candidates.isNotEmpty() current = candidates.getMin() furthest = result.getMax() if distance(current, q) > distance(furthest, q) break // Мы в локальном минимуме. for v : смежные с current вершины в слое layer if !visited.contains(r) visited.add(v) furthest = result.getMax() if distance(v, q) < distance(furthest, q) or result.count() < ef candidates.add(v) result.add(v) if result.count() > ef result.removeLast() return result
Поиск ближайших соседей во всей структуре
![](/wiki/images/b/be/HnswSearch.png)
Жадно ищем ближайшего соседа на каждом уровне, кроме 0. Когда находим, спускаемся через него на уровень ниже. На нулевом уровне жадно ищем K ближайших соседей.
knn(hnsw, q, K, ef): // Входные данные: граф hnsw, запрос q, искомое количество ближайших соседей K, количество кандидатов при поиске ef // Возвращает: K ближайших соседей q result = new TreeSet() // Вершины упорядочены по возрастанию расстояния до request. ep = случайная вершина из верхнего слоя hnsw maxLevel = индекс самого высокого слоя в hnsw for level = maxLevel to 1 result = searchLayer(q, ep, ef=1, level) // На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. ep = result.getMin() result = searchLayer(q, ep, ef, lc=0) return первые K элементов из result
Вставка элемента
Случайным образом выбираем максимальный слой, на котором представлена q. Жадно ищем M ближайших вершин к q на каждом уровне, на котором она представлена; добавляем связи q с ними; удаляем лишние связи у новообразовавшихся соседей.
insert(hnsw, q, m, mMax, ef, mL): // Входные данные: граф hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины // на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. // Возвращает: hnsw с вставленным элементом q. result = new TreeSet() // Вершины упорядочены по возрастанию расстояния до q. ep = случайная вершина из верхнего слоя hnsw maxLevel = индекс самого высокого слоя в hnsw qLevel = -ln(rand(eps, 1.0)) * mL // Верхний слой для вершины q. for level = maxLevel to qLevel + 1 result = searchLayer(q, ep, ef=1, level) ep = result for level = min(maxLevel, qLevel) to 0 result = searchLayer(q, ep, ef, level) neighbors = searchLayer.getFirst(M) Добавить связи между neighbours и q на уровне level for v : neighbors // Убираем лишние связи, если требуется. vNeighbours = смежные с v на уровне level if vNeighbours.Count() > mMax оставить у v только связи с ближайшими mMax смежными вершинами на уровне level ep = result if qLevel > maxLevel Добавить недостающие слои в hnsw, в каждый из них положить q
См. также
Метрический классификатор и метод ближайших соседей
Иерархическая кластеризация