Поиск ближайших соседей с помощью иерархического маленького мира

Иерархический маленький мир (англ. Hierarchical Navigable Small World) — структура данных, позволяющая эффективно находить K почти что ближайших соседей. По своей концепции напоминает список с пропусками.

Маленький мир

Жадный поиск ближайшего соседа. Чёрные ребра — короткие связи с ближайшими соседями, красные рёбра — длинные связи, обеспечивающие малое мат. ожидание длины пути. Оригинал

Маленький мир (англ. Small World) — граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально [math]\log{N}[/math]. Но при этом средняя степень вершины мала.

Для маленького мира на точках в Евклидовом пространстве жадный поиск K ближайших соседей будет выглядеть так:

knn(V, E, request, m, k):
    W = [math]\emptyset[/math]  // ближайшие к q вершины 
    C = [math]\emptyset[/math]  // вершины, которые предстоит посетить 
    V = [math]\emptyset[/math]  // посещённые вершины 
    for i = 1 to m
        C = С [math]\bigcup[/math] [math]random_v[/math] v [math]\in[/math] G
        TN = [math]\emptyset[/math]  // ближайшие вершины в этом проходе
        while true
            u = {q1 | [math]\forall[/math] q2 [math]\in[/math] C, |q - q1| < |q - q2|}
            C = C [math]\setminus[/math] u
            if u дальше чем k-й элемент W
                break
            for e: (u, e) in G
                if e [math]{\notin}[/math] V
                    C = C [math]\bigcup[/math] e
                    V = V [math]\bigcup[/math] e
                    TN = TN [math]\bigcup[/math] e
        W = W [math]\bigcup[/math] TN
    return k первых вершин из W

Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает.

Описание структуры

Иерархический Маленький мир (англ. Hierarchical Navigable Small World) — слоистая структура графов. На нулевом слое представлены все N вершин из исходной выборки. Вершина, присутствующая на уровне L так же присутствует на уровне L + 1 с вероятностью P. Т.е. кол-во слоёв растет как [math]O(\log N)[/math]. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за [math]O(\log N)[/math].

Иерархический маленький мир. Источник

Операции над структурой

Поиск ближайших соседей в слое

Жадно идём по уровню в сторону запроса.

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

Поиск ближайших соседей во всей структуре

Жадный поиск вершины. Оригинал

Жадно ищем ближайшего соседа на каждом уровне, кроме 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

См. также

Метрический классификатор и метод ближайших соседей
Иерархическая кластеризация

Источники информации

Статья на википедии о маленьких мирах