Содержание к диссертации
Введение
Глава 1. Модели и методы кластеризации гипертекстовых структур 14
1.1. Общая характеристика проблемы кластеризации веб-документов 14
1.2. Задача семантической кластеризации гипертекстовых документов 20
1.3. Традиционные методы семантической кластеризации документов 23
1.4. Подходы к моделированию гипертекстовой структуры для ее кластеризации 26
Глава 2. Разработка модели семантической кластеризации гипертекстовой структуры с использованием статистики переходов 30
2.1. Сбор данных о действиях пользователей на веб-сайте 30
2.2. Моделирование поведения пользователей в гипертексте 33
2.3. Семантическая кластеризация гипертекстовой структуры с учётом статистики переходов 36
Глава 3. Разработка программного комплекса для кластеризации гипертекста с использованием статистики переходов 45
3.1. Требования к программной системе 45
3.2. Общая архитектура системы 47
3.3. Реализация программной системы 51
Глава 4. Методика оценки эффективности семантической кластеризации гипертекста 59
4.1. Разработка методики оценки эффективности 59
4.2. Оценка эффективности разработанного метода семантической кластеризации на реальных веб-сайтах 63
4.3. Практические рекомендации к подбору входных параметров модели и ограничения её применения 67
Заключение 73
Список литературы
- Задача семантической кластеризации гипертекстовых документов
- Подходы к моделированию гипертекстовой структуры для ее кластеризации
- Моделирование поведения пользователей в гипертексте
- Оценка эффективности разработанного метода семантической кластеризации на реальных веб-сайтах
Задача семантической кластеризации гипертекстовых документов
Подходы к кластеризации веб-документов в гипертекстовой структуре могут отличаться от традиционных подходов к кластеризации обычных текстовых документов. Ключевой разницей является наличие гипертекстовых свойств у веб-документов – во-первых, это их HTML-структура, а во-вторых, наличие гиперссылок между веб-документами. Данные свойства гипертекста могут также быть использованы для анализа семантики его документов.
Существенным нововведением в данной области стало изобретение алгоритма PageRank С. Брином и Л. Пейджем [40]. Подход, используемый в основе данного алгоритма, предполагает, что наличие ссылок с одного веб-сайта косвенно указывают на его семантическую связь с другим веб-сайтом. Таким образом, имея мета-описание одного веб-сайта (например, в виде ключевых слов), существует возможность предположить тематику других веб-сайтов, на которые ссылается первый. Данный подход аналогично работает не только на множестве веб-сайтов, но и на множестве веб-страниц, между которыми проставляются гиперссылки.
Отсюда вытекает важное следствие, что схожие по смыслу веб-документы будут указывать ссылками скорее друг на друга, чем на веб-страницы другой тематики. То есть, внутри гипертекстовой структуры могут формироваться группы тесно связанных друг с другом страниц, причем данные группы обособлены от других веб-страниц низким количеством ссылок на них. Данная особенность может быть использована при проведении семантической кластеризации, целью которой как раз и является определение групп (кластеров) веб-страниц по схожести тематики. Формально, каждый веб-сайт может быть представлен определенной гипертекстовой моделью (кроме того, данная модель может соответствовать на только веб-сайту, размещенному в сети Интернет, но и другим реализациям, например, приложению-справке, использующей HTML в качестве разметки). Мы можем определить гипертекстовую модель веб-сайта Н как набор двух основных множеств: Н = {Р, L], (1) где Р = {р±, ..., рп) - множество страниц гипертекста, а L = [і Зр1( р2 є Р : р±, р2 Є l(Pi, Р2)} – множество гиперссылок между страницами.
Более формально описание задачи семантической кластеризации можно представить следующим образом. Пусть на множестве гипертекстовых документов Р = {рг, ...,рп} определена функция расстояния между ними psem(p,p ). Требуется разбить исходное множество объектов на подмножества - кластеры таким образом, чтобы каждый кластер содержал объекты, близкие по метрике psem, а объекты разных кластеров существенно отличались. В результате каждому гипертекстовому документу рі Є Р приписывается номер кластера yt Є У . Функция fsem\P Y называется функцией семантической кластеризации, а ее конкретная реализация зависит от выбранного метода кластеризации.
Методы текстовой кластеризации используют для работы лишь текстовое содержание веб-страницы - Т. Соответствующая функция семантической кластеризации для них определена на данном множестве и будет выглядеть как fsemi(T). В случае веб-документов, требуется выполнить извлечение текстового содержания Т из всего содержимого страницы Р: ext: Р Т (2) Тогда: fseml (Т) = fseml (ext(P)) (3) Однако описанные в предыдущем параграфе проблемы с извлечением текстового содержимого из веб-страниц, возможным отсутствием данного текста вовсе, отделением смыслового содержания от визуального шаблона страницы, могут приводить к тому, что ext(P) = 0. В таком случае, функция кластеризации становится неопределенной и не может быть применена для данной задачи.
В случае рассмотрения веб-документа как элемента гипертекстовой структуры, мы можем дополнительно учесть в функции кластеризации еще и множество гиперссылок L: fsem2(ext(P),L):P Y (4) Функция fsem2 (4) в таком случае зависит не только от текстового наполнения, но и от ссылочной структуры, и не теряет применимости в случае ext(P) = 0. Однако во многих случаях только данных о ссылочной структуре может быть недостаточно для проведения кластеризации. Например, тогда, когда все документы имеют приблизительно равное количество гиперссылок на другие документы. Или же, ссылочная структура является линейной, с последовательными гиперссылками между документами.
Следующим шагом в разработке модели гипертекстовой структуры, мы можем расширить базовое представление гипертекста как статической структуры, за счет его рассмотрения в динамическом контексте посещения гипертекстовых страниц пользователями. Поведение пользователей на веб-сайте можно трактовать не как случайные переходы между веб-страницами, а последовательное решение определенной поисковой задачи в пределах одного сеанса, с некоторой вероятностью отклонения от курса [94, 97, 109]. Иными словами, пользователь в рамках своей сессии переходит по веб-страницам, соответствующим, по его мнению, определенному поисковому запросу и определенной тематике.
Статистика посещений S совокупности таких сеансов также может учитываться для представления гипертекста совместно со статистикой переходов и проведении семантической кластеризации: fsem3{ext{P),L,Sy.P Y (5)
В данном случае, при ext(P) = 0, для кластеризации доступна не только гипертекстовая ссылочная структура, но и статистика переходов пользователей в ней, что позволяет повысить эффективность по сравнению с использованием функции fsem2 (4).
Таким образом, задача семантической кластеризации гипертекста имеет формализованное представление. Общая задача состоит в том, чтобы разбить исходное множество документов на подмножества - кластеры таким образом, чтобы каждый кластер содержал объекты, близкие по метрике psem, а документы разных кластеров существенно отличались. В результате каждому гипертекстовому документу р Є Р приписывается номер кластера у EY. Данное отображение задается в виде fsem(H): Р - У.
Эффективность и применимость функции кластеризации может меняться в зависимости от фактических условий и выбора подхода к моделированию гипертекста и рассмотрению разного набора его параметров.
Подходы к моделированию гипертекстовой структуры для ее кластеризации
После того, как был составлен редуцированный граф, объединяющий маршруты пользователей, он может быть использован при кластеризации. Как упоминалось в первой главе, существуют различные алгоритмы кластеризации графа, которые по сути реализуют функцию сопоставления каждой вершине vt Є Vi номеров кластеров yt Є Y. Формально, это можно представить в виде следующего выражения: fsem(G,R,&T,w0) = AlgClust(G{)\V - Y (11) где V - множество вершин графа G,Y - множество меток кластеров вершин, Gt - взвешенный редуцированный граф, AlgClust(G{) - реализующая алгоритм кластеризации функция. Среди множества известных алгоритмов кластеризации графов, таких как MCL [107], Chinese Whispers [38], k-means [54], Girwan-Newman [55], BorderFlow [77], при решении конкретной задачи необходимо выбрать наиболее подходящий алгоритм. Часть из них (например, k-means) требует указать число кластеров в качестве входного параметра, однако данный параметр заранее не известен.
Ключевым параметром в алгоритмах кластеризации на графах является метрика Psem(P Р Х используемая для собственно группирования вершин в единый кластер. На взвешенном графе такая метрика естественным образом определяется как средневзвешенное расстояние между вершинами. То есть, вершины, входящие в общий кластер, между собой имеют большее значение метрики, чем с вершинами других кластеров.
В одном из алгоритмов кластеризации графа, BorderFlow, метрика как раз задается таким образом, чтобы в кластер включались вершины, у которых взвешенная сумма связей с другими вершинами данного кластера сильнее относительно взвешенных связей с вершинами вне кластера.
На приведенном рисунке 12 видно, что внутренние связи в кластере (заштрихованная область) сильнее, чем связи с внешними узлами графа (поскольку граф на рисунке невзвешенный, все веса можно считать равными единице). Функция кластеризации взвешенного ориентированного графа задается как функция максимизации некоторого соотношения F путем перебора всех вершин в графе: fBF(G) = [ХІІХІ = arg max F(Xi+v),Xi Є V, G = {V,E} (U\ ven{Xi) ) Отношение F в свою очередь задается так: где b(X) = {х Є Х\3у Є V\X: w(x,y) 0} - вершины на границе множества X, п(Х) = {у EV\X\3xE X:w(x,y) 0} - ближайшие соседи множества X, П(Х,У) = їхеХіУЕУ\к(х,у) - суммарные веса ребер, исходящих из одного множества в другое. Из данного отношения видно, что алгоритм BorderFlow полностью удовлетворяет основному критерию.
Для задачи семантической кластеризации, выработаны и другие критерии выбора подобного алгоритма. Во-первых, алгоритм кластеризации графа должен уметь работать со взвешенным графом, то есть учитывать веса при своей работе. При распределении весов, отличных от равномерного, должно повыситься значение модулярности (6), а значит, сообщества в графе, обладающие высоким внутренним весом, должны сильнее отделяться друг от друга.
Во-вторых, разброс размеров кластеров должен быть как можно меньше, а сами размеры кластеров - включать количество элементов, сопоставимое с размерами групп, полученных при текстовой кластеризации. В таком случае, представляется возможной привязка нетекстовых документов, входящих в состав кластера, к тематике кластера текстовых документов.
В-третьих, асимптотическая вычислительная сложность алгоритма кластеризации должна ограничиваться сверху полиномом второй (в крайнем случае, третей) степени относительно числа узлов или ребер (для веб-графов, зависимость числа ребер от количества вершин обычно линейная). В противном случае, кластеризация графов средних и больших веб-сайтов (боле 10000 страниц) будет занимать неприемлемое вычислительное время. Выбранный алгоритм BorderFlow соответствует, в том числе, указанным критериям.
На рисунке 13 слева изображен исходный граф, в котором наиболее существенные связи отмечены черным цветом. Серым отмечены несущественные связи, а также вершины, которые они соединяют. В результате редукции графа и применения алгоритма кластеризации, получим разбиение графа на три кластера (отмечены группами на графе справа). На примере кластера II из рисунка видно, что в кластере остались наиболее плотно связанные по метрике вершины – сумма их внутренних весов в кластере выше, чем веса в соседние кластеры.
На том же модельном примере также отмечены темной заливкой нетекстовые документы. Видно, что при редукции часть связей с ними была отброшена. Однако по другим, более весомым связям данные вершины попали в кластеры вместе с вершинами текстовых документов.
В итоге, задача семантической кластеризации гипертекстовой структуры сводится к задаче кластеризации взвешенного редуцированного графа , полученного по входным параметрам, включающим исходный граф гипертекста и маршруты переходов. Тогда функция семантической кластеризации с учетом выбранного алгоритма кластеризации строится таким образом, чтобы учитывать не только топологию гипертекстовой структуры, но и данные о маршрутах в ней: /sem(G, Я, ДГ, w0) = BorderFlowiGO: V Y, (14) где BorderFlow(G{) - реализующая алгоритм BorderFlow функция.
Таким образом, семантическая кластеризация гипертекста может решаться при помощи построения новой расширенной графовой модели гипертекстовой структуры, в которой веса вычисляются с учётом статистики переходов пользователей. Разработанный для данной модели семантической кластеризации основывается на использовании известного алгоритма кластеризации графа BorderFlow. Данный алгоритм удовлетворяет всем необходимым требованиям, в том числе, используемая в нём метрика сопоставления вершин подходит под заданные критерии.
Моделирование поведения пользователей в гипертексте
Другой способ также требует привлечения экспертов, однако основной их задачей является оценка результатов каждого конкретного разбиения. Безусловно, такая задача проще и требует меньше затрат со стороны экспертной группы, по сравнению с первым способом. Недостатком является необходимость выполнять такую экспертную оценку каждый раз в ручном режиме.
Несмотря на распространенность использования данных способов в различных исследованиях, посвященных семантической кластеризации, они подразумевают работу только с текстовыми документами. Это означает, во-первых, невозможность использования существующих эталонных наборов данных для проверки эффективности разработанного в рамках данного исследования метода. Во-вторых, сложность к оценке результатов разбиения кластеров, содержащих текстовые и нетекстовые документы, без привязки к конкретной тематике – по сути, эксперту пришлось бы определять тематику каждого кластера самостоятельно, просматривая содержимое каждого документа. Поэтому для оценки эффективности разработанного метода кластеризации требуется новая методика.
Предлагается осуществлять данную оценку путем «привязки» (сопоставления) кластеров текстовых и нетекстовых документов, тематика которых неизвестна по итогам разбиения, полученного новым методом, с конкретной заданной тематикой. В качестве источника для данной тематики может послужить разбиение исходного веб-сайта на кластеры при помощи традиционных методов семантической кластеризации, обрабатывающих только текстовые документы, но при этом определяющих их тематику.
Разработанную методику оценки на базе вычислительного эксперимента можно описать следующей последовательностью действий. Сначала к веб-документам выбранного сайта требуется применить традиционный метод текстовой кластеризации, в рассмотрение которого попадают только текстовые веб-документы.
Результатом его работы будет являться множество кластеров текстовых документов {At} (рисунок 20а). Каждому кластеру соответствует определенная тематика, составленная при анализе содержимого веб-документов, вошедших в кластер.
Далее ко всем исходным веб-документам необходимо применить новый метод семантической кластеризации на основе статистики переходов, который рассматривает как текстовые, так и нетекстовые веб-документы. Результатом работы будет множество кластеров, включающих оба вида документов {Bj}.
Для того, чтобы соотнести нетекстовые документы кластеров {Bj}, кластеры из множества {Bj} сопоставляются с кластерами {At} с известной тематикой путем их пересечения (рисунок 20б). Поэтому можно косвенно определить тематику нетекстовых документов путем соотнесения с известной тематикой кластера текстовых документов.
Поиск кластеров нетекстовых документов из множества {Bj} для сопоставления с кластером текстовых документов определяется по введенной численной метрике, которая вычисляется как отношение размера пересечения множеств А и В к размеру множества В: \А п В\ Precision , В) = (15) Высокие значения метрики должны указывать на вероятную семантическую близость кластеров А и В.
Предложенная метрика учитывает относительное количество общих документов в двух кластерах - известной и неизвестной тематики. Если кластеры не содержат общих документов, значение метрики будет равно нулю. Если кластер В будет полностью включен в кластер А, метрика достигнет максимального значения (единица). Очевидно, что второй случай возможен только если кластер В не будет содержать нетекстовых документов. В то же время, если кластер В будет содержать слишком много нетекстовых документов (\В\ - оо, \А П В\ = const), то значение метрики будет стремиться к нулю. На реальных примерах целевое значение должно находиться в диапазоне [0,5;0,9], сама метрика применима в тех случаях, когда кластеры нового метода по размеру скорее меньше, чем кластеры традиционных методов.
Также возможно использование и других метрик для сопоставления кластеров известной и неизвестной тематики. Похожим образом может быть рассчитана метрика, которая относит размер пересечения двух кластеров к размеру кластера заданной тематики: \А п В\ Recall(A, В) = (16) То есть, кластер неизвестной тематики В при максимальном значении метрики Recall включает в себя кластер известной тематики. Такое возможно, если кластеры, полученные при разбиении веб-сайта новым методом, скорее больше по размеру, чем группы текстовой кластеризации. В конце концов, может применяться сбалансированная метрика (F-мера), которая в своем расчете включает в себя приведенные выше метрики Precision и Recall: 2 X Precision , В) X Recall(A, В) FmeasureiA, В) = Precision(A в) + Recall(A в) (17) Метрика может быть удобна для сбалансированной оценки пересечений кластеров, когда заранее сделать выводы о соотношении размеров кластеров сложно. Листинг реализации алгоритмов расчёта всех трёх метрик представлен в приложении Б.
Все перечисленные метрики широко используются задачах классификации, распознавания образов, анализа данных, и применяются как раз для сопоставления исходного и целевого множеств.
В рамках данного исследования проведена оценка эффективности метода семантической кластеризации, согласно разработанной методике. Проверка эффективности разработанного метода проводилась в рамках вычислительных экспериментов на примере трёх реальных веб-сайтов: aksw.org14, museum.seun.ru15 и sstu.ru.
Как было изложено в предыдущих главах, важным требованием при выборе веб-сайтов служит наличие накопленных данных о статистике переходов пользователей. В данном случае, были выбраны веб-сайты, статистика посещения которых отслеживается более одного года, чтобы иметь возможность варьировать показатели временного интервала, за который осуществляется выборка.
Оценка эффективности разработанного метода семантической кластеризации на реальных веб-сайтах
Прежде всего, рассмотрим влияние временного интервала выборки статистики переходов . Поскольку каждый веб-сайт обладает своим уровнем посещаемости среди пользователей, выбор данного параметра для веб-сайта должен быть индивидуальным. При слишком низких объемах статистики, невозможно построение полноценной модели взвешенного графа, так как большая часть весов будет близка к единице, а это в свою очередь может означать попросту случайные переходы, совершенные пользователем. В итоге, взвешенный редуцированный граф будет слишком маленьким для применения алгоритмов кластеризации.
Кроме того, с точки зрения основной задачи – кластеризации нетекстовых документов, стоит учитывать количество переходов к нетекстовым документам. При небольших объемах статистики, такие переходы опять же могут быть случайными или незначительными, а значит, при дальнейшей кластеризации невозможно будет отнести их к конкретной тематике.
С другой стороны, выборка статистики за длительный интервал времени может содержать значительное число неактуальных веб-страниц или переходов. Это следует из динамичного развития и обновления большинства веб-сайтов – публикуется множество новых страниц, старые страницы часто помещаются в архив или удаляются (или удаляются ссылки на них). Кроме того, обработка больших объемов статистики переходов требует больше вычислительных мощностей и может занимать больше времени. Также, в некоторых системах сбора статистики посещений (например, используемой в данной работе системы Google Analytics) существуют искусственные ограничения на выгрузку данных. Поэтому выгрузка самих данных может быть затруднена или требовать дополнительных материальных затрат.
Другой параметр – пороговое значение веса, по которому происходит усечение графа. Как показал опыт построения модели для трёх различных вебсайтов, выбор значения для данного параметра также индивидуален для конкретного сайта. Хотя цель редукции общая для всех – отсечение случайных переходов пользователей, значение параметра 0 может колебаться в диапазоне [1..10] и в общем получается на один-два порядка ниже среднего значения веса.
При этом важно помнить о том, что слишком высокие значения порогового веса могут отбросить переходы к нетекстовым документам, снизив тем самым их количество в редуцированном графе.
Выше на рисунке 22 показаны графики зависимости размера редуцированного графа от выбранного порогового значения веса. Как видно на примере веб-сайтов aksw.org и museum.seun.ru, явно выделяются два ключевых порога для весов в графе: 2 перехода (снижение количества весов примерно на 50%) и 4 перехода (снижение еще примерно на 30%). Однако ситуация для museum.seun.ru осложняется тем, что после второго порога остается весьма малое количество ребер, особенно при выборке за небольшой временной интервал.
Дальнейшее снижение количества ребер при повышении порога происходит весьма монотонно, без резких колебаний, что может означать образование устойчивых связей между документами, по которым часто переходят пользователи. Следовательно, дальнейшее увеличение порогового значения не привлечет к улучшению результатов.
Для веб-сайта sstu.ru ситуация несколько отличается (рисунок 23). При продолжительных интервалах времени для выборки статистики (2 месяца и более) количество ребер даже при небольшом пороге, равном 2, может снижаться в несколько раз. После редукции, количество посещенных ребер за длительные интервалы приближается к аналогичному количеству посещенных за меньшие интервалы. Это может означать слишком высокое количество случайных переходов пользователей, а значит, дальнейшее увеличение интервалов наблюдения для данного веб-сайта вряд ли позволит улучшить результаты кластеризации. Исходные данные, по которым были построены графики на рисунках 22 и 23, представлены в приложении
В конце концов, отметим условия применимости предложенной модели и метода семантической кластеризации. Исходя из основного принципа построения модели, необходимо наличие собранной статистики переходов за заданный интервал времени. С технической точки зрения, это означает необходимость подключения веб-сайта к системе сбора данной статистики (Google Analytics, Яндекс Метрика и другие). При отсутствии статистики, модель сводится к невзвешенному орграфу, кластеризация которого даст в целом непредсказуемый результат.
Другим ограничением является наличие хотя бы нескольких текстовых документов на веб-сайте, поскольку именно к кластеру таких документов в дальнейшем будет производиться привязка нетекстовых документов. Как раз текстовый кластер позволяет определить тематику (при помощи традиционных методов семантической кластеризации) и затем привязать к данной тематике нетекстовые документы.
Дополнительно стоит отметить особенности вычислительных ограничений. Основным является сложность применения данного метода для графов очень больших веб-сайтов с числом вершин порядка 106 и выше. Ограничения вызваны тем, что известные алгоритмы кластеризация имеют вычислительную асимптотическую сложность 0(п2) или выше, где n - количество вершин в графе. Проведение кластеризации на графах большего размера требует значительного увеличения вычислительных ресурсов и эффективных (по использованию вычислительных ресурсов) многопоточных алгоритмов. Ряд ограничений, связанных с технической реализацией программного комплекса, описан в предыдущей главе.
Несмотря на упомянутые ограничения, разработанная модель и метод кластеризации остаются применимы к многим современным веб-сайтам. Согласно открытой статистике, средний размер веб-сайта за последние несколько лет не превышает 104, такие веб-сайты содержат как текстовые, так и нетекстовые