Welcome to the Machine

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

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

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

На Западе (как, впрочем, и в России), начали активно развиваться технологии TDT - Topic Detection and Tracking, служащие не только для нахождения похожих новостей, но и для мониторинга отдельных событий, и для получения информационной картины мира в определенное время.

Теория Topic Detection and Tracking призвана решить следующие задачи:
1. Сегментация статей (Story Segmentation) - задача разделения непрерывного потока на новости, связанные одним и тем же событием.
2. Отслеживание новостной дорожки (Topic Tracking) - нахождение всех новостей, которые “похожи” на множество эталонных новостей. Используется для отлова всех потенциально интересных документов по теме, которые могут появиться в будущем.
3. Определение дорожки (Topic Detection) - кластеризация всех новостей, порожденных конкретным событием.
4. Определение первой новости в дорожке (First Story Detection) -
для нахождения самого первого сообщения в новом событии.
5. Определение связей (Link Detection) - позволяет определить, порождены ли две новости одним и тем же событием.

Эти задачи в той или иной форме решены в новостных службах Яндекс-Новости и Новотека.

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

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

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

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

Яндекс-Новости работает по другому принципу. По словам его разработчика Михаила Маслова в этой системе каждому документу сопоставляется “поисковый образ” - запрос из характерных терминов; запрос строится на основе поиска по кворуму (это стандартный оператор Яндекса, хотя и плохо задокументированный). Из списков найденных документов строится матрица близости; при вычислении меры близости документов используется стандартная же мера релевантности Яндекса, причем используется агломеративный метод кластеризации.
Подводя итоги, можно сказать, что пока никому не удалось создать квази-идеальный сервис для работы с новостями, поэтому каждая служба хороша по своему.

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

Правила републикации. Данную статью разрешается перепечатывать только с указанием автора и источника: Вячеслав Тихонов