Régression parabolique non triviale

[leon1789]

Le calcul issu du raisonnement foyer et droite directrice donne ceci :
a := 0.479
b := 0.537
Et l'équation de la parabole obtenue :
0 = 0.178*x^2 - 0.317*x*y + 0.142*y^2 - 0.613*x - 0.687*y

Graphe :


Je suis quand même étonné d'une telle différence. Si quelqu'un pouvait refaire les calculs pour la rotation et affinité svp.

[leon1789]

4 points (10;1) , (18;10) , (2;10), (5; 15)
le sommet est toujours en (0;0)

Le calcul issu du raisonnement rotation et coeff d'affinité donne ceci :
t := 0.727
a := 0.314
Et l'équation de la parabole obtenue (en rouge sur le graphe) :
0 = 0.164*x^2- 0.291*x*y+ 0.129*y^2- 0.621*x -0.698*y

Le calcul issu du raisonnement foyer et droite directrice donne ceci :
a := 0.470
b := 0.521
Et l'équation de la parabole obtenue (en vert sur le graphe) :
0 = 0.180*x^2- 0.325*x*y+ 0.147*y^2- 0.614*x- 0.681*y

[Ben314]

Pour la première méthode, je trouve bien la même chose.

Et, pour la deuxième méthode, si ce que tu as cherché à minimiser, (avec F=Foyer et Delta=directrice) c'est ça :

Alors ça devrait donner exactement la même chose que la première méthode.

Mais si tu as minimisé ça :

Alors c'est normal que ça donne pas la même chose.

[leon1789]

Pour la première méthode, je trouve bien la même chose.

ok, tant mieux.

Et, pour la deuxième méthode, si ce que tu as cherché à minimiser, (avec F=Foyer et Delta=directrice) c'est ça :

Alors ça devrait donner exactement la même chose que la première méthode.

c'est pourtant bien cela que j'ai minimisé (le carré d'une distance étant plus simple que la distance elle-même)

Du coup, on peut se poser la question : quelle est "la meilleure" méthode ? existe-t-elle ?
Autrement dit, comment mesurer numériquement la qualité d'un ajustement ? une mesure intrinsèque ?
La recherche de la parabole dépend de cela.

[Ben314]

Sinon, après coup; je trouve ça moyen la méthode que je propose çi dessus du fait que ça mesure la distance d'un point à la parabole en regardant la différence entre les ordonnées dans le repère "tourné" donc la façon de mesurer "l'écart" dépend de l'angle.
Et pour les points loin de l'origine, la distance calculée est beaucoup beaucoup plus grande que la distance minimale du point à la parabole. Sauf que cette dernière est très compliquée à calculer (il faut résoudre une équation du 3em degré...)

Mais bon, pour savoir si, tel quel, c'est acceptable ou pas, il faudrait savoir ce que sylvain compte faire avec sa parabole "optimum" histoire d'avoir une vague idée de ce qui est le plus pertinent à minimiser . . .

EDIT : j'ai tapé sans avoir lu ton dernier message et . . . je me pose la même question . . .

[leon1789]

S ça mesure la distance d'un point à la parabole en regardant la différence entre les ordonnées dans le repère "tourné" donc la façon de mesurer "l'écart" dépend de l'angle.

C'était un peu l'intuition que j'avais ce matin, sans trouver de "contre-exemple", je n'avais pas les idées claires.
Remarque : maintenant, c'est à peine mieux

[lyceen95]

Dans ces histoires de régression, il y a un problème récurrent.

Prenons une dizaine de points, et cherchons la droite y=ax+b qui se rapproche le mieux de ces points. On trouve une droite D1.
A partir des même points, cherchons la droite x =ay'+b' qui se rapproche le mieux de ces points. On trouve une droite D2, et ce n'est pas la même droite que D1, paradoxalement.

La méthode des moindres carrés est facile à mettre en oeuvre, mais la droite qui ressort est systématiquement trop 'horizontale' (quand on cherche avec y=ax+b).
Pour illustrer cela rapidement, à partir de 4 points disposés en carré, on va obtenir une droite horizontale. Et visiblement, c'est arbitraire, pourquoi une droite horizontale plutôt qu'une droite verticale.

Ce qu'on minimise, ce n'est pas la distance entre un point et le point le plus proche sur la droite, mais entre un point et le point de même abscisse sur la droite (et on élève ça au carré, mais ça me paraît assez sain d'élever au carré).

La méthode des moindres carrés était incontournable quand on n'avait pas d'ordinateur. C'était la seule méthode qui permettait de trouver un résultat pas trop mal, via 2 ou 3 calculs très rapides. Aujourd'hui, numériquement, par tâtonnements successifs, on doit pouvoir trouver la droite qui minimise la somme des distances point/Droite, élevées au carré.

Pour la parabole, on risque d'avoir le même souci.
Minimiser la somme des distances (au carré ou non) entre chaque point M et le point le plus proche sur la parabole (objectif n°1), ou minimiser la somme des distances entre chaque point M et le point de même abscisse sur la parabole (objectif n°2), ça va forcément donner 2 résultats différents.

Une méthode basée sur les moindres carrés va solutionner l'objectif n°2, mais l'objectif n°1 est beaucoup plus proche du vrai besoin.

[leon1789]

oui, ceci est clair. Et l'exemple de la droite pour 4 points est frappant (et c'est encore pire si on les fait tourner).

C'est un peu "chiant" de calculer la distance entre un point formel et une parabole (en prenant simplement la parabole y=x²), non ?

[lyceen95]

Compliqué, oui, mais chiant, non.

Là où ça devient chiant, c'est qu'une fois qu'on sait calculer cette distance, une fois qu'on sait sommer cette distance sur les différents points, on sait plus ou moins dériver cette somme en fonction de a ( le a de y=ax²), mais on ne sait pas trouver facilement les valeurs de a qui annulent cette dérivée. Enfin, c'est ce que j'imagine.
Et donc, on est obligé de sortir du domaine mathématique, pour aller dans le domaine 'calcul numérique', on tâtonne, on essaie différentes valeurs de a, jusqu'à trouver une valeur approchée qui minimise cette somme de distances, ou somme de distances au carré.

Dans la méthode des moindres carrés, pourquoi on choisit les carrés, et pas les valeurs des distances elles-mêmes ? Tout simplement, parce que en choisissant les carrés, on arrive à des équations qu'on sait résoudre. D'une certaine façon, c'est une arnaque. On cherche la droite qui se rapproche le mieux d'un nuage de point (celle qui minimise la somme des distances), on ne sait pas faire de façon directe, donc on va viser un autre objectif, qui lui est à notre portée.

[lyceen95]

Après quelques calculs griffonnés sur un brouillon, comment trouver la distance entre un point et une parabole.

On a la parabole P :
Et on a un point
On cherche le point qui est sur la parabole, et qui est le plus proche de
Donc on va chercher la tangente à la parabole passant par , puis l'équation de la droite normale à la parabole, passant par ce point ; forcément, si est le point de la parabole le plus proche de , cette droite normale passe par .

Pente de la parabole en :
Equation de la normale à la parabole passant par :
Cette droite doit passer par le point M, on doit donc avoir
On a donc une équation du 2nd degré, où l'inconnue est .
On sait résoudre ça ; a priori, la valeur de qui nous intéresse est celle dont le signe est le même que le signe de
Et quand on a trouvé le qui convient, calculer la distance , c'est facile.

Quand est connu, tout ça se passe bien. Quand est un paramètre (c'est le cas ici), c'est déjà plus compliqué.

[Ben314]

Pente de la parabole en :
Equation de la normale à la parabole passant par :

Ton équation (avec comme pente la dérivée), il me semble que c'est plutôt celle de la tangente elle même . . .
La normale, elle a pour pente donc pour équation et chercher les tels que cette normale passe par un point fixé revient à résoudre une équation du 3em degré (en ).
De plus ça se voit géométriquement : si tu trace la normale en un point A de la parabole autre que le sommet et que tu prend comme point M l'intersection de cette normale et de l'axe des y, il y a 3 normales qui passe par ce point : celle partant de A, celle partant du sommet et celle partant du symétrique de A par rapport à l'axe des y.
Par contre, effectivement, si on cherche des tangentes passant par un point fixé et pas des normales, il y a bien au plus 2 solutions.

[Ben314]

Il y aurait éventuellement une autre voie peut être envisageable : commencer par chercher l'équation de la conique qui "approche au mieux" ce qui est faisable avec des moindres carrés vu que ça dépend de façon linéaire des coeffs. inconnus (*) puis chercher la parabole centrée en (0,0) qui approxime "au mieux" cette conique (là, à priori, ça va pas être linéaire du tout donc avec des méthodes plus "calcul numérique")

(*) Modulo qu'on obtient la même conique en multipliant tout les coeffs. par une constante donc qu'il faut rajouter un truc si on veut obtenir autre chose que la solution triviale A=B=C=D=E=F=0. Et soit on rajoute un truc style A=1, mais dans ce cas, le min. va dépendre de qui on a fixé comme étant égal à 1, soit on rajoute un truc du style A^2+B^2+C^2=1 et là, c'est plus linéaire (mais je sais pas si c'est pas jouable quand même...)

EDIT : Mais, bon, en ce qui me concerne, si c'est pour répondre à la question de départ et pas juste pour m'amuser à chercher des méthodes rigolotes, j'aimerais bien en savoir un peu plus sur le bidules : où sont lus les points et à quoi va servie la fameuse parabole . . .

[leon1789]

Lycéen,
pour moi, les moindres carrés proviennent directement de la distance euclidienne, projection orthogonale, etc.
Et il est vrai que les calculs sont davantage faisables, qu'avec d'autres normes.

Dire que c'est la solution "la plus probable" comme le fait le comique de service, sans comprendre ce qu'il répète toujours bêtement. Il n'y a d'ailleurs aucune occurrence de probabilité ici.

[sylvain231]

Ben314 ta méthode ne marche pas, la parabole n'a rien à voir avec les points de départ, je te donne mon code C++ :

Code: Tout sélectionner

std::vector<Point2d> translatePoint2ds(const std::vector<Point2d>& points, const Point2d& sommet) {
    std::vector<Point2d> translatedPoint2ds;
    for (const auto& point : points) {
        translatedPoint2ds.push_back({point.x - sommet.x, point.y - sommet.y});
    }
    return translatedPoint2ds;
}

double E(vector<Point2d> vec,double a, double b) {
    double res = 0;
    int n = vec.size();
    for (int i = 0; i < n; i++)
        res += pow(vec[i].x, a) * pow(vec[i].y, b);
    return res / n;
}

void Parabole::fit(std::vector<cv::Point2d> points, cv::Point2d sommet) {
    this->sommet = sommet;
    points = translatePoint2ds(points, sommet);
    double bestTheta = 0;
    double minimum= std::numeric_limits<double>::infinity();
    for (double theta = 0; theta < 2 * CV_PI; theta += CV_PI / 1000) {
        double c = cos(theta);
        double s = sin(theta);
        double delta = E(points, 0, 2) * pow(c, 2) + 2 * E(points, 1, 1) * c * s + E(points, 2, 0) * pow(s, 2) -
            (pow(E(points, 2, 1) * pow(c, 3) + (E(points, 3, 0) - 2 * E(points, 1, 2)) * pow(c, 2) * s + (E(points, 0, 3) - 2 * E(points, 2, 1)) * c * pow(s, 2) + E(points, 1, 2) * pow(s, 3), 2))
                / (E(points, 4, 0) * pow(c, 4) - 4 * E(points, 3, 1) * pow(c, 3) * s + 6 * E(points, 2, 2) * pow(c, 2) * pow(s, 2) - 4 * E(points, 1, 3) * c * pow(s, 3) + E(points, 0, 4) * pow(s, 4));
        if (delta < minimum) {
            minimum = delta;
            bestTheta = theta;
        }
    }
    double c = cos(theta);
    double s = sin(theta);
    this->theta_radians = bestTheta;
    this->theta = bestTheta * 180 / CV_PI;
    this->a= (E(points, 2, 1) * pow(c, 3) + (E(points, 3, 0) - 2 * E(points, 1, 2)) * pow(c, 2) * s + (E(points, 0, 3) - 2 * E(points, 2, 1)) * c * pow(s, 2) + E(points, 1, 2) * pow(s, 3))
        / (E(points, 4, 0) * pow(c, 4) - 4 * E(points, 3, 1) * pow(c, 3) * s + 6 * E(points, 2, 2) * pow(c, 2) * pow(s, 2) - 4 * E(points, 1, 3) * c * pow(s, 3) + E(points, 0, 4) * pow(s, 4));

}


[sylvain231]

mes points pour tes tests sont :

[141, 242]
[123, 242]
[142, 243]
[143, 243]
[124, 243]
[124, 244]
[144, 244]
[144, 244]
[125, 244]
[126, 245]
[145, 245]
[145, 245]
[127, 245]
[128, 246]
[146, 246]
[146, 246]
[129, 247]
[147, 247]
[147, 247]
[130, 248]
[149, 248]
[131, 249]
[150, 249]
[150, 249]
[132, 250]
[133, 250]
[151, 251]
[134, 251]
[151, 251]
[135, 251]
[135, 252]
[152, 252]
[152, 252]
[136, 252]
[136, 253]
[154, 253]
[154, 253]
[138, 254]
[155, 254]
[139, 255]
[139, 255]
[156, 255]
[156, 256]
[141, 256]
[141, 256]
[158, 257]
[158, 257]
[142, 257]
[143, 258]
[159, 258]
[159, 258]
[144, 259]
[144, 259]
[145, 259]
[161, 260]
[161, 260]
[146, 260]
[146, 260]
[147, 261]
[162, 261]
[162, 261]
[162, 261]
[149, 262]
[164, 262]
[164, 263]
[149, 263]
[164, 263]
[150, 263]
[150, 263]
[166, 264]
[166, 264]
[166, 264]
[153, 265]
[153, 265]
[153, 266]
[167, 266]
[168, 266]
[154, 266]
[168, 266]
[154, 266]
[155, 267]
[155, 267]
[155, 267]
[156, 268]
[169, 268]
[169, 268]
[156, 268]
[170, 268]
[170, 268]
[157, 268]
[157, 268]
[157, 269]
[158, 269]
[158, 269]
[159, 270]
[172, 270]
[172, 270]
[159, 270]
[172, 270]
[172, 270]
[159, 270]
[160, 271]
[162, 272]
[162, 272]
[174, 272]
[174, 272]
[174, 272]
[163, 273]
[174, 273]
[175, 273]
[175, 273]
[163, 273]
[163, 273]
[164, 274]
[165, 274]
[165, 275]
[166, 275]
[167, 276]
[178, 276]
[178, 276]
[167, 276]
[178, 276]
[178, 276]
[178, 276]
[168, 276]
[178, 276]
[179, 277]
[179, 277]
[168, 277]
[179, 277]
[179, 277]
[179, 277]
[179, 277]
[179, 277]
[169, 277]
[179, 277]
[179, 277]
[179, 277]
[169, 278]
[180, 278]
[180, 278]
[180, 278]
[180, 278]
[180, 278]
[170, 278]
[180, 278]
[171, 279]
[171, 279]
[181, 279]
[181, 279]
[181, 279]
[181, 279]
[172, 279]
[181, 279]
[181, 279]
[182, 280]
[182, 280]
[182, 280]
[173, 280]
[182, 280]
[182, 280]
[182, 280]
[182, 280]
[182, 280]
[173, 280]
[182, 280]
[182, 280]
[183, 281]
[174, 281]
[183, 281]
[183, 281]
[174, 281]
[183, 281]
[183, 281]
[183, 281]
[175, 281]
[175, 282]
[176, 282]
[176, 283]
[177, 283]
[177, 283]
[185, 283]
[185, 283]
[185, 283]
[185, 284]
[186, 284]
[178, 284]
[186, 284]
[178, 284]
[179, 284]
[179, 285]
[180, 285]
[187, 285]
[187, 285]
[180, 285]
[187, 285]
[187, 285]
[180, 285]
[181, 285]
[181, 286]
[188, 286]
[188, 286]
[188, 286]
[188, 286]
[188, 287]
[189, 287]
[183, 287]
[189, 287]
[183, 287]
[184, 287]
[189, 288]
[184, 288]
[189, 288]
[184, 288]
[189, 288]
[185, 288]
[190, 288]
[190, 288]
[185, 288]
[185, 289]
[190, 289]
[185, 289]
[190, 289]
[190, 289]
[186, 289]
[190, 289]
[186, 289]
[190, 289]
[186, 289]
[190, 289]
[187, 289]
[190, 289]
[187, 289]
[191, 289]
[187, 290]
[191, 290]
[187, 290]
[191, 290]
[187, 290]
[191, 290]
[188, 290]
[191, 290]
[188, 290]
[191, 290]
[188, 290]
[191, 290]
[188, 290]
[189, 290]
[191, 290]
[189, 291]
[191, 291]
[189, 291]
[191, 291]
[189, 291]
[191, 291]
[189, 291]
[191, 291]
[191, 291]
[190, 291]
[191, 291]
[191, 291]
[190, 291]
[190, 291]
[191, 291]
[191, 291]
[190, 291]
[190, 291]
[191, 291]
[191, 291]

[leon1789]

Ok Sylvain, on va faire le calcul, pas de souci.
Mais quelles sont les coordonnées du sommet imposé ?

[sylvain231]

200,300

[sylvain231]

merci de votre aide

[Ben314]

Lycéen,
pour moi, les moindres carrés proviennent directement de la distance euclidienne, projection orthogonale, etc.
Et il est vrai que les calculs sont davantage faisables, qu'avec d'autres normes.
Dire que c'est la solution "la plus probable" comme le fait le comique de service, sans comprendre ce qu'il répète toujours bêtement. Il n'y a d'ailleurs aucune occurrence de probabilité ici.

Pour rebondir là dessus (j'ai hésité à répondre au premier message de Sylvain sur le sujet), je me rappelle qu'il y a un certain temps, je pensait comme Sylvain que ça serait plus "logique" de minimiser la somme des valeur absolues des différences, et que c'était pour des raisons de facilités (calculatoire) qu'on minimisait la somme des carrés des différences.

Sauf que, à force de faire des proba./stats il me semble qu'on se rend compte que la "bonne" notion de la "dispersion", ben c'est la variance et pas autre chose . . . Donc j'ai changé mon fusil d'épaule et mon opinion actuelle, c'est celle de Léon : minimiser la somme des carrés des écarts, c'est bien "la bonne" méthode et pas que pour des raisons de facilité des calculs.

[Ben314]

Sinon, concernant l'algo., j'ai uniquement testé avec Géogébra et 5 points : ça marche "relativement" bien (*).

Sinon, j'ai regardé ce que tu as programmé en diagonale et ce qu'il faut vérifié 3 fois plutôt qu'une c'est la grosse formule de calcul de pour voir si tu aurait pas recopié un coefficient de travers.

Par contre, vu ta façon de programmer, de procéder avec cette méthode, ça n'a plus aucun intérêt vu que LE intérêt de la méthode, c'est de ne parcourir qu'une seule fois la liste de points pour calculer les coeffs. E_{a,b} utiles à la suite puis d'utiliser ces coeffs. des tonnes de fois pour minimiser la fonction.
Alors que toi, tu recalcule les coeffs. à chaque itération de ta boucle pour chercher le minimum : heureusement que tu as pas des tonnes de points et que tu as coupé l'intervalle que en 1000, vu que sinon, tu pourrait toujours attendre ton résultat (mais bon, ça change rien au résultat : il faut juste 1000 fois plus de temps pour que ton programme s'exécute)

(*) le "relativement" venant du fait que je suis pas convaincu que, graphiquement parlant, que ce soit le plus "joli", mais comme je sais pas ce que tu compte faire de ta parabole, aussi bien ce coté "pas joli", c'est pas génant.