Algorithme de voisin le plus proche incrémental en Python

Question

Quelqu'un sait-il qu'un algorithme de voisin le plus proche implémenté en Python peut être mis à jour de façon incrémentielle? Tous ceux que j'ai trouvés, tels que this one, semblent être des processus par lots. Est-il possible de mettre en œuvre un algorithme NN incrémental?

Answer 1

Je pense que le problème avec la construction incrémentielle d'un arbre KD ou d'un arbre KNN est, comme vous l'avez mentionné dans un commentaire, que l'arbre finira par être déséquilibré et que vous ne pourrez pas faire de rotation simple équilibrer les problèmes et maintenir la cohérence. Au minimum, la tâche de rééquilibrage n'est pas triviale et on ne voudrait certainement pas le faire à chaque insertion. Souvent, on choisira de construire un arbre avec une méthode batch, d'insérer un tas de nouveaux points et de déséquilibrer l'arbre jusqu'à un point, puis de rééquilibrer

Une chose très similaire à faire est de construire la structure de données en batch pour les points M, utilisez-le pour les points M ', puis reconstruisez la structure de données en batch avec les points M + M'. Puisque le rééquilibrage n'est pas l'algorithme normal et rapide que nous connaissons pour les arbres, la reconstruction n'est pas nécessairement lente en comparaison et, dans certains cas, peut être plus rapide (en fonction de la séquence des points entrant dans votre algorithme incrémental). Cela dit, la quantité de code que vous écrivez, la difficulté de débogage et la facilité avec laquelle les autres comprennent votre code peuvent être considérablement plus petites si vous utilisez l'approche de reconstruction. Si vous le faites, vous pouvez utiliser une méthode batch et conserver une liste externe de points qui ne sont pas encore insérés dans l'arborescence. Une approche de force brute peut être utilisée pour s'assurer qu'aucun de ceux-ci n'est plus proche que ceux de l'arbre.

Certains liens vers des implémentations/discussions Python sont ci-dessous, mais je n'en ai trouvé aucun explicitement prétendant être incrémental. Bonne chance.

http://www.scipy.org/Cookbook/KDTree

http://cgi.di.uoa.gr/~compgeom/pycgalvisual/kdppython.shtml

http://sites.google.com/site/mikescoderama/Home/kd-tree-knn

http://www.java2s.com/Open-Source/Python/Math/SciPy/scipy/scipy/spatial/kdtree.py.htm

http://en.wikipedia.org/wiki/Kd-tree

Note: Mes commentaires appliquent à des espaces de grande dimension. Si vous travaillez en 2D ou en 3D, ce que j'ai dit n'est peut-être pas approprié. (Si vous travailler dans des espaces très haute dimension, utiliser la force brute ou rapprocher le plus proche voisin.)

Answer 2

Il y a. Le site Web Scipy Cookbook comprend une implémentation complète d'un kNN algorithm qui peut être mis à jour de façon incrémentielle. Peut-être que quelques lignes d'arrière-plan seraient utiles pour toute personne intéressée mais ne connaissant pas la terminologie.

Un moteur kNN est alimenté par l'une des deux représentations de données - les distances par paires entre tous les points dans l'ensemble de données stockées dans un tableau multidimensionnel (une matrice de distance ), ou un kd-arbre, qui stocke simplement les points de données eux-mêmes dans un arbre binaire multidimensionnel.

Ce ne sont que deux opérations qu'un algorithme KNN à base kd-tree-besoins: vous créez l'arbre de l'ensemble de données (analogue à la formation étape effectuée en mode batch dans d'autres algorithmes ML), et vous recherchez l'arbre pour trouver les «plus proches voisins» (analogue à l'étape test).

Entraînement en ligne ou incrémental dans le contexte d'un algorithme KNN (à condition qu'il soit basé sur un kd-tree) signifie insérer les nœuds à un kd-tree déjà construit. Retour à l'implémentation de kd-Tree dans le livre de recettes SciPy: Les lignes de code spécifiques à l'insertion des nœuds apparaissent après la ligne de commentaire "insérer un nœud dans kd-tree" (en fait, tout le code après ce commentaire est dirigé vers l'insertion de noeud).

Enfin, il y a une mise en œuvre kd-arbre dans le module spatial de la bibliothèque SciPy (scipy.spatial module) appelé KDTree (scipy.spatial.KDTree) mais je ne crois pas qu'il supporte l'insertion de noeud , au moins une telle fonction n'est pas dans les Docs (je n'ai pas regardé la source).

Answer 3

C'est bien tard, mais pour la postérité:

Il est en fait une technique pour convertir des algorithmes traités par lots comme KD- Arbre en algorithmes incrémentaux: il s'agit d'une transformation statique-dynamique .

Pour générer une variante incrémentale d'un arbre KD, vous stockez un ensemble d'arbres au lieu d'un seul arbre. Quand il y a N éléments dans votre structure de plus proche voisin, votre structure aura un arbre pour chaque bit "1" dans la représentation binaire de N. Par ailleurs, si l'arbre T_i correspond à la i-ième bit deN, puis arbre T_i contient 2^i éléments.

Donc, si vous avez 11 éléments dans votre structure, puis N = 11 ou 1011 en binaire, et donc vous avez trois arbres - T_3, T_1 et T_0 - avec 8 éléments , 2 éléments et 1 élément, respectivement.

Maintenant, insérons un élément et dans notre structure. Après l'insertion, nous aurons 12 éléments, ou 1100 en binaire. En comparant la nouvelle et la précédente chaîne binaire, on voit que T_3 ne change pas, nous avons un nouvel arbre T_2 avec 4 éléments, et des arbres T_1 et T_0 sont supprimés. Nous construisons le nouvel arbre T_2 en faisant une insertion par lots de e ainsi que tous les éléments dans les arbres « ci-dessous » T_2, qui sont T_1 et T_0. De cette manière, nous créons une structure de requête ponctuelle incrémentielle à partir d'une structure de base statique.Il y a, cependant, un ralentissement asymptotique dans "incrementalizing" structures statiques comme celle-ci sous la forme d'un log (N) facteur supplémentaire:

• insertion N éléments de structure: O (log N (N) log (n))
• le plus proche de requête voisin pour la structure avec N éléments: O (log (n) log (n))