Enregistrement et mise à jour progressive du modèle du voisin le plus proche dans R

Question

Il existe plusieurs packages R voisins les plus proches (par exemple, FNN, RANN, yaImpute), mais aucun ne semble permettre de sauvegarder la structure de données NN (arbre de couverture, arbre KD, etc.), de sorte que les voisins les plus proches des nouvelles requêtes puissent être calculés sans modification. reconstruire l'arbre entier. Existe-t-il de telles fonctions dans R?

Je recherche une fonction qui renvoie une structure de données que je peux mettre à jour progressivement à mesure que de nouvelles données arrivent pour effectuer une recherche de K voisin le plus proche.

Answer 1

Il y a une bonne raison pourquoi pas NN colis n'a que.

La raison en est que le "NN structure de données" inclut nécessairement tous les points de données (sous la forme d'un KD tree), donc il n'y a pas d' espace d'épargne contre l'entrée de données. Il semble qu'il serait temps de l'épargne de ne pas avoir à re-créer le KD-tree pour chaque nouvelle entrée, mais ce n'est pas le cas, hélas.

La raison en est que le temps de construire un KD-tree est, en général, pire que linearithmic. Cela signifie que, pour les grandes entrées, il est logique de trier les données avant la construction du KD-tree, parce que cela va produire le KD-tree plus vite et il sera mieux équilibré, ce qui permettra d'améliorer la recherche, de trop (c'est aussi pire que logarithmique, en général). Cette approche permettrait d'accélérer la modélisation et de l'évaluation, mais décourager de mises à jour incrémentielles, bien sûr.

Votre meilleur pari, je pense que, si pour trouver un générique KD-arbre de package et de l'utiliser à la place.