Slope One

Slope One

El filtrado colaborativo es una técnica usada por los Sistemas de Recomendación para combinar las opiniones y pruebas de diferentes usuarios con el fin de obtener recomendaciones personalizadas. Hay al menos dos clases de filtrados colaborativos: las técnicas basadas en usuarios son derivadas de la medición de similitudes entre usuarios, mientras que las técnicas basadas en artículos comparan las valoraciones dadas por distintos usuarios. Slope One es una familia de algoritmos usados para el Filtrado Colaborativo introducida en Slope One Predictors for Online Rating-Based Collaborative Filtering por Daniel Lemire y Anna Maclachlan. Posiblemente, esta es la forma más simple de filtrado colaborativo basado en artículos. Su simplicidad la hace especialmente sencilla de implementar eficientemente mientras que su exactitud está a la par de algoritmos más complejos y costosos.

Contenido

Filtrado colaborativo basado en artículos de recursos valorados y overfitting

Cuando la valoración de los artículos está disponible, como es el caso cuando las personas tienen la opción de ofrecer su valoración (entre 1 y 5, por ejemplo), el filtrado colaborativo ayuda a predecir la valoración de un individuo basado en su historial de valoraciones y en una (gran) base de datos de valoraciones conformada por otros usuarios.

Ejemplo. ¿Podemos predecir la valoración que un individuo pudiera dar al nuevo álbum de Celine Dion teniendo que le otorgó 5 de 5 a Los Beatles?

En este contexto, un Filtrado Colaborativo basado en artículos[1] [2] predice las valoraciones de un artículo basado en las valoraciones de otro, típicamente usando regresión lineal (f(x) = ax + b). Por lo tanto, si tenemos 1.000 artículos, pudiera haber hasta 1.000.000 de regresiones lineales por aprender, y entonces, hasta 2.000.000 de regresores. Este enfoque puede sufrir de overfitting[3] a menos que se seleccionen solamente los pares de elementos para los cuales varios usuarios hayan valorado ambos artículos.

Una mejor alternativa puede ser aprender un predictor simple como f(x) = x + b: los experimentos demuestran que este predictor simple (llamado Slope One) algunas veces supera[3] la regresión lineal mientras que tiene la mitad del número de regresores. Este enfoque simplificado también reduce los requerimientos de almacenamiento y la latencia.

El filtrado colaborativo basado en artículos es solo una forma más de filtrado colaborativo. Otras alternativas incluyen el filtrado colaborativo basado en usuarios donde las relaciones entre los usuarios son de intereses. En cualquiera de los casos, el filtrado colaborativo basado en artículos es especialmente escalable con respecto al número de usuarios.

Filtrado colaborativo basado en artículos de estadísticas de compra

No siempre se otorgan valoraciones: cuando los usuarios solo proveen datos sobre si se compró o no el artículo, entonces Slope One y otros algoritmos basados en valoraciones no aplican. Ejemplos de algoritmos binarios sobre filtrado colaborativo basado en artículos incluyen al Algoritmo artículo-a-artículo patentado de Amazon[4] el cuál calcula el coseno entre vectores binarios que representan las compras en una matriz usuario-artículo.

Siendo posiblemente más simple que incluso Slope One, el algoritmo de artículo-a-artículo ofrece un interesante punto de referencia. Permítanos mostrarle un ejemplo.

Estadísticas de compra
Cliente Artículo 1 Artículo 2 Artículo 3
Juan Lo compró No lo ha comprado Lo compró
Marcos No lo ha comprado Lo compró Lo compró
Lucía No lo ha comprado Lo compró No lo ha comprado


En este caso, el coseno entre el elemento 1 y el 2 es

\frac{(1,0,0)\cdot (0,1,1) }{ \Vert (1,0,0)\Vert \Vert (0,1,1)\Vert }= 0,

el coseno entre el elemento 1 y 3 es

\frac{(1,0,0)\cdot (1,1,0) }{ \Vert (1,0,0)\Vert \Vert (1,1,0)\Vert }= \frac{1}{\sqrt{2}},

mientras que el coseno entre el elemento 2 y el 3 es

\frac{(0,1,1)\cdot (1,1,0)}{ \Vert (0,1,1)\Vert \Vert (1,1,0)\Vert }= \frac{1}{2}.

Por lo tanto, un usuario que visite el artículo 1 recibiría como recomendación el item 3, un usuario que visite el item 2 recibiría como recomendación el item 3 igualmente; y finalmente, un usuario que visite el item 3 recibiría como recomendación el item 1 (y después el item 2). El modelo usa un sólo parámetro por cada par de elementos (el coseno) para hacer la recomendación. Por lo tanto, si hay n elementos, hasta n(n-1)/2 cosenos necesitan ser calculados y almacenados.

El filtrado colaborativo para recursos valorados de Slope One

Para reducir drásticamente el tiempo empleado en aprendizaje (overfitting), mejorar el rendimiento y facilitar la implementación, fue propuesta la familia de algoritmos Slope One para el Filtrado Colaborativo basado en valoraciones para articulos. Esencialmente, en vez de usar una regresión lineal de las valoraciones de un elemento para las valoraciones de otro (f(x) = ax + b), se usa una forma simple de regresión con un sólo parámetro (f(x) = x + b). El parámetro indicado es entonces una diferencia de promedio entre la valoración de dos elementos. Esto ha demostrado ser mucho más exacto que la regresión lineal en algunas instancias,[3] y toma la mitad del espacio de almacenamiento o menos.

Simplicity diagram.png Ejemplo:

  1. Juan dio 1 a María y 1.5 a Pedro
  2. Carlos dio 2 a María
  3. ¿Cómo piensas que Carlos valorará a Pedro?
  4. La respuesta de Slope One será 2.5 (1.5-1+2=2.5).


Para un ejemplo más realista, considere la siguiente tabla.

Base de datos de valoración
Cliente Artículo 1 Artículo 2 Artículo 3
Juan 5 3 2
Marcos 3 4 Didn't rate it
Lucía No ha valorado 2 5

En este caso, el promedio de las diferencias en las valoraciones entre el artículo 2 y el 1 es (2+(-1))/2=0.5. Entonces, en promedio, el artículo 1 es valorado antes que el 2 por 0.5. De la misma manera, el promedio de las diferencias entre el artículo 3 y el 1 es 3. Por lo tanto, si intentamos predecir la valoración de Lucía para el artículo 1 usando su valoración para el artículo 2, obtenemos 2+0.5=2.5. Asimismo, si tratamos de predecir su valoración para el artículo 1 usando la del artículo 3 obtenemos 5+3=8.

Si un usuario ha valorado varios items, las predicciones son combinadas usando un promedio ponderado donde una buena eleccion para esta ponderación es el número de usuario que han valorado dos items. En el ejemplo anterior, pudiéramos predecir la siguiente valoración de Lucía para el artículo 1

\frac{2 \times 2.5 + 1 \times 8 }{2+1} = \frac{13 }{3} = 4.33

Por lo tanto, teniendo n artículos, para implementar Slope One, todo lo que se necesita es calcular y almacenar el promedio de las diferencias y el número de valoraciones comunes para cada uno de los n2 pares de elementos.

Complejidad algorítmica de Slope One

Suponiendo que hay n elementos, m usuarios y N valoraciones. Calculando las diferencias de valoración promedio para cada par de elementos requiere hasta n(n-1)/2 unidades de almacenamiento, y hasta m n 2 unidades de tiempo. Esta cota calculada puede ser pesimista: si asumimos que los usuarios han valorado hasta y elementos, entonces es posible calcular las diferencias en no más que n2+my2. Si un usuario ha ingresado x valoraciones, prediciendo una valoración simple requerirá x unidades de tiempo, y prediciendo todas las valoraciones que faltan requerirá hasta (n-x)x unidades de tiempo. Actualizando la base de datos cuando un usuario ha ingresado x valoraciones, e ingresa una nueva, requerirá x unidades de tiempo.

Es posible reducir los requerimientos de almacenamiento particionando los datos (Partición (Base de datos)) o usando almacenamiento disperso: pares de elementos que no tengan (o tengan pocos) usuarios que los hayan valorado puede ser omitidos

Sistemas de recomendación que usan Slope One

Software de código abierto que implementa Slope One

Python:

Java (lenguaje de programación):

PHP:

Erlang:

Scala:

Haskell:

Visual Basic para aplicaciones:

C Sharp:

T-SQL:

Referencias

  1. Slobodan Vucetic, Zoran Obradovic: Collaborative Filtering Using a Regression-Based Approach. Knowl. Inf. Syst. 7(1): 1-22 (2005)
  2. Badrul M. Sarwar, George Karypis, Joseph A. Konstan, John Riedl: Item-based collaborative filtering recommendation algorithms. WWW 2001: 285-295
  3. a b c Daniel Lemire, Anna Maclachlan, Slope One Predictors for Online Rating-Based Collaborative Filtering, In SIAM Data Mining (SDM'05), Newport Beach, California, April 21-23, 2005.
  4. Greg Linden, Brent Smith, Jeremy York, "Amazon.com Recommendations: Item-to-Item Collaborative Filtering," IEEE Internet Computing, vol. 07, no. 1, pp. 76-80, Jan/Feb, 2003
  5. Daniel Lemire, Sean McGrath, "Implementing a Rating-Based Item-to-Item Recommender System in PHP/SQL", Technical Report D-01, January 2005.

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Slope One — Slope One  семейство алгоритмов для коллаборативной фильтрации (используемой в рекомендательных системах) для анализа различных мнений и пожеланий пользователей и выработки персональных рекомендаций. Существует как минимум 2 класса… …   Википедия

  • Slope One — Collaborative filtering is a technique used by recommender systems to combine different users opinions and tastes in order to achieve personalized recommendations. There are at least two classes of collaborative filtering: user based techniques… …   Wikipedia

  • Slope — is used to describe the steepness, incline, gradient, or grade of a straight line. A higher slope value indicates a steeper incline. The slope is defined as the ratio of the rise divided by the run between two points on a line, or in other words …   Wikipedia

  • Slope Day — is an annual day of celebration held at Cornell University during the last day of regular undergraduate classes. It usually falls on the first Friday of May and the official site of Slope Day is the Libe Slope, on the university campus. Though… …   Wikipedia

  • Slope side — is a term used in the North American ski lodging industry to describe any accommodation from which one can reasonably walk to the ski lifts. Such lodgings are usually at the bottom of, or right beside, the ski hill hence the term slope side . Due …   Wikipedia

  • Slope — Slope, n. [Formed (like abode fr. abide) from OE. slipen. See {Slip}, v. i.] 1. An oblique direction; a line or direction including from a horizontal line or direction; also, sometimes, an inclination, as of one line or surface to another. [1913… …   The Collaborative International Dictionary of English

  • Slope of a plane — Slope Slope, n. [Formed (like abode fr. abide) from OE. slipen. See {Slip}, v. i.] 1. An oblique direction; a line or direction including from a horizontal line or direction; also, sometimes, an inclination, as of one line or surface to another.… …   The Collaborative International Dictionary of English

  • slope — ► NOUN 1) a surface of which one end or side is at a higher level than another. 2) a part of the side of a hill or mountain, especially as a place for skiing. ► VERB 1) be inclined from a horizontal or vertical line; slant up or down. 2) informal …   English terms dictionary

  • One Hundred Famous Views of Edo — The Plum Garden in Kameido Artist Hiroshige Year 1856–58 Type ukiyo e One Hundred Famous Views of Edo (in Japanese 名所江戸百景 Meisho Edo Hyakkei ) is a series of …   Wikipedia

  • slope — [[t]slo͟ʊp[/t]] slopes, sloping, sloped 1) N COUNT: usu with supp A slope is the side of a mountain, hill, or valley. Saint Christo is perched on a mountain slope. ...the lower slopes of the Himalayas. 2) N COUNT: usu sing A slope is a surface… …   English dictionary

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”