Информационно-поисковые системы. Сычев А.В г. 1 Анализ гиперссылок при информационном поиске в Веб Воронежский государственный университет Факультет компьютерных наук Кафедра информационных систем

Информационно-поисковые системы. Сычев А.В г. 2 Базовые допущения при анализе гиперссылок Допущение о рекомендательности: Если страница содержит ссылку на другую, то тем самым автор первой страницы рекомендует вторую Допущение о тематической локальности: Если страницы связаны между собой гиперссылками, то с большей вероятностью они относятся к той же тематике нежели к разным. Допущение об анкерном описании: Текст связанный с анкерным тэгом ( ) гиперссылки описывает целевой документ, на который указывает гиперссылка. Замечание: гиперссылки могут содержать как дополнительную полезную информацию так и шум (в т.ч. спам)

Информационно-поисковые системы. Сычев А.В г. 3 Алгоритмы анализа гиперссылок Используются для косвенной оценки качества документов и для оптимизации работы сетевого робота. Принято выделять: Методы глобального анализа (независящие от запроса), например PageRank. Методы локального анализа (зависящие от запроса), например HITS.

Информационно-поисковые системы. Сычев А.В г. 4 Алгоритм PageRank Был предложен Сергеем Брином и Ларри Пейджем, использован для ранжирования в ИПС Google. В основу заложена модель случайного блуждания по веб-графу, которая используется для вычисления веса страницы (показатель PageRank) как вероятности ее достижимости. Страница имеет высокий PR (показатель PageRank), если на нее ссылаются страницы с высоким PR.

Информационно-поисковые системы. Сычев А.В г. 5 Модель случайного блуждания: Вначале пользователь случайным образом выбирает веб-страницу Далее на каждом шаге он Либо переходит на другую страницу, выбранную таким же случайным образом с вероятностью d Либо переходит к другой случайно выбранной странице из числа тех, которые связаны с текущей гиперссылками, с вероятностью 1-d Другими словами, средняя доля шагов до страницы a определяется через величину PR(a) Алгоритм PageRank

Информационно-поисковые системы. Сычев А.В г. 6 Расчет коэффициента PageRank Коэффициент PR для текущей веб страницы a рассчитывается по формуле: где n – количество страниц в веб-графе G C(b) – количество исходящих ссылок со страницы b D – коэффициент настройки, выбирается в пределах от 0.1 до 0.2.

Информационно-поисковые системы. Сычев А.В г. 7 Как видно, для вычисления PR(a) требуется рекурсивная процедура, которая продолжается до достижения сходимости (на практике до 100 итераций). Следует иметь в виду, что коэффициенты PR рассчитываются только один раз и не зависят от конкретных запросов. Расчет коэффициента PageRank

Информационно-поисковые системы. Сычев А.В г. 8 Алгоритм HITS Hypertext Induced Topic Search Поскольку короткие запросы приводят к выборке большого множества документов, то в рамках подхода, сформулированного в 1997 г. Кляйнбергом (Kleinberg), было предложено среди всех веб-страниц выделять два особых класса страниц: авторитеты и концентраторы.

Информационно-поисковые системы. Сычев А.В г. 9 Хорошие авторитеты – страницы, которые содержат релевантную информацию (хорошие источники информации). Хорошие концентраторы – страницы, ссылающиеся на нужные страницы (хорошие источники ссылок). Эффект взаимного усиления: Высокая авторитетность происходит из входящих ссылок от хороших концентраторов Хороший концентратор имеет исходящие ссылки на хорошие авторитеты. Авторитеты и концентраторы

Информационно-поисковые системы. Сычев А.В г. 10 Авторитеты и концентраторы Показатель авторитетности a(v) = h(u 1 )+h(u 2 )+h(u 3 ) u1u1 u2u2 u3u3 v Показатель концентрации h(u) = a(v 1 )+a(v 2 )+a(v 3 ) v1v1 v2v2 v3v3 u

Информационно-поисковые системы. Сычев А.В г. 11 На основе ранжированной выборки по запросу пользователя формируется стартовое множество S документов (порядка двухсот первых документов из выданного списка). Путем использования входящих и исходящих ссылок на документы из S строится расширенное множество T документов (не более 50-ти для каждого стартового документа), находящихся на расстоянии 1 ребро от стартовых узлов в веб-графе. Простой учет количества входящих и исходящих ссылок на документы не является эффективным, поэтому далее следует итерационная процедура расчета показателей авторитетности и концентрации для всех узлов множества T. Алгоритм HITS

Информационно-поисковые системы. Сычев А.В г. 12 Процедура расчета весов авторитетности и концентрации Все веса инициализируются значением 1. Повторяется цикл до достижения сходимости: Для узла u рассчитывается вес авторитетности Для узла u рассчитывается вес концентрации После каждой итерации выполняется нормализация весов

Информационно-поисковые системы. Сычев А.В г. 13 Так как алгоритм фактически вычисляет главные собственные векторы двух матриц, то векторы H и A должны сходиться, хотя точное значение числа итераций не известно. На практике вектора сходятся очень быстро. Процедура расчета весов авторитетности и концентрации

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

Информационно-поисковые системы. Сычев А.В г. 15 Алгоритм HITS Расширения ARC (Automated Resourse Compilation) Расширение стартового подмножества за счет узлов на расстоянии 2 ребер Использование текста анкерных тэгов (и их окружения) при расчете весов SALSA (Stochastic algorithm for link structure analysis).

Информационно-поисковые системы. Сычев А.В г. 16 Различие между PageRank и HITS PageRank вычисляет веса для всех проиндексированных веб-страниц до запросов. HITS применяется только к веб-страницам, выданным по конкретному запросу пользователя. HITS находит авторитеты и концентраторы, PageRank – только авторитеты. PageRank – требует нетривиальных вычислений, HITS – простой алгоритм, но очень затратный по времени вычисления

Информационно-поисковые системы. Сычев А.В г. 17 Литература S.Brin, L.Page "The anatomy of a large-scale hypertextual web search engine". Proc. 7th World Wide Web Conf. (WWW7), p. 107–117. S.Brin, L.Page "The anatomy of a large-scale hypertextual web search engine". Proc. 7th World Wide Web Conf. (WWW7), p. 107–117 L.Page, S.Brin, R.Motwani, T.Winograd. "The PageRank citation ranking: Bringing order to the Web". Stanford, Digital Library Technologies, Working Paper , L.Page, S.Brin, R.Motwani, T.Winograd. "The PageRank citation ranking: Bringing order to the Web". Stanford, Digital Library Technologies, Working Paper , 1998 M. Kleinberg "Authoritative sources in a hyperlinked environment". Journal of the ACM, 46(5):604–632, M. Kleinberg "Authoritative sources in a hyperlinked environment". Journal of the ACM, 46(5):604–632, 1999.

Информационно-поисковые системы. Сычев А.В г. 18 M.Henzinger "Link Analysis in Web Information Retrieval". Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, M.Henzinger "Link Analysis in Web Information Retrieval". Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, A.Borodin, G.O.Roberts, J.S.Rosenthal, P.Tsaparas"Link Analysis and Experiments". ACM Transactions on Internet Technology, Vol.5, No.1, February 2005, P. 231–297. A.Borodin, G.O.Roberts, J.S.Rosenthal, P.Tsaparas"Link Analysis and Experiments". ACM Transactions on Internet Technology, Vol.5, No.1, February 2005, P. 231–297.Литература