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

Многие сайты предлагают некоторую статистику, например «Самые горячие темы за последние 24 часа». Например, Topix.com показывает это в разделе «Тенденции новостей». Там вы можете увидеть темы, которые имеют наиболее быстро растущее число упоминаний.

Я хочу вычислить такой "шум" и для темы. Как я мог это сделать? Алгоритм должен взвешивать темы, которые всегда менее горячие. Темы, которые обычно (почти) никто не упоминает, должны быть самыми горячими.

Google предлагает «Горячие тренды», topix.com показывает «Горячие темы», fav.or.it показывает «Тенденции ключевых слов» - у всех этих сервисов есть одна общая черта: они показывают только будущие тренды, которые в настоящий момент необычайно горячие.

Такие термины, как «Бритни Спирс», «погода» или «Пэрис Хилтон», не появятся в этих списках, потому что они всегда горячие и частые. Эта статья называет это «Проблема Бритни Спирс».

Мой вопрос: как вы можете написать алгоритм или использовать существующий для решения этой проблемы? Имея список с ключевыми словами, которые искали за последние 24 часа, алгоритм должен показать вам 10 (например) самых горячих.

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

Я надеюсь, что вы можете мне помочь (примеры кодирования были бы хорошими).

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

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

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

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

  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-показателями - это ваши «самые горячие тренды» дня. Наконец, обновите каждое из 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

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

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

Нормализовать

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

Выведите

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

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

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

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

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

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

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

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

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

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

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

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

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

v2-v1/t or dv/dt

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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