Структура данных/Алгоритм для потоковой передачи данных и определения тем

Question

Я хочу знать эффективные алгоритмы/структуры данных, чтобы идентифицировать приведенную ниже информацию в потоковых данных.

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

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

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

Идентифицируйте верхние k тем, обсуждаемых пользователями.

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

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

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

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

Что будет эффективным алгоритмом/структурой данных для достижения этой цели.

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

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

Рассмотрите многоязычные данные из твитов по всему миру. Как я могу определить похожие темы, обсуждаемые в географической области?

У нас есть 2 проблемы. Одним из них является идентификация используемого языка. Его можно определить на основе персонализации. Но эта информация может повлиять на конфиденциальность пользователей. Другая идея может быть запущена через алгоритм обучения. Какой метод лучше всего подходит для этого. Другая проблема - это поиск слова в словаре и связывание его с общим промежуточным языком, например, английским. Как позаботиться о смысловом смысле слова, как одно и то же слово, используемое в разных конкурсах.

Определять границы слов

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

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

Ваш отзыв приветствуется.

Спасибо за ваше время.

- Bala

Answer 1

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

Удаление дубликатов (относительно) легко. Чтобы удалить «близкие» дубликаты, вы можете сначала удалить неинтересные части из ваших данных. Вы можете начать с удаления капитализации и пунктуации. Вы также можете удалить наиболее распространенные слова. Затем вы можете добавить полученное сообщение в фильтр Bloom. Хешинг недостаточно хорош для Twitter, так как хэшированные сообщения не будут намного меньше, чем полные сообщения. У вас будет хеш, который не вписывается в память. Вот почему вы использовали фильтр Bloom. Возможно, это должен быть очень большой фильтр Bloom, но он все равно будет меньше, чем хеш-таблица.

Другая часть - сложная проблема категоризации. Вы, наверное, не хотите сами писать эту часть. Существует множество библиотек и программ, доступных для категоризации, но может быть трудно найти тот, который соответствует вашим потребностям. Примером может служить проект Vowpal Wabbit, который является быстрым онлайн-алгоритмом для категоризации. Однако он работает только по одной категории за раз. Для нескольких категорий вам придется запускать несколько копий и обучать их отдельно.

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

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

Answer 2

Я не совсем уверен, если я отвечаю на ваш главный вопрос, но вы могли бы определить схожесть двух сообщений путем вычисления Levenshtein distance между ними. Вы можете думать об этом как о «различии в редактировании» между двумя строками (I.E., сколько изменений нужно будет сделать для одного, чтобы преобразовать его в другое).

Answer 3

Привет, мы создали очень похожее демо, используя api.cortical.io функциональность. Там вы можете создавать семантические отпечатки пальцев каждого твита. (вы также можете извлечь самые популярные ключевые слова или некоторые подобные термины, которые не обязательно должны быть частью твита). Мы использовали отпечатки пальцев для фильтрации потока твиттера на основе контента. На странице twistiller.com вы можете увидеть результат. Общественный поток 1% twitter отслеживается для четырех различных областей темы.