Слайд 2Информационный поиск (ИП)
Цель: удовлетворить информационные потребности пользователя
Обсуждаемые темы:
Модели ИП
Критерии оценки качества поиска
Поиск
в Интернет
Поиск по значимости
Слайд 3Модель ИП:
Логическое представление документов
Логическое представление запросов
Framework моделирования представлений документов и запросов, их
взаимосвязей
Ранжирующая функция
Слайд 4Классификация моделей
Булева модель
(теория множеств и булева алгебра)
Векторная модель
(векторные пространства и
линейная алгебра)
Вероятностная модель
(множества, теория вероятностей)
Классические модели подразумевают независимость слов (термов)
Слайд 5Булевы модели
Модель на нечетких множествах
(с термом запроса ассоциировано нечеткое множество документов)
Расширенная булева
модель
Расширяет булеву модель для использования весов термов
Обобщает модель на нечетких множествах и векторную модель (выбирая метрику)
Слайд 6Векторные модели
Обобщенная векторная модель
(учет корреляции между термами)
Латентно-семантический анализ
(отображение документов и запросов
в пространство концепций)
Нейронные сети
(нейроны —термы документов и документы,
многошаговое распространение сигнала)
Слайд 7Вычисление весов термов
Частота терма в документе
Обратная частота термов в коллекции
Вычисление весов
Слайд 8Нормализация весов
Преимущества длинных документов:
Больше различных термов
Выше частоты термов
Методы нормализации:
по максимальной частоте
по длине
вектора весов всех термов в данном документе
по длине в байтах
Слайд 9Вероятностные модели
Вероятностный принцип
Оценить вероятность того, что документ будет интересен пользователю
Модель сетей
вывода (inference networks)
На основе сети Байеса
Могут имитировать булеву модель, некоторые векторные модели, обратную связь
Реализована в Inquery
Слайд 10Моделирование языка
Zipf’s Law
Heaps’ Law
Слова
F
V
Размер текста
Слайд 11Предварительная обработка текста
Лексический анализ
Исключение стоп-слов
Выделение основ слов (stemming)
Выбор термов для индексирования
(например
только существительных)
Тезаурусы
(выделение категорий термов)
Слайд 12Языки запросов
Запросы по ключевым словам
однословные
контекстные
логические
на естественном языке
Запросы по шаблонам
Протоколы запросов (Z39.50, WAIS)
Слайд 13Уточнение запросов:
Изменение весов термов запроса
Добавление новых термов в запрос
Основные подходы:
Обратная связь (Relevance
feedback)
Автоматический локальный анализ
Автоматический глобальный анализ
Слайд 14Критерии оценки
Точность
Полнота
Процент мусора
A
R
S
Слайд 15Критерии оценки (2)
Средняя точность
Интерполяция
По числу документов
P@20, P@50, p@100
Слайд 16Критерии оценки (3)
Точность на уровне обнаружения заданного числа релевантных документов
Точность среди первых
R возвращенных, где R – число реально релевантных
(R-precision)
Гистограммы точности
(сравнение эффективности двух алгоритмов на каждом запросе)
Слайд 17Критерии оценки (4)
Среднее гармоническое (b = 1)
(компромисс между точностью и полнотой)
E-мера
(учет
предпочтений пользователя)
Слайд 18Критерии оценки (5)
Пользовательские критерии:
Коэффициент покрытия
(процент уже известного среди найденного)
Коэффициент новизны
(отношение нового к
уже известному)
Относительная полнота
(отношение нового к ожидаемому)
Слайд 19Особенности поиска в Интернет
Огромный размер
> 1 миллиарда документов (февраль 2000)
> 75 миллионов
узлов
Короткие запросы ( < 2 слов)
Почти не используются продвинутые возможности языка запросов
Много изменений в данных (40% в месяц)
Слайд 21Оценка качества индекса
Не все страницы одинаково важны
Метрики
Суммарная значимость всех страниц
Средняя значимость страниц
Метод случайной прогулки
Как проверить наличие страницы в индексе?
Как оценить значимость страницы?
Слайд 22TREC и Web
Коллекция VLC2:
100Гб, 18.5 миллионов документов
Короткие запросы из TREC (2.5
слова)
5 поисковых систем
Слайд 23Задачи ИП в Интернет
Обнаружение дубликатов
Интеллектуальные сетевые роботы
Борьба с опечатками
Levenshtein(survey, surgery) = 2
LCS(survey,
surgery) = surey
Метапоиск
Как делать слияние результатов (data fusion)?
Слайд 24Классификация типов копий
Повторение содержания (1) и структуры (2)
Слайд 25Оценка повторения структуры
Построение описаний URL
yahoo.com/ref/art/news.htm
(yahoo,com) (ref, art, 0) (art, news, 1) (news,
htm, 2)
Сокращение числа кандидатов
(стоп-слова, нехарактерные пары)
Вычисление весов (IDF)
Вычисление оценки похожести узлов
Уровни похожести: 100%, 50%, 0%
Слайд 26Оценка повторения содержания
Выбор страниц для проверки
Проверка на полную идентичность
Вычисление оценки близости:
S(A) —
множество k-грамм документа A
Слайд 27Сетевые роботы
Области применения:
Построение индексов
Сбор статистики
Поиск ресурсов
Исследование структуры Интернет
Проверка целостности ссылок
Стратегии обхода:
Простые
Учет структуры
URL
(уровень вложенности)
Учет структуры графа
(PageRank)
Учет содержимого страницы
(OASIS Crawler)
Слайд 28Поиск по значимости
Дополнение к оценкам близости
Значимость не зависит от запроса
Значимость бывает не
только у текстовых ресурсов
Более значимые ресурсы имеют приоритет при прочих равных
Слайд 29Значимость из содержимого
Анализ документа
(PHOAKS, определение жанра текста)
Анализ коллекции
(Google, SCAM, PHOAKS)
Информационный контекст
(Referral Web)
Внутренние
метки в документе
(PICS, RDF)
Слайд 30Значимость из действий
Явные указания:
Обратная связь
(групповая)
Триггеры на данные
(почтовые фильтры)
Синтезированные фильтры
(пользователь задает
высокоуровневое описание)
Слайд 31Значимость из действий (2)
Неявные указания:
Коллективное поведение пользователей
(WebWatcher, Hotbot)
Индивидуальное поведение пользователя
Какие документы/коллекции
он посещает?
Что он делает с документом?
(время просмотра, новая закладка, запись на диск, ответ на письмо)