Inscription / Connexion Nouveau Sujet
Découverte d'une suite de nombres
Bonjour tout le monde,
il s'agit de mon premier post sur ce forum, je ne suis pas mathématicien.
J'ai un problème à résoudre et je pense que c'est les mathématiques qui peuvent m'aider.
Je voudrais écrire un programme ou algo qui puisse me donner une suite de nombres répétitifs retrouvés dans un ensemble de nombres. Ces suites ne pourront pas être exactement identiques, par exemple: 4, 3, 5, 100, 3, 3, 5, 117, 4, 4, 5, 112, ...
Si l'algo peut me donner 4, 3, 5, 110 par exemple, ce serait parfait.
L'idée c'est de traiter un ensemble de nombres afin de trouver une suite plus ou moins identique et l'utiliser pour prédire le nombre suivant dans un nouvel ensemble de nombres.
Quel outil de mathématique, loi, théorème me permettrait de réaliser cela ?
Petite info qui peut avoir son importance, je ne suis pas mathématicien mais informaticien 
En vous remerciant par avance
Bonjour ,
sans être sûr d'avoir compris ce que tu cherches à obtenir , tu pourrais à partir de la liste initiale créer une 2° liste de couples (chiffre, nombre d'apparitions) .
Ensuite il suffit d'exploiter (trier , ...) cette 2° liste .
Cordialement
Bonjour,
merci pour ta réponse.
Juste pour clarifier: j'ai un système qui génére des nombres (peu importe l'origine). Lorsque je fais un représentation graphique ou que je lis les nombres que j'ai enregistré dans un fichier, je vois qu'ils suivent toujours le même "schéma": eg. petit nombre, petit nombre, petit nombre, grand nombre. Ces nombres sont très rarement les mêmes mais ils sont relativement proches, ce qui fait que le schéma reste le même.
Je voudrais extraire ce 'schéma'.
L'utilisation que je veux en faire est pour détecter ce schéma dans un flux en temps réel et à partir de la périodicité de ce schéma dans le flux, anticiper/prévoir les prochains nombres.
fm_31, comment exploiter les statistiques (je suppose qu'on parle de densité dans la liste que tu proposes) pour extraire ce schéma ?
Bonjour,
comme la suite est "quasimemt presque périodique" par hypothèse, on peut imaginer effectuer une décomposition en série de Fourier (FFT) sur les échantillons obtenus
ensuite les suivants seront obtenus en extrapolant cette série de Fourier, à laquelle on ajouterait un bruit aléatoire vu qu'il est de toute façon illusoire de vouloir prédire les termes suivants d'une suite dont on ne connait pas à priori une expression mathématique.
Le quasiment périodique étant uniquement et rien que une hypothèse (j'aurais même envie d'ajouter "gratuite")
Des documents sur le "traitement numérique du signal" (transformée en z etc) pourraient aussi donner des idées exploitables... ?
Une solution très simple pour un informaticien, si la pseudo période est supposée constante :
En appelant n la longueur de la série traitée...
Pour periode = 1 à n/2
Extraire les sous-suites successives de longueur = periode
Calculer la sous-suite moyenne
Calculer l'écart-quadratique moyen des sous-suites (~ "distance" à la suite moyenne)
Sélectionner la "période optimale" qui donne le moindre écart
Afficher la suite moyenne correspondant à la période optimale
Afficher un ou plusieurs indicateurs de la qualité de l'ajustement (fluctuations) :
suite des écarts moyens à la suite moyenne
suite des écarts moyens relatif
affichage sur une courbe (suite moyenne + fluctuations)
En bonus : étudier un critère statistique qui diagnostiquerait si le schéma trouvé est significatif.
Autre bonus : étudier le critère qui hiérarchise au mieux les différentes périodes candidates...
... il y a peut-être mieux que le moindre écart quadratique, selon la nature du problème traité...
Bonjour mathafou,
je vais aller jeter un oeil du côté des transformées de Fourier. Je n'ai jamais utilisé cet outil, c'est l'occasion
Quand tu parles de 'bruit' aléatoire, qu'est ce que tu entend par là ?
Merci pour ta réponse.
Pour un contrôle en continu, il faut préciser si on observe toute la série à mesure qu'elle s'allonge, ou si on se limite par exemple à une longueur maximale et donc à une série "glissante".
Dans tous les cas, il est possible d'optimiser l'algorithme que j'ai proposé, dans le cadre d'une application à un processus continu. Pour cela, on stocke ce qu'il faut sur le calcul des critères utilisés, pour les adapter avec la dernière valeur connue. Ce qui évite de refaire une grande partie des calculs déjà réalisés.
que tu as "prédit" 4, 3, 5, 110
mais que ça aurait tout aussi bien pu être 3,6,5,109 ou absolument n'importe quoi de "proche"
et donc que tu peux ajouter à disons 5,5,5,110 une valeur aléatoire à chacun des 4 nombres indépendamment.
avec ton exemple ça sera tout aussi "pertinent".
On pourrait voir ce que je propose comme une sorte d'analyse de variance (ANOVA) pour chaque période envisagée, avec sélection de la période qui livre l'ANOVA la plus significative : moindre variance inter groupes par rapport à la variance intra groupes.
@mathafou: d'accord, j'ai compris. Merci !
@LeDino:
- mmh, je pense que le problème va être justement de déterminer cette période. Du coup, il va peut-être falloir utiliser la TF que propose mathafou, non ?
- est-ce que l'algorithme que tu proposes porte un nom ?
- mmh, je pense que le problème va être justement de déterminer cette période.
Du coup, il va peut-être falloir utiliser la TF que propose mathafou, non ?
Pas sur l'adéquation de l'approche de mathafou... mais plutôt sur le fait que tu saches la mettre en œuvre.
Ton problème relève de la prévision sur séries chronologiques. Il y a diverses façons de "capter" des périodicités ou autres cycles... Mais pour cela il faut postuler des "formes" de modèles... Ce n'est pas quelque chose qui s'improvise ou que tu peux faire facilement "par correspondance" si tu n'as pas les connaissances et l'expérience.
L'intérêt de ce que je te propose réside dans le fait que c'est empiriquement très simple (tout en étant parfaitement rigoureux si tu fais les choses proprement) et que tu devrais avoir beaucoup moins de mal à le mettre en œuvre.
- est-ce que l'algorithme que tu proposes porte un nom ?
!
Il s'agit d'un simple ajustement de série chronologique par un modèle dont tu as toi même défini les degré de liberté. Avec comme critère les moindres carrés entre le modèle et l'observé... mais il pourrait y avoir d'autres critères : tout dépend de la nature de la série et des conséquences des décisions que tu prendras en appliquant le modèle (point très important que tu n'as pas évoqué pour l'instant...).
Ici la particularité, c'est de répéter cette modélisation pour chaque valeur de période possible, pour trouver celle qui produit le meilleur ajustement.
Bon, j'essaye de comprendre ta proposition mais je coince, c'est peut-être à cause du vocabulaire. Est-ce qu'on pourrait prendre un exemple ?
Désolé, j'étais en train d'éditer mon post pendant que ton exemple arrivait.
Je te remercie beaucoup d'avoir pris le temps de réaliser cet exemple.
Je regarde ...
Exemple, pour p=2 : on considère que la période est 2.
Donc la série devient une succession de séquences de longueur 2 :
4 3 5 100 3 3 5 117 4 4 5 112
4.3 est la moyenne de 4 5 3 5 4 5
56.5 est la moyenne de 3 100 3 117 4 112
La séquence moyenne qui en résulte sera : 4,3 56,5
... qu'on peut si l'on veut arrondir à : 4 57
On compare alors la série d'origine avec la série de répétition de la séquence qu'on vient de trouver.
4 3 5 100 3 3 5 117 4 4 5 112 (observé)
4 57 4 57 4 57 4 57 4 57 4 57 (modèle)
Si l'écart entre les deux séries (observé et modèle) est faible : l'ajustement est bon.
Au final : on sélectionne la meilleure période (p*) : celle qui offre le meilleur ajustement.
C'est comme ça que l'algorithme trouvera naturellement que p*=4 offre de loin le meilleur ajustement.
Merci encore pour ton exemple. Je comprend un peu mieux maintenant ton approche et je la trouve intéressante.
Il y a une chose qui m'échappe. ERR est la racine carrée de la moyenne de "écarts quadratiques". Comment as-tu calculé ces écarts quadratiques ?
Il y a une chose qui m'échappe. ERR est la racine carrée de la moyenne de "écarts quadratiques". Comment as-tu calculé ces écarts quadratiques ?
Je prend chaque terme de la série et je calcule son écart avec la série "modèle" (répétition de la séquence périodique, autant que nécessaire). J'élève au carré chaque terme. J'additionne ces carrés. Je divise par le nombre de termes pour homogénéiser (avoir une distance ramenée à la mesure). Et enfin j'extrais la racine carrée.
Il y a plein de façons d'évaluer la distance entre deux séries.
Celle-ci est assez standard en modélisation.
Elle a certaines propriétés, et en particulier elle pondère fortement les écarts importants.
Et elle est valable dans une grande majorité de cas.
De toutes façons, les différentes métriques aboutiront souvent à désigner la même période comme optimale, surtout si cette période est vraiment avérée : le résultat sera flagrant quelle que soit la métrique;
Mais en toute rigueur tu pourrais choisir une autre métrique, en fonction de la nature supposée de la série. Tu sais quand même de quoi il s'agit et les types de valeurs que tu peux obtenir ainsi que leur signification et conséquences... En fonction des impacts des décisions qui dépendront de ton modèle prédictif, tu peux avoir intérêt à favoriser des effets différents.
Par exemple :
Minimiser les écarts importants
Minimiser le nombre de prévisions en dehors d'un intervalle resserré
Avoir un écart moyen minimal : en valeur absolue, en valeur relative pondérée...
Toi tu sais quel usage sera fait de ton modèle. Nous non.
Donc on peut imaginer des tas de possibilités farfelues.
Par exemple, s'il s'agit d'un jeu où tu dois être proche de la cible à un point près le plus souvent possible... alors l'erreur quadratique moyenne n'est pas le meilleur indicateur.
Si en revanche il s'agit d'une application médicale et que tout écart supérieur à 20 points entraîne un décès... tu as intérêt à choisir ta métrique avec soin
...Je prend chaque terme de la série et je calcule son écart avec la série "modèle" (répétition de la séquence périodique, autant que nécessaire). J'élève au carré chaque terme. J'additionne ces carrés. Je divise par le nombre de termes pour homogénéiser (avoir une distance ramenée à la mesure). Et enfin j'extrais la racine carrée.
Ok, c'est ce que je faisais mais je trouvais un résulat légérement différent. En fait, c'était à cause des arrondissements (eg. pour le premier terme (4-4.3)2=0.9 alors que le résultat était 0.11=(4-4.3333)2
Dans le tableau, il y a 10 éléments pour les écarts à la moyenne. Je m'attendais à 12. Est-ce qu'il manquait de la place ou j'ai loupé quelque chose ?
Une autre question: cet algo repose sur le fait que le premier élément de la séquence et le premier élément de la suite périodique. Que se passerait-il si on avait une séquence démarrant au milieu de la suite ?
Dans le tableau, il y a 10 éléments pour les écarts à la moyenne. Je m'attendais à 12. Est-ce qu'il manquait de la place ou j'ai loupé quelque chose ?
. C'est une erreur de ma part. Désolé : j'ai fait une fausse manip.
Il doit bien y avoir logiquement 12 termes d'erreur, puisque c'est la longueur de la série.
Une autre question: cet algo repose sur le fait que le premier élément de la séquence et le premier élément de la suite périodique. Que se passerait-il si on avait une séquence démarrant au milieu de la suite ?
Si une séquence est périodique, alors elle est "cyclique"... Elle n'a pas de début ou de fin.
Donc si tu décales ta série de deux crans : 5 100 3 3 5 117 4 4 5 112 4 3
... l'algorithme trouvera simplement une séquence périodique décalée : 5 110 4 3... qui fonctionne tout aussi bien.
Donc si tu décales ta série de deux crans : 5 100 3 3 5 117 4 4 5 112 4 3
... l'algorithme trouvera simplement une séquence périodique décalée : 5 110 4 3... qui fonctionne tout aussi bien
ah oui
Je viens d'implémenter en python l'algo, de manière bourrine, et je peux retrouver les valeurs du tableau. Du coup, j'ai essayé avec des nombres qui proviennent d'une capture réelle.
J'ai la série:
223947, 1240, 1384, 1386, 1386, 217416, 1236, 1384, 1386, 1387, 214719, 1241, 1386, 1387, 1384, 213696, 1234, 1384, 1386, 1388, 219904, 1240, 1385, 1389, 1385, 212240, 1240, 1386, 1386, 1386, 214415, 1236, 1384, 1386, 1387, 214276, 1234, 1384, 1388, 1385
Et le résultat ci-dessous. Premier chiffre, c'est ERR et entre crochets la sous-suite.
Je me rend compte que l'algo detecte une suite qui se repete.
86005.74 [44728.0, 43961.0]
85693.18 [47633.0, 33981.0, 51166.0]
86004.15 [45463.0, 44045.0, 43992.0, 43877.0]
1628.8 [216327.0, 1238.0, 1385.0, 1387.0, 1386.0]
84386.37 [63570.0, 31466.0, 32581.0, 31695.0, 36916.0, 72849.0]
85035.92 [73936.0, 36721.0, 36866.0, 36916.0, 36504.0, 44563.0, 45060.0]
86003.51 [45867.0, 43527.0, 44023.0, 43935.0, 45059.0, 44563.0, 43962.0, 43818.0]
84673.56 [45868.0, 44023.0, 45061.0, 43962.0, 1349.0, 55393.0, 54426.0, 54061.0, 54572.0]
1384.19 [218246.0, 1239.0, 1385.0, 1387.0, 1386.0, 214407.0, 1236.0, 1385.0, 1387.0, 1387.0]
81521.48 [56990.0, 1351.0, 54608.0, 54061.0, 54427.0, 55356.0, 1348.0, 1385.0, 72396.0, 74176.0, 72448.0]
80332.4 [56988.0, 54063.0, 1349.0, 54463.0, 1335.0, 73395.0, 72346.0, 1336.0, 74225.0, 1338.0, 72497.0, 72302.0]
79160.51 [56990.0, 1337.0, 72155.0, 1335.0, 72395.0, 73346.0, 1336.0, 74225.0, 1338.0, 72349.0, 72447.0, 1337.0, 71671.0]
78513.32 [75572.0, 72107.0, 72344.0, 1335.0, 1385.0, 73397.0, 74176.0, 72300.0, 1335.0, 1387.0, 72497.0, 71622.0, 1313.0, 1387.0]
1453.16 [217353.0, 1237.0, 1384.0, 1386.0, 1387.0, 217199.0, 1237.0, 1384.0, 1388.0, 1386.0, 213480.0, 1241.0, 1386.0, 1387.0, 1385.0]
73574.12 [75522.0, 1337.0, 1386.0, 72350.0, 74175.0, 73347.0, 1336.0, 1386.0, 1386.0, 106814.0, 107980.0, 1314.0, 1386.0, 1387.0, 107900.0, 107466.0]
73555.84 [75573.0, 72301.0, 1335.0, 74225.0, 1338.0, 73395.0, 1313.0, 1385.0, 106813.0, 1314.0, 108053.0, 1314.0, 1386.0, 107901.0, 1310.0, 107540.0, 1310.0]
70902.7 [75522.0, 1337.0, 74225.0, 1337.0, 1386.0, 109403.0, 1311.0, 106812.0, 1313.0, 1387.0, 108053.0, 1314.0, 107901.0, 1312.0, 1384.0, 107541.0, 1311.0, 107830.0]
70919.08 [75574.0, 74176.0, 1312.0, 1386.0, 1388.0, 109401.0, 106738.0, 1312.0, 1386.0, 1387.0, 108053.0, 107828.0, 1311.0, 1386.0, 1385.0, 107542.0, 107755.0, 1309.0, 1385.0]
Ton algorithme semble correct.
J'ai calculé la même erreur type que toi (1629) pour p=5.
Le terme technique en anglais est plutôt RMSE (Root Mean Square Error) ou RMSD (Root Mean Square Deviation).
Quand on prend chaque terme de la séquence pseudo périodique, on peut aussi analyser leurs fluctuations :
Séquence périodique 216327 1238 1385 1 387 1 386
Ecart type 3434 3 1 1 1
Ecart type relatif 1,6% 0,2% 0,1% 0,1% 0,1%
Si ton modèle est valable, et stable dans le temps... alors ces écart observés sur le passé sont à peu près représentatif de ce qu'il devraient être sur le futur (sauf si le processus évolue dans le temps... et là tout dépend de tes hypothèses).
Dans ce cas, reste à voir comment expliquer les fluctuations et leurs évolutions...
Obéissent-elles à une tendance ?
En particulier pour le premier terme qui est plus élevé et plus fluctuant.
---
Pour choisir p* parmi 5 et ses multiples :
Il faudrait "en principe" prendre la plus petite valeur de p.
C'est celle qui "consomme" le moins de degrés de libertés, donc c'est c'elle qui produira en principe le modèle le plus "robuste", c'est à dire le plus généralisable.
Lorsque tu prends p=10, tu introduis 10 paramètres dans ton modèle (les 10 valeurs moyennes qui constituent ta séquence périodique), alors que pour p=5 tu n'introduis que 5 paramètres (les 5 valeurs moyennes de la séquence périodique).
Il est donc techniquement normal de produire un "meilleur ajustement" avec 10 paramètres qu'avec 5.
Mais ce meilleur ajustement n'est que technique et n'a pas forcément de justification.
En modélisation on appelle ça un phénomène de "sur-apprentissage" ou "apprentissage par cœur".
Tout ça ce sont des considérations "générales" et c'est en fonction de ta connaissance du contexte que tu dois trancher, naturellement...
Pour sélectionner p* qui serait le plus petit p parmi ceux dont le RMSE est faible :
Trier les RMSE par valeur croissante.
Démarrer à k=2
Prendre les k premières valeurs de p.
Tant que leur PGDC est > 1 augmenter k.
Garder le plus petit p parmi ces valeurs.
J'ai passé un peu de temps à recogiter tout ça. Les maths, ça fait longtemps et c'est pas mon rayon Bref, j'ai refait tous les calculs, histoire de bien comprendre.
Je me suis rendu compte en relisant les posts que je n'ai pas donné le contexte du problème.
Sur un système, je mesure l'intervalle de temps entre deux interruptions (même interruption) et je stocke ces valeurs dans un petit tableau de 8 valeurs (ça pourrait être un peu plus). A un instant donné, j'ai besoin d'estimer quand va se produire la prochaine interruption afin de déterminer combien de temps il me reste avant celle-ci. En fonction, du temps qu'il me reste j'effectue une opération ou pas.
Une mauvaise prédiction ou une bonne prédiction n'a pas d'impact sur les intervalles suivants et n'a pas de conséquences désastreuses. Une suite continue de mauvaises prédictions provoquera une baisse des performances du système et une augmentation de sa consommation d'énérgie. Nous sommes ici dans un cas de "best effort".
Jusqu'ici, l'algo que j'ai utilisé, mesure tout simplement la moyenne de ces intervalles et ça fonctionne plus ou moins bien. Je pense si l'algo pouvait intégrer la détection des patterns répétitifs alors le nombre de bonnes prédictions serait plus important avec des conséquences très positives pour le système.
Cependant, nous sommes dans le noyau, donc il y a des contraintes d'utilisation mémoire et de rapidité d'execution très fortes. Ce qui m'inquiete c'est la lourdeur de l'algo de détection de répétition.
Bonjour,
S'il est important que l'algorithme soit très économique et que tu penses qu'il y a une période fiable et que ce qui t'intéresse c'est en fait une prédiction "binaire" du type "si le prochain Tprévu est supérieur à un seuil Tmin, alors je lance un calcul qui se glissera dans l'intervalle"... alors tu peux simplifier le processus de détection.
Tu as une suite de temps Tk.
Lorsqu'arrive un nouveau terme Tn+1 de cette suite, tu remontes la suite en arrière terme à terme et tu repères le dernier terme > Tmin (qu'on appelera un "pic"). Tu notes DERP le Dernier Ecart de Rang à un Pic. Et ensuite tu regardes si ce DERP constitue une période plausible. Simplement en observant si les termes espacés de DERP sont en majorité des pics.
L'algorithme est super simplifiable. Même pas besoin de faire une recherche pour calculer DERP : il se calculera par incrément à chaque nouveau terme Tk (Dès que se présente un pic, tu réinitialises DERP à 0 pour le T suivant)...
Et tu peux calculer le nombre de pics effectivement trouvés sur les N dernières périodes de longueur DERP. Si ce nombre dépasse un taux (par exemple 90%), tu décides qu'il s'agit bien d'une période et donc qu'il est intéressant de prédire un pic. En prime, dès que le processus est suffisamment avancé, tu aura une trace de la période repérée par l'algorithme. Tu peux alors décider de l'utiliser sans la recalculer si tu es certain de sa stabilité.
Tout ça est à régler en prototypant.
Mais c'est ce qu'on peut imaginer de plus simple d'après les informations que tu donnes.
Le point clé ici, c'est la régularité de la période.
Si tu en es certain, cet algorithme élémentaire doit fonctionner facilement et efficacement.
Si la période peut "bouger", il faut imaginer une variante du genre : y a t-il un pic dans la série à période DERP plus ou moins un rang, par exemple... Et même sans ça, l'intérêt de l'algorithme proposé c'est qu'il est capable de corriger la période au fil du temps, si celle-ci passe d'une valeur à une autre. A creuser un peu, mais avec une pondération et en ne conservant que les termes les plus récents de la suite, tu peux avoir quelque chose qui s'adapte tout seul... A paramétrer et tester, bien sûr...
Trier les RMSE par valeur croissante.
Démarrer à k=2
Prendre les k premières valeurs de p.
Tant que leur PGDC est > 1 augmenter k.
Garder le plus petit p parmi ces valeurs.
J'ai utilisé une autre méthode. Au fur et à mesure, les RMSE sont triées par ordre croissant. Ensuite, je parcours les listes en partant du RMSE le plus petit, et dés que le RMSE courant dévie de plus de 20% du min RMSE (donc le premier élément de la liste), je prend la liste la plus petite sur celles que je viens de parcourir, les suivantes ne sont plus interessantes.
J'ai utilisé une autre méthode. Au fur et à mesure, les RMSE sont triées par ordre croissant. Ensuite, je parcours les listes en partant du RMSE le plus petit, et dés que le RMSE courant dévie de plus de 20% du min RMSE (donc le premier élément de la liste), je prend la liste la plus petite sur celles que je viens de parcourir, les suivantes ne sont plus interessantes.
Dès qu'il y a un saut trop important, c'est qu'on n'est plus dans un phénomène périodique...
J'avais pensé à quelque chose de similaire mais je n'avais pas osé l'évoquer de peur que ça ne te parle pas.
C'est bien que tu aies trouvé ça tout seul
.
Annuler
connectez vous