Особенности ранжирования текстовых и гипертекстовых документов

Применение метода латентного семантического индексирования к ранжированию выдачи информационно-поисковых систем, основанному на цитировании.

Алгоритм HITS обеспечивает выбор из информационного потока лучших «авторов» (первоисточников) и «посредников» (документов от которых идут ссылки цитирования). Понятно, что страница является хорошим посредником, если она содержит ссылки на ценные первоисточники, и наоборот, страница является хорошим первоисточником, если она упоминается хорошими посредниками.

Для каждого документа рекурсивно вычисляется его значимость как первоисточника ap и посредника hp по формулам:

Если ввести понятие матрицы инциденций A, элемент которой аij равен единице, если документ Di содержит ссылку на документ Dj, и нулю в противном случае, то алгоритм HITS обеспечивает выбор наиболее авторитетных документов документов (первоисточников – ap или посредников - hp), которые предположительно соответствуют собственным векторам матриц AAT и ATA с наибольшими модулями собственных значений. В этом смысле алгоритм HITS эквивалентен LSI.

Действительно, пусть, в соответствии с сингулярным разложением A= USVT, S – квадратная диагональная матрица. Тогда AAT = USVT VSUT = US I SUT = US2UT, где S2 – диагональная матрица с элементами sii

2. Очевидно, как и при LSI, собственные векторы, соответствующие наибольшим сингулярным значениям AAT и/или ATA будут соответствовать наиболее статистически важным авторам и/или посредникам.

Алгоритм вычисления рангов HITS влечет рост рангов страниц при увеличении количества и степени связанности страниц соответствующего сообщества. В этом случае в результат выдачи информационно-поисковой системы может попасть много страниц на темы, не соответствующие информационной потребности пользователя, то есть часть выдаваемых результатов, соответствующих требуемой теме, может оказаться не доминирующей. Это обуславливает присвоениe высших рангов страницам на тему, не требуемую пользователем, т.е. происходит смещение тематики (topic drift).

Как некоторое расширение стандартного алгоритма HITS рассматривается алгоритм PHITS - Probabilistic HITS, авторы - Д. Кон (D. Cohn) и Х. Чанг (H. Chang). Предполагается: D – множество цитирующих документов, C – множество ссылок, Z - множество классов (факторов).

Пусть d Є D, генерируется с вероятностью P(d).

Условные вероятности P(c|zk) и P(zk|d) для описания зависимостей между наличием ссылки c Є C, латентным фактором zk Є Z и документом - d.

Оценивается (максимизируется функция):

L(D,C) = П P(d,c) = П c є C, d є D P(d)P(c|d),

где

P(c|d) = Σ k P(c|zk) P(zk|d). __

Задача состоит в том, чтобы подобрать P(zk), P(c|zk), P(zk|d), чтобы максимизировать L(D,C).

После этого:

P(c|zk) – ранги первоисточников

P(d|zk) – ранги посредников.

Для вычисления рангов необходимо задать количество факторов в Z, и тогда P(c|zk) будет характеризовать качество страницы как “первоисточника” в контексте тематики zk. Кроме того, итеративный процесс зачастую останавливается не на абсолютном, а на локальном максимуме функции правдоподобия L.

В ситуациях, когда в множестве Web-страниц нет явного доминирования тематики запроса PHITS ведет себя лучше HITS.

PageRank:

Алгоритм PageRank близок по идеологии к литературному индексу цитирования и рассчитывается с учетом количества ссылок из других документов на данный документ. PageRank, в отличие от литературного индекса цитирования, не считает все ссылки равными.

Объяснение принципа подсчета ранга Web-страницы PageRank следующее. Рассматривается процесс, при котором пользователь сети Internet открывает случайную Web-страницу, из которой переходит по случайно избранной гиперссылке. Потом он перемещается на другую Web-страницу и снова активизирует случайную гиперссылку и т.д., постоянно переходя от странице к странице, никогда не возвращаясь. Иногда ему такое блуждание надоедает, и он снова переходит на случайную Web-страницу - не по ссылке, а набрав вручную некоторый URL. В этом случае, вероятность того, что блуждающий в Сети пользователь перейдет на некоторую определенную Web-страницу - это ее ранг - PageRank. PageRank Web-страницы тем выше, чем больше других страниц ссылается на нее, и чем эти страницы популярнее.

Пусть есть n страниц T={T1, Т2, …, Tn}, которые ссылаются на данный документ (Web страницу А), а C(A) — общее число ссылок с Web-страницы А на другие документы. Пусть d (damping factor) - это вероятность того, что пользователь, пересматривая какую-нибудь Web страницу из множества Т, перейдет на страницу А по ссылке, а не набирая ее URL или другими средствами. Тогда вероятность продолжения Web-серфинга не используя гиперссылок, путем ручного введения адреса (URL) из случайной страницы будет составлять 1-d. Индекс PageRank PR(A) для страницы А вычисляется по формуле:

PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)).

Таким образом индекс легко подсчитывается простым итерационным алгоритмом.

Несмотря на расхождение данных алгоритмов, в них общее то, что авторитетность (вес) узла зависит от веса других узлов, а уровень "посредника" зависит от того, насколько авторитетные соседние узлы. Кроме того, оба алгоритмы используют вычисление собственных векторов для матриц взаимосвязи (инциденций) соответствующих Web-страниц. Расчет авторитетности отдельных документов сегодня широко используется в таких применениях, как определение порядка сканирования документов, ранжирование результатов поиска, формирование тематических сюжетов и т.п. Формулы расчета авторитетности постоянно совершенствуются. Предполагается, что применение этих алгоритмов в будущем станет еще более эффективным, так как гиперссылки между документами постоянно оптимизируются с учетом предпочтений пользователей и ориентируясь на существующие методы их обработки поисковыми системами.