In [2]:
#IMPORT
import numpy as np
import copy
import operator
from tqdm import tqdm
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.
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)
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))
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)
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
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)
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)
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))
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
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]:
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