Марковские модели широко используются для моделирования поведения пользователей в навигации на сайтах. Структура ссылок на сайте может рассматриваться как источник сети. Применяя библиографические общие цитаты и связи для анализа и построения Марковской модели из log-файла на сайте, мы предлагаем алгоритм кластеризации, который называется CitationCluster для кластеризации концептуально связанных страниц. Результат кластеризации используется для построения концептуальной иерархии сайта. Марковские модели интегрированы с иерархией для оказания помощи навигации пользователей на сайте и лежат в основе прогнозирования.
Просматривая процесс навигации каждого пользователя Интернета на сайте в виде Марковской цепи, мы можем построить модель Маркова сайта, с использованием переходов предыдущих пользователей по гиперссылкам, как накопившегося поведения навигации. Мы построим граф ссылок, в котором страницы – это узлы, гиперссылки между страницами являются связями между узлами, и количество проходов по гиперссылкам в прошлом пользователями — веса по ссылкам из из log-файла на Web-узле [8]. Мы предполагаем, что большинство пользователей переходят по ссылкам на страницы, которые их заинтересовали. Просматривая веса по ссылкам, с которыми предыдущие пользователи неявно связывали свои предпочтения в следующей гиперссылке на каждой странице [8], можно использовать граф ссылок для расчета матрицы вероятностей перехода, содержащую одношаговые вероятности перехода между состояниями в модели Маркова. Библиографический анализ — количественный метод для изучения источников между научной литературой. Almind, T. C. и Ingwersen, P. [1] утверждают, что World Wide Web (WWW) представляет собой сеть общих источников и библиографического анализа, поэтому описанный подход может быть применен к WWW. Гиперссылки между Web-страницами, концептуально похожи на ссылки цитат. Одна страница ссылается на другую, как в библиографии, один документ ссылается на другой. На основании сходства между структурой Web ссылок и сбора общих источников и цитируемых научных работ, мы стараемся расширить совместную цитированность и анализ связи с моделью Маркова. Мы определим сходство совместно цитированных двух Web-страниц, как расстояние, основанноге на одношаговой вероятности перехода на «входные» адреса, связное сходство этих двух страниц, и основанных на расстоянии из «выходных» ссылок. Мы предлагаем иерархический алгоритм кластеризации названый CitationCluster Web –страниц для концептуальной формы кластеров на основе сходства их общих источников и связи. На основании отношений цитированности между кластерами и не кластерированной отдельной страницы, мы можем построить концептуальную иерархию сайта, который имеет иерархическую организацию информации.
В работе [7], мы представили PageRate алгоритм дающий поиск результатов оценок, основанных на поведении навигации предыдущих пользователей на сайтах, и PageClustering алгоритм для кластеризации Web-страниц с аналогичными «входными» ссылками в форме понятийных категорий, для интеграции с результатами поиска. В работе [6], мы использовали Марковские модели, чтобы найти концептуальную кластеризацию Web-страниц, основанных на сходстве ссылок между Web-страницами. В [8], мы использовали алгоритм матрицы переходов для сжатия модели Маркова сайта для оптимального размера и эффективного прогнозирования ссылок на сайте. Sarukkai [4], использует модель Маркова, основанную на методе прогнозирования ссылок на сайтах. Kleinberg [2] предложил HITS-алгоритм нахождения и узлов на основе структуры Web-ссылок. Thimbleby [5], использует Марковские модели для исследования юзабилити сайта
У нас есть две основные цели нашего исследования. Во-первых, это использование модели Маркова построеную из структуры ссылок на сайте для кластеризации концептуально связанных Web-страниц. Во-вторых, это использование результатов кластеризации для построения концептуальной иерархии сайта для интеграции с прогнозированием навигации пользователей на сайте.
На основании сходства гиперссылок между страницами и ссылками между научной литературой, мы стараемся увеличить общую цитированность и связи анализа структуры ссылок на сайте. Мы определяем сходство совместной цитированостьи и связи двух Web-страниц, как расстояние, основанное на сходстве переходных вероятностей на их «по»-ссылки и «из»-ссылки, соответственно. Сходство общих цитат и связей служат для измерения концептуальных связей между Web-страницами. Мы предлагаем CitationCluster, трех-этапный агломерационный иерархический алгоритм кластеризации, чтобы найти три варианта концептуальнных кластеров, а именно: навигационные, категориальные и справочные кластеры. Навигационные кластеры определяются как группа Web-страниц, иерархически сгруппированые вместе, на основе сходства их совместных источников и связи. Категориальные кластера определяется как группа Web-страниц, иерархически сгруппированы в блоки на основе их сходство с общими источниками. Справочные кластера определяется как группа Web-страниц, иерархически сгруппированые в блоки на основе сходства их совместных источников. Мы рассчитываем матрицу сходства, состоящая из сходства общих источников и связи между каждой парой страниц из модели Маркова. Во-первых, мы используем сходства общих источников и связи с кластером Web-страниц для навигационных кластеров. Во-вторых, мы используем подобность общей цитированности с кластером Web-страниц для категориальных кластеров. В-третьих, мы используем подобие связией кластера Web-страниц для справочных кластеров. Каждая группа получает название по концептуальному изучению [3], чтобы заключить содержание всех страниц кластера. Есть также не кластерированные страницы при кластеризации.
Мы используем: навигационные, категориальные и справочные кластеры, а не кластерированные страницы выступают в качестве строительных блоков построения концептуальной иерархии сайта для навигации. Мы создаем семантические виртуальные связи (в отличие от физического гиперссылки) между строительными блоками на основе семантических отношений между ними отраженными в вероятности перехода между ними в модели Маркова. Для иерархического сайта, концептуальная иерархия домашняя страница выступает в качестве основной, которая ссылается на множество кластеров и страниц на общем уровне концепции. Каждый из них ссылается на множество кластеров и страниц на более или менее общем уровнем концепции, и так далее, до набора кластеров и страниц на самые специфические уровни концепции. Концептуальноая иерархия визуализируется в прототип под названием ONE (Online Navigation Explorer) [6] для оказания помощи навигации пользователей на Web-сайте.
Учитывая текущую страницу пользователя и множество посещенных страниц и кластеров, как историю, мы можем использовать модель Маркова для расчета вероятности посещения других кластеров и страниц в концептуальной иерархии прогнозирования. В ONE, мы визуализируем историю пользователей путем расширения кластерного содержания посещенных страниц, выделяя текущую страницу, и использовать значки указывающих на порядок их посещений. Мы выделяем страницы и кластеры с высокой вероятностью посещаемости в будущем, увеличиваем уровень кластеров со ссылками на страницы и кластеры с высокой вероятностью, и используем значки, чтобы показывать разные уровни возможностей.
Мы построили модель Маркова с помощью файла Лог из сайта Олстерского Университета. Алгоритм CitationCluster был применена модель Маркова. Результаты кластеризации были использованы для создания концептуальной иерархии сайта, который визуализируется в одном и комплексного прогнозирования со ссылкой на помощь навигации пользователя. Члены нашей группы использовали ONE для навигации на сайте университета. По сравнению с прогнозированием [4,8], концептуальная иерархия дает четкое представление о потоке перемещений нахождения на сайте, а также семантические отношения между посещенными и рекомендованными страницами/кластерами. Мы заметили, что наша работа внесла свой вклад в повышение эффективности и точности в поиске Web-страниц, люди заинтересованы в анализе визитов на сайт с помощью ONE.
Иерархический алгоритм кластеризации называется CitationCluste. Он предлагается кластеризация концептуально связанных Web-страниц на Web-узле на основе сходства общих цитат и связей между Web-страницами, определенных на переходных вероятностей на их «по»-ссылкам и «из»-ссылкам, соответственно. Результаты кластеризации затем используются для построения концептуальной иерархии сайта. Наконец, базирует прогнозирование модель Маркова интегрированная с иерархией, чтобы помочь пользователю в навигации с помощью прототипа под названием ONE.
Прогнозирования в ONE должно быть оценено большой группой пользователей. Мы планируем, выбрать группу пользователей, включая студентов, сотрудников университета Ольстера, и людей за пределами университета, чтобы использовать ONE. Их взаимодействие с ONE, будут анализироваться. Мы планируем использовать log-файлы из некоторых коммерческих сайтов, чтобы построить модель Маркова для связи прогнозирования и оценки результатов на различных группах пользователей.
Мы хотели бы поблагодарить Mark Bernstein и Jayne Klenner за их ценные комментарии к предыдущей версии этого документа.
1. Almind, T. C. and Ingwersen, P., (1997). Informetric Analysis on the World Wide Web: Methodological Approaches to “Webometrics”. Journal of Documentation 53, no. 4: 404-426.
2. Kleinberg, J. M., (1999). Authoritative sources in a hyperlinked environment. Journal of ACM, 46:604-632.
3. Perkowitz, M. and Etzioni, O., (1999). Adaptive web sites: conceptual cluster mining. In Proceedings of IJCAI 1999.
4. Sarukkai, R. R., (2000). Link prediction and path analysis using Markov chains, WWW9, Amsterdam.
5. Thimbleby, H., Cairns, P., and Jones, M., (2001). Usability Analysis with Markov Models. ACM Transactions on Computer-Human Interaction, Vol. 8, No. 2, pp. 99-132.
6. Zhu, J., (2001). Using Markov Chains for Structural Link Prediction in Adaptive Web Sites. In Proc. of User Modeling 2001, pp. 298-300.
7. Zhu, J., Hong, J., and Hughes, J., (2001). PageRate: Counting Web Users' Votes. In Proc. of ACM Hypertext’01, pp. 131-132.
8. Zhu, J., Hong, J., and Hughes, J., (2002). Using Markov Chains for Link Prediction in Adaptive Web Sites. In Proc. of Soft- Ware 2002: Computing in an Imperfect World, Springer-Verlag LNCS 2311, pp. 60-73.