Информационный поиск:модели и методы

Содержание

Слайд 2

Информационный поиск (ИП)

Цель: удовлетворить информационные потребности пользователя
Обсуждаемые темы:
Модели ИП
Критерии оценки качества поиска
Поиск

Информационный поиск (ИП) Цель: удовлетворить информационные потребности пользователя Обсуждаемые темы: Модели ИП
в Интернет
Поиск по значимости

Слайд 3

Модель ИП:

Логическое представление документов
Логическое представление запросов
Framework моделирования представлений документов и запросов, их

Модель ИП: Логическое представление документов Логическое представление запросов Framework моделирования представлений документов
взаимосвязей
Ранжирующая функция

Слайд 4

Классификация моделей

Булева модель (теория множеств и булева алгебра)
Векторная модель (векторные пространства и

Классификация моделей Булева модель (теория множеств и булева алгебра) Векторная модель (векторные
линейная алгебра)
Вероятностная модель (множества, теория вероятностей)
Классические модели подразумевают независимость слов (термов)

Слайд 5

Булевы модели

Модель на нечетких множествах (с термом запроса ассоциировано нечеткое множество документов)
Расширенная булева

Булевы модели Модель на нечетких множествах (с термом запроса ассоциировано нечеткое множество
модель
Расширяет булеву модель для использования весов термов
Обобщает модель на нечетких множествах и векторную модель (выбирая метрику)

Слайд 6

Векторные модели

Обобщенная векторная модель (учет корреляции между термами)
Латентно-семантический анализ (отображение документов и запросов

Векторные модели Обобщенная векторная модель (учет корреляции между термами) Латентно-семантический анализ (отображение
в пространство концепций)
Нейронные сети (нейроны —термы документов и документы, многошаговое распространение сигнала)

Слайд 7

Вычисление весов термов

Частота терма в документе
Обратная частота термов в коллекции
Вычисление весов

Вычисление весов термов Частота терма в документе Обратная частота термов в коллекции Вычисление весов

Слайд 8

Нормализация весов

Преимущества длинных документов:
Больше различных термов
Выше частоты термов
Методы нормализации:
по максимальной частоте
по длине

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

Слайд 9

Вероятностные модели

Вероятностный принцип Оценить вероятность того, что документ будет интересен пользователю
Модель сетей

Вероятностные модели Вероятностный принцип Оценить вероятность того, что документ будет интересен пользователю
вывода (inference networks)
На основе сети Байеса
Могут имитировать булеву модель, некоторые векторные модели, обратную связь
Реализована в Inquery

Слайд 10

Моделирование языка

Zipf’s Law

Heaps’ Law

Слова

F

V

Размер текста

Моделирование языка Zipf’s Law Heaps’ Law Слова F V Размер текста

Слайд 11

Предварительная обработка текста

Лексический анализ
Исключение стоп-слов
Выделение основ слов (stemming)
Выбор термов для индексирования (например

Предварительная обработка текста Лексический анализ Исключение стоп-слов Выделение основ слов (stemming) Выбор
только существительных)
Тезаурусы (выделение категорий термов)

Слайд 12

Языки запросов

Запросы по ключевым словам
однословные
контекстные
логические
на естественном языке
Запросы по шаблонам
Протоколы запросов (Z39.50, WAIS)

Языки запросов Запросы по ключевым словам однословные контекстные логические на естественном языке

Слайд 13

Уточнение запросов:

Изменение весов термов запроса
Добавление новых термов в запрос
Основные подходы:
Обратная связь (Relevance

Уточнение запросов: Изменение весов термов запроса Добавление новых термов в запрос Основные
feedback)
Автоматический локальный анализ
Автоматический глобальный анализ

Слайд 14

Критерии оценки

Точность
Полнота
Процент мусора

A

R

S

Критерии оценки Точность Полнота Процент мусора A R S

Слайд 15

Критерии оценки (2)

Средняя точность
Интерполяция
По числу документов P@20, P@50, p@100

Критерии оценки (2) Средняя точность Интерполяция По числу документов P@20, P@50, p@100

Слайд 16

Критерии оценки (3)

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

Критерии оценки (3) Точность на уровне обнаружения заданного числа релевантных документов Точность
R возвращенных, где R – число реально релевантных (R-precision)
Гистограммы точности (сравнение эффективности двух алгоритмов на каждом запросе)

Слайд 17

Критерии оценки (4)

Среднее гармоническое (b = 1) (компромисс между точностью и полнотой)
E-мера (учет

Критерии оценки (4) Среднее гармоническое (b = 1) (компромисс между точностью и
предпочтений пользователя)

Слайд 18

Критерии оценки (5)

Пользовательские критерии:
Коэффициент покрытия (процент уже известного среди найденного)
Коэффициент новизны (отношение нового к

Критерии оценки (5) Пользовательские критерии: Коэффициент покрытия (процент уже известного среди найденного)
уже известному)
Относительная полнота (отношение нового к ожидаемому)

Слайд 19

Особенности поиска в Интернет

Огромный размер > 1 миллиарда документов (февраль 2000) > 75 миллионов

Особенности поиска в Интернет Огромный размер > 1 миллиарда документов (февраль 2000)
узлов
Короткие запросы ( < 2 слов)
Почти не используются продвинутые возможности языка запросов
Много изменений в данных (40% в месяц)

Слайд 20

Размер поисковых систем

Размер поисковых систем

Слайд 21

Оценка качества индекса

Не все страницы одинаково важны
Метрики
Суммарная значимость всех страниц
Средняя значимость страниц

Оценка качества индекса Не все страницы одинаково важны Метрики Суммарная значимость всех

Метод случайной прогулки
Как проверить наличие страницы в индексе?
Как оценить значимость страницы?

Слайд 22

TREC и Web

Коллекция VLC2: 100Гб, 18.5 миллионов документов
Короткие запросы из TREC (2.5

TREC и Web Коллекция VLC2: 100Гб, 18.5 миллионов документов Короткие запросы из
слова)
5 поисковых систем

Слайд 23

Задачи ИП в Интернет

Обнаружение дубликатов
Интеллектуальные сетевые роботы
Борьба с опечатками Levenshtein(survey, surgery) = 2 LCS(survey,

Задачи ИП в Интернет Обнаружение дубликатов Интеллектуальные сетевые роботы Борьба с опечатками
surgery) = surey
Метапоиск
Как делать слияние результатов (data fusion)?

Слайд 24

Классификация типов копий

Повторение содержания (1) и структуры (2)

Классификация типов копий Повторение содержания (1) и структуры (2)

Слайд 25

Оценка повторения структуры

Построение описаний URL yahoo.com/ref/art/news.htm (yahoo,com) (ref, art, 0) (art, news, 1) (news,

Оценка повторения структуры Построение описаний URL yahoo.com/ref/art/news.htm (yahoo,com) (ref, art, 0) (art,
htm, 2)
Сокращение числа кандидатов (стоп-слова, нехарактерные пары)
Вычисление весов (IDF)
Вычисление оценки похожести узлов
Уровни похожести: 100%, 50%, 0%

Слайд 26

Оценка повторения содержания

Выбор страниц для проверки
Проверка на полную идентичность
Вычисление оценки близости: S(A) —

Оценка повторения содержания Выбор страниц для проверки Проверка на полную идентичность Вычисление
множество k-грамм документа A

Слайд 27

Сетевые роботы

Области применения:
Построение индексов
Сбор статистики
Поиск ресурсов
Исследование структуры Интернет
Проверка целостности ссылок

Стратегии обхода:
Простые
Учет структуры

Сетевые роботы Области применения: Построение индексов Сбор статистики Поиск ресурсов Исследование структуры
URL (уровень вложенности)
Учет структуры графа (PageRank)
Учет содержимого страницы (OASIS Crawler)

Слайд 28

Поиск по значимости

Дополнение к оценкам близости
Значимость не зависит от запроса
Значимость бывает не

Поиск по значимости Дополнение к оценкам близости Значимость не зависит от запроса
только у текстовых ресурсов
Более значимые ресурсы имеют приоритет при прочих равных

Слайд 29

Значимость из содержимого

Анализ документа (PHOAKS, определение жанра текста)
Анализ коллекции (Google, SCAM, PHOAKS)
Информационный контекст (Referral Web)
Внутренние

Значимость из содержимого Анализ документа (PHOAKS, определение жанра текста) Анализ коллекции (Google,
метки в документе (PICS, RDF)

Слайд 30

Значимость из действий

Явные указания:
Обратная связь (групповая)
Триггеры на данные (почтовые фильтры)
Синтезированные фильтры (пользователь задает

Значимость из действий Явные указания: Обратная связь (групповая) Триггеры на данные (почтовые
высокоуровневое описание)

Слайд 31

Значимость из действий (2)

Неявные указания:
Коллективное поведение пользователей (WebWatcher, Hotbot)
Индивидуальное поведение пользователя
Какие документы/коллекции

Значимость из действий (2) Неявные указания: Коллективное поведение пользователей (WebWatcher, Hotbot) Индивидуальное
он посещает?
Что он делает с документом? (время просмотра, новая закладка, запись на диск, ответ на письмо)
Имя файла: Информационный-поиск:модели-и-методы.pptx
Количество просмотров: 137
Количество скачиваний: 0