Что лучший способ состоит в том, чтобы вычислить актуальные темы или теги?

, вероятно, сработал бы простой градиент частоты тем - большой положительный градиент = быстро растет популярность.

Самый простой способ - определить количество поисков в день, поэтому у вас есть что-то вроде

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

, а затем выясните, насколько оно изменилось изо дня в день:

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

и просто примените некоторый порог, чтобы дни, когда увеличение было> 50, считались «горячими». Вы могли бы сделать это намного сложнее, если хотите. вместо абсолютной разницы вы можете взять относительную разницу, чтобы переход от 100 до 150 считался горячим, а от 1000 до 1050 - нет. или более сложный градиент, учитывающий тенденции за более чем один день до следующего.

Обычно "жужжание" вычисляется с использованием некоторой формы механизма экспоненциального / логарифмического затухания. Для обзора того, как Hacker News, Reddit и другие справляются с этим простым способом, см. этот пост .

Это не полностью относится к вещам, которые всегда популярны. То, что вы ищете, похоже на функцию Google Hot Trends . Для этого вы можете разделить текущее значение на историческое значение и затем вычесть значения, которые ниже некоторого порога шума.

Вам нужен алгоритм, который измеряет скорость темы - или, другими словами, если вы наметите ее, вы хотите показать те, которые растут с невероятной скоростью.

Это первая производная линии тренда, и ее нетрудно включить в качестве взвешенного фактора вашего общего расчета.

Нормализация

Одна из техник, которую вам нужно сделать, - это нормализация всех ваших данных. Для каждой темы, которую вы читаете, сохраняйте фильтр низких частот, который определяет базовый уровень этой темы. Теперь каждая точка данных, которая приходит по этой теме, должна быть нормализована - вычтите ее базовый уровень, и вы получите ВСЕ ваши темы около 0, с пиками выше и ниже линии. Вместо этого вы можете разделить сигнал на его базовую величину, что приведет к тому, что сигнал приблизится к 1. 0 - это не только приводит все сигналы в соответствие друг с другом (нормализует базовую линию), но также нормализует пики. Пик Бритни будет на величины больше, чем у кого-то другого, но это не значит, что вы должны обратить на него внимание - шип может быть очень маленьким по сравнению с ее исходным уровнем.

Вывод

Как только вы нормализовались все, разберись по наклону каждой темы. Возьмите два последовательных пункта и измерьте разницу. Положительная разница имеет тенденцию к росту, отрицательная разница имеет тенденцию к снижению. Затем вы можете сравнить нормализованные различия и выяснить, какие темы становятся все более популярными по сравнению с другими темами, причем каждая тема масштабируется в соответствии со своим собственным «нормальным» значением, которое может быть величиной порядка, отличного от других тем.

Это действительно первый проход в проблеме. Существуют более продвинутые методы, которые вам нужно использовать (в основном это комбинация вышеупомянутых с другими алгоритмами, взвешенными в соответствии с вашими потребностями), но этого должно быть достаточно, чтобы начать работу.

Относительно статьи

Статья Речь идет о трендовых темах, но не о том, как рассчитать, что горячо, а что нет, а о том, как обрабатывать огромное количество информации, которую такой алгоритм должен обрабатывать в таких местах, как Lycos и Google. Пространство и время, необходимое для задания счетчика каждой темы и поиска счетчика каждой темы при поиске по ней, огромны. Эта статья о проблемах, с которыми приходится сталкиваться при попытке выполнить такую ​​задачу. В нем упоминается эффект Бритни, но не говорится о том, как его преодолеть.

Я думаю, что ключевое слово, на которое вы должны обратить внимание, это «ненормально». Чтобы определить, когда что-то «ненормально», вы должны знать, что является нормальным. То есть вам понадобятся исторические данные, которые вы можете усреднить, чтобы узнать нормальную частоту конкретного запроса. Возможно, вы захотите исключить ненормальные дни из расчета усреднения, но опять же, для этого потребуется наличие достаточного количества данных, чтобы вы знали, какие дни исключить.

Оттуда вам придется установить порог (который потребует экспериментируя, я уверен), и если что-то выходит за порог, скажем, на 50% больше запросов, чем обычно, вы можете считать это «тенденцией». Или, если вы хотите найти «Top X Trendiest», как вы упомянули, вам просто нужно упорядочить вещи по тому, насколько (в процентном отношении) они отличаются от своего нормального показателя.

Например, предположим, что ваши исторические данные говорят вам, что Бритни Спирс обычно получает 100 000 запросов, а Пэрис Хилтон - 50000. Если у вас есть день, когда они оба получают на 10000 больше запросов, чем обычно, вы должны считать Париж «более горячим», чем Бритни, потому что ее поиски увеличились на 20% больше, чем обычно, в то время как у Бритни было только 10%.

Боже, я могу Не думаю, что я только что написал параграф, сравнивающий "жаркость" Бритни Спирс и Пэрис Хилтон. Что ты со мной сделал?

Если у вас есть день, когда они оба получают на 10000 больше запросов, чем обычно, вы должны считать Париж «более горячим», чем Бритни, потому что ее поиски увеличились на 20% больше, чем обычно, в то время как у Бритни было только 10%.

Боже, я могу Не думаю, что я только что написал параграф, сравнивающий "жаркость" Бритни Спирс и Пэрис Хилтон. Что ты со мной сделал?

Если у вас есть день, когда они оба получают на 10000 больше запросов, чем обычно, вы должны считать Париж «более горячим», чем Бритни, потому что ее поиски увеличились на 20% больше, чем обычно, в то время как у Бритни было только 10%.

Боже, я могу Не думаю, что я только что написал параграф, сравнивающий "жаркость" Бритни Спирс и Пэрис Хилтон. Что ты со мной сделал?

Эта проблема требует z-показателя или стандартного значения, которое будет учитывать среднее историческое значение, как упоминали другие люди, а также стандартное отклонение этих исторических данных, что делает его более надежнее, чем просто используя среднее значение.

В вашем случае z-показатель рассчитывается по следующей формуле, где трендом будет показатель, такой как число просмотров / день.

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

Когда используется z-показатель, чем выше или чем ниже z-показатель, тем более ненормальный тренд, например, если z-показатель очень положительный, тогда тенденция ненормально возрастает, а если он сильно отрицательный, он ненормально падает. Поэтому, как только вы вычислите z-показатель для всех вероятных тенденций, наибольшие 10 z-показателей будут относиться к наиболее ненормально увеличивающимся z-показателям.

Для получения дополнительной информации о z-показателях см. Википедию . ,

Код

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

Пример выходных данных

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

Примечания

• Этот метод можно использовать со скользящим окном (т. Е. За последние 30 дней), если вы не хотите принимать во внимание слишком много истории, что сделает краткосрочные тренды более произносится и может сократить время обработки.

• Вы также можете использовать z-показатель для значений, таких как изменение просмотров с одного дня на следующий день, чтобы найти ненормальные значения для увеличения / уменьшения просмотров в день. Это похоже на использование наклона или производной графика просмотров за день.

• Если вы отслеживаете текущий размер населения, текущий итог населения и текущий итог x ^ 2 населения, вы не нужно пересчитывать эти значения, только обновлять их, и, следовательно, вам нужно только сохранить эти значения для истории, а не для каждого значения данных. Следующий код демонстрирует это.

   из математического импорта sqrt
  
  класс zscore:
   def __init __ (self, pop = []):
   self.number = float (len (pop))
   self.total = sum (pop)
   self.sqrTotal = сумма (х ** 2 для х в поп)
   def update (self, value):
   self.number + = 1.0
   self.total + = значение
   self.sqrTotal + = значение ** 2
   def avg (self):
   вернуть self.total / self.number
   def std (self):
   return sqrt ((self.sqrTotal / self.number) - self.avg () ** 2)
   def def (self, obs):
   return (obs - self.avg ()) / self.std ()
  

• Используя этот метод, ваш рабочий процесс будет следующим. Для каждой темы, тега или страницы создайте поле с плавающей запятой для общего количества дней, суммы просмотров и суммы просмотров в квадрате в вашей базе данных. Если у вас есть исторические данные, инициализируйте эти поля, используя эти данные, в противном случае инициализируйте в ноль. В конце каждого дня рассчитайте z-показатель, используя количество просмотров за день по историческим данным, хранящимся в трех полях базы данных. Темы, теги или страницы с самыми высокими X z-показателями - это ваши «самые горячие тренды» дня. Наконец, обновите каждое из 3 полей значением дня и повторите процедуру завтра.

Новое дополнение

Нормальные z-оценки, как обсуждалось выше, не учитывают порядок данных и, следовательно, z-оценку для наблюдение «1» или «9» будет иметь такую ​​же величину против последовательности [1, 1, 1, 1, 9, 9, 9, 9]. Очевидно, что для определения тренда самые последние данные должны иметь больший вес, чем более старые данные, и поэтому мы хотим, чтобы наблюдение «1» имело больший показатель магнитуды, чем наблюдение «9». Чтобы достичь этого, я предлагаю плавающий средний z-счет. Должно быть ясно, что этот метод НЕ гарантированно является статистически надежным, но должен быть полезен для поиска тренда или аналогичного. Основное различие между стандартным z-показателем и плавающим средним z-показателем заключается в использовании плавающего среднего для вычисления среднего значения популяции и квадрата среднего значения популяции. Подробности см. В коде:

Код

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

Пример ввода-вывода

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

Обновление

Как правильно заметил Дэвид Кемп, если задан ряд постоянных значений, а затем запрашивается zscore для наблюдаемого значения, которое отличается от других значений, результат, вероятно, должен быть ненулевым. На самом деле возвращаемое значение должно быть бесконечностью. Поэтому я изменил эту строку,

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

на:

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

Это изменение отражено в коде решения fazscore. Если кто-то не хочет иметь дело с бесконечными значениями, приемлемым решением было бы вместо этого изменить строку на:

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

Вы можете использовать логарифмические отношения правдоподобия, чтобы сравнить текущую дату с прошлым месяцем или годом. Это статистически обоснованно (учитывая, что ваши события обычно не распределяются, что следует из вашего вопроса).

Просто отсортируйте все ваши термины по logLR и выберите первую десятку.

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 - неупорядоченный сборник слов. Для каждого документа вы создаете один пакет терминов. Просто посчитай вхождения слов. Затем метод вхождений возвращает количество вхождений данного слова, а метод size возвращает общее количество слов. Лучше всего как-нибудь нормализовать слова, обычно достаточно toLowerCase . Конечно, в приведенных выше примерах вы создадите один документ со всеми запросами за сегодняшний день и один со всеми запросами за прошлый год.

Идея состоит в том, чтобы отслеживать такие вещи и замечать, когда они значительно скачут по сравнению с их собственной базовой линией.

Таким образом, для запросов, которые имеют более определенного порога, отслеживайте каждый и когда оно меняется на какое-то значение (скажем, почти вдвое) своей исторической ценности, тогда это новая горячая тенденция.

Чад Берч и Адам Дэвис правы в этом вам придется оглянуться назад, чтобы установить базовый уровень. Ваш вопрос в том виде, как он сформулирован, предполагает, что вы хотите просматривать данные только за последние 24 часа, и это не совсем удачно.

Один из способов выделить вашим данным некоторую память без необходимости запрашивать большой массив исторических данных заключается в использовании экспоненциальной скользящей средней . Преимущество этого заключается в том, что вы можете обновлять это один раз за период, а затем очищать все старые данные, поэтому вам нужно запомнить только одно значение. Поэтому, если у вас дневной период, вы должны поддерживать атрибут «среднесуточное значение» для каждой темы, что можно сделать следующим образом:

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

Где a_n - это скользящее среднее за день n , b - некоторая константа между 0 и 1 (чем ближе к 1, тем длиннее память), а c_n - количество совпадений в день n . Прелесть в том, что если вы выполните это обновление в конце дня n , вы можете сбросить c_n и a_ (n-1) .

Тот предостережение в том, что он будет изначально чувствителен к тому, что вы выберете для своего начального значения a .

РЕДАКТИРОВАТЬ

Если это поможет визуализировать этот подход, возьмите n = 5 , a_0 = 1 и b = .9 .

Предположим, новые значения 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

Не очень похоже на среднее, не так ли? Обратите внимание на то, что значение осталось близким к 1, хотя нашим следующим вводом было 5. Что происходит? Если расширить математику, то получится:

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

Что я имею в виду под остаточным весом? Ну, в любом среднем, все веса должны складываться к 1. Если бы n было бесконечным, и ... могло бы продолжаться бесконечно, тогда все веса были бы в сумме 1. Но если n относительно мало, вы получите хороший вес. на исходном входе.

Если вы изучите приведенную выше формулу, вы должны понять несколько вещей об этом использовании:

1. Все данные всегда вносят что-то в среднее значение. Фактически, есть момент, когда вклад действительно очень мал.
2. Последние значения вносят больший вклад, чем более старые значения.
3. Чем выше b, тем менее важны новые значения и более длинные старые значения имеют значение. Однако, чем выше b, тем больше данных вам нужно для уменьшения начального значения a.

Я думаю, что первые две характеристики - это именно то, что вы ищете. Чтобы дать вам представление о том, как это просто реализовать, вот реализация на Python (за вычетом всего взаимодействия с базой данных):

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