Was ist der beste Weg, um Trendthemen oder Tags zu berechnen?

182

Viele Websites bieten Statistiken wie "Die heißesten Themen der letzten 24 Stunden". Zum Beispiel zeigt Topix.com dies in seinem Abschnitt "News Trends". Dort sehen Sie die Themen mit der am schnellsten wachsenden Anzahl von Erwähnungen.

Ich möchte einen solchen "Buzz" auch für ein Thema berechnen. Wie könnte ich das machen? Der Algorithmus sollte die Themen gewichten, die immer weniger heiß sind. Die Themen, die normalerweise (fast) niemand erwähnt, sollten die heißesten sein.

Google bietet "Hot Trends" an, topix.com zeigt "Hot Topics", fav.or.it zeigt "Keyword Trends" - all diese Dienste haben eines gemeinsam: Sie zeigen Ihnen nur kommende Trends, die momentan ungewöhnlich heiß sind.

Begriffe wie "Britney Spears", "Wetter" oder "Paris Hilton" werden in diesen Listen nicht angezeigt, da sie immer heiß und häufig sind. Dieser Artikel nennt dies "The Britney Spears Problem".

Meine Frage: Wie können Sie einen Algorithmus codieren oder einen vorhandenen verwenden, um dieses Problem zu lösen? Wenn Sie eine Liste mit den Schlüsselwörtern haben, die in den letzten 24 Stunden gesucht wurden, sollte der Algorithmus Ihnen die 10 (zum Beispiel) heißesten anzeigen.

Ich weiß, dass im obigen Artikel eine Art Algorithmus erwähnt wird. Ich habe versucht, es in PHP zu codieren, aber ich glaube nicht, dass es funktionieren wird. Es findet nur die Mehrheit, nicht wahr?

Ich hoffe, Sie können mir helfen (Codierungsbeispiele wären großartig).

krächzen
quelle
3
Interessante Frage, neugierig zu sehen, was die Leute zu sagen haben.
mmcdole
14
Kein Grund zu schließen, dies ist eine gültige Frage
TStamper
1
Das ist genau die gleiche Frage und das sagt er sogar! Warum stimmen die Leute dafür?
Darryl Hein
3
Ich bin ein wenig verwirrt darüber, nach welcher Art von Ergebnis Sie suchen. Der Artikel scheint darauf hinzudeuten, dass "Britney Spears" konsistent in der "Hot" -Liste gefunden wird, weil so viele Leute nach diesem Begriff suchen, aber Ihre Frage besagt, dass er NICHT in der Liste erscheint, weil die Anzahl der Suchvorgänge nach diesem Begriff dies tut im Laufe der Zeit nicht viel zunehmen (sie bleiben hoch, aber stabil). Welches Ergebnis versuchen Sie zu erreichen? Sollte "Britney Spears" hoch oder niedrig rangieren?
e.James
1
@eJames, "Britney Spears" sollte keinen hohen Rang haben, da sie durchweg ein hoher Suchbegriff ist und er nach Suchbegriffen mit hoher Geschwindigkeit sucht.
mmcdole

Antworten:

102

Dieses Problem erfordert einen Z-Score oder Standard-Score, der den historischen Durchschnitt berücksichtigt, wie andere bereits erwähnt haben, aber auch die Standardabweichung dieser historischen Daten, wodurch sie robuster sind als nur die Verwendung des Durchschnitts.

In Ihrem Fall wird ein Z-Score nach der folgenden Formel berechnet, wobei der Trend eine Rate wie Ansichten / Tag ist.

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

Wenn ein Z-Score verwendet wird, ist der Trend umso abnormaler, je höher oder niedriger der Z-Score ist. Wenn beispielsweise der Z-Score hoch positiv ist, steigt der Trend abnormal an, während er ungewöhnlich stark fällt, wenn er stark negativ ist . Sobald Sie den Z-Score für alle Kandidatentrends berechnet haben, beziehen sich die höchsten 10 Z-Scores auf die ungewöhnlich ansteigenden Z-Scores.

Weitere Informationen zu Z-Scores finden Sie in Wikipedia .

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

Beispielausgabe

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

Anmerkungen

  • Sie können diese Methode mit einem Schiebefenster (dh den letzten 30 Tagen) verwenden, wenn Sie nicht zu viel Verlauf berücksichtigen möchten, wodurch kurzfristige Trends deutlicher werden und die Verarbeitungszeit verkürzt werden kann.

  • Sie können auch einen Z-Score für Werte wie die Änderung der Ansichten von einem Tag zum nächsten Tag verwenden, um die abnormalen Werte für das Erhöhen / Verringern der Ansichten pro Tag zu ermitteln. Dies entspricht der Verwendung der Steigung oder Ableitung der Ansichten pro Tag.

  • Wenn Sie die aktuelle Bevölkerungsgröße, die aktuelle Gesamtbevölkerung und die aktuelle Gesamtgröße von x ^ 2 der Bevölkerung verfolgen, müssen Sie diese Werte nicht neu berechnen, sondern nur aktualisieren und müssen daher nur Behalten Sie diese Werte für den Verlauf bei, nicht für jeden Datenwert. Der folgende Code demonstriert dies.

    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()
    
  • Mit dieser Methode würde Ihr Arbeitsablauf wie folgt aussehen. Erstellen Sie für jedes Thema, Tag oder jede Seite ein Gleitkommafeld für die Gesamtzahl der Tage, die Summe der Ansichten und die Summe der Ansichten in Ihrer Datenbank. Wenn Sie historische Daten haben, initialisieren Sie diese Felder mit diesen Daten, andernfalls initialisieren Sie sie auf Null. Berechnen Sie am Ende eines jeden Tages den Z-Score anhand der Anzahl der Aufrufe des Tages anhand der in den drei Datenbankfeldern gespeicherten historischen Daten. Die Themen, Tags oder Seiten mit den höchsten X Z-Scores sind Ihre X "heißesten Trends" des Tages. Aktualisieren Sie abschließend jedes der 3 Felder mit dem Tageswert und wiederholen Sie den Vorgang morgen.

Neuer Zusatz

Normale Z-Scores, wie oben diskutiert, berücksichtigen nicht die Reihenfolge der Daten, und daher hätte der Z-Score für eine Beobachtung von '1' oder '9' gegenüber der Sequenz die gleiche Größe [1, 1, 1, 1 9, 9, 9, 9]. Offensichtlich sollten für die Trenderkennung die aktuellsten Daten mehr Gewicht haben als ältere Daten, und daher möchten wir, dass die '1'-Beobachtung eine größere Größenbewertung als die' 9'-Beobachtung hat. Um dies zu erreichen, schlage ich einen gleitenden durchschnittlichen Z-Score vor. Es sollte klar sein, dass diese Methode NICHT garantiert statistisch fundiert ist, sondern für die Trenderkennung oder ähnliches nützlich sein sollte. Der Hauptunterschied zwischen dem Standard-Z-Score und dem gleitenden Durchschnitt des Z-Scores besteht in der Verwendung eines gleitenden Durchschnitts zur Berechnung des durchschnittlichen Bevölkerungswerts und des durchschnittlichen quadratischen Bevölkerungswerts. Siehe Code für Details:

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

Beispiel 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

Aktualisieren

Wie David Kemp richtig hervorhob, sollte das Ergebnis wahrscheinlich ungleich Null sein, wenn eine Reihe konstanter Werte und dann ein Z-Wert für einen beobachteten Wert angegeben werden, der sich von den anderen Werten unterscheidet. Tatsächlich sollte der zurückgegebene Wert unendlich sein. Also habe ich diese Zeile geändert,

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

zu:

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

Diese Änderung spiegelt sich im Code der Fazscore-Lösung wider. Wenn man sich nicht mit unendlichen Werten befassen möchte, könnte eine akzeptable Lösung darin bestehen, stattdessen die Zeile zu ändern in:

if self.std() == 0: return obs - self.avg
Nixuz
quelle
1
Nein, Ihr Code hat einen kleinen Fehler in der folgenden Zeile. $ z_score = $ Hits_Today - ($ Average_hits_per_day / $ Standard_Deviation); Es sollte sein: $ z_score = ($ Hits_today- $ Average_hits_per_day) / $ Standard_Deviation; Beachten Sie die Änderung in Klammern.
Nixuz
1
@nixuz - fehlt mir etwas: fazscore (0.8, map (lambda x: 40, range (0.200))). score (1) == 0 (für beliebige Werte)?
kͩeͣmͮpͥ 17
1
@Nixus - Ich dachte, ich könnte diesen aus dem Grab ausgraben. Könnten Sie die PHP-Implementierung erneut veröffentlichen? Die pasteLinks scheinen nicht zu funktionieren ... danke!
Drewness
1
Für alle, die es möchten, habe ich jetzt SQL-Abfragen, um dies zu tun.
Thouliha
1
Der Zerfall hier ist kontraintuitiv; Wenn Sie 2 Werte eingeben würden, z. B. [10, 20] mit einem Abfall von 0,8, beträgt der AVG 10 * 0,8 + 20 * 0,2 = 12. Sie würden einen Wert über 15 erwarten, da 20 bei Zerfall mehr Gewicht als 10 haben sollte. Es gibt eine viel bessere Alternative, die einen gewichteten Durchschnitt in numpy.average verwendet, bei dem Sie eine parallele Liste mit Gewichten erstellen. Zum Beispiel: Daten = Bereich (10, 30, 10) Zerfall = 0,8 Zerfallsgewichte = [Zerfall ** a für einen In-Bereich (len (Daten), 0, -1)] print np.average (Daten, Gewichte = Zerfallsgewichte)
Jeroen
93

Sie benötigen einen Algorithmus, der die Geschwindigkeit eines Themas misst - oder mit anderen Worten, wenn Sie es grafisch darstellen, möchten Sie diejenigen anzeigen, die mit einer unglaublichen Geschwindigkeit steigen.

Dies ist die erste Ableitung der Trendlinie, und es ist nicht schwierig, sie als gewichteten Faktor in Ihre Gesamtberechnung einzubeziehen.

Normalisieren

Eine Technik, die Sie ausführen müssen, besteht darin, alle Ihre Daten zu normalisieren. Behalten Sie für jedes Thema, dem Sie folgen, einen Tiefpassfilter bei, der die Grundlinie dieses Themas definiert. Jetzt sollte jeder Datenpunkt, der zu diesem Thema eingeht, normalisiert werden. Subtrahieren Sie die Grundlinie, und Sie erhalten ALLE Ihre Themen in der Nähe von 0 mit Spitzen über und unter der Linie. Möglicherweise möchten Sie das Signal stattdessen durch seine Grundliniengröße teilen, wodurch das Signal auf etwa 1,0 gebracht wird. Dadurch werden nicht nur alle Signale miteinander in Einklang gebracht (normalisiert die Grundlinie), sondern auch die Spitzen normalisiert. Ein Britney-Spike wird größer sein als der Spike eines anderen, aber das bedeutet nicht, dass Sie darauf achten sollten - der Spike kann im Verhältnis zu ihrer Grundlinie sehr klein sein.

Ableiten

Wenn Sie alles normalisiert haben, ermitteln Sie die Steigung jedes Themas. Nehmen Sie zwei aufeinanderfolgende Punkte und messen Sie die Differenz. Ein positiver Unterschied ist im Aufwärtstrend, ein negativer Unterschied im Abwärtstrend. Anschließend können Sie die normalisierten Unterschiede vergleichen und herausfinden, welche Themen im Vergleich zu anderen Themen immer beliebter werden. Jedes Thema ist entsprechend seiner eigenen „Normalität“ skaliert, wobei sich die Größenordnungen möglicherweise von anderen Themen unterscheiden.

Dies ist wirklich ein erster Durchgang bei dem Problem. Es gibt fortgeschrittenere Techniken, die Sie verwenden müssen (meistens eine Kombination der oben genannten mit anderen Algorithmen, gewichtet nach Ihren Anforderungen), aber es sollte ausreichen, um Ihnen den Einstieg zu erleichtern.

Zum Artikel

In dem Artikel geht es um Themen-Trends, aber es geht nicht darum, zu berechnen, was aktuell ist und was nicht, sondern darum, wie viele Informationen verarbeitet werden müssen, die ein solcher Algorithmus an Orten wie Lycos und Google verarbeiten muss. Der Raum und die Zeit, die erforderlich sind, um jedem Thema einen Zähler zu geben und den Zähler jedes Themas zu finden, wenn eine Suche durchgeführt wird, sind enorm. In diesem Artikel geht es um die Herausforderungen, denen man beim Versuch einer solchen Aufgabe gegenübersteht. Der Brittney-Effekt wird zwar erwähnt, es wird jedoch nicht darüber gesprochen, wie er überwunden werden kann.

Wie Nixuz betont, wird dies auch als Z- oder Standard-Score bezeichnet .

Adam Davis
quelle
1
Ich habe dies vor der Bearbeitung positiv bewertet und bin zurückgekommen und wollte es erneut verbessern!
Gute
Vielen Dank! Ich würde Pseudocode machen, aber ich habe momentan keine Zeit. Vielleicht später, oder vielleicht wird jemand anderes diese Konzepte nehmen und umsetzen ...
Adam Davis
Vielen Dank, Adam Davis! Wenn Nixuz wirklich dasselbe beschrieben hat, habe ich wahrscheinlich eine Lösung in PHP: paste.bradleygill.com/index.php?paste_id=9206 Glaubst du, dieser Code ist richtig?
Caw
Sollte es nicht eher eine Beschleunigung des Themas als eine Geschwindigkeit sein? Überprüfen Sie heraus die letzte Antwort
Sap
17

Chad Birch und Adam Davis haben insofern Recht, als Sie zurückblicken müssen, um eine Basislinie zu erstellen. Ihre Frage deutet darauf hin, dass Sie nur Daten der letzten 24 Stunden anzeigen möchten, und das wird nicht ganz funktionieren.

Eine Möglichkeit, Ihren Daten Speicherplatz zu geben, ohne nach einer großen Anzahl historischer Daten fragen zu müssen, ist die Verwendung eines exponentiellen gleitenden Durchschnitts. Dies hat den Vorteil, dass Sie dies einmal pro Periode aktualisieren und dann alle alten Daten löschen können, sodass Sie sich nur einen einzigen Wert merken müssen. Wenn Ihre Periode also ein Tag ist, müssen Sie für jedes Thema ein Attribut "Tagesdurchschnitt" beibehalten. Dies können Sie tun, indem Sie:

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

Wo a_nist der gleitende Durchschnitt ab Tag n, b ist eine Konstante zwischen 0 und 1 (je näher an 1, desto länger der Speicher) und c_nist die Anzahl der Treffer am Tag n. Das Schöne ist, wenn Sie dieses Update am Ende des Tages durchführen n, können Sie spülen c_nund a_(n-1).

Die einzige Einschränkung ist, dass es anfangs empfindlich auf alles reagiert, was Sie für Ihren Anfangswert von auswählen a.

BEARBEITEN

Wenn es diesen Ansatz zu visualisieren hilft, nehmen n = 5, a_0 = 1und b = .9.

Angenommen, die neuen Werte sind 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

Sieht nicht sehr nach einem Durchschnitt aus, oder? Beachten Sie, wie der Wert nahe 1 blieb, obwohl unsere nächste Eingabe 5 war. Was ist los? Wenn Sie die Mathematik erweitern, was bekommen Sie das:

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

Was meine ich mit Restgewicht? Nun, in jedem Durchschnitt müssen sich alle Gewichte zu 1 addieren. Wenn n unendlich wäre und das ... für immer weitergehen könnte, würden sich alle Gewichte zu 1 summieren. Wenn n jedoch relativ klein ist, bleibt eine gute Menge an Gewicht übrig auf dem ursprünglichen Eingang.

Wenn Sie die obige Formel studieren, sollten Sie einige Dinge über diese Verwendung erkennen:

  1. Alle Daten tragen für immer etwas zum Durchschnitt bei. In der Praxis gibt es einen Punkt, an dem der Beitrag wirklich sehr, sehr gering ist.
  2. Aktuelle Werte tragen mehr dazu bei als ältere Werte.
  3. Je höher b ist, desto weniger wichtig sind neue Werte und desto länger sind alte Werte von Bedeutung. Je höher b ist, desto mehr Daten benötigen Sie jedoch, um den Anfangswert von a zu verwässern.

Ich denke, die ersten beiden Merkmale sind genau das, wonach Sie suchen. Um Ihnen eine Vorstellung davon zu geben, wie einfach dies sein kann, ist dies eine Python-Implementierung (abzüglich der gesamten Datenbankinteraktion):

>>> 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
David Berger
quelle
1
Dies ist auch als Infinite Impulse Response Filter (IIR) bekannt
Adam Davis
Hey, eine bessere Version meiner Antwort.
Joshua
@ Adam Wirklich? Ich kenne sie nicht. Ist es ein Sonderfall eines IIR? Die Artikel, die ich überfliege, scheinen keine Formeln zu enthalten, die sich im einfachen Fall auf einen exponentiellen gleitenden Durchschnitt reduzieren.
David Berger
Vielen Dank, David Berger! Wenn es funktioniert, wäre es eine großartige Ergänzung zu den anderen Antworten! Ich habe jedoch einige Fragen. Ich hoffe, Sie können sie beantworten: 1) Definiert der Faktor b, wie schnell die alten Daten abnehmen? 2) Wird dieser Ansatz im Vergleich zur einfachen Speicherung der alten Daten und zur Berechnung des Durchschnitts ungefähr gleichwertige Ergebnisse liefern? 3) Ist das deine Formel in Worten? $ durchschnittlicher_Wert = $ alter_Durchschnitt_Wert * $ Glättungsfaktor + $ Hits_Today * (1- $ Glättungsfaktor)
Caw
Die Punkte 1 und 3 sind korrekt. Siehe meine Bearbeitung für eine nuancierte Diskussion von 2.
David Berger
8

Typischerweise wird "Buzz" unter Verwendung eines Exponential- / Log-Zerfallsmechanismus herausgefunden. Eine Übersicht darüber, wie Hacker News, Reddit und andere auf einfache Weise damit umgehen, finden Sie in diesem Beitrag .

Dies spricht die Dinge, die immer beliebt sind, nicht vollständig an. Was Sie suchen, scheint so etwas wie Googles " Hot Trends " -Funktion zu sein. Dazu können Sie den aktuellen Wert durch einen historischen Wert teilen und dann diejenigen subtrahieren, die unterhalb einer Rauschschwelle liegen.

Jeff Moser
quelle
Ja, Google Hot Trends ist genau das, wonach ich suche. Was sollte der historische Wert sein? Der Durchschnittswert der letzten 7 Tage zum Beispiel?
Caw
1
Dies hängt davon ab, wie volatil Ihre Daten sind. Sie könnten mit einem 30-Tage-Durchschnitt beginnen. Wenn es sich um eine zyklische Angelegenheit handelt (z. B. Kentucky Derby), ist es möglicherweise sinnvoll, jährliche Vergleiche durchzuführen. Ich würde experimentieren und sehen, was in der Praxis am besten funktioniert.
Jeff Moser
7

Ich denke, das Schlüsselwort, das Sie beachten müssen, ist "abnormal". Um festzustellen, wann etwas "abnormal" ist, müssen Sie wissen, was normal ist. Das heißt, Sie benötigen historische Daten, die Sie mitteln können, um die normale Rate einer bestimmten Abfrage zu ermitteln. Möglicherweise möchten Sie abnormale Tage von der Durchschnittsberechnung ausschließen. Dafür müssen jedoch bereits genügend Daten vorhanden sein, damit Sie wissen, welche Tage ausgeschlossen werden müssen.

Von dort aus müssen Sie einen Schwellenwert festlegen (was sicherlich Experimente erfordern würde). Wenn etwas außerhalb des Schwellenwerts liegt, z. B. 50% mehr Suchanfragen als normal, können Sie dies als "Trend" betrachten. Oder wenn Sie in der Lage sein möchten, die "Top X Trendiest" zu finden, wie Sie es erwähnt haben, müssen Sie die Dinge nur danach bestellen, wie weit (prozentual) sie von ihrer normalen Rate entfernt sind.

Nehmen wir zum Beispiel an, Ihre historischen Daten haben Ihnen mitgeteilt, dass Britney Spears normalerweise 100.000 Suchanfragen und Paris Hilton normalerweise 50.000 Suchanfragen erhält. Wenn Sie einen Tag haben, an dem beide 10.000 Suchanfragen mehr als normal erhalten, sollten Sie Paris als "heißer" als Britney betrachten, da ihre Suchanfragen um 20% höher waren als normal, während die von Britney nur 10% waren.

Gott, ich kann nicht glauben, dass ich gerade einen Absatz geschrieben habe, in dem die "Schärfe" von Britney Spears und Paris Hilton verglichen wird. Was hast du mit mir gemacht?

Chad Birch
quelle
Danke, aber es wäre ein bisschen zu einfach, sie nur durch ihre schrittweise Erhöhung zu bestellen, nicht wahr?
Caw
7

Ich habe mich gefragt, ob es in einem solchen Fall überhaupt möglich ist, eine reguläre Physikbeschleunigungsformel zu verwenden.

v2-v1/t or dv/dt

Wir können v1 als anfängliche Likes / Stimmen / Anzahl der Kommentare pro Stunde und v2 als aktuelle "Geschwindigkeit" pro Stunde in den letzten 24 Stunden betrachten.

Dies ist eher eine Frage als eine Antwort, aber es scheint, als würde es einfach funktionieren. Jeder Inhalt mit der höchsten Beschleunigung wird das Trendthema sein ...

Ich bin sicher, dass dies das Problem von Britney Spears nicht lösen kann :-)

Saft
quelle
Es wird funktionieren, da es nur die Stimmenzunahme pro Zeit berechnet, und das ist es, was wir brauchen. Es könnte das "Britney Spears-Problem" teilweise lösen, da dieser Suchbegriff immer einen hohen Wert hat v1und einen sehr hohen v2Wert benötigt , um als "Trend" zu gelten. Es gibt jedoch wahrscheinlich bessere und ausgefeiltere Formeln und Algorithmen, um dies zu tun. Trotzdem ist es ein grundlegendes Arbeitsbeispiel.
Caw
In einem Kontext, in dem Sie immer etwas im "Trend" -Feed haben müssen, ist dies perfekt. So etwas wie eine Registerkarte "Durchsuchen", auf der Sie die derzeit besten auf der Plattform auflisten. Wenn Sie ein anderes Algo verwenden, wird möglicherweise eine leere Ergebnismenge angezeigt.
Kilianc
5

wahrscheinlich würde ein einfacher Gradient der Themenhäufigkeit funktionieren - großer positiver Gradient = schnell wachsende Popularität.

Der einfachste Weg wäre, die Anzahl der gesuchten Personen pro Tag zu speichern, damit Sie so etwas haben

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

und dann herausfinden, wie sehr es sich von Tag zu Tag verändert hat:

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

und wenden Sie einfach eine Art Schwellenwert an, damit Tage, an denen der Anstieg> 50 war, als "heiß" betrachtet werden. Sie könnten dies auch viel komplizierter machen, wenn Sie möchten. Anstelle des absoluten Unterschieds können Sie den relativen Unterschied so nehmen, dass ein Wechsel von 100 auf 150 als heiß angesehen wird, 1000 auf 1050 jedoch nicht. oder ein komplizierterer Gradient, der Trends über mehr als nur einen Tag zum nächsten berücksichtigt.

Autoplektisch
quelle
Danke dir. Aber ich weiß nicht genau, was ein Farbverlauf ist und wie ich damit arbeiten kann. Es tut uns leid!
Caw
Vielen Dank. Also muss ich einen Vektor erstellen, der die tägliche Häufigkeit enthält, oder? Die relativen Werte wären besser, da bin ich mir sicher. Beispiel: Ein Wachstum von 100 auf 110 ist nicht so gut wie ein Wachstum von 1 auf 9, würde ich sagen. Aber gibt es nicht eine Vektorfunktion, mit der ich die heißesten Themen finden kann? Es würde nicht ausreichen, nur die relativen Werte zu bewerten, oder? Ein Wachstum von 100 auf 200 (100%) ist nicht so gut wie ein Wachstum von 20.000 auf 39.000!?
Caw
Zu welcher Art von Website fügen Sie dies hinzu? Der Vorschlag von @ Autoplectic, die Änderung der Suchanfragen von Tag zu Tag zu zählen, lässt sich nicht gut für ein beliebtes Forum skalieren, in dem Sie Tausende von Themen haben und jeden Tag neue definiert werden.
Quantum7
Sie haben Recht, ich brauche einen Algorithmus für riesige Datenmengen, Tausende von Themen pro Stunde.
Caw
Das ist eine schlechte Strategie. Auf diese Weise ist eine Zunahme von 50 Suchanfragen nach Britney Spears so heiß wie +50 Suchanfragen nach einem neuen Referendum in Europa.
Iman Akbari
4

Ich hatte an einem Projekt gearbeitet, bei dem mein Ziel darin bestand, Trendthemen aus dem Live-Twitter-Stream zu finden und auch sentimentale Analysen zu den Trendthemen durchzuführen (herauszufinden, ob über Trendthemen positiv / negativ gesprochen wurde). Ich habe Storm für den Umgang mit Twitter-Streams verwendet.

Ich habe meinen Bericht als Blog veröffentlicht: http://sayrohan.blogspot.com/2013/06/finding-trending-topics-and-trending.html

Ich habe Total Count und Z-Score für das Ranking verwendet.

Der Ansatz, den ich verwendet habe, ist etwas allgemein gehalten, und im Diskussionsteil habe ich erwähnt, wie wir das System für Nicht-Twitter-Anwendungen erweitern können.

Hoffe die Informationen helfen.

Rohan Karwa
quelle
3

Wenn Sie sich einfach Tweets oder Statusmeldungen ansehen, um Ihre Themen zu erhalten, werden Sie auf viel Lärm stoßen. Auch wenn Sie alle Stoppwörter entfernen. Eine Möglichkeit, eine bessere Untergruppe von Themenkandidaten zu erhalten, besteht darin, sich nur auf Tweets / Nachrichten zu konzentrieren, die eine URL gemeinsam haben, und die Schlüsselwörter aus dem Titel dieser Webseiten abzurufen. Und stellen Sie sicher, dass Sie POS-Tagging anwenden, um auch Substantive + Nominalphrasen zu erhalten.

Titel von Webseiten sind normalerweise aussagekräftiger und enthalten Wörter, die beschreiben, worum es auf der Seite geht. Darüber hinaus ist das Teilen einer Webseite normalerweise mit dem Teilen aktueller Nachrichten verbunden (dh wenn eine Berühmtheit wie Michael Jackson gestorben ist, werden viele Leute einen Artikel über seinen Tod teilen).

Ich habe Experimente durchgeführt, bei denen ich nur beliebte Schlüsselwörter aus Titeln nehme UND dann die Gesamtzahl dieser Schlüsselwörter über alle Statusmeldungen hinweg erhalte, und sie entfernen definitiv viel Rauschen. Wenn Sie dies auf diese Weise tun, benötigen Sie keinen komplexen Algorithmus. Führen Sie einfach eine einfache Reihenfolge der Keyword-Häufigkeiten durch, und schon sind Sie auf halbem Weg.

Henley Chiu
quelle
2

Sie können Log-Likelihood-Verhältnisse verwenden, um das aktuelle Datum mit dem letzten Monat oder Jahr zu vergleichen. Dies ist statistisch fundiert (da Ihre Ereignisse nicht normal verteilt sind, was aus Ihrer Frage hervorgeht).

Sortieren Sie einfach alle Ihre Begriffe nach logLR und wählen Sie die Top Ten aus.

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, ein TermBag ist eine ungeordnete Sammlung von Wörtern. Für jedes Dokument erstellen Sie eine Tasche mit Begriffen. Zählen Sie einfach das Vorkommen von Wörtern. Dann gibt die Methode occurrencesdie Anzahl der Vorkommen eines bestimmten Wortes zurück, und die Methode sizegibt die Gesamtzahl der Wörter zurück. Es ist am besten, die Wörter irgendwie zu normalisieren, normalerweise toLowerCaseist es gut genug. In den obigen Beispielen würden Sie natürlich ein Dokument mit allen Abfragen von heute und eines mit allen Abfragen des letzten Jahres erstellen.

akuhn
quelle
Entschuldigung, ich verstehe den Code nicht. Was sind TermBags? Es wäre großartig, wenn Sie kurz erklären könnten, was dieser Code bewirkt.
Caw
1
Ein TermBag ist eine Tüte mit Begriffen, dh die Klasse sollte in der Lage sein, die Gesamtzahl der Wörter im Text und die Anzahl der Vorkommen für jedes Wort zu beantworten.
Akuhn
0

Die Idee ist, solche Dinge im Auge zu behalten und zu bemerken, wenn sie im Vergleich zu ihrer eigenen Basislinie signifikant springen.

Verfolgen Sie also bei Abfragen, die mehr als einen bestimmten Schwellenwert haben, jeden einzelnen. Wenn sich der historische Wert auf einen Wert (z. B. fast das Doppelte) ändert, handelt es sich um einen neuen Trend.

Joshua
quelle