Discussion :

[melwin]

Bonjour,

Je suis un débutant en programmation et en reprise d'étude. J'ai beaucoup de mal à analyser et à convertir en algorithme.
Donc j'aurais besoin d'aide dans un premier temps pour m'orienter et ensuite éventuellement corriger ou améliorer le programme.
Ensuite, si quelqu'un connait une méthode pour apprendre justement à analyser ce que l'on souhaite programmer.

Je dois élaborer un petit programme en python qui simule une chaîne de Markov.
Le système est composé de 3 états. Il y a des probabilités identique de transitions entre chaque états.
Il y a aussi des probabilités de rester sur le même état.

Pour les variables:
- matrice: matrice 3*3 décrivant les probabilités de transition.
- tableau: distribution initiale, état de départ.
- Nombre : le nombre de pas à effectuer
Fonctions:
- Transition (etat,matrice) : prend l'état de la chaîne et retourne un état de la chaîne.
- probChange (matrice, tableau, nombre): calcule les fréquences de passage sur chacun des états pour obtenir les valeurs théoriques de la limite de la chaîne.

[php_faboul]

Bonjour,

Quel est le problème ?

[melwin]

Bonjour,

Quel est le problème ?

j'ai du mal à analyser les différentes fonctionnalités et à les décrire pour commencer.

Voilà comment je vois les choses:

Fonction1: prend en entrée "etat" de la chaine et fonction de la "matrice" retourne un nouvel "etat" de la chaîne.

Fonction2: enregistre le passage sur chaque 'etat' pour calculer les fréquences relatives de passages => passage/nombre

[fred1599]

C'est quoi un état?

Vous auriez pas plutôt un exemple?

[melwin]

Pour prendre un exemple classique, le tirage répété d'un dé (6 faces).

Chaque fois que l'on fait un tirage (transition) il y a une probabilité de retomber sur le même chiffre ou sur un autre chiffre (etat).

Pour info, la chaîne de Markov, c'est la suite des valeurs obtenues pendant les tirages.

Donc dans mon cas, il n'y a que 3 états.

Il me vient un exemple:
Régulièrement on consulte le thermomètre, la température ne change pas, elle monte ou elle descend.

Donc 3 états : monte, descend, change pas.

On se limite à un cas homogène. C'est à dire que la probabilité de se trouver à l'état Xn+1 à la consultation n+1 ne dépend que de l'état Xn à la consultation n mais pas de n. En gros on considère que la température est montée par rapport à la consultation précédente mais pas parce que c'est la 20ème consultations.

[fred1599]

La valeur lors de la consultation est aléatoire alors?

Si oui la température est comprise entre ... et ... ?

Nombre de consultations?

Selon le nombre de consultations, on peut utiliser de simples listes, il y en faut beaucoup pour utiliser numpy

Une fonction simple pour retourner ton état

Code :

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

1
2
3
4
5
def tester(actuel, suivant):
    if suivant > actuel : etat = "monte"
    elif suivant < actuel : etat = "descend"
    else: etat = "change pas"
    return etat

[melwin]

Oui, la valeur de température est aléatoire, par contre il y a des pourcentages fixes en fonction d'un état pour passer à un autre état ou pour ne pas changer.
Par exemple: si la température est à l'état "ne change pas" il à 30% qu'elle descende, 40% qu'elle ne change pas et 30% qu'elle monte.

La matrice c'est donc un tableau b-dimensionnel et la somme des 3 valeurs de chaque lignes ou chaque colonnes est égal à 1 (100%)

exemple: matrice = [[0.3,0.4,0.3][0.2, 0.6, 0.2][0.5,0.4,0.5]]



Le nombre de consultations peut être demandé au début du programme. Le but étant de calculer les probabilités empiriques de la distribution, c'est à dire lorsqu'on augmente le nombre de consultation on approche de la limite de la chaîne... la loi des grands nombre.

[fred1599]

Une matrice peut être créée par des listes de liste.

Exemple:

Code :

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

1
2
3
4
5
6
7
>>> mat = [[0 for i in range(3)] for i in range(3)] # création d'une matrice 3x3
>>> mat[0][1] = 5 # assignation de la 1ère matrice 2ème colonne la valeur 5
>>> mat
[[0, 5, 0], [0, 0, 0], [0, 0, 0]]
>>> mat[1][0] = 12
>>> mat
[[0, 5, 0], [12, 0, 0], [0, 0, 0]]

les températures aléatoires entre combien et combien?

Faut être plus précis.

Il faudra utiliser le module random

Il faudra aussi que tu donnes la version python que tu utilises (2.x ou 3.x)

[melwin]

Pour commencer, merci beaucoup pour ton aide, c'est vraiment sympa.

J'utilise la version 2.7.2 pour l'instant, c'est lié à une autre application.

J'ai modifié le poste précédent parce qu'au fur et à mesure, en voulant répondre à tes questions ça commence à s'éclaircir.

Pour les températures, il n'y a pas de limite.

Ce qui m'intéresse c'est d'arriver à faire une analyse des fonctionnalités, les classer suivant les besoins. Pour ensuite les décrire en algorithme. Après ce sera la traduction en langage.

Le but c'est effectivement de faire ce petit programme mais aussi de m'exercer à ces mécanismes. Je souhaite par la suite continuer, pour développer des applis, alors pour l'instant je bosse les bases, je me tape les tutoriels etc.

[fred1599]

Il y a fallu que je me remette dans la doc numpy (float oblige) et voici un exemple

Code :

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

1
2
3
4
>>> import numpy as np
>>> matrice = np.array([(0.3, 0.4, 0.3), (0.2, 0.6, 0.2), (0.5, 0.4, 0.5)])
>>> matrice.sum(axis=1)
array([ 1. ,  1. ,  1.4])

C'est ce que tu veux?

Si tu veux faire des tirages au hasard

Code :

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

1
2
3
4
>>> np.random.random((3,3))
array([[ 0.59028396,  0.58048832,  0.54331258],
       [ 0.6210478 ,  0.30040728,  0.50516346],
       [ 0.91399721,  0.66105523,  0.18690204]])

[melwin]

Alors les valeurs de la matrice ne change pas, on les fixes.

exemple: matrice = [[0.3,0.4,0.3][0.2, 0.6, 0.2][0.3,0.4,0.3]]

Il faut lire comme ça:
- La première ligne correspond à descend, la seconde bouge pas, troisième monte.
- Si, on est à descend il y a 30% (0.3) que cela continue de descendre, 40% (0.4) que ça ne bouge pas et 30% (0.3) que ça monte.
- si ça passe à ne bouge pas (on se base alors sur la deuxième ligne), il y a 20% (0.2) que ça descende, 60% (0.6) que ça ne bouge pas, etc...

[fred1599]

Sauf que maintenant tu as tous les éléments pour faire cela, non?

[ZZelle]

- Transition (etat,matrice) : prend l'état de la chaîne et retourne un état de la chaîne.
- probChange (matrice, tableau, nombre): calcule les fréquences de passage sur chacun des états pour obtenir les valeurs théoriques de la limite de la chaîne.

Que font exactement tes 2 fonctions ?
Transition calcule en partant de la n-ème distribution d'états (Dn, c'est le vecteur de probabilité des états) la suivante Dn+1 basé sur la transition définie dans la matrice de Markov M:
Dn+1 = transition(Dn, M) = Dn * M ?

probChange calcule la n-ème distribution à partir de la distribition initiale ? D'où
Dn = probChange(M, Do, n) ?

Sauf erreur tu auras du mal à calculer les limites de la chaîne avec ces 2 fonctions ... elles te permettront d'avoir un estimé ... il faudrait une fonction qui puisse calculer la limite d'une exponentiation (c'est le bon terme ?) de matrice pour calculer la limite (numpy c'est le faire ?)

[melwin]

C'est un peu plus clair. Je suis en train d'essayer de faire des algorithmes des différents morceaux du programme et je le publie

[melwin]

Que font exactement tes 2 fonctions ?
Transition calcule en partant de la n-ème distribution d'états (Dn, c'est le vecteur de probabilité des états) la suivante Dn+1 basé sur la transition définie dans la matrice de Markov M:
Dn+1 = transition(Dn, M) = Dn * M ?

probChange calcule la n-ème distribution à partir de la distribition initiale ? D'où
Dn = probChange(M, Do, n) ?

Sauf erreur tu auras du mal à calculer les limites de la chaîne avec ces 2 fonctions ... elles te permettront d'avoir un estimé ... il faudrait une fonction qui puisse calculer la limite d'une exponentiation (c'est le bon terme ?) de matrice pour calculer la limite (numpy c'est le faire ?)

- Transition va effectivement à partir de la n-ième distribution d'états donner la suivante n+1. Alors comme c'est en fonction de pourcentage, il va falloir faire un random entre 0< X< 1 et le comparer aux valeurs de la matrice avec un
if ... <x
faire...
else


ProbChange va incrémenter la valeur du passage sur chaque état. Cette valeur sera divisée par le nombre de passage pour en donner la fréquence.

[ZZelle]

- Transition va effectivement à partir de la n-ième distribution d'états donner la suivante n+1. Alors comme c'est en fonction de pourcentage, il va falloir faire un random entre 0< X< 1 et le comparer aux valeurs de la matrice avec un
if ... <x
faire...
else

Pourquoi tu as besoin de faire un random ? Dn+1 est fonction de Dn (que tu as) et de M (que tu as), non ?

ProbChange va incrémenter la valeur du passage sur chaque état. Cette valeur sera divisée par le nombre de passage pour en donner la fréquence.

Pas compris, ce qu'est la valeur du passage.
Quand tu dis fréquence, tu veux dire probabilité ?

[melwin]

Pourquoi tu as besoin de faire un random ? Dn+1 est fonction de Dn (que tu as) et de M (que tu as), non ?


Pas compris, ce qu'est la valeur du passage.
Quand tu dis fréquence, tu veux dire probabilité ?

En fonction d'un etat tu as les probabilités données par la matrice.
Ensuite c'est aléatoire en fonction de ces probabilités. Je ne comprends pas ton Dn *M. J'ai l'impression que Dn et M c'est la même chose.


Pour la valeur de passage: prenons le nombre de transitions égal à 100. Après les 100 transitions, imaginons qu'il y a eu 60 stable, 10 baisse et 30 monte. Fréquence relative de stable 60/100 = 0.6, fréquence relative de baisse 10/100 = 0.1, fréquence relative de monte 30/100 = 0.3 .Ça donne effectivement des probabilités de se trouver à un des état à l'instant n.

[dividee]

Ensuite c'est aléatoire en fonction de ces probabilités. Je ne comprends pas ton Dn *M. J'ai l'impression que Dn et M c'est la même chose.

Ce n'est pas aléatoire si on travaille sur la distribution de probabilité des états au lieu de travailler sur les états concrets.
Pour illustrer Dn * M = Dn+1:

Code :

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

1
2
3
                  [0.3, 0.4, 0.3]
[0.1, 0.8, 0.1] * [0.2, 0.6, 0.2] = [0.23, 0.56, 0.21]
                  [0.4, 0.4, 0.2]

Pour la valeur de passage: prenons le nombre de transitions égal à 100. Après les 100 transitions, imaginons qu'il y a eu 60 stable, 10 baisse et 30 monte. Fréquence relative de stable 60/100 = 0.6, fréquence relative de baisse 10/100 = 0.1, fréquence relative de monte 30/100 = 0.3 .Ça donne effectivement des probabilités de se trouver à un des état à l'instant n.

En travaillant comme cela par simulation, cela convergera aussi, mais beaucoup plus lentement...

[melwin]

Bon, je vais sûrement vous faire hérisser les cheveux sur la tête, mais tant pis je me jette à l'eau. Je voyais plutôt les choses comme ça:

Code :

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

1
2
3
4
5
6
7
8
9
10
tableau [baisse, 0.3, stable, 0.4, monte, 0.3]
var1 = random()
var2= 0.0
for index in range(len(tableau)):
    if var2+tableau[2]>var1:
        return tableau[1]
    elif var2 += tableau[4]>var1:
        return tableau[3]
    else
        return tableau [5]

C'est pas très propre, on doit pouvoir simplifier et je ne suis pas sur de mon coup et d'avoir bien compris la méthode utilisée.

[melwin]

c'était trop compliqué pour moi alors je le fais en 2 morceaux et puis c'est encore plus flou pour moi ce concept.

Pour le tableau ont doit pouvoir extraire les valeurs de la matrice

Code :

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

1
2
3
4
 
tableau []
for valeur in valeurEtat (etat):
    tableau.append [ etat, valeur ]