Recommender System: Million Song Dataset

Introducción a la Minería de Datos: CC5602-1

Integrantes: María Ignacia Caamaño, Juan Andrés Moreno, Javier Espinoza

---

Introducción

Los sistemas de recomendación apuntan a ayudar a un usuario o un grupo de usuarios dentro de un sistema a seleccionar ítems cuando existen muchos de estos. (MacNee et. al 2006) Éstos se clasifican de la siguiente manera:

1. Considerando los datos Usados
   1. Basado en reglas
   2. Basado en contenidos
   3. Filtrado Colaborativo
2. Considerando el modelo
   1. Memory-based(KNN)
   2. Model-based(Representacion Latente)

Para este proyecto se experimentó con dos tipos de sistemas recomendadores, el primero, el cual llamaremos primer acercamiento es Filtrado Colaborativo y el segundo, el cual llamaremos segundo acercamiento es Model-based: SVD.

---

Acerca del Dataset y Descripción del Problema

En abril del 2012 el sitio Kaggle lanzo una compentencia llamada "Million Song Dataset Challenge" el cual consistió en: dado el historial completo de canciones de 1 millón de usuarios y la mitad del historial de 110 mil otros usuarios, lograr predecir correctamente la segunda mitad de canciones escuchadas para esos 110 mil usuarios.

Obtener los datasets necesarios:

Para este proyecto se utilizaron los siguiente datasets (Click para descargarlos):

1. Train_triplets.txt (~500Mb)
2. MisMatches.txt (adjunto)
3. Test_triplets.txt (Usamos el archivo mas pequeño)
4. Validate_triplets.txt

Descripción de cada uno:

Train_triplets.txt corresponde a alrededor de 43 millones de filas, donde cada fila es una tripleta UserID - SongID - PlayCount. Como veremos luego, este dataset se puede representar como una matriz esparsa de densidad ~0.00011.

MisMatches.txt es un archivo que contiene dos columnas por cada fila, donde cada fila corresponde a un SongID que no se tiene certeza si esta bien asociado a su nombre y artista. Esto ocurrió cuando se construyo el dataset y por comodidad este archivo se utilizó para borrar todos los SongID's presentes en este de el dataset Train_triplets.

Test_triplets.txt Tiene la misma estructura que Train_triplets.txt pero sólo contiene tripletas para 10 mil usuarios distintos. Estas tripletas son la primera mitad del historial musical de los usuarios para los cuales se quiere generar una recomendación. I.e, luego de entrenar el modelo se prueba este con los userID's en este dataset.

Validate_triplets.txt corresponde a la segunda mitad del historial de los 10 mil usuarios previamente mencionados. Se utiliza para evaluar las recomendaciones generadas.

---

Limpieza de Datos:

Los datasets proporcionados no necesitaron de una limpieza muy extensa. Lo unico que debió hacerse sobre estos datos fue eliminar del dataset Train_triplets.txt todos los SongID que estuvieran presentes en MisMatches.txt. Si bien al final se utilizaron los SongID's solamente como identificadores del dataset principal esta limpieza sirvio para tener un dataset un poco más liviano. En Python, todo este proceso se puede hacer con las siguientes instrucciones:

import pandas as pd
#Cargamos los datasets
train_triplets = 
pd.read_csv("train_triplets.txt", sep="\t", names=["UserID", "SongID", "PlayCount"])

misMatches = 
pd.read_csv('mismatches.txt', sep=" ", header= None, names= ['SongID', 'TrackID'])

test_triplets = 
pd.read_csv("year1_valid_triplets_visible.txt", sep="\t", names=["UserID", "SongID", "PlayCount"])

validate_triplets = 
pd.read_csv("year1_valid_triplets_hidden.txt", sep="\t", names=["UserID", "SongID", "PlayCount"])

#Limpiamos
train_triplets = train_triplets[~train_triplets.SongID.isin(misMatches.SongID)]
test_triplets = test_triplets[~test_triplets.SongID.isin(misMatches.SongID)]
validate_triplets = validate_triplets[~validate_triplets.SongID.isin(misMatches.SongID)]

Exploración de Datos:

La exploración de datos fue hecha más que nada para ver qué medidas podían tomarse en el caso de que el tamaño del dataset se tornara inmanejable. Lo que se quiso averiguar en la exploración fue lo siguiente:

1. ¿Cuántas reproducciones (!= de PlayCount) tiene cada canción? ¿Existen canciones con 1, 2, 5 reproducciones en total?
2. ¿Cuántas canciones distintas escuchan los usuarios en el dataset? ¿Son las suficientes individualmente para generar una buena recomendacion?
3. Construyendo la matriz de preferencias, ¿cuál es la densidad de la matriz? ie, ¿cuántas entradas distintas de 0 tiene?

Sistemas recomendadores

Matriz de preferencias

Para ambos sistemas de recomendaciones propuestos se utilizo una matriz de preferencias. Esta corresponde a una matriz donde cada fila es un usuario y cada columna una canción. De esta manera cada fila indica qué canciones escuchó (y cuántas veces) cada usuario. Para esta primera parte se utilizó la matriz exactamente como se describió previamente, mientras que para la segunda parte se utilizó la traspuesta.

Cabe destacar que con la cantidad de información que se manejó para el proyecto era imposible representar como un arreglo esta matriz en memoria, o como un DataFrame de Pandas. Si bien era posible cargarlos, cualquier operación levemente elaborada sobre ellos era inaguantable. En este punto Mauricio Quezada nos orientó hacia las representaciones de scipy de matrices sparsas, las cuales resultan ser bastante más manejables que las mencionadas anteriormente.

El siguiente extracto del código se encarga de generar estas representaciones:

from scipy import sparse

#Se genera un indice para UserID y SongID distinto.
triplets['UserID'] = triplets['UserID'].astype("category")
triplets['SongID'] = triplets['SongID'].astype("category")

#Representación en matriz esparsa. Donde el segundo argumento indica las filas y el tercero
#las columnas.
plays = sparse.coo_matrix((triplets['PlayCount'].astype(float), 
                           (triplets['UserID'].cat.codes, 
                            triplets['SongID'].cat.codes)))

---

Primer acercamiento: Filtrado colaborativo

En este caso el algoritmo es bastante simple y es el siguiente:

Filtrado-Colaborativo(userID := u):
1. Vecinos := Set de K vecinos mas similares a u
2. CancionesVecinos(V) := Set de canciones que los vecinos de u escuchan y u no.
3. Para cada cancion en CancionesVecinos(V):
    score(cancion) := Promedio Ponderado de PlayCount de cancion con similitud de u y v.
4. Retorna M canciones con mejor score

Si bien el algoritmo es simple la implementación propuesta para esta tarea no fue la mejor. Esto pues el paso 3 del algoritmo resultó ser muy costoso de calcular. Para solucionar esto se decidió simplemente recomendar el set de canciones que escuchan los K vecinos más similares. Por otro lado, gran parte del éxito o fracaso de estos métodos radica en la definición o medida de similitud que se defina. En este caso se nos ocurrió pensar en el conjunto de canciones como un set de palabras y el conjunto de usuarios como un set de documentos. De esta manera pudimos aplicar TF-IDF sobre cada usuario. Esto nos permitió capturar dos nociones importantes para nuestro recomendador:

1. Se resta importancia a PlayCounts excesivos de usuarios a canciones, pues TF-IDF toma el log de los PlayCounts
2. Se logra recoger la noción de que dos usuarios son más similares si escuchan selectivamente las mismas cosas. Con otros modelos, un usuario que escucha de todo puede ser muy similar a muchos usuarios distintos

from sklearn.feature_extraction.text import TfidfTransformer

#Aplicamos TF-IDF sobre la matriz esparsa.
tfidf =  TfidfTransformer()
wplays = tfidf.fit_transform(plays)

Despues de esto para computar la similitud entre dos usuarios simplemente se encontraba el angulo entre ambos vectores. Luego, nuestra similitud se tornaba en una distancia. A menor distancia mayor similitud.

Las siguientes funciones son las necesarias para hacer estos calculos:

@Verbibliografia 
def unit_vector(vector):
    return vector / np.linalg.norm(vector)

@Verbibliografia
def angle_between(v1, v2):
    v1_u = unit_vector(v1)
    v2_u = unit_vector(v2)
    return np.arccos(np.clip(np.dot(v1_u, v2_u), -1.0, 1.0))

def row_no(userID):
    return triplets['UserID'].cat.categories.get_loc(userID)

def similarityMatrix(userID, weightedMatrix):
    rowNo = row_no(userID)
    userRow = weightedMatrix.getrow(rowNo).toarray().flatten()
    neighbours = set()
    for songID in triplets.loc[triplets['UserID'] == userID].SongID.tolist():
        neighbours = neighbours.union(set(triplets.loc[triplets['SongID'] == songID].UserID.tolist()))

    neighbours = islice(neighbours,2000)
    similarity = np.array([[otherUserID, angle_between(userRow, weightedMatrix.getrow(row_no(otherUserID)).toarray().flatten())]
                      for otherUserID in neighbours])
    return similarity

Cabe notar que en la ultima función, encargada de construir la matriz de similitud, el primer 'for' se encarga de seleccionar todos los UserID's que han escuchado al menos una cancion dentro de las escuchadas por el sujeto a generar al recomendación. De no limitarse esto genera una lista muy extensa de vecinos tentativos, por lo que para efectos de computabilidad se corta esta lista en los primeros 2000 vecinos tentativos encontrados.

Ahora bien, resta decidir el tamaño del vecindario que se utilizará para generar los K vecinos más cercanos. Esto se hizo por prueba y error y se reportaron los siguientes resultados:

K	100	200	300	400
Mean Average Precision	0.53	0.66	0.67	0.73

Se puede ver que como es de esperar, a medida que incrementamos el tamaño del vecindario la precisión del recomendador incrementa. Este sistema derrota un poco su propósito. Esto pues la idea de un sistema recomendador es reducir la cantidad de opciones que tiene un usuario, presentadole un subconjunto reducido el cual tiene altas posibilidades de contener ítems de su interés. En este caso, estamos reduciendo un item set de alrededor de 380 mil canciones a un set recomendado de alrededor de 1500 canciones. Nos gustaría quizás, que este numero sea menor.

Por último, cabe destacar que esta prueba se realizó tomando el Mean Average Precision para 10 usuarios distintos. Esta tabla tomo alrededor de 2 horas en ser computada.

Segundo acercamiento: SVD (Basado en este articulo)

Una de las complicaciones del primer acercamiento era la eficiencia de su implementación. Esta provocaba que partes del algoritmo se hicieran incalculables en un tiempo razonable para este curso. Es por esto que se decidió buscar otra solución mas escalable y que pudiera generar resultados en un tiempo razonable. En este articulo el autor propone, entre otras cosas, aplicar técnicas de álgebra lineal para reducir la dimensionalidad de los datos y luego trabajar sobre este nuevo espacio.

La idea es básicamente, generar una aproximación de dimensión inferior de la matriz de preferencias y luego en este espacio, computar similitudes. De esta manera, si en el primer acercamiento para calcular la similitud operabamos dos vectores de largo ~380000, ahora operaremos vectores de largo K, donde K es el parametro entregado al SVD.

Usar SVD de esta manera lleva el nombre de "Latent semantic analysis". Esto pues al hacer la reducción de dimensionalidad se revelan los llamados "factores de latencia" de los datos de entrada, los cuales pueden revelar semántico sobre estos. Por ejemplo, si antes teníamos que cada vector de SongID tenía un largo igual a la cantidad de usuarios en los datos, luego de hacer SVD, cada componente del nuevo vector representante de esta cancion puede significar algo, como por ejemplo "Grado de rock" de la canción.

La siguiente línea de código es la encargada de efectuar esta reducción de dimensionalidad, y para este acercamiento, es el punto que más tiempo toma en completarse:

artist_factors, _, user_factors = scipy.sparse.linalg.svds(wplays.transpose(), K)

Lo bueno, es que si bien esto toma un tiempo considerable, para generar las recomendaciones para cualquier usuario, sólo se necesita ejecutar esta instrucción una vez. Cabe notar que para este acercamiento se tomó una estrategia distinta. En el primer acercamiento, dado un usuario se buscaba usuarios similares a él y se recomendaba segun lo que sus vecinos más similares escuchaban. En este segundo acercamiento se propone una solucion distinta:

SVD(userID := u):
1. Canciones := Set de canciones que escucho u.
2. Recomendadas(u) := Set de canciones a recomendar a u.
3. Para cada cancion en Canciones:
    Recomendadas += masSimilares(cancion)
4. Retorna Recomendadas

El hecho de contar con los factores de cada canción nos permite buscar canciones similares a las escuchadas por el usuario y recomendar ese conjunto. El artículo mencionado anteriormente provee con una clase para obtener las N canciones mas similares. Se tienen entonces dos parámetros para variar en este caso: el parámetro K de SVD y el N. Los mejores valores para estos se buscaron por prueba y error y se obtuvieron los siguientes resultados:

K/N	5	10	20	40
10	0.08	0.10	0.14	0.20
50	0.15	0.24	0.26	0.30
70	0.16	0.20	0.22	0.29

Se tiene entonces que el mejor resultado se obtuvo con K=50 y N=40, aún asi se puede ver que los resultados mejoran progresivamente a medida que aumenta el valor de N, lo que como se apuntó en el primer acercamiento, tiene sentido.

Cabe notar que por un tema de tiempo disponible, esta tabla fue generada obteniendo el Mean Average Precision para 10 usuarios distintos dentro del testset. Esta prueba tomo alrededor de 30 minutos en generarse.

Evaluación

Para evaluar los recomendadores se utilizó el Mean Average Precision, es decir, se midió en promedio qué cantidad de canciones fueron las realmente escuchadas por sobre las recomendadas. La siguiente función entrega este resultado para los distintos recomendadores:

def evaluateRecommendation(recList, userID):
    songs = recList
    userSongs = set(validate_triplets.loc[validate_triplets['UserID'] == userID].SongID.tolist())
    return len(songs.intersection(userSongs))/len(userSongs)

Conclusiones

El construir un recomendador tiene muchas aristas complicadas, entre las que se pudieron encontrar en este proyecto fueron:

1. Se deben hacer cálculos "pesados" reiteradamente sobre grandes cantidades de datos.
2. La forma en que se elige representar los datos dentro de las implementaciones es crucial al momento de buscar eficiencia en éstas.
3. La eficiencia en los sistemas recomendadores es vital, en los casos prácticos ningún cliente va a esperar mucho tiempo para ver las recomendaciones que le son sugeridas. Esto pues la recomendaciones son las que deben apelar al cliente y no en sentido contrario.
4. La medida de similitud toma una gran importancia en estos sistemas. Pues al momento de recomendar debe existir una noción de similitud entre dos usuarios o ítems. Es importante que la noción de similitud definida en el problema trate de captar las nociones respectivas del dominio en que se desarrolla el sistema recomendador.

Trabajo propuesto

1. Implementar de manera más eficiente el primer acercamiento.
2. Lograr encontrar valores N y K optimos para el segundo acercamiento. Debido al tiempo que toma hacer pruebas, esto no se pudo lograr este semestre.
3. Tratar un tercer acercamiento usando tecnicas de factorización de matrices (alternating least squares es una posibilidad).
4. Proponer nuevamente el proyecto pero sampleando los datos, para tener un set mas manejable. En el cual sí se puedan efectuar más pruebas en un tiempo razonable.

Bibliografia

1. Frederickson, B. (2016, 3 de Mayo). Matrix Factorization. Consultada el 10/12/2016, desde http://www.benfrederickson.com/matrix-factorization/

2. Frederickson, B. (2015, 27 de Abril). Distance Metrics for Fun and Profit. Consultada el 10/12/2016, desde http://www.benfrederickson.com/distance-metrics/