theory - Generando ''vecinos'' para los usuarios según la clasificación
cluster-analysis neighbours (7)
¿Has oído hablar de las redes kohonen ?
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 dicha estructura de datos, encontrar y almacenar vecinos con gustos similares es trivial, ya que los usuarios similares deberían almacenar en ubicaciones similares (casi como un código hash inverso).
Esto reduce su problema a uno de encontrar las variables que definirán la similitud y establecer distancias entre posibles valores de enumeración, como por ejemplo clásico y acústico, están cerca, 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 un árbol de decisión . Los nodos más cercanos a la raíz serán las variables más importantes para establecer la "cercanía".
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 tenía era simplemente calcular la compatibilidad de cada combinación de usuarios y seleccionar a los usuarios mejor calificados para que fueran 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 consejos, enlaces a artículos, etc. sobre la mejor manera de lograr un sistema como este.
El problema parece ser ''problemas de clasificación''. Sí, hay tantas soluciones y enfoques.
Para comenzar la exploración, verifique esto: http://en.wikipedia.org/wiki/Statistical_classification
En el libro Programación de la inteligencia colectiva
http://oreilly.com/catalog/9780596529321
El Capítulo 2 "Hacer recomendaciones" hace un muy buen trabajo de delinear métodos para recomendar elementos a las personas en función de las similitudes entre los usuarios. Puede usar los algoritmos de similitud para encontrar los "vecinos" que está buscando. El capítulo está disponible en la búsqueda de libros de google aquí:
http://books.google.com/books?id=fEsZ3Ey-Hq4C&printsec=frontcover
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 manera latente, por ejemplo, cada hora, día, etc. para luego generar bordes y almacenamiento optimizados para la consulta en tiempo de ejecución, por ejemplo, los 10 mejores usuarios similares para cada usuario.
+1 para Programación de Inteligencia Colectiva también - es muy informativo - ¡desearía que no estuviera (¡o lo fuera!) Como orientado a Python, pero aún así es bueno.
Parece que necesita leer sobre algoritmos de agrupamiento . 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.
Puede encontrar un video sobre la agrupación en la serie de Google sobre computación en clúster y mapreduce .
Asegúrese de consultar el filtrado colaborativo . 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 de 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 Premio Netflix es una competencia para determinar quién puede resolver de manera más efectiva este tipo de problema. Siga los enlaces de su LeaderBoard . Algunos de los competidores comparten sus soluciones.
En cuanto a una solución computacionalmente económica, puedes intentar esto:
- Crea categorías para tus 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 clasifica un artículo, 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 llegue el momento de buscar vecinos, en lugar de recorrer todas las calificaciones, solo busque puntajes similares en las categorías.
Este método no sería tan preciso, pero es rápido.
Aclamaciones.
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 es utilizar la agrupación espectral , 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, es decir, el algoritmo es O (n ^ 2).
Si necesitas absolutamente un algoritmo más rápido que O (n ^ 2), entonces puedes probar un enfoque llamado espacios de disimilitud . 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, es decir, por un punto en un espacio de 100 dimensiones. Luego puede usar cualquier algoritmo de clúster estándar, como K-means .
La pregunta ahora es cómo elegir los prototipos y cuántos necesitas. Se han intentado varias heurísticas, sin embargo, aquí hay una disertación 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.