En Menéame teníamos desde 2008 un control de diversidad de votos. Éste se basaba en el control de los votos de los usuarios al autor de un envío, se tomaba en cuenta el porcentaje de noticias votadas al mismo usuario. Aunque cumplió con su papel, claramente era insuficiente. Las críticas de que un grupo de personas podían conseguir una “ventaja” de lo que salía en portada tenían algo de razón. El control existente no hacía un control más global, es decir, grupos de personas con un mismo patrón de votos, por lo que intencionadamente o no, si hay un centenar de personas muy activas y afines entre ellas, éstas consiguen que sus noticias se publiquen con mayor facilidad.
Llevaba años pensando en una solución al problema. Los algoritmos y técnicas usadas son en general basadas en “corpus completo”, se construye un grafo o sus correspondientes matrices con la información completa que se quiere analizar. Para ello se pueden usar algoritmos de clustering, centralidad y/o afinidad para obtener información del grado de “diversidad de votos” en cada noticia.
Estas soluciones, por su requerimiento computacional, hacía imposible -por caro- su uso en Menéame, requieren analizar millones de votos y todas sus combinaciones posibles entre usuarios. El algoritmo de promoción de noticias se ejecuta cada cinco minutos, éste necesitaría analizar esos millones de votos, de decenas de miles de noticias, para poder calcular los “votos afines” con un mínimo de significación estadística.
Las técnica más usada para la afinidad entre usuarios son las de “distancias en espacio vectorial”, en Menéame podría aplicarse calculando la distancia entre cada par de usuarios, y a partir de ellas intentar discriminar el grado de diversidad de una noticia. Aún así no se obtiene una solución directa ¿cómo se comparan distancias agregadas entre pares de usuarios? Llevaba años buscando una solución, tuve largas reuniones y charlas con gente especializada en el tema, de mi universidad, de otras universidades (entre ellos @JJMerelo, que colaboró bastante), e incluso investigadores del CSIC.
Incluso probé con algoritmos basados en valores propios (como los que se usan para cálculo de centralidadde grafos) y análisis espectral, pero no obtenían resultados razonables. El problema era el mismo: poder hacer cálculos incrementales en vez de hacerlo con el corpus completo.
Hasta que a finales de setiembre se me ocurrió la solución, estando en la ducha, literalmente. (Lo que me hace sospechar que era yo el que tenía problemas de explicar y atacar el problema correctamente. Además de conocimientos, me falta la creatividad de los buenos matemáticos).
Tenía que escribir un apunte para explicarlo este nuevo algoritmo a los usuarios de Menéame (y actualizar la explicación ya obsoleta), pero como no encontré nada similar en toda la literatura a la que tuve acceso en los últimos años (al menos no para este tipo de análisis de afinidad, sí para análisis de poblaciones) decidí hacerlo con un poco más de detalle para los que tengan problemas similares (también estoy meditando si tiene el suficiente valor y vale la pena presentarlo en algún congreso o revista de temas técnicos de redes sociales).
Introducción
La idea es muy sencilla, está basada en la comparación de densidad del grafo de votos de cada noticia que se analiza para publicar versus la densidad del grafo de las noticias (al momento de ser publicadas) de los últimos días. Si la noticia tiene mayor diversidad que el histórico, se le aplica un bonus proporcional a la distribución, si tiene menos, una penalización también proporcional.
La ventaja de lo implementado es que permite realizar comparaciones relativamente complejas con bajo coste computacional (CPU y memoria) como de almacenamiento (se almacenan muy pocos valores). Además, dependiendo del caso, es “robusto”: no se le puede engañar votando a muchas noticias para engañar al algoritmo (como es posible con la mayoría de algoritmos de afinidad basado en distancias). Las mismas técnicas pueden ser aplicadas a problemas similares, por ejemplo analizar el grado de diversidad de matriculación de asignaturas, o la compra de productos en una tienda electrónica (da una idea si un producto se vende sólo a un nicho o perfil de clientes específico) y, por supuesto, a todos los sistemas de “democracia digital” que están surgiendo en los últimos años (por ejemplo, saber el grado de consenso que tiene cada medida votada).
Los programas que implementan son relativamente sencillos y breves, fueron programados en pocos días. Empecé con las pruebas el 1 de octubre y funcionan de forma estable desde el 5 de octubre. Los resultados se pueden ver en los “registros” de cada noticia, se puede observar que la densidad es de 2.16, su probabilidad de 0.42 está por debajo de la mediana (0.5) por lo que obtiene 34 puntos de karma de bonus.
Funcionamiento
El problema fundamental es cómo construir el grafo de votos de cada noticia para poder comparar su densidad con el histórico. Para ello hay tres pasos:
- Construir y mantener un grafo general, con pesos, con el historial de votos de usuarios: es el algoritmo más complejo y que más recursos consumo, pero se hace de forma incremental, tres veces por día.
- Obtener el subgrafo con los votos de una noticia y calcular su densidad
- Obtener la probabilidad de la densidad de la noticia con el histórico mediante una función de distribución acumulada y calcular el bonus o penalización de karma.
Construcción del grafo general
Se trata de tener un grafo con pesos (o valores) en las aristas, que representan la similitud entre cada par de usuarios. Este grafo debe ser de construcción incremental, ya que hacerlo completo varias veces al día requeriría muchos recursos informáticos que no están a nuestro alcance.
En los análisis de afinidad se suelen usar distancias (vectoriales) entre usuarios, los más sencillos son la distancia euclídea, la de Jaccard o las de cosenos. Pero estas tienen sus problemas, entre ellos es que es complicado poder hacer actualizaciones incrementales, es más complicado establecer relaciones simétricas (es decir, con aristas sin dirección) o sin “proporciones” para evitar que sean fácilmente engañados.
La decisión más importante fue optar por el número de votos que coinciden cada par de usuarios. Tiene varias ventajas, desde que es simétrico entre cada par de usuarios, hasta que se pueden establecer reglas para permitir la actualización incremental.
Básicamente lo que hace el algoritmo es crear un grafo de las relaciones entre usuarios por sus votos coincidentes y almacenarlo en la base de datos (la tabla users_similarities en el esquema). Sólo se almacena la matriz superior del grafo (con la diagonal en cero). La clave está formada por “minor” y “major”, el primero es el id de usuario menor, y el segundo el mayor, “value” es el valor calculado para el arista y en “date” se almacena la fecha del último cálculo, que luego se usa para el decay temporal que se explica más adelante. Los votos que se analizan son los votos a las noticias que no han sido publicadas y en caso de que sí lo sean, sólo los votos antes de su publicación. Se hace así para evitar el “ruido” y coste de la cantidad de votos que se producen una vez que están en portada.
El siguiente es una representación parcial del grafo que se almacena, los nodos (puntos) son usuarios, las aristas son los votos compartidos entre usuarios. Por razones de visualización (aunque casi no se ve nada), sólo se muestran las aristas calculadas en un período de 12 horas (tampoco se muestran los valores de esas aristas, se verán más adelante).
El programa que genera y actualiza el grafo general es bastante breve (gracias al Python), pero utiliza “trucos avanzados” de SQL para minimizar tiempo y consultas a la base de datos. Toma sólo unos 20 minutos para un análisis de las últimas 48 horas, aunque casi los 20 minutos son para insertar o actualizar cada arista en la base de datos (entre 400.0000 hasta 1 millón en cada ejecución).
El programa primero construye en memoria el grafo bipartito de los votos a noticias del período especificado (48 horas para el cálculo de madrugada, 24 horas para los dos cálculos que se hacen durante el día). La información se obtiene de una única consulta a la base de datos:
SELECT link_id, link_date, link_status, vote_user_id, vote_date, vote_value, UNIX_TIMESTAMP(now()) – UNIX_TIMESTAMP(link_date)
FROM votes, links
WHERE vote_type = ‘links’ and vote_user_id > 0 and vote_date > date_sub(now(), interval %s hour) and vote_date < date_sub(now(), interval %s hour) and link_id = vote_link_id»% (time_from, time_to)
A partir de esta información se construye el grafo de relaciones entre usuarios (el mostrado arriba), el peso de cada arista es el número de votos que coinciden entre cada par de usuarios. Si ambos votan similar (positivo o negativo) el valor será positivo, si el voto es contrario, será negativo.
Una vez calculado el valor del “grafo parcial” (almacenado en commons), hay que actualizar los valores previos si existen, o insertar uno nuevo, con las siguientes reglas:
- Si no existe la arista en la base de datos, o el valor absoluto del calculado es superior al anterior, guardar el último valor calculado.
- Si existe un valor anterior, y su valor absoluto es menor, el nuevo valor se calculará de la siguiente forma:
- Se usará una suma ponderada, donde el “alfa” es proporcional al tiempo analizado:
alpha = 0.9analized_hours/24 - Se aplicará un temporal decay al valor almacenado teniendo en cuenta el campo “date”. El objetivo es que un dato más antiguo debe tender a cero, el cálculo hace que se pierda el 50% del valor en 30 días.
Las operaciones anteriores están resumidas en un único SQL que minimiza las consultas a la base de datos:
INSERT INTO users_similarities (minor, major, value, date) VALUES (%s, %s, %s, ‘%s‘)
ON DUPLICATE KEY UPDATE
value = GREATEST(%s, %s * value * (1 – LEAST(1, timestampdiff(day, date, ‘%s‘)/60) ) + (1-%s) * %s), date = ‘%s‘»
% (k, l, commons[k][l], now, commons[k][l], alpha, now, alpha, commons[k][l], now)
El grafo valuado no dirigido almacenado de esta forma representa la “similitud” entre los usuarios al momento que se hizo el análisis. El algoritmo tiene en cuenta también otros detalles, como no tomar en cuenta uno de los votos (es decir n-1) de usuarios a envíos que están en pendientes, así evita que si dos usuarios sólo coincidieron una vez en una pendiente, se considere como si no hubo tal coincidencia todavía (es decir, la densidad debe tendera cero, no a uno).
Subgrafo de una noticia y su densidad
El algoritmo del “promote” que reajusta y selecciona las noticias a publicar se ejecuta cada cinco minutos. Éste es el responsable de obtener el subgrafo de los votantes a esa noticia y calcular su densidad. Para ello llama a la función PHP calculate_common_votes() de la clase Link (también hay ejemplo en Python). Para cada par de usuarios que votaron a la noticia (el total es igual a ½ n (n-1)) obtiene su valor en la tabla del grafo general y calcula su densidad que es igual a la suma de todos los valores de las aristas (cero, si no existe) dividido por ½ n (n-1).
Los grafos resultantes son similares a:
Para que se observe mejor, a continuación se muestra un grafo de una noticia con menos votos (los números en los nodos son los id de usuarios, los azules el valor de la arista -0.0 si no hay coincidencia-):
Esta función también tiene en cuenta la última fecha del cálculo del valor de la arista, y aplica la misma fórmula que el general (línea 47) para el decay temporal.
El cálculo se realiza para todas todas las noticias que están como candidatas. Se calcula la densidad de cada una y se almacena en la tabla link_commons. Esta tabla se usa para guardar los históricos para las comparaciones del paso siguiente, también se usa también como cache (2 horas máximo), para no tener que recrear el grafo completo cada vez (línea 6 a 22) ya que 100 votos de una noticia en pendientes generan 4950 consultas a la base de datos (por la fórmula ½ n (n-1)). Con los datos almacenados en la tabla, es posible calcular sólo las nuevas aristas generadas por los votos desde la última vez que se calculó.
El valor de la densidad calculada en cada ejecución también puede consultarse en los “registros” de la noticia, tal como muestra la primera imagen (se almacena como “anotaciones” junto con las demás de karma, votos, etc.).
Cálculo de la probabilidad
El último paso para calcular la bonificación o penalización es el cálculo de la probabilidad con respecto al historial de densidades de las publicadas en los últimos siete días. El código que lo hace está en el programa promote10.php.
Primero obtiene el histórico, lo ordena de menor a mayor, y luego se obtiene la probabilidad con la función de distribución acumulada mencionada anteriormente (el código es muy sencillo). Con la probabilidad calculada (el “probabilidad 0.42” que se observa en la primera imagen) se calcula el bonus. Si es menor que 0.5 será positivo, si es mayor será negativo, y toma unos valores ±30% del karma actual.
Primeros resultados
La siguiente es una gráfica de las densidades de las noticias publicadas desde el 5 de octubre hasta hoy 4 de noviembre:
Como se puede observar en la tendencia, se produce un descenso rápido de la densidad (i.e., las publicadas tienen mayor variedad de votos) en los primeros días desciende rápidamente. Luego el descenso es paulatino, hasta que en un momento se estabilizará o empezará a oscilar. Todavía no lo sabemos con precisión porque sólo tenemos datos de treinta de los sesenta días que se tomará en cuenta en el grafo general. Si no se producen cambios en los algoritmos, a principios de diciembre publicaré la misma curva, pero ya con sesenta días de datos.
Para acabar, a continuación dos tablas. La primera con las 10 noticias con menos densidad en las últimas dos semanas. La segunda las 10 con mayor densidad en el mismo período.
Ricardo Galli, de software 
Pingback: Explicación simple del algoritmo de promoción de noticias (promote) « menéame
Pingback: Cálculo comparativo de la diversidad de votos mediante densidad de grafos
Una duda ¿contempla este sistema de grafos la afinidad por votos negativos y penaliza a esos usuarios que votan sistemáticamente de manera negativa por URL de origen sin leer siquiera el contenido?
Pingback: Nuevo algoritmo de análisis y bonificación por diversidad de votos « menéame
Y por qué no usas una graph db?
Interesante. De todas formas, de la misma manera que no me interesan las películas más populares si no las películas que les gustan a gente afín a mí, ¿para cuando un sistema de recomendaciones de noticias personalizado? La verdad es que muchas veces la portada de Menéame me resulta de bajo interés.
Quizás pudieras utilizar el grafo que ya calculas para recomendar noticias que ha votado gente afín a tí.
Inicialmente yo había pensado que se podría llevar a cabo con un algoritmo de «Colaborative filtering» pero, después de leer tu post, veo que necesitarías una matriz de n x m, donde n es el número de usuarios y m el número de noticias, lo que pude ser computacionalmente difícil de llevar a la práctica (aunque se podría intentar simplificar eliminando noticias antiguas o usuarios que no hayan votado en los últimos meses).
En fin, felicidades y esperando que meneame sea cada vez mejor.
«Si no se producen cambios en los algoritmos, a principios de noviembre publicaré la misma curva, pero ya con sesenta días de datos»… en los primeros días de diciembre, no??
Pregunto lo mismo que @Remo: «contempla este sistema de grafos la afinidad por votos negativos y penaliza a esos usuarios que votan sistemáticamente de manera negativa por URL de origen sin leer siquiera el contenido??»
@remo @xurxo G.G.
Los votos negativos no son tan relevantes para este tema, son pocos y en realidad «faltan» más negativos, sobre todo para la demagogia que se disparó desde la crisis. Pero lo habrá.
Sí, es diciembre, lo arreglo, gracias.
@alnair Al principio de menéame se hacía, había una pestaña de «recomendadas», pero muy pocos la usaban, y los que sí, sólo se quejaban. El codigo todavía está en el SVN:
http://websvn.meneame.net/filedetails.php?repname=meneame&path=%2Fbranches%2Fversion4%2Fscripts%2Faffiliation-simple.pl
http://websvn.meneame.net/filedetails.php?repname=meneame&path=%2Fbranches%2Fversion4%2Fscripts%2Faffiliation.pl
Quizás con este código sea posible hacer algo más, pero en sitios como menéame nunca ha triunfado lo de «personalizado», hubo varios intentos, están todos muertos. Para eso ya puedes seguir en Twitter o Facebook a los más afines… y se vuelve en un coñado de cámara de eco.
@eduardo
¿Qué ganaría? Quizás sólo reducir el número de consultas y update, pero pierdes en consumo de memoria y complejidad: debería instalar y mantener otra base de datos diferentes. Odio todo lo que no sea KISS 😉
Comprendo. Pero quizás no gustó porqué no funcionaba bien (es evidente, a la gente no le gustaba). Pero de esta forma os perdéis el «Long tail», solo contentáis a la mayoría, en el mismo sentido que los grandes medios buscan la mayor audiencia.
Y si, para seguir aquellos temas minoritarios que me interesan seguiré conectado a los feeds RSS de mis blogs favoritos. Y seguiré dedicando más cantidad de mi tiempo libre en eso que consultando Menéame para informarme.
En mi opinión, lo que le falta a Menéame para pasar de ser un negocio rentable (?) a ser una empresa puntera es tener un sistema de recomendación personalizada de noticias que funcione (en el sentido que funcione como Google en las búsquedas).
A mi lo que mas me llama la atención de Meneame son los votos negativos sin leer el contenido del usuario jorsovernet.
Un día este logaritmo de menéame se exportará a comunidades reales, estoy seguro.
En política sería fabuloso.
¿Que tipo de problemas has tenido con algoritmos basados en autovectores? Me pica la curiosidad sobre las alternativas que has evaluado. ¿ACP, Análisis de Componentes Principales o mejor conocido como PCA en inglés? ¿U otras?
Lo que puede hacer inviable la idea de los auto vectores es que a medida que más usuarios y votos hay, la matriz crece de forma excesiva. Si tus ideas se basaron en PCA, como sospecho, hay una manera de hacerlo más llevadero. Básicamente en vez de operar con la matriz de covarianza original (A x At), se toma la reducida (At x A) Siendo At la traspuesta. Ambas matrices comparten los mismos autovectores. A esto lo he visto en el trabajo de Turk y Pentland sobre Eigenface. En su trabajo, Turk explica el «truco», ahora en lugar de tener más autovectores éstos se normalizan, reduciendo las dimensiones.
Yendo a tu caso, siendo M la cantidad de usuarios, y N la de votos, y mientras M < N se puede obtener esta forma reducida a una matriz de tamaño M x M, en vez de generar una matriz N^2 x N^2. (Si fuera N < M se invierten los papeles y se obtiene una de N x N en lugar de M^2 x M^2… el análisis es el mismo). Entonces basta ahora con calcular sobre esta matriz de covarianza reducida y tienes tus M (de dimensión N^2) autovectores y no N^2. Para obtener los M autovectores a la dimensión original N^2 basta con hacer A * V (O V * A, no tengo el paper a mano y a estas horas mi cabeza no razona demasiado). Siendo V la matriz de autovectores.
Otra optimización está en el hecho de que no se evalúe (o compare) las distancias contra todo los autovectores, sino de tomar justamente lo más representativos. En tu caso vendría a significar las publicaciones más destadas del espacio, de la semana por ejemplo. Esto es posible si se tienen ordenados los autovectores de mayor a menor. Generalmente basta con un número pequeño.
Yo entiendo que justamente quieras evitarte todo esta operatoria, después de todo aún con las optimizaciones y mejoras, tienen su costo. Más que nada debido a que esto requiere tener constantemente "actualizada" la matriz de covarianza y una creciente cantidad de usuarios y votos.
Tu propuesta me parece interesante, y hasta de esperarse… en cierto modo se busca independizarse de los tamaños de las matrices y grafos e intentar compararlos uno a otro y directamente obtener una métrica de ellos que sea más fácil de compararlas entre sí.
Leyendo tu exposición, me pregunto ¿Y si se asume que este "universo" es más o menos estable a lo largo del tiempo? De ese modo no vas recalculando reiteradas veces los autovectores… Si se dispone de un margen de tolerancia y recién cuando los cálculos se salen de órbita recalcular todo. También para achicar más las cosas, en lugar de contar con todos los votos y usuarios por cada noticia, sólo considerar de éstos un grupo reducido. Algo como lo que se hace en el sistema de puntaje olímpico… quitas los votos/usuarios por encima y por debajo y te quedas con los del "medio". Es decir quitas los votos con mayores cantidades de positivos y negativos, y/o a los usuarios "demasiado buenos" y a los "demasiado malos". Mi duda en ese punto es ¿A que se consideraría un usuario con reputación promedio?
Yo desconozco todo lo que tiene Menéame, y en como funciona por dentro, por lo que no sabría decir mucho.
Es lo que se me vino a la cabeza en cuanto leí tu post.
Saludos,
Que interesante! Para los que trabajamos en redes complejas tu idea resuena con algunas ideas que hay sobre algoritmos de recomendación, redes sociales y/o propagación viral en redes. Por ejemplo: recientes estudios han visto que la propagación de información en redes sociales está determinada por la diversidad estructural de la red, más que por la conectividad
http://www.pnas.org/content/109/16/5962.abstract
De este modo, si la red de votos nos dice algo sobre la red social (probablemente ya que en las redes sociales hay mucha similaridad) tu idea se podría traducir también como que la noticia que tiene menor densidad es la que tiene mayor diversidad estructural y por tanto la que puede llegar a más gente.
Otra idea de redes sociales que se puede traducir a lo que has hecho es que el nuevo algoritmo promociona las noticias que son «brokers» en la red bipartita de usuarios-noticias. Son aquellas noticias que conectan a gente muy diversa, es decir gente que vota a noticias muy diferentes. Es decir, una especie de «the strength of weak ties» de Granovetter pero en la red bipartita.
Siempre esta la posibilidad como comenta Marcelo, de usar SVD (Singular Value Decomposition) o NMF (non negative factorization), ambos son reducciones de dimensionalidad se usan usualmente en machine learning y especialmente en procesamiento de lenguaje natural para reducir las dimensiones de los vectores de representacion ojo, pero al mismo tiempo que reduces dimensionalidad, es capaz de capturar estructuras discriminativas. Un ejemplo en la clasificacion de textos, supongamos que tienes dos textos que hablan sobre el espacio, uno usa la palabra «cosmonauta», y el otro texto usa la palabra «astronauta», en la representaicond e vectores iniciales, ambos pertenecen a dimensiones diferentes por tanto en principio corresponden a dos caracteristicas diferentes. Sin embargo usando SVD o NMF es posible encontrar la estructura latente y unificar esas dos dimensiones automaitcamente. 🙂
@gallir no comparto para nada tu despreocupación por los votos negativos. No comprendo como en una página que supuestamente intenta proporcionar noticias populares los votos negativos tengan tanto peso frente a los positivos. La muestra que pongo siempre:
http://www.meneame.net/story/espana-campeona-eurocopa-2012
No entiendo que clase de algoritmo de cálculo no consigue que una noticia con 2000 votos positivos no llegue a portada sólo porque hay un 15% de los usuarios a quienes no les gusta.
En mi opinión se abusa de los votos «irrelevante» y «sensacionalista», dado que más que realidades son opiniones. Existe gente en meneame que se dedica a filtrar y censurar opiniones politicas gracias al sobredimensionamiento de estos votos y cada vez más meneame se está convirtiendo en un cortijo con poca o nula diversidad de opiniones políticas, al menos en la portada.
Es una pena que la mayor página de promoción de noticias de España no sea un verdadero foro abierto representativo de la sociedad española.
Un humilde aporte: Para calcular la similitud entre dos evaluadores, puedes usar el índice de acuerdo kappa, que tiene buena fama para comparar dos opinadores. Muy empleado entre médicos. En índice va entre 0 (sin acuerdo) a 1 (acuerdo total). Es fácil de calcular, yo lo he programado más de una vez.
– Es simétrico.
– Es multiclase si quieres (posibles clases: «meneo», «irrelevante», «sensacionalista», etc).
– Se calcula a partir de una matriz de confusion de los dos usuarios a comparar. El índice se calcula en tiempo constante dada la matriz. Creo que si guardas esa matriz para cada par de usuarios, se puede actualizar con cada nueva noticia que entre y hayan votado los dos. Cuando nececistes el kappa entre dos, te traes la matriz y pides el kappa.
– Tiene en cuenta los sesgos. Es decir, si comparas dos usuarios que sólo votan positivo cuando votan (nunca negativo), el kappa le da un 0 de similitud, ya que son optimistas por naturaleza, podríamos decir :-).
– Problema que le veo: No tiene en cuenta el número de noticias donde concurren los dos usuarios. Es decir, le da igual si el nivel de acuerdo se encuentra en 10 que en 100 noticias donde hayan coincidido. Quizás se pueda establecer un mínimo de noticias donde hayan concurrido dos usuarios para calcular el kappa.
http://en.wikipedia.org/wiki/Cohen%27s_kappa
@qwerty22
> no comparto para nada tu despreocupación por los votos negativos
No me hagas decir cosas que no dije.
No dije que no me preocupen, sino que son muchos menos relevantes. Estás citando un ejemplo, del millón y medio de envíos, y de las 120.000 publicadas. Te puedo citar centenares, o quizás miles, de noticias que no deberían haber sido publicadas por erróneas.
También podría dar centenares o miles de ejemplo de noticias que se publican porque las votan los mismos.
A eso me refiero con priorizar un problema sobre otro. No significa que no preocupe, sino que el impacto es muy diferente.
Además, esa noticia que indicas fue «depublicada», aún cuando estaba activado el control de endogmía que también controla los votos negativos. Aún más: para evitar esos problemas de fanboyerismo y «anti deportes» es que abrimos uno especializado en deportes http://deportes.meneame.net/
> Es una pena que la mayor página de promoción de noticias de España no sea un verdadero foro abierto representativo de la sociedad española.
¿Y esto es culpa mía o de los algoritmos? No obligamos a votar o enviar determinados temas. Es más, trabajamos duro justamente para promover la diversidad, y lo que estoy explicando aquí es un ejemplo de eso, al que también criticas, pero por todo lo contrario.
De todas formas, como siempre digo: hacemos lo mejor que podemos, y seguramente cometemos fallos. Si tú estás seguro de cómo hacerlo mucho mejor, en vez de exigir inténtalo, hasta el software es libre. Es que no hay software o algoritmo que pueda solucionar las taras (como el sesgo) y las fobias humanas.
@marcelo
Impresionante comentario. No probamos directamente PCA, pero sí similares. Para estos casos el PCA da una idea de clustering, como el k-clustering, y que de él se pueden obtener «outliers». Por allí íba al principio, luego el uso de los valores propios para centralidad, pero caíamos en dos problemas:
– El enorme tamaño de las matrices (donde usuarios son unos 15.000 diarios, y votos, unos 60.000).
– Se necesita un historia relevante, de al menos 1 mes, lo que hace que el coste del análisis sea muy elevado.
– No encontré la forma de «componer» eigenvectors, de forma de poder hacer un análisis incremental.
Lo que dices de usar «tolerancia», no lo había pensado, aunque ahora mismo no sabría cómo hacerlo. Los votos de unas pocas horas pueden (y deben) modificar el resultado. Si son unos pocos usuarios no es tan relevante, pero debes detectar cuando es una parte imortante hizo lo mismo, lo que lleva a un análisis adicional bastante complejo (computacionalmente) por sí mismo.
@lipido
Ya se hace eso ahora mismo, los votos «contrapuestos» restan al valor de la arista. Está en el:
if x*y > 0:
commons[ax][ay] += 1
else:
commons[ax][ay] -= 1
El voto negativo en menéame es el azote de los Community Mangers, a menudo expertos en hacer ruido donde les dejan. De ahí tanta queja específica sobre eso.
@galli,
Según veo lo que me dices, parece que si coinciden en el voto sumas, en caso contrario restas. ¿Se hace algo más?, Por ejemplo: si tú y yo hemos votado en 50 noticas igual y en 25 no coincidimos ¿la arista valdría 25?
Sería magnífico, estimado Ricardo, liberar parte de tus datos (anonimizados, por supuesto) para que la comunidad científica pudiera explorarlos y ofrecerte soluciones. Es decir, deja que los científicos compitan entre si, porque ellos van a estar encantados, todos ganaremos en conocimiento y, por supuesto, Menéame podrá caminar «a hombros de gigantes» 😉
¿Por qué no plateas un reto? ¿Una competición al estilo NetFlix Prize?
http://www.netflixprize.com/
@Arturo
Hemos pasado los datos (aninimizados, que lleva trabaj= a varias universidades, e incluso d einvestigadores del CSIC. Se publicaron varios papers sobre el tema (el menéame salió alguno).
Sobre una competición, humm… interesante 😉
@lipido
Sí, si fueron en el mismo períodos (24 o 48 hs), si no, depende del decay temporal. Si los contrarios fueron más recientes, tenderá a valores más próximos a cero. Incluso si hay mucho diferencia (30 días), será menor que cero.
@Pedro
jorsovernet tiene la misma personalidad que el ratoncito Pérez xD
Entonces, dejando de lado el período (suponemos el mismo período), si A y B comparten 50 enlaces y coinciden en 25 (el 50%), la arista vale 25. Pero si A y B comparten 25 enlaces y coinciden en los 25 (el 100%)… ¿también vale 25 la arista, no?
Hola de nuevo,
Como sospeché, el principal motivo de porqué no es deseable el uso de PCA o algo basado en autovectores es justamente el enorme tamaño de la matriz y el costo de tales operaciones.
El análisis incremental directamente no lo pretendía hacer tan «tiempo real». Justamente para paliar el tema de costos de tales operaciones crecientes…
Por ello yo me decía si podría asumirse que si el espacio es algo ya uniforme y estable entre todas las noticias que los componen… porqué no hacer una poda y tomar una muestra más chica y manejable. De ese modo no se trabajaría con esa escala sino una menor… Digamos por ejemplo que es tan uniforme el comportamiento de los usuarios y votos que se podría llegar «estadísticamente» a los mismos resultados si se tomaran el 10% de éstos.
Entonces en vez de trabajar con 15000 y 60000 lo harías con 1500 y 6000 (Seleccionando justamente los usuarios y votos «promedios» o centrales). Y no se toca más a esta matriz… salvo cuando los resultados obtenidos difieran mucho de un margen de tolerancia (Que habría que estudiar en como determinarlo). Lo que indicaría que es el momento de ampliar la matriz.
En Eigenface, que se vale de PCA, por ejemplo se genera una matriz de distancias. De éstas se calcula un umbral para cada de las clases de modo tal que se llegue lo más posible a un EER. Cuando se ingresa una nueva imagen a reconocer, se obtiene el vector de características y se calculan las distancias de éste a cada clase, se da por válida y reconocida cuando dicho valor es menor a su umbral.
Tomando este principio digamos por ejemplo que tomas una media ponderada entre todos los umbrales (o quizá más apropiado calcular el desvío estándar). Este numerito mágico podría servir de ayuda para ver si ya es hora de generar una nueva matriz un tanto más grande. Y nuevamente… se repite la historia.
Algo así es como me lo imaginé.
Pero si dices que los votos en unas pocas horas pueden y deben dar vuelta los resultados entonces mi planteo no sirve de mucho. Yo mucho sobre comportamiento tan dinámico no se, mis conocimientos no son tan avanzados de lo que acabo de comentarte. Lo que más me huele o que podría concebir es el uso de redes neuronales pero como bajar las ideas e implementarlas es todo un reto.
Me parece que no es nada sencillo (y quizá imposible) darle un enfoque más KISS que equilibre la dupla {volumen de datos, tiempo} al asunto. Salvo que compliques el diseño de la base de datos y añadas las tablas necesarias para registrar los datos lo más «masticados» o pre-procesados posibles como para que con algunas que otras operaciones de medianas complejidad lleguen a buen puerto (al mismo, o más aproximado) que si empleases mecanismos avanzados… sea que hablemos de análisis de grafos, autovectores, redes neuronales, etc.
Saludos,
La verdad es que es un avance y una idea muy ingeniosa. Tengo ganas de ver como este algoritmo da sus frutos, puesto que estoy harto de que la portada parezca un panfleto izquierdoso (que no izquierdista).
Finalmente he visto como lo haces en el código fuente y confirma que lo había entendido bien. Te dejo aquí una implementación para el user_common_votes.py que incluye kappa. La idea es que puedes switchear tu medida de similitud por esta y la densidad de grafos dejarla como está. (aunque kappa va entre valores negativos y como máximo vale 1).
La función main de ese fichero se parece mucho a la main que ya tienes, simplemente que pone datos de prueba directamente, pero respetando la misma estructura (o eso creo).
El fichero es directamente ejecutable en consola, donde puedes ver matrices de confusion, su índice kappa y la comparativa con la medida original que usas ahora. La matriz de confusión incluye también las abstenciones (es decir: no votar la noticia en ningún sentido).
http://dl.dropbox.com/u/11652966/meneame_kappa.py
más info sobre kappa
http://en.wikipedia.org/wiki/Cohen%27s_kappa
una calculadora de kappa para cacharrear
http://graphpad.com/quickcalcs/kappa1/?K=3