Bonjour,
Je cherche à prédire le prochain point d'une courbe.
Elle représente le nombre de place disponible d'un parking en activité.
En fonction de l'évolution du remplissage, je cherche à déterminer quelle pourra être la prochaine valeur.
Exemple:
10 - 9 - 8 - 7 - 7 - 8 - 7 - 6 - 5 - ?
réponse => probablement 4
Existe-t'il un algo ou une méthode qui puisse me permettre, à partir d'un tableau de point, de déterminer la prochaine valeur.
Merci d 'avance.
Sebastien
Le meilleur algorithme que j'ai pu trouver:
Ams, tram, gram,
Pic et pic et colégram,
Bour et bour et ratatam,
Ams, tram, gram.
Super marrant !
J'aurais pensé que dans ce forum on aurait pu me parler de:
* l'algorithme des moindres carrés,
* Levenberg-Marquard,
* steepest descent,
* approximation d'une courbe par une autre courbe de degré N-1 (N=nbre d'échantillons),
* etc ...
exemple de réponses que j'ai pu obtenir dans d'autres sites.
Mais bon, je me suis surement trompé d'endroit
Au revoir.
La reponse d'alligator, certes un peu abrupte, est tout a fait correcte. Tu n'as aucun, absolument aucun moyen de predire la prochaine valeur si tu n'as pas un modèle mathématique sous la main. A la limite tu peux evaluer la probabilité d'apparition de chaque nombre, mais sortir une valeur en particulier du lot ca ne tiendra pas la route.
Met n'importe quelle valeur derriere ta liste et je te trouve au choix un polynome, une fonction trigo, exponentielle, ou a peu pres n'importe quoi qui passe par tes points ou qui les approxime, au choix.
pour faire ce genre de chose il faut que tu sache quelle "tete" doit avoir la fonction qui va derriere.
Désole, mais je ne suis d'accord,
Il ne s'agit pas d'une modélisation mathématique pure.
C'est à dire que la valeur que je cherche à découvrir est issue d'un cas concret : le nombre de places libres d'un parking.
A moins que les voitures fasse du passe muraille, il a peu de chance que le courbe fasse:
10 - 9 - 8 - 7 - 7 - 8 - 7 - 6 - 5 - 255
mais plutôt
10 - 9 - 8 - 7 - 7 - 8 - 7 - 6 - 5 - 4 (ou 5, voire 3 ou 7 s'il y a 2 sorties en parallèles).
L'idée est de PROLONGER la courbe représentée par les X points mémorisés afin "d'estimer" quel pourrait être le suivant.
L'estimation n'a pas l'ambition d'être exacte : je ne cherche pas à trouver à tous les coups la prochaine valeur.
Je cherche juste à me servir de cette prédiction pour enclencher ou pas une action préventive (notamment lorsqu'on est proche du COMPLET).
Si quelqu'un a une idée ?
Les algos que j'ai cité plus haut sont un peu compliqués à appliquer.
Non pas au niveau de la programmation de l'algorithme, mais j'ai des difficultés à faire le lien entre ces algos et les X valeurs mémorisées : je ne sait pas où les mettre.
Cordialement.
Moi siEnvoyé par hash{ment}
.
Juste un exemple tes places libres
10 - 9 - 8 - 7 - 7 - 8 - 7 - 6 - 5
si la dernière valeur correspond à une heure de sortie des bureaux, il y a de forte chance que le nombre de places libres augmente très vite, si au contraire c'est l'heure où les gens vont au théatre, il y a de forte chance que ce nombre diminue tout aussi vite; comme le disais jobhertz, il te faut un modèle, sinon la méthode de aligator250 n'est pas plus mauvaise qu'une autre.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Justement non, les évolutions sont lentes par rapport à mon temps de cycle.
2 voitures "cul à cul" sont séparées d'à peine 10 secondes.
Mon processus de vérification tournera plusieurs fois par secondes, j'ai donc largement le temps de voir les évolutions, même s'il y plusieurs travées en parallèle.
J'aurais pensé que les techniques employées pour le codage de la parole (notamment dans les GSM) auraient pu m'aider.
Mais bon, ...
Peut-être que je vais finalement m'en remettre aux sciences occultes
Aie...
Bah oui, c'est bien pour ca qu'il faut une modélisation...C'est à dire que la valeur que je cherche à découvrir est issue d'un cas concret : le nombre de places libres d'un parking.
C'est pour ca que j'ai dit que tu peux raisonner en terme de probabilité, et borner les valeurs possibles... Mais prédire sans un modèle... Pas évident.A moins que les voitures fasse du passe muraille, il a peu de chance que le courbe fasse:
10 - 9 - 8 - 7 - 7 - 8 - 7 - 6 - 5 - 255
mais plutôt
10 - 9 - 8 - 7 - 7 - 8 - 7 - 6 - 5 - 4 (ou 5, voire 3 ou 7 s'il y a 2 sorties en parallèles).
Merci, prend moi pour une buse, j'avais compris..L'idée est de PROLONGER la courbe représentée par les X points mémorisés afin "d'estimer" quel pourrait être le suivant.
Peut etre parce que ces algorithmes necessitent justement d'avoir un modèle...
Les algos que j'ai cité plus haut sont un peu compliqués à appliquer.
Non pas au niveau de la programmation de l'algorithme, mais j'ai des difficultés à faire le lien entre ces algos et les X valeurs mémorisées : je ne sait pas où les mettre.
Honnetement, sans modele tu peux essayer d'appliquer des techniques de probas/stats, mais pour predire une valeur ca n'a pas vraiment de sens autant que je sache...
Et que pensez-vous d'une méthode comme celle là:
* calculer les différences entre 2 points
* pondérer chacune d'entre elle avec un facteur d'oubli différent ce qui rendrait plus importantes les dernières valeurs, par exemple en multipliant la première différence par 0,9, la deuxième par 0,9^2, la troisième par 0,9^3, etc...
* diviser la somme des différences pondérées par 0,9 + 0,9^2 + 0,9^3 + etc...
* voir si la courbe monte ou descend,
* plus la valeur calculée est petite, et plus la courbe est "plate"
* en déduire une estimation du prochain point en se basant sur la valeur calculée.
Non?
Qu'en pensez-vous ?
Il faut bien comprendre que les evenments sont a priori equiprobable !!! savoir que juste avant l'instant t 3 voitures sont sorties ne te donne aucune info sur ce qu'il va se passer ensuite !
La seule chose que tu peux faire c'est avoir une approche "globale" et reperer en moyenne quelles sont les heures de pointes dans la journée, et agir en consequence. mais estimer des veleurs individuellement ca me semble infaisable.
J'en pense que pour écrire cela tu présupposes (consciemment ou non) un modèle : le nombre de voitures est fonction linéaire des n valeurs précédentes pondérées (si le modèle est juste il faudra encore trouver les pondérations).
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Actuellement, je n'ai rien,
présupposer un modèle linéaire est déjà un point de départ.
Je suis d'accord avec vous en ce qui concerne les pondérations, elles vont devoir être réglées.
Pensez-vous qu'il puisse exister une autre méthode ?
Sauf que concretement tu as une situtation qui, autant que je la comprenne, est fondamentalement aleatoire... Donc peu d'espoir d'avoir un modele "regulier" credible....
hash{ment}, je vois principalement deux techniques:
La première consiste à simplement prolonger ta courbe par une demi-droite de même pente que la tangente en le dernier point.
C'est basique et ça suppose plusieurs choses pour être efficace:
- le nombre de places est sujet à un phénomène de tendances (pour un parking, ça semble judicieux)
- l'évolution est relativement continue
- tu ne t'intéresses qu'à l'avenir immédiat et ne cherche rien d'autre
La seconde est (beaucoup, beaucoup) plus complexe à mettre en oeuvre, mais c'est l'application typique d'un réseau de neurones...
Pour un parking, il me semble que ce n'est justement pas aléatoire (heures de bureaux citées précédemment, évènements particuliers, ...)
Un modèle, un modèle !
oui, mais lequel ?
C'est aussi ce que je recherche : une méthode "à l'aveugle" de type boite noire, ou bien un modèle à appliquer.
J'ai toute un ensemble de valeur que je peux compulser sur 24h, mais j'en fait quoi honnêtement ?
Qu'est-ce qu'il faut que je recherche ?
Réseau de neurones. C'est vraiment exactement le cas d'école.
Mais c'est pas facile à mettre en place.
Si c'est aleatoire, ce qui n'est absolument pas contradictoire avec le fait qu'il y ait des tendances globales !
Pour etre concret, ce que j'essaie de dire c'est qu'on peut observer qu'en moyenne, un jour de semaine, le parking est plein a 90% jusqu'a 18h, puis a 40% jusqu'a 19h, etc. a un sens, c'est une approche globale, statistique. Mais dire "2 voitures sont rentrés puis 3 sont sorties donc il y a de tres forte chances que 4 voitures rentre dans les 3 secondes", la ca ne tient plus. On ne peut pas estimer efficacement l'evolution a la voiture et a la seconde pres...
ça me semble pas mal, compte tenu du fait que je dois calculer une estimation du prochain point en temps réel, l'algo à l'air faisable.
C'est tout a fait ce que je supposeC'est basique et ça suppose plusieurs choses pour être efficace:
- le nombre de places est sujet à un phénomène de tendances (pour un parking, ça semble judicieux)
Oui ça me semble OK.- l'évolution est relativement continue
C'est exactement cela, juste le prochain point.- tu ne t'intéresses qu'à l'avenir immédiat et ne cherche rien d'autre
Je la calcule comment ma tangente au dernier point compte tenu des autres ?
Je suis d'accord avec toi:
vu de très près c'est aléatoire, vu de plus loin, c'est modélisable.
Vu que hash{ment} souhaite une alerte quand on s'approche d'un seuil, je pense que c'est la vue "de loin" qui l'intéresse (même si son premier énoncé n'était peut-être pas aussi clair que ça)
Euh... je dois avouer que mes restes de maths ne sont plus suffisants pour faire ça.
A ta place, je tenterais cette approximation là:
Choisis un intervalle de temps "correct" (suffisamment petit pour ne pas effacer les tendances, suffisamment grand pour que la courbe ne soit pas plate dans cet intervalle)
mettons que tu choisisses un intervalle de taille T (qui contient t mesures)
Ensuite, tu ré-échantillonnes tes points en réduisant à cet intervalle de temps (par exemple en faisant une moyenne)
Enfin, tu calcules les pentes des X (5 à 1à, par ex mais ça dépend de tes données) derniers segments obtenus.
La moyenne finale de ces segments devrait te donner un truc qui ressemble à la pente de la dernière tangente.
Désolé d'être aussi "informaticien de base", mais mes souvenirs de maths sont trop éloignés pour que je me souvienne comme calculer cette pente
Après, il faut ajuster les paramètres (T et X) pour que ça aille bien avec tes échantillons.
Note: ne prends en compte qu'une moitié de tes données pour débuter, et utilise la seconde partie pour vérifier si ça tient la route.
ça ressemble à la méthode que je pensais employer avec la moyenne pondérée des écarts entre chaque point ?
Je pense que je vais déjà partir avec cela et je verrai d'affiner les pondérations avec l'expérience.
Merci.
Bah oui, sauf que vouloir une valeur ou meme une tendance en fonction des valeurs precedente ca ne tient pas vraiment la route.. Ce qu'il faut c'est observer la totalité d'une journée type, et trouver les tendances en fonction d'autres parametres... Donc le coup de la tangente je le sens moyen...
Ca marche bien avec la bourse, pourquoi pas avec un parking ?
(Ceci n'est bien sur pas à prendre au premier degré... mais le fait est que tracer des tendances à partir du passé proche est faisable. Pas 100% fiable, mais suffisamment pour donner des alertes quand il est manifeste qu'on va droit dans le mur)
Je confirme que je cherche à déterminer le prochain point compte tenu des valeurs proches de l'instant T, et non pas à partir de l'évolution macroscopique (au fil de la journée).
En fait, il faut que je pilote des panneaux de signalisation routier (255 en tout) sur lesquels seront affichés les nombres de places restantes d'un parking (ou d'une somme de parking).
L'idée est de faire rafraîchir le plus vite possible les panneaux affichant une valeur qui :
S'il reste des places de parking
* est proche du complet,
* a tendance à chuter.
Si le parc est en complet
* viens de sortir du complet,
* a tendance à augmenter.
Ceci afin d'indiquer au plus juste, et plus vite possible, aux clients, l'évolution de la disponibilité.
Voilà pourquoi je cherche à déterminer le prochain point de ma courbe compte tenu des secondes précédentes l'instant T (et ceci pour chaque panneau).
Ouh là ! Alors dans ces conditions, je rejoins les autres: autant tirer à pile ou face.
En fait, pour pouvoir prédire quoique ce soit, tu es obligé de te reculer suffisamment pour estomper l'effet du hasard. "quelques secondes" n'est pas pour moi un recul suffisant. Dans le cadre d'un parking très fréquenté, on pourrait envisager de faire ça sur quelques (10 ?) minutes, mais là, tu demandes trop de précision.
Je ne comprends pas pourquoi.
Sur mes 255 panneaux, répartis en groupes de 7 panneaux (maximum)
Je dois analyser 7 courbes.
Sur ces 7 courbes, je cherche en fait à catégoriser la "dangerosité" d'une courbe par rapport à une autre, mais cela sur un temps de quelques secondes.
Exemple,
Entre une courbe qui me fait en 20 secondes :
1 - 2 - 3 - 4 - 4 - 3 - 5 - 7
et une qui me fait dans le même temps
10 - 8 - 6 - 4 - 3 - 2
J'aurais tendance à vouloir forcer le rafraîchissement de la seconde plutôt que de la première (dont il semble que je soit tiré d'affaire).
C'est juste un algo pour privilégier une courbe plutôt qu'une autre, pas la peine de se prendre la tête sur l'exactitude stricto-census de la méthode.
Au pire, je me trompe, je ne rafraîchirait pas le bon panneau super rapidement, il devra attendre les prochaines 6 secondes, c'est pas dramatique non plus...
Maintenant, si vous avez des idées pour résoudre cela, je suis preneur.
En fait, dans ce cas, il te "suffit" de choisir celle qui a le moins de places libres. Les quelques secondes passées ne te serviront à rien.
Même s'il semble que la suite 5-4-3-2 est plus risquée que 1-2-3-2, ce n'est pas du tout le cas:
Les deux ont la même chance de passer à 1.
C'est entièrement vrai!
Je ne cherche pas forcément à rafraîchir à toute force la courbe la plus "pertinente", je ne le peux pas (j'en ai bien conscience), d'ailleurs ton exemple le montre bien.
Par contre il semble judicieux, à mon avis, dans l'exemple que j'ai cité, d'écarter la courbe qui fuit au profit de celle chutant vers le complet.
Je cherche juste à écarter "grossièrement" les courbes non dangereuses.
J'en ai besoin pour des questions de débit sur la ligne de transmission, je préfère rafraîchir LE(S) panneau(x) pertinent plutôt que de faire un polling cyclique, bête et méchant, toute les x millisecondes.
D'ailleurs, quand il y aura télescopage, je prendrai n'importe laquelle des courbes qui se présentent.
