Использование алгоритмов кластеризации и суммирования для агрегации новостей

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

Содержание

Главная идея
Парсинг новостных данных
Алгоритмы кластеризации
– K-средние
– DB-SCAN
– Среднее смещение
Сравнение алгоритмов кластеризации
Обобщение текста
– Алгоритмы извлечения
— Слова темы
— Ранжирование текста
— Анализ скрытой семантики
— Алгоритмы извлечения
Сравнение алгоритмов суммирования
Заключительные заметки
Рекомендации

Главная идея

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

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

Скрапинг данных

Я составил список из примерно 40 URL-адресов RSS самых популярных медиа-источников на македонском языке. URL-адреса предназначены для местных, экономических, политических и мировых новостей. Каждый URL-адрес в среднем содержит 20 новостных статей, поэтому в итоге остается около 800 статей для дальнейшей обработки. Очистка выполняется с помощью BeautifulSoup4 и регулярных выражений для очистки текста. Весь процесс очень прост, поэтому я не буду приводить сюда код, но вы можете найти его на моем GitHub.

Алгоритмы кластеризации

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

Прежде чем использовать какой-либо конкретный алгоритм, компьютер должен «понять» текст новостной статьи. Компьютеры не могут обрабатывать текст на естественном языке так, как это делают люди, поэтому его приходится кодировать в векторе. Многие алгоритмы и модели машинного обучения делают именно это, например, Bag of words, TFIDF, GloVe, Doc2Vec, BERT и многие другие. Это область изучения обработки естественного языка (NLP). Для простоты я использую алгоритм частотно-обратной частоты документа Term (TF-IDF). Хотя это и не так продвинуто, как более сложные модели машинного обучения, этого достаточно для решения этой задачи.

TF-IDF состоит из двух частей:

Частота термина (TF) — измеряет частоту термина в тексте.
Обратная частота документа (IDF) — измеряет, насколько важен этот термин. Это позволяет алгоритму не придавать большого значения общеупотребительным словам.

Окончательное значение рассчитывается как отношение этих двух значений. Реализовать этот алгоритм просто с помощью sklearn.

K-средние

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

Однако у алгоритма есть серьезная проблема для этой конкретной задачи агрегирования новостей. Количество кластеров (K) необходимо задать явно перед запуском алгоритма. В некоторые дни тем новостей гораздо больше, чем в другие, поэтому мы не можем заранее знать, каким будет это число. При тестировании я обнаружил, что в среднем 40 кластеров идеально подходят для этой задачи. Эта конфигурация успешно объединяет большинство популярных тем новостей. Он терпит неудачу в темах, которые не очень популярны, создавая кластеры, которые представляют собой смесь более чем одной новостной темы.

ДБСКАН

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

eps - максимальное расстояние между двумя точками данных, чтобы одна из них считалась соседней с другой.
min_samples — минимальное количество точек данных, чтобы они считались новым кластером.

Все остальные точки данных, не входящие в кластеры, считаются выбросами. В отличие от K-средних, количество кластеров DBSCAN является динамическим, и его не нужно устанавливать заранее. Для этой конкретной задачи я обнаружил, что лучше всего иметь значение eps 1,05 и минимальный размер выборки 3. Это дает около 50 кластеров, при этом около 35% точек данных являются выбросами.

Средний сдвиг

Среднее смещение — это неконтролируемый алгоритм кластеризации, используемый в основном при обработке изображений. Он использует подход «подъем в гору» для итеративного смещения ядер кластеров в более плотную область до тех пор, пока не будет достигнута сходимость или максимальное количество итераций. Как и DBSCAN, ему не нужно заранее указывать количество кластеров.

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

Сравнение алгоритмов кластеризации

K-Means — это универсальный алгоритм, дающий отличные результаты. Его можно эффективно использовать для агрегации новостей, если пользователю будут показаны только первые N кластеров, поскольку менее плотные кластеры, как правило, содержат новости из разных тем.

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

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

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

Обобщение текста

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

Извлекающее обобщение

Алгоритмы экстрактивного реферирования используют предложения, которые уже есть в тексте, для формирования реферата. Общая идея состоит в том, что предложения ранжируются по «важности», и используются только первые N предложений. Вычисление этой «важности» отличает алгоритмы извлечения друг от друга. Можно использовать несколько алгоритмов.

Тематические слова

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

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

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

Текстовый ранг

Алгоритм текстового ранжирования — это популярный алгоритм на основе графов, который можно эффективно использовать для создания сводок. Он основан на более популярном алгоритме «Page Rank», который используется поисковыми системами для определения того, какие веб-страницы ранжируются первыми.

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

В следующем коде показана реализация на python.

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

Скрытый семантический анализ (LSA)

Латентный семантический анализ — это сложный алгебро-статистический метод, который извлекает скрытую семантику в словах и предложениях. Он выясняет, какие слова или фразы используются вместе и какие общие слова встречаются в разных предложениях. Большое количество общих слов указывает на большое сходство между предложениями. Разложение по единственному значению — это алгебраический метод, используемый для нахождения отношений между этими словами и предложениями.

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

Абстрактные алгоритмы

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

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

Другой вариант — использовать более общие предварительно обученные большие языковые модели, такие как GPT-2, RoBERTa и другие. Эти модели обычно обучаются на текстовых данных на английском языке, и очень немногие работают с македонскими.

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

Сравнение алгоритмов суммирования

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

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

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

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

Заключительные заметки

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

Я создал веб-сайт, на котором показаны основные кластеры македонских новостей, каждый из которых содержит три пункта сводных данных (наиболее важные предложения). Веб-сайт использует кластеризацию DBSCAN с суммированием LSA. Он доступен по этой ссылке.

Полный код этой статьи с бэкендом flask и фронтендом React можно найти по этой ссылке.