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