« An Investigation of Practical Approximate

Nearest Neighbor Algorithms »

T. Liu, A. W. Moore, A. Gray, K.Yang

—la gang de CMU(présentation par N. Chapados)

K plus proches voisins (KNN)

Pourquoi cet article?

• KNN naïf prend O(N) à trouver les plus proches voisins

• Méthodes de partitionnement de l’espace (kd-trees ou metric trees) promettent une borne inférieure de O(log N)– Sujettes à la malédiction de la dimensionalité

• Cet article: KNN APPROXIMATIF– Spill trees + recherche heuristique

Metric Trees

• Partition récursive de l’espace

Points de pivot (dist maximale paire-à-paire)

Frontière de décision L

Observation évidente :la balle

• Pour chaque nœud v, on peut construire une hypersphère qui contient tous les points du nœud

• Centre = v.center Rayon = v.r• Remarque: les balles des enfants d’un nœud

ne sont pas nécessairement disjointes

Chercher un voisin dans un Metric Tree

• Recherche en profondeur– (depth-first search; DFS)

• Pour un nœud N• —— explore gauche ou droite selon

L• —— conserve un candidat NN• On élague les nœud qui ne peuvent

pas contenir le point de recherche

Élaguage

q

NN

v

v.r

||v.center-q||

r

Élague si

Recherche « défaitiste »

• UN SEUL chemin de la racine à la feuille

• Aucun backtracking• Rapide: O(N)• Approximatif• Ne fonctionne pas très bien pour

Metric Trees– Si le point-test est près de la frontière

d’une balle, il est souvent mal classifié

Spill Trees

QuickTime™ et undécompresseur TIFF (LZW)

sont requis pour visionner cette image.

• Améliore la précision de la recherche « défaitiste »• Tau=zero <==> Metric tree

Recherche hybride

• Problème avec spill-trees:– Profondeur varie énormément avec taille d’overlap

• Introduit un seuil d’équilibre (balance threshold) – Cas typique: =70%

• Si un enfant se retrouve avec plus de 70% des points du parent, alors on fixe =0 et on marque le nœud comme non-overlapping

• Les nœuds « non-overlapping » sont conservés comme points de banchement dans recherche DFS

– Nœuds overlapping agissent comme des Cut en Prolog

Résultats (1)• Perf. de spill-tree (speedup p/r à LSH)• Aerial: N=275 465 , d=60• Corel_hist: N=20 000 , d=64• Corel_uci: N=68 040 , d=64• Disk_trace: N=40 000 , d=1024• Galaxy: N=40 000 , d=4000

QuickTime™ et undécompresseur TIFF (LZW)

sont requis pour visionner cette image.

Résultats (2)

QuickTime™ et undécompresseur TIFF (LZW)

sont requis pour visionner cette image.