< Попер   ЗМІСТ   Наст >

Алгоритм HITS

Алгоритм HITS (Hyperlink Induced Topic Search), предложенный Дж. Клейнбергом, обеспечивает выбор из информационного массива лучших "авторов" (первоисточников, на которые введут ссылки) и "посредников" (документов, от которых идут ссылки цитирования). Понятно, что страница является хорошим посредником, если она содержит ссылки на ценные первоисточники, и наоборот, страница является хорошим автором, если она упоминается хорошими посредниками.

Для каждого документа

рекурсивно вычисляется его значимость как автора и посредника

по формулам:

Если ввести понятие матрицы инциденций A, элемент которой равен единице, когда документ dt содержит ссылку на документ dy, и нулю в противном случае, то алгоритм HITS обеспечивает выбор наиболее авторитетных документов (авторов или посредников). Эти документы соответствуют собственным векторам матриц AAT и ATA с наибольшими модулями собственных значений (здесь AT -транспонированная матрица A ).

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

Для решения этой проблемы как альтернатива стандартному алгоритму HITS был предложен алгоритм PHITS. В рамках этого алгоритма предполагается: D—множество цитирующих документов, C — множество ссылок, Z—множество классов (близких по какому-нибудь критерию документов), на которые разделяются документы. Предполагается также, что событие d є D (то, что выбранный для рассмотрения наугад документ является документом d ) происходит с вероятностью P(d).

Условные вероятности P(c | z) (вероятность того, что ссылка из класса z - это c) и P(z| d) (вероятность того, что выбранный документ д относится к классу г) используются для описания зависимостей между наличием ссылки с є С, фактором г є Z и документом д є О.

Оценивается функция правдоподобия:

где

Цель алгоритма РНГТБ состоит в том, чтобы подобрать Р(^), Р(с z), Р(дг) , чтобы максимизировать ДД С).

После этого:

Р(с z) - ранги авторов;

P(d z) - ранги посредников.

Для вычисления рангов необходимо задать количество факторов в 2, и тогда Р(с z) будет характеризовать качество страницы как автора в контексте тематики z. К недостаткам метода надо отнести то, что итеративный процесс чаще всего останавливается не на абсолютном, а на локальном максимуме функции правдоподобия L. Вместе с там в ситуациях, когда в множестве найденных веб-страниц нет явного доминирования тематики запроса, PHITS превосходит алгоритм HITS.

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

 
< Попер   ЗМІСТ   Наст >