КАТЕГОРИЗАЦИЯ НОВОСТНОЙ ЛЕНТЫ ВЕБ-САЙТА

АННОТАЦИЯ

В данной статье предлагается решение задачи семантической кластеризации (категоризации) новостной ленты сайта. В качестве метода используется алгоритм кластеризации k-meansи частотный словарный анализ. Для новостной ленты сайта sstu.ru были проведены эксперименты с разным значением параметра k. Для полученных кластеров проведён частотный анализ ключевых слов, на основе чего предложены рекомендации по категоризации файлов новостной ленты сайта.

Ключевые слова: веб-сайт, новостная лента, семантическая кластеризация, ключевые слова.

Введение

Основная цель разработчика сайта – спроектировать такую его структуру, которая наиболее удобна для поиска необходимой пользователю информации. Данная задача решается путем реинжиниринга сайта как на основе анализа его гипертекстовой структуры (как правило представляемой графовой моделью) [1], так и на основе учета поведения пользователей сайта, результатов веб-аналитики [2].

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

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

Результаты кластеризации новостной ленты веб-сайта

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

Рисунок 1. Распределение выборки из 2000 файлов новостной ленты сайта www.sstu.ru по кластерам по результатам кластеризации методом K-средних с разным значением параметра k: a) k=6, б) k=8, в) k=10, г) k=12.

Нумерация кластеров ведется с нуля, количество файлов в кластере обозначаются над столбиками гистограмм.

В качестве объекта исследования была рассмотрена новостная лента образовательного сайта www.sstu.ru. В качестве эксперимента была взята выборка из 2000 записей базы данных новостей сайта, которая была кластеризована алгоритмом k-means (k-средних). В результате мы получили совокупность новостных файлов, разделённую на кластеры, характеризующие рубрики новостей.

Всего было проведено 4 эксперимента с разным числом задаваемых алгоритму кластеров. Распределение новостей по кластерам, изображенным в виде подписанных столбцов, с указанием их количества, показано на рисунке 1. При числе кластеров равном шести самое большое количество новостей попадает в кластер с номером 0, а самое малое количество новостей – в кластер с номером 2.

Для восьми кластеров самое большое количество новостей попадает в кластер с номером 0, а самое малое количество новостей – в кластер с номером 7. Значительное количество новостей мы видим также в кластерах с номерами 3 и 4.

При разбиении на десять кластеров самое большое количество новостей попадает в кластер с номером 8, а самое малое количество новостей – в кластер с номером 0. При этом лишь в двух кластерах количество новостей превышает 300 записей – в кластере 6 и кластере 8.

Наконец, при числе k=12 самое большое количество новостей попадает в кластер с номером 6, а самое малое количество новостей – в кластер с номером 5. В двух кластерах с номерами 4 и 5 количество новостей превышает 300 записей. Стоит отметить также, что в данном эксперименте оказалось больше всего кластеров, число записей новостей в которых не превышает 100 записей.

Для того чтобы понять, по какому семантическому принципу новостные файлы объединились в кластеры, для каждого кластера мы на основе частотного анализа произвели отбор ключевых слов. Для этого была использована программа Statistica, с помощью которой мы для совокупности новостных файлов каждого кластера подсчитываем частоту слов. При этом были исключены наиболее часто встречающиеся слова, встречающиеся во всех кластерах, и самые редко встречающиеся слова, по которым невозможно отнести новости к определённому кластеру. Набор ключевых слов, приписываемых кластеру можно охарактеризовать в общих терминах, то есть отнести кластер к некоторой категории. Полученные результаты для разбиений новостных файлов по кластерам во всех проведенных экспериментах представлены в таблицe 1-4.

Таблица 1.

Семантическое описание в виде набора ключевых слов и категоризация кластеров  при разбиении новостной ленты сайта sstu.ru. на 6 кластеров

Таблица 2.

Семантическое описание в виде набора ключевых слов и категоризация кластеров  при разбиении новостной ленты сайта sstu.ru. на 8 кластеров

Таблица 3.

Семантическое описание в виде набора ключевых слов и категоризация кластеров  при разбиении новостной ленты сайта sstu.ru. на 10 кластеров

Таблица 4.

Семантическое описание в виде набора ключевых слов и категоризация кластеров  при разбиении новостной ленты сайта sstu.ru. на 12 кластеров

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

Методы и используемые инструменты для решения задачи

Для программной реализации кластеризации мы использовали алгоритм кластеризации k-means [3], реализованный средствами  библиотеки Scikit-learn [4] языка Python.

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

Для выполнения стеминга (выделения основы слов) использовался инструмент Snowballstemmer, который имеет поддержку русского языка.

Программа работает с базой данных в формате SQLite, поддерживаемой Python путем импорта модуля SQLite3. Текстовые файлы базы данных подвергаются частотному анализу [5], суть которого состоит в следующем:

• построить словарь V из всех слов, используемых в исходных текстах T,
• для каждого текста t_i∊T и для каждого слова из словаря v_j∊V, посчитать число вхождений x_ij слова v_j в текст t_i.

Таким образом, для каждого текста t_i∊T мы получаем вектор целых неотрицательных чисел x_i, длина которого равна количеству слов в словаре V.

Для текстов разного размера величина значений частоты x может сильно отличаться, т.е. чем больше текст, тем больше может быть повторов слов. Для уменьшения этого эффекта применяется метод нормализованного частотного анализа или TF (term frequency), значения частоты x делятся на общее число слов в тексте t:

.

Для выполнения частотного анализа применялся инструмент TfidfVectorizer библиотеки Scikit-learn, по причине удобства использования, а также в виду совмещения в себе функций хеширования слов в тексте и использования частотного анализатора.

Для удобства статистической обработки результатов кластеризации данные из БД SQLite были экспортированы в формат *.csv для использования в Microsoft Office Excel. Фрагмент результата операции представлен на рисунке 2.

Рисунок 2. Фрагмент таблицы с корректным разделением столбцов при просмотре в Microsoft Office Excel

Семантическая характеризация кластеров была выполнена на основе статистики частного распределения слов текстов соответствующего кластера. Для частотного словарного анализа текстов была использована программа Statistica, в которую загружаются новости с присвоенными им номерами кластеров, и которая подсчитывает частоту слов в тексте. При этом были исключены наиболее часто встречающиеся слова, присутствующие во всех кластерах, и самые редкие слова, по которым невозможно определить принадлежность новости к определённому кластеру.

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

Для решения этой задачи используются два метода: лематизация - приведение слов в тексте к нормальной форме (единственное число, именительного падежа) и стеминг - выделение основы слов путём отбрасывания приставок и окончаний [6,7]. Последний способ нормализации текста работает гораздо быстрее чем лематизация. Он менее качественный, но для частотного анализа его вполне достаточно, и поэтому именно он был  использован при написании программы.

Заключение

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

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

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

Список литературы:

1. А.А. Сытник, С.В. Папшев, И.В. Курчанова. Сравнительный анализ некоторых методов семантической кластеризации гипертекста // Материалы XII Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» (ТиПВСИТ 2015). Улан-Удэ, 11-18 августа 2015 г. – Улан-Удэ, Изд-во ВСГТУ, 2015. С. 51-56.
2. Vladimir Salin, Maria Slastihina, Ivan Ermilov, René Speck, Sören Auer, and Sergey Papshev. Semantic Clustering of Website Based on its Hypertext Structure  // Communications in Computer and Information Science. 6th International Conference, KESW 2015 Moscow, Russia, September 30 – October 2, 2015. Proceedings. Pp. 182-194.
3. Introduction to K-means [Электронный ресурс] / Introduction to K-means Режим доступа: http://www.cs.cmu.edu/~dpelleg/kmeans.html (дата обращения 18.04.2018)
4. Scikit-learn Machine Learning in Python [Электронный ресурс] / scikit-learn - Режим доступа: http://scikit-learn.org/stable/modules/clustering.html (дата обращения 18.04.2018)
5. Е. Борисов. Автоматизированная обработка текстов на естественном языке, с использованием инструментов языка Python [Электронный ресурс]/ Е. Борисов – режим доступа: http://mechanoid.kiev.ua/ml-text-proc.html (дата обращения 8.05.2018)
6. С.А. Айвазян. Прикладная статистика: Классификации и снижение размерности : справ. изд. / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков, Л.Д. Мешалкин; под ред. С.А.Айвазяна. – М. : Финансы и статистика, 1989. – 607 с. : ил.
7. Г. Ингерсолл. Обработка неструктурированных текстов / Г. Ингерсолл, Т. Мортон, Э. Фэррис пер. с англ. «ДМК Пресс» - 2015 г.. – стр. 213-220.