Quelle est la meilleure façon de calculer les sujets ou les tags tendances ?

Question

De nombreux sites proposent des statistiques telles que "Les sujets les plus chauds des dernières 24 heures". Par exemple, Topix.com le montre dans sa section "Tendances de l'actualité". Vous pouvez y voir les sujets dont le nombre de mentions augmente le plus rapidement.

Je souhaite également calculer un tel "buzz" pour un sujet. Comment puis-je le faire ? L'algorithme devrait pondérer moins les sujets qui sont toujours chauds. Les sujets que normalement (presque) personne ne mentionne devraient être les plus chauds.

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

Des termes comme "Britney Spears", "météo" ou "Paris Hilton" n'apparaîtront pas dans ces listes car ils sont toujours d'actualité et fréquents. Cet article appelle cela "le problème Britney Spears".

Ma question : Comment coder un algorithme ou utiliser un algorithme existant pour résoudre ce problème ? En 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 que, dans l'article ci-dessus, il est question d'une sorte d'algorithme. J'ai essayé de le coder en PHP mais je ne pense pas que ça va marcher. Il trouve juste la majorité, n'est-ce pas ?

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

Answer 1

Ce problème nécessite un score z ou un score standard, qui prendra en compte la moyenne historique, comme d'autres personnes l'ont mentionné, mais aussi l'écart type de ces données historiques, ce qui le rend plus robuste 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 les 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 faible, plus la tendance est anormale. Par exemple, si le z-score est très positif, la tendance est anormalement ascendante, tandis que s'il est très négatif, elle est anormalement descendante. Ainsi, une fois que vous aurez calculé le z-score de 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 z-scores.

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

Notes

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

• Vous pouvez également utiliser un z-score pour des valeurs telles que le changement de vues d'un jour à l'autre pour localiser les valeurs anormales d'augmentation/diminution des vues par jour. Cela revient à utiliser la pente ou la dérivée du graphique des vues par jour.

• Si vous gardez la 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, seulement de les mettre à jour et donc vous n'avez besoin de garder ces valeurs que pour l'historique, pas chaque valeur de données. Le code suivant en fait la démonstration.

    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, étiquette 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 disposez de données historiques, initialisez ces champs en utilisant ces données, sinon initialisez-les à 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, les tags ou les pages présentant les X z-scores les plus élevés sont vos X "tendances les plus chaudes" du jour. Enfin, mettez à jour chacun des trois champs avec la valeur du jour et répétez le processus le jour suivant.

Nouvel ajout

Les z-scores normaux, comme nous l'avons vu plus haut, ne tiennent pas compte de l'ordre des données et, par conséquent, le z-score pour une observation de '1' ou de '9' aurait la même magnitude par rapport à la séquence [1, 1, 1, 1, 9, 9, 9, 9]. Il est évident que pour la recherche de tendances, les données les plus récentes devraient avoir plus de poids que les données plus anciennes et nous voulons donc que l'observation '1' ait un score de magnitude plus élevé que l'observation '9'. Pour y parvenir, je propose un z-score moyen flottant. Il convient de préciser que cette méthode n'est PAS garantie comme étant statistiquement valable, mais qu'elle devrait être utile pour la recherche de tendances ou autres. 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 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

Mise à jour

Comme David Kemp l'a fait remarquer à juste titre, si l'on donne une série de valeurs constantes et que l'on demande ensuite un zscore pour une valeur observée qui diffère des autres valeurs, le résultat devrait probablement être différent de zéro. En fait, la valeur renvoyée devrait être l'infini. J'ai donc modifié cette ligne,

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

à :

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

Ce changement est reflété dans le code de la solution fazscore. Si l'on ne veut pas traiter les valeurs infinies, une solution acceptable pourrait être de remplacer la ligne par :

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

Answer 2

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

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

Normaliser

L'une des techniques que vous devrez utiliser est de normaliser toutes vos données. Pour chaque sujet que vous suivez, gardez un filtre passe-bas qui définit la ligne de base de ce sujet. Maintenant, chaque point de données qui arrive 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 au-dessous de la ligne. Il est préférable de diviser le signal par sa magnitude de base, ce qui amènera le signal à environ 1,0 - cela permet non seulement d'aligner tous les signaux entre eux (normalisation de la base), mais aussi de normaliser les pics. Un pic de Britney sera plus grand que le pic de quelqu'un d'autre, mais cela ne signifie pas que vous devez 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 est une tendance à la hausse, une différence négative est une tendance à la baisse. Vous pouvez ensuite comparer les différences normalisées et découvrir les sujets qui 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 de grandeur différent de celui des autres sujets.

Il s'agit vraiment d'une première approche du problème. Il existe des techniques plus avancées que vous devrez utiliser (la plupart du temps, il s'agit d'une combinaison de ce qui précède avec d'autres algorithmes, pondérés en fonction de vos besoins), mais cela devrait être suffisant pour vous permettre de 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, il s'agit de savoir 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 attribuer un compteur à chaque sujet, et retrouver le compteur de chaque sujet lorsqu'une recherche sur celui-ci est lancée, sont énormes. Cet article traite des défis auxquels on est confronté lorsqu'on tente d'accomplir une telle tâche. Il mentionne l'effet Brittney, mais ne dit rien sur la façon de le surmonter.

Comme Nixuz souligne On parle également de Z ou de Score standard .

Answer 3

Chad Birch et Adam Davis ont raison de dire qu'il faut regarder en arrière pour établir une base de référence. Votre question, telle qu'elle est formulée, suggère que vous souhaitez uniquement visualiser les données des dernières 24 heures, ce qui n'est pas le cas.

Une façon de donner de la mémoire à vos données sans avoir à demander un grand nombre de données historiques est d'utiliser un fichier de type moyenne mobile exponentielle. L'avantage de cette méthode est que vous pouvez la mettre à jour une fois par période, puis vider toutes les anciennes données, de sorte que vous ne devez vous souvenir que d'une seule valeur. Ainsi, si votre période est d'un jour, vous devez gérer un attribut "moyenne quotidienne" pour chaque sujet, ce que vous pouvez faire de la manière suivante :

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

Où a_n est la moyenne mobile à partir du jour n b est une constante comprise entre 0 et 1 (plus on se rapproche de 1, plus la mémoire est longue) et c_n est le nombre d'occurrences le jour n . La beauté de la chose est que si vous effectuez cette mise à jour à la fin de la journée n vous pouvez tirer la chasse c_n y a_(n-1) .

La seule réserve est qu'il sera initialement sensible à ce que vous choisissez comme valeur initiale de a .

EDITAR

Si cela vous aide à visualiser cette approche, prenez n = 5 , a_0 = 1 y b = .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

Ça ne ressemble pas vraiment à une moyenne, n'est-ce pas ? Notez comment la valeur est restée proche de 1, même si notre prochaine entrée était 5. Que se passe-t-il ? Si vous développez les maths, 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 je veux dire par "poids restant" ? Eh bien, dans toute moyenne, la somme de tous les poids doit être égale à 1. Si n était infini et que le ... pouvait continuer indéfiniment, alors la somme de tous les poids serait égale à 1. Mais si n est relativement petit, il reste une bonne quantité de poids sur l'entrée originale.

Si vous étudiez la formule ci-dessus, vous devriez vous rendre compte de certaines choses concernant cet usage :

1. Toutes les données contribuent quelque chose à la moyenne pour toujours. En pratique, il y a un point où la contribution est vraiment, vraiment faible.
2. Les valeurs récentes contribuent davantage que les valeurs plus anciennes.
3. Plus b est élevé, moins les nouvelles valeurs sont importantes et plus les anciennes valeurs 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 sont exactement ce que vous recherchez. Pour vous donner une idée de la simplicité de la mise en œuvre, voici une implémentation en python (sans toute l'interaction avec 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

Answer 4

Généralement, le "buzz" est calculé à l'aide d'une forme de mécanisme de décroissance exponentielle/log. Pour une vue d'ensemble de la façon dont Hacker News, Reddit et d'autres gèrent cela de manière simple, voir ce poste .

Cela n'aborde pas complètement les choses qui sont toujours populaires. Ce que vous recherchez semble être quelque chose comme le " Tendances chaudes La fonction " ". Pour cela, vous pourriez diviser la valeur actuelle par une valeur historique, puis soustraire celles qui sont inférieures à un certain seuil de bruit.

Answer 5

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. En d'autres termes, vous allez avoir besoin de données historiques, que vous pouvez moyennées pour trouver le taux normal d'une requête particulière. Vous pouvez exclure les jours anormaux du calcul de la moyenne, mais là encore, vous devez disposer de suffisamment de données pour savoir quels jours exclure.

À partir de là, vous devrez fixer un seuil (ce qui nécessitera une expérimentation, j'en suis sûr), et si quelque chose sort de ce seuil, par exemple 50 % de recherches de plus que la normale, vous pourrez le considérer comme une "tendance". Ou, si vous voulez être en mesure de trouver le "Top X des tendances" comme vous l'avez mentionné, vous devez simplement classer les choses en fonction de l'écart (en pourcentage) qu'elles présentent par rapport à leur taux normal.

Par exemple, disons que vos données historiques vous indiquent que Britney Spears obtient généralement 100 000 recherches, et Paris Hilton 50 000. Si, un jour, elles obtiennent toutes deux 10 000 recherches de plus que la normale, vous devriez considérer que Paris est plus "chaude" que Britney, car ses recherches ont augmenté de 20 % par rapport à la normale, alors que celles de Britney n'ont augmenté que de 10 %.

Mon Dieu, je n'arrive pas à croire que je viens d'écrire un paragraphe comparant les "hotesses" de Britney Spears et Paris Hilton. Qu'est-ce que tu m'as fait ?