Предсказание следующей страницы при помощи PageRank с учётом её размера, частоты и длины визитов

Аннотация

В данной работе мы расширяем применение алгоритма PageRank для предсказания следующей страницы по нескольким навигационным параметрам, таким как размер страницы, продолжительность посещения страницы и продолжительность перехода (последовательность двух посещений страниц), частота посещения страницы и частота переходов. В нашей модели мы определяем популярность переходов и страниц при помощи информации о продолжительности и используем её отношение к размеру страницы и частоте визитов. Используя оценку популярности страницы, мы модифицируем традиционный алгоритм PageRank и разрабатываем систему рекомендации следующей страницы, которая создаёт рекомендации по данному top-n значению. Фактически мы разрабатываем Duration Based Rank (DPR, PageRank на основе продолжительности визита), который нацелен на анализ отношения размера страницы к продолжительности визита. Так же мы разрабатываем модель ранжирования Popularity Based Page Rank (PPR), направленную на анализ пропорции размера страницы/продолжительности визита и значение частоты посещений страницы. Кроме того, мы сравниваем эффективность глобального и локального ранжирования PPR и DPR.

1. Введение

Число пользователей Мировой Паутины увеличилось на 400% к 2011 году [7]. При этом, количество проиндексированных страниц в Интернете превысило 50 миллиардов [12]. Согласно наблюдениям, это число удваивается каждые 6-10 месяцев. В интернете размещён огромный объём данных, к сожалению, в «сыром» виде. Так как поиск информации является неотъемлемой частью нашей жизни, необходимо превратить «сырые» данные в упорядоченную информацию. Одним из путей извлечения скрытой информации является дата-майнинг использования Интернета пользователями. Дата-майнинг использования Веба можно считать добычей специфических данных о посещении страницы. В нашем исследовании мы сосредоточились на комбинации дата-майнинга использования Веба и структурной информации о веб-сайтах. Предсказания следующей страницы веб-сайта является перспективной темой исследований, в особенности, в контексте рекомендационных систем, учитывающих навигацию пользователей по сайту. Такие рекомендации обычно узконаправленны на предсказание следующей страницы, которую посетит пользователь. Система может работать на различных доменах. К примеру, в онлайн-магазинах, музыкальных или видео-сайтах подобная информация является очень ценной и с её помощью можно предлагать пользователю новинки, основываясь на данных анализа похожего поведения прочих пользователей данного сайта.

В научных работах описываются различные способы анализа веб-логов [9, 13, 3, 5] с целью предсказания следующей страницы. Анализ в значительной степени основан на методиках дата-майнинга. Кластеризация, последовательный майниг, майнинг по ассоциативным правилами и модели вероятностей являются популярными техниками для предсказания следующей страницы пользователю [8, 4, 14]. Модели Маркова являются часто используемым подходом для расчёта вероятности последовательности [16]. Эти модели исследовались в различных сферах и успешно работают для предсказания следующей страницы [1, 2, 14]. По Маркову, модель, использующая длинные последовательности навигации для предсказания следующих страниц показывает более точные результаты. С другой стороны, это увеличивает сложность охвата (space complexity). Это является главным ограничением в использовании моделей Маркова. Другим способом предсказания следующей страницы пользователя является использование PageRank, алгоритма поисковой системы Google [15]. Следующей страницей является та, что имеет самую высокую оценку в системе подобного вида. Главной идеей алгоритма PageRank является следующее условие: если популярная страница а указывает на страницу b, то страница b популярнее a. Таким образом, входящие ссылки определяют популярность документа. Следовательно, популярность можно определить несколькими способами. Несмотря на то, что PageRank является хорошим способом маркировки качественных рекомендательных страниц, существует определённый недостаток в его работе. Кроме того, что его достаточно долго пытались использовать в задачах продвижения сайтов, PageRank определяет популярность страниц в глобальном контексте, который не учитывает историю навигационного поведения пользователя. Игнорирование этой информации генерирует практически одинаковые результаты предсказания. В качестве решения в [5, 6] PageRank комбинируется с моделью Маркова низкого уровня (которая так же описывается как ориентированный граф). В данной работе мы расширяем этот комбинированный подход по времени, проведённому на веб-странице, структурной информации страницы (т.е. её размеру в байтах) и частоте переходов. В нашей работе мы определяем популярность переходов страницы и популярность страниц в рамках частоты перехода между ними, а так же частоты кликов, соответственно. По этой причине следующие факторы учитываются при вычислении ранга страницы: частота визитов страницы и переходов, продолжительность посещения страницы и переходов (среднее время, проведённое на странице), размер страницы в байтах, количество входящих и исходящих ссылок. Эти факторы используются в работе двух отдельных алгоритмов. Duration Based Rank (DPR) работает с длиной посещения и размером страницы, в то время как Popularity Based Page Rank (PPR) фокусируется и на пропорции продолжительности визита/размера страницы и на частоте посещений страницы.

Вкратце, в нашей рекомендательной системе архитектура состоит из последовательности элементов (см. рис. 1) в оффлайновой части. В оффлайновой обработке Page Finder анализирует страницы и фильтрует данные. Затем Session Finder конструирует сессии на основе лога кликов веб-страницы. Feature Calculator рассчитывает значения продолжительности посещения страницы и переходов, частоту визитов и переходов, а так же размер страницы. Наконец, Rank Calculator рассчитывает оценку по алгоритмам ранжирования PPR, DPR и UPR как для локальной, так и для глобальной моделей. В онлайн-части системы Recommender рекомендует top-n страниц, относящихся к последней посещённой пользователем странице, проанализированной системой.

Рисунок 1. Общая архитектура рекомендательной системы.

Главным вкладом этой работы являет то нововведение, что при расчёте значения PageRank мы уделяем особое внимание продолжительности визита по отношению к размеру страницы наряду с частотой визитов страницы и переходов (с неё). Кроме того, мы исследуем эффект ограничения количества top-n, моделируя переходы глобально (на всём веб-сайте) и локально (по основным частям сайта). Статья организована следующим образом: раздел 2 описывает смежные работы по предсказанию следующей страницы, за ним следует краткое описание модели Маркова и алгоритма PageRank. В разделе 4 представлено подробное описание предложенной модели, включая расчёт DPR и PPR. В разделе 5 описана методика оценки новых алгоритмов. В разделе 6 составлено заключение.

2. Смежные работы

В данной работе мы рассмотрим несколько исследований, схожих с нашим в ряде аспектов. В [14] Mobasher и др. работают с областью майнинга данных по использованию Веба, концентрируясь на создании ассоциативных правил из логов сетевых серверов. В их работе правила извлекаются с использованием алгоритма Apriori. Так же возможно использование вероятностных методик. Особенно часто применяется модель Маркова и её модификации, использующие историю навигационных паттернов пользователей. В основе лежит предположение, что в последовательности визитов пользователя каждая вероятность посещения одной страницы и вероятность бинарных перестановок данной последовательности определяют вероятность всей последовательности [16].

В моделях Маркова вероятности заключены в большую матрицу вероятностей, а измерения могут быть определены как комбинация страниц по уровню порядка (order level). По этой причине несколько исследований направлены на уменьшение размера модели Маркова с помощью нескольких методик сокращения (прим. пер.: имеется в виду шумоподавление посредством исключения статистически незначительных результатов). Работа [2] использует модель Маркова с сокращением ошибок, частоты визитов и степени доверия. Такая модель называется выборочной моделью Маркова. А в работе [1] рассматривается модель Маркова переменной длины, которая варьируется в зависимости от сложности поставленной задачи.

Алгоритм PageRank [3] использует ссылочную структуру страниц для поиска наиболее релевантных поисковому запросу документов. Согласно алгоритму, если входящие ссылки (т.е. страницы, указывающие на документ) страницы являются важными, то исходящие ссылки (страницы, на которые указывает сам документ) так же становятся важными. Таким образом алгоритм PageRank распределяет свой вес по указанным страницам. Существуют модели, которые привязывают PageRank к другим типам данных использования Веба, структурированным данным или содержанию Веба. В [5] представлен алгоритм Usage Based Page Rank в виде распределения оценки страниц в зависимости от частоты посещений и переходов. В работе рассматривается версия локального ранжирования ориентированного графа. В работе [9] исходный алгоритм PageRank модифицируется с учётом проведённого пользователем времени на релевантной странице. Однако в ней не учитывается ни размер страниц, ни частота посещений.

3. Общие положения

3.1 Модель Маркова и ориентированный граф

Целый веб-сайт или какая-либо его часть могут быть представлены как ориентированный граф с веб-страницами в виде узлов и переходами между страницами в виде рёбёр графа. Модель (цепь) Маркова является математической системой, которая меняет своё состояние от одного к другому в пределах конечного числа состояний [16]. Это случайный процесс, который называют беспамятным, так как следующее состояние зависит только от текущего, но не от последовательности предшествующих. Однако в k-упорядоченной модели Маркова, вероятности перехода могут быть рассчитаны по предыдущим действиям в зависимости от порядка модели. Следовательно, навигация по веб-страницам так же может быть представлена в виде ориентированного графа, который моделирует цепь Маркова путём добавления значений вероятности к рёбрам переходов. В нашем расчёте сперва используется модель Маркова первого порядка по причине высокого числа страниц в логах сервера.

3.2 Алгоритм PageRank

Алгоритм PageRank [15] моделирует весь Веб как ориентированный граф с веб-страницами в качестве узлов. В алгоритме используется ссылочная структура страниц для определения важности документов. Механизм поисковой системы Google [11] использует PageRank для рекомендации релевантных страниц пользователю путём упорядочивания документов по значению важности. Согласно алгоритму, если на страницу ссылаются важные документы, то эта страница повышает важность документов, на которые ссылается сама. Базовый расчёт PageRank описан в Формуле 1. IN(v) отражает входящие ссылки страницы v, OUT(v) – исходящие, |OUTv| – число исходящих ссылок страницы v и WS – количество элементов выборки, включающей в себя все страницы веб-сайта.

При расчёте PageRank, в особенности для крупных систем, используется итеративный метод вычислений. В итеративном методе происходит несколько циклов вычислений. В первом цикле все значения оценки приравниваются к константе (например, 1) и с каждой итерацией оценка нормализуется ~50 раз по ε = 0.85 В [6] описан алгоритм Usage Based PageRank (UPR). UPR — вариация PageRank, которая задействует данные о частоте визитов, извлечённые из предыдущих сессий пользователя. В формуле показан расчёт UPR по n количеству итераций. IN(pi) отражает набор входящих ссылок на страницу pi, OUT(pj) отражает набор исходящих ссылок страницы pj, wi — частота посещений страницы pi, а wi->j частота посещений страницы pj после pi.

4. Предложенная модель

4.1 Определение сессии

При обсуждении навигационного поведения пользователя, следует знать правильное определение термина сессия пользователя. Сессия пользователя описывает навигационное поведение (или переходы) по веб-сайту. Вся пользовательская навигация на веб-сайте может быть смоделирована в виде ориентированного графа. В Таблице 1 показан пример пользовательских сессий. В графе «переходы» Pi – это страницы, которые пользователь посещает за сессию в указанном порядке.

Таблица 1. Таблица с примером сессий переходов.

ID сессии Переходы
S1 P1 — P2 — P3 — P4
S2 P2 — P4
S3 P1 — P2 — P4
S4 P1 — P3 — P1 — P2

На Рисунке 2 изображён ориентированный граф сессий S1, S2, S3 и S4. В данном графе веса узлов и веса рёбер – это частота посещений страницы и частота переходов, соответственно. Чтобы закончить граф мы добавили узлы старта (S) и финиша (F) к графу, которые являются абстракциями и не привязываются к реальной странице в сессиях. Будем считать, что каждая сессия начинается в узле старта и завершается в узле финиша, соответственно.

Рисунок 2. Пример ориентированного графа сессий.

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

4.2 Duration Based Page Rank (DPR)

Равномерное распределение значений ранга страницы по документам, на которую она указывает является не лучшим способом расчёта PageRank для предсказания следующей страницы. При расчёте DPR это распределение просто зависит от продолжительности визитов и переходов и размера страницы. Длительность визита определяется как время, проведённое пользователем на странице после посещения предыдущей страницы в данной сессии. Так как мы анализируем общее поведение переходов и значений PageRank, при расчёте DPR мы используем средние значения продолжительности. С другой стороны, время перехода может быть определено как время, проведённое на двух страницах с последующим переходом. Например, длительность P1 -> P2 может быть рассчитана через поиск всех переходов P1 -> P2 в сессиях и извлечении времени, проведённого на P2 после посещения P1. Более того, мы учитываем соотношение проведённого на странице времени к её размеру, так как в некоторых случаях пользователь проводит больше времени на странице не из-за личного интереса, а просто из-за долгой загрузки контента. Составляя пропорцию пары значений мы пытаемся определить реальный уровень заинтересованности пользователей в веб-страницах.

Обычный подход к расчёту PageRank добавляет фактор «случайного блуждания пользователя» к значению важности страницы, который предполагает отсутствие связи между переходом на следующую страницу и контекстом текущей страницы [3]. Например, пользователь может написать произвольную URL в адресной строке. Поэтому мы определяем нормальное (последовательное) навигационное поведение как совершение визита по рёбрам, а «прыгающее» поведение как случайное посещение узлов графа. Расчёт DPR использует длительность посещения по модели случайного блуждания, а длительность перехода для нормального поведения пользователя. Расчёт DPR дан в Формуле 3.

4.3 Popularity Based Page Rank (PPR)

Расчёт Popularity Based Page Rank (PPR), показанный в Формуле 4, был создан в рамках системы популярности как переходов, так и популярности страниц, которые указывают (являются входящими ссылками) на рассматриваемую страницу. В уравнении IN(xj) отражает выборку всех входящих ссылок оцениваемой страницы.

По вышеописанному уравнению в нашей модели распределение важности страниц опирается на популярность страницы (PageP) и популярность переходов (TransitionP) на эту страницу. В нашей системе мы определяем популярность в двух измерениях: популярность по измерению страницы и по измерению переходов. В обоих измерениях популярность измеряется в рамках времени, которое пользователь провёл на странице, размера страницы и частоты посещения страницы. Наша расчётная модель создана с использованием коэффициентов по назначению важности страницы иным образом, чем распределение важности по модели PageRank, которая назначает одинаковую важность всем входящим ссылкам страницы. Рассчитывая популярность, соответствующее значение по странице и переходу рассчитываются отдельно и независимо друг от друга, но, при этом, схожим образом. Расчёт популярности страницы необходим для вычисления поведения случайного блуждания пользователя, а расчёт популярности перехода требуется для вычисления нормального навигационного поведения пользователя. Однако конечная цель в обоих подсчётах одинакова: узнать популярность узлов и рёбер. Расчёт популярностей страницы и перехода описывается Формулами 5 и 6, соответственно.

В качестве главного отличия между популярностью перехода и популярностью страницы можно рассматривать целевой способ их вычисления. Мы начинаем с пояснения, что такое измерение страницы и плавно переходим к измерению перехода. В Формуле 7 приводится расчёт частоты (посещения) страницы. wj – частота посещения страницы pj.

Расчёт средней продолжительности визита, который так же учитывает размер страницы, показан в Формуле 8. В данном уравнении di – время, проведённое на этой странице до следующего навигационного действия, а si – размер страницы.

Наконец, общий вид формулы популярности может быть записан как (9).

Уравнением 10 представлен расчёт частоты переходов. В этом уравнении элемент wj→i описан как частота перехода. Как следствие, можно рассматривать данную величину как число визитов, в которых pi следует за страницей pj. В дополнение, OUT(pj) является выборкой страниц, которые ссылаются на pj.

В уравнении 11 dj→i является продолжительностью перехода, а si – размер страницы, получаемой в результате перехода. WS – выборка веб-страниц, которая включает все страницы данного сайта. Пропорция размера продолжительности (переведи поточнее!!???) была вдохновлена [13], где, правда, она используется несколько в ином контексте.

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

4.4 Подробный расчёт PPR и DPR

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

Таблица 2. Свойства страницы в тестовых сессиях.

ID страницы Размер страницы (в байтах) Средняя длина визита (мс) Частота визитов
P1 1216 297000 3
P2 8103 231000 2
P3 303537 97000 2
P4 9039 10500 3

В Таблице 3 перечислены переходы и средние продолжительности переходов для экспериментального случая. Это искусственные данные, полученные специально в целях иллюстрации работы. Так как назначение Стартового (S) и Финишного (F) узлов является абстракцией, домысленной для завершения ориентированного графа, время переходов в данной схеме навигации не рассчитывается из серверных логов. В предложенной нами модели мы назначили данным переходам среднее значение продолжительности перехода. Допущенные значения в экспериментальном случае превышают действительные величины, однако стоит отметить, что в реальной выборке данные значения существенно ниже значений, рассчитанных для экспериментального случая.

Таблица 3. Таблица средней продолжительности переходов для экспериментальных сессий.

Переход Рассчитанная средняя длина визита (мс) Итоговая средняя длина визита (мс)
S — P1 NA 77000
S — P2 NA 77000
P1 — P2 123500 123500
P2 — P3 97000 97000
P3 — P4 10500 10500
P2 — F NA 77000
P4 — P3 NA 77000

В соответствии с этими значениями можно легко рассчитать величину ранга данных страниц. Мы приведём подробные вычисления только для одной страницы, а результаты по всем остальным будут сведены в таблицу 4. Будем рассчитывать популярность страницы P2 шаг за шагом. По уравнению популярности страницы, популярность страницы P2 принимает значение в 0.023.

Значения, рассчитанные для всех переходов в экспериментальном случае приведены в Таблице 4.

Таблица 4. Популярность переходов в экспериментальных сессиях.

Переход Частота d/s Популярность перехода
S — P1 2 63.32237 0.50000
S — P2 2 9.50265 0.07503
P1 — P2 3 15.24127 0.24069
P2 — P3 2 0.31957 0.00336
P3 — P4 1 1.16163 0.01834
P2 — F 1 1.16667 0.00614
P4 — P3 3 1.16667 0.01842

По окончании первой итерации при ε = 0.85 значения ранга в экспериментальной сессии записаны в Таблице 5. И хотя мы просто показываем результаты одного цикла в демонстрационных целях, при расчёте рекомендации следующей страницы нам будет важна стабильность значений важности. Эта стабильность обеспечивается посредством нормализации значений на протяжении последующих итераций. В Таблице 5 перечислены значения Popular Page Rank страниц после одной итерации.

Таблица 5. Значения Popular Page Rank для экспериментальных сессий.

Страница d/s Популярность страницы PPR
P1 244.24342 0.30000 0.45500
P2 28.50796 0.02334 0.141182
P3 0.3195742 0.00026 0.00080
P4 1.16163 0.00143 0.141182
S NA 0.00323 0.0320

4.5 Предсказание следующей страницы

Для предсказания следующей страницы конструируется рекомендационная выборка по предложенным алгоритмам. Главной идеей, стоящей за предсказанием следующей страницы, является создание рекомендаций из ориентированного графа, который моделируется на основе сессий из логов веб-серверов. В ориентированном графе до определённой глубины перечисляются страницы и сортируются в убывающем порядке по рассчитанному значению важности. Следовательно, метод предсказания следующей страницы может рассматриваться как модель Маркова, которая работает со значениями важности страниц вместо вероятностей. Такая модель может считаться моделью Маркова 1-го порядка, основой которой является ранг страницы. Рассмотрим пример навигационного графа, показанного на Рисунке 3. Если пользователь посещает страницу P1, то при этом рекомендационная выборка с глубиной второго уровня включает в себя страницы P2 и P3, которые отсортированы в убывающем порядке по их важности. Как следствие, рекомендационная выборка будет записана как R={P2, P3}, упорядоченная по значению PPR.

Рисунок 3. Ориентированный граф для предсказания следующей страницы.

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

5. Расчёт

В экспериментах мы изучаем и сравниваем точность работы алгоритмов UPR, DPR и PPR. Фактически мы используем те же тесты, что и в [5], однако дополнительно применяем ещё несколько методов оценки. В опытах использовались логи сервера METU с 29 мая 2010 по 18 февраля 2011. Необработанные данные содержат 5 168 361 уникальных URL страниц. Мы случайным образом разделили выборку на обучающую и проверочную. Примерно 1/3 данных была оставлена для проверки, а 2/3 стали основой для обучения. С целью удаления шума использовалось сокращение частоты (frequency pruning, [2]). Работа со страницами с более высокой посещаемостью даёт более стабильные результаты. По этой причине мы установили минимальный порог частоты визита в 10 единиц. После удаления шума в обучающей выборке осталось около 6000 страниц, а в тестовой – 2000.

В экспериментах применяется 4-ступенчатая кросс-валидация. Так же проводится оценка как в локальном [5], так и в глобальном ранжировании. Помимо сокращения частоты мы используем ещё несколько техник шумоподавления. Для того, чтобы сконструировать сессии мы группируем посещения страниц (переходы), которые проводятся с одного и того же IP-адреса и имеют одно и то же имя клиента (т.е. используемый браузер) в пределах 30 минут. Более того, мы задали правило, согласно которому время, проведённое на странице не должно превышать 10 минут. Если этот порог пройден, то создаётся новая сессия, началом которой служит последний переход. После предварительной подготовки, формулы из раздела 4 использовались с коэффициентом ε = 0.85, итогом чего является 50 итераций и фактор телепортации (jumping factor) 0.15. Ранг рассчитывается по всем трём алгоритмам (Usage Based, Duration Based и Popularity Based Page Rank). Отметим ещё раз, что вычисления проводятся до глубины второго уровня в глобальной и локальной моделях. После сокращения частотности тестовая выборка содержала около 110 сессий, а обучающая – порядка 225 сессий. По этим сессиям был построен ориентированный веб-граф в проверочной выборке с целью получения реальных значений переходов и сравнения с предсказанием. При каждой оценке мы выбирали страницу в ориентированном графе, на которую указывало 2 и более узлов. Затем алгоритмы создавали для этой страницы рекомендационную выборку.

Для сравнения предсказаний с реальными визитами мы использовали два алгоритма определения сходства, которые чаще всего используются для сравнения пары наборов данных. Первый алгоритм под названием Osim [10] вычисляет сходство двух выборок без учёта упорядоченности элементов списка. Он сравнивает число общих элементов в обеих выборках до определённого предела. Данный предел задаётся как топ-n рекомендаций для данной посещённой страницы. Формула алгоритма Osim приведена в (13), где A и B – сравниваемые выборки одинаковой длины, а n – топ-n значение сравнения. Максимальное сходство соответствует 1, минимальное – нулю.

Второй метрикой является алгоритм Ksim, который использует расстояние Кендалла (Kendall Tau Distance, [10, 5]) для сравнения сходства предсказания, полученного из обучающей выборки и реального посещения, проверенного на тестовой выборке. Дистанция Кендалла – это число попарных несоответствий между двумя выборками. Оно так же называется дистанцией сортировки простыми обменами (сортировка пузырьком, bubble sort), так как оно описывает число перестановок для приведения двух списков к одному порядку с помощью метода сортировки пузырьком. По этой метрике сходства с увеличением дистанции сходство падает. Вычисление сходства по Ksim описано в Формуле 14. Иногда сравниваемые выборки могут иметь различную длину. Длины выборок приравниваются путём использования объединяющей выборки, как показано в (14).

Дистанция τ берёт корни из вышеупомянутого алгоритма τ-расстояния Кендалла. По плану мы провели раздельные эксперименты с топ-3, топ-5 и топ-10 сравнений рекомендаций, которые оценивались Ksim и Osim по глобальному и локальному ранжированию. Результаты экспериментов по точности предсказания сведены в таблицу 6.

Таблица 6. Результаты точности.

локальный ksim глобальный ksim локальный osim глобальный osim
UPR top 3 0.69 0.68 0.70 0.73
DPR top 3 0.79 0.79 0.92 0.92
PPR top 3 0.83 0.85 0.94 0.94
UPR top 5 0.73 0.72 0.66 0.67
DPR top 5 0.84 0.84 0.69 0.69
PPR top 5 0.87 0.87 0.70 0.70
UPR top 10 0.75 0.77 0.42 0.42
DPR top 10 0.87 0.87 0.42 0.42
PPR top 10 0.89 0.96 0.42 0.42

При анализе глобальной и локальной моделей по разным метрикам схожести, кажется, что в целом эффективность графовой модели весьма ограничена. Единственным эффективным случаем является моделирование рекомендаций с помощью Ksim, которое лучше на 8% в глобальной модели по сравнению с локальной. Результаты показывают немного большую эффективность в глобальном ранжировании, поэтому в последующих экспериментах мы не будем рассматривать локальное моделирование. В [5] отмечается низкая производительность глобальной модели ранжирование. Однако в данной работе мы существенно сокращаем продолжительность вычислений путём сохранения промежуточных значений в БД. Таким образом, экономя на времени мы повышаем эффективность глобального моделирования. Чтобы оценить эффективность рекомендационной выборки, мы провели эксперименты с топ-3, топ-5 и топ-10 предсказаний, соответственно. Так как в реальных рекомендационных системах пользователям не требуется крупный список рекомендаций, мы ограничили его до максимума в 10 элементов. Опытным путём было обнаружено, что метрику Osim невыгодно использовать по мере роста рекомендационной выборки – её точность сильно снижается. И в глобальной и в локальной модели наилучшие результаты были показаны в эксперименте с топ-3 количеством рекомендаций.

Кроме того, используя метрику Osim мы обнаружили, что моделирование PPR показывает наиболее реалистичные прогнозы со степенью точности в 0.94. Моделирование DPR имеет аккуратность в 0.92 и UPR – 0.70. Мы так же сделали вывод, что задавая большее число рекомендаций для подбора, точность сильно снижается и результаты PPR и DPR приближаются к UPR. Другими словами PPR эффективнее работает по небольшим рекомендационным наборам страниц с пропорцией в 34%.

Рисунок 4. Osim с разными пределами top-n.

На Рисунке 5 показано влияние размера выборки предсказания по метрике Ksim на все три алгоритма. Как видно на графике, с увеличением размера выборки, точность алгоритмов растёт. Кроме того, мы наблюдали, что для каждого порогового значения существует разница между UPR и PPR с пропорцией примерно в 19%. Наконец, на графике 6 показаны средние значения измерений в глобальном моделировании и ограничение данных топ-3 для Ksim и Osim. Подробные результаты по каждому слою 4-слойной кросс-валидации отражены на графиках 7 и 8.

Рисунок 5. Ksim с разными пределами top-n.

Рисунок 6. Значения Ksim и Osim для top-3.

Рисунок 7. Ksim в глобальном моделировании.

Рисунок 8. Osim в глобальном моделировании.

5.1 Эффективность локального и глобального моделирования

Для оценки точности локального и глобального моделирования предсказаний мы используем t-критерий статистической проверки гипотез. По значениям каждого слоя мы оцениваем t-критерий с доверительным интервалом в 99%. В наших t-тестах используется одновыборочный попарный тест, так как мы знаем, что каждое значение получено одним и тем же измерением. Мы используем статистическую проверку на каждой итерации измерения сходства в Ksim и Osim.

Таблица 7. P-значения локального и глобального моделирования.

  ksim top-2 osim top-2 ksim top 4 osim top 4 ksim top-8 osim top-8
3-fold 0.017 0.0145 0.022 0.035 0.022 0.0141

В данных t-тестах мы определяем гипотезу h0 как «Не существует статистических различий между глобальным и локальным моделированием при вычислении точности измерения сходства.» При этому α = 0.01. Если p-значение < α, то можно сказать, что локальное и глобальное моделирование статистически важно в расчёте точности измерений сходства при доверительном интервале в 99%. В наших расчётах ни один из результатов не был меньше значения α, что означает, что гипотеза h0 принимается с уверенностью в 99%.

6. Заключение

Алгоритмы важности страниц зачастую используются как для предсказания следующей страницы, так и в системах информационного поиска. Дополнительно можно учитывать продолжительность визитов страниц, полученную из переходов [9]. Однако продолжительность посещения страницы, напрямую связанная с её размером не моделируется в алгоритме ранжирования страниц. К примеру, если пользователь ожидает загрузки крупной страницы, содержащей «тяжёлые» изображения, то, очевидно, посещение будет дольше. И хотя информация о размере страницы не отражает её популярность, пропорция продолжительности визита и размера может дать некоторую характеристику. Мы используем эту возможность в алгоритме Duration Based Page Rank (DPR). Кроме того, мы так же используем гибридный подход Popularity Based Page Rank, который учитывает и вышеописанную пропорцию и частоту посещения страниц и переходов. Мы применили несколько видов анализа для оценки работы DPR и PPR и выяснили, что эти алгоритмы имеют высокий потенциал по причине своей более высокой точности по сравнению с ранними моделями данного типа. Использование суммы всех продолжительностей визитов вместо максимальной продолжительности в расчёте средней длины визита может быть полезно в модифицированных формулах алгоритмов. Мы использовали разные варианты, однако текущий вид выдаёт оптимальные результаты. В дальнейшей работе будет учтена семантическая информация о веб-страницах, а фактор популярности будет зависеть от контекста страниц. Маркировка или контекстное объединение страниц может быть добавлена к значению популярности страницы.

Ссылки:

[1] J. Borges and M. Levene. Evaluating variable-length markov chain models for analysis of user web navigation sessions. Knowledge and Data Engineering, IEEE Transactions on, 19(4):441-452, April 2007.

[2] M. Deshpande and G. Karypis. Selective markov models for predicting web page accesses. ACM Trans. Internet TechnoL, 4:163-184, May 2004.

[3] N. Duhan, A. Sharma, and K. Bhatia. Page ranking algorithms: A survey. In Advance Computing Conference, 2009. I AC С 2009. IEEE International, pages 1530-1537, March 2009.

[4] M. Eirinaki and M. Vazirgiannis. Web mining for web personalization. ACM Trans. Internet Technol., 3:1-27, February 2003.

[5] M. Eirinaki and M. Vazirgiannis. Usage-based pagerank for web personalization. In Data Mining, Fifth IEEE International Conference on, page 8 pp., nov. 2005.

[6] M. Eirinaki, М. Vazirgiannis, and D. Kapogiannis. Web path recommendations based on page ranking and markov models. In Proceedings of the 7th annual ACM international workshop on Web information and data management, WIDM ’05, pages 2-9, New York, NY, USA, 2005. ACM.

[7] M. M. Group. Internet world stats — usage and population statistic. internetworldstats.com/stats.htm/, 2011. Last Visit: 2011 October.

[8] S. Guriduz and M. T. Ozsu. A web page prediction model based on click-stream tree representation of user behavior. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’03, pages 535-540, New York, NY, USA, 2003.

[9] Y. Z. Guo, K. Ramamohanarao, and L. Park. Personalized pagerank for web page prediction based on access time-length and frequency. In Web Intelligence, IEEE/WIC/ACM International Conference on, pages 687-690, Nov. 2007.

[10] Т. Haveliwala. Topic-sensitive pagerank: a context-sensitive ranking algorithm for web search. Knowledge and Data Engineering, IEEE Transactions on, 15(4):784-796, July-Aug. 2003.

[11] G. Inc. Google search engine. google.com, 2011. Last Visit: 2011 October.

[12] M. D. Kunder. World wide web size — daily estimated size of the world wide web. worldwidewebsize.com/, 2011. Last Visit: 2011 November.

[13] H. Liu and V. Keselj. Combined mining of web server logs and web contents for classifying user navigation patterns and predicting users’ future requests. Data Knowl. Eng., 61:304-330, May 2007.

[14] B. Mobasher, H. Dai, T. Luo, and M. Nakagawa. Effective personalization based on association rule discovery from web usage data. In Proceedings of the 3rd international workshop on Web information and data management, WIDM ’01, pages 9-15, New York, NY, USA, 2001.

[15] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, November 1999.

[16] М. К. N. Wai-Ki Ching. Markov Chains: Models, Algorithms and Applications. Springer, 2005.

Перевод материала «Investigating the Effect of Duration, Page Size and Frequency on Next Page Recommendation with Page Rank Algorithm» выполнил Роман Мурашов