Каков наилучший способ расчета трендов или тегов?

Ответ 1

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

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

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

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

Подробнее о z-баллах см. Wikipedia.

код

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-score для таких значений, как изменение просмотров с одного дня на следующий день, чтобы найти ненормальные значения для увеличения/уменьшения просмотров в день. Это похоже на использование наклона или производного графика просмотров в день.

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

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

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

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

Нормальные 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 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()

Пример 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

Обновление

Как правильно указал Дэвид Кемп, если задан ряд постоянных значений, а затем запрашивается 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

Ответ 2

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

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

нормировать

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

получать

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

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

По поводу статьи

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

Как указывает Никсуз, это также называется Z или стандартным счетом.

Ответ 3

Чад Берч и Адам Дэвис верны в том, что вам придется оглянуться назад, чтобы установить базовый уровень. Ваш вопрос, как сформулировано, предполагает, что вы хотите просматривать данные только за последние 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 относительно невелико, вы получаете хорошее количество веса влево на исходном входе.

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

• Все данные вносят что-то в среднем навсегда. Практически говоря, есть момент, когда вклад действительно, очень маленький.
• Последние значения вносят больше, чем более старые значения.
• Чем выше значение 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

Ответ 4

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

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

Ответ 5

Мне было интересно, возможно ли вообще использовать обычную формулу ускорения физики?

v2-v1/t or dv/dt

Мы можем считать, что v1 является начальным нравом/голосом/количеством комментариев в час и v2 для текущей "скорости" в час за последние 24 часа?

Это больше похоже на вопрос, чем на ответ, но кажется, что он может просто работать. Любое содержимое с наибольшим ускорением будет обсуждаемой темой...

Я уверен, что это может не решить проблему Бритни Спирс: -)

Ответ 6

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

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

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

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

Ответ 7

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

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

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 нет. или более сложный градиент, который учитывает тенденции более чем на один день до следующего.

Ответ 8

Я работал над проектом, где моя цель заключалась в поиске "Тенденции тем" из "Живого Twitter-потока", а также в сентиментальном анализе по обсуждаемым темам (поиск положительно/отрицательно обсуждался в "Трендах" ). Я использовал Storm для обработки твиттер-потока.

Я опубликовал свой отчет как блог: http://sayrohan.blogspot.com/2013/06/finding-trending-topics-and-trending.html

Я использовал Total Count и Z-Score для ранжирования.

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

Надеемся, что информация поможет.

Ответ 9

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

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

Ответ 10

Если вы просто посмотрите на твиты или сообщения о статусе, чтобы получить свои темы, вы столкнетесь с большим количеством шума. Даже если вы удалите все слова остановки. Один из способов получить лучшее подмножество кандидатов по темам - сосредоточиться только на твитах/сообщениях, которые используют URL-адрес, и получить ключевые слова из названия этих веб-страниц. И убедитесь, что вы применяете теги POS для получения имен существительных + существительных.

Заголовки веб-страниц обычно более описательны и содержат слова, описывающие, о чем идет речь. Кроме того, совместное использование веб-страницы, как правило, коррелирует с разделением новостей, которые ломаются (т.е. Если умерла знаменитость, такая как Майкл Джексон, вы получите много людей, которые расскажут о своей смерти).

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

Ответ 11

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

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

Ответ 12

Метод Z-показателя не сработает, если количество ключевых слов (или тем) мало. В этом случае я бы рекомендовал моделировать задачу как распределение Пуассона.