Discussion :

[pseudocode]

@pseudocode. Commencer par chercher des solutions ne veut pas dire qu'on renonce à optimiser, on commence par restreindre le nombre des candidats.

C'est bien pour cela que je parlais de découper l'espace en case de taille DxD et de travailler sur un voisinage 3x3. Ca permet rapidement d'eliminer du problème les groupes de points qui sont éloignés et ca limite le nombre de calculs de distance points à points de PxQ.

[Zavonen]

C'est bien pour cela que je parlais de découper l'espace en case de taille DxD et de travailler sur un voisinage 3x3. Ca permet rapidement d'eliminer du problème les groupes de points qui sont éloignés et ca limite le nombre de calculs de distance points à points de PxQ.

Oui, c'est une idée qu'elle est bonne ...
Toute bonne méthode commencera pas décider qui on garde, et on gardera évidemment tout point de P situé à distance >=d de tout point de Q et vice-versa, ces points pourront être éliminés du problème.
Enfin dans certains cas cela ne donne rien du tout, par exemple quand Q est un simple réarrangement de P.
Quant aux points communs aux deux nuages ils peuvent être éliminés du problème aussi a contrario, il ne peuvent faire partie d'une solution quelconque ou optimale, on peut donc supposer les deux nuages disjoints.

[benDelphic]

ma solution est en o ( max ( card p, card de Q)). vu qu'on ne verifiera que du point de vu de l'un des ensembles ( celui dont la cardinalité est maximum )

[Alp]

L'idée des SVM a été abandonnée ?

[pseudocode]

L'idée des SVM a été abandonnée ?

A priori la vitesse de l'algo est plus importante que l'optimalité, donc je ne suis pas bien sûr que les SVM soient une solution viable.

(surtout avec des SVM non linéaires).

[Alp]

Les SVM ne seront définitivement pas la solution la plus rapide.

Par contre, il faudrait connaître l'importance relative de la rapidité sur l'optimalité... Parce que si on veut faire rapide, on prend la médiatrice des centres de gravité de (Pi) et (Qi) et on enlève tous les points qui sont "du mauvais côté"

[pseudocode]

Non, Je me suis mal exprimé. Ce n'est pas ce que je voulais dire.

Les SVM ne donnent pas directement la solution au problème. Ils fournissent juste une meilleure courbe de séparation que la "mediatrice".

Il faudra tout de meme choisir les points à supprimer pour garantir la contrainte et maximiser la taille des populations. C'est cette partie de l'algorithme qui est couteuse, et c'est celle la qu'il faut accelerer.

Donc l'utilisation des SVM c'est un petit "plus" dans la selection des point candidats à la suppression. Mais ce n'est pas là que se trouve le coeur du problème.

[Zavonen]

Et alors, la fin du film c'est quoi ?

[souviron34]

Si je comprend correctement le problème :

• On a 1 nuage de points
• Dans ce nuage, on souhaiterait faire la différenCe entre 2 classes (forme du style bilboquet)
• Cette séparation serait basée sur une distance minimale D

C'est bien ça ??

[Nemerle]

quelques petites remarques:

- le problème vient bien de la "vraie" vie, donc pas de points exentriques ou de cas tordus. Par contre, la "forme" des 2 nuages peut l'être (au sens l'enveloppe des points est non convexe par exemple).
- La solution proposée par Jean-MArc est celle que j'ai implémenté, et ç'est ~ satisfaisant en temps de calcul;
- Les nuages P & Q ont en général ~ 10 000 points chacun, mais le nombre de points de P à distance inférieure à D de Q sont de l'ordre de 1000-2000; on se restreint donc bien sûr à ces points pour la matrice.

- Mais... plutôt que de définir pour chaque pt le nombre de pts d'en face impactés, et de boucler sur un recalcul des distances, on pourrait peut-être travailler avec la liste de ces pts: pour tout pt de P & Q notons L(pt) cette liste; on recherche alors le plus petit ensemble pt1,...,ptn tel que la réunion des L(pti) soit égale à la réunion des L(pt) pour tout pt . C'est volumineux, et en temps de calcul?


- Autre idée possible: on recherche une certaine équation de diffusion dont la solution est une courbe de séparation des 2 nuages en relation avec la distance D. On se ramène ainsi à un algo de discrétisation d'une EDP...

[Jean-Marc.Bourguet]

Est-ce que les nuages sont clairement separes ou bien il peut y avoir un recouvrement?

[Nemerle]

IL n'y a pas de recouvrement!

[souviron34]

j'avais exposé dans un autre post un algo que j'avais créé pour séparer des cellules orageuses (temps réel : de 100 à 300 000 points séparés).

Dans ce cas, on a un seul gros nuage de points, plus ou moins "aléatoirement" répartis.

Le principe est de d'abord ranger les points (qsort) en X.

Puis, pour chaque point, d'explorer les N avants et N après. Dès que la distance en X devient supérieure à D, on arrête.

(ce qui revient à explorer le voisinage en X,Y).

On stocke alors une étiquette (numéro de la cellule) pour chaque point.

Les optimisations sont doubles : d'une part on a un tri globalement en N log(N). D'autre part, si on ne manipule que les adresses des points et non les points, on ne bouge qu'un minimum de mémoire.

Dans ce cas, le temps de calcul (expérimental) est en moyenne (sur plus de 500 000 cas) environ proportionnel à 5*N.

PS: j'ai le code C quelque part..

[Zavonen]

Est-ce que les nuages sont clairement separes ou bien il peut y avoir un recouvrement?

La question ne se pose pas vraiment, puisque s'il y a des points communs aucun ne peut appartenir à une solution. On peut donc les éliminer d'office, et faire la supposition de Nemerle.
Par ailleurs, bien que cela ne semble avoir soulevé beaucoup d'enthousiasme, je plaide à nouveau pour ma 'pré-solution'.
Placer chaque nuage dans un rectangle minimal au moyen du coefficient de régression et du coefficient de corrélation.
Cela fait, examiner les tailles et positions respectives de ces rectangles et surtout comparer leurs dimensions avec d.
Il se peut qu'on puisse de la sorte mettre hors jeu immédiatement un très grand nombre de points comme appartenant systématiquement à toute solution maximale. On peut ensuite appliquer l'algo de Nemerle sur un nombre de points restreint.
Evidemment on n'a aucune garantie, surtout si les nuages sont très entremêlés, mais s'ils sont au départ suffisamment séparés on peut se simplifier grandement l'existence.

[Jean-Marc.Bourguet]

La question ne se pose pas vraiment, puisque s'il y a des points communs aucun ne peut appartenir à une solution.

Telle que je l'ai comprise, la contrainte sur la distance est sur les ensembles finaux (donc chacun des ensembles initiaux est toujours une solution, au pire en vidant completement l'autre).

[Nemerle]

Souviron: ton idée est intéressante, c'est un algo de parcours de " ~ voisinages topologiques"...

J'essayerai dès que j'aurai un moment de l'implémenter pour voir les temps de calcul...

[ol9245]

Je prend ce problème en cours de route. Désolé si mon grain de sel tombe à plat...

Si il n'y a que 10000 éléments par nuage, on peut faire une triangulation de delaunay de l'ensemble des points de tous les nuages. Ca coute N Log(N), ou N est le nomnre total e points.

Puis on parcours chaque point et on enlève chacun de ses voisins qui contedit la règle. Chaque passage complet du nuage coûte N (y-compris la mise à jour de la triangulation)

Le côut total est donc de l'ordre de ( d + log(N) ) * N, ou d est une densité de points le long de la distance d à éviter.

Optimisation : si les nuages sont disjoints, il est possible non pas de parcourir tout le nuage, mais seulement l'enveloppe convexe des points d'une couleur donnée. (avec un problème e mon côté : trouver l'enveloppe convexe non pas d'une triangulation, mais d'un sous ensemble dans une triangulation existante).

[ol9245]

autre idée :

je récapitule l'énoncé :
on a des nuages de points (non convexes) et on veut qu'il existe une distance minimale R entre eux. en gros : qu'une bille de diamètre R puisse rouler librement autour de chaque nuage sans en toucher un autre.

Voila une suggestion d'algos:
1/ calculer les enveloppes de chaque nuage (il y a des algos qui calculent les enveloppes non convexes me semble-t-il. (*)
2/ dilater chacune des enveloppes E d'un rayon R. On considère le volume entre E et (E+R).
3/ virer tous les points étrangers se trouvant dans ce volume.

Pour optimiser, on peut aussi ordonner ces volumes par ordre croissant.

(*) si mes souvenirs sont bons, on commence à calculer une triangulation de delaunay et l'enveloppe convexe, puis on vire les vertex dont une arête est supérieure à R et un sommet appartient à l'enveloppe convexe.