Master 2 DAC

Fouille de Donnée et Média Sociaux (FDMS)

Recommandation

Sources de données

Les plus connues:

Les algorithmes à mettre en oeuvre et évaluer (dans l'ordre)

  • Biais
  • Similarités (sur des petites bases)
  • Factorisation matricielle SVD
  • Factorisation matricielle - descente de gradient
  • Marche aléatoire dans les graphes

Evaluation

A moins de monter un site web avec beaucoup d'audience... MSE

Rapport

  • Comparaison de modèles
  • Influence de la régularisation et mise en évidence du sur-apprentissage
  • Mise en oeuvre d'une technique sur des bases plus grandes
  • Influence de le prise en compte des contenus (types des films...)
  • Tracé de l'espace latent des items en 2D + quelques analyses qualitatives

Pointeurs pour les développements

Chargement des données:

  np.loadtxt

Idée importante: garder les données sous forme de triplet (ne pas forcément les mettre sous forme de matrice) Comme un petit schéma vaut souvent mieux qu'un long discours... Voici un exemple de manipulation des triplets

Calcul des biais

filen = "ml-100k/u.data"
data = np.loadtxt(filen) # chargement du fichier

maxs = data.max(0) # extraction des nb d'utilisateurs et d'item
nu = maxs[0]+1
ni = maxs[1]+1

user_bias = np.zeros(nu)
item_bias = np.zeros(ni)
user_count = np.zeros(nu)
item_count = np.zeros(ni)

# systeme basique: plus simple de travailler sur les triplets

for iteration in xrange(len(data)):
    u = data[iteration,0]
    i = data[iteration,1]
    r = data[iteration,2]
    user_bias[u] += r
    item_bias[i] += r
    user_count[u] += 1
    item_count[i] += 1

# ATTENTION AUX DIVISIONS PAR 0 !!
user_bias /= np.where(user_count == 0, 1, user_count)
item_bias /= np.where(item_count == 0, 1, item_count)
print u"user and item biases computed."

Visualisation des résultats sous forme de distributions... Souvent très instructif!

plt.figure()
plt.subplot(211)
plt.hist(user_bias,100)
plt.title('Utilisateur')
plt.subplot(212)
plt.hist(item_bias,100)
plt.title('Item')
plt.savefig("recoBias.pdf")

Calcul des similarités

Un programme basic de calcul des similarités... Un peu lent (~2 minutes) mais ça calcule ce qu'il faut. Pour ceux qui veulent gagner du temps: calculer une fois pour toutes les matrices correspondant aux 5 folds et sauver les à l'aide de pickle.

def calcSimi(data, user_bias):

    maxs = data.max(0)
    nu = int( maxs[0]+1)
    ni = int( maxs[1]+1)

    sim = np.zeros((nu,nu))
    den1 = np.zeros((nu,nu))
    den2 = np.zeros((nu,nu))

    for i in xrange(1,ni):
        if i%100 == 0:
            print i
        subdata = data[data[:,1]==i,:] # selection du produit i
        n = subdata.shape[0]
        for i1 in xrange(n):
            for i2 in xrange(i1,n):
                u1= subdata[i1,0]
                u2= subdata[i2,0]
                r1= subdata[i1,2]
                r2= subdata[i2,2]
                v1 = (r1-user_bias[u1])
                v2 = (r2-user_bias[u2])
                sim[u1,u2] += v1*v2
                sim[u2,u1] += v1*v2
                den1[u1,u2] += v1**2
                den1[u2,u1] += v1**2
                den2[u1,u2] += v2**2
                den2[u2,u1] += v2**2
    return sim/np.maximum(np.sqrt(den1)*np.sqrt(den2),1), den1, den2

Proposition d'implémentation pour la factorisation matricielle (par descente de gradient)


# factorisation matricielle: on travaille de nouveau sur les triplets pour minimiser les hypothèses
# sur les cases vides

# paramétrage
random = np.random.RandomState(0)
epochs = 5 # nb de passage sur la base
nZ = 10 # taille de l'espace latent
l1_weight = 0.00 # contraintes de régularization L1 + L2
l2_weight = 0.0001
learning_rate = 0.001

train_indexes = np.arange(len(data)) # pour cet exemple, je prends tous les indices en apprentissage...

# initialisation à moitié vide... randn + seuillage > 0
user_latent = np.random.randn(nu, nZ)
item_latent = np.random.randn(ni, nZ)
user_latent = np.where(user_latent > 0, user_latent, 0) # profils positifs sparses
item_latent = np.where(item_latent > 0, item_latent, 0)

for epoch in xrange(epochs):
    print "epoch : %d"%epoch
    # Update
    random.shuffle(train_indexes)
    for index in train_indexes:
        # extraction des variables => lisibilité
        label, user, item = data[index,2], data[index,0], data[index,1]
        gamma_u, gamma_i = user_latent[user, :], item_latent[item, :]
        # Optimisation
        delta_label = 2 * (label - np.dot(gamma_u, gamma_i))
        gradient_u = l2_weight * gamma_u + l1_weight - delta_label * gamma_i
        gamma_u_prime = gamma_u - learning_rate * gradient_u
        user_latent[user, :] = np.where(gamma_u_prime * gamma_u > 0, gamma_u_prime, 0) # MAJ user
        gradient_i = l2_weight * gamma_i + l1_weight - delta_label * gamma_u
        gamma_i_prime = gamma_i - learning_rate * gradient_i
        item_latent[item, :] = np.where(gamma_i_prime * gamma_i > 0, gamma_i_prime, 0) # MAJ item

Proposition de visualisation basique pour les 100 premiers utilisateurs

# visualisation des users
plt.figure()
plt.imshow(user_latent[:100,:], interpolation="nearest") # 100 premiers utilisateurs
plt.colorbar()
plt.savefig("userLatent.pdf")

Perspective: faire des groupes à l'aide d'algorithmes de type k-means puis visualiser les profils types des clusters et leur correspondance en terme de filmographie.

Proposition de visualisation basique pour les items

# visualisation des users
import scipy.linalg as lin

code,sig,dico = lin.svd(item_latent)
item2d = code[:,:2] # deux premieres colonnes = 2 premières valeurs singulières (les plus fortes)

plt.figure()
plt.scatter(item2d[:,0], item2d[:,1])
plt.savefig("itemLatent.pdf")

Perspective: faire des groupes à l'aide d'algorithmes de type k-means puis visualiser les groupes de films et vérifier le sens des regroupements

Bibliothèque de recommandation

La bibliothèque à la mode en ce moment est GraphLab lien tutoriel