<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Modèle de diffusion 
Step1:  Objectif
Le but est de prédire à partir d'un ensemble d'utilisateur infectés quels seront les utilisateurs inféctés par la suite. Pour cela nous allons représenter liens entre utilisateurs sous forme de graphe, les probabilités d'infection entre deux utilisateur seront alors représentés par les poids des arcs.
Lecture des donnees
Step2:  Creation des liste de successeurs
Step3:  Création des graphes
Step4:  Apprentissage
Fonction pour avoir la probabilité, P chapeau
Step5:  Poids du graphe assignés en random
Step6:  Fonction d'apprentissage
Step7:  Inférence
Il s'agit à partir du graphe et d'une liste des premiers utilisateurs inféctés, de déduire quels seront les suivants.
Step8:  La mean average precision
Elle permet d'évaluer notre modèle de diffusion en calculant la précision moyenne entre la liste de diffusion réelle et celle prédite par notre algorithme.
<ASSISTANT_TASK:>
Python Code:
#IMPORT
import numpy as np
import copy
import operator
from tqdm import tqdm
Explanation: Modèle de diffusion : INDEPENDENT CASCADES
End of explanation
file_train = open("cascades_train.txt")
file_test = open("cascades_test.txt")
data_train=[]
for i in file_train.readlines():
    tab = [[float(j.split(":")[0]),float(j.split(":")[1])] for j in i.split(";")[:-1]]
    tab.sort(key=lambda x: x[1])
    data_train.append(tab)
    
data_test=[]
for i in file_test.readlines():
    tab = [[float(j.split(":")[0]),float(j.split(":")[1])] for j in i.split(";")[:-1]]
    tab.sort(key=lambda x: x[1])
    data_test.append(tab)
Explanation: Objectif
Le but est de prédire à partir d'un ensemble d'utilisateur infectés quels seront les utilisateurs inféctés par la suite. Pour cela nous allons représenter liens entre utilisateurs sous forme de graphe, les probabilités d'infection entre deux utilisateur seront alors représentés par les poids des arcs.
Lecture des donnees
End of explanation
def getSuccsOfTab(tab):
    succ=[]
    for i in tab:
        succ_i=[]
        for j in tab:
            if(i[1]<j[1]):
                succ_i.append(j[0])
        succ.append([i[0],succ_i])
    return succ
def unique(liste):
    seen=set()
    seen_add =seen.add
    return [x for x in liste if not(x in seen or seen_add(x))]
succs_train = []
for line in data_train:
    succs_train.append(getSuccsOfTab(line))
succs_test = []
for line in data_test:
    succs_test.append(getSuccsOfTab(line))
Explanation: Creation des liste de successeurs
End of explanation
#optimisation au niveau du temps possible
def getGraph(succs):
    graph={}
    for h in succs:
        for i in h:
            try:
                for j in i[1]:
                    graph[i[0]].append(j)
                graph[i[0]]=unique(graph[i[0]])
                graph[i[0]].sort()
            except KeyError:
                graph[i[0]]=i[1]
    return graph
graph_train = getGraph(succs_train)
graph_test = getGraph(succs_test)
Explanation: Création des graphes
End of explanation
#liste correspond a un D
def getListPrec(liste):
    prec=[]
    for i in liste:
        if (i[1]>1):
            p=[]
            for j in liste:
                if (i[1]>j[1]):
                    p.append(j[0])
            prec.append((i[0],p))
    return prec
#listePrec obtenue avec getListPrec dun D
def getProbaOfList(listePrec,graph_weight_d):
    a={}
    for i in listePrec:
        prod=1
        for pre in i[1]:
            prod= prod *(1 - graph_weight_d[pre][i[0]])
        a[i[0]]=1-prod
    return a
#dicoPrec obtenue avec constructAllDicoPrec 
def getProbaOfDicoPrec(dicoPrec,graph_weight_d):
    a={}
    for i in dicoPrec:
        prod=1
        for pre in dicoPrec[int(i)]:
            prod= prod *(1 - graph_weight_d[int(pre)][int(i)])
        a[i]=1-prod
    return a
#fonction permettant de savoir si il existe une infection de l'element u sur v, lors d'un episode D
#si oui retourne les indices
def existLinkUV(d,u,v):
    listeSucc = getSuccsOfTab(d)
    listeU = [i[0] for i in listeSucc]
    if u in listeU:
        indiceU = np.where(np.array(listeU)==u)[0][0]
        listeV = listeSucc[indiceU][1]
        if v in listeV:
            return True
    return False
def constructDicoDsucc(d):
    dico1={}
    dico={}
    for i in d:
        dico1[i[0]]=i[1]
        dico[i[0]]={}
    for i in dico:
        for j in d:
            if(dico1[i]<j[1]):
                dico[i][j[0]]=j[1]
    return dico
def constructDicoDprec(d):
    dico1={}
    dico={}
    for i in d:
        dico1[i[0]]=i[1]
        dico[i[0]]={}
    for i in dico:
        for j in d:
            if(dico1[i]>j[1]):
                dico[i][j[0]]=j[1]
    return dico
def constructAlldicosSucc(data):
    listeAllDico=[]
    for i in data:
        listeAllDico.append(constructDicoDsucc(i))
    return listeAllDico
def constructAlldicosPrec(data):
    listeAllDico=[]
    for i in data:
        listeAllDico.append(constructDicoDprec(i))
    return listeAllDico
        
Explanation: Apprentissage
Fonction pour avoir la probabilité, P chapeau
End of explanation
#creation des poids du graph dico
def getGraphWeightRandom(graph):
    graph_weight_d={}
    for i in graph:
        dico={}
        for e in graph[i]:
            rando=np.random.rand()
            dico[e]=rando
        graph_weight_d[i]=dico
    return graph_weight_d
gInit_train = getGraphWeightRandom(graph_train)
Explanation: Poids du graphe assignés en random
End of explanation
#ne fonctionne pas
def fitModele(data_train,nbIt=1,eps=1e-1):
    succs_train = []
    for line in data_train:
        succs_train.append(getSuccsOfTab(line))
    graph_train = getGraph(succs_train)   
        
    #init    
    graph_cur = getGraphWeightRandom(graph_train)
    
    #it=0
    #ep=100000
    #while((it<nbIt) & (ep>eps)):
        #probas_chapiteau=[getProbaOfList(getListPrec(d),graph_cur) for d in data_train]
        
    
    #loop for : utilisateur u vers v 
    for m,u in enumerate(graph_cur):
        if((m % 10)==0):
            print(u)
        for v in graph_cur[u]:
            s=0
            nbUV=0
            nbnotUV=0
            for idx,d in enumerate(data_train[:3]):
                probas_chapiteau = getProbaOfList(getListPrec(d),graph_cur)
                if(existLinkUV(d,u,v)):
                    nbUV+=1
                    s+=graph_cur[u][v]*1.0/probas_chapiteau[v]
                else:
                    nbnotUV+=1
            graph_cur[u][v]= s*1.0/(nbUV+nbnotUV) # met a jour les poids
                
    return graph_cur
#pc = fitModele(data_train)
#devrait fonctionner
def fitModele2(data_train,nbIt=2,eps=1e-1):
    succs_train = []
    for line in data_train:
        succs_train.append(getSuccsOfTab(line))
    graph_train = getGraph(succs_train)   
        
    #init    
    theta_cur = getGraphWeightRandom(graph_train)
    
    for it in range(nbIt):
        dicoAS = constructAlldicosSucc(data_train)      
        dicoAP = constructAlldicosPrec(data_train)
        sommeDico={}
        compteurDuvplus={}
        compteurDuvmoins={}
        for u in theta_cur:
            sommeDico[u]={}
            compteurDuvplus[u]={}
            compteurDuvmoins[u]={}
            for v in theta_cur[u]:
                sommeDico[u][v]=0.0
                compteurDuvplus[u][v]=0.0
                compteurDuvmoins[u][v]=0.0
        probas=[]
        for i in dicoAP:
            probas.append(getProbaOfDicoPrec(i,theta_cur))
        #A OPTIMISER  
        for p in probas:
            for u in theta_cur:
                for v in theta_cur[u]:
                    try:
                        p[v]
                        try:
                            sommeDico[u][v]=sommeDico[u][v]+(theta_cur[u][v]*1.0/p[v])
                            compteurDuvplus[u][v]=compteurDuvplus[u][v]+1
                        except ZeroDivisionError:
                            pass
                    except KeyError:
                        compteurDuvmoins[u][v]=compteurDuvmoins[u][v]+1
        print(compteurDuvplus[0][1]+compteurDuvmoins[0][1])
        #maj des poids du graph
        theta_tmp = copy.deepcopy(theta_cur)  
        for u in theta_tmp:
            for v in theta_tmp[u]:
                try:
                    theta_tmp[u][v]= sommeDico[u][v]*1.0/(compteurDuvplus[u][v]+compteurDuvmoins[u][v])
                except ZeroDivisionError:
                    pass
        
        #calcul de la vraissemblance
        probas_chap=[]
        for i in dicoAP:
            probas_chap.append(getProbaOfDicoPrec(i,theta_tmp))  
        
        vraissemblance=0
        for idx,p in enumerate(probas_chap):
            for u in theta_tmp:
                for v in theta_tmp[u]:
                    try:
                        p[v]
                        try:
                            a=(theta_tmp[u][v]/p[v])*np.log(theta_cur[u][v])
                            b=(1-theta_tmp[u][v]/p[v])*np.log(1-theta_cur[u][v])
                            vraissemblance+= a+b + np.log(1-theta_cur[u][v])
                            
                        except ZeroDivisionError:
                            pass
                    except KeyError:
                        pass
        print("vraissemblance",vraissemblance)
        
        theta_cur=copy.deepcopy(theta_tmp)
    return theta_cur
pc = fitModele2(data_train,nbIt=10)
Explanation: Fonction d'apprentissage
End of explanation
#ne fonctionne pas
def inference(listeT1, graph):
    listeUP=[]
    listeU=[]
    listeTmp=[]
    
    for u in listeT1:
        for v in graph[u]:
            if (np.random.rand()<graph[u][v]):
                if(v not in listeU):
                    listeU.append(v)
                    listeUP.append((v,graph[u][v]))
                    listeTmp.append(v)
                    
    t=1
    while((len(listeTmp)>0) &(t<15)):
        listeTmp2=[]
        for u in listeTmp:
            for v in graph[u]:
                if (np.random.rand()<graph[u][v]):
                    if(v not in listeU):
                        listeU.append(v)
                        listeUP.append((v,graph[u][v]))
                        listeTmp2.append(v)
        listeTmp=copy.deepcopy(listeTmp2)
        t+=1
        
    listeUP.sort(key=lambda elem: elem[1])
    return  [i[0] for i in listeUP]
t1=[68.0]
print(inference(t1,pc))
#devrait fonctionner
def inference2(listeT1, graph,iteration):
    
    dicoProbaInfection={}
    for u in graph:
        dicoProbaInfection[u]=0
        
    for it in range(iteration):
        listeFinalInfected={}
        listeTM1={}
        
        #on affecte les personnes au temps T2
        for u in listeT1.keys():
            for v in graph[u]:
                if(np.random.rand()<graph[u][v]):
                    try:
                        listeT1[v]
                    except KeyError:
                        try:
                            listeFinalInfected[v]
                            #listeTM1[v]
                        except KeyError:
                            listeFinalInfected[v]=1
                            listeTM1[v]=1
        
        #on affecte les gens aux temps t3 et suivants
        t=1
        while(len(listeTM1.keys())>0 & t<20):
            listeTM1tmp={}
            for u in listeTM1.keys():
                for v in graph[u]:
                    try:
                        listeT1[v]
                    except KeyError:
                        try:
                            listeTM1[v]
                        except KeyError: 
                            try:
                                listeFinalInfected[v]
                                #listeTM1tmp[v]
                            except KeyError:
                                try:
                                    if (np.random.rand()<graph[u][v]):
                                        listeTM1tmp[v]=1
                                        listeFinalInfected[v]=1
                                except KeyError:
                                    print("le lien entre u ",u,"et v ",v," n'existe pas dans le graphe")
                        
                           
            listeTM1=copy.deepcopy(listeTM1tmp)
            t+=1
            
        for u in listeFinalInfected:
            dicoProbaInfection[u]+=1
    somme = 0
    for u in dicoProbaInfection:
        somme += dicoProbaInfection[u]
        
    for u in dicoProbaInfection:
        try:
            dicoProbaInfection[u] = dicoProbaInfection[u]*1.0/somme
        except ZeroDivisionError:
            pass
    return  dicoProbaInfection
Explanation: Inférence
Il s'agit à partir du graphe et d'une liste des premiers utilisateurs inféctés, de déduire quels seront les suivants.
End of explanation
def MAP(graph,data_test):
    s=0
    for d in data_test:
        listeD=[i[0] for i in d if (i[1]>1)]
        listeT1=[i[0] for i in d if (i[1]==1)]
        listeU=inference(listeT1,graph)
        s2=0
        for i,u in enumerate(listeU):
            intersection = [val for val in listeD if val in listeU[:i]]
            s2+=len(intersection)*1.0/(i+1)
        try:
            s+=s2/len(listeU)
        except ZeroDivisionError:
            pass
    return s/len(data_test)
MAP(pc,data_test)     
MAP2(pc,data_test)  
#devrait fonctionner
def MAP2(graph,data_test,it=2):
    s=0
    for d in tqdm(data_test):#boucle dataset
        
        listeD=[i[0] for i in d if (i[1]>1)]
        listeT1={}
        for i in d:
            if (i[1]==1):
                 listeT1[i[0]]=1     
        dicoU=inference2(listeT1,graph,it)
        listeU = [i[0] for i in sorted(dicoU.items(), key=operator.itemgetter(1))[::-1]]
        
        s2=0
        for i,u in enumerate(listeU):
            intersection = [val for val in listeD if val in listeU[:i]]
            s2+=len(intersection)*1.0/(i+1)
        try:
            s+=s2/len(listeU)
        except ZeroDivisionError:
            pass
    return s/len(data_test)
MAP2(pc,data_test)  
Explanation: La mean average precision
Elle permet d'évaluer notre modèle de diffusion en calculant la précision moyenne entre la liste de diffusion réelle et celle prédite par notre algorithme.
End of explanation
<END_TASK>