Discussion :

[Oliveuh]

Bonjour,
J'ai un certain nombres de données que je souhaite approximer sous forme d'une équation linéaire :
V(x1, ..., xN) = k1 * x1 + k2 * x2 + ... + kN * xN avec N un entier fixé
Je connais différentes valeurs V(x1, ..., xN) pour des xi donnés avec 1 <= i <= N
J'ai beaucoup de mesures de V(x1, ..., xN) donc beaucoup d'équations.
Comment déterminer (ou plutôt approximer) les coefficients ki ? (sachant que j'ai un système d'équations ayant plus d'équations que d'inconnues)

Je cherche des algos me permettant de répondre à mon problème, voire un projet Java (voire C++) me permettant de résoudre ce type de problème.

Merci pour vos réponses !

[Mac LAK]

Salut.

Je suis peut-être un peu crevé, mais j'avoue que j'ai un peu de mal à saisir où est ton problème...

Tu as un nuage de points plus ou moins linéaires, et tu cherches la droite approximant au mieux ce nuage, c'est bien ça ?

Si c'est bien le cas, ça s'appelle une régression linéaire (linear regression). Une "variante" est la régression affine, qui est quand même la plus utilisée. En général, on fait un abus de langage et on parle de "régression linéaire" même lorsque c'est une régression affine.
D'un point de vue mathématique, ça fait partie des statistiques.

Une recherche sur le net te donnera pas mal de réponses, normalement.

Déjà, un cours théorique sur le sujet :
http://nte-serveur.univ-lyon1.fr/nte...urs/chap1b.htm

Ensuite, de quoi regarder comment ça marche :
http://www2.ac-lyon.fr/enseigne/math...di1.html#seq16 (un fichier ZIP est à télécharger).
http://www.stat.sc.edu/~west/javahtml/Regression.html


En anglais, mais correspondant exactement à ce que tu veux :
http://www.math.csusb.edu/faculty/st...s/regress.html (applet + sources Java)


Note : Il existe beaucoup de types différents de régressions, notamment les régressions hyperboliques, factorielles, polynomiales, etc... Fais attention, si c'est uniquement une régression linéaire qu'il te faut, de ne pas confondre.


Et si ça résoud ton problème, n'oublie pas de cliquer sur [Résolu]...

A+ !

[Oliveuh]

Tout d'abord, merci pour ton aide.
J'avais déjà regardé du côté de la regression linéaire et des regressions multiples mais à mon avis, cela sera trop complexe.

Voilà, ce que je cherche à faire. Je cherche à approximer les coefficients Ki de plusieurs équations du type : V = Sum(Ki * Vi) avec 1 <= i <= N et Ki réels
(dans mon cas N = 133)
Donc par exemple, j'aurai des mesures qui vont me donner des équations comme celles ci :

125124 = K1 * 80500 + K2 * 22 + K3 * 0 + K4 * 0 + K5 * 1
101007 = K1 * 60512 + K2 * 24 + K3 * 1 + K4 * 0 + K5 * 1
21512 = K1 * 40125 + K2 * 19 + K3 * 1 + K4 * 0 + K5 * 0
25124 = K1 * 50832 + K2 * 22 + K3 * 0 + K4 * 1 + K5 * 1
120749 = K1 * 36500 + K2 * 22 + K3 * 0 + K4 * 1 + K5 * 0
171139 = K1 * 94500 + K2 * 18 + K3 * 1 + K4 * 1 + K5 * 1
325124 = K1 * 99978 + K2 * 19 + K3 * 1 + K4 * 1 + K5 * 1
...

Et je cherche à approximer K1, K2, K3, K4, K5. Sachant que mon système va s'enrichir de plusieurs mesures par minutes.

Donc je ne pense pas que la régression soit efficace. Je pense qu'il serait mieux de résoudre des systèmes de N équations à N inconnues. Donc déterminer les Ki pour chaque système d'équations et de faire une moyenne des Ki.

Qu'en pensez-vous ?

[Mac LAK]

Tout d'abord, merci pour ton aide.
J'avais déjà regardé du côté de la regression linéaire et des regressions multiples mais à mon avis, cela sera trop complexe.

Complexe ??? Faut pas exagérer, c'est simple, comme algo !! On peut coder ça en une cinquantaine de lignes sans forcer !

Voilà, ce que je cherche à faire. Je cherche à approximer les coefficients Ki de plusieurs équations du type : V = Sum(Ki * Vi) avec 1 <= i <= N et Ki réels
(dans mon cas N = 133)
<snip>
Et je cherche à approximer K1, K2, K3, K4, K5.

Sachant que ton système ne va pas être simple à résoudre (avec 133 inconnues, on s'en serait douté), tu risques d'être pas mal ennuyé pour le résoudre (valeurs exactes, en admettant que ce soit possible), comme pour approcher les solutions. Vu le nombre d'inconnues, passer par un simili pivot de Gauss me semble la seule approche raisonnable en terme de temps de calcul... Cependant, j'avoue aussi ne pas avoir passé des heures à réfléchir sur le problème.

Sachant que mon système va s'enrichir de plusieurs mesures par minutes.

Ca, c'est pas un problème : plusieurs valeurs par minute, c'est très très lent... Tu peux refaire les calculs à chaque fois s'ils ne sont pas itératifs, ou presque.

Donc je ne pense pas que la régression soit efficace.

Ben si, elle l'est : as-tu testé la petite applet Java dont je t'ai donné le lien précédemment ? Malgré le langage, le calcul d'une nouvelle droite de régression est instantané à l'oeil humain lorsque tu rajoutes des points...

Je pense qu'il serait mieux de résoudre des systèmes de N équations à N inconnues. Donc déterminer les Ki pour chaque système d'équations et de faire une moyenne des Ki.

Déjà, tu n'est pas certain de pouvoir résoudre ton système. Comme je te l'ai dit, avec autant d'inconnues, ça va être très long, surtout si tu multiplie les systèmes NxN !! De plus, la moyenne de tes Ki n'est pas du tout la bonne solution, sur ce coup : ce n'est pas forcément la meilleure solution. Afin d'éliminer les aberrations, il faudra de toutes façons faire une régression linéaire (qui se résume à minimiser la somme des carrés des distances) pour trouver le Ki "idéal", mais ça pourrait perturber le calcul des autres Ki si les coefficients sont corrélés.

Si tes Vi sont aussi différents que ceux de ton exemple, voici ce que je ferais :
- Approximation des K1 par régression linéaire. Les points du nuage sont calculés en ignorant complètement les Vi/Ki (i>1).
Ex :

Code :

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

1
2
3
4
K1_1=125124/80500
K1_2=101007/60512
K1_3=21512/40125
etc...

A partir de là, tu as un nuage de points qui peut être approché par une régression linéaire (attention, la moyenne ne convient pas !!). Comme la droite sera horizontale, tu vas obtenir ton K1 approché très facilement, car les calculs sont grandement simplifiés dans un tel cas.
- Réintégration du K1 "approché" dans les équations d'origine, et suppression du paramètre (car K1 est connu, donc K1*V1 peut être oté du 1er membre de l'équation).
- On refait la même manip pour K2, puis K3, etc... jusqu'à ne plus avoir de coefficients à approcher.

De cette manière, tu "précible" tes coefficients en fonction de celui qui a le plus de poids, puis tu affine le résultat avec le 2nd coefficient (toujours en terme de poids), etc...

Ca s'apparente à la décomposition d'un nombre dans une base numérique un peu étrange.

Ai-je été assez clair ? Sinon, n'hésites pas à demander.

[ceugniet]

Salut,

Je connais un peu de maths, mais rien aux statistiques... Enfin, à vue de nez, il semble que tu doives résoudre un système avec plus d'équations que d'inconnues.

SI TU N'AIMES PAS LES MATHS : SAUTE à "EN PRATIQUE" ...

A priori, c'est donc impossible. Cependant, les mesures que tu fais étant, je suppose, entâchées d'erreurs, en fait, lorsque tu dis :

125124 = K1 * 80500 + K2 * 22 + K3 * 0 + K4 * 0 + K5 * 1

tu veux dire :

K1 * 80500 + K2 * 22 + K3 * 0 + K4 * 0 + K5 * 1 proche de 125124

Je te dis tout de suite que si ce n'est pas cela, alors soit ton système n'a pas de solutions, soit certaines équations sont surabondantes, en ce sens que l'on pourrait les déduire des autres. Dans ce dernier cas, il faudrait trouver 5 équations (dans le cas où tu as 5 inconnues Ki) qui forment un système ayant une solution et automatiquement, toutes les autres équations seront vérifiées. Mais je doute que ce soit le cas...

Dans le premier cas donc, on voudrait trouver 5 coefficients (m dans le cas général) tels que ces 7 équations (n dans le cas général) soient vérifiées "au mieux", c'est à dire :

K1 * 80500 + K2 * 22 + K3 * 0 + K4 * 0 + K5 * 1 proche de 125124
K1 * 60512 + K2 * 24 + K3 * 1 + K4 * 0 + K5 * 1 proche de 101007
K1 * 40125 + K2 * 19 + K3 * 1 + K4 * 0 + K5 * 0 proche de 21512
K1 * 50832 + K2 * 22 + K3 * 0 + K4 * 1 + K5 * 1 proche de 25124
K1 * 36500 + K2 * 22 + K3 * 0 + K4 * 1 + K5 * 0 proche de 120749
K1 * 94500 + K2 * 18 + K3 * 1 + K4 * 1 + K5 * 1 proche de 171139
K1 * 99978 + K2 * 19 + K3 * 1 + K4 * 1 + K5 * 1 proche de 325124

Dans ce cas, il existe une méthode dite des moindres carrés qui consiste à faire la somme des carrés des différences, soit :

S = (K1 * 80500 + K2 * 22 + K3 * 0 + K4 * 0 + K5 * 1 - 125124)**2
+ (K1 * 60512 + K2 * 24 + K3 * 1 + K4 * 0 + K5 * 1 - 101007)**2
+ (K1 * 40125 + K2 * 19 + K3 * 1 + K4 * 0 + K5 * 0 - 21512)**2
+ (K1 * 50832 + K2 * 22 + K3 * 0 + K4 * 1 + K5 * 1 - 25124)**2
+ (K1 * 36500 + K2 * 22 + K3 * 0 + K4 * 1 + K5 * 0 - 120749)**2
+ (K1 * 94500 + K2 * 18 + K3 * 1 + K4 * 1 + K5 * 1 - 171139)**2
+ (K1 * 99978 + K2 * 19 + K3 * 1 + K4 * 1 + K5 * 1 - 325124)**2

et finalement à minimiser S. On cherche alors les valeurs de K1, K2,...,K5 telles que S soit minimale.

On a donc une série de n équations à m inconnues.

P(1,1)*K(1)+P(1,2)*K(2)+...P(1,m)*K(m)=Q(1)
P(2,1)*K(1)+P(2,2)*K(2)+...P(2,m)*K(m)=Q(2)
...
P(n,1)*K(1)+P(n,2)*K(2)+...P(n,m)*K(m)=Q(n)

Pour revenir à ton exemple :

125124 = K1 * 80500 + K2 * 22 + K3 * 0 + K4 * 0 + K5 * 1
101007 = K1 * 60512 + K2 * 24 + K3 * 1 + K4 * 0 + K5 * 1
21512 = K1 * 40125 + K2 * 19 + K3 * 1 + K4 * 0 + K5 * 0
25124 = K1 * 50832 + K2 * 22 + K3 * 0 + K4 * 1 + K5 * 1
120749 = K1 * 36500 + K2 * 22 + K3 * 0 + K4 * 1 + K5 * 0
171139 = K1 * 94500 + K2 * 18 + K3 * 1 + K4 * 1 + K5 * 1
325124 = K1 * 99978 + K2 * 19 + K3 * 1 + K4 * 1 + K5 * 1
...
On dira que :

P(1,1)=80500
P(1,2)=22
...
P(1,5)=1
Q(1)=125124,
...
etc.

Si j'appelle P la matrice des coefficients P(i,j), Q celle des seconds membres Q(i), K, celle des inconnues K(j) ton problème revient à minimiser

|| P*K - Q || **2 (opérations matricielles)

Si j'appelle Pt la matrice P transposée (les colonnes deviennent des lignes, les lignes des colonnes) alors, il suffit de résoudre le système :

(Pt * P) * K = Pt * Q

P étant une matrice de n lignes et m colonnes, Pt sera une matrice de m lignes et n colonnes et le produit matriciel Pt * P une matrice de m lignes et m colonnes. Quant à Pt * Q ce sera une matrice de m lignes et 1 colonne. Finalement, tu auras à résoudre un système de m équations à m inconnues. Si tes variables Ki sont linéairement indépendantes, tu as toutes les chances de pouvoir résoudre ton système. Si elles sont linéairement dépendantes, alors point de salut : cela ne marchera pas.

Il suffit donc de calculer Pt * P que j'appellerai PTP, et Pt * Q que j'appelerai PTQ :

EN PRATIQUE :

1 - Définir P et Q :

P(1,1)=80500
P(1,2)=22
...
P(1,5)=1
Q(1)=125124,
...
etc.

2 - Calculer PTP

for (int i=0;i<m;i++)
{
for (int j=0;j<m;j++)
{
PTP[i][j]=0;
for (int k=0;k<n;k++)
{
PTP[i][j]=PTP[i][j]+P[k][i]*P[k][j];
}
}
}

3- Calculer PTQ

for (int i=0;i<m;i++)
{
PTQ[i]=0;
for (int k=0;k<n;k++)
{
PTQ[i]=PTQ[i]+P[k][i]*Q[k];
}
}

4 - Reste à résoudre le système linéaire probablement bien conditionné que tu viens de créer. S'agissant d'un système où m=133, il faut moins de 6 millisecondes sur mon PC pour le résoudre (assez rapide il est vrai, 3 GHz). Et même pour un PC plus ancien, dix fois moins rapide, il faudrait environ 6 centisecondes, ce qui permet quand même de faire le calcul tout le temps...

Comme je te l'ai dit, je ne connais rien aux statistiques, mais je pense que ceci n'est rien d'autre qu'une régression linéaire...

[®om]

Vu le nombre d'inconnues, passer par un simili pivot de Gauss me semble la seule approche raisonnable en terme de temps de calcul...

À en croire mon cours sur la gestion et la propagation d'erreurs, la méthode du pivot de Gauss est complètement inutilisable sur un PC... La propagation d'erreur (due à l'arrondi en double à 53 digits) fait que le programme donne des résultats complètement farfelues (et démontré en cours de maths sur un autre exemple que celui de Gauss).

[Steki-kun]

je suis désolé s'il y a des redites, je n'ai pas tout lu.

Pour ton problème, tu sembles avoir besoin d'une approximation de la solution, donc si ton système est assez régulier, une approximation de l'inverse de la matrice n*n suffit, et ça ça s'obtient assez vite avec la méthode de Pan et Reiff (cherche sur google pour le détail mais elle est très simple). Maintenant inverser une matrice bêtement en passant par la comatrice n'est pas dramatiquement plus long pour un ordinateur moderne, donc sauf si tu dois en faire 1000 par seconde...

[Mac LAK]

Vu le nombre d'inconnues, passer par un simili pivot de Gauss me semble la seule approche raisonnable en terme de temps de calcul...

À en croire mon cours sur la gestion et la propagation d'erreurs, la méthode du pivot de Gauss est complètement inutilisable sur un PC... La propagation d'erreur (due à l'arrondi en double à 53 digits) fait que le programme donne des résultats complètement farfelues (et démontré en cours de maths sur un autre exemple que celui de Gauss).

Tout dépend : tu noteras le "simili" dans ma phrase. Il existe des manières de réduire l'erreur du pivot, notamment en ne choisissant pas les équations au hasard mais en fonction de l'erreur inverse (=> recalculer dans l'autre sens, et vérifier le delta d'erreur). On peut aussi le réduire en conservant en mémoire non pas les équations modifiées, mais une matrice d'opérations à effectuer, et on conserve ainsi les coefficients d'origine.
Mais si tu utilises la méthode "brute", il est effectivement fréquent d'obtenir des erreurs hallucinantes, notamment lors de divisions avec des valeurs très petites ou très grandes. C'est d'ailleurs ce problème des divisions qui permet encore une autre méthode de gestion des erreurs, en conservant les coefficients sous forme d'une fraction de "double", afin de limiter la disparition de bits significatifs dans la mantisse des réels.
Bref, de quoi s'amuser !

[®om]

Vu le nombre d'inconnues, passer par un simili pivot de Gauss me semble la seule approche raisonnable en terme de temps de calcul...

À en croire mon cours sur la gestion et la propagation d'erreurs, la méthode du pivot de Gauss est complètement inutilisable sur un PC... La propagation d'erreur (due à l'arrondi en double à 53 digits) fait que le programme donne des résultats complètement farfelues (et démontré en cours de maths sur un autre exemple que celui de Gauss).

Tout dépend : tu noteras le "simili" dans ma phrase. Il existe des manières de réduire l'erreur du pivot, notamment en ne choisissant pas les équations au hasard mais en fonction de l'erreur inverse (=> recalculer dans l'autre sens, et vérifier le delta d'erreur). On peut aussi le réduire en conservant en mémoire non pas les équations modifiées, mais une matrice d'opérations à effectuer, et on conserve ainsi les coefficients d'origine.
Mais si tu utilises la méthode "brute", il est effectivement fréquent d'obtenir des erreurs hallucinantes, notamment lors de divisions avec des valeurs très petites ou très grandes. C'est d'ailleurs ce problème des divisions qui permet encore une autre méthode de gestion des erreurs, en conservant les coefficients sous forme d'une fraction de "double", afin de limiter la disparition de bits significatifs dans la mantisse des réels.
Bref, de quoi s'amuser !

OK merci de la précision...
Mon prof d'algo/maths avait juste évoqué en cours le fait que la méthode de Gauss était réputée pour être très mauvaise à cause de la propagation d'erreur, mais on n'a pas étudié ça plus en détail, on n'a pas cherché d'optimisations qui permettraient un résultat "correct"...