Дерево K-d
-
Описание k-d деревьев
- k-d деревья — это бинарные деревья, где каждый узел представляет k-мерную точку.
- Каждый узел генерирует разделяющую гиперплоскость, делящую пространство на полупространства.
- Гиперплоскость перпендикулярна оси измерения, связанного с узлом.
-
Построение k-d деревьев
- Существует множество способов выбора плоскостей разбиения.
- Канонический метод использует медиану точек для создания сбалансированного дерева.
- Альтернативные алгоритмы предварительно сортируют данные перед построением дерева.
-
Добавление элементов
- Добавление точки аналогично добавлению элемента в дерево поиска.
- Добавление может привести к разбалансировке дерева, что требует повторной балансировки.
-
Удаление элементов
- Удаление точки требует формирования набора вершин и листьев и воссоздания части дерева.
- Другой подход — поиск замены удаленной точке.
-
Балансировка k-d деревьев
- Балансировка требует осторожности, так как k-d деревья сортируются по нескольким измерениям.
- Существуют различные варианты сбалансированных k-d деревьев, такие как разделенное k-d-дерево и псевдо-k-d-дерево.
-
Поиск ближайшего соседа
- Алгоритм поиска ближайшего соседа рекурсивно перемещается по дереву, проверяя узлы на близость к заданной точке.
- Алгоритм может быть расширен для поиска k ближайших соседей или для аппроксимации.
-
Определение ближайшего соседа
- Отказ от обновления уточнения для узлов с нулевым расстоянием
- Отбрасывание точек, не уникальных, но близких к исходной точке
- Приближенный ближайший сосед полезен в реальном времени
-
Поиск по диапазону
- Поиск по диапазонам параметров
- k-d деревья полезны для поиска по диапазону
- Наихудшее время поиска диапазона в k-мерном k-d дереве
-
Снижение производительности при высокой размерности
- Нахождение ближайшей точки требует O(log(n)) времени
- В пространствах с высокой размерностью алгоритм посещает больше ответвлений
- При n ≫ 2^k эффективность не выше, чем при исчерпывающем поиске
-
Снижение производительности при удаленности точки запроса
- В малоразмерном пространстве производительность ухудшается при большом расстоянии между точками
- Можно задать параметр максимального расстояния для сокращения рекурсивного поиска
-
Сложность и операции
- O(n log2 n) для нахождения медианы на каждом уровне
- O(n log n) для выбора медианы с использованием алгоритма O(n) медиана из медиан
- O(kn log n) для предварительно отсортированных точек
- Вставка и удаление точек занимают O(log n) времени
- Запрос диапазона занимает O(n1-1/k +m) времени
- Поиск 1 ближайшего соседа занимает O(log n) времени
-
Вариации и связанные структуры
- Объемные объекты: прямоугольники или гиперпрямоугольники
- Указывает только на листья: точки хранятся в листьях, различные механизмы разбиения
- Скользящая средняя точка: разделение посередине при наличии точек, иначе в ближайшей точке
-
Связанные структуры и проблемы
- Quadtree, октодерево, шаровое дерево, иерархия R-дерева и ограничивающих интервалов
- Дерево точек обзора: гиперсферы вместо гиперплоскостей
- Рекурсивное разбиение, задача измерения Клее, задача гильотины
-
Реализации с открытым исходным кодом
- ALGLIB, CGAL, SciPy, scikit-learn