Generando 'vecinos' para usuarios según la clasificación

Question

Estoy buscando técnicas para generar 'vecinos' (personas con gustos similares) para los usuarios en un sitio en el que estoy trabajando; algo similar a la forma en que last.fm funciona.

Actualmente, tengo una función de compatibilidad para los usuarios que podría entrar en juego. Califica a los usuarios al tener 1) calificar artículos similares 2) clasificar el artículo de manera similar. La función pesa el punto 2 más alto y esto sería lo más importante si tuviera que usar solo uno de estos factores al generar "vecinos".

Una idea que tuve fue simplemente calcular la compatibilidad de cada combinación de usuarios y seleccionar a los usuarios mejor calificados para ser los vecinos del usuario. La desventaja de esto es que a medida que aumenta el número de usuarios, este proceso lleva mucho tiempo. Para solo 1000 usuarios, necesita llamadas de 1000C2 (0.5 * 1000 * 999 = = 499 500) a la función de compatibilidad, que también podría ser muy pesada en el servidor.

Así que estoy buscando cualquier consejo, enlaces a artículos, etc. sobre la mejor manera de lograr un sistema como este.

Answer 1

El problema parece ser 'problemas de clasificación'. Sí, hay tantas soluciones y enfoques.

Para iniciar la verificación de exploración este: http://en.wikipedia.org/wiki/Statistical_classification

Answer 2

en la programación Libro colectivo de Inteligencia
http://oreilly.com/catalog/9780596529321

Capítulo 2 "Cómo hacer recomendaciones" no basa un muy buen trabajo de delinear los métodos de recomendar artículos a la gente en las similitudes entre los usuarios. Puede usar los algoritmos de similitud para encontrar los "vecinos" que está buscando. El capítulo está disponible en Google de búsqueda de libros aquí:
http://books.google.com/books?id=fEsZ3Ey-Hq4C&printsec=frontcover

Answer 3

Ha oído hablar de kohonen networks?

Es un algoritmo de aprendizaje autoorganizado que agrupa variables similares en ranuras similares. Aunque la mayoría de los sitios como el que te enlace muestra la red como bidimensional, hay poco involucrado en extender el algoritmo en un hipercubo de múltiples dimensiones.

Con esta estructura de datos, encontrar y almacenar vecinos con gustos similares es trivial ya que usuarios similares deberían almacenar en ubicaciones similares (casi como un código hash inverso).

Esto reduce su problema a encontrar las variables que definirán la similitud y establecer distancias entre posibles valores de enumeración, como por ejemplo clásica y acústica, mientras que el death metal y el reggae son bastante distantes (al menos en mi opinión)

Por cierto, para encontrar buenas variables de división, el mejor algoritmo es decision tree. Los nodos más cercanos a la raíz serán las variables más importantes para establecer la "cercanía".

Answer 4

Parece que necesita leer acerca de clustering algorithms. La idea general es que en lugar de comparar cada punto con cada otro punto cada vez los divides en grupos de puntos similares. Entonces el vecindario puede ser todos los puntos en el mismo grupo. El número/tamaño de los clústeres suele ser un parámetro del algoritmo de agrupamiento.

Yo puedo encontrar un video about clustering en la serie de Google sobre cluster computing and mapreduce.

Answer 5

Las preocupaciones sobre el rendimiento se pueden mitigar en gran medida si se considera esto como un problema de compilación/lote en lugar de una consulta en tiempo real.

El gráfico puede calcularse estáticamente y luego actualizarse de forma latente, p. cada hora, día, etc. para luego generar bordes y almacenamiento optimizados para la consulta en tiempo de ejecución, p. Los 10 mejores usuarios similares para cada usuario.

+1 para programar la inteligencia colectiva también - es muy informativo - ¡desearía que no estuviera (o yo lo fuera) como orientado a Python, pero aún así es bueno!

Answer 6

Asegúrese de mirar Collaborative Filtering. Muchos sistemas de recomendación utilizan el filtrado colaborativo para sugerir elementos a los usuarios. Lo hacen encontrando "vecinos" y luego sugiriendo artículos que sus vecinos calificaron mucho pero que no han calificado. Podrías llegar a encontrar vecinos, y quién sabe, tal vez querrás recomendaciones en el futuro.

GroupLens es un laboratorio de investigación en la Universidad de Minnesota que estudia las técnicas de filtrado colaborativo. Tienen toneladas de investigaciones publicadas, así como algunos conjuntos de datos de muestra.

El Netflix Prize es una competencia para determinar quién puede resolver de manera más efectiva este tipo de problema. Siga los enlaces en su LeaderBoard. Algunos de los competidores comparten sus soluciones.

En cuanto a una solución de bajo costo computacional, puede probar esto:

• crear categorías para sus artículos. Si hablamos de música, pueden ser clásicos, rock, jazz, hip-hop ... o ir más allá: Grindcore, Math Rock, Riot Grrrl ...
• Ahora, cada vez que un usuario califica un elemento, suba sus calificaciones en el nivel de categoría Entonces, usted sabe que a 'Usuario A' le gusta Honky Tonk y Acid House porque le dan a esos artículos puntuaciones altas con frecuencia. La frecuencia y la fuerza son probablemente importantes para su puntaje agregado de categoría.
• Cuando es hora de buscar vecinos, en lugar de recorrer todas las calificaciones, solo busque puntuaciones similares en las categorías.

Este método no sería tan preciso pero es rápido.

Saludos.

Answer 7

Lo que necesita es un algoritmo de agrupamiento, que agrupe automáticamente a usuarios similares. La primera dificultad a la que se enfrentan es que la mayoría de los algoritmos de agrupación esperan que los elementos que agrupan se representen como puntos en un espacio euclidiano. En tu caso, no tienes las coordenadas de los puntos. En cambio, puede calcular el valor de la función de "similitud" entre pares de ellos.

Una buena posibilidad aquí es usar spectral clustering, que necesita precisamente lo que tiene: una matriz de similitud. La desventaja es que todavía necesita calcular su función de compatibilidad para cada par de puntos, i. mi. el algoritmo es O (n^2).

Si necesitas absolutamente un algoritmo más rápido que O (n^2), entonces puedes probar un acercamiento llamado dissimilarity spaces. La idea es muy simple. Invierte su función de compatibilidad (por ejemplo, tomando su recíproco) para convertirla en una medida de desemejanza o distancia. Luego, compara cada elemento (usuario, en su caso) con un conjunto de elementos prototipo y trata las distancias resultantes como coordenadas en un espacio. Por ejemplo, si tiene 100 prototipos, cada usuario estaría representado por un vector de 100 elementos, i. mi. por un punto en el espacio de 100 dimensiones.Luego puede usar cualquier algoritmo de clúster estándar, como K-means.

La pregunta ahora es cómo eliges los prototipos y cuántos necesitas. Se han intentado varias heurísticas, sin embargo, aquí hay un dissertation que sostiene que elegir prototipos aleatoriamente puede ser suficiente. Muestra experimentos en los que el uso de 100 o 200 prototipos seleccionados al azar produjo buenos resultados. En tu caso, si tienes 1000 usuarios y eliges 200 de ellos para que sean prototipos, entonces necesitarías evaluar tu función de compatibilidad 200,000 veces, lo que es una mejora de un factor de 2,5 sobre la comparación de cada par. La ventaja real, sin embargo, es que para 1,000,000 de usuarios, 200 prototipos seguirían siendo suficientes, y tendría que hacer 200,000,000 comparaciones, en lugar de 500,000,000,000, una mejora de un factor de 2500. Lo que obtiene es el algoritmo O (n), que es mejor que O (n^2), a pesar de un factor constante potencialmente grande.