Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide | Shop Recherche
805 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Optimisation des plus proche voisins

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Optimisation des plus proche voisins

n°2230249
Terminapor
I'll see you rise.
Posté le 09-06-2014 à 12:37:08  profilanswer
 

Bonjour :hello:
 
Je travaille sur l'implémentation d'un algorithme qui trace les veines d'une feuille.
Voilà le papier : http://algorithmicbotany.org/paper [...] ig2005.pdf
 
La phase la plus lente c'est la recherche des plus proche voisins.  
En gros, il y a deux listes de points : Les veines, et les sources.
Chaque veines cherchent quelles sont les source les plus proches, en suivant cette formule :
 
(∀u ∈ V)||v−s|| < max{||u−s||,|v−u||}.
 
Où u est une veine parmi les autres, s la veine pour laquelle ont cherche ses plus proches voisins, et v les sources testées.
 
L'implémentation "naïve" me donne ça :  
 

Code :
  1. std::vector<int> VeinGenerator::GetNeighbors( int VeinIndex )
  2. {
  3.     std::vector<int> VL;
  4.     VL.reserve( Veins.size() );
  5.     for ( size_t i=0;i< Sources.size(); ++i )
  6.     {
  7.  //---------------------------
  8.  // Is i (source) a nearest neighbor ?
  9.  float DistI_Source = _distance( Sources[i].Location, Veins[VeinIndex].Location );
  10.  bool bNearestNeighbor = true;
  11.  for ( size_t j=0;j< Veins.size() && bNearestNeighbor; ++j )
  12.  {
  13.   if ( j != VeinIndex )
  14.   {
  15.    float DistJ_Source = _distance( Veins[j].Location, Veins[VeinIndex].Location );
  16.    if ( DistI_Source >= std::max(DistJ_Source, _distance( Sources[i].Location, Veins[j].Location ) )  )
  17.    {
  18.     bNearestNeighbor = false;
  19.    }
  20.   }
  21.  }
  22.  if ( bNearestNeighbor )
  23.   VL.push_back( i );
  24.  //---------------------------
  25.     }
  26.     VL.shrink_to_fit();
  27.     return VL;
  28. }


 
(_distance renvoi la distance au carrée entre deux points, ça évite d'avoir un calcul de racine carrée.)
 
Le soucis, c'est que le nombre de veines et de sources augmentent très rapidement, du coups les temps sont assez longs.
Dans leur papier, ils parlent des diagrammes de Voronoi pour optimiser ce problème, et de la triangulation de Delaunay pour générer ce diagramme, mais je dois avouer que c'est assez flou pour moi.. :sweat:
 
Si quelqu'un pouvait m'éclairer un peu à ce sujet ça serait cool :D
 
Merci à vous :jap:


---------------
Perhaps you don't deserve to breathe
mood
Publicité
Posté le 09-06-2014 à 12:37:08  profilanswer
 

n°2230310
rufo
Pas me confondre avec Lycos!
Posté le 10-06-2014 à 10:56:28  profilanswer
 

Ces 2 algos permettent de limiter les zones sur lesquelles l'algo va travailler.
Dans Wikipedia, y'a de bons articles sur ces 2 sujets ;)


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Cantine Calandreta : http://sourceforge.net/projects/canteen-calandreta
n°2230317
Terminapor
I'll see you rise.
Posté le 10-06-2014 à 12:36:23  profilanswer
 

Oui j'ai compris le principe, mais je vois pas trop comment le mettre en pratique..
Je sais qu'il faut un diagramme de Voronoi pour les veines, et un pour les sources, mais je vois pas comment se passe la recherche une fois ceci mis en place.


---------------
Perhaps you don't deserve to breathe
n°2230320
rufo
Pas me confondre avec Lycos!
Posté le 10-06-2014 à 13:36:02  profilanswer
 

Y'a un truc pas très clair pour moi (et j'ai pas trop le temps de lire le papier :D) : tu dis que pour chaque veine "s", tu cherches la source "v" la plus proche (au passage, pas très logique d'appeler "s" la veine et "v" la source :pt1cable: ). Du coup, que vient faire "u" qui est une autre veine là-dedans ?
 
Je précise que si je connais le principe de Voronoï, je l'ai jamais utilisé. Par contre, la notion de plus proche voisin me fais penser à dijkstra et le plus court chemin, voire, peut-être plus adapté, les plus courts chemins d'un graphe via l'algo de Bellman-Ford :  
http://fr.wikipedia.org/wiki/Algor [...] llman-Ford
Ca pourrait pas t'aider ?


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Cantine Calandreta : http://sourceforge.net/projects/canteen-calandreta
n°2230340
honrisse
Posté le 10-06-2014 à 17:00:34  profilanswer
 

Bonjour,
 
Je ne sais pas si mon post va être utile mais on peut aussi utiliser une structure de données particulières les kd-tree pour les recherches de plus proche voisin.

n°2230351
Terminapor
I'll see you rise.
Posté le 10-06-2014 à 18:16:43  profilanswer
 

Bon effectivement en fait j'avais compris l'algo de travers :o

 

Dans mon implémentation, chaque veine cherche les sources les plus proche, c-a-d qu'il n'existe aucune autre veine plus proche des sources.
Les résultats étaient pas mauvais, mais en relisant ça se fait dans l'autre sens.

 

Chaque sources cherchent la veine la plus proche (unique veine), et influence celle-ci (open pattern, si je ne me trompe pas c'est plus pour simuler les branches / racines d'un arbre que des veines de feuilles).
Ensuite, pour le closed pattern, une source S peut influencer plusieurs veines, auquel cas ça donne que la source S et ses plus proches voisins influencent la veine la plus proche de S.
Pour les plus proche voisins, l'algo dit ça :

 

"La source V est un plus proche voisin de la source S si pour toutes veines U plus proche de S que ne l'est V, V est plus proche de S que de U." ( :sweat: )

 

Bon, pour l'instant je vais rester sur ma première implémentation, c'est déjà assez le bordel comme ça :o

 

J'ai commencé à réfléchir pour l'implémentation de l'opti avec un quad-tree, ça ressemble du coups aux KD-Tree ( sauf qu'eux se basent sur la médiane si j'ai bien compris).
Mon approche donnerait ça :

 

A chaque fois qu'une veine doit vérifier si une source est belle et bien son plus proche voisin, elle retrouvera sa position dans le quad-tree et commencera par vérifier toute les autres veines du noeud correspondant. Si aucune de ces veines ne sont plus proche, alors ça ira sur le noeud parent du noeud de la source.
Du coups, pour chaque veine ça donnerai dans le pire des cas (aucune veine n'est plus proche de cette source que ne l'est la veine actuelle) une complexité en O(n) où n est le nombre de source, et dans le meilleur... Bah là de tête je saurais pas dire, mais bien mieux :D

 

Pour ce qui est de Djikstra et Bellman-Fort, les graphs ont un nombres d'arcs donnés, moi dans mon cas chaque point serait reliés les un aux autres, du coups ça va pas faire un truc assez lent :??:


Message édité par Terminapor le 10-06-2014 à 18:16:53

---------------
Perhaps you don't deserve to breathe
n°2230407
rufo
Pas me confondre avec Lycos!
Posté le 11-06-2014 à 10:07:58  profilanswer
 

Je sais pas si ça peut fonctionner Bellman-Ford, ça dépend un peu du contexte. l'idée, c'était de pouvoir pré-calculer la matrice des distances entre toutes les veines et sources. Si à une feuille tu peux associer la matrice déjà calculée, après, pour ton algo, il reste plus qu'à faire des recherches dans la matrice. Dans ce cas, là, je pense que tu peux gagner du temps... Par contre, si tes feuilles sont générées dynamiquement, à chaque fois, faudra calculer le matrice puis l'exploiter : dans ce cas, c'est pas dit que tu gagnes du temps...


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Cantine Calandreta : http://sourceforge.net/projects/canteen-calandreta
n°2230629
Terminapor
I'll see you rise.
Posté le 12-06-2014 à 15:00:50  profilanswer
 

Oui effectivement, les points sont rajoutés au fur et à mesure donc ça ne me semble pas être l'idéal...

 

J'ai retapé le déroulement de l'algo, ma première implémentation était vraiment dégueu en fait :D
Rien que le fait de faire que chaque source trouve sa veine la plus proche (au lieu que chaque veine trouve ses sources les plus proche) ça a ajouté un sacré boost de temps.
J'ai essayé ensuite de créer un quad-tree qui continent chaque noeud de chaque veine pour booster la recherche du plus proche voisin (basé sur cet exemple : http://bl.ocks.org/patricksurry/6478178), et ça ralenti l'algo énormément au final.. :(

 

J'vais tenter avec l'implémentation de Voronoi de la librairie Boost, mais je sais pas trop ce que ça va donner (l'insertion dans un quad-tree est extrêmement rapide, je sais pas si c'est le cas pour Voronoi), après au pire je peux toujours "optimiser" la version naïve du plus proche voisin en faisant du multi-threading ( grouper les sources par threads, ça devrait être un gros speed-up non ?)

 

Faut aussi que je jette un coups d'oeil aux kd-trees, sur le quad-tree l'arbre était quasiment toujours parcouru...

 

edit : En fait mon implé pour les quad-trees était mal foutu, j'avais pas adapté pour bosser avec les distances au carrée. Le quad-tree est en moyenne 2x plus rapide que la version naïve sur mon algo :D


Message édité par Terminapor le 12-06-2014 à 16:47:01

---------------
Perhaps you don't deserve to breathe

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Optimisation des plus proche voisins

 

Sujets relatifs
Optimisation de tableau de fonctionsSite ou thème CMS proche de Google Play ou Itunes
optimisation requete fgetsOptimisation lecture fichier texte
Optimisation recherche doublonsSQL Loader : Optimisation de chargement et commit
[VB6] Simplification et optimisation code[Résolu][Perl] Découper un fichier en plusieurs et optimisation
Optimisation du codeOptimisation code php
Plus de sujets relatifs à : Optimisation des plus proche voisins


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC / Shop HFR