Algoritmo di semplice popolarità

Question

Ci sono un sacco di suggested algorithms per il calcolo della popolarità in base all'età di un articolo e il numero di voti, clic o acquisti ricevuti da un articolo. Tuttavia, i metodi più robusti che ho visto richiedono spesso calcoli eccessivamente complessi e più valori memorizzati che ingombrano il database. Stavo pensando ad un algoritmo estremamente semplice che non richiede la memorizzazione di variabili (oltre al valore di popolarità stesso) e richiede solo un semplice calcolo. E 'ridicolmente semplice:

p = (p + t)/2

Qui, p è il valore di popolarità memorizzato nel database e t è il timestamp corrente. Quando viene creato per la prima volta un articolo, è necessario inizializzare p. Ci sono due possibili metodi di inizializzazione:

1. Inizializza p con il timestamp corrente t
2. Inizializza p con la media di tutti p valori nel database

Note quel metodo di inizializzazione (1) dà agli articoli aggiunti di recente un chiaro vantaggio rispetto agli articoli storici, aggiungendo così un elemento di relevan ce. D'altra parte, il metodo di inizializzazione (2) tratta i nuovi elementi come uguali rispetto agli elementi storici.

Supponiamo di utilizzare il metodo di inizializzazione (1) e di inizializzare p con il timestamp corrente. Quando l'elemento riceve il suo primo voto, p diventa la media del tempo di creazione e del tempo di votazione. Pertanto, il valore di popolarità p rappresenta ancora un timestamp valido (assumendo il numero intero più vicino), ma il tempo effettivo che rappresenta è astratto.

Con questo metodo, è richiesto solo un semplice calcolo e nel database deve essere memorizzato solo un valore (p). Questo metodo impedisce anche i valori di fuga, dal momento che la popolarità di un dato oggetto non può mai superare l'ora corrente.

Un esempio dell'algoritmo sul posto di lavoro per un periodo di 1 giorno: http://jsfiddle.net/q2UCn/
Un esempio dell'algoritmo sul posto di lavoro per un periodo di 1 anno: http://jsfiddle.net/tWU9y/

Se vi aspettate voti a flusso costantemente nel livello sub -secondi intervalli, quindi sarà necessario utilizzare un timestamp di microsecondi, ad esempio la funzione PHP microtime(). In caso contrario, funzionerà un timestamp UNIX standard, ad esempio la funzione PHP time().

Ora per la mia domanda: vedi qualche grave difetto con questo approccio?

Answer 1

Penso che questo sia un approccio molto buono, data la sua semplicità. Un risultato molto interessante.

Ho fatto una rapida serie di calcoli e ho scoperto che questo algoritmo sembra capire cosa significhi "popolarità". Il suo problema è che ha una chiara tendenza a favorire voti recenti come questo:

Immagina di prenderci il tempo e dividerlo in valori di timestamp discreti che vanno da 100 a 1000. Supponiamo che at = 100 sia A che B (due elementi) hanno lo stesso 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). 

Quando t = 1000 viene, sia A che B ricevono voti, quindi:

Pa(1000) = 850 with 8 votes 
Pb(1000) = 856 with 5 votes 

Perché? perché l'algoritmo consente a un articolo di rapidamente battere i leader storici se riceve voti più recenti (anche se l'articolo ha meno voti in totale).

EDIT ivi compresa la simulazione

L'OP ha creato un bel violino che ho cambiato per ottenere i seguenti risultati:

http://jsfiddle.net/wBV2c/6/

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.

Answer 2

Il difetto è che qualcosa con 100 voti è solitamente più significativo di qualcosa con un solo voto recente. Tuttavia non è difficile trovare varianti del tuo schema che funzionino abbastanza bene.

Answer 3

vedo un problema, contano solo gli ultimi ~ 24 voti.

p_i+1 = (p + t)/2 

Per due voti abbiamo

p2 = (p1 + t2)/2 = ((p0 + t1) /2 + t2)/2 = p0/4 + t1/4 + t2/2 

espansione che per 32 voti dà:

p32 = t*2^-32 + t0*2^-32 + t1*2^-31 + t2*2^-30 + ... + t31*2^-1 

Così per firmati valori a 32 bit, t0 non ha alcun effetto sul risultato. Poiché t0 viene diviso per 2^32, non contribuirà a p32.

Se abbiamo due elementi A e B (non importa quanto grandi siano le differenze) se ottengono entrambi gli stessi 32 voti, avranno la stessa popolarità. Quindi la tua storia risale a soli 32 voti. Non c'è differenza tra 2032 e 32 voti, se gli ultimi 32 voti sono gli stessi.

Se la differenza è inferiore a un giorno, saranno uguali dopo 17 voti.