Data Clustering Contest: Round 2

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

Общая информация о конкурсе — в канале @contest.

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

Исходные данные

Участникам предлагается тестовый набор данных в формате HTML:

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

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

Задания конкурса

  1. Создание или усовершенствование алгоритмов кластеризации. Необходимо, опираясь на рекомендации, создать или улучшить качество работы созданных в первом этапе конкурса алгоритмов для:

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

  3. Выдача ранжированных сюжетов за период времени. Алгоритм должен уметь формировать список сюжетов по указанной тематике за указанный период времени, отсортированный по важности. При этом сюжеты на русском должны быть актуальны для читателя из России, а сюжеты на английском — для широкого круга международных читателей.

Более подробно задачи описаны ниже, в разделе проверка работ. Для удобства участников, также прилагаются критерии, рекомендованные для оценки качества кластеризации и ранжирования.

Прием работ

Работы будут приниматься в виде standalone приложения tgnews. Приложение должно уметь работать в двух режимах:

  • CLI-интерфейс. Для проверки качества кластеризации приложение будет запускаться несколько раз с различными параметрами, описанными ниже. В этом режиме приложение должно вывести результат работы алгоритма в формате JSON в STDOUT и завершить работу. При этом приложение не должно кешировать и переиспользовать никаких данных между запусками. Запуски могут быть выполнены в произвольном порядке, и это не должно влиять на результат работы алгоритма.
  • HTTP-сервер. Приложение должно уметь работать в режиме HTTP/1.1 сервера с поддержкой Keep-Alive. Для индексации и выдачи ранжированных списков новостей к серверу будут выполняться HTTP-запросы, описанные ниже. Приложение должно хранить проиндексированные данные на диске в рабочей директории приложения и быть готово к тому, что HTTP-сервер может быть перезапущен в любой момент между запросами.

Общие требования к работам

  • Приложение в режиме CLI не должно использовать сеть.
  • Приложение в режиме HTTP-сервера не должно создавать исходящих соединений. Оно может обрабатывать входящие соединения только на указанном в параметрах порту.
  • Процесс tgnews должен оставаться активным, пока работает HTTP-сервер. При убийстве процесса tgnews убивается HTTP-сервер и все порождённые им дочерние процессы. Если вы используете внешний скрипт для запуска веб-сервера, то мы рекомендуем использовать exec.
  • Приложение должно отличаться высокой относительной скоростью работы (по этой причине приложения, написанные на C++, могут получить преимущество).
  • Использование внешних зависимостей рекомендуется свести к минимуму. Зависимости, которые все же необходимы, нужно перечислить в текстовом файле deb-packages.txt. Они будут установлены перед запуском командой sudo apt-get install ...
  • Приложения будут тестироваться на серверах с Debian GNU/Linux 10.1 (buster), x86-64 с 8 ядрами и 16 GB RAM. Обязательно проверьте корректность работы программы на чистой системе перед отправкой работы.
  • Приложения в режиме CLI, выполняющиеся дольше 60 секунд на каждые 1000 файлов, переданных в source_dir, рассматриваться не будут. Это ограничение должно выполняться для каждого запуска скрипта в режиме CLI.
  • Приложение в режиме HTTP-сервера должно успешно обрабатывать до 1000 запросов в 60 секунд. При этом время инициализации не должно превышать 60 секунд на каждые 1000 файлов в индексе.
  • На выходе требуется ZIP-файл со следующей структурой.

    submission.zip
      -> tgnews - запускаемый бинарный файл с интерфейсом, описанным ниже
      -> src - директория с исходным кодом приложения
      -> deb-packages.txt - текстовый файл с названиями пакетов внешних зависимостей, разделенных переводом строки
      -> * - дополнительные файлы, необходимые для работы программы (используйте относительные пути для доступа к ним)

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


Проверка работ

Проверка работ будет происходить в два этапа.

Этап 1. Кластеризация

Для проверки качества кластеризации алгоритм будет запускаться в режиме CLI со следующими параметрами:

1.1. Выделение текстов на русском и английском языках
tgnews languages <source_dir>

где:

  • <source_dir> – путь до директории с HTML-файлами, содержащими тексты статей. Может содержать поддиректории с HTML-файлами, которые также необходимо обработать.

Результат должен быть выведен в формате JSON в STDOUT. Формат ответа:

[
  {
    "lang_code": "en",
    "articles": [
      "981787246124324.html",
      "239748235923753.html",
      ...
    ]
  },
  {
    "lang_code": "ru",
    "articles": [
      "273612748127432.html",
      ...
    ]
  },
  ...
]

где:

  • lang_code – ISO 639-1 two-letter language code (обязательны en и ru, остальные опциональны)
  • articles – список имен файлов (без указания относительного или абсолютного пути), содержащих тексты на языке lang_code
1.2. Отделение новостей от других материалов
tgnews news <source_dir>

где:

  • <source_dir> – путь до директории с HTML-файлами, содержащими тексты статей. Может содержать поддиректории с HTML-файлами, которые также необходимо обработать. Тексты статей могут быть на английском и/или русском языках.

Результат должен быть выведен в формате JSON в STDOUT. Формат ответа:

{
  "articles": [
    "981787246124324.html",
    ...
  ]
}

где:

  • articles – список имен файлов (без указания относительного или абсолютного пути), содержащих новости

Подробные рекомендации для определения новостей »

1.3. Группировка по тематике
tgnews categories <source_dir>

где:

  • <source_dir> – путь до директории с HTML-файлами, содержащими тексты статей. Может содержать поддиректории с HTML-файлами, которые также необходимо обработать. Тексты статей могут быть на английском и/или русском языках.

Результат должен быть выведен в формате JSON в STDOUT. Формат ответа:

[
  {
    "category": "society",
    "articles": [
      "981787246124324.html",
      ...
    ]
  },
  {
    "category": "sports",
    "articles": [
      "2348972396239813.html",
      ...
    ]
  },
  ...
]

где:

  • category"society", "economy", "technology", "sports", "entertainment", "science" или "other"
  • articles – список имен файлов (без указания относительного или абсолютного пути), содержащих статьи по тематике category

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

Подробные рекомендации для группировки по категориям »

1.4. Группировка похожих новостей в сюжеты
tgnews threads <source_dir>

где:

  • <source_dir> – путь до директории с HTML-файлами, содержащими тексты статей. Может содержать поддиректории с HTML-файлами, которые также необходимо обработать. Тексты статей могут быть на английском и/или русском языках.

Результат должен быть выведен в формате JSON в STDOUT. Формат ответа:

[
  {
    "title": "Telegram announces Data Clustering Contest",
    "articles": [
      "6354183719539252.html",
      ...
    ]
  },
  {
    "title": "Apple reveals new AirPods Pro",
    "articles": [
      "9436743547232134.html",
      ...
    ]
  },
  ...
]

где:

  • title – общий заголовок для сгруппированного набора новостей
  • articles – список имен файлов (без указания относительного или абсолютного пути), содержащих похожие новости, отсортированный по релевантности (релевантные выше)

Подробные рекомендации для группировки по сюжетам »

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

Этап 2. Индексация и ранжирование

Для проверки индексации и ранжирования приложение будет запускаться со следующими параметрами:

tgnews server <port>

где:

  • <port> – номер порта.

Приложение должно поднять HTTP-сервер на порту port и подготовиться к получению HTTP-запросов (например, подгрузить индекс с диска). Пока сервер не готов, он должен отвечать 503 ошибкой. Пример ответа:

HTTP/1.1 503 Service Unavailable

HTTP-запросы, отправляемые приложению, описаны далее. Гарантируется, что параллельно будет отправляться не более 100 запросов.

2.1. Индексация

HTTP-запрос:

PUT /article.html HTTP/1.1
Content-Type: text/html
Cache-Control: max-age=<seconds>
Content-Length: 9

<content>

где:

  • article.html – имя HTML-файла,
  • <seconds> – время жизни статьи в секундах (от 5 минут до 30 дней),
  • <content> - содержимое HTML-файла.

Приложение должно проиндексировать файл со статьей, содержащийся в теле запроса. Гарантируется, что статья содержит метатег <meta property="article:published_time"> c датой публикации статьи. В заголовке Cache-control: max-age будет передано время жизни статьи в индексе в секундах. Если от даты публикации текущей статьи до даты публикации самой поздней статьи в индексе прошло больше <seconds> секунд, текущая статья должна быть удалена из индекса.

HTTP-сервер должен ответить кодом 201, если статьи еще не было в индексе, или 204, если статья была обновлена в индексе. Пример ответа:

HTTP/1.1 201 Created

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

2.2. Удаление из индекса

HTTP-запрос:

DELETE /article.html HTTP/1.1

где:

  • article.html – имя HTML-файла.

Приложение должно удалить файл со статьей из индекса.

HTTP-сервер должен ответить кодом 204, если статья была успешно удалена, или 404, если статья отсутствует в индексе. Пример ответа:

HTTP/1.1 204 No Content
2.3. Ранжирование сюжетов

HTTP-запрос:

GET /threads?period=<period>&lang_code=<lang_code>&category=<category> HTTP/1.1

где:

  • <period> – период времени в секундах (от 5 минут до 30 дней),
  • <lang_code> – язык статей, en или ru,
  • <category> – тематика (society, economy, technology, sports, entertainment, science, other) или any.

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

Рекомендации для определения важности и актуальности сюжетов »

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

В списке всегда должны быть только новости, на указанном языке. Если сюжетов получается больше 1000, алгоритм может вернуть первые 1000 сюжетов (сюжетов, не статей). Гарантируется, что в запросе будут присутствовать все указанные параметры и они будут иметь валидные значения.

HTTP-сервер должен ответить кодом 200. Данные должны быть возвращены в формате JSON в теле ответа. Пример ответа:

HTTP/1.1 200 OK
Content-type: application/json
Content-length: 373

{
  "threads": [
    {
      "title": "Telegram announces Data Clustering Contest",
      "category": "technology",
      "articles": [
        "6354183719539252.html",
        ...
      ]
    },
    {
      "title": "Apple reveals new AirPods Pro",
      "category": "technology",
      "articles": [
        "9436743547232134.html",
        ...
      ]
    },
    ...
  ]
}

где:

  • threads – список сюжетов, отсортированный по важности (важные выше). Каждый сюжет содержит название и список статей. Если был запрошен category=any, также содержит поле category.
  • title – общий заголовок для сюжета.
  • category"society", "economy", "technology", "sports", "entertainment", "science" или "other". Только для category=any.
  • articles – список имен файлов статей по этому сюжету (без указания относительного или абсолютного пути), отсортированных по релевантности (релевантные выше).

Скрипт для проверки

Для проверки приложения на соответствие указанным выше форматам запросов и ответов, вы можете использовать скрипт на языке PHP (дата последнего обновления: 25.05.2020 15:15 UTC), который запускает приложение во всех необходимых режимах:

php dc-check.php <binary> all <port> <source_dir>

где:

  • <binary> – путь до запускаемого бинарного файла tgnews.
  • <port> – номер любого свободного порта.
  • <source_dir> – путь до директории с HTML-файлами, содержащими тексты статей, на которых будет произведено тестирование.

Вы также можете использовать одну из следующих команд, чтобы протестировать только одно из заданий конкурса:

php dc-check.php <binary> languages <source_dir>
php dc-check.php <binary> news <source_dir>
php dc-check.php <binary> categories <source_dir>
php dc-check.php <binary> threads <source_dir>
php dc-check.php <binary> server <port> <source_dir>

Обратите внимание, что скрипт проверяет только корректность запуска и формат ответа и НЕ оценивает качество работы программы. Работа скрипта тестировалась на сервере с Debian GNU/Linux 10.1 (buster), x86-64. Если вы используете внешний скрипт для запуска приложения, то мы рекомендуем использовать exec.


Рекомендации по кластеризации

При разметке данных, модераторы опираются на следующие инструкции:

Определение новостей

Новости описывают события, изменения и происшествия в широком смысле, происходящие в данный момент или случившиеся в недавнем прошлом (относительно момента публикации). Как правило, прочитав новостную статью, можно ответить одним предложением на вопрос: “Что случилось?” Часто именно такое предложение будет являться заголовком статьи (впрочем, исключения нередки, и опираться на один заголовок не следует).

Масштаб новости не имеет значения. Крошечная заметка “В Малых Вершках восстановили электроснабжение” или “Овощной склад на западе городка переоборудуют в квартиры” — это всё равно новости.

Примеры статей, не являющихся новостями:

  • Относительно безвременные статьи-рассуждения (“Почему демократия плоха для Африки?”)
  • Исторические статьи (“Как Наполеон переходил Альпы”, “В 1914-м году средние заработки рабочих в Российской Империи начали падать”).
  • Энциклопедические, справочные и обучающие материалы (“Виды короедов России”, “Как выбрать шкаф?”, “Решение уравнений с тремя неизвестными”).
  • Списки, не относящиеся к событиям (“Шесть способов отдохнуть от работы в этот понедельник”, “Лучшие роутеры 2019-го”). Здесь стоит отметить, что “Опубликован полный список номинантов на Золотой Глобус” или “Павел Дуров рассказал о 7 причинах не ехать в Кремниевую Долину” — это новости).

Группировка по категориям

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

Статьи, принадлежащие к трём категориям, крайне редки. Особенно не рекомендуется добавлять Society как третью категорию (например статью “Курс акций Tesla упал после пожара на заводе” можно отнести к категориям Экономика и Технологии, но не Общество).

  • Society: политика, выборы, законодательство, происшествия, преступления и т.д. Самая обширная категория. Включает принятые и планирующиеся законы, любые политические события, преступления, происшествия и несчастные случаи любого масштаба и так далее.

  • Economy: рынки, финансы, бизнес и т.д. Также новости компаний, рынки, акции, кризисы, экономические показатели. “Уровень безработицы вырос на 15%” и т.д.

  • Technology: устройства, автомобили, приложения, сервисы в интернете и т.д. Компьютерные игры относятся к развлечениям, в категории Entertainment, а не к “Технологиям”. В качестве второй категории, “Технологии” могут быть добавлены к новостям об играх в редких исключениях, когда в новости важен именно технологический компонент — например, “Первой игрой, поддержавшей Direct X 18, стала Assassin's Creed 33”).

  • Sports: всевозможный спорт, включая киберспорт.

  • Entertainment: кино, музыка, игры, книги, выставки и прочее искусство, еда, рестораны, знаменитости, светская хроника и т.д. Сюда же относятся животные (исключения: если животных вывели в лаборатории это “Наука”, если они затоптали 100 человек, это “Общество” — и т.д.).

  • Science: здоровье, биология, физика, генетика и т.д.

  • Other: всё остальное. Сюда, в частности, относятся прогнозы погоды (если они не достаточно катастрофические, чтобы попасть в “Общество” или научные-аномальные, чтобы попасть в “Науку”), а также эзотерика, гороскопы, не-технологическая реклама и т.д. Категория Other не может быть присвоена статье, которая относится к любой другой категории.

К примеру, так можно было бы разобрать по категориям различные новости о коронавирусе:

  • Science: Новости про симптомы, советы как не заболеть, поиски вакцины и т.д.
  • Society: Карантинные меры в разных регионах, заболевшие политики, обращение королевы и т.д.
  • Economy: Проблемы малого бизнеса, предприниматели получат компенсации и т.д.
  • Entertainment: Заболевшие знаменитости (не политики), новое граффити Бэнкси о пандемии, концерт в поддержку врачей и т.д.
  • Sports: Перенос Олимпиады в Токио из-за пандемии и т.д.
  • Technology: Apple и Google готовят приложение, предупреждающее о контактах с зараженными, WHO запустила бота и т.д.

Группировка по сюжетам

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

Несколько примеров возможных сюжетов внутри темы “эпидемия коронавируса”:

Один сюжет: “В Москве вводится обязательное ношение масок и перчаток”, “Мэр Сергей Собянин объявил о режиме обязательного ношения масок и перчаток”, “Москвичей будут штрафовать за отсутствие масок и перчаток”.
Другой сюжет: “В Московской области отложили штрафы за отсутствие масок”

Один сюжет: “Трамп прокомментировал версию о намеренном создании коронавируса Китаем”, “Президент США заявил, что не верит в преднамеренное распространение Китаем коронавируса”, “Трамп: Китай сделал ужасную вещь с коронавирусом, но нечаянно”.
Другой сюжет: “В Германии назвали обвинения США против Китая отвлечением внимания от ошибок”

Один сюжет: “В Турции рассказали, когда смогут принимать российских туристов”, “Турция рассчитывает на российских туристов с июля”, “Из России в Турцию: возобновление международных рейсов возможно в середине июля”.
Другой сюжет: “Политолог объяснил, почему Турция не откажется от системы «всё включено»”.

Агрегационные статьи, освещающие несколько заведомо разных сюжетов (“Главные новости за выходные” и т.д.), не должны объединяться в один сюжет ни с одним из упоминаемых в них сюжетов.

Заголовок сюжета

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

Пример хорошего заголовка сюжета:
“Актёр Том Хэнкс стал донором плазмы для больных COVID-19”.

Неудачный заголовок сюжета:
“«Это так же просто, как вздремнуть». Звезда фильмов «Зеленая миля» и «Форест Гамп» о донорстве для получения вакцины от COVID-19 (5 фото)”.

Рекомендации по ранжированию

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

Актуальность для временного периода

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

Алгоритм НЕ должен возвращать новости, не актуальные для временного периода.

Актуальность для английского раздела

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

Актуально:
“China Reports First New COVID-19 Case In Wuhan”, “Hundreds gather in Hong Kong malls as anti-gov't rallies reemerge”, “World’s biggest lockdown: 1.3 billion Indians ordered to stay home”, “Xbox exec says it ‘set some wrong expectations’ for Xbox Series X game reveals”.

Не актуально:
“Amash's candidacy injects uncertainty for Trump in key swing state of Michigan”, “Lagos governor pledges 'maximum' health funding”, “Yogi Adityanath asks high-level teams to camp in Agra, Meerut, Kanpur”, “Made in Qatar 2020' expo to open in Kuwait”.

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

Актуальность для русского раздела

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

Актуально:
“Отрицатели коронавируса сожгли вышку сотовой связи”, “Little Big представит Россию на Евровидении”, “Извержение вулкана в Новой Зеландии”, “Власти Уханя рассказали о новой вспышке коронавируса”, “Скандальный разговор Трампа и Зеленского”.

Не актуально:
“Белорусская авиакомпания забрала граждан из Судана и Анголы”, “Украинская киноакадемия назвала победителей кинопремии «Золотая Дзига»”, “Масштабный пожар в Одесской области: горел торговый центр, погибших нет”, “С начала года в Минское агентство по госрегистрации обратились более 100 тыс. посетителей”.

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