Predicción de Me gusta: dentro de los algoritmos de un motor de recomendación simple

Un motor de recomendación (a veces denominado sistema de recomendación) es una herramienta que permite a los desarrolladores de algoritmos predecir lo que le puede gustar o no a un usuario entre una lista de elementos determinados. Los motores de recomendación son una alternativa bastante interesante a los campos de búsqueda, ya que los motores de recomendación ayudan a los usuarios a descubrir productos o contenido que de otro modo no encontrarían. Esto hace que los motores de recomendación sean una gran parte de los sitios web y servicios como Facebook, YouTube, Amazon y más.

Los motores de recomendación funcionan idealmente en una de dos formas. Puede basarse en las propiedades de los elementos que le gustan a un usuario, que se analizan para determinar qué más le puede gustar al usuario; o bien, puede basarse en los gustos y disgustos de otros usuarios, que el motor de recomendaciones utiliza para calcular un índice de similitud entre los usuarios y recomendarles elementos en consecuencia. También es posible combinar ambos métodos para construir un motor de recomendaciones mucho más robusto. Sin embargo, como todos los demás problemas relacionados con la información, es esencial elegir un algoritmo que sea adecuado para el problema que se está abordando.

En este tutorial, lo guiaremos a través del proceso de creación de un motor de recomendaciones colaborativo y basado en la memoria. Este motor de recomendación recomendará películas a los usuarios en función de lo que les guste y no les guste, y funcionará como el segundo ejemplo mencionado anteriormente. Para este proyecto, utilizaremos operaciones básicas de conjuntos, un poco de matemáticas y Node.js/CoffeeScript. Todo el código fuente relevante para este tutorial se puede encontrar aquí.

Conjuntos y Ecuaciones

Antes de implementar un motor de recomendación basado en la memoria colaborativa, primero debemos comprender la idea central detrás de dicho sistema. Para este motor, cada elemento y cada usuario no son más que identificadores. Por lo tanto, no tendremos en cuenta ningún otro atributo de una película (por ejemplo, el reparto, el director, el género, etc.) al generar recomendaciones. La similitud entre dos usuarios se representa mediante un número decimal entre -1,0 y 1,0. A este número lo llamaremos índice de similitud. Finalmente, la posibilidad de que a un usuario le guste una película se representará mediante otro número decimal entre -1,0 y 1,0. Ahora que hemos modelado el mundo alrededor de este sistema usando términos simples, podemos desatar un puñado de elegantes ecuaciones matemáticas para definir la relación entre estos identificadores y números.

En nuestro algoritmo de recomendación, mantendremos una serie de conjuntos. Cada usuario tendrá dos conjuntos: un conjunto de películas que le gustan al usuario y un conjunto de películas que no le gustan al usuario. Cada película también tendrá dos conjuntos asociados: un conjunto de usuarios a los que les gustó la película y un conjunto de usuarios a los que no les gustó la película. Durante las etapas en las que se generan las recomendaciones, se producirán una serie de conjuntos, en su mayoría uniones o intersecciones de los otros conjuntos. También tendremos listas ordenadas de sugerencias y usuarios similares para cada usuario.

Para calcular el índice de similitud, utilizaremos una variación de la fórmula del índice de Jaccard. Originalmente conocida como "coeficiente de comunidad" (acuñada por Paul Jaccard), la fórmula compara dos conjuntos y produce una estadística decimal simple entre 0 y 1,0:

La fórmula implica la división del número de elementos comunes en cualquiera de los conjuntos por el número de todos los elementos (contados solo una vez) en ambos conjuntos. El índice de Jaccard de dos conjuntos idénticos siempre será 1, mientras que el índice de Jaccard de dos conjuntos sin elementos comunes siempre dará 0. Ahora que sabemos cómo comparar dos conjuntos, pensemos en una estrategia que podamos usar para comparar dos usuarios Como se discutió anteriormente, los usuarios, desde el punto de vista del sistema, son tres cosas: un identificador, un conjunto de películas que les gustan y un conjunto de películas que no les gustan. Si tuviéramos que definir el índice de similitud de nuestros usuarios basándonos únicamente en el conjunto de películas que les gustan, podríamos usar directamente la fórmula del índice de Jaccard:

Aquí, U1 y U2 son los dos usuarios que estamos comparando, y L1 y L2 son los conjuntos de películas que les han gustado a U1 y U2, respectivamente. Ahora, si lo piensa, dos usuarios a los que les gustan las mismas películas son similares, entonces dos usuarios a los que no les gustan las mismas películas también deberían ser similares. Aquí es donde modificamos un poco la ecuación:

En lugar de solo considerar los gustos comunes en el numerador de la fórmula, ahora también agregamos la cantidad de disgustos comunes. En el denominador, tomamos el número de todos los elementos que le han gustado o disgustado al usuario. Ahora que hemos considerado tanto los gustos como los disgustos de forma independiente, también deberíamos pensar en el caso en el que dos usuarios son polos opuestos en sus preferencias. El índice de similitud de dos usuarios donde a uno le gusta una película y al otro no le gusta no debería ser 0:

¡Esa es una fórmula larga! Pero es simple, lo prometo. Es similar a nuestra fórmula anterior con una pequeña diferencia en el numerador. Ahora estamos restando el número de gustos y disgustos en conflicto de los dos usuarios del número de sus gustos y disgustos comunes. Esto hace que la fórmula del índice de similitud tenga un rango de valores entre -1,0 y 1,0. Dos usuarios con gustos idénticos tendrán un índice de similitud de 1,0, mientras que dos usuarios con gustos totalmente opuestos en cuanto a películas tendrán un índice de similitud de -1,0.

Ahora que sabemos cómo comparar a dos usuarios en función de su gusto por las películas, tenemos que explorar una fórmula más antes de que podamos comenzar a implementar nuestro algoritmo de motor de recomendación casero:

Desglosemos un poco esta ecuación. Lo que queremos decir con P(U,M) es la posibilidad de que a un usuario U le guste la película M ZL y ZD son la suma de los índices de similitud del usuario U con todos los usuarios a los que les ha gustado o disgustado la película M , respectivamente. |ML|+|MD| representa el número total de usuarios a los que les ha gustado o no la película M . El resultado P(U,M) produce un número entre -1,0 y 1,0.

Eso es todo. En la siguiente sección, podemos usar estas fórmulas para comenzar a implementar nuestro motor de recomendación basado en la memoria colaborativa.

Construyendo el motor de recomendación

Construiremos este motor de recomendación como una aplicación Node.js muy simple. También habrá muy poco trabajo en el front-end, principalmente algunas páginas y formularios HTML (usaremos Bootstrap para que las páginas se vean ordenadas). Del lado del servidor, usaremos CoffeeScript. La aplicación tendrá algunas rutas GET y POST. Aunque tendremos la noción de usuarios en la aplicación, no tendremos ningún mecanismo elaborado de registro/inicio de sesión. Para la persistencia, usaremos el paquete Bourne disponible a través de NPM que permite que una aplicación almacene datos en archivos JSON sin formato y realice consultas básicas de bases de datos en ellos. Usaremos Express.js para facilitar el proceso de administración de rutas y controladores.

En este punto, si es nuevo en el desarrollo de Node.js, es posible que desee clonar el repositorio de GitHub para que sea más fácil seguir este tutorial. Al igual que con cualquier otro proyecto de Node.js, comenzaremos creando un archivo package.json e instalando un conjunto de paquetes de dependencia necesarios para este proyecto. Si está utilizando el repositorio clonado, el archivo package.json ya debería estar allí, desde donde instalar las dependencias requerirá que ejecute "$ npm install". Esto instalará todos los paquetes enumerados dentro del archivo package.json.

Los paquetes de Node.js que necesitamos para este proyecto son:

• asíncrono
• bourne
• guión de café
• Rápido
• jade
• guion bajo

Construiremos el motor de recomendaciones dividiendo todos los métodos relevantes en cuatro clases CoffeeScript separadas, cada una de las cuales se almacenará en "lib/engine": Motor, Evaluador, Similares y Sugerencias. La clase Engine será responsable de proporcionar una API simple para el motor de recomendación y unirá las otras tres clases. El calificador será responsable de rastrear los gustos y disgustos (como dos instancias separadas de la clase Calificador). Similares y Sugerencias serán responsables de determinar y rastrear usuarios similares y elementos recomendados para los usuarios, respectivamente.

Seguimiento de gustos y disgustos

Comencemos primero con nuestra clase de evaluadores. Esto es muy simple:

 class Rater constructor: (@engine, @kind) -> add: (user, item, done) -> remove: (user, item, done) -> itemsByUser: (user, done) -> usersByItem: (item, done) ->

Como se indicó anteriormente en este tutorial, tendremos una instancia de Rater para Me gusta y otra para No me gusta. Para registrar que a un usuario le gusta un artículo, lo pasaremos a "Evaluador # agregar ()". De igual forma, para eliminar la calificación, las pasaremos a “Evaluador#remove()”.

Dado que usamos Bourne como una solución de base de datos sin servidor, almacenaremos estas calificaciones en un archivo llamado "./db-#{@kind}.json", donde tipo es "me gusta" o "no me gusta". Abriremos la base de datos dentro del constructor de la instancia de Rater:

 constructor: (@engine, @kind) -> @db = new Bourne "./db-#{@kind}.json"

Esto hará que agregar registros de calificación sea tan simple como llamar a un método de base de datos Bourne dentro de nuestro método “Evaluador#agregar()”:

 @db.insert user: user, item: item, (err) =>

Y es similar eliminarlos ("db.delete" en lugar de "db.insert"). Sin embargo, antes de que agreguemos o eliminemos algo, debemos asegurarnos de que no exista en la base de datos. Idealmente, con una base de datos real, podríamos haberlo hecho como una sola operación. Con Bourne, primero tenemos que hacer una verificación manual; y, una vez realizada la inserción o eliminación, debemos asegurarnos de recalcular los índices de similitud para este usuario, y luego generar un conjunto de nuevas sugerencias. Los métodos “Evaluador#agregar()” y “Evaluador#remove()” se verán así:

 add: (user, item, done) -> @db.find user: user, item: item, (err, res) => if res.length > 0 return done() @db.insert user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done remove: (user, item, done) -> @db.delete user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done

Por brevedad, omitiremos las partes en las que verificamos si hay errores. Esto podría ser algo razonable para hacer en un artículo, pero no es una excusa para ignorar los errores en el código real.

Los otros dos métodos, "Evaluador#itemsByUser()" y "Evaluador#usersByItem()" de esta clase implicarán hacer lo que sus nombres implican: buscar elementos calificados por un usuario y usuarios que hayan calificado un elemento, respectivamente. Por ejemplo, cuando se crea una instancia de Rater con kind = “likes” , “Rater#itemsByUser()” encontrará todos los elementos que el usuario calificó.

Encontrar usuarios similares

Pasando a nuestra siguiente clase: Similares. Esta clase nos ayudará a calcular y realizar un seguimiento de los índices de similitud entre los usuarios. Como se discutió anteriormente, calcular la similitud entre dos usuarios implica analizar los conjuntos de elementos que les gustan y no les gustan. Para hacer eso, confiaremos en las instancias de Rater para obtener los conjuntos de elementos relevantes y luego determinaremos el índice de similitud para ciertos pares de usuarios utilizando la fórmula del índice de similitud.

Al igual que nuestra clase anterior, Rater, pondremos todo en una base de datos Bourne llamada “./db-similars.json”, que abriremos en el constructor de Rater. La clase tendrá un método “Similars#byUser()”, que nos permitirá buscar usuarios similares a un usuario dado a través de una simple búsqueda en la base de datos:

 @db.findOne user: user, (err, {others}) =>

Sin embargo, el método más importante de esta clase es “Similars#update()”, que funciona tomando un usuario y computando una lista de otros usuarios que son similares y almacenando la lista en la base de datos, junto con sus índices de similitud. Comienza por encontrar los gustos y disgustos del usuario:

 async.auto userLikes: (done) => @engine.likes.itemsByUser user, done userDislikes: (done) => @engine.dislikes.itemsByUser user, done , (err, {userLikes, userDislikes}) => items = _.flatten([userLikes, userDislikes])

También encontramos a todos los usuarios que han valorado estos artículos:

 async.map items, (item, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.usersByItem item, done , done , (err, others) =>

Luego, para cada uno de estos otros usuarios, calculamos el índice de similitud y lo almacenamos todo en la base de datos:

 async.map others, (other, done) => async.auto otherLikes: (done) => @engine.likes.itemsByUser other, done otherDislikes: (done) => @engine.dislikes.itemsByUser other, done , (err, {otherLikes, otherDislikes}) => done null, user: other similarity: (_.intersection(userLikes, otherLikes).length+_.intersection(userDislikes, otherDislikes).length-_.intersection(userLikes, otherDislikes).length-_.intersection(userDislikes, otherLikes).length) / _.union(userLikes, otherLikes, userDislikes, otherDislikes).length , (err, others) => @db.insert user: user others: others , done

En el fragmento anterior, notará que tenemos una expresión de naturaleza idéntica a nuestra fórmula de índice de similitud, una variante de la fórmula de índice de Jaccard.

Generación de recomendaciones

Nuestra siguiente clase, Sugerencias, es donde tienen lugar todas las predicciones. Al igual que la clase Similars, confiamos en otra base de datos de Bourne llamada “./db-suggestions.json”, abierta dentro del constructor.

La clase tendrá un método "Suggestions#forUser()" para buscar sugerencias calculadas para el usuario dado:

 forUser: (user, done) -> @db.findOne user: user, (err, {suggestions}={suggestion: []}) -> done null, suggestions

El método que calculará estos resultados es “Sugerencias#actualizar()”. Este método, como “Similars#update()”, tomará un usuario como argumento. El método comienza enumerando todos los usuarios similares al usuario dado y todos los elementos que el usuario dado no ha calificado:

 @engine.similars.byUser user, (err, others) => async.auto likes: (done) => @engine.likes.itemsByUser user, done dislikes: (done) => @engine.dislikes.itemsByUser user, done items: (done) => async.map others, (other, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.itemsByUser other.user, done , done , done , (err, {likes, dislikes, items}) => items = _.difference _.unique(_.flatten items), likes, dislikes

Una vez que tenemos todos los demás usuarios y los elementos no calificados enumerados, podemos comenzar a calcular un nuevo conjunto de recomendaciones eliminando cualquier conjunto anterior de recomendaciones, iterando sobre cada elemento y calculando la posibilidad de que al usuario le guste según la información disponible:

 @db.delete user: user, (err) => async.map items, (item, done) => async.auto likers: (done) => @engine.likes.usersByItem item, done dislikers: (done) => @engine.dislikes.usersByItem item, done , (err, {likers, dislikers}) => numerator = 0 for other in _.without _.flatten([likers, dislikers]), user other = _.findWhere(others, user: other) if other? numerator += other.similarity done null, item: item weight: numerator / _.union(likers, dislikers).length , (err, suggestions) =>

Una vez hecho esto, lo guardamos de nuevo en la base de datos:

 @db.insert user: user suggestions: suggestions , done

Exponiendo la API de la biblioteca

Dentro de la clase Engine, vinculamos todo en una ordenada estructura similar a una API para facilitar el acceso desde el mundo exterior:

 class Engine constructor: -> @likes = new Rater @, 'likes' @dislikes = new Rater @, 'dislikes' @similars = new Similars @ @suggestions = new Suggestions @

Una vez que creamos una instancia de un objeto Engine:

 e = new Engine

Podemos agregar o eliminar fácilmente Me gusta y No me gusta:

 e.likes.add user, item, (err) -> e.dislikes.add user, item, (err) ->

También podemos comenzar a actualizar los índices de similitud de los usuarios y las sugerencias:

 e.similars.update user, (err) -> e.suggestions.update user, (err) ->

Finalmente, es importante exportar esta clase de motor (y todas las demás clases) desde sus respectivos archivos ".coffee":

 module.exports = Engine

Luego, exporte el motor del paquete creando un archivo "index.coffee" con una sola línea:

 module.exports = require './engine'

Creación de la interfaz de usuario

Para poder usar el algoritmo del motor de recomendación en este tutorial, queremos proporcionar una interfaz de usuario simple en la web. Para hacer eso, generamos una aplicación Express dentro de nuestro archivo "web.iced" y manejamos algunas rutas:

 movies = require './data/movies.json' Engine = require './lib/engine' e = new Eengine app = express() app.set 'views', "#{__dirname}/views" app.set 'view engine', 'jade' app.route('/refresh') .post(({query}, res, next) -> async.series [ (done) => e.similars.update query.user, done (done) => e.suggestions.update query.user, done ], (err) => res.redirect "/?user=#{query.user}" ) app.route('/like') .post(({query}, res, next) -> if query.unset is 'yes' e.likes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.dislikes.remove query.user, query.movie, (err) => e.likes.add query.user, query.movie, (err) => if err? return next err res.redirect "/?user=#{query.user}" ) app.route('/dislike') .post(({query}, res, next) -> if query.unset is 'yes' e.dislikes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.likes.remove query.user, query.movie, (err) => e.dislikes.add query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" ) app.route('/') .get(({query}, res, next) -> async.auto likes: (done) => e.likes.itemsByUser query.user, done dislikes: (done) => e.dislikes.itemsByUser query.user, done suggestions: (done) => e.suggestions.forUser query.user, (err, suggestions) => done null, _.map _.sortBy(suggestions, (suggestion) -> -suggestion.weight), (suggestion) => _.findWhere movies, id: suggestion.item , (err, {likes, dislikes, suggestions}) => res.render 'index', movies: movies user: query.user likes: likes dislikes: dislikes suggestions: suggestions[...4] )

Dentro de la aplicación, manejamos cuatro rutas. La ruta de índice "/" es donde servimos el HTML de front-end al representar una plantilla de Jade. La generación de la plantilla requiere una lista de películas, el nombre de usuario del usuario actual, los gustos y aversiones del usuario y las cuatro sugerencias principales para el usuario. El código fuente de la plantilla de Jade no se incluye en el artículo, pero está disponible en el repositorio de GitHub.

Las rutas "/me gusta" y "/no me gusta" son donde aceptamos solicitudes POST para registrar los gustos y disgustos del usuario. Ambas rutas agregan una calificación eliminando primero cualquier calificación en conflicto, si es necesario. Por ejemplo, si a un usuario le gusta algo que antes no le gustaba, el controlador eliminará primero la calificación de "no me gusta". Estas rutas también permiten al usuario "no me gusta" o "no me gusta" un elemento, si lo desea.

Finalmente, la ruta “/actualizar” permite al usuario regenerar su conjunto de recomendaciones a pedido. Si bien, esta acción se realiza automáticamente cada vez que el usuario realiza alguna calificación a un elemento.

Prueba de conducción

Si ha intentado implementar esta aplicación desde cero siguiendo este artículo, deberá realizar un último paso antes de poder probarla. Deberá crear un archivo ".json" en "data/movies.json" y completarlo con algunos datos de películas como este:

 [ { "id": "1", "name": "Transformers: Age of Extinction", "thumb": { "url": "//upload.wikimedia.org/wikipedia/en/7/7f/Inception_ver3.jpg" } }, // … ]

Es posible que desee copiar el disponible en el repositorio de GitHub, que se completa previamente con un puñado de nombres de películas y URL de miniaturas.

Una vez que todo el código fuente está listo y conectado, iniciar el proceso del servidor requiere que se invoque el siguiente comando:

 $ npm start

Suponiendo que todo salió bien, debería ver aparecer el siguiente texto en la terminal:

 Listening on 5000

Dado que no hemos implementado ningún sistema de autenticación de usuario real, la aplicación prototipo se basa solo en un nombre de usuario elegido después de visitar "http://localhost:5000". Una vez que se haya ingresado un nombre de usuario y se haya enviado el formulario, debe ser llevado a otra página con dos secciones: "Películas recomendadas" y "Todas las películas". Dado que carecemos del elemento más importante de un motor de recomendación (datos) basado en la memoria colaborativa, no podremos recomendar ninguna película a este nuevo usuario.

En este punto, debe abrir otra ventana del navegador en "http://localhost:5000" e iniciar sesión como un usuario diferente allí. Me gusta y no me gusta algunas películas como este segundo usuario. Regrese a la ventana del navegador del primer usuario y califique también algunas películas. Asegúrese de calificar al menos un par de películas comunes para ambos usuarios. Deberías empezar a ver recomendaciones inmediatamente.

Mejoras

En este tutorial de algoritmos, lo que hemos construido es un prototipo de motor de recomendación. Ciertamente hay formas de mejorar este motor. Esta sección tocará brevemente algunas áreas donde las mejoras son esenciales para que esto se use a gran escala. Sin embargo, en los casos en que se requiera escalabilidad, estabilidad y otras propiedades similares, siempre debe recurrir al uso de una buena solución probada. Al igual que el resto del artículo, la idea aquí es proporcionar una idea de cómo funciona un motor de recomendación. En lugar de discutir las fallas obvias del método actual (como la condición de carrera en algunos de los métodos que hemos implementado), las mejoras se discutirán a un nivel superior.

Una mejora muy obvia aquí es usar una base de datos real, en lugar de nuestra solución basada en archivos. La solución basada en archivos puede funcionar bien en un prototipo a pequeña escala, pero no es una opción razonable para un uso real. Una opción entre muchas es Redis. Redis es rápido y tiene capacidades especiales que son útiles cuando se trata de estructuras de datos similares a conjuntos.

Otro problema que simplemente podemos resolver es el hecho de que estamos calculando nuevas recomendaciones cada vez que un usuario hace o cambia sus calificaciones para las películas. En lugar de hacer nuevos cálculos sobre la marcha en tiempo real, deberíamos poner en cola estas solicitudes de actualización de recomendaciones para los usuarios y realizarlas en segundo plano, tal vez estableciendo un intervalo de actualización cronometrado.

Además de estas elecciones “técnicas”, también hay algunas elecciones estratégicas que se pueden hacer para mejorar las recomendaciones. A medida que crezca la cantidad de elementos y usuarios, será cada vez más costoso (en términos de tiempo y recursos del sistema) generar recomendaciones. Es posible hacer esto más rápido eligiendo solo un subconjunto de usuarios para generar recomendaciones, en lugar de procesar toda la base de datos cada vez. Por ejemplo, si se tratara de un motor de recomendación para restaurantes, podría limitar el conjunto de usuarios similares para que contenga solo aquellos usuarios que viven en la misma ciudad o estado.

Otras mejoras pueden implicar la adopción de un enfoque híbrido, donde las recomendaciones se generan en función del filtrado colaborativo y el filtrado basado en el contenido. Esto sería especialmente bueno con contenido como películas, donde las propiedades del contenido están bien definidas. Netflix, por ejemplo, toma esta ruta y recomienda películas basándose tanto en las actividades de otros usuarios como en los atributos de las películas.

Conclusión

Los algoritmos del motor de recomendación colaborativo basado en la memoria pueden ser algo bastante poderoso. El que experimentamos en este artículo puede ser primitivo, pero también es simple: simple de entender y simple de construir. Puede estar lejos de ser perfecto, pero las implementaciones sólidas de los motores de recomendación, como Recomendable, se basan en ideas fundamentales similares.

Como la mayoría de los otros problemas de informática que involucran una gran cantidad de datos, obtener recomendaciones correctas tiene mucho que ver con elegir el algoritmo correcto y los atributos apropiados del contenido para trabajar. Espero que este artículo le haya dado una idea de lo que sucede dentro de un motor de recomendación basado en la memoria colaborativa cuando lo está utilizando.