Qual é a melhor maneira de calcular tópicos ou tags de tendências?

Muitos sites oferecem algumas estatísticas como "Os tópicos mais quentes nas últimas 24h". Por exemplo, o Topix.com mostra isso em sua seção "Tendências de notícias". Lá, você pode ver os tópicos que têm o número de menções que mais cresce.

Também quero calcular esse "burburinho" para um tópico. Como eu pude fazer isso? O algoritmo deve ponderar os tópicos que estão sempre menos quentes. Os tópicos que normalmente (quase) ninguém menciona devem ser os mais quentes.

O Google oferece "Hot Trends", topix.com mostra "Hot Topics", fav.or.it mostra "Keyword Trends" - todos esses serviços têm uma coisa em comum: eles mostram apenas as próximas tendências que estão anormalmente quentes no momento.

Termos como "Britney Spears", "clima" ou "Paris Hilton" não aparecerão nessas listas porque são sempre quentes e frequentes. Este artigo chama isso de "O problema de Britney Spears".

Minha pergunta: como você pode codificar um algoritmo ou usar um existente para resolver esse problema? Tendo uma lista com as palavras-chave pesquisadas nas últimas 24 horas, o algoritmo deve mostrar as 10 (por exemplo) mais populares.

Eu sei, no artigo acima, há algum tipo de algoritmo mencionado. Eu tentei codificá-lo em PHP, mas não acho que funcione. Apenas encontra a maioria, não acha?

Espero que você possa me ajudar (exemplos de codificação seriam ótimos).

Esse problema exige uma pontuação z ou pontuação padrão, que levará em consideração a média histórica, como outras pessoas mencionaram, mas também o desvio padrão desses dados históricos, tornando-o mais robusto do que apenas usando a média.

No seu caso, um escore z é calculado pela fórmula a seguir, onde a tendência seria uma taxa como visualizações / dia.

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

Quando um escore z é usado, quanto maior ou menor o escore z, mais anormal é a tendência; por exemplo, se o escore z é altamente positivo, a tendência aumenta anormalmente, enquanto se é altamente negativo, diminui anormalmente. . Portanto, depois de calcular o escore z para todas as tendências candidatas, os 10 escores z mais altos se relacionam com os escores z que aumentam anormalmente.

Por favor, consulte a Wikipedia para obter mais informações sobre z-scores.

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

Saída de amostra

>>> 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

• Você pode usar esse método com uma janela deslizante (ou seja, nos últimos 30 dias) se não levar muito em consideração o histórico, o que tornará as tendências de curto prazo mais acentuadas e reduzirá o tempo de processamento.

• Você também pode usar um z-score para valores como alteração de visualizações de um dia para o dia seguinte para localizar os valores anormais de aumento / diminuição de visualizações por dia. É como usar a inclinação ou a derivada das visualizações por dia.

• Se você acompanhar o tamanho atual da população, o total atual da população e o total atual de x ^ 2 da população, não precisará recalcular esses valores, apenas atualizá-los e, portanto, precisará apenas mantenha esses valores para o histórico, não cada valor de dados. O código a seguir demonstra isso.

  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 esse método, seu fluxo de trabalho seria o seguinte. Para cada tópico, tag ou página, crie um campo de ponto flutuante, para o número total de dias, soma de visualizações e soma de visualizações ao quadrado no banco de dados. Se você tiver dados históricos, inicialize esses campos usando esses dados; caso contrário, inicialize com zero. No final de cada dia, calcule a pontuação z usando o número de visualizações do dia em relação aos dados históricos armazenados nos três campos do banco de dados. Os tópicos, tags ou páginas com as maiores pontuações z de X são as suas "tendências mais quentes" do dia. Por fim, atualize cada um dos 3 campos com o valor do dia e repita o processo amanhã.

Nova adição

Os escores z normais, conforme discutido acima, não levam em consideração a ordem dos dados e, portanto, o escore z para uma observação de '1' ou '9' teria a mesma magnitude em relação à sequência [1, 1, 1, 1 9, 9, 9, 9]. Obviamente, para encontrar tendências, os dados mais atuais devem ter mais peso que os dados mais antigos e, portanto, queremos que a observação '1' tenha uma pontuação de magnitude maior que a observação '9'. Para isso, proponho um escore z médio flutuante. Deve ficar claro que esse método NÃO é estatisticamente correto, mas deve ser útil para encontrar tendências ou algo semelhante. A principal diferença entre o escore z padrão e o escore z médio flutuante é o uso de uma média flutuante para calcular o valor médio da população e o valor médio da população ao quadrado. Consulte o código para obter detalhes:

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()

IO de amostra

>>> 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

Atualizar

Como David Kemp apontou corretamente, se for fornecida uma série de valores constantes e, em seguida, for solicitado um zscore para um valor observado diferente dos outros valores, o resultado provavelmente deve ser diferente de zero. De fato, o valor retornado deve ser infinito. Então eu mudei essa linha,

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

para:

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

Essa alteração é refletida no código da solução fazscore. Se alguém não quiser lidar com valores infinitos, uma solução aceitável seria alterar a linha para:

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

Você precisa de um algoritmo que mede a velocidade de um tópico - ou, em outras palavras, se você o representar graficamente, deseja mostrar aqueles que estão subindo a um ritmo incrível.

Essa é a primeira derivada da linha de tendência e não é difícil incorporar como um fator ponderado do seu cálculo geral.

Normalizar

Uma técnica que você precisará fazer é normalizar todos os seus dados. Para cada tópico que você está seguindo, mantenha um filtro de passagem muito baixa que defina a linha de base desse tópico. Agora todos os pontos de dados que aparecem sobre esse tópico devem ser normalizados - subtraia sua linha de base e você terá TODOS os seus tópicos perto de 0, com picos acima e abaixo da linha. Em vez disso, você pode dividir o sinal pela magnitude da linha de base, o que trará o sinal para cerca de 1,0 - isso não apenas alinha todos os sinais entre si (normaliza a linha de base), mas também normaliza os picos. Um pico de britney será magnitudes maiores que o de outra pessoa, mas isso não significa que você deva prestar atenção a ele - o pico pode ser muito pequeno em relação à linha de base.

Derivar

Depois de normalizar tudo, descubra a inclinação de cada tópico. Tome dois pontos consecutivos e meça a diferença. Uma diferença positiva está tendendo para cima, uma diferença negativa está tendendo para baixo. Em seguida, você pode comparar as diferenças normalizadas e descobrir quais tópicos estão aumentando em popularidade em comparação com outros tópicos - com cada tópico dimensionado de acordo com seu próprio 'normal', que pode ter magnitudes de ordem diferentes de outros tópicos.

Esta é realmente uma primeira passagem para o problema. Existem técnicas mais avançadas que você precisará usar (principalmente uma combinação das opções acima com outros algoritmos, ponderadas para atender às suas necessidades), mas isso deve ser suficiente para você começar.

Em relação ao artigo

O artigo é sobre tendências de tópicos, mas não é sobre como calcular o que é interessante e o que não é, é sobre como processar a enorme quantidade de informações que esse algoritmo deve processar em locais como Lycos e Google. O espaço e o tempo necessários para atribuir um contador a cada tópico e encontrar o contador de cada tópico quando uma pesquisa é enorme. Este artigo é sobre os desafios que se enfrenta ao tentar essa tarefa. Ele menciona o efeito Brittney, mas não fala sobre como superá-lo.

Como Nixuz aponta, isso também é chamado de Z ou Pontuação padrão .

Chad Birch e Adam Davis estão certos, pois você precisará olhar para trás para estabelecer uma linha de base. Sua pergunta, conforme formulada, sugere que você deseja visualizar apenas os dados das últimas 24 horas e isso não será suficiente.

Uma maneira de fornecer aos seus dados alguma memória sem precisar consultar um grande corpo de dados históricos é usar uma média móvel exponencial. A vantagem disso é que você pode atualizá-lo uma vez por período e liberar todos os dados antigos, portanto, é necessário lembrar apenas de um único valor. Portanto, se seu período é um dia, você deve manter um atributo "média diária" para cada tópico, o que pode ser feito por:

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

Onde a_nestá a média móvel a partir do dia n, b é uma constante entre 0 e 1 (quanto mais próximo de 1, maior a memória) ec_n é o número de ocorrências no dia n. A beleza é que, se você executar essa atualização no final do dia n, poderá liberar c_ne a_(n-1).

A única ressalva é que ela será inicialmente sensível ao que você escolher como valor inicial a.

EDITAR

Se ajudar a visualizar essa abordagem, faça n = 5,a_0 = 1 e b = .9.

Digamos que os novos valores sejam 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

Não parece muito com uma média, parece? Observe como o valor ficou próximo de 1, mesmo que nossa próxima entrada tenha sido 5. O que está acontecendo? Se você expandir a matemática, o que você obtém é:

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

O que quero dizer com sobra de peso? Bem, em qualquer média, todos os pesos devem adicionar a 1. Se n fosse infinito e o ... pudesse durar para sempre, todos os pesos seriam somados a 1. Mas se n for relativamente pequeno, você terá uma boa quantidade de peso restante na entrada original.

Se você estuda a fórmula acima, deve entender algumas coisas sobre esse uso:

1. Todos os dados contribui algo à média para sempre. Na prática, há um ponto em que a contribuição é muito, muito pequena.
2. Valores recentes contribuem mais que valores antigos.
3. Quanto mais alto b, menos importantes são os novos valores e mais antigos são os valores antigos. No entanto, quanto maior b, mais dados você precisa para diluir o valor inicial de a.

Eu acho que as duas primeiras características são exatamente o que você está procurando. Para lhe dar uma idéia simples de implementar, aqui está uma implementação em python (menos toda a interação com o banco de dados):

>>> 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

Normalmente, o "buzz" é descoberto usando alguma forma de mecanismo de decaimento exponencial / de log. Para uma visão geral de como o Hacker News, Reddit e outros lidam com isso de uma maneira simples, consulte este post .

Isso não aborda completamente as coisas que sempre são populares. O que você procura parece ser algo como o recurso " Hot Trends " do Google . Para isso, você pode dividir o valor atual por um valor histórico e subtrair os que estiverem abaixo de algum limite de ruído.

Eu acho que a palavra-chave que você precisa notar é "anormalmente". Para determinar quando algo é "anormal", você precisa saber o que é normal. Ou seja, você precisará de dados históricos, que podem ser calculados em média para descobrir a taxa normal de uma consulta específica. Convém excluir dias anormais do cálculo da média, mas novamente será necessário ter dados suficientes, para que você saiba quais dias excluir.

A partir daí, você terá que definir um limite (o que exigiria experimentação, tenho certeza) e, se algo ultrapassar o limite, digitar 50% mais pesquisas do que o normal, você poderá considerá-lo uma "tendência". Ou, se você quiser encontrar o "Top X Trendiest" como você mencionou, basta solicitar as coisas pela distância (percentual) em que elas estão da sua taxa normal.

Por exemplo, digamos que seus dados históricos informam que Britney Spears geralmente recebe 100.000 pesquisas e Paris Hilton geralmente recebe 50.000. Se você tem um dia em que os dois recebem 10.000 pesquisas a mais do que o normal, considere Paris "mais quente" que Britney, porque as pesquisas dela aumentaram 20% a mais do que o normal, enquanto as de Britney foram apenas 10%.

Deus, eu não acredito que acabei de escrever um parágrafo comparando "gostosuras" de Britney Spears e Paris Hilton. O que você fez comigo?

Eu queria saber se é possível usar a fórmula regular de aceleração física nesse caso?

v2-v1/t or dv/dt

Podemos considerar v1 como curtidas / votos / contagem de comentários iniciais por hora e v2 como "velocidade" atual por hora nas últimas 24 horas?

Isso é mais uma pergunta do que uma resposta, mas parece que pode funcionar. Qualquer conteúdo com maior aceleração será o tópico de tendência ...

Estou certo de que isso pode não resolver o problema de Britney Spears :-)

provavelmente um simples gradiente de frequência de tópicos funcionaria - grande gradiente positivo = crescendo rapidamente em popularidade.

a maneira mais fácil seria separar o número de pesquisas por dia, para que você tenha algo como

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

e descubra o quanto isso mudou de dia para dia:

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

e apenas aplique algum tipo de limite para que os dias em que o aumento fosse> 50 sejam considerados "quentes". você pode tornar isso muito mais complicado se você também quiser. em vez da diferença absoluta, você pode fazer a diferença relativa para que ir de 100 a 150 seja considerado quente, mas 1000 a 1050 não. ou um gradiente mais complicado que leva em consideração as tendências de mais de um dia para o outro.

Eu havia trabalhado em um projeto, onde meu objetivo era encontrar os Tópicos de Tendências do Live Twitter Stream e também fazer análises sentimentais sobre os tópicos de tendências (descobrir se o Tópico de Tendências falava de maneira positiva / negativa). Eu usei o Storm para lidar com o fluxo do twitter.

Publiquei meu relatório como um blog: http://sayrohan.blogspot.com/2013/06/finding-trending-topics-and-trending.html

Eu usei Total Count e Z-Score para o ranking.

A abordagem que usei é um pouco genérica e, na seção de discussão, mencionei que como podemos estender o sistema para aplicativos que não são do Twitter.

Espero que a informação ajude.

Se você simplesmente olhar tweets ou mensagens de status para obter seus tópicos, encontrará muito barulho. Mesmo se você remover todas as palavras de parada. Uma maneira de obter um subconjunto melhor de candidatos a tópicos é focar apenas nos tweets / mensagens que compartilham um URL e obter as palavras-chave no título dessas páginas da web. E certifique-se de aplicar a marcação POS para obter substantivos + frases substantivas também.

Os títulos das páginas da web geralmente são mais descritivos e contêm palavras que descrevem o que é a página. Além disso, o compartilhamento de uma página da web geralmente está correlacionado com o compartilhamento de notícias que estão surgindo (por exemplo, se uma celebridade como Michael Jackson morreu, muitas pessoas compartilharão um artigo sobre a morte dele).

Fiz experimentos em que apenas tomo palavras-chave populares de títulos e, em seguida, obtenho a contagem total dessas palavras-chave em todas as mensagens de status, e elas definitivamente removem muito ruído. Se você fizer isso dessa maneira, não precisará de um algoritmo complexo, basta fazer um pedido simples das frequências das palavras-chave e estará no meio do caminho.

Você pode usar proporções de probabilidade de log para comparar a data atual com o último mês ou ano. Isso é estatisticamente correto (considerando que seus eventos não são normalmente distribuídos, o que deve ser assumido em sua pergunta).

Basta classificar todos os seus termos por logLR e escolher os dez primeiros.

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));
}

PS, um TermBag é uma coleção desordenada de palavras. Para cada documento, você cria um pacote de termos. Apenas conte as ocorrências de palavras. Em seguida, o método occurrencesretorna o número de ocorrências de uma determinada palavra e o método sizeretorna o número total de palavras. É melhor normalizar as palavras de alguma forma, normalmente toLowerCaseé bom o suficiente. Obviamente, nos exemplos acima, você criaria um documento com todas as consultas de hoje e um com todas as consultas do ano passado.

A idéia é acompanhar essas coisas e perceber quando elas saltam significativamente em comparação com sua própria linha de base.

Portanto, para consultas com mais de um limite de limite, acompanhe cada uma delas e, quando ela mudar para algum valor (digamos quase o dobro) do seu valor histórico, será uma nova tendência quente.