¿Cuál es la mejor manera de calcular temas o etiquetas de tendencias?

Muchos sitios ofrecen algunas estadísticas como "Los temas más candentes en las últimas 24 horas". Por ejemplo, Topix.com muestra esto en su sección "Tendencias de noticias". Allí, puede ver los temas que tienen el mayor número de menciones.

También quiero calcular tal "zumbido" para un tema. ¿Cómo podría hacer esto? El algoritmo debe ponderar los temas que siempre son menos interesantes. Los temas que normalmente (casi) nadie menciona deberían ser los más candentes.

Google ofrece "Tendencias populares", topix.com muestra "Temas de actualidad", fav.or.it muestra "Tendencias de palabras clave": todos estos servicios tienen una cosa en común: solo muestran tendencias futuras que son anormalmente actuales en este momento.

Términos como "Britney Spears", "clima" o "Paris Hilton" no aparecerán en estas listas porque siempre son calientes y frecuentes. Este artículo llama a esto "El problema de Britney Spears".

Mi pregunta: ¿cómo puede codificar un algoritmo o utilizar uno existente para resolver este problema? Al tener una lista con las palabras clave buscadas en las últimas 24 horas, el algoritmo debería mostrar las 10 (por ejemplo) más populares.

Lo sé, en el artículo anterior, hay algún tipo de algoritmo mencionado. He intentado codificarlo en PHP pero no creo que funcione. Simplemente encuentra la mayoría, ¿no?

Espero que me puedan ayudar (codificar ejemplos sería genial).

Este problema requiere un puntaje z o puntaje estándar, que tendrá en cuenta el promedio histórico, como han mencionado otras personas, pero también la desviación estándar de estos datos históricos, lo que lo hace más robusto que el simple uso del promedio.

En su caso, la siguiente fórmula calcula un puntaje z, donde la tendencia sería una tasa tal como vistas / día.

z-score = ([current trend] - [average historic trends]) / [standard deviation of historic trends]

Cuando se utiliza un puntaje z, cuanto mayor o menor es el puntaje z, más anormal es la tendencia, por ejemplo, si el puntaje z es altamente positivo, entonces la tendencia aumenta de manera anormal, mientras que si es altamente negativo, disminuye anormalmente . Entonces, una vez que calcule el puntaje z para todas las tendencias candidatas, los 10 puntajes z más altos se relacionarán con los puntajes z más anormales.

Consulte Wikipedia para obtener más información sobre las puntuaciones z.

Código

from math import sqrt

def zscore(obs, pop):
    # Size of population.
    number = float(len(pop))
    # Average population value.
    avg = sum(pop) / number
    # Standard deviation of population.
    std = sqrt(sum(((c - avg) ** 2) for c in pop) / number)
    # Zscore Calculation.
    return (obs - avg) / std

Salida de muestra

>>> zscore(12, [2, 4, 4, 4, 5, 5, 7, 9])
3.5
>>> zscore(20, [21, 22, 19, 18, 17, 22, 20, 20])
0.0739221270955
>>> zscore(20, [21, 22, 19, 18, 17, 22, 20, 20, 1, 2, 3, 1, 2, 1, 0, 1])
1.00303599234
>>> zscore(2, [21, 22, 19, 18, 17, 22, 20, 20, 1, 2, 3, 1, 2, 1, 0, 1])
-0.922793112954
>>> zscore(9, [1, 2, 0, 3, 1, 3, 1, 2, 9, 8, 7, 10, 9, 5, 2, 4, 1, 1, 0])
1.65291949506

Notas

• Puede usar este método con una ventana deslizante (es decir, los últimos 30 días) si no desea tener en cuenta demasiado historial, lo que hará que las tendencias a corto plazo sean más pronunciadas y reduzca el tiempo de procesamiento.

• También puede usar una puntuación z para valores como el cambio en las vistas de un día al día siguiente para ubicar los valores anormales para aumentar / disminuir las vistas por día. Esto es como usar la pendiente o derivada del gráfico de vistas por día.

• Si realiza un seguimiento del tamaño actual de la población, el total actual de la población y el total actual de x ^ 2 de la población, no necesita recalcular estos valores, solo actualícelos y, por lo tanto, solo necesita mantenga estos valores para el historial, no cada valor de datos. El siguiente código demuestra esto.

  from math import sqrt
  
  class zscore:
      def __init__(self, pop = []):
          self.number = float(len(pop))
          self.total = sum(pop)
          self.sqrTotal = sum(x ** 2 for x in pop)
      def update(self, value):
          self.number += 1.0
          self.total += value
          self.sqrTotal += value ** 2
      def avg(self):
          return self.total / self.number
      def std(self):
          return sqrt((self.sqrTotal / self.number) - self.avg() ** 2)
      def score(self, obs):
          return (obs - self.avg()) / self.std()
  

• Con este método, su flujo de trabajo sería el siguiente. Para cada tema, etiqueta o página, cree un campo de punto flotante, para el número total de días, la suma de vistas y la suma de vistas al cuadrado en su base de datos. Si tiene datos históricos, inicialice estos campos utilizando esos datos, de lo contrario, inicialícelos a cero. Al final de cada día, calcule el puntaje z utilizando el número de vistas del día contra los datos históricos almacenados en los tres campos de la base de datos. Los temas, las etiquetas o las páginas con los puntajes z X más altos son sus X "tendencias más populares" del día. Finalmente actualice cada uno de los 3 campos con el valor del día y repita el proceso mañana.

Nueva adquisición

Los puntajes z normales como se discutió anteriormente no tienen en cuenta el orden de los datos y, por lo tanto, el puntaje z para una observación de '1' o '9' tendría la misma magnitud contra la secuencia [1, 1, 1, 1 , 9, 9, 9, 9]. Obviamente para la búsqueda de tendencias, los datos más actuales deberían tener más peso que los datos más antiguos y, por lo tanto, queremos que la observación '1' tenga una puntuación de magnitud mayor que la observación '9'. Para lograr esto, propongo una puntuación z promedio flotante. Debe quedar claro que NO se garantiza que este método sea estadísticamente sólido, pero debería ser útil para la búsqueda de tendencias o similar. La principal diferencia entre el puntaje z estándar y el puntaje z promedio flotante es el uso de un promedio flotante para calcular el valor promedio de la población y el valor promedio de la población al cuadrado. Ver código para más detalles:

Código

class fazscore:
    def __init__(self, decay, pop = []):
        self.sqrAvg = self.avg = 0
        # The rate at which the historic data's effect will diminish.
        self.decay = decay
        for x in pop: self.update(x)
    def update(self, value):
        # Set initial averages to the first value in the sequence.
        if self.avg == 0 and self.sqrAvg == 0:
            self.avg = float(value)
            self.sqrAvg = float((value ** 2))
        # Calculate the average of the rest of the values using a 
        # floating average.
        else:
            self.avg = self.avg * self.decay + value * (1 - self.decay)
            self.sqrAvg = self.sqrAvg * self.decay + (value ** 2) * (1 - self.decay)
        return self
    def std(self):
        # Somewhat ad-hoc standard deviation calculation.
        return sqrt(self.sqrAvg - self.avg ** 2)
    def score(self, obs):
        if self.std() == 0: return (obs - self.avg) * float("infinity")
        else: return (obs - self.avg) / self.std()

Muestra IO

>>> fazscore(0.8, [1, 1, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9]).score(1)
-1.67770595327
>>> fazscore(0.8, [1, 1, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9]).score(9)
0.596052006642
>>> fazscore(0.9, [2, 4, 4, 4, 5, 5, 7, 9]).score(12)
3.46442230724
>>> fazscore(0.9, [2, 4, 4, 4, 5, 5, 7, 9]).score(22)
7.7773245459
>>> fazscore(0.9, [21, 22, 19, 18, 17, 22, 20, 20]).score(20)
-0.24633160155
>>> fazscore(0.9, [21, 22, 19, 18, 17, 22, 20, 20, 1, 2, 3, 1, 2, 1, 0, 1]).score(20)
1.1069362749
>>> fazscore(0.9, [21, 22, 19, 18, 17, 22, 20, 20, 1, 2, 3, 1, 2, 1, 0, 1]).score(2)
-0.786764452966
>>> fazscore(0.9, [1, 2, 0, 3, 1, 3, 1, 2, 9, 8, 7, 10, 9, 5, 2, 4, 1, 1, 0]).score(9)
1.82262469243
>>> fazscore(0.8, [40] * 200).score(1)
-inf

Actualizar

Como David Kemp señaló correctamente, si se le da una serie de valores constantes y luego se solicita un puntaje z para un valor observado que difiere de los otros valores, el resultado probablemente no sea cero. De hecho, el valor devuelto debe ser infinito. Entonces cambié esta línea,

if self.std() == 0: return 0

a:

if self.std() == 0: return (obs - self.avg) * float("infinity")

Este cambio se refleja en el código de la solución fazscore. Si uno no quiere lidiar con valores infinitos, una solución aceptable podría ser cambiar la línea a:

if self.std() == 0: return obs - self.avg

Necesita un algoritmo que mida la velocidad de un tema, o en otras palabras, si lo grafica, desea mostrar los que están subiendo a una velocidad increíble.

Esta es la primera derivada de la línea de tendencia, y no es difícil de incorporar como un factor ponderado de su cálculo general.

Normalizar

Una técnica que deberá hacer es normalizar todos sus datos. Para cada tema que esté siguiendo, mantenga un filtro de paso muy bajo que defina la línea base de ese tema. Ahora, todos los puntos de datos que surjan sobre ese tema deben normalizarse: reste su línea de base y obtendrá TODOS sus temas cerca de 0, con picos encima y debajo de la línea. En cambio, es posible que desee dividir la señal por su magnitud de línea de base, lo que hará que la señal sea de alrededor de 1.0; esto no solo alinea todas las señales entre sí (normaliza la línea de base), sino que también normaliza los picos. Una espiga de Britney será de magnitud mayor que la espiga de otra persona, pero eso no significa que debas prestarle atención; la espiga puede ser muy pequeña en relación con su línea de base.

Derivar

Una vez que haya normalizado todo, descubra la pendiente de cada tema. Tome dos puntos consecutivos y mida la diferencia. Una diferencia positiva es una tendencia ascendente, una diferencia negativa es una tendencia descendente. Luego, puede comparar las diferencias normalizadas y descubrir qué temas se están disparando en popularidad en comparación con otros temas, con cada tema ajustado a su propia 'normalidad', que pueden ser magnitudes de orden diferentes de otros temas.

Esto es realmente un primer paso en el problema. Hay técnicas más avanzadas que necesitará usar (principalmente una combinación de lo anterior con otros algoritmos, ponderados para satisfacer sus necesidades), pero debería ser suficiente para comenzar.

Sobre el articulo

El artículo trata sobre tendencias de temas, pero no trata sobre cómo calcular lo que está de moda y lo que no, sino sobre cómo procesar la gran cantidad de información que dicho algoritmo debe procesar en lugares como Lycos y Google. El espacio y el tiempo necesarios para dar un contador a cada tema y encontrar el contador de cada tema cuando se realiza una búsqueda es enorme. Este artículo trata sobre los desafíos que uno enfrenta cuando intenta tal tarea. Menciona el efecto Brittney, pero no habla de cómo superarlo.

Como señala Nixuz, esto también se conoce como Z o puntaje estándar .

Chad Birch y Adam Davis tienen razón en que tendrá que mirar hacia atrás para establecer una línea de base. Su pregunta, tal como está redactada, sugiere que solo desea ver los datos de las últimas 24 horas, y eso no será suficiente.

Una forma de dar a sus datos algo de memoria sin tener que consultar un gran cuerpo de datos históricos es usar un promedio móvil exponencial. La ventaja de esto es que puede actualizar esto una vez por período y luego eliminar todos los datos antiguos, por lo que solo necesita recordar un solo valor. Entonces, si su período es un día, debe mantener un atributo de "promedio diario" para cada tema, lo que puede hacer de la siguiente manera:

a_n = a_(n-1)*b + c_n*(1-b)

Donde a_nestá el promedio móvil a partir del día n, b es algo constante entre 0 y 1 (cuanto más cercano a 1, más largo es el recuerdo) y c_nes el número de visitas en el día n. La belleza es que si realiza esta actualización al final del día n, puede enjuagarse c_ny a_(n-1).

La única advertencia es que inicialmente será sensible a lo que elija para su valor inicial de a.

EDITAR

Si se ayuda a visualizar este enfoque, tomar n = 5, a_0 = 1y b = .9.

Digamos que los nuevos valores son 5,0,0,1,4:

a_0 = 1
c_1 = 5 : a_1 = .9*1 + .1*5 = 1.4
c_2 = 0 : a_2 = .9*1.4 + .1*0 = 1.26
c_3 = 0 : a_3 = .9*1.26 + .1*0 = 1.134
c_4 = 1 : a_4 = .9*1.134 + .1*1 = 1.1206
c_5 = 4 : a_5 = .9*1.1206 + .1*5 = 1.40854

¿No se parece mucho a un promedio? Observe cómo el valor se mantuvo cerca de 1, a pesar de que nuestra siguiente entrada fue 5. ¿Qué está pasando? Si expandes las matemáticas, lo que obtienes es que:

a_n = (1-b)*c_n + (1-b)*b*c_(n-1) + (1-b)*b^2*c_(n-2) + ... + (leftover weight)*a_0

¿Qué quiero decir con peso sobrante? Bueno, en cualquier promedio, todos los pesos deben sumarse a 1. Si n fuera infinito y el ... pudiera continuar para siempre, entonces todos los pesos sumarían 1. Pero si n es relativamente pequeño, queda una buena cantidad de peso en la entrada original.

Si estudia la fórmula anterior, debe darse cuenta de algunas cosas sobre este uso:

1. Todos los datos aportan algo al promedio para siempre. Hablando prácticamente, hay un punto en el que la contribución es muy, muy pequeña.
2. Los valores recientes contribuyen más que los valores anteriores.
3. Cuanto mayor sea b, los valores nuevos menos importantes son y los valores antiguos más largos son importantes. Sin embargo, cuanto mayor sea b, más datos necesitará para diluir el valor inicial de a.

Creo que las dos primeras características son exactamente lo que estás buscando. Para darle una idea de lo simple, esto puede ser implementar, aquí hay una implementación de Python (menos toda la interacción de la base de datos):

>>> class EMA(object):
...  def __init__(self, base, decay):
...   self.val = base
...   self.decay = decay
...   print self.val
...  def update(self, value):
...   self.val = self.val*self.decay + (1-self.decay)*value
...   print self.val
... 
>>> a = EMA(1, .9)
1
>>> a.update(10)
1.9
>>> a.update(10)
2.71
>>> a.update(10)
3.439
>>> a.update(10)
4.0951
>>> a.update(10)
4.68559
>>> a.update(10)
5.217031
>>> a.update(10)
5.6953279
>>> a.update(10)
6.12579511
>>> a.update(10)
6.513215599
>>> a.update(10)
6.8618940391
>>> a.update(10)
7.17570463519

Por lo general, el "zumbido" se resuelve utilizando alguna forma de mecanismo de descomposición exponencial / logarítmica. Para obtener una descripción general de cómo Hacker News, Reddit y otros manejan esto de una manera simple, vea esta publicación .

Esto no aborda completamente las cosas que siempre son populares. Lo que estás buscando parece ser algo así como la función " Tendencias populares " de Google . Para eso, puede dividir el valor actual por un valor histórico y luego restar los que están por debajo de un umbral de ruido.

Creo que la palabra clave que debes notar es "anormalmente". Para determinar cuándo algo es "anormal", debe saber qué es normal. Es decir, necesitará datos históricos, que puede promediar para averiguar la tasa normal de una consulta en particular. Es posible que desee excluir días anormales del cálculo del promedio, pero nuevamente eso requerirá tener suficientes datos ya, para que sepa qué días excluir.

A partir de ahí, tendrá que establecer un umbral (lo que requeriría experimentación, estoy seguro), y si algo sale del umbral, digamos 50% más de búsquedas de lo normal, puede considerarlo una "tendencia". O bien, si desea poder encontrar el "Top X Trendiest" como mencionó, solo necesita ordenar las cosas según la distancia (porcentual) que están lejos de su tasa normal.

Por ejemplo, supongamos que sus datos históricos le han dicho que Britney Spears generalmente obtiene 100,000 búsquedas, y Paris Hilton generalmente obtiene 50,000. Si tiene un día en el que ambos obtienen 10,000 búsquedas más de lo normal, debería considerar a Paris "más caliente" que Britney, porque sus búsquedas aumentaron un 20% más de lo normal, mientras que las de Britney fueron solo del 10%.

Dios, no puedo creer que acabo de escribir un párrafo que compara la "pasión" de Britney Spears y Paris Hilton. ¿Qué me has hecho?

Me preguntaba si es posible utilizar la fórmula de aceleración física regular en tal caso.

v2-v1/t or dv/dt

¿Podemos considerar v1 como me gusta / votos / conteo de comentarios iniciales por hora y v2 como "velocidad" actual por hora en las últimas 24 horas?

Esto se parece más a una pregunta que a una respuesta, pero parece que puede funcionar. Cualquier contenido con mayor aceleración será el tema de tendencia ...

Estoy seguro de que esto puede no resolver el problema de Britney Spears :-)

probablemente funcionaría un simple gradiente de frecuencia de tema: gran gradiente positivo = creciente popularidad rápidamente.

la forma más fácil sería agrupar el número de búsquedas cada día, para que tenga algo como

searches = [ 10, 7, 14, 8, 9, 12, 55, 104, 100 ]

y luego descubra cuánto cambió día a día:

hot_factor = [ b-a for a, b in zip(searches[:-1], searches[1:]) ]
# hot_factor is [ -3, 7, -6, 1, 3, 43, 49, -4 ]

y simplemente aplique algún tipo de umbral para que los días en que el aumento fue> 50 se consideren "calientes". podrías hacer esto mucho más complicado si quieres también. en lugar de la diferencia absoluta, puede tomar la diferencia relativa para que pasar de 100 a 150 se considere caliente, pero de 1000 a 1050 no. o un gradiente más complicado que tenga en cuenta las tendencias durante más de un día para el siguiente.

Había trabajado en un proyecto, donde mi objetivo era encontrar temas de tendencias de Live Twitter Stream y también hacer un análisis sentimental sobre los temas de tendencias (encontrar si el tema de tendencias hablaba positiva / negativamente). He usado Storm para manejar la transmisión de Twitter.

He publicado mi informe como blog: http://sayrohan.blogspot.com/2013/06/finding-trending-topics-and-trending.html

He usado Total Count y Z-Score para el ranking.

El enfoque que he usado es un poco genérico, y en la sección de discusión, mencioné cómo podemos extender el sistema para aplicaciones que no son de Twitter.

Espero que la información ayude.

Si simplemente mira tweets o mensajes de estado para obtener sus temas, encontrará mucho ruido. Incluso si elimina todas las palabras vacías. Una forma de obtener un mejor subconjunto de candidatos a temas es centrarse solo en tweets / mensajes que comparten una URL y obtener las palabras clave del título de esas páginas web. Y asegúrese de aplicar el etiquetado POS para obtener sustantivos + frases nominales también.

Los títulos de las páginas web generalmente son más descriptivos y contienen palabras que describen de qué trata la página. Además, compartir una página web generalmente se correlaciona con el intercambio de noticias de última hora (es decir, si una celebridad como Michael Jackson murió, habrá muchas personas compartiendo un artículo sobre su muerte).

Realicé experimentos donde solo tomo palabras clave populares de los títulos, y luego obtengo el recuento total de esas palabras clave en todos los mensajes de estado, y definitivamente eliminan mucho ruido. Si lo hace de esta manera, no necesita un algoritmo complejo, solo haga un simple pedido de las frecuencias de las palabras clave y estará a medio camino.

Puede usar las razones de probabilidad de registro para comparar la fecha actual con el último mes o año. Esto es estadísticamente sólido (dado que sus eventos no se distribuyen normalmente, lo que debe suponerse a partir de su pregunta).

Simplemente ordene todos sus términos por logLR y elija los diez mejores.

public static void main(String... args) {
    TermBag today = ...
    TermBag lastYear = ...
    for (String each: today.allTerms()) {
        System.out.println(logLikelihoodRatio(today, lastYear, each) + "\t" + each);
    }
} 

public static double logLikelihoodRatio(TermBag t1, TermBag t2, String term) {
    double k1 = t1.occurrences(term); 
    double k2 = t2.occurrences(term); 
    double n1 = t1.size(); 
    double n2 = t2.size(); 
    double p1 = k1 / n1;
    double p2 = k2 / n2;
    double p = (k1 + k2) / (n1 + n2);
    double logLR = 2*(logL(p1,k1,n1) + logL(p2,k2,n2) - logL(p,k1,n1) - logL(p,k2,n2));
    if (p1 < p2) logLR *= -1;
    return logLR;
}

private static double logL(double p, double k, double n) {
    return (k == 0 ? 0 : k * Math.log(p)) + ((n - k) == 0 ? 0 : (n - k) * Math.log(1 - p));
}

PD: un TermBag es una colección desordenada de palabras. Para cada documento, crea una bolsa de términos. Solo cuenta las ocurrencias de las palabras. Luego, el método occurrencesdevuelve el número de apariciones de una palabra determinada y el método sizedevuelve el número total de palabras. Es mejor normalizar las palabras de alguna manera, por lo general toLowerCasees lo suficientemente bueno. Por supuesto, en los ejemplos anteriores, crearía un documento con todas las consultas de hoy y uno con todas las consultas del año pasado.

La idea es hacer un seguimiento de tales cosas y notar cuándo saltan significativamente en comparación con su propia línea de base.

Por lo tanto, para consultas que tienen más de un umbral determinado, haga un seguimiento de cada una y cuando cambie a algún valor (digamos casi el doble) de su valor histórico, entonces es una nueva tendencia.