Recherche des plus proches voisins dans un espace variable à K dimensions parmis N

**JeromeBcx** · 18/03/2008, 17h20

Bonjour à tous,

Je possède un ensemble de M points dans un espace à N dimensions.
J'aimerais connaître les plus proches voisins d'un points, mais au lieu de se référer au N dimensions, je n'en sélectionne qu'un sous ensemble K parmis les N.
Jusque là, pas de problèmes... un "petit" calcul de distance euclidienne... mais mon problème se situe au niveau de mon sous ensemble K.
Lors d'itérations, je vais sélectionner qu'une partie de mes dimensions (différents à chaque itération) et donc en utilisant la distance euclidienne, je dois recalculer les distances pour l'ensemble de mes points dans l'espace à Ki dimensions... et ce un grand nombre de fois...
Je peux alléger les calculs avec une distance un peu moins gourmande, mais j'aimerais trouver une autre approche plus propre (et surtout plus rapide !!! Mes processeurs vont finir par me demander une augmentation à force de faire des heures sup!!!)

Je me demandais s'il n'existait pas une autre approche pour retrouver mes voisins sans pour autant recalculer tout à chaque fois, quitte à devoir perdre un peu de temps au début.

Si quelqu'un a une petite idée
En vous remerçiant par avance

**ToTo13** · 18/03/2008, 17h55

Bonjour,

dans le calcul de la distance Euclidienne, c'est les carrés et la racine qui sont gourmands.
Pourquoi ne pas précalculer les carrés et travailler avec le carré de la distance Euclidienne ?
Ainsi à chaque itération tu n'aurais qu'à faire la somme des Ki carrés concernés. Ce qui sera beaucoup plus rapide.

**JeromeBcx** · 18/03/2008, 18h11

Merci toto13,

Effectivement, je gagne pas mal de temps en utilisant cette méthode, mais je me demandais s'il n'existait pas une approche radicalement différente pour trouver mes voisins, genre arbre, changement d'espace, ...
Vu mes volumes que je me retrouve à calculer, j'explose tout très rapidement...

**PRomu@ld** · 18/03/2008, 18h23

Ca semble être un sujet récurent non ?

http://www.developpez.net/forums/sho...d.php?t=510842

**JeromeBcx** · 18/03/2008, 18h38

Envoyé par PRomu@ld

Ca semble être un sujet récurent non ?

Oui, j'avais vu le poste de arnoldo165, mais comme mon problème diffère du fait que mes dimensions peuvent être variables, je ne voulais pas faire dériver le sujet.

De plus, les différentes techniques proposées ne parraissent pas convenir au sous espace variable

Cdt,

Jérôme

**souviron34** · 18/03/2008, 19h40

Envoyé par JeromeBcx

De plus, les différentes techniques proposées ne parraissent pas convenir au sous espace variable

c'est a dire ??

Tout depend si tu etudies les combinaisons possibles , ou l'addition des differentes dimensions..

Si c'est le deuxieme cas, tu peux au premier passage calculer la distance par une boucle sur les dimensions et stocker dans un tableau indice par le nbe de dimensions la distance pour chaque point...

**JeromeBcx** · 19/03/2008, 11h10

Envoyé par souviron34

Tout depend si tu etudies les combinaisons possibles , ou l'addition des differentes dimensions..

Bonjour Souviron et merci de la réponse.
Hélas, je suis dans le premier cas ou toutes les combinaisons de dimensions sont possibles

L'algorithme sélectionne un sous ensemble de dimensions (quasiment aléatoirement) et je recherche les plus proches voisins dans ce "nouvel" espace.
Par contre, dans une seconde phase de mon algorithme, mes points sont définis sur K dimensions et j'ajoute ou enlève une dimension puis je recherche les plus proches voisins

**Nemerle** · 19/03/2008, 11h13

Y-a pas de miracle: en fait tu projettes à chaque fois tes points sur le sous-espace K puis tu cherches tes voisins ==> ton problème dépend complètement de la métrique naturelle sur K, et en passant à un autre K les voisins peuvent être bien sûr complêtement différent! TU dois donc recalculer tes distances, en précalculant proprement tes carrés comme signalé, voir plus: si tes K sont "particuliers", précalcule au maximum tout ce que tu peux.

**JeromeBcx** · 19/03/2008, 11h32

Envoyé par Nemerle

...et en passant à un autre K les voisins peuvent être bien sûr complêtement différent!

Merci Nemerle,
C'est effectivement le problème

, mais aussi le but de l'algorithme

J'avais peur d'arriver à cette conclusion. Précalculer le maximum de chose me permet néanmoins d'être plus rapide.
Tant qu'à optimiser, j'avais espéré qu'il existait d'autres méthodes. Vu que j'avais la tête dans le guidon avec mes distances euclidiennes, j'espérais qu'un regard neuf... ça m'apprendra d'espérer !!! L'espoir fait vivre, mais il ne résout pas les algorithmes...

**Nemerle** · 19/03/2008, 13h26

Tes K sont-ils réellement quelconques?

**JeromeBcx** · 19/03/2008, 13h51

Non, en fait je recherche à diminuer l'espace à N dimensions (qui peut atteindre les 1000) vers un espace à K dimensions plus petit (de l'ordre de 10). Ce nouvel espace doit pouvoir concervé les propriétés de séparation de mes éléments : certaines dimensions n'apporte pas d'information et son exclues au cours de l'algoritme jusqu'à trouver le plus "petit" espace qui répond aux propriétés.
Ce système me permet de créer un modèle : je connais les propriétés de mes éléments de construction.
Lorsque j'introduit un nouveau point, à l'aide de mon sous espace, je pourrais connaître ses propriétés par rapport à mon modèle

**Nemerle** · 19/03/2008, 18h48

Ahhh.... là ce n'est pas pareil, on peut faire quelque-chose.

Le point le plus important est de définir exactement ce que tu veux au niveau de la notion de "voisin". Que veux-tu?
[Edit]Et combien de points?[/Edit]

**JeromeBcx** · 20/03/2008, 12h03

Envoyé par Nemerle

Ahhh.... là ce n'est pas pareil, on peut faire quelque-chose.

Envoyé par Nemerle

Le point le plus important est de définir exactement ce que tu veux au niveau de la notion de "voisin". Que veux-tu?

En fait, par rapport à mon point P, je regarde les voisins les plus proches (dans mon cas en terme de distance (pour l'instant)), j'identifie leur propriété. En mode apprentissage, je compte le nombre de points dont la propriété est identique à mon point P, en mode "prédiction", j'affecte à mon point P la propriété la plus représentative parmis les voisins.

Envoyé par Nemerle

Et combien de points?

C'est un paramètre de mon application, les bornes standards étant [3-8]

Merci Nemerle pour ce coups de pouce

**Nemerle** · 20/03/2008, 16h54

Donc si je résume, pour toi, les voisins d'un point P sont les points Q1...Qn qui appartiennent à la boule de centre P et de rayon e, e étant fixé au préalable?

Et tu veux trouver le plus petit sous-espace K où les projetés Q1...QN sont toujours dans la boule de K de centre P et de rayon e?

Si C ça, C pas bon: n'importe quel K de dimension 2 marche...

**JeromeBcx** · 20/03/2008, 17h34

Bonjour Nemerle,

Non, ce n'est pas ça... Sinon, effectivement, je devrais trouver 1 seule dimension qui réponds à ce critère de distance e.

J'essaie d'expliquer plus clairement
J'ai un esemble de points M de coordonnées xi avec i€[0,N[
Chaque point M possède une propriété que je connais en mode "apprentissage"
L'ensemble des propriétés est un esemble fini de valeurs

Mon algorithme doit être capable de trouver le sous espace le plus petit possible qui concerve la "bonne" propriété de chacun de mes points.
Pour vérifier que mon espace concerve ces propriétés, je recherche pour chaque point les plus proches voisins (leur nombre est fixé par l'appli de 3 à 8 environ) et je compte le nombre de voisins qui ont la même propriété que mon point référent : ceci me donne un score de validité pour chacun des points de mon ensemble. L'ensemble des scores me donne un score global que j'affecte à mon sous espace et ainsi je peux savoir si mon sous espace est intérressant pour la classification de mes points.
Par itération, je fais évolué mes dimensions en essayant d'améliorer le score global.

Dans l'algorithme, c'est la recherche des kppv qui me demande le plus de calcul et je recherche des méthodes pour diminuer le temps de recherche et la seule chose que je vois c'est de sélectionner les voisins en calculant les distances qui séparent mes points, mais comme mon espace change à chaque itération, je dois recalculer à chaque fois cette distance et c'est long

Voila, en espérant avoir présenter le plus clairement possible mon algorithme.

**JeromeBcx** · 20/03/2008, 19h40

Encore un petit détail... de taille

l'algo doit être capable de supporter 10 000 points, 1 000 dimensions
Les données sont actuellement stockée sous forme de double...
Donc je peux stocker les xi² et yi² mais pas une matrice des xi*yi pour le calcul des distances euclidiennes et encore, cela me demande tout de même ~40Mo : pour une application qui doit tourner en arrière plan, c'est beaucoup (160Mo en tout)

**Nemerle** · 21/03/2008, 15h05

Envoyé par JeromeBcx

J'essaie d'expliquer plus clairement...

Bonjour jérome, tu vas me trouver "chiant", mais non, ce n'est pas encore clair pour moi...

- Tu parles de coordonnées xi et de propriétés: on est d'accord, ce n'est pas la même chose? Si oui, chaque point M a donc des coordonnées (Mx0,...,Mx(N-1)), ainsi qu'une (seule?) propriété P(M)

- tu cherches un plus petit sous-espace: qu'est-ce pour toi un sous-espace? Est-ce un sous-ensemble de tes points M, ou bien est-ce au sens d'une projection de tes points?

Désolé pour ces demandes!

**JeromeBcx** · 21/03/2008, 15h09

Bonjour Nemerle,

Non pas du tout, c'est clair que l'algo n'est pas forcément des plus explicite, puis en quelques petites phrases, ce n'est pas évident de bien le formaliser !!!

J'ai effectivement une seule propriété par point.
Par sous espace, j'entends une partie des N dimensions.
(NB : je ne veux pas faire de projection)

Encore merci
Bonne journée