В настоящее время я пытаюсь найти K ближайших соседей всех узлов сбалансированного KD-дерева (с K=2).
Моя реализация представляет собой вариант кода из статьи Википедии, и найти KNN довольно быстро любого узла O(log N).
Проблема заключается в том, что мне нужно найти KNN каждого узла. Получается около O(N log N), если я перебираю каждый узел и выполняю поиск.
Есть ли более эффективный способ сделать это?
В зависимости от ваших потребностей, вы можете поэкспериментировать с приблизительными методами. Для получения дополнительной информации ознакомьтесь с работой Арьи и Маунта по этому вопросу. Ключевой документ находится здесь. Подробная информация о сложности BigO находится в их документе '98.
Ниже представлена графическая иллюстрация работы:
Источник: http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif
Я использовал их библиотеку для очень многомерных наборов данных с сотнями тысяч элементов. Это быстрее, чем что-либо еще, что я нашел. Библиотека поддерживает как точный, так и приблизительный поиск. Пакет содержит несколько утилит CLI, с помощью которых вы можете легко экспериментировать с вашим набором данных; и даже визуализировать kd-дерево (см. выше).
FWIW: я использовал привязки R.
Из руководства ANN:
... это было показано Арьей и Маунтом [AM93b] и Арьей и др. [AMN+98] что, если пользователь готов допустить небольшую ошибку в поиске (возвращая точку, которая может не быть ближайшим соседом, но не намного дальше от точки запроса, чем истинный ближайший сосед), тогда можно добиться значительного улучшения времени работы. ANN — это система для точного и приблизительного ответа на запросы ближайших соседей.
Я использовал дерево покрытия для этой проблемы. Вот ссылка: http://hunch.net/~jl/projects/cover_tree/cover_tree.html
В наборе данных размером 50M (все запросы kNN, k = 100) создание дерева покрытия заняло 5,5 с, а запрос — 120 с. Анне Либ потребовалось 3,3 с для создания дерева и 138 с для запросов.
обновлено: ближайший сосед не является симметричным отношением. Рассмотрим это: A(0,0) B(1,0) C(3,0). B является ближайшим к C, а C не является ближайшим к B
Если сами узлы являются точками запроса, время поиска может быть меньше. Вы можете начать с этапа возврата, и первые протестированные узлы уже находятся рядом с точкой запроса. Тогда большие участки дерева можно обрезать в ближайшее время.
Ближайший сосед является симметричным отношением (если n1 является ближайшим соседом n2, то же самое относится и к n2), поэтому вам нужно искать только половину узлов, пропуская все узлы, уже отмеченные как ближайшие соседи. Просто идея.
Вы также можете попробовать поиск KD-Tree BBF (Best-Bin First), который поможет вам быстрее найти ближайшие узлы (бины). Я реализовал это на C#, поэтому напишите мне, если вас интересует исходный код.
Конечно, фактическое время работы зависит от размерности, структуры KD-дерева и распределения точек в вашем наборе данных.
Кластеризация точек также может быть уместной.
Термин для поиска: knn join. Точнее, вы, вероятно, хотите сделать самосоединение.
Возможно, эти результаты поиска помогут:
Я видел алгоритмы соединения knn только для R*-дерева. Однако в моих собственных экспериментах они не смогли превзойти повторный запрос. Возможно, мне не хватает некоторых идей реализации. Но в целом правильно хранить данные для соединения дерева гораздо сложнее, чем для одного запроса knn.
