Как улучшить мой Алгоритм, чтобы найти, что Горячие Темы как Твиттер делают

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

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

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

Просто некоторые мысли :-)

редактирование:

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

То, что вы ищете, обычно называется стоп-словом . Вот запись в блоге со списком (даже в формате массива PHP для вас) и другая версия текстового файла.

Еще немного погуглив, вы найдете другие примеры.

Еще несколько потенциальных идей по улучшению алгоритма в целом:

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

2. Создайте таблицу базы данных слов и их средней частоты в сообщениях на вашем сайте. При просмотре сообщений, созданных за последние X часов, сравните частоту слов со средней частотой в вашей базе данных. Те слова, частота которых значительно выше средней, будут считаться "горячими". Убедитесь, что вы пересчитываете среднюю частоту для слов на полурегулярной основе (возможно, раз в день?)

Если вам нужны статически значимые значения, вы можете вычислить z-значение для каждого слова в недавнем подмножестве относительно общего текста.

Так что если

t is number of occurrences of word in subset
o is number of occurrences of word overall
n_t is number of words in subset
n_o is number of words overall

тогда вычислить:

p_hat = t / n_t
p_0 = o / n_o

z = (p_hat - p_0) / sqrt((p_0 * (1 - p_0)) / n_t)

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

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

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

Для подсчета, сортировки и усечения реального списка "трендовых тем" я предлагаю следующее:

function buildTopTen($word = null)
{
    static $wordList = array();
    if (isset($word)) {
        if (!isset($wordList[$word])) {
            $wordList[$word] = 0;
        }
        $wordList[$word]++;
        return $wordList[$word];
    } else {
        arsort($wordList);
        return array_slice($wordList, 0, 10);
    }
}

Просто вызовите функцию с параметром слова до тех пор, пока вы не закончите. В ответ вы получите текущее количество этого слова, если оно вам пригодится.

Вызовите его один раз без параметров, и вы получите десятку наиболее часто употребляемых слов из списка.

Я протестировал его, и пока что производительность кажется нормальной.

Конечно, это всего лишь предложение, и оно может быть доработано гораздо дольше.

Вот идея:

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

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

Алгоритм вычисления частоты прост:

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

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

] Возможно, вы захотите ознакомиться с NLTK (Natural Language Toolkit). Существует бесплатная книга, которая научит вас пользоваться ею по адресу []http://www.nltk.org/book[]. Единственным недостатком является то, что она находится в Питоне, и я полагаю, что вам нужно решение на PHP. Не пугайтесь слишком сильно, потому что книга не ожидает, что вы заранее знаете какой-нибудь питон.[

]NLKT очень мощный и определенно стоит посмотреть.[

] Не проще ли отсканировать каждую подачу во время создания, чем проводить большой массовый поиск каждые 2 часа? [

Возможно, вы захотите исследовать использование цепей Маркова / Скрытых моделей Маркова.

Эти математические модели были довольно успешны в обработке естественного языка.

Точность в трендовых темах была бы гораздо выше. (И вы можете позволить ей учиться...)

Вот дешевый и веселый способ сделать это.

Каждые 2 часа создавайте гистограмму частот ваших слов. Эг;

Snow, 150
Britney, 100
The, 150000

Сохраните все эти файлы.

Каждые так часто, берите 50 файлов из вашей истории и усредняйте частоты. Это сглаживает тенденции, которые развивались с течением времени. Итак, из этих трех файлов;

Snow, 10
Britney, 95
...

Snow, 8
Britney, 100
...

Snow, 12
Britney, 105
...

вы получаете этот базовый набор;

Snow, 10
Britney, 100

Определите соотношение между этим базовым набором и самым последним;

Snow 1500%
Britney 100%

Ваши тренды имеют самые высокие соотношения. Будьте осторожны с разделением на нули здесь.

Приятно то, что вы настраиваете свои тренды, выбирая данные из более длительного или более короткого периода времени. Eg, вы можете увидеть тенденции этого месяца путем усреднения за год, и сегодня днем тенденции путем усреднения за последние 24 часа.

Правка -- с этим алгоритмом вам не нужно беспокоиться о стоп-словах, потому что все они будут иметь относительно стабильные соотношения, примерно на 100%, так что всегда будут скучными (например, вне тренда)