© ElVisti Лекция 8 Ранжирование результатов поиска Дмитрий Владимирович ЛАНДЭ МЕЖДУНАРОДНЫЙ СОЛОМОНОВ УНИВЕРСИТЕТ

© ElVisti2 Задачи ранжирования Необозримость возможного списка отклика ИПС приводит к идее сортировки всей базы данных по определенным параметрам, которая заменяет поиск. Сортировка результатов поиска по уровню релевантности (например, не подходит для булевой модели). Перспективный путь – использование многопрофильных шкал, сформированных на основании некоторых метаданных, использование кластерного анализа. Реализация сюжетных цепочек в тематических информационных массивах и их взвешивание рассматриваются как один из алгоритмов ранжирования. Ранжирование - процесс, при котором поисковая система: - принимает запрос пользователя; - находит все подходящие веб-страницы; и - выстраивает их в определенном порядке по принципу наибольшего соответствия конкретному запросу. Выведение рейтинга зависит от алгоритма ранжирования, которым пользуется поисковая машина. (Глоссарий.ru).

© ElVisti3 Особенности ранжирования Текстовые документы – - по сети, образуемой контекстными ссылками, - по уровню релевантности, - по времени публикации, - по многопрофильным рангам: - территории - автора - источника Гипертекстовые документы (дополнительно) - - по сети, образуемой гипертекстовыми ссылками - по метаданным

© ElVisti4 Алгоритм Клейнберга - HITS Применение метода латентного семантического индексирования к ранжированию выдачи информационно-поисковых систем, основанному на цитировании. Алгоритм HITS обеспечивает выбор из информационного потока лучших «авторов» (первоисточников) и «посредников» (документов от которых идут ссылки цитирования). Понятно, что страница является хорошим посредником, если она содержит ссылки на ценные первоисточники, и наоборот, страница является хорошим первоисточником, если она упоминается хорошими посредниками. Для каждого документа рекурсивно вычисляется его значимость как первоисточника a p и посредника h p по формулам: a p = h q, h p = a q Дж. М. Клейнберг,

© ElVisti5 Матрица инциденций Матрица инциденций A = {а ij }, а ij = 1, если документ D i содержит ссылку на документ D j, и а ij = 0 в противном случае. Алгоритм HITS обеспечивает выбор наиболее авторитетных документов (первоисточников – a p или посредников - h p ), которые предположительно соответствуют собственным векторам матриц A T A и AA T с наибольшими модулями собственных значений, соответственно. Предполагается, что процедура формирования анализируемого множества документов влечет доминирование документов нужной тематики в этом множестве.

© ElVisti6 Эквивалентность HITS и LSI Алгоритм HITS эквивалентен LSI. Действительно, A= USV T, где S – квадратная диагональная матрица. Тогда: AA T = USV T VSU T = US I SU T = US 2 U T, где S 2 – диагональная матрица с элементами s ii 2. Как и при LSI, собственные векторы, соответствующие наибольшим сингулярным значениям AA T и/или A T A будут соответствовать наиболее статистически важным авторам и/или посредникам.

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

© ElVisti8 Вероятностный HITS - PHITS Как некоторое расширение стандартного алгоритма HITS рассматривается алгоритм PHITS - Probabilistic HITS, авторы - Д. Кон (D. Cohn) и Х. Чанг (H. Chang). Предполагается: D – множество цитирующих документов, C – множество ссылок, Z- множество классов (факторов). Пусть d Є D, генерируется с вероятностью P(d). Условные вероятности P(c|z k ) и P(z k |d) для описания зависимостей между наличием ссылки c Є C, латентным фактором z k Є Z и документом - d. Оценивается (максимизируется функция): L(D,C) = П P(d,c) = П c є C, d є D P(d)P(c|d), где P(c|d) = Σ k P(c|z k ) P(z k |d)

© ElVisti9 PHITS – основная задача Задача состоит в том, чтобы подобрать: P(z k ), P(c|z k ), P(z k |d), чтобы максимизировать L(D,C). После этого: P(c|z k ) – ранги первоисточников P(d|z k ) – ранги посредников. Недостатки и преимущество PHITS: Для вычисления рангов необходимо задать количество факторов k в Z, и тогда P(c|z k ) будет характеризовать качество страницы как первоисточника в контексте тематики z k. Кроме того, итеративный процесс зачастую останавливается не на абсолютном, а на локальном максимуме функции правдоподобия L. В ситуациях, когда в множестве Web-страниц нет явного доминирования тематики запроса PHITS ведет себя лучше HITS.

© ElVisti10 Алгоритм PageRank В отличие от литературного индекса цитирования не все ссылки считаются равнозначными. PageRank подсчитывает общий "авторитет" документа, в то время как HITS определяет "авторитет" документа для конкретной темы. Алгоритм был развит в 1996 году в Стенфордском Университете Лэрри Пейджем (Larry Page) и Сергеем Брином (Sergey Brin). PageRank – система ранжирования, используемая в Google.

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

© ElVisti12 PageRank - пояснение Пусть есть n страниц T={T 1, Т 2, …, T n }, которые ссылаются на данный документ (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)). Индекс легко подсчитывается простым итерационным алгоритмом.

© ElVisti13 Весовой алгоритм ранжирования текстовых сообщений В этом алгоритме ключевым словам из документов, выдаваемых информационно-поисковой системой, приписывается некоторый вес. Вес документа определяется как средний вес входящих в него значимых ключевых слов (значимость отдельных слов определяется, например по принципу TF*IDF). Очевидно, чем меньше этот вес, тем документ более уникальный.

© ElVisti14 Ранжирование по Хиршу В 2005 г. в области наукометрии произошло важное событие - физиком Йоргом Хиршем был предложен новый метод оценки научных публикаций, претендующий на более высокую точность и, что особенно важно, объективность по сравнению с получившим широкое распространение индексом цитирования. Метод состоит в подсчете числа h публикаций одного автора, на которые имеется не менее h ссылок. Учёный имеет индекс h, если h из его N p статей цитируются как минимум h раз каждая, в то время как оставшиеся (N p – h) статей цитируются менее чем h раз каждая. N tot ~ a h 2. Йорг Хирш

© ElVisti15 Интерпретация принципа Хирша для сайтов Параметр Хирша для сайта-источника равен максимальному количеству дней в месяце (H), в течение которых было зафиксировано не менее H внешних ссылок на данный сайт (параметр на практике подсчитывается для новостных сайтов). Рейтинг Хирша характеризует как регулярность ссылок на источники, так и количество этих ссылок. Показатель Хирша учитывает стабильность авторитетности источника на протяжении длительного периода.

© ElVisti Спасибо за внимание! Ландэ Д.В МЕЖДУНАРОДНЫЙ СОЛОМОНОВ УНИВЕРСИТЕТ Киев, Украина