algorithme de détermination de "sous-séries"

**Giansolo** · 01/03/2007, 14h55

C'est les mêmes données que le modèle en post 3 je crois, ou j'affiche les résultats satisfaisant avec le modèle actuel.

J'ai pas mal de données donc la je commencer par une courbe avec de bonnes sous tendances bien visibles, pour les cas ou il est plus difficile de fitter les sous séries, j'ai mis un exemple dans le meme post ou je montre ou l'algo se casse la figure.

j'avais ptet oublié de préciser que mon algo doit pouvoir être suffisament flexible pour s'adapter à plusieurs jeux de données, qui correspondent toutefois à la même tendance générale, c-a-d une grande exponentielle décroissante avec plein de sous tendances, pouvant parfois remonter à la fin (années 1990 à 2006+)

J'en profite même pour poster deux séries de données :
un exemple "facile" :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#Annee	#data
1901	1080
1911	1060
1918	1060
1924	1040
1930	1030
1934	1020
1954	1010
1958	1000
1966	995
1981	993
1988	992
1991	990
1992	986
1994	985
1996	984
1999	979
2002	978
2005	977
2006	977

un exemple plus "difficile" (j'en ait plusieurs en manche la

):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#Annee	#data
1901	478
1916	474
1928	470
1932	462
1936	461
1939	460
1948	459
1950	458
1955	454
1956	452
1960	449
1967	445
1968	438
1988	432
1999	431

pour ceux qui veulent tester le challenge.......

Sinon souviron34, n'est-il pas possible de tracer une droite de régression via une autre méthode ?

EDIT : Oui l'échelle en X n'est pas la meme, je constate aussi, mais je plot le résultat de la régression linéaire avec les coefficients obtenus par la regression à savoir :

Code :

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

1
2
3
4
5
 
A = cov(X, Y) / var(X);
B = mean(Y) - A*mean(X);
 
mod_out = A * X + B;

Avec X correspondant bien aux années (1900 -> 2006)

Le problème de la modélisation vient surement du fait que le modèle doit pouvoir trouver les sous séries de manière assez flexible (bien sur, tout dépend de ce qu'on veut observer mais après, pour le fit, on peut toujours étudier la chose avec différentes versions)...

**souviron34** · 01/03/2007, 15h10

bon je regarderais plus tard dans la journée..

D'abord je comparerais que j'ai les bonnes valeurs (j'avais fait à l'oeil d'après les courbes

)

et tu es sûr que la première forme sous-jacente est une exponentielle décroissante ? ya une explication ?

**Giansolo** · 01/03/2007, 15h30

Et bien en fait je ne suis pas sur que la première forme soit une exponentielle, ca peut peut-etre etre une forme un peu plus poussée, mais je la modélise avec quelque chose de simple (A.exp(bx) + H) d'une part parce qu'après ca devient un peu trop poussé pour moi, et que je n'ai pas les compétences suffisantes dans le domaine statistiques, et d'autre part parce que je tiens à étudier le coefficient 'b' dans ma formule (comme je le disais avant) qui est un bon indicateur.

Mais même si la courbe finale ne "fit" pas très bien la sous série, le point crucial reste avant tout de pouvoir déterminer les sous séries de manière la plus automatique possible, ou avec un degré de granularité spécifiable... je suis assez ouvert sur la méthode, tant que les sous-séries sont relativement bien trouvées, après le fit je peux le faire avec un logiciel (même si je préfère le faire moi même pour essayer de comprendre un peu).

Mais c'est un problème relativement délicat, j'ai déjà demandé conseil à quelques personnes, qui n'ont pas pu me renseigner (bon en meme temps, leur niveau de compétence en analyse numérique est sensiblement identique au mien, à savoir mauvais lol

)

et sinon ton idée de modéliser en splines pour obtenir une continuité en X et pouvoir étudier les dérivées secondes c'est encore d'actualité ? je pense que je vais le tenter voir ce que ca donne.

Edit :
voici le résultat du fittage par splines pour l'exemple 'facile':
on note effectivement que chaque vallée puis "bosse" précède la fin d'une sous-série (et le commencement d'une nouvelle).

J'ai pas encore testé sur un exemple difficile...

Edit2 :
j'en profite pour poster une série particulièrement chaotique (j'ai pas encore tout regardé, mais celle-ci est la pire de loin) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#Annee	#Data
1912	111.9
1926	111.6
1928	110.6
1932	109.8
1936	109.7
1937	109.6
1938	108.4
1939	106.6
1955	105.7
1962	104.3
1973	103.7
1976	103.5
1977	103.4
1979	102.3
1981	101.7
1997	101.1

**souviron34** · 01/03/2007, 18h26

bon j'avais pas récupéré la dernière série

mais voilà ce que j'obtiens en automatique pour les 2 courbes :

[EDIT]

Bon les splines sont connus pour leurs écarts (comme les gaussiennes) quand les points de mesure sont rapprochés (voir la fin de la deuxième courbe). Mais ça peut s'arranger..

Mais à part ça ça me semble pas mal, non ?

Bon là il n'y a aucune modélisation, juste la séparation en séries..

Je ferais l'autre plus tard

[/EDIT]

**Giansolo** · 01/03/2007, 19h39

Oui ca à l'air pas mal pour pouvoir déterminer les sous séries!
j'obtient les memes résutlats que toi concernant le fit en spline (c'est facile tu me diras avec matlab, ca le fait tout seul lol).

Si je suis ta méthode (qui semble être plutot bonne) il s'agit maintenant d'étudier les variations des dérivées secondes ?

**Giansolo** · 02/03/2007, 12h03

J'ai un peu reflechis au deux étapes de l'algorithme, et je trouve ca vraiment excellent... surtout le fait, en première partie, de pouvoir enlever les points un peu "out" par une droite de regression linéaire.

Maintenant les questions
-comment déteminer cette droite avec le type de données que j'ai ? (la regression linéaire ne fonctionnant pas (si on considère y=ax+b)).
-a partir des splines (2ème partie donc) comment déterminer la fin d'un plateau et donc l'indice d'une nouvelle sous série ? (dérivées secondes? je suis en train de regarder la...)

**souviron34** · 02/03/2007, 15h55

je n'ai pas le temps de regarder précisément, mais :

1) les courbes ne sont pas vraiment facilement modèlisables, enfin leur apparence ne donnent pas d'indication sur une tendance mathématique..
(j'inclus ici 3 fits "au plus près" avec les 3 courbes, en utilisant une interpolation exponentielle entre chaque point de mesure...)

On voit bien des "sous-séries", mais il n'y a pas l'air d'y avoir une quelquonque loi qui puisse décrire facilement.. Visiblement les exponentielles décroissantes ne marcheront pas...

2) En ce qui concerne la détermintation des sous-séries avec les splines, ce que j'avais fait était tout bêtement explorer le tableau dans le sens croissant, et dès que ça "remontait", mettre un indcateur, continuer, et là dès que ça descendait arrêter la série en cours et en démarrer une autre...

**Giansolo** · 02/03/2007, 16h40

Re! (do sol mi fa)
En ce qui concerne le fit "au plus pret", ce n'est pas vraiment nécessaire, il suffit juste de modéliser les sous-tendances générales, le modèle de fit (f(x)=A.exp(Bx)+H) que j'utilisais se casse pas mal la figure sur certaines séries (voir première page du topic), mais je travaillerais dessus dans un second temps.

Pour le moment, je m'intéresse précisémment à extraire les sous séries de manière pseudo automatique, et je dois dire que ta méthode semble particulièrement bonne!
Je pensais qu'il fallait étudier la courbure avec la dérivée seconde mais je vais essayer ta méthode de marqueur (le plus simple est parfois le plus efficace!)

J'aimerais toutefois enlever les points "out" par une droite de régression comme tu l'avais proposé, je pense que c'es tune étape indispensable de l'algorithme. Mais la régression linéaire avec y=ax+b ne fonctionne pas... je me demande si je ne devrais pas normaliser les données, réduire l'échelle des X et des Y et effectuer la régression a ce moment la pour voir quels indices sont suceptibles de disparaitre)....

**souviron34** · 02/03/2007, 17h48

re...

je te poste le code en C qui fait la séparation, mais c'est pas fullproof....

Juste une idée...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
Parametres :
 
  year et val les valeurs lues dans le fichier
  result les valeurs interpolées toutes les annees
  N : nombre de points dans le fichier
  110 : maximum de points interpoles (1900 a 2010)
 
 
 
/* 
OUVERTURE FICHIER PREMIERE SERIE
*/
   sprintf ( Ligne, "./serie0" );
 
   fich = fopen ( Ligne, "w" );
   if ( fich == NULL )
     {
       fprintf ( stderr, " ERREUR ouverrture fchier %s",Ligne);
       exit(1) ;
     }
 
   Ntot = Ntot + 1 ;
   imin = 0 ;
   imax = 0 ;
   for ( i = 1 ; i < 110 ; i++ )
     {
/* 
ON REMONTE
*/
       if ( result[i] > result[i-1] )
	 {
/*
 DEBUT
*/
	   if ( remonte == 0 )
	     {
	       remonte = 1 ;
	     }
/*
 CONTINUATION
*/
	   imax = i ;
	 }
       else
	 {
/*
 ICI C'EST LE PASSAGE NORMAL
*/
/* 
DONC SI ON DESCEND ET QU'AVANT ON MONTAIT
*/
	   if ( remonte == 1 )
	     {
	       remonte = 0 ;
	       imax = i-1 ;
 
/* 
OUVERTURE FICHIER SERIE SUIVANTE
*/
	       fclose(fich);
	       sprintf ( Ligne, "./serie%d", Ntot );
 
	       fich = fopen ( Ligne, "w" );
	       if ( fich == NULL )
		 {
		   fprintf ( stderr, " ERREUR ouverrture fchier %s",Ligne);
		   exit(1) ;
		 } 
 
	       Ntot = Ntot + 1 ;
	       imin = i ;
	       imax = i ;
	     }
/*
 SINON DESCENTE NORMALE
*/
	   else
	     imax = i ;
	 }
 
 
       if ( (1900 + i) == (int)year[N-1] ) 
	 {
	   fprintf ( fich, "%d %g\n",(1900+i),val[N-1]); 
	   break ;
	 }
       else
	 fprintf ( fich, "%d %g\n",(1900+i),result[i]); 
     }
 
   fclose(fich);

a+ et bon courage...

**Giansolo** · 05/03/2007, 10h46

Je n'ai (malheureusement) pas de compilateur C sur ma machine, il me sera difficile de tester ce code directement ! Je vais d'abord le transcrire en Octave, ca ira très bien! :-)

As-tu une idée quand à la régression linéaire simple? comment tracer la droite de régression qui approxime au mieux les points (sachant que y=ax+B ne marche pas!).

merci!

EDIT : j'ai résolu mon problème à propos de la régression linéaire, c'est mon echelle qui était mauvaise! :-(
Je vais maintenant essayer de déterminer quels points seront à traiter dans les sous séries (tu proposais sigma<1.5 je crois).

EDIT2 : Comment calcules-tu ton erreur sigma? s'agit-il des résidus ? Sigma(i) = y(i) - a*x(i) - b ?

**souviron34** · 05/03/2007, 15h31

Envoyé par Giansolo

EDIT2 : Comment calcules-tu ton erreur sigma? s'agit-il des résidus ? Sigma(i) = y(i) - a*x(i) - b ?

Normalement c'est de la statistique :

Ecart = (Somme ( (y[i] - a*x[i] -b) au carré ))/N
Sigma = (1/sqrt(2*PI)) * sqrt(Ecart)

Et en général on dit que la valeur estr trop éloignée lorsqu'elle est supérieure à 2*sigma

**Giansolo** · 05/03/2007, 17h08

ah, merci pour cette information.
Je n'ai (malheureusement) aucune connaissance en stats à part mes souvenirs de lycée mais je potasse ca.

Sinon un petite question :
Ton algo sélectionne les sous parties quand celles-ci redescendent, mais j'ai des courbes ou la tendance générale est complètement inverse, cà dire que la tendance générale de la courbe est croissante au lieu d'être décroissante. Donc il faut "inverser" ton algo en quelque sorte.
Du coup il y a deux solutions, ou bien j'estime avant la tendance générale, pour savoir dans quel sens faire aller l'algo ou bien je trouve quelque chose de plus "générique" me permettant de trouver les vallées et les bosses.

Dans cet ordre d'idée je regardais la dérivée seconde, troisième et quatrième... Quels est l'intérêt des troisièmes et quatrièmes ? j'ai cru lire qu'en physique on s'en servait pour trouver l'accélération notamment...

**souviron34** · 05/03/2007, 17h21

il me semble que la dérivée seconde dans une courbe donne la courbure, et en physique l'accélération... (voir la gravité).

Oui mon algo est grossier... C'était juste pour voir si ça pouvait se faire. Et oui, on pourrait l'inverser si la pente est en sens inverse.

Disons qu'avec une approximation polynomiale (cubique) ce serait sans doute plus facile d'isoler les termes du second ordre...

Mais cela doit pouvoir se faire avec le spline, puisqu'il est cubique aussi.

Je pense (mais juste comme ça, de tête) que si tu imprimes la matrice de sortie du spline avant l'interpolation, tu auras les coefficients, et donc je soupçonnes qu'on devrait voir une inversion de signe lorsqu'on franchi les points d'inflexion.

.....

**Giansolo** · 06/03/2007, 17h42

J'ai implémenté ton algo avec quelques modifications :
-je cherche les minimums locaux
-à partir de ces minimums, je monte
-dès que je redescend, je prends la valeur suivante X réel la plus proche qui correspond.

Ca marche plutôt pas mal, meme si sur certaines séries ca à tendance à être légèrement "décalé". La dérivée seconde donne bien les points d'inflexion de courbures (proche de 0) mais les indices de démarrage des sous Séries sont parfois un "cran" plus loin...
Le gros problème restant est que quand deux points ont des valeurs proches (sur Y) et que l'écart en distance est conséquent suivant X, on obtient forcément une séparation des sous séries alors que ces valeurs peuvent être inclues dans la continuité de la pente.
Un exemple en image en pièce jointe.

J'ai regardé sur Wikipedia, et j'ai été incapable de trouver des renseignements concernant la formule sur Sigma que j'ai implémentée comme suit :

Code :

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

1
2
 
SigmaErr = (1/sqrt(2*pi)) * sqrt(Ecart);

J'ai été surpris que Pi appaisse la (bon j'ai une méconnaissance totale des stats, je ne m'attendais pas à le voir dans ce calcul), on calcule l'angle entre des vecteurs?

Je ne comprends pas très bien le calcul de l'erreur : (>2 Sigma). Ca veut dire que si la valeur (donc Y(xi)) est > 2 * sigma (une erreur calculée sur l'ensemble des points) alors on l'élimine ? Je dois me tromper, ne serais-ce pas l'erreur y[i] - a*x[i] -b plutot que Y(xi) ?

**pseudocode** · 06/03/2007, 19h34

Envoyé par Giansolo

J'ai été surpris que Pi appaisse la (bon j'ai une méconnaissance totale des stats, je ne m'attendais pas à le voir dans ce calcul), on calcule l'angle entre des vecteurs?

Non pas vraiment. En fait la formule de souviron34 est un calcul d'erreur statistique sur une loi normale.

Derriere ce terme barbare se cache une simple proba: Quelles sont les chances qu'un point X appartienne bel et bien a une population, et ne soit pas une "erreur".

Pour calculer cette proba, on doit "supposer" des "choses" sur la population: sa répartition, sa moyenne, etc... On concentre toutes ces "choses" dans ce qu'on appelle la "loi".

Il y a des "lois" qui correspondents a des cas bien connus: Loi de Bernouilli, Loi binomiale, Loi de Student, ...

**souviron34** · 07/03/2007, 01h08

absolument.. merci pseudocode de me rafraîchir la mémoire...

Je connais et j'utilise la formule par coeur depuis + 25 ans, mais j'allais juste poster un message disant que je posterais le détail théorique demain (c'est dans un bouquin que j'ai au grenier...)

ça faisait un bail que j'avais plus eu à trouver cette justification théorique... On s'fait vieux...

Et le 2*sigma correspond au fait qu'on élimine 5% (on en garde 95 %)...

Et pour l'écart, on prend le carré de la différence, car comme on en fait la moyenne, on veut pas se retrouver avec zéro comme résultat

Donc il faut ensuite en calculer la moyenne, puis la racine carrée, et ça donne l'écart moyen applicable en chaque mesure. D'où l'évaluation du sigma ensuite pour avoir une mesure correspondante à la répartition des écarts tels qu'on les attend dans la vraie vie...

Et en fait cette formule est utilisée pour la plupart des cas de mesures physiques, car elle correspond (expère-t-on) à la réalité...

**Giansolo** · 08/03/2007, 10h45

Ok, merci pour ces détails!
j'ai tout suivit (enfin je crois) jusqu'a l'évaluation de sigma, donc si j'ai bien compris on compare, pour chaque mesure, l'"écart" (y[i] - a*x[i] -b) absolu avec 2*sigma ?

Edit : euh non ca doit pas etre ca, je dois me tromper.

**souviron34** · 08/03/2007, 11h48

si si c'est bien ça ...

Si valeur absolue de la différence (valeur estimée - valeu reelle) > 2*sigma élimine le point.

Et d'autre part, en relisant un peu plus haut, pour améliorer grandement la détection du point de changement d'inflexion, tu peux remplir un tableau par interpolation chaque année, ou chaque 6 mois.... Comme ça tu auras une ligne continue en X. C'est ce que j'avais fait pour mon petit exemple (là comme c'était pour tester j'avais fait chaque année).

Bon courage

**Giansolo** · 08/03/2007, 11h56

ouais!
merci pour toutes ces infos!
je vais bosser la d'dessus illico presto

Edit : j'ai fait un premier test avec les valeurs à supprimer de la regression linéaire et ca m'enlève pret de 26% des valeurs sur l'exemple 'facile'. Mais je vais le refaire en détails la. S'pour ca qu'j'avais un doute.