Discussion :

[ledjlale]

Bonjour, je cherche un/des algorithmes (regression lineraire multi-modal ou autres..) me permettant de clusteriser ce type de probleme de façon à décomposer un nuage de point en droites.



Les points pour l'exemple sont en 2D et fournis en piece jointe au cas où...

A vue de nez, on voit bien que l'on peut en ressortir au moins 2 droites (voir 3) d'à peu pres même pente. Le tout est de savoir comment.
J'ai essayé les algos fourni par ELKI mais sans succés (ou alors, j'ai du rater un truc )
J'aimerais éviter de réinventer la roue.

Merci!

[Aleph69]

Bonjour,

je n'ai jamais vu un tel problème auparavant donc je ne sais pas s'il existe des algorithmes éprouvés pour le faire. Dans le cas où tu serais amené à devoir faire ta propre méthode, il me semble qu'en combinant classification et régression linéaire, on pourrait aboutir à quelque chose d'acceptable à défaut d'être optimal.

Visuellement, tu sembles avoir plusieurs points par abscisse. Puisque tu veux deux droites, il faudrait segmenter en deux parties chaque nuage de point associé à chaque abscisse x. Tu obtiendrais donc deux classes, dont je note c1(x) et c2(x) les centres respectifs, avec la convention c1(x)<c2(x). Or, puisque tu veux avoir deux droites, tu dois chercher ces centres sous les formes respectives
c1(x)=a1*x+b1
c2(x)=a2*x+b2
avec a1, a2, b1, b2 des nombres réels.

La mise en place d'un algorithme "naïf" ne me semble pas du tout hors de portée. Classiquement, j'estimerais a1, a2, b1 et b2 au sens des moindres carrés, et je chercherais les centres de manière à minimiser les variances intra-classe et inter-classe. Tout ceci est très classique, mais la combinaison l'est moins à mon avis. Ceci dit, en écrivant proprement les choses comme un problème de minimisation sous contraintes, on doit pouvoir aboutir à un algorithme direct relativement performant. Une autre approche possible est de mettre en place un algorithme itératif alterné, c'est-à-dire trouver c1(x) et c2(x), puis estimer a1, a2, b1, b2, puis chercher à nouveau c1(x) et c2(x), puis estimer a1, a2, b1, b2, et ainsi de suite, en injectant l'information calculée à chaque étape dans la suivante bien entendu.

EDIT : la présence de valeurs aberrantes dans tes données pourrait un peu trop perturber la solution, je ne sais pas trop. Dans un premier temps, enlève les points trop éloignés, je pense notamment au trois points isolés tout en bas, ou alors essaye d'augmenter le nombres de classes/droites à chercher.

[souviron34]

bah, pourquoi pas simplement :

1 passage : une régression linéaire / moindre carrés

2ième passage : sélectionner tous les points < -sigma (ou -2 sigma), tous les points > sigma (tou +2 sigma), et tous les points entre les 2 en 3 tableaux.

3ième passage : avoir 3 régresion/moindres carrés.

[Aleph69]

Salut souviron,

effectivement ton approche a le mérite d'être vraiment simple en plus. Vois-tu comment la généraliser pour avoir seulement 2 droites, ou 4, ou 5, ou tout autre chose que 3 droites?

[souviron34]

lol

Je suppose que ça dépend du style de distribution...

Mais si c'est du style "lamellaire" comme c'est le cas ici, ça devrait pas poser de problème..

A la limite tu peux faire un seuillage "auto", en regardant par abcisse les nuages continus en ordonnées (bien que dans ces-ci au milieu ça marchera pas trop), ou en comptant les "trous" dans les premières et dernières fois où tu atteins ces "trous"..

[Aleph69]

D'accord,
éventuellement, on pourrait améliorer ta méthode en cherchant les médianes par abscisses et en faisant la première régression linéaire à partir de ces points seulement. Cela devrait éliminer le problème de la sensibilité de la méthode aux valeurs aberrantes.

[souviron34]

Ou simplement faire un premier passage sur la première régression en éliminant tous les points à , je sais pas +/- 5 sigmas, ou +/- 7..

Ou par exemple déterminer l'écart max, et éliminer tout ce qui est > à écart_max/2, ou 2/3 écart max..

Ou, encore plus juste, faire un histograme des y en fonction de x, et éliminer tous les pics "minces"..

[ledjlale]

Merci beaucoup pour vos pistes. Effectivement, ça m'a l'air plus simple que je ne le pensais, j'etais parti sur de la modification des algos de culstering à la OPTICS/DBSCAN ^^

Sinon, j'avais pensé plutôt à utiliser l'estimateur de Theil–Sen plutôt que des moindres carrés pour se rapprocher plus facilement des formes... mais je ne sais pas encore trop ce que ça vaut pour ce type de problème.

[souviron34]

bah je pense qu'au nombre de points que tu as, avec une bête première régression, puis élimination des points trop éloignés comme je mentionnais, re-calcul, et ensuite ce que je mentionnais dans ma première réponse ça devrait marcher super nickel...