#!/usr/bin/env python
# coding: utf-8

# # TP3 : Parcours de graphes 

# In[ ]:


get_ipython().run_line_magic('matplotlib', 'inline')


# In[ ]:


import numpy as np
import os
import scipy.sparse as sp
import re
from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import CountVectorizer
import matplotlib.pyplot as plt
import scipy.io as io
import string


# # Exo 1 : prédiction de textes
# 
# Un texte est une séquence de caractères modélisable comme une série de tirages aléatoires selon une loi L à déterminer.

# ### Lecture des données

# In[ ]:


newsgroups_train = fetch_20newsgroups(subset='train',remove=('headers', 'footers', 'quotes'))
n = newsgroups_train.filenames.shape[0]
corpus = newsgroups_train.data


# In[ ]:


print corpus[0]


# ### Indexation des caractères

# In[ ]:


caract =['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' ']
index = {}
for i in range(len(caract)):
    index[caract[i]] = i


# ## Modèle unigramme
# Soit une séquence de symboles $x_1,...,x_t,...$. Le modèle unigramme considère chaque symbole $x_t$ comme issu d'un tirage multinomial de probabilité $(p_1,...,p_n)$ avec $\sum_i p_i =1$, où n est le nombre de symboles.

# #### Fonction de tirage aléatoire 

# In[ ]:


def tirage(p):
    # réalise un tirage multinomial à partir du vecteur de probabilités p
    v = np.random.multinomial(1,p, 1)
    return np.where(v==1)[1][0]


# #### Fonction de "nettoyage" des caractères de ponctuation et des majuscules

# In[ ]:


def nettoie(d):
    l = re.findall(r'[a-z \n]',d,re.I)
    r = string.join(l,'')
    r = string.replace(r,'\n',' ')
    #print d,'\n','-'*30,'\n',d_prim.lower()
    return r.lower()


# In[ ]:


print nettoie(corpus[0])


# ### A Faire
# 
# 1. A partir du corpus '20 newsgroups", calculez le vecteur de probabilité $(p_1,...,p_n)$ en fonction des fréquences d'apparition des différents caractères (pensez à utiliser la fonction de nettoyage ci-dessus).
# 2. Ensuite, vous utiliserez la fonction tirage ci-dessus pour générer une séquence de caractères obéissant à cette loi de probabilité.

# In[ ]:





# ## Modèle bigramme
# 
# Soit une séquence de symboles $x_1,...,x_t,...$. Le modèle bigramme considère que la probabilité d'apparition du symbole $x_t$ dépend du symbole précédent uniquement, soit $P(X_t=x_t|X_1=x_1,...,X_{t-1}=x_{t-1}) = P(X_t=x_t|X_{t-1}=x_{t-1}) $
# 
# Cette probabilité peut être représentée à l'aide d'un tableau bidimensionnel $(P_{ij})_{i,j= 1..n}$, avec $\sum_j P_{ij}=1$, où $P_{ij}$ représente la probabilité de choisir le symbole $j$ après le symbole $i$.
# 
# 1. A partir du corpus '20 newsgroups", calculez la matrice de probabilité $((p_{11},...,p_{1n}), ..., (p_{n1}, ..., p_{nn}))$ en fonction des fréquences d'apparition des différents couples de caractères dans la base.
# 
# 2. Ensuite, vous utiliserez la fonction tirage pour générer une séquence de caractères obéissant à cette loi de probabilité.

# In[ ]:





# # Exo 2 : Enron database
# 
# La base Enron contient la liste des emails envoyés et reçus par les différents employés de la société "Enron". Cette liste permet de définir un grape des échanges de messages entre employés. A partir de la structure  de ce graphe, il est possible de calculer un score de "popularité" pour chaue employé selon le principe du "PageRank" vu en cours.

# ### Liste de employés

# In[ ]:


employe = np.load('employe.npy')


# In[ ]:


employe[1191]


# In[ ]:


index = {}
for i in range(len(employe)):
    index[employe[i]] = i


# In[ ]:


index['kenneth.lay@enron.com']


# ### Lecture du graphe

# In[ ]:


G = io.mmread('M.mtx')
G = G.tolil()


# #### Affichage "matrice pleine" :

# In[ ]:


G[:10,:10].todense()


# #### Affichage "matrice creuse" :

# In[ ]:


sp.find(G[:10,:10])


# #### Liste des destinataires et nombre de messages envoyés pour l'employé 1191 :
# 

# In[ ]:


print employe[1191]
sp.find(G[1191,:])


# #### Tirage multinomial (idem exercice précédent)

# In[ ]:


def tirage(x):
    v = np.random.multinomial(1,x, 1)
    return np.where(v==1)[1][0]


# **PROBLEME**
# 
# 1. Calculer la matrice de transition $P$ à partir du graphe de liens en tenant compte des valeurs:
#   $$\forall (i,j), P_{ij} = \frac{G_{ij}} {\sum_k G_{ik}}$$
# 1. Implémenter l'algorithme PageRank simplifié (sans mise à jour de la matrice de transition) :
#   * Initialiser le vecteur $\boldsymbol{x}$ à la valeur $(1/n,1/n, ..., 1/n)$ 
#   * Pour chaque employé visité $i$ :
#     - choisir un employé $j$ au hasard parmi les liens sortants
#     - Mettre à jour le score $x_j$ de la page $j$, i.e. $$ x_j \leftarrow q \sum_{i:i\rightarrow j} P_{ij} x_i + \frac{1-q}{n}$$
#     - $i \leftarrow j$
#   
#   (q = 0.85)
# 1. Comment faire pour gérér les noeuds "cul-de-sac"?
# 1. Quelle est le score et la fonction des 10 employés les plus "populaires"?
# (voir : http://www.inf.ed.ac.uk/teaching/courses/tts/assessed/roles.txt)
# 1. Quel est le score et le rang de Kenneth Lay?
# 

# In[ ]: