Etiquetas

, ,

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:

  1. 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.
  2. Obtener el subgrafo con los votos de una noticia y calcular su densidad
  3. 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:

  1. 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.
  2. 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.

Publicadas con menor densidad

0.58 http://www.meneame.net/story/baumgartner-espanoles-11-000-metros-caida-libre-sin-trajes
0.59 http://www.meneame.net/story/donarias-05-tu-patrimonio
0.75 http://www.meneame.net/story/mapa-animado-batalla-trafalgar
0.76 http://www.meneame.net/story/desobedientes-salvados-programa-completo
0.83 http://www.meneame.net/story/opoposicion-oponte-tu-ejecucion-hipotecaria
0.88 http://www.meneame.net/story/gobierno-ultima-supresion-puentes-festivos
0.9 http://www.meneame.net/story/castellers-vilafranca-hacen-historia-nuevo-inmenso-castell-gama
0.92 http://www.meneame.net/story/murio-anais-fournier-consumir-bebida-energetica-monster
0.93 http://www.meneame.net/story/apple-no-podra-usar-marca-iphone-mexico
0.94 http://www.meneame.net/story/tasa-paro-espana-provincias

Publicadas con mayor densidad

4.8 http://www.meneame.net/story/television-valenciana-congela-ere-falta-financiacion-pagarlo
4.73 http://www.meneame.net/story/localizados-fosa-paterna-restos-doce-fusilados
4.47 http://www.meneame.net/story/hallan-sustancia-ayuda-exfumadores-no-volver-caer-vicio
4.2 http://www.meneame.net/story/como-crisis-crea-siervos-nuevos-senores-deudales
4.13 http://www.meneame.net/story/montoro-destituye-cupula-patrimonio-tras-fallido-prestamo-fla
4.11 http://www.meneame.net/story/trabajar-madrugada-sin-seguridad-social-3-euros-hora
4.07 http://www.meneame.net/story/cifuentes-abre-expediente-sancionador-okupas-congreso-anoche
3.84 http://www.meneame.net/story/lista-lagarde-completa-ha-motivado-detencion-kostas-vaxevanis
3.8 http://www.meneame.net/story/anos-investigacion-cientifica-perdidos-ratones-ahogados-huracan
3.79 http://www.meneame.net/story/150-municipios-franceses-no-pagan-factura-electrica-fr