Сохранение и инкрементное обновление модели ближайшего соседа в R

Существует несколько пакетов ближайшего соседа R (например, FNN, RANN, yaImpute), но ни один из них, похоже, не позволяет сэкономить структуру данных NN (дерево обложек, дерево KD и т.д.), так что ближайшие соседи новых запросов могут рассчитываться без восстановления всего дерева. Существуют ли такие функции в R?

Я ищу функцию, которая возвращает структуру данных, которую я могу обновить по мере поступления новых данных, чтобы выполнить приблизительный поиск ближайшего соседа K.

Ответы

Ответ 1

Существует хорошая причина, почему пакет NN не делает этого.

Причина в том, что "структура данных NN" обязательно включает в себя все входные точки данных (в виде KD tree), поэтому нет экономии пространства для входных данных. Похоже, что было бы экономить время, когда вам не пришлось бы повторно создавать KD-дерево для каждого нового ввода, но это не так, увы.

Причина в том, что время создания KD-дерева в общем случае хуже, чем linearithmic. Это означает, что для больших входов имеет смысл сортировать данные перед построением KD-дерева, поскольку это приведет к быстрому созданию KD-дерева, и оно будет лучше сбалансировано, что также улучшит поиск (это также хуже логарифмического, в целом). Этот подход ускорит моделирование и оценку, но, конечно, будет препятствовать инкрементным обновлениям.

Лучше всего, я думаю, если найти общий пакет KD-tree и использовать его вместо этого.

Ответ 2

Пакет nabor позволяет создавать дерево и впоследствии выполнять запросы на нем. Но я не думаю, что это позволяет вам постепенно обновлять дерево.