Modèle de diffusion : INDEPENDENT CASCADES


In [2]:
#IMPORT
import numpy as np
import copy
import operator
from tqdm import tqdm

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


In [3]:
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)

Creation des liste de successeurs


In [4]:
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))]

In [5]:
succs_train = []
for line in data_train:
    succs_train.append(getSuccsOfTab(line))

succs_test = []
for line in data_test:
    succs_test.append(getSuccsOfTab(line))

Création des graphes


In [6]:
#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

In [7]:
graph_train = getGraph(succs_train)
graph_test = getGraph(succs_test)

Apprentissage

Fonction pour avoir la probabilité, P chapeau


In [8]:
#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

In [9]:
#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

In [10]:
#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

In [11]:
#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

In [12]:
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

Poids du graphe assignés en random


In [13]:
#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

In [14]:
gInit_train = getGraphWeightRandom(graph_train)

Fonction d'apprentissage


In [15]:
#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

In [16]:
#pc = fitModele(data_train)

In [19]:
#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

In [ ]:
pc = fitModele2(data_train,nbIt=10)

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.


In [15]:
#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))


[37.0, 11.0, 54.0, 3.0, 68.0, 4.0, 50.0, 12.0, 30.0, 55.0, 8.0, 29.0, 34.0, 89.0, 67.0, 73.0, 82.0, 57.0, 5.0, 99.0, 9.0, 75.0, 84.0, 70.0, 98.0, 90.0, 20.0, 48.0, 61.0, 96.0, 58.0, 43.0, 52.0]

In [52]:
#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

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.


In [ ]:
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)

In [ ]:
MAP2(pc,data_test)

In [122]:
#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)

In [123]:
MAP2(pc,data_test)



Out[123]:
0.13164138039898668

Optimisation de IC avec spark

Lors de l'apprentissage de l'algorithme IC, nous faisons trois boucles:

- une pour chaque episode

- une pour chaque utilisateur u qui est infecté

- une pour chaque utilisateur v qui est suceptible d'être infecté

Nous proposons de faire correspondre à la liste des épisode, une structure RDD permettant d'être "mappée". Le résultat de ce map renverra trois liste de tuples (key,value) ayant chacun pour key un tuple (u,v).

premier tuple : ((u,v),value) avec $value =\tfrac{\hat{\Theta}_{u,v}}{\hat{P}_{t_{v^D}}(v)}$ ##nous l'appelerons X

deuxième tuple: ((u,v),value) avec $value = 1$ quand $D_{u,v}+$ existe 0 sinon ##nous l'appelerons A

troisième tuple: ((u,v),value) avec $value = 1$ quand $D_{u,v}-$ existe 0 sinon ##nous l'appelerons B

Il reste à faire l'opération de reduce sur ces trois liste de tuples qui fait l'addition entre chaque pair de meme key. Il reste à map toutes les key (u,v) possible et de faire l'opération voulu c'est a dire