Эффективный метод нахождения KNN всех узлов в KD-дереве

Question

В настоящее время я пытаюсь найти K ближайшего соседа из всех узлов сбалансированного дерева KD (с K = 2).

Моя реализация представляет собой вариант кода из статьи Википедии , и довольно быстро можно найти KNN любого узла O (log N).

Проблема заключается в том, что мне нужно найти KNN из каждого узла. Приблизительно O (N log N), если я переберу каждый узел и выполню поиск.

Есть ли более эффективный способ сделать это?

Answer 1

В зависимости от ваших потребностей, вы можете экспериментировать с приблизительными методами. За подробностями обращайтесь к работам Arya и Mount на эту тему. Ключевой документ здесь . Детали сложности BigO находятся в их '98 бумаге .

Графическая иллюстрация работы показана ниже:

^{Источник: http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif}

Я использовал их библиотеку для наборов данных очень большого размера с сотнями тысяч элементов. Это быстрее, чем что-либо еще, что я нашел. Библиотека обрабатывает как точный, так и приблизительный поиск. Пакет содержит некоторые утилиты CLI, которые вы можете использовать, чтобы легко поэкспериментировать с вашим набором данных; и даже визуализировать kd-дерево (см. выше).

FWIW: я использовал R Bindings .

Из руководства ANN:

... это показали Арья и Гора [AM93b] и Arya, et al. [AMN + 98], что если пользователь готов терпеть небольшая ошибка в поиске (возвращая точку, которая не может быть ближайший сосед, но не значительно дальше от точка запроса, чем истинный ближайший сосед) тогда можно добиться значительных улучшений в Продолжительность. ANN - это система для отвечая на запросы ближайшего соседа точно и приблизительно.

Answer 2

Я использовал дерево покрытия для этой проблемы. Вот ссылка: 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

Answer 3

Если сами узлы являются точками запроса, тогда время поиска может быть меньше. Вы можете начать со стадии возврата, и первые проверенные узлы уже находятся рядом с точкой запроса. Тогда большие участки дерева могут быть скоро обрезаны.

Ближайший сосед - это симметричное отношение (если n1 - ближайший сосед n2, то же самое относится и к n2), поэтому вам нужно искать только половину узлов, пропуская все узлы, уже отмеченные как ближайшие соседи. Просто идея.

Вы также можете попробовать поиск KD-Tree BBF (Best-Bin First), который поможет вам быстрее искать ближайшие узлы (ячейки). Я реализовал это в C #, поэтому напишите мне, если вы заинтересованы в исходном коде.

Конечно, фактическое время выполнения зависит от размерности, структуры KD-дерева и распределения точек в вашем наборе данных.

Группировка точек также может быть уместной.

Answer 4

Термин для поиска: knn join . Точнее, вы, вероятно, хотите сделать самостоятельное соединение.

Может быть, эти результаты поиска помогут:

• http://scholar.google.com/scholar?q=k-d-tree+knn+join

Я видел только алгоритмы соединения knn для R * -дерева. Однако в моих собственных экспериментах они не смогли превзойти повторный запрос. Я мог бы пропустить некоторые идеи реализации. Но в целом правильное хранение данных для объединения в дерево гораздо сложнее, чем один запрос knn.