Quelle est la meilleure façon de calculer des sujets ou des tags tendance?

De nombreux sites proposent des statistiques comme "Les sujets les plus chauds des dernières 24h". Par exemple, Topix.com le montre dans sa section "News Trends". Là, vous pouvez voir les sujets qui ont le plus grand nombre de mentions.

Je veux aussi calculer un tel "buzz" pour un sujet. Comment pourrais-je faire ça? L'algorithme doit pondérer les sujets qui sont toujours moins chauds. Les sujets qui normalement (presque) personne ne mentionne devraient être les plus chauds.

Google propose "Hot Trends", topix.com montre "Hot Topics", fav.or.it montre "Keyword Trends" - tous ces services ont une chose en commun: ils ne vous montrent que les tendances à venir qui sont anormalement chaudes pour le moment.

Des termes tels que «Britney Spears», «météo» ou «Paris Hilton» n'apparaîtront pas dans ces listes car ils sont toujours chauds et fréquents. Cet article appelle cela «le problème de Britney Spears».

Ma question: comment coder un algorithme ou utiliser un algorithme existant pour résoudre ce problème? Ayant une liste avec les mots-clés recherchés dans les dernières 24h, l'algorithme devrait vous montrer les 10 (par exemple) les plus chauds.

Je sais, dans l'article ci-dessus, il y a une sorte d'algorithme mentionné. J'ai essayé de le coder en PHP mais je ne pense pas que cela fonctionnera. Il trouve juste la majorité, n'est-ce pas?

J'espère que vous pourrez m'aider (des exemples de codage seraient formidables).

Ce problème appelle un z-score ou score standard, qui prendra en compte la moyenne historique, comme d'autres l'ont mentionné, mais aussi l'écart type de ces données historiques, ce qui les rend plus robustes que la simple utilisation de la moyenne.

Dans votre cas, un z-score est calculé par la formule suivante, où la tendance serait un taux tel que vues / jour.

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

Lorsqu'un z-score est utilisé, plus le z-score est élevé ou bas, plus la tendance est anormale.Par exemple, si le z-score est très positif, la tendance augmente anormalement, tandis que si elle est très négative, elle diminue anormalement . Ainsi, une fois que vous calculez le z-score pour toutes les tendances candidates, les 10 z-scores les plus élevés seront liés aux z-scores les plus anormalement croissants.

Veuillez consulter Wikipedia pour plus d'informations sur les scores z.

Code

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

Exemple de sortie

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

Remarques

• Vous pouvez utiliser cette méthode avec une fenêtre glissante (c'est-à-dire les 30 derniers jours) si vous souhaitez ne pas prendre trop d'historique en compte, ce qui rendra les tendances à court terme plus prononcées et réduira le temps de traitement.

• Vous pouvez également utiliser un score z pour des valeurs telles que la modification des vues d'un jour au lendemain pour localiser les valeurs anormales pour augmenter / diminuer les vues par jour. C'est comme utiliser la pente ou la dérivée du graphique des vues par jour.

• Si vous gardez une trace de la taille actuelle de la population, du total actuel de la population et du total actuel de x ^ 2 de la population, vous n'avez pas besoin de recalculer ces valeurs, uniquement de les mettre à jour et il vous suffit donc de conservez ces valeurs pour l'historique, pas pour chaque valeur de données. Le code suivant illustre cela.

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

• En utilisant cette méthode, votre flux de travail serait le suivant. Pour chaque sujet, balise ou page, créez un champ à virgule flottante, pour le nombre total de jours, la somme des vues et la somme des vues au carré dans votre base de données. Si vous avez des données historiques, initialisez ces champs à l'aide de ces données, sinon initialisez à zéro. À la fin de chaque journée, calculez le score z en utilisant le nombre de vues de la journée par rapport aux données historiques stockées dans les trois champs de la base de données. Les sujets, balises ou pages avec les scores X les plus élevés sont vos X "tendances les plus chaudes" de la journée. Enfin, mettez à jour chacun des 3 champs avec la valeur du jour et répétez le processus demain.

Nouvel ajout

Les scores z normaux comme discuté ci-dessus ne prennent pas en compte l'ordre des données et par conséquent le score z pour une observation de «1» ou «9» aurait la même grandeur par rapport à la séquence [1, 1, 1, 1 , 9, 9, 9, 9]. Évidemment, pour la recherche de tendances, les données les plus récentes devraient avoir plus de poids que les données plus anciennes et, par conséquent, nous voulons que l'observation «1» ait un score de magnitude plus grand que l'observation «9». Pour y parvenir, je propose un score z moyen flottant. Il devrait être clair que cette méthode n'est PAS garantie d'être statistiquement valable, mais devrait être utile pour la recherche de tendances ou similaire. La principale différence entre le z-score standard et le z-score moyen flottant est l'utilisation d'une moyenne flottante pour calculer la valeur moyenne de la population et la valeur moyenne de la population au carré. Voir le code pour plus de détails:

Code

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

Exemple d'E / S

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

Mettre à jour

Comme David Kemp l'a correctement souligné, si une série de valeurs constantes est donnée, puis un zscore pour une valeur observée qui diffère des autres valeurs est demandé, le résultat devrait probablement être différent de zéro. En fait, la valeur renvoyée doit être l'infini. Alors j'ai changé cette ligne,

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

à:

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

Cette modification est reflétée dans le code de la solution fazscore. Si l'on ne veut pas traiter des valeurs infinies, une solution acceptable pourrait être de changer la ligne à la place:

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

Vous avez besoin d'un algorithme qui mesure la vitesse d'un sujet - ou en d'autres termes, si vous le représentez graphiquement, vous voulez montrer ceux qui augmentent à un rythme incroyable.

Il s'agit de la première dérivée de la ligne de tendance et il n'est pas difficile à intégrer comme facteur pondéré de votre calcul global.

Normaliser

Une technique que vous devrez faire est de normaliser toutes vos données. Pour chaque sujet que vous suivez, conservez un filtre passe-bas qui définit la ligne de base de ce sujet. Désormais, chaque point de données sur ce sujet doit être normalisé - soustrayez sa ligne de base et vous obtiendrez TOUS vos sujets proches de 0, avec des pics au-dessus et en dessous de la ligne. Vous pouvez plutôt diviser le signal par sa magnitude de ligne de base, ce qui ramènera le signal à environ 1,0 - cela non seulement alignera tous les signaux les uns avec les autres (normalise la ligne de base), mais normalise également les pointes. Un pic britney sera d'une magnitude plus grande que le pic de quelqu'un d'autre, mais cela ne signifie pas que vous devriez y prêter attention - le pic peut être très petit par rapport à sa ligne de base.

Dériver

Une fois que vous avez tout normalisé, déterminez la pente de chaque sujet. Prenez deux points consécutifs et mesurez la différence. Une différence positive tend à augmenter, une différence négative tend à diminuer. Ensuite, vous pouvez comparer les différences normalisées et découvrir quels sujets gagnent en popularité par rapport à d'autres sujets - chaque sujet étant mis à l'échelle en fonction de sa propre `` normale '', qui peut être d'un ordre différent des autres sujets.

C'est vraiment un premier passage au problème. Il existe des techniques plus avancées que vous devrez utiliser (principalement une combinaison de ce qui précède avec d'autres algorithmes, pondérées en fonction de vos besoins), mais cela devrait suffire pour vous aider à démarrer.

Concernant l'article

L'article porte sur les tendances des sujets, mais il ne s'agit pas de savoir comment calculer ce qui est chaud et ce qui ne l'est pas, mais comment traiter l'énorme quantité d'informations qu'un tel algorithme doit traiter dans des endroits comme Lycos et Google. L'espace et le temps nécessaires pour donner à chaque sujet un compteur et trouver le compteur de chaque sujet lorsqu'une recherche est effectuée sont énormes. Cet article traite des défis auxquels on est confronté lors de la tentative d'une telle tâche. Il mentionne l'effet Brittney, mais ne parle pas de la façon de le surmonter.

Comme le souligne Nixuz, cela est également appelé un score Z ou standard .

Chad Birch et Adam Davis ont raison en ce sens que vous devrez regarder en arrière pour établir une base de référence. Votre question, telle qu'elle est formulée, suggère que vous ne voulez afficher que les données des dernières 24 heures, et cela ne fonctionnera pas vraiment.

Une façon de donner de la mémoire à vos données sans avoir à interroger un grand nombre de données historiques consiste à utiliser une moyenne mobile exponentielle. L'avantage est que vous pouvez le mettre à jour une fois par période, puis vider toutes les anciennes données, vous n'avez donc besoin de vous souvenir que d'une seule valeur. Donc, si vos règles sont d'un jour, vous devez maintenir un attribut «moyenne quotidienne» pour chaque sujet, ce que vous pouvez faire en:

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

Où a_nest la moyenne mobile à partir du jour n, b est une constante entre 0 et 1 (le plus proche de 1, plus la mémoire c_nest longue) et est le nombre de hits le jour n. La beauté est que si vous effectuez cette mise à jour à la fin de la journée n, vous pouvez rincer c_neta_(n-1) .

La seule mise en garde est qu'il sera initialement sensible à tout ce que vous choisissez pour votre valeur initiale de a .

ÉDITER

Si elle aide à visualiser cette approche, prendre n = 5, a_0 = 1etb = .9 .

Disons que les nouvelles valeurs sont 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

Cela ne ressemble pas beaucoup à une moyenne, n'est-ce pas? Notez comment la valeur est restée proche de 1, même si notre entrée suivante était 5. Que se passe-t-il? Si vous développez les calculs, ce que vous obtenez:

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

Qu'est-ce que j'entends par poids résiduel? Eh bien, dans n'importe quelle moyenne, tous les poids doivent s'additionner à 1. Si n était l'infini et que ... pouvait durer indéfiniment, alors tous les poids se résumeraient à 1. Mais si n est relativement petit, il vous reste une bonne quantité de poids sur l'entrée d'origine.

Si vous étudiez la formule ci-dessus, vous devriez réaliser quelques choses à propos de cet usage:

1. Toutes les données contribuent pour toujours quelque chose à la moyenne. En pratique, il y a un point où la contribution est vraiment, vraiment minime.
2. Les valeurs récentes contribuent plus que les anciennes valeurs.
3. Plus b est élevé, moins les nouvelles valeurs sont importantes et les anciennes valeurs plus longues comptent. Cependant, plus b est élevé, plus vous avez besoin de données pour diluer la valeur initiale de a.

Je pense que les deux premières caractéristiques correspondent exactement à ce que vous recherchez. Pour vous donner une idée simple, cela peut être à implémenter, voici une implémentation python (moins toute l'interaction de la base de données):

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

Typiquement, le "buzz" est compris en utilisant une forme de mécanisme de décroissance exponentielle / log. Pour un aperçu de la façon dont Hacker News, Reddit et d'autres gèrent cela de manière simple, consultez cet article .

Cela ne répond pas pleinement aux choses qui sont toujours populaires. Ce que vous recherchez semble être quelque chose comme la fonctionnalité " Hot Trends " de Google . Pour cela, vous pouvez diviser la valeur actuelle par une valeur historique, puis soustraire celles qui sont en dessous d'un certain seuil de bruit.

Je pense que le mot clé que vous devez remarquer est «anormalement». Afin de déterminer quand quelque chose est "anormal", vous devez savoir ce qui est normal. Autrement dit, vous allez avoir besoin de données historiques, que vous pouvez calculer en moyenne pour connaître le taux normal d'une requête particulière. Vous voudrez peut-être exclure les jours anormaux du calcul de la moyenne, mais encore une fois, cela nécessitera d'avoir déjà suffisamment de données, afin que vous sachiez quels jours exclure.

À partir de là, vous devrez définir un seuil (ce qui nécessiterait une expérimentation, j'en suis sûr), et si quelque chose dépasse le seuil, disons 50% de recherches en plus que la normale, vous pouvez le considérer comme une "tendance". Ou, si vous voulez être en mesure de trouver le "Top X Trendiest" comme vous l'avez mentionné, il vous suffit de classer les choses en fonction de leur distance (en pourcentage) par rapport à leur taux normal.

Par exemple, supposons que vos données historiques vous indiquent que Britney Spears obtient généralement 100 000 recherches et que Paris Hilton en obtient généralement 50 000. Si vous avez une journée où ils obtiennent tous les deux 10 000 recherches de plus que la normale, vous devriez considérer Paris "plus chaud" que Britney, car ses recherches ont augmenté de 20% de plus que la normale, alors que celles de Britney n'étaient que de 10%.

Dieu, je ne peux pas croire que je viens d'écrire un paragraphe comparant "la chaleur" de Britney Spears et Paris Hilton. Qu'est-ce que tu m'as fait?

Je me demandais s'il est possible d'utiliser une formule d'accélération physique régulière dans un tel cas?

v2-v1/t or dv/dt

Nous pouvons considérer v1 comme étant les likes initiaux / votes / nombre de commentaires par heure et v2 comme étant la "vitesse" actuelle par heure au cours des dernières 24 heures?

Cela ressemble plus à une question qu'à une réponse, mais il semble que cela puisse fonctionner. Tout contenu avec une accélération la plus élevée sera le sujet tendance ...

Je suis sûr que cela ne résoudra peut-être pas le problème de Britney Spears :-)

probablement un simple gradient de fréquence des sujets fonctionnerait - grand gradient positif = popularité croissante.

le moyen le plus simple serait de classer le nombre de recherches chaque jour, donc vous avez quelque chose comme

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

puis découvrez à quel point cela a changé de jour en jour:

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

et appliquez simplement une sorte de seuil pour que les jours où l'augmentation était> 50 soient considérés comme «chauds». vous pouvez aussi rendre cela beaucoup plus compliqué si vous le souhaitez. plutôt que la différence absolue, vous pouvez prendre la différence relative de sorte que passer de 100 à 150 est considéré comme chaud, mais 1000 à 1050 ne le sont pas. ou un gradient plus compliqué qui prend en compte les tendances sur plus d'un jour sur l'autre.

J'avais travaillé sur un projet, où mon objectif était de trouver des sujets tendance à partir de Live Twitter Stream et de faire également une analyse sentimentale sur les sujets tendance (trouver si le sujet tendance parlait positivement / négativement). J'ai utilisé Storm pour gérer le flux Twitter.

J'ai publié mon rapport sous forme de blog: http://sayrohan.blogspot.com/2013/06/finding-trending-topics-and-trending.html

J'ai utilisé Total Count et Z-Score pour le classement.

L'approche que j'ai utilisée est un peu générique, et dans la section de discussion, j'ai mentionné comment nous pouvons étendre le système pour les applications non Twitter.

J'espère que l'information vous aidera.

Si vous regardez simplement des tweets ou des messages de statut pour obtenir vos sujets, vous allez rencontrer beaucoup de bruit. Même si vous supprimez tous les mots vides. Une façon d'obtenir un meilleur sous-ensemble de sujets candidats est de se concentrer uniquement sur les tweets / messages qui partagent une URL et d'obtenir les mots-clés à partir du titre de ces pages Web. Et assurez-vous d'appliquer le balisage POS pour obtenir également des noms + des phrases nominales.

Les titres des pages Web sont généralement plus descriptifs et contiennent des mots qui décrivent le sujet de la page. De plus, le partage d'une page Web est généralement corrélé avec le partage de nouvelles qui se brisent (c'est-à-dire que si une célébrité comme Michael Jackson est décédée, vous allez avoir beaucoup de gens partageant un article sur sa mort).

J'ai mené des expériences dans lesquelles je ne prends que les mots-clés populaires des titres, ET j'obtiens ensuite le nombre total de ces mots-clés dans tous les messages d'état, et ils suppriment définitivement beaucoup de bruit. Si vous le faites de cette façon, vous n'avez pas besoin d'un algorithme complexe, faites simplement un ordre simple des fréquences des mots clés, et vous êtes à mi-chemin.

Vous pouvez utiliser des rapports de vraisemblance logarithmique pour comparer la date actuelle avec le dernier mois ou année. Ceci est statistiquement valable (étant donné que vos événements ne sont pas normalement distribués, ce qui doit être supposé à partir de votre question).

Triez simplement tous vos termes par logLR et choisissez les dix premiers.

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, un TermBag est une collection de mots non ordonnée. Pour chaque document, vous créez un ensemble de termes. Comptez simplement les occurrences de mots. Ensuite, la méthode occurrencesrenvoie le nombre d'occurrences d'un mot donné et la méthode sizerenvoie le nombre total de mots. Il est préférable de normaliser les mots d'une manière ou d'une autre, c'est généralement toLowerCasesuffisant. Bien sûr, dans les exemples ci-dessus, vous créeriez un document avec toutes les requêtes d'aujourd'hui et un avec toutes les requêtes de l'année dernière.

L'idée est de garder une trace de ces choses et de remarquer quand elles sautent de manière significative par rapport à leur propre base de référence.

Ainsi, pour les requêtes qui ont plus d'un certain seuil, suivez chacune d'elles et lorsqu'elle passe à une valeur (disons presque le double) de sa valeur historique, il s'agit d'une nouvelle tendance à chaud.