algorithm - citation - the anatomy of a large-scale hypertextual web search engine español
Algoritmo de popularidad simple (5)
Creo que este es un muy buen enfoque, dada su simplicidad. Un resultado muy interesante.
Hice un conjunto rápido de cálculos y descubrí que este algoritmo parece entender lo que significa "popularidad". Su problema es que tiene una clara tendencia a favorecer los votos recientes como este:
Imagina que tomamos el tiempo y lo dividimos en valores de marca de tiempo discretos que van de 100 a 1000. Supongamos que en t = 100, tanto A como B (dos elementos) tienen la misma P = 100.
A gets voted 7 times on 200, 300, 400, 500, 600, 700 and 800
resulting on a final Pa(800) = 700 (aprox).
B gets voted 4 times on 300, 500, 700 and 900
resulting on a final Pb(900) = 712 (aprox).
Cuando t = 1000 llega, tanto A como B reciben votos, entonces:
Pa(1000) = 850 with 8 votes
Pb(1000) = 856 with 5 votes
¿Por qué? porque el algoritmo permite que un elemento supere rápidamente a los líderes históricos si recibe votos más recientes (incluso si el elemento tiene menos votos en total).
EDICIÓN INCLUYENDO SIMULACIÓN
El OP creó un bonito violín que cambié para obtener los siguientes resultados:
Item A receives one vote each day from 1970 till 2012 (15339 votes)
Item B receives one vote each month from Jan to Jul 2012 (7 votes)
The result: B is more popular than A.
Hay muchos algoritmos sugeridos para calcular la popularidad según la edad de un elemento y la cantidad de votos, clics o compras que recibe un elemento. Sin embargo, los métodos más robustos que he visto a menudo requieren cálculos demasiado complejos y múltiples valores almacenados que saturan la base de datos. He estado contemplando un algoritmo extremadamente simple que no requiere almacenar ninguna variable (aparte del valor de popularidad en sí mismo) y solo requiere un cálculo simple. Es ridículamente simple:
p = (p + t) / 2
Aquí, p es el valor de popularidad almacenado en la base de datos y t es la marca de tiempo actual . Cuando se crea un artículo por primera vez, se debe inicializar p . Hay dos posibles métodos de inicialización:
- Inicialice p con la marca de tiempo actual t
- Inicialice p con el promedio de todos los valores de p en la base de datos
Tenga en cuenta que el método de inicialización (1) le da a los artículos recientemente agregados una clara ventaja sobre los artículos históricos, agregando así un elemento de relevancia . Por otro lado, el método de inicialización (2) trata los elementos nuevos como iguales en comparación con los elementos históricos.
Digamos que utiliza el método de inicialización (1) e inicializa p con la marca de tiempo actual. Cuando el elemento recibe su primer voto, p se convierte en el promedio del tiempo de creación y el tiempo de voto. Por lo tanto, el valor de popularidad p aún representa una marca de tiempo válida (suponiendo que redondeas al número entero más cercano), pero el tiempo real que representa se extrae.
Con este método, solo se requiere un cálculo simple y solo se necesita almacenar un valor en la base de datos ( p ). Este método también evita valores fuera de control, ya que la popularidad de un elemento dado nunca puede exceder la hora actual.
Un ejemplo del algoritmo en funcionamiento durante un período de 1 día: http://jsfiddle.net/q2UCn/
Un ejemplo del algoritmo en funcionamiento durante un período de 1 año: http://jsfiddle.net/tWU9y/
Si espera que los votos se transmitan de manera constante en intervalos de un segundo, entonces deberá usar una marca de tiempo de microsegundos, como la función PHP microtime() . De lo contrario, funcionará una marca de tiempo estándar de UNIX, como la función PHP time() .
Ahora, para mi pregunta: ¿ve algún defecto importante con este enfoque?
El algoritmo propuesto es un buen enfoque, y es un caso especial de una media móvil exponencial donde alfa = 0.5:
p = alpha*p + (1-alpha)*t = 0.5*p + 0.5*t = (p+t)/2 //(for alpha = 0.5)
Una forma de modificar el hecho de que la solución propuesta para alfa = 0.5 tiende a favorecer los votos recientes (como lo señala el daniloquio) es elegir valores más altos para alfa (por ejemplo, 0.9 o 0.99). Tenga en cuenta que aplicar esto al testcase propuesto por daniloquio no funciona sin embargo, porque cuando alfa aumenta el algoritmo necesita más "tiempo" para establecerse (por lo tanto, las matrices deberían ser más largas, lo que a menudo es cierto en aplicaciones reales).
Así:
- para alfa = 0.9 el algoritmo promedia aproximadamente los últimos 10 valores
- para alfa = 0.99 el algoritmo promedia aproximadamente los últimos 100 valores
- para alfa = 0.999 el algoritmo promedia aproximadamente los últimos 1000 valores
- etc.
La falla es que algo con 100 votos suele ser más significativo que algo con solo un voto reciente. Sin embargo, no es difícil encontrar variantes de su esquema que funcionen razonablemente bien.
No creo que la lógica antes discutida vaya a funcionar. p_i + 1 = (p_i + t) / 2
El artículo A se ve en las marcas de tiempo: 70, 80, 90 popularidad (Artículo A): 82.5
El artículo B se ve en las marcas de tiempo: 50, 60, 70, 80, 90 popularidad (Artículo B): 80.625
En este caso, la popularidad del artículo B debería haber sido más. En primer lugar, el artículo B se vio recientemente como el artículo A y, en segundo lugar, también se vio más veces que el artículo A.
Veo un problema, solo los últimos ~ 24 votos cuentan.
p_i+1 = (p + t) / 2
Por dos votos tenemos
p2 = (p1 + t2) / 2 = ((p0 + t1) /2 + t2 ) / 2 = p0/4 + t1/4 + t2/2
Expandiendo eso por 32 votos da:
p32 = t*2^-32 + t0*2^-32 + t1*2^-31 + t2*2^-30 + ... + t31*2^-1
Entonces, para valores de 32 bits firmados, t0 no tiene efecto en el resultado. Debido a que t0 se divide por 2 ^ 32, no contribuirá nada a p32.
Si tenemos dos elementos A y B (sin importar qué tan grandes sean las diferencias) si ambos obtienen los mismos 32 votos, tendrán la misma popularidad. Así que tu historia se remonta por solo 32 votos. No hay diferencia en 2032 y 32 votos, si los últimos 32 votos son los mismos.
Si la diferencia es menor a un día, serán iguales después de 17 votos.