Discussion :

[Nemerle]

Ok, si j'ai bien compris:

- Notons A= {0,1,...,N-1}
- On a un ensemble E de points M de coordonnées (Mx0,...,Mx(N-1)), chaque point M ayant une propriétés P(M)
- Décomposons arbitrairement A en deux sous-ensembles disjoints K et K', et notons E(K) l'ensemble des points de coordonnées obtenues à partir de celles de M en passant à zéro les coordonnées xi de M pour i appartenant à K'
- Pour chaque M de E(K) on recherche ses 8 voisins et on compte le nombre nb(M) de ses voisins ayant la même propriété P(M) que M
- Score est la somme des nb(M) pour tout M de E(K)

On cherche à maximiser Score en fonction de K

J'ai bon?

[JeromeBcx]

OUI

[Okdokey]

le plus simple semble d'iterer en enlevant(ou ajoutant) qu'une dimension a la fois ce qui rend le calcul de distance et la recherche des points voisins plus rapides.

[Nemerle]

OUI

Désolé, je suis complêtement débordé en ce moment...

Je te suggère un algorithme génétique, ça devrait bien fonctionner et rapidement converger vers une solution acceptable.

[JeromeBcx]

Merci Nemerle

C'est effectivement dans le cadre de l'optimisation d'un algorithme génétique que je cherche à calculer le plus rapidement possible les plus proches voisins...

[Alikendarfen]

Bonjour,

Jérôme, pourquoi ne pas segmenter ton espace ?

Par exemple si on découpe chaque dimension en n intervalles Ii, sur cette dimension, un point donné d'un intervalle i, ne peut être proche que de ceux de Ii-1, Ii, Ii+1 (... c'est vrai en dimension n ... ?).

Ceci te rajoute de l'ordre de 10Mo (si les i < 256). Et sans doute, il faudrait adapter le nombre et la "position" des intervalles sur chaque axe en fonction des valeurs concrètes des points sur l'axe.

Dans cette représentation, trouver les points proches d'un point revient à sélectionner les points correspondant aux intervalles proches (Ii-1, Ii, Ii+1) sur chaque dimension parmi celles choisies. Cette sélection devrait être beaucoup plus rapide que le calcul de distances.

Si la sélection te ramène le nombre requis de voisins... c'est gagné sans calcul de distance. S'il y en a plus il faudrait les calculer mais donc sur beaucoup moins de points.

Il se peut aussi que la sélection ne ramène pas le nombre de voisins requis (entre 3 et 8). Il faudrait alors l'élargir à (Ii-2, Ii+2) ou bien simplement en déduire que ce "manque de proximité" signifie que les propriétés ne sont pas à vérifier... ?

[JeromeBcx]

Bonjour,

Jérôme, pourquoi ne pas segmenter ton espace ?

Par exemple si on découpe chaque dimension en n intervalles Ii, sur cette dimension, un point donné d'un intervalle i, ne peut être proche que de ceux de Ii-1, Ii, Ii+1 (... c'est vrai en dimension n ... ?).

Ceci te rajoute de l'ordre de 10Mo (si les i < 256). Et sans doute, il faudrait adapter le nombre et la "position" des intervalles sur chaque axe en fonction des valeurs concrètes des points sur l'axe.

Dans cette représentation, trouver les points proches d'un point revient à sélectionner les points correspondant aux intervalles proches (Ii-1, Ii, Ii+1) sur chaque dimension parmi celles choisies. Cette sélection devrait être beaucoup plus rapide que le calcul de distances.

Si la sélection te ramène le nombre requis de voisins... c'est gagné sans calcul de distance. S'il y en a plus il faudrait les calculer mais donc sur beaucoup moins de points.

Il se peut aussi que la sélection ne ramène pas le nombre de voisins requis (entre 3 et 8). Il faudrait alors l'élargir à (Ii-2, Ii+2) ou bien simplement en déduire que ce "manque de proximité" signifie que les propriétés ne sont pas à vérifier... ?

L'idée me plait bien, je creuse dans ce sens et posterait mes résultats prochainement, merci

[Alikendarfen]

Attention, rien n'est parfait : un point de Ii (sur un axe donné) peut être plus proche d'un point de Ii-2 que d'un point de Ii+1.

Une question Jérôme : on est d'accord que tes points sont fixes (pas d'ajout de points) pour une recherche donnée ?

[souviron34]

en fait, ça revient à faire un histogramme multi-dimensions...

Mais après, on peut raffiner en repassant à travers chacun et en groupant les points dans les bins adjacents...

Mais c'est une bonne idée...

[JeromeBcx]

Attention, rien n'est parfait : un point de Ii (sur un axe donné) peut être plus proche d'un point de Ii-2 que d'un point de Ii+1.

Une question Jérôme : on est d'accord que tes points sont fixes (pas d'ajout de points) pour une recherche donnée ?

L'ensemble des points est bien fixe (ouf), c'est le nombre de dimensions qui peut varier.
Lidée de l'histogramme mulit dimensionnel est très interressante.
Par rapport à la définition des voisins, effectivement, l'exemple que tu sites peut arriver très fréquement, mais l'intérêt est de regarder l'ensemble des voisins proches, donc au lieu de fixer par exemple K voisins, on peut très bien imaginer prendre comme critère : l'ensemble des points des cellules voisines. Il faudra par contre controler le nombre de points par intervalle et surement passer par des intervalles de tailles variables

en fait, ça revient à faire un histogramme multi-dimensions...

JE vois cela comme ça aussi : en terme de temps de calcul, on peut faire des merveilles (de plus je normalise mes données en début de calcul, donc je peux créer les histogrammes dans la foulée.

Mais après, on peut raffiner en repassant à travers chacun et en groupant les points dans les bins adjacents..

Euh ... là j'avoue ne pas comprendre comment tu veux regrouper les points...


Encore merci à tous.
Bonne fin de journée

[souviron34]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
         |---|
---      |   |
   |     |    ----|
   ------|        |---|

Le "patatoide" (les 2 bins consecutifs) du milieu peut-etre considere comme un seul... Tu ne peux pas vraiment determiner si un point tombant a l'extremite droite du bin de gauche n'est pas plus pres de la mesure du bin droite... Car tout depend du demarrage (le point 0).

Mais dans ton cas ca ne s'applique pas forcement....

Mais c'etait pour expliquer...

[Alikendarfen]

Encore une question, Jérôme ! (juste pour comprendre)

Ton problème est en fait un problème de data mining : quels sont les éléments discriminants, significatifs de propriétés données... donc quelles sont les causes de quelque chose. Je me trompe ?

[Alikendarfen]

... si c'est le cas : ce lien http://fr.wikipedia.org/wiki/Analyse...es_principales

et notamment :

Le choix de réduire ou non le nuage de points (i.e. les K réalisations de la variable aléatoire (X1, …, XN)) est un choix de modèle :

* si on ne réduit pas le nuage : une variable à forte variance va « tirer » tout l'effet de l'ACP à elle ;
* si on réduit le nuage : une variable qui n'est qu'un bruit va se retrouver avec une variance apparente égale à une variable informative.

... juste pour contribuer (je suis peut être totalement hors sujet)

[JeromeBcx]

Merci souviron34 pour les explications.

Alikendarfen,

Oui effectivement, c'est dans le cadre de data-mining.
l'ACP, je connais bien, mais dans notre domaine, les résultats de cette méthode sont plutot .
Par contre, l'algorithme génétique nous donne des résultats très interressants. Seulement, la fonction d'évaluation nous prend un temps fou, donc un peu d'optimisation ne fait pas de mal...

Encore merci à vous tous.

[JeromeBcx]

Bon pas de techniques miracles... mais une nette amélioration en calculant une carte des distances et en optimisant le code (float plutot que double, pas de racines, ...)

Encore merci pour vos différentes propositions et remarques