Методы предварительной обработки данных для алгоритма Клейнберга А. Корявко И. Некрестьянов

Зачем нужно ранжировать? Большой объем доступной информации. Низкая селективность запросов пользователей. Нежелание пользователей тратить время на анализ результата.

Источники информации Содержимое документа – Совсем не работают для коротких запросов Поведение других пользователей (DirectHit) – Плохо масштабируемо по числу запросов Структура Веб – Глобальные (PageRank) – Локальные (алгоритм Клейнберга - HITS)

Тематические сообщества Сообщество - множество страниц близкой тематики, где со страницы большая часть ссылок ведет на другие страницы этого же сообщества Роли страниц - первоисточники и посредники

Подход Клейнберга Как считать ранг? Первоисточник ценнее, если на него ссылаются авторитетные посредники Посредник лучше, если он цитирует хорошие первоисточники Где считать ранг? Окрестность тех страниц, которые надо ранжировать

BaseSet RootSet Алгоритм Клейнберга 1. Находим множество страниц для ранжирования 2. Строим их окрестность (BaseSet) 3. Итеративно вычисляем ранги A=S T H; H=SA

Достоинства и недостатки Учитывает тематический контекст (зависит от запроса пользователя) Может найти новые результаты (высоко ранжированные страницы не из RootSet) Проблема смещения тематики (неудачный BaseSet)

Модификации HITS Модификация исходного набора данных Модификация метода вычисления рангов (использование иерархической структуры документа) Анализ неглавных тематических сообществ

Рассматриваемые методы предварительной обработки Постраничная обработка – Близость к исходному запросу – Тематическая близость к RootSet Обработка на уровне отдельных ссылок – Удаление внутридоменных ссылок – Тематическая схожесть страниц Итеративные методы – Сокращение – Уточнение

Набор данных Базовая поисковая система – Яндекс Запрос|RootSet||BaseSet| атеизм электронные библиотеки русский tex программирование crack ленинград

Критерии оценки качества Релевантность страниц - g(d) – Автоматическая оценка (tfidf) – Экспертная оценка (от 0 до 1, шаг 0.1) Оценка ранжирования – Совокупная выгода – Обесцениваемая совокупная выгода Характеристики матрицы

Результаты для запроса атеизм МетодАвтоматический выбор Экспертная оценка Главний вектор ||S|| M0 34( )35( ) M2 0( )8( ) M3 49( )17( ) M1+M3 15( )24( ) M3+M4 12( )

Результаты для запроса атеизм M3 – отсутствие корреляции. M2, M3+M4 – есть корреляция. M1+M3 – хорошее главное сообщество.

Результаты итеративных подходов После второй итерации получен лучший результат Улучшается качество главного сообщества Нет сходимости

Типы сообществ Гетерогенные Сайт с посредниками сам не содержит полезной информации Первоисточники – конкуренты и друг на друга не ссылаются Гомогенные Сайты содержат и оригинальные материалы, и подборки ссылок

Дальнейшие планы Расширение набора тестовых запросов Удаление ссылок по результатам выявления шаблонов оформления страниц Критерий завершения итеративных подходов Исследование гомогенных сообществ Применение теории возмущений для формального анализа стабильности