Недавно в Telegram прошел конкурс Кластеризация данных, в котором участникам было предложено создать прототип службы агрегации новостей, подобной сервисам вроде Google News и Яндекс.Новости. Я занял второе место в этом конкурсе (ник Daring Frog), не используя ничего, кроме Python, поэтому решил поделиться подробностями своего решения на случай, если кто-то сочтет его полезным. Вы можете проверить количество очков за задачу (благодаря Mindful Kitten), сравнение скорости, итоговую таблицу лидеров, код и поиграть с живым приложением, которое выглядит так:

🗃 Часть 1 - Автономная пакетная обработка

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

📡 Часть 2 - Онлайн-обработка с HTTP-сервером

  1. Определить язык статей и отфильтровать статьи, которые не на английском или русском
  2. Разделите статьи на одну или несколько из 7 категорий: society, economy, technology, sports, entertainment, science, other
  3. Отфильтровать статьи, не являющиеся новостями (например, инструкции, советы, энциклопедический контент)
  4. Сгруппируйте статьи в темы. Тема - это просто сборник статей об одном и том же событии.
  5. Сортировать статьи в цепочке по релевантности
  6. Сортировать темы по важности
  7. Раскрутите HTTP-сервер, загрузите его предыдущее состояние, если оно существует

✅ Решение

  1. Индексировать входящие статьи
  2. Обновить существующие статьи
  3. Удалить существующие статьи
  4. Показывать самые популярные темы статей с дополнительными фильтрами по языку, категории и временному диапазону.
  5. Поддержка параллельных запросов. На этапе оценки команда Telegram отправляла до 100 параллельных запросов в двоичный файл, что не поддерживалось моим приложением. К счастью, они все еще могли отправлять запросы в одном потоке на большинстве этапов оценки, но это не могло быть сделано для режима «Сегодня», поэтому мое приложение полностью зависло там. Я думал, что это полностью дисквалифицирует мою заявку, но, вероятно, хорошие результаты во всех других задачах помогли с окончательной оценкой.

Помимо этих требований, Telegram подчеркнул, что «скорость имеет первостепенное значение», запросил размер двоичного файла не более 200 МБ и потребовал, чтобы двоичный файл выполнялся на автономной 8-ядерной машине Debian GNU / Linux 10.1 с 8-ядерным ОЗУ 16 ГБ без графического процессора. Вдобавок к этому было невозможно протестировать или запустить приложение на стороне Telegram до отправки, поэтому участники в основном должны были обеспечить безупречную воспроизводимость. Эти требования были главными факторами моего предпочтения простоте алгоритмов и библиотек, которые я использовал.

🗃 Часть 1 - автономная пакетная обработка

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

📡 Часть 2 - Онлайн-обработка с HTTP-сервером

1. Предварительная обработка. Входной HTML-код читается как открытый текст. Метатеги для заголовка, описания, URL-адреса и времени публикации извлекаются с помощью простых регулярных выражений. Основная очистка выполняется для заголовка и описания: удаление знаков препинания и специальных символов, строчные буквы (но не для аббревиатур), добавление пробелов вокруг денежных значений (например, 100 $ становится 100 $), ограничение максимальной длины строки. Слова нормализованы с использованием lemminflect (для EN) и OpenCorpora (для RU), чтобы улучшить качество категоризации и кластеризации (описано ниже), поскольку это помогает уменьшить размер словарного запаса и уменьшить переобучение. Исходные тексты сохраняются и используются вместе с очищенными, в зависимости от задачи.

2. Определение языка. Определение языка выполняется с помощью библиотеки fastText (lid.176.bin). Язык устанавливается на UNK, если показатель достоверности fastText ниже заданного порогового значения. Дополнительная эвристика (сопоставление определенных символов и популярных фраз) используется для устранения неоднозначности угловых случаев для языков, которые fastText считает похожими на русский (UA, TG, BG).

Предварительная обработка и определение языка выполняются совместно с использованием Посредством пакета multiprocessing создано 16 потоков, так как файлы HTML могут обрабатываться независимо.

3. Классификация категорий. Классификация категорий выполняется с помощью простого SGDClassifier из scikit-learn с modified_huber потерями. Входными данными в модель является вектор из TfidfVectorizer, который запускается путем объединения заголовка статьи, домена и описания с максимальной длиной такого текста, не превышающей 500 символов. TfidfVectorizer работает с уни- и биграммами (со стоп-словами NLTK), использует сублинейное масштабирование TF, min_df=3, max_df=0.95 и dtype=np.float32. Для этой задачи отлично подходит простой SGDClassifier:
- Он очень хорошо улавливает словарный запас, что важно, поскольку в мире новостей существует множество терминов, относящихся к конкретным категориям, и часто необходимо запоминать их на основе только на нескольких доступных примерах. Например. Размер словаря TfidfVectorizer составляет 142 КБ для RU и 70 КБ для EN, что считается большим для типичного варианта использования, но работает достаточно хорошо для сбора разнообразных новостей.
- С помощью такой простой модели можно избежать переобучения даже при использовании такого большого словаря и небольшого набора данных.
- Это невероятно быстро и поддерживает ввод разреженных матриц. Разреженность означает, что мы можем 1) эффективно работать с большим объемом словаря без необходимости передавать выходные данные TF-IDF через дорогостоящий этап SVD и 2) нет необходимости поддерживать массивные матрицы встраивания, которые занимают оперативную память, дисковое пространство и приводят к чрезмерно параметризованным моделей.
- Легко интерпретировать и отлаживать (можно легко проследить прогнозы модели вплоть до весов, присвоенных каждому термину словаря).
Я также рассмотрел десятки других типов моделей - см. Приложение B почему они не были выбраны.

TfidfVectorizer и SGDClassifier обучаются на таких наборах данных, как Lenta.ru (RU), HuffPost (EN), TagMyNews (EN), Набор данных агрегатора новостей (EN), BBC (EN), Webhose (EN), а также вручную сканировали веб-сайты по категориям новостей (например, технологии, автомобили, погода), которые страдали от нехватки меток в вышеупомянутых наборах данных. Обучающая выборка была дополнительно обогащена с использованием немаркированных выборочных данных, предоставленных Telegram, путем автоматического присвоения меток категорий с использованием информации URL-адреса статьи: например, если /football/ находится в URL-адресе уважаемого домена, мы можем отнести его к категории sports с очень высокой степенью уверенности. В целом, сохраняя разумное распределение примеров по классам (примерно совпадающие соотношения, ожидаемые на момент вывода), мне удалось получить ~ 120 000 обучающих примеров для EN и 313 000 для RU. В таблице ниже вы можете увидеть количество и соотношение обучающих примеров по категориям.

4. Фильтрация новостей. Фильтрация новостей основана на наборе эвристик, которые представляют собой простые правила, основанные на следующих функциях:
- Классификатор категорий (описан выше); оценка достоверности;
- Количество токенов в заголовке / описании статьи.
- Наличие специальных символов
- Соответствие предварительно утвержденным или предварительно запрещенным словам, подсловам или леммам
- Соответствие заголовка определенным предварительно скомпилированным регулярным выражениям: статьи с практическими рекомендациями, плохие фразы, неправильное начало заголовка , списки / перечисления (например, «10 советов для…») и т. д.
- Соответствие заведомо плохому шаблону заголовка. Это небольшой трюк, который вы можете использовать для поиска шаблонных (например, автоматически сгенерированных) заголовков, по сути, путем преобразования заголовка в код (например, Music — Lounge. 27.03.2020. becomes W — W. ##.##.####.) и кластеризации таких кодов или просто проверки наиболее часто. Это займет всего пару строк кода:

Вы можете увидеть подробные правила в скрипте вывода.

5. Кластеризация потоков. Новости группируются в потоки с помощью DBSCAN со следующими настройками: min_samples=2, eps=0.55, metric='cosine', который запускается на векторах TF-IDF заголовков статей. Векторы TF-IDF создаются с помощью TfidfVectorizer с функцией токенизации SentencePiece. Так же, как и для классификации новостей, я установил dtype=np.float32 для векторизатора TF-IDF, чтобы немного ускорить процесс. Модели TfidfVectorizer и SentencePiece обучаются по всем образцам статей EN и RU, предоставленным Telegram (~ 600 КБ на каждый язык). Размер словаря модели SentencePiece составляет 10К токенов. Кроме того, для некоторых токенов (например, связанных с географией) я повышаю показатели TF-IDF, чтобы придать им большее значение в кластеризации (это, например, заставляет одноименные новости из несвязанных городов помещаться в отдельные кластеры).

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

7. Сортировка потоков. Новостные цепочки сортируются просто по произведению количества уникальных доменов в цепочке с объединенным PageRank этих доменов. И если этот балл одинаков для двух статей, производится дополнительная сортировка по количеству статей в ветке. Категория темы определяется просто как наиболее частая категория среди статей в цепочке. PageRank домена был рассчитан с использованием образцов статей, предоставленных Telegram для всех доменов с как минимум 100 публикациями (~ 3K доменов).

🛠 Часть 3 - Создание двоичного файла

1. Раскрутите HTTP-сервер. Для обработки HTTP-запросов используется SimpleHTTPRequestHandler. Сервер отвечает HTTP/1.1 503 Service Unavailable, пока не будут загружены ресурсы (такие как модели, векторизаторы, словари и предыдущее состояние индекса).

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

4. Удалить существующие статьи. Удалить статью очень просто, поскольку мы просто стираем всю информацию об этой статье. Один потенциально интересный момент здесь заключается в том, что мы хотим удалить строку из матрицы «встраивания» (с нормализованными векторами TF-IDF), что не поддерживается матрицей CSR по умолчанию. К счастью, мы можем выполнять такие эффективные удаления на месте:

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

Telegram требовал, чтобы при подаче заявки на конкурс был предоставлен исполняемый двоичный файл. Также было дополнительное требование, чтобы размер двоичного файла не превышал 200 МБ. Поэтому я использовал отдельную среду «conda» с минимальным набором используемых библиотек (только fasttext, numpy, scipy, scikit-learn, sentencepiece). Используя эту среду, легко создать легкий двоичный исполняемый файл, указав pyinstaller на сценарий Python вывода:

Заключение

Если вы хотите запустить приложение на демонстрационных данных, вы сможете сделать это, используя двоичный файл, созданный на этом этапе, выполнив команду, подобную этой (следуя API, описанному здесь): ./tgnews threads "/path/to/directory/with/articles".

Или просто запустите его напрямую с помощью скрипта Python, например: python tgnews.py threads "/path/to/directory/with/articles".

В конце концов, мое решение - это просто комбинация Python, fastText, SentencePiece, TF-IDF, SGDClassifier и DBSCAN. Я считаю его очень простым и немного хакерским, но, несмотря на это, он оказался 2-м по качеству и 3-м по скорости выполнения (наравне или быстрее, чем решения C ++ 🤷‍♂). Эта простота позволила мне делать все на моем старом MacBook Pro 2012 - что редко возможно в соревнованиях, подобных Kaggle.

🚀 Приложение A. Возможные улучшения

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

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

Решены проблемы с режимом «Сегодня». Обновленное приложение поддерживает до 100 параллельных запросов и было значительно ускорено за счет введения инкрементной записи на диск, блокировок потоков и ограничения длины ввода. Теперь он может индексировать до 200 новостных статей в секунду независимо от размера индекса. Приложение Live доступно по адресу «https://1410.topnews.com/».

😢 Приложение Б. Что не сработало

  • Фильтрация новостей должна основываться на модели, а не на наборе эвристик на основе регулярных выражений. Одна из идей может заключаться в объединении задач фильтрации и категоризации новостей, как это делали некоторые участники («1», «2»), однако может быть полезно держать их отдельно. В любом случае существует потребность в тщательно обозначенных примерах «не новостей», поскольку это расплывчато определенная концепция, по которой практически отсутствуют общедоступные данные.
  • Очевидно, что модели категоризации новостей не хватает глубины (то есть она не принимает решения, основанные на значении, а, скорее, основывает их на запоминании определенных ассоциаций терминов и категорий). Если позволяют вычислительные ресурсы, было бы полезно объединить широту текущей модели с глубиной и нелинейностями, которые приносят нейронные сети. Это можно сделать с использованием моделей Wide & Deep, модельных ансамблей или других техник.
  • Предварительно обученные вложения могут быть добавлены по всему конвейеру (фильтрация новостей, категоризация, кластеризация). Я полностью их пропустил из-за требований к размеру двоичного файла 200 МБ.
  • Следует использовать другие возможности статьи и издателя. Использование только заголовка, URL-адреса и части описания крайне ограничивает.
  • Текущая кластеризация, основанная на исчерпывающем поиске скалярных продуктов, должна быть отброшена в пользу масштабируемых высокопроизводительных методов «ИНС», подобных «ScaNN», «HNSW» и «FAISS». Это поможет поддерживать индексы размером в миллион и миллиард, сохраняя при этом низкую задержку.
  • Следует использовать графические процессоры / TPU, а также машины с высокой памятью (ОЗУ) для хранения соответствующих частей индекса в памяти.
  • Создание набора данных с пометкой для конкретной задачи. Было бы не слишком дорого получить 100–1 млн этикеток, чего должно хватить для точной настройки моделей, обученных на общедоступных наборах данных. Если бюджет ограничен, поможет «активное обучение». Не маркируя образцы статей, я, вероятно, столкнусь с перекосом при обучении и другими нежелательными предубеждениями. Команда, занявшая «1-е» место, помечала статьи через оценщиков, что позволило им «значительно опередить другие материалы» в задаче категоризации.
  • HDBSCAN для пакетной автономной кластеризации. Обычно HDBSCAN - это инструмент для кластеризации, который очень хорошо масштабируется и дает очень высококачественные выходные данные. Однако здесь DBSCAN превзошел его как по качеству, так и по скорости IIRC.

«» Обновление (25.09.2020) «»

  • БЕРЕЗА для потоковой кластеризации (слишком медленно).
  • DenStream для потоковой кластеризации (настраиваемый алгоритм был более гибким).
  • FAISS для потоковой кластеризации (IIRC, это было не намного быстрее, чем хорошо оптимизированные операции с разреженными матрицами, особенно при малых объемах данных).
  • Используется float16 (вместо float32). Исходя из мира графических процессоров, я думал, что это то, что scipy и numpy также могут поддерживать, но, к сожалению, они не поддерживают, поскольку float16 не поддерживается процессором.
  • Другие типы моделей для классификации новостей: я пробовал все, начиная с scikit-learn, что работает с разреженными входными данными. Никакой другой тип модели не может сравниться по качеству и скорости с простым SGDClassifier. ComplementNB был близок или немного лучше по производительности, но приводил к большему размеру двоичного файла.
  • Другие фреймворки для классификации новостей (TF, Keras, PyTorch): я с самого начала переиграл их, чтобы сохранить небольшой размер двоичного файла и быстрый вывод. Добавление TF в автономный двоичный файл приведет к превышению лимита в 200 МБ.
  • Загрузка текстовых файлов как json или gzip. Это значительно медленнее, чем простой старый pickle из-за декомпрессии и необходимости синтаксического анализаjson файла.
  • Обход фильтрации новостей для всех статей от ведущих издателей по PageRank. Идея заключалась в том, что, возможно, они никогда не публикуют не новостной контент. Я ошибался, иногда есть статьи, которые по описанию задачи классифицируются как «не новостные».
  • Использование взвешенных по TF-IDF «CBOW fastText embeddings» для кластеризации (вместо разреженных векторов TF-IDF). Обычно вы обнаружите, что вложения, взвешенные по TF-IDF (например, «word2vec»), являются очень сильной, быстрой и простой базой, но здесь они были медленнее и приводили к более разбавленным кластерам.
  • Перегибы EN из WordNet. LemmInflect был немного лучше по качеству.
  • 2. Индексируйте входящие статьи. Поскольку статьи поступают нескончаемым потоком, нам в основном приходится выполнять кластеризацию в реальном времени, поскольку цепочки статей могут расширяться или изменяться со временем. Из описания конкурса было непонятно, можем ли мы терпеть какие-либо задержки при кластеризации, поэтому я решил выбрать решение, в котором кластеры индексов и статей всегда актуальны. Для этого я написал наивный алгоритм агломеративной кластеризации, похожий на SLINK.

    Шаг 0: входящая статья предварительно обрабатывается, векторизуется и классифицируется, как описано выше, в офлайн-режиме. раздел. В случае, если статья не является {EN, RU} или новостью, мы сохраняем ее как таковую и пропускаем следующие шаги.
    Шаг 1: для плетения статей в нити мы работаем с 16-часовыми интервалами (ведрами). Для данной статьи выбираются ее предыдущие, текущие и будущие сегменты, т. Е. Рассматривается 48-часовое окно (мы предполагаем, что ни одна цепочка статей не будет охватывать более 2 полных дней). Нам нужно заглянуть в будущее, поскольку не исключено, что некоторые статьи приходят с опозданием, например если сканер нашел статью вчера, мы могли бы захотеть сшить ее в кластер с сегодняшнего дня.
    Шаг 2: выбираются токены заголовков статей с рейтингом IDF ниже заданного порогового значения (т. е. мы игнорируем слишком общие термины). Для таких токенов в каждом из сегментов (прошлое, настоящее и будущее) мы выполняем поиск по инвертированному индексу, чтобы получить подмножество ранее проиндексированных статей, которые разделяют один или несколько терминов с текущей статьей. Инвертированный индекс - это простая lil_matrix, где строки - это идентификаторы терминов, а столбцы - идентификаторы статей, поэтому мы можем выполнить поиск по идентификаторам токенов из вектора TF-IDF, чтобы получить идентификаторы соответствующих статей, которые затем можно использовать для поиска векторов вверх (встраивания) релевантных статей в основную матрицу встраивания.
    Шаг 3: среди этих кандидатов статей мы находим ближайшую статью по сходству скалярных произведений, вычисленному на L2-нормализованном Векторы TF-IDF. Если мы находим существующую статью, сходство которой превышает заданный порог, мы можем назначить нашу новую статью в кластер с существующей статьей. Если мы не находим существующую статью, которая достаточно похожа, мы создаем новый кластер.
    Шаг 4: L2-нормализованный вектор TF-IDF для новой статьи складывается поверх существующая матрица CSR с векторами для ранее проиндексированных статей в этот период времени. Матрица CSR отлично подходит для этого варианта использования, поскольку она обеспечивает быстрое умножение, хорошо сочетается с разреженным векторизатором TF-IDF, позволяет быстро v-stacking и удаление строк, и в целом оказывается наиболее эффективной разреженной матрицей для этот вариант использования. Обратите внимание, что каждый временной сегмент имеет свою собственную матрицу CSR, что значительно ускоряет скалярное произведение (поскольку мы можем игнорировать векторы для всех других несущественных периодов времени), а также гарантирует, что индекс может линейно масштабироваться со временем (если мы сильно упрощаем и предполагаем постоянное ежедневное число новостей).
    Шаг 5: все другие соответствующие свойства для инвертированного индекса и информации о кластере (максимальное время, категория, список статей) обновляются соответственно.

Просмотрите каталог ввода и проанализируйте все файлы HTML (статьи) в нем с новостным содержанием.

🥈2-е место в конкурсе по кластеризации данных Telegram