Jaki jest najlepszy sposób obliczania popularnych tematów lub tagów?

Wiele stron oferuje statystyki takie jak „Najgorętsze tematy w ciągu ostatnich 24 godzin”. Na przykład Topix.com pokazuje to w sekcji „Trendy informacyjne”. Tam możesz zobaczyć tematy, które mają najszybciej rosnącą liczbę wzmianek.

Chcę też obliczyć taki „szum” dla tematu. Jak mogłem to zrobić? Algorytm powinien ważyć tematy, które zawsze są mniej popularne. Tematy, o których normalnie (prawie) nikt nie wspomina, powinny być najgorętsze.

Google oferuje „Gorące trendy”, topix.com pokazuje „Gorące tematy”, fav.or.it pokazuje „Trendy słów kluczowych” - wszystkie te usługi mają jedną wspólną cechę: pokazują tylko nadchodzące trendy, które są obecnie niezwykle gorące.

Terminy takie jak „Britney Spears”, „pogoda” lub „Paris Hilton” nie pojawią się na tych listach, ponieważ zawsze są gorące i częste. Artykuł nazywa to „problemem Britney Spears”.

Moje pytanie: jak możesz kodować algorytm lub użyć istniejącego, aby rozwiązać ten problem? Mając listę ze słowami kluczowymi wyszukanymi w ciągu ostatnich 24 godzin, algorytm powinien pokazać Ci 10 (na przykład) najgorętszych.

Wiem, że w powyższym artykule wymieniono jakiś algorytm. Próbowałem napisać kod w PHP, ale nie sądzę, że zadziała. Po prostu znajduje większość, prawda?

Mam nadzieję, że możesz mi pomóc (przykłady kodowania byłyby świetne).

Ten problem wymaga wyniku z-score lub standardowego, który weźmie pod uwagę średnią historyczną, jak wspomnieli inni ludzie, ale także standardowe odchylenie tych danych historycznych, co czyni ją bardziej niezawodną niż zwykłe stosowanie średniej.

W twoim przypadku wynik Z obliczany jest według następującego wzoru, w którym trendem będzie wskaźnik, taki jak liczba wyświetleń / dzień.

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

Gdy stosuje się wynik Z, im wyższy lub niższy wynik Z, tym bardziej nienormalny jest trend, więc na przykład, jeśli wynik Z jest bardzo pozytywny, to trend rośnie nienormalnie, a jeśli jest wysoce ujemny, to nienormalnie spada . Tak więc po obliczeniu wyniku Z dla wszystkich trendów kandydujących najwyższe 10 punktów Z odniesie się do najbardziej nienormalnie rosnących wyników Z.

Więcej informacji na temat wyników Z można znaleźć na Wikipedii .

Kod

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

Przykładowe dane wyjściowe

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

Notatki

• Możesz użyć tej metody z przesuwanym oknem (tj. Z ostatnich 30 dni), jeśli nie chcesz brać pod uwagę zbyt dużej historii, co sprawi, że trendy krótkoterminowe będą bardziej wyraźne i mogą skrócić czas przetwarzania.

• Możesz również użyć wyniku Z dla wartości takich jak zmiana wyświetleń z jednego dnia na następny dzień, aby zlokalizować nieprawidłowe wartości zwiększania / zmniejszania wyświetleń dziennie. To jest jak użycie nachylenia lub pochodnej wykresów na dzień.

• Jeśli śledzisz bieżącą wielkość populacji, bieżącą sumę populacji i bieżącą sumę x ^ 2 populacji, nie musisz ponownie obliczać tych wartości, tylko je aktualizować, a zatem musisz tylko zachowaj te wartości dla historii, nie dla każdej wartości danych. Poniższy kod to pokazuje.

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

• Dzięki tej metodzie przepływ pracy wyglądałby następująco. Dla każdego tematu, znacznika lub strony utwórz zmiennoprzecinkowe pole dla całkowitej liczby dni, sumy wyświetleń i sumy wyświetleń w bazie danych. Jeśli masz dane historyczne, zainicjuj te pola przy użyciu tych danych, w przeciwnym razie zainicjuj do zera. Na koniec każdego dnia oblicz wynik Z na podstawie liczby wyświetleń w danym dniu w porównaniu do danych historycznych przechowywanych w trzech polach bazy danych. Tematy, tagi lub strony z najwyższymi wynikami X-Z to Twoje „najgorętsze trendy” dnia. Na koniec zaktualizuj każde z 3 pól wartością dnia i powtórz proces jutro.

Nowy dodatek

Normalne wyniki Z, jak omówiono powyżej, nie uwzględniają kolejności danych, a zatem wynik Z dla obserwacji „1” lub „9” miałby taką samą wielkość w stosunku do sekwencji [1, 1, 1, 1 , 9, 9, 9, 9]. Oczywiście w celu znalezienia trendów najbardziej aktualne dane powinny mieć większą wagę niż starsze dane, dlatego chcemy, aby obserwacja „1” miała większy wynik jasności niż obserwacja „9”. Aby to osiągnąć, proponuję zmienną średnią z-score. Powinno być jasne, że ta metoda NIE jest gwarantowana pod względem statystycznym, ale powinna być użyteczna do znajdowania trendów lub podobnych. Główną różnicą między standardowym wynikiem Z i zmienną średnią oceną Z jest zastosowanie zmiennej ruchomej do obliczenia średniej wartości populacji i kwadratowej średniej wartości populacji. Szczegóły w kodzie:

Kod

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

Próbka 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

Aktualizacja

Jak słusznie zauważył David Kemp, jeśli otrzyma się ciąg stałych wartości, a następnie zscore dla obserwowanej wartości, która różni się od innych wartości, wynik powinien być prawdopodobnie niezerowy. W rzeczywistości zwracana wartość powinna być nieskończonością. Więc zmieniłem tę linię,

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

do:

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

Ta zmiana znajduje odzwierciedlenie w kodzie rozwiązania fazscore. Jeśli nie chcesz zajmować się nieskończonymi wartościami, akceptowalnym rozwiązaniem może być zmiana linii na:

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

Potrzebujesz algorytmu, który mierzy prędkość tematu - lub innymi słowy, jeśli go wykreślisz, chcesz pokazać te, które idą w niewiarygodnym tempie.

Jest to pierwsza pochodna linii trendu i nie jest trudna do włączenia jako ważonego czynnika w twoich ogólnych obliczeniach.

Normalizować

Jedną z technik, którą musisz wykonać, jest normalizacja wszystkich danych. Dla każdego śledzonego tematu utrzymuj filtr dolnoprzepustowy, który określa linię bazową tego tematu. Teraz każdy punkt danych, który pojawia się na ten temat, powinien zostać znormalizowany - odejmij jego linię bazową, a otrzymasz WSZYSTKIE swoje tematy w pobliżu 0, z pikami powyżej i poniżej linii. Zamiast tego możesz podzielić sygnał przez jego wartość bazową, co doprowadzi sygnał do około 1,0 - to nie tylko zrównuje wszystkie sygnały ze sobą (normalizuje linię bazową), ale także normalizuje skoki. Skok britney będzie większy od skoku kogoś innego, ale to nie znaczy, że powinieneś zwrócić na to uwagę - skok może być bardzo mały w stosunku do jej linii bazowej.

Czerpać

Gdy wszystko znormalizujesz, ustal nachylenie każdego tematu. Weź dwa kolejne punkty i zmierz różnicę. Dodatnia różnica rośnie w górę, ujemna różnica spada. Następnie możesz porównać znormalizowane różnice i dowiedzieć się, które tematy zwiększają popularność w porównaniu do innych tematów - z każdym tematem skalowanym odpowiednio do jego własnej „normalności”, która może być wielkości rzędu innej niż inne tematy.

To naprawdę pierwszy krok do rozwiązania problemu. Istnieją bardziej zaawansowane techniki, których będziesz potrzebować (głównie połączenie powyższych z innymi algorytmami, dostosowanymi do twoich potrzeb), ale powinno wystarczyć, aby zacząć.

Odnośnie artykułu

Artykuł dotyczy trendów w temacie, ale nie chodzi o to, jak obliczyć, co jest gorące, a co nie, chodzi o to, jak przetworzyć ogromną ilość informacji, które taki algorytm musi przetworzyć w miejscach takich jak Lycos i Google. Przestrzeń i czas wymagany do nadania każdemu tematowi licznika i znalezienia licznika każdego tematu, gdy trwa wyszukiwanie, jest ogromny. Ten artykuł dotyczy wyzwań, jakie stoją przed podjęciem takiego zadania. Wspomina o efekcie Brittneya, ale nie mówi o tym, jak go pokonać.

Jak zauważa Nixuz, jest to również określane jako Z lub Standard Score .

Chad Birch i Adam Davis mają rację, ponieważ trzeba będzie spojrzeć wstecz, aby ustalić linię bazową. Twoje pytanie, jak zostało sformułowane, sugeruje, że chcesz tylko przeglądać dane z ostatnich 24 godzin, a to nie całkiem latać.

Jednym ze sposobów na zapewnienie pamięci danych bez konieczności wyszukiwania dużej ilości danych historycznych jest zastosowanie wykładniczej średniej ruchomej. Zaletą tego jest to, że możesz aktualizować to raz na okres, a następnie wyczyścić wszystkie stare dane, więc musisz zapamiętać tylko jedną wartość. Więc jeśli twój okres to dzień, musisz zachować atrybut „średniej dziennej” dla każdego tematu, co możesz zrobić poprzez:

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

Gdzie a_nśrednia ruchoma na dzień n, b jest stałą stałą między 0 a 1 (im bliżej 1, tym dłuższa pamięć) i c_njest liczbą trafień w ciągu dnia n. Piękno polega na tym, że jeśli wykonasz tę aktualizację pod koniec dnia n, możesz spłukać c_ni a_(n-1).

Jedynym zastrzeżeniem jest to, że początkowo będzie wrażliwy na wszystko, co wybierzesz dla swojej początkowej wartości a.

EDYTOWAĆ

Jeśli to pomaga wizualizować to podejście, brać n = 5, a_0 = 1i b = .9.

Powiedzmy, że nowe wartości to 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

Czy to nie wygląda na przeciętne? Zwróć uwagę, jak wartość pozostała blisko 1, mimo że naszym następnym wejściem było 5. Co się dzieje? Jeśli rozszerzysz matematykę, co otrzymasz:

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

Co mam na myśli przez pozostałą wagę? Cóż, w każdym uśrednieniu, wszystkie ciężary muszą dodać się do 1. Gdyby n było nieskończonością, a ... mogłoby trwać wiecznie, to wszystkie ciężary sumowałyby się do 1. Ale jeśli n jest względnie małe, pozostawia się dobrą ilość masy na oryginalnym wejściu.

Jeśli przestudiujesz powyższą formułę, powinieneś zdać sobie sprawę z kilku rzeczy na temat tego użycia:

1. Wszystkie dane przyczyniają się coś do średniej na zawsze. Praktycznie rzecz biorąc, jest taki moment, w którym wkład jest naprawdę bardzo niewielki.
2. Najnowsze wartości wnoszą więcej niż starsze wartości.
3. Im wyższa wartość b, tym mniej ważne są nowe wartości i dłuższe stare wartości mają znaczenie. Jednak im wyższa wartość b, tym więcej danych potrzebujesz, aby zmniejszyć początkową wartość a.

Myślę, że dwie pierwsze cechy są dokładnie tym, czego szukasz. Aby dać ci wyobrażenie o prostocie, możesz to zaimplementować, oto implementacja python (minus cała interakcja z bazą danych):

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

Zazwyczaj „brzęczenie” jest określane za pomocą jakiejś formy mechanizmu rozkładu wykładniczego / logarytmicznego. Aby zapoznać się z tym, jak Hacker News, Reddit i inni radzą sobie z tym w prosty sposób, zobacz ten post .

Nie dotyczy to w pełni rzeczy, które są zawsze popularne. To, czego szukasz, wydaje się być czymś w rodzaju „ gorących trendów ” Google . W tym celu można podzielić bieżącą wartość przez wartość historyczną, a następnie odjąć te, które są poniżej pewnego progu hałasu.

Myślę, że kluczowym słowem, które należy zauważyć, jest „nienormalnie”. Aby ustalić, kiedy coś jest „nienormalne”, musisz wiedzieć, co jest normalne. Oznacza to, że będziesz potrzebować danych historycznych, które możesz uśrednić, aby znaleźć normalną stawkę dla konkretnego zapytania. Możesz wykluczyć nieprawidłowe dni z obliczeń uśredniania, ale znowu będzie to wymagało posiadania wystarczającej ilości danych, abyś wiedział, które dni należy wykluczyć.

Stamtąd będziesz musiał ustawić próg (jestem pewien, że wymagałoby to eksperymentów), a jeśli coś wykroczy poza próg, powiedz o 50% więcej wyszukiwań niż normalnie, możesz uznać to za „trend”. Lub, jeśli chcesz znaleźć „Top X najmodniejszych”, jak wspomniałeś, musisz tylko uporządkować rzeczy według odległości (procentowej) od ich normalnej stawki.

Załóżmy na przykład, że z twoich danych historycznych wynika, że ​​Britney Spears zwykle uzyskuje 100 000 wyszukiwań, a Paris Hilton zwykle 50 000. Jeśli masz dzień, w którym oboje uzyskują 10 000 więcej wyszukiwań niż normalnie, powinieneś rozważyć Paryż „gorętszy” niż Britney, ponieważ jej wyszukiwania wzrosły o 20% więcej niż normalnie, podczas gdy Britney było tylko 10%.

Boże, nie mogę uwierzyć, że właśnie napisałem akapit porównujący „upał” Britney Spears i Paris Hilton. Co mi zrobiłeś?

Zastanawiałem się, czy w takim przypadku można w ogóle zastosować zwykłą formułę przyspieszenia fizyki?

v2-v1/t or dv/dt

Możemy uznać v1 za początkowe polubienia / głosy / liczbę komentarzy na godzinę, a v2 za bieżącą „prędkość” na godzinę w ciągu ostatnich 24 godzin?

To bardziej przypomina pytanie niż odpowiedź, ale wydaje się, że może po prostu działać. Najpopularniejsze będą treści o najwyższym przyspieszeniu ...

Jestem pewien, że to może nie rozwiązać problemu Britney Spears :-)

prawdopodobnie zadziałałby prosty gradient częstotliwości tematów - duży gradient dodatni = szybko rosnąca popularność.

najłatwiejszym sposobem jest zbieranie liczby wyszukiwań każdego dnia, więc masz coś takiego

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

a następnie dowiedz się, jak bardzo zmieniło się z dnia na dzień:

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

i po prostu zastosuj jakiś próg, aby dni, w których wzrost był> 50, były uważane za „gorące”. możesz to jeszcze bardziej skomplikować, jeśli chcesz. zamiast bezwzględnej różnicy możesz wziąć różnicę względną, tak że przejście od 100 do 150 jest uważane za gorące, ale od 1000 do 1050 nie. lub bardziej skomplikowany gradient, który uwzględnia trendy w ciągu więcej niż jednego dnia.

Pracowałem nad projektem, w którym moim celem było znalezienie popularnych tematów z Live Twitter Stream, a także przeprowadzenie analizy sentymentalnej na temat popularnych trendów (ustalenie, czy temat ten był pozytywny / negatywny). Użyłem Storm do obsługi strumienia Twittera.

Mój raport opublikowałem jako blog: http://sayrohan.blogspot.com/2013/06/finding-trending-topics-and-trending.html

Do rankingu wykorzystałem Total Count i Z-Score.

Podejście, które zastosowałem, jest nieco ogólne, aw sekcji dyskusji wspomniałem, w jaki sposób możemy rozszerzyć system dla aplikacji innych niż Twitter.

Mam nadzieję, że informacje pomogą.

Jeśli po prostu spojrzysz na tweety lub komunikaty o stanie, aby uzyskać dostęp do swoich tematów, napotkasz dużo hałasu. Nawet jeśli usuniesz wszystkie słowa stop. Jednym ze sposobów uzyskania lepszego podzbioru kandydatów do tematu jest skupienie się tylko na tweetach / wiadomościach, które mają wspólny adres URL, i uzyskanie słów kluczowych z tytułu tych stron internetowych. I upewnij się, że stosujesz tagowanie POS, aby uzyskać także rzeczowniki i wyrażenia rzeczownikowe.

Tytuły stron internetowych są zazwyczaj bardziej opisowe i zawierają słowa opisujące treść strony. Ponadto udostępnianie strony internetowej jest zwykle skorelowane z dzieleniem się nowymi wiadomościami (np. Jeśli umrze celebrytka taka jak Michael Jackson, wielu ludzi udostępni artykuł na temat jego śmierci).

Przeprowadziłem eksperymenty, w których pobieram tylko popularne słowa kluczowe z tytułów, a następnie uzyskuję całkowitą liczbę tych słów kluczowych we wszystkich komunikatach o stanie i zdecydowanie usuwają dużo hałasu. Jeśli zrobisz to w ten sposób, nie potrzebujesz skomplikowanego algorytmu, po prostu zrób proste uporządkowanie częstotliwości słów kluczowych i jesteś w połowie drogi.

Możesz użyć współczynników wiarygodności do porównania bieżącej daty z ostatnim miesiącem lub rokiem. Jest to poprawne statystycznie (biorąc pod uwagę, że wydarzenia nie są normalnie dystrybuowane, co należy założyć na podstawie pytania).

Po prostu posortuj wszystkie warunki według logLR i wybierz pierwszą dziesiątkę.

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, TermBag to nieuporządkowany zbiór słów. Dla każdego dokumentu tworzysz jedną torbę terminów. Po prostu policz wystąpienia słów. Następnie metoda occurrenceszwraca liczbę wystąpień danego słowa, a metoda sizezwraca całkowitą liczbę słów. Najlepiej jakoś znormalizować słowa, zwykle toLowerCasewystarcza. Oczywiście w powyższych przykładach utworzyłbyś jeden dokument ze wszystkimi zapytaniami z dnia dzisiejszego i jeden ze wszystkimi zapytaniami z ostatniego roku.

Chodzi o to, aby śledzić takie rzeczy i zauważać, kiedy skaczą znacznie w porównaniu z własną linią bazową.

Tak więc, w przypadku zapytań, które mają więcej niż pewien próg, należy śledzić każde, a gdy zmienia się ono na pewną wartość (powiedzmy prawie dwukrotnie) swojej wartości historycznej, jest to nowy gorący trend.