Эффективный способ для нахождения KNN всех узлов в KD-дереве
Я в настоящее время пытаюсь найти Ближайшего Соседа K всех узлов сбалансированного KD-дерева (с K=2).
Моя реализация является изменением кода из статьи Wikipedia, и это прилично быстро для нахождения KNN любого узла O (зарегистрируйте N).
Проблема связана с тем, что я должен найти KNN каждого узла. Придумывая о O (N регистрируют N), если я выполняю итерации по каждому узлу и выполняю поиск.
Существует ли более эффективный способ сделать это?
1 ответ
В зависимости от ваших потребностей , вы можете поэкспериментировать с приблизительными методами. Для получения подробной информации ознакомьтесь с работой Арьи и Маунта по этому вопросу. Ключевой документ здесь . Детали сложности BigO можно найти в их статье '98 .
Графическая иллюстрация работы приведена ниже:
Источник: http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif
Я использовал их библиотека на очень многомерных наборах данных с сотнями тысяч элементов. Это быстрее, чем все, что я нашел. Библиотека обрабатывает как точный, так и приблизительный поиск. Пакет содержит несколько утилит CLI, которые вы можете использовать, чтобы легко экспериментировать с вашим набором данных; и даже визуализировать kd-дерево (см. выше).
FWIW: Я использовал привязки R .
Из руководства ИНС:
... это было показано Арьей и Маунтом [AM93b] и Арьей и др. [AMN + 98], что , если пользователь готов допустить небольшую ошибку при поиске (возврат точки, которая может не быть ближайший сосед, но не значительно дальше от точки запроса , чем истинный ближайший сосед), то можно добиться значительных улучшений в {{ 1}} время работы. ИНС - это система для точных и приближенных ответов на запросы ближайшего соседа .