algorithm - keywords - meta title html

¿Cuál es la mejor forma de calcular temas o etiquetas de tendencia? (11)

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 número de menciones que crece más rápidamente.

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

Google ofrece "Hot Trends", topix.com muestra "Hot Topics", fav.or.it muestra "Keyword Trends": todos estos servicios tienen una cosa en común: solo muestran las próximas tendencias que son anormalmente calientes en este momento.

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

Mi pregunta: ¿cómo se 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 mostrarle los 10 (por ejemplo) más populares.

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

Espero que me puedas ayudar (los ejemplos de codificación serían geniales).

Chad Birch y Adam Davis están en lo correcto, ya que tendrán que mirar hacia atrás para establecer una línea de base. Tu pregunta, tal como está formulada, sugiere que solo deseas ver los datos de las últimas 24 horas, y eso no funcionará del todo.

Una forma de dar a sus datos algo de memoria sin tener que consultar un gran conjunto 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 cual puede hacer de la siguiente manera:

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

Donde a_n es la media móvil a partir del día n , b es una constante entre 0 y 1 (cuanto más cerca de 1, más larga es la memoria) y c_n es 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 descargar c_n y a_(n-1) .

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

EDITAR

Si ayuda a visualizar este enfoque, tome n = 5 , a_0 = 1 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 ¿verdad? 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, ¿qué obtienes?

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 sobrante de peso? Bueno, en cualquier promedio, todos los pesos deben sumar 1. Si n fuera infinito y ... pudiera continuar para siempre, todos los pesos se sumarían a 1. Pero si n es relativamente pequeño, se obtiene una buena cantidad de peso restante en la entrada original.

Si estudias la fórmula anterior, deberías darte cuenta de algunas cosas sobre este uso:

Todos los datos aportan algo al promedio para siempre. Hablando en términos prácticos, hay un punto donde la contribución es realmente, realmente pequeña.
Los valores recientes contribuyen más que los valores anteriores.
Cuanto mayor es b, menos importantes son los nuevos valores y los mayores valores antiguos importan. 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

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

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

Por ejemplo, digamos que sus datos históricos le han dicho que Britney Spears generalmente recibe 100.000 búsquedas, y Paris Hilton generalmente obtiene 50,000. Si tienes un día en el que ambos obtienen 10.000 búsquedas más de lo normal, deberías considerar a París "más sexy" 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 compare "hotness" de Britney Spears y Paris Hilton. ¿Qué me has hecho?

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

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

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

Cuando se usa 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, la tendencia aumenta anormalmente, mientras que si es altamente negativo, está cayendo 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 que aumenten más anormalmente.

Consulte Wikipedia para obtener más información acerca de los puntajes 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

Muestra de salida

>>> 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 utilizar este método con una ventana deslizante (es decir, los últimos 30 días) si no desea tener en cuenta mucho historial, lo que hará que las tendencias a corto plazo sean más pronunciadas y puede reducir el tiempo de procesamiento.
También puede usar un puntaje 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 la 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 actualizarlos y, por lo tanto, solo necesita mantenga estos valores para el historial, no para 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()
Usando este método, su flujo de trabajo sería el siguiente. Para cada tema, etiqueta o página, cree un campo de coma flotante para la cantidad 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 usando esos datos; de lo contrario, inicialice a cero. Al final de cada día, calcule el puntaje z usando el número de vistas del día en comparación con los datos históricos almacenados en los tres campos de la base de datos. Los temas, etiquetas o páginas con los puntajes X z más altos son sus X "tendencias más atractivas" 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 toman 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 el hallazgo 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 un puntaje de magnitud mayor que la observación ''9''. Para lograr esto, propongo un puntaje z de promedio flotante. Debe quedar claro que este método NO tiene la garantía de ser estadísticamente sólido, pero debe ser útil para encontrar tendencias o similar. La principal diferencia entre el puntaje z estándar y el puntaje z de 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 señaló correctamente David Kemp, si se le da una serie de valores constantes y luego se solicita un zscore para un valor observado que difiere de los otros valores, el resultado probablemente sea distinto de cero. De hecho, el valor devuelto debe ser infinito. Así que cambié esta línea,

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

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

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

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

La idea es hacer un seguimiento de esas cosas y observar cuando saltan significativamente en comparación con su propia línea de base.

Por lo tanto, para las 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 se trata de una nueva tendencia importante.

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

v2-v1/t or dv/dt

Podemos considerar que v1 es me gusta / votos iniciales / conteo de comentarios por hora y v2 es la "velocidad" actual por hora en las últimas 24 horas.

Esto es más como una pregunta que una respuesta, pero parece que puede funcionar. Cualquier contenido con la aceleración más alta será el tema de tendencia ...

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

Puede usar log-likelihood-ratios para comparar la fecha actual con el último mes o año. Esto es estadísticamente correcto (dado que sus eventos no se distribuyen normalmente, lo que se supone de su pregunta).

Solo ordena todos tus términos con logLR y elige los diez primeros.

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 de palabras desordenada. Para cada documento, crea una bolsa de términos. Simplemente cuente las ocurrencias de palabras. Luego, las occurrences del método devuelve el número de apariciones de una palabra dada, y el size del método devuelve el número total de palabras. Lo mejor es normalizar las palabras de alguna manera, por lo general, para toLowerCase es lo suficientemente bueno. Por supuesto, en los ejemplos anteriores crearía un documento con todas las consultas de hoy y otro con todas las consultas del año pasado.

Si simplemente mira los tweets o mensajes de estado para obtener sus temas, se encontrará con mucho ruido. Incluso si elimina todas las palabras de detención. Una forma de obtener un mejor subconjunto de candidatos de tema es centrarse únicamente en los 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é se trata la página. Además, compartir una página web generalmente se correlaciona con el intercambio de noticias que se están rompiendo (es decir, si una celebridad como Michael Jackson murió, vas a lograr que mucha gente comparta un artículo sobre su muerte).

He realizado experimentos en los que solo tomo palabras clave populares de 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, simplemente haga un orden simple de las frecuencias de palabra clave, y ya está a medio camino.

Típicamente, el "zumbido" se descifra utilizando algún tipo de mecanismo de descomposición exponencial / de registro. Para obtener una descripción general de cómo Hacker News, Reddit y otros manejan esto de una manera sencilla, consulte 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 de Google " Hot Trends ". Para eso, puedes dividir el valor actual por un valor histórico y luego restar los que están por debajo de algún umbral de ruido.

Trabajé en un proyecto en el que mi objetivo era encontrar temas clave de Live Twitter Stream y también realizar análisis sentimentales sobre los temas más populares (para saber si se hablaba de manera positiva / negativa del tema de tendencias). He usado Storm para manejar la transmisión de Twitter.

Publiqué mi informe en un 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 utilizado es un poco genérico, y en la sección de discusión mencioné cómo podemos ampliar el sistema para aplicaciones que no son de Twitter.

Espero que la información ayude.

probablemente funcionaría una simple gradiente de frecuencia de tema: gran gradiente positivo = creciendo rápidamente en popularidad.

la forma más fácil sería almacenar el número de búsquedas por día, de modo 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 solo aplique algún tipo de umbral para que los días en que el aumento fue> 50 se consideran "calientes". podrías hacer esto mucho más complicado si quisieras, también. en lugar de la diferencia absoluta, puede tomar la diferencia relativa de modo que pasar de 100 a 150 se considera caliente, pero de 1000 a 1050 no lo es. o un gradiente más complicado que toma en cuenta las tendencias en más de un día para otro.

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 un ritmo increíble.

Esta es la primera derivada de la línea de tendencia, y no es difícil incorporarla 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, cada punto de datos que surja sobre ese tema debe ser normalizado: reste su línea base y obtendrá TODOS sus temas cerca de 0, con picos arriba y debajo de la línea. En su lugar, puede querer dividir la señal por su magnitud de referencia, lo que acercará la señal a 1.0; esto no solo alinea todas las señales entre sí (normaliza la línea base), sino que también normaliza los picos. Un pico de britney va a tener magnitudes mayores que el pico de otra persona, pero eso no significa que debas prestarle atención: el pico puede ser muy pequeño en relación con su línea base.

Derivar

Una vez que hayas normalizado todo, averigua la pendiente de cada tema. Toma dos puntos consecutivos y mide la diferencia. Una diferencia positiva tiende a subir, una diferencia negativa tiende a la baja. Luego, puede comparar las diferencias normalizadas y descubrir qué temas están subiendo de popularidad en comparación con otros temas, con cada tema escalado apropiado para su propia ''normal'', que puede tener magnitudes de orden diferentes a otros temas.

Esto es realmente una primera pasada al problema. Existen técnicas más avanzadas que deberá usar (principalmente una combinación de las anteriores con otros algoritmos, ponderadas para satisfacer sus necesidades) pero deberían ser suficientes para comenzar.

En cuanto al artículo

El artículo trata sobre la tendencia del tema, pero no se trata de cómo calcular qué está caliente y qué no, sino 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 es sobre los desafíos que uno enfrenta al intentar tal tarea. Menciona el efecto Brittney, pero no habla de cómo superarlo.

Como Nixuz señala, esto también se conoce como Z o Standard Score .