Пространственные структуры: KD-дерево и расстояния

«Найди ближайшую точку» — кажется простой задачей, но при миллионах точек наивный перебор смертельно медленный. Спасает KD-дерево.

KD-дерево — структура данных, разбивающая пространство на области, чтобы находить ближайшего соседа быстро, не перебирая все точки.

Зачем искать ближайших соседей

Задача «найти k ближайших точек» — основа множества алгоритмов: k-NN-классификация, рекомендации («похожие товары»), кластеризация, обработка облаков точек в 3D-сканировании, поиск похожих изображений по векторам. Везде нужно быстро отвечать: «что рядом с этой точкой?».

Метрики расстояния

Сначала — как мерить «близость». Расстояний несколько:

Метрика	Формула (2D)	Смысл
Евклидово (L2)	√((Δx)² + (Δy)²)	прямая линия «по воздуху»
Манхэттенское (L1)	\|Δx\| + \|Δy\|	путь по сетке улиц
Чебышёва (L∞)	max(\|Δx\|, \|Δy\|)	ходы короля в шахматах

Наивный поиск ближайшего «руками»

Простейший способ — перебрать все точки и запомнить ближайшую. Работает, но это O(n) на запрос:

import math

points = [(1.0, 1.0), (5.0, 4.0), (2.0, 3.0), (8.0, 1.0), (3.0, 5.0)]
query = (2.5, 2.5)

def dist(a, b):
    return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

best = None
best_d = float("inf")
for p in points:
    d = dist(query, p)
    if d < best_d:
        best_d = d
        best = p

print("Ближайшая точка :", best)
print("Расстояние      :", round(best_d, 4))

Вывод:

Ближайшая точка : (2.0, 3.0)
Расстояние      : 0.7071

Идея KD-дерева

Наивный перебор перебирает все точки. KD-дерево делит пространство пополам по очереди по каждой оси (как двоичный поиск, но в нескольких измерениях). При запросе мы спускаемся к нужной области и проверяем лишь немногие точки, отсекая целые ветви, которые заведомо дальше. Поиск ускоряется с O(n) до примерно O(log n) — на миллионе точек это разница между тысячами проверок и десятком.

        разрез по X
        /         \
   x < 4           x >= 4
   /    \          /    \
 разрез по Y     разрез по Y
 ...             ...

Запрос спускается в свою область, проверяет соседние ветви
только если они МОГУТ содержать что-то ближе найденного.

А в SciPy — одна строка

import numpy as np
from scipy.spatial import KDTree, distance

pts = np.array([[1,1],[5,4],[2,3],[8,1],[3,5]], dtype=float)
tree = KDTree(pts)

d, idx = tree.query([2.5, 2.5])      # ближайший сосед
print(idx, pts[idx], round(d, 4))    # 2 [2. 3.] 0.7071

# k ближайших сразу:
dists, idxs = tree.query([2.5, 2.5], k=3)

# матрица всех попарных расстояний:
D = distance.cdist(pts, pts)

Как работает под капотом

Ключ к скорости KD-дерева — отсечение ветвей. Найдя кандидата на расстоянии r, при спуске по дереву мы для каждой неисследованной ветви спрашиваем: «может ли в этой полуплоскости быть точка ближе r?». Если граница разреза дальше r от запроса — вся ветвь отбрасывается без единой проверки точек. Эффект тем сильнее, чем меньше размерность. Важная оговорка: в очень многомерных пространствах (десятки-сотни измерений) KD-дерево вырождается в перебор — это «проклятие размерности», и там используют приближённые методы (LSH, HNSW).

Частые ошибки

Сравнивать корни расстояний без нужды. Чтобы найти ближайшего, достаточно сравнить квадраты расстояний — корень считать необязательно (экономия).
KD-дерево в высокой размерности. При большом числе измерений оно не ускоряет — берите приближённый поиск.
Перестроение дерева на каждый запрос. Дерево строится один раз (O(n log n)), потом отвечает на много запросов; не стройте его в цикле.

Итог

Поиск ближайших соседей — основа k-NN, рекомендаций, обработки облаков точек.
Метрики: евклидова (по воздуху), манхэттенская (по сетке), Чебышёва (по диагонали).
Наивный перебор — O(n); KD-дерево отсекает ветви и даёт ~O(log n).
В SciPy — KDTree и distance.cdist из scipy.spatial.