РАЗВИТИЕ МЕТОДА КЛАСТЕРИЗАЦИИ СТРАНИЦ ВЕБ-САЙТА НА ОСНОВЕ ДАННЫХ ВЕБ-АНАЛИТИКИ

АННОТАЦИЯ

В статье рассматривается задача повышения эффективности построения сайта на основе учета поведения пользователей, статистики их переходов по гиперсвязям. В данной работе реализуется подход к моделированию гипертекстового пространства сайта, представленного в виде взвешенного графа. Веса дуг графа устанавливаются на основе мета-данных веб-аналитики. Полученный граф подвергается кластеризации алгоритмами MCL и BorderFlow. В рамках данного подхода разработана методика решения задачи, подобран комплекс программ и средства кластеризации. Тестирование метода проводится на примере образовательного сайта sstu.ru. Результаты кластеризации различными алгоритмами являются практически идентичными, что позволяет объективно содержательно описывать кластеры и использовать данную информацию при реинжиниринге веб-сайта.

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

Введение

Объем информации в сети Интернет растёт экспоненциально, в связи с чем остается актуальной проблема эффективного поиска нужных данных. Есть множество подходов к решению данной проблемы [9].  С точки зрения пользователя это проблема контекстного поиска информации, а с точки зрения разработчика – предварительная структуризация данных. Наиболее распространенным способом структуризации информации в Интернете является ее представление в виде гипертекста, который является основой веб-сайтов.

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

Ряд работ в области семантической кластеризации страниц веб-сайтов использует в качестве существенного элемента гипертекстовые связи между страницами. Так, например, в [4] представлена математическая модель гипертекстовой структуры в виде взвешенного редуцированного графа и предложен метод семантической кластеризации гипертекстовой структуры, использующий данные веб-аналитики [12]. В [5] применялся метод кластеризации с помощью алгоритма BorderFlow с ограниченным использованием мета данных. Апробировалась также кластеризация гипертекста алгоритмом MCL [6], но без использования данных веб-аналитики.

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

Сбор статистики о поведении пользователей на веб-сайте

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

В данной работе был использован сервис Google Analytics, который позволяет накапливать данные о поведении пользователей на сайте. Работа сервиса базируется на том, что в каждую страницу сайта встраивается JavaScript код (рисунок 1), который отслеживает действия пользователя при каждой новой сессии. Данный код отслеживания позволяет вычислить время нахождения пользователя на сайте, порядок посещения страниц, время пребывания на каждой из них, сведения о ссылках нажатых пользователем и многое другое.

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

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

• просмотры страниц – общее количество страниц, просмотренных посетителями. Учитываются повторные просмотры одной страницы.
• время, которое пользователь оставался на странице – среднее количество времени, в течение которого пользователи просматривают заданную страницу/экран или набор страниц/экранов.

Так как сервис Google Analytics не позволяет выгружать напрямую данные веб-аналитики, то для этой цели мы использовали инструмент Query Explorer. Данный инструмент является запросчиком (рисунок 2) и позволяет выгружать данные веб-аналитики в  формате таблицы excel (рисунок 3).

Рисунок 2. Интерфейс запросчика Query Explorer, позволяет выбрать сайт, с которого будут взяты данные веб аналитики, за какой период времени, различные метрики метаданных, путь пользователя

Рисунок 3. Фрагмент выгруженных данных веб-аналитики сервисом Query Explorer, первые три столбца - это путь, представляющий собой переход между страницами (узлами) сайта, четвертый столбец количество переходов, пятый – суммарное время нахождения пользователей на узле

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

Таким образом, в общем случае, гипертекст может быть представлен как граф H={P,L,W} (рисунок 4), где H – множество гипертекстовых документов,  L - множество гиперссылок между ними, а W - веса в графе, где веса учитывают количество переходов, совершенных пользователями и время нахождения на узле.

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

Семантическая кластеризация страниц веб-сайта

Для кластеризации графов существует ряд специализированных алгоритмов [10]. Мы воспользовались приложением Graph Clustering and Visualization Framework. После загрузки данных в приложение в нем можно выбрать один из реализованных алгоритмов кластеризации. В нашем случае кластеризация фрагмента сайта sstu.ru была выполнена алгоритмами MCL и BorderFlow. Данные методы были выбраны, так как они специализированы для работы с графами [2].

На рисунке 6 представлены последовательные шаги действий, реализованного метода, которые образуют три этапа: выгрузка данных веб-аналитики, построение графовой модели веб-сайта, кластеризация веб-сайта выбранными алгоритмами.

Рисунок 6.  Диаграмма последовательности действий при кластеризации страниц веб-сайта

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

При кластеризации веб-сайта было получены следующие разбиения на кластеры (рисунок 5).

а)                                                               б)

Рисунок 5. Гистограммы распределения страниц сайта по кластерам, полученные в результате работы алгоритмов MCL[8] (а) и BorderFlow (б). На шкале горизонтали отмечены номера кластеров разбиения, по вертикальной - количество веб-страниц в соответствующих кластерах

На рисунках 7 и 8 приведены результаты работы алгоритмов кластеризации гипертекстовой структуры веб-сайта sstu.ru с учетом данных веб-аналитики. Кластеры были получены с помощью стороннего свободно распространяемого программного приложения Cugar. На данных рисунках можно видеть, что оба алгоритма кластеризации выделяют по 8 кластеров. Это означает, что при кластеризации веб-документов различными алгоритмами, с одинаковыми метаданными разбиения на кластеры весьма схожи.

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

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

Анализ результатов по пересечению кластеров, полученных алгоритмами MCL и BorderFlow, изображены в таблице 1. В таблице по вертикали представлены номера кластеров , полученных алгоритмом BorderFlow, по горизонтали - MCL. Для каждого кластера указано количество страниц в нем. В строках приведен процент веб-страниц для каждого из кластеров алгоритма MCL, попавших в кластеры BorderFlow.

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

Таблица 1.

Результаты кластеризации фрагмента веб-сайта sstu.ru алгоритмами MCL и BorderFlow

Заключение

В работе представлены результаты кластеризации фрагмента веб-сайта sstu.ru алгоритмами MCL и BorderFlow с расширенным использованием данных веб-аналитики, что повышает возможности семантической кластеризации страниц ваб-сайта. Сходные результаты кластеризации разными алгоритмами свидетельствуют об объективном характере образованных кластеров, что является веским аргументом для учета группирования страниц при их последующем семантическом анализе. На основе данных кластеризации можно строить семантическое описание кластеров и использовать при реинжиниринге веб-сайта.

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

1. Анализ данных с помощью отчета «Пути пользователей» [Электронный ресурс]. — Режим доступа: https://support.google.com/analytics/answer/1713056 (дата обращения: 5.06.2017)
2. Бериков В.Б. и Лбов Г.С. Современные тенденции в кластерном анализе [Журнал] // Институт математики им. С.Л. Соболева. - 2009 г.. - стр. 1–26.
3. Для чего нужна web аналитика? [Электронный ресурс]. –  Режим доступа:  http://www.workformation.ru/veb-analitika.html (дата обращения: 10.06.2017)
4. Салин В.С., Папшев С.В., Сытник А.А. Графовая модель веб-сайта как основа для анализа его структуры [Конференция] // Телематика'2012 : тр. XIX всерос. науч.-метод. конф., г. Санкт-Петербург. - 2012. - стр. 190-191.
5. Семантическая сегментация веб-гипертекста на основе дискретных математических моделей [Текст] / В.С. Салин, С.В. Папшев // Компьютерная лингвистика и вычислительные онтологии : сб. науч. ст. XVIII Объединенной конф. «Интернет и современное общество» IMS-2015, Санкт-Петербург, 23-25 июня 2015 г. / ун-т ИТМО. - СПб., 2015. - С. 119-129. - Библиогр.: с. 129
6. Сравнительный анализ некоторых методом семантической кластеризации гипертекста [Текст] / А.А. Сытник, С.В. Папшев, И. В. Курчанова // Теоретические и прикладные вопросы современных информационных технологий : материалы XII всерос. науч.-техн. конф., Улан-Удэ, 11-18 августа 2015 г. - Улан-Удэ, 2015. - С. 51-56. - Библиогр.: с. 55-56
7. Hollink Vera, Van Someren Maarten и Wielinga Bob J. Navigation behavior models for link structure optimization [Журнал] // User Modelling and User-Adapted Interaction. - 2007 г.. - 4 : Т. 17. - стр. 339-377. - ISBN: 0924-1868 1573-1391 ISSN: 09241868 DOI: 10.1007/s11257-007-9030-0.
8. MCL - a cluster algorithm for graphs. [Электронный ресурс]. —  Режим доступа:  http://micans.org/mcl/.
9. Shadbolt N, Hall W и Berners-Lee T. The Semantic Web Revisited [Журнал] // IEEE Intelligent Systems. - 2006 г.
10. Schaeffer Satu Elisa Graph clustering by flow simulation [Журнал] // Computer Science Review. - 2007 г.. - 1 : Т. 1. - стр. 27-64. - ISSN: 15740137 DOI: 10.1016/j.cosrev.2007.05.001.
11. Xiao J. [и др.] Measuring similarity of interests for clustering web-users [Конференция] //Proceedings of the 12th Australasian database conference. – IEEE Computer Society, 2001. – С. 107-114.
12. Vladimir Salin, Maria Slastihina, Ivan Ermilov, René Speck, Sören Auer, Sergey Papshev. Semantic Clustering of Website Based on its Hypertext Structure // Proceedings of 6th International Conference. Communications in Computer and Information Science., KESW 2015 Moscow, Russia, September 30 – October 2, 2015. Pp. 182-194