Технологии обработки информации. Лекция 6. Технологии поиска информации Антон Викторович Кудинов, доцент кафедры ВТ

Содержание Понятие поиска Виды поиска Оценка эффективности Методы и стратегии поиска Алгоритмы ( индексы, деревья, графы, хеширование ) Поиск изображений 2

Поиск ( в широком смысле ) 1) действия субъекта, направленные на получение нового или утерянного ( забытого ): новой информации, данных, сведений, знаний открытие закономерностей действия по раскрытию ( осознанию ) скрытых содержаний, недостающих для целостного состояния ( действие по восстановлению целостности ) 2) один из способов обучения, обеспечивающих возможность получения знаний через самостоятельные мыслительные действия для решения возникающих задач 3

Понятия поиска (2) Поиск данных раздел информатики, изучающий алгоритмы для поиска и обработки информации как в структурированных ( базы данных ) так и неструктурированных ( текстовый документ ) данных Информационный поиск ( англ. Information retrieval) процесс поиска неструктурированной документальной информации, удовлетворяющей информационные потребности, и наука об этом поиске Поиск информации процесс выявления в массиве информации записей, удовлетворяющих заранее определенному условию поиска или запросу Термин был впервые введён Кельвином Муром в

Поиск как наука Алгоритмы и структуры данных Машинное обучение (Machine Learning) НИУ ВШЭ Факультет бизнес - информатики Базовая кафедра Яндекс. Курсы магистратуры : Web- графы и поиск Алгоритмы и структуры данных для поиска Анализ символьных последовательностей Многомерный статистический анализ 5

Поиск как процесс последовательность операций, направленных на сбор, обработку и предоставление информации 6 формулировка запроса определение источников извлечение информации предоставление и оценка результатов

Виды поиска Что и как можно искать ? 7

Виды поиска полнотекстовый - поиск по всему содержимому документа по метаданным - поиск по атрибутам документа ( название, дата создания, размер, автор и т. д.) поиск изображений – распознавание объектов, лиц Существует путаница, связанная с понятиями поиска данных, поиска документов, информационного поиска и текстового поиска. 8

Методы поиска Адресный поиск – знаем точный адрес документа (URL, библиографическая ссылка и т. д.) Семантический поиск – по содержанию Документальный поиск Фактографический поиск 9

Оценки эффективности поиска Как численно определить качество результатов поиска ? 10

Оценки эффективности. Релевантность ( лат. relevo поднимать, облегчать ) в информационном поиске семантическое соответствие поискового запроса и поискового образа документа [ 11

Оценки эффективности. Точность (precision) Определяется как отношение числа релевантных документов, найденных ИПС, к общему числу найденных документов 12 где это множество релевантных документов в базе, а множество документов, найденных системой

Оценки эффективности. Полнота (recall) Отношение числа найденных релевантных документов, к общему числу релевантных документов в базе 13 где это множество релевантных документов в базе, а множество документов, найденных системой

Оценки эффективности. Выпадение (fall-out) Выпадение характеризует вероятность нахождения нерелевантного ресурса и определяется, как отношение числа найденных нерелевантных документов к общему числу нерелевантных документов в базе 14 где D nrel это множество нерелевантных документов в базе, а множество документов, найденных системой

F- мера (F-measure, мера Ван Ризбергена ) 15 Сбалансированная F- мера ( F 1 -мера) придает одинаковый вес точности и полноте ( = ½)

Стратегии поиска. Классификация. Индексы Классификатор ( индекс ) систематизированный перечень наименованных объектов, каждому из которых в соответствие дан уникальный код ( индекс ) Методы : Иерархический Фасетный Кодирование - присвоение кода классификационной группировке или объекту классификации. Методы : Порядковый Серийно - порядковый Последовательный Параллельный 16

Пример : индекс в БД объект базы данных, создаваемый с целью повышения производительности поиска данных Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет искать строки, удовлетворяющие критерию поиска Ускорение работы с использованием индексов достигается за счёт того, что индекс имеет структуру, оптимизированную под поиск например, сбалансированного дерева, В - дерева и т. д. 17

Стратегии поиска. Деревья Двоичное дерево древовидная структура данных, в которой каждый узел имеет не более двух потомков ( детей ) Двоичное дерево поиска это двоичное дерево, для которого выполняются следующие дополнительные условия ( свойства дерева поиска ): Оба поддерева левое и правое, являются двоичными деревьями поиска У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X 18

Двоичное дерево поиска (2) Двоичное дерево состоит из узлов записей вида (data, left, right), где data некоторые данные, привязанные к узлу, left и right ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно Данные (data) обладают ключом (key), на котором определена операция сравнения " меньше ". В конкретных реализациях это может быть пара (key, value) - ( ключ и значение ), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё 19

Двоичное дерево поиска (3) Поиск элемента (FIND) Дано : дерево Т и ключ K Задача : проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел Алгоритм : Если дерево пусто, сообщить, что узел не найден, и остановиться Иначе сравнить K со значением ключа корневого узла X Если K=X, выдать ссылку на этот узел и остановиться Если K>X, рекурсивно искать ключ K в правом поддереве Т Если K

Стратегии поиска. Хэширование преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины Такие преобразования также называются хеш - функциями или функциями свёртки, а их результаты называют хешем, хеш - кодом или сводкой сообщения Если у двух строк хеш - коды разные, строки гарантированно различаются, если одинаковые строки, вероятно, совпадают Предложил сотрудник IBM Хансу Петер Лун в январе 1953 года 21

Хэширование (2) Существует множество алгоритмов хеширования с различными свойствами ( разрядность, вычислительная сложность, криптостойкость и т. п.) Простейшие примеры хеш - функций : контрольная сумма или CRC Хорошая хеш - функция должна удовлетворять двум свойствам : 1. Быстро вычисляться 2. Минимизировать количество коллизий Коллизией хеш - функции H называется два различных входных блока данных x и y таких, что H(x) = H(y) 22

Хэширование. Виды (3) Хеш - функции основанные на делении H (k) = k mod m Мультипликативная схема хеширования Хеширование строк переменной длины ( Хеширование Пирсона ) Универсальное хеширование - используется не одна конкретная хеш - функция, а происходит выбор из заданного семейства по случайному алгоритму 23

Хэширование. Хэш - таблицы (3) Хеш - таблицей называется структура данных, позволяющая хранить пары вида ( ключ, хеш - код ) и поддерживающая операции поиска, вставки и удаления элемента Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш - кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву 24

Информационный поиск ( Information retrieval) Документ - некий объект, содержащий информацию в зафиксированном виде ( тексты на естественном или формализованном языке, изображения, звуковая информация и т. д.) Запрос - формализованный способ выражения информационных потребностей пользователя системы ( языки поисковых запросов, синтаксис которых варьируется ) Релевантность - функция соответствия документа запросу, субъективна 25

Модели информационного поиска Булевская Векторная Вероятностная … 26

Булевская модель Словарь : T = {t 1,... t n }, где t i термы Документ : D T, иначе говоря D {0, 1} n Запрос : t 5 OR t 7 NOT t 12 Используется : Внутрикорпоративные системы поиска Базы данных Недостаток : Жесткость Непригодность для ранжирования 27

Векторная модель Реализована в 1968 Джерардом Солтоном (Gerard Salton) в поисковой системе SMART Снова коллекция документов, каждый из которых теперь является мультимножеством слов Матрица M, где M ij = TF ij · IDF i, где : Частота терма TF ij относительная доля слова i в тексте j Обратная встречаемость в документах IDF i величина, обратная количеству документов, содержащих слово i Физический смысл M ij степень соответствия слова i тексту j Запрос : t 3 AND t 5 ( разрешаем только AND) 28

Вероятностная модель Робертсон (Robertson) и Спарк - Джоунз (Sparck-Jones) в 1977 г. Релевантность – здесь вероятность того, что данный документ может оказаться интересным пользователю Документ : множество слов D = {d 1,..., d n } Запрос : Q k тоже, но храним как множество Соответствие : Зафиксируем запрос Q k Пусть есть распределение вероятностей на всех текстах быть релевантным запросу Q k : обозначаем P(R|Q k,D) Пусть есть распределение вероятностей на всех текстах быть НЕрелевантным запросу Q k : обозначаем P( |Q k,D) Функцией соответствия будет их отношение ( или логарифм этой дроби ) 29

Поиск в Вебе Нужно анализировать не только текст документа, но и off-page факторы : положение на сайте посещаемость авторитетность источника частота обновления цитируемость страницы и ее авторов Искусственное накручивание рейтинга страниц (SEO) Поиск в полуструктурированных данных 30

Полуструктурированные данные 1) такой способ хранения данных, при котором у каждой единицы информации может быть произвольный набор полей 2) данные без постоянной чётко определённой структуры, либо данные со структурой, неизвестной пользователю. Их удобно представлять в виде графа 31

XML XML (eXtensible Markup Language) – язык текстовой разметки, стандартизованный W3C, удобный для представления полуструктурированных данных 32 XML and IR: A SIGIR 2000 Workshop David Carmel, Yoelle Maarek, Aya Soffer XQL and Proximal Nodes Ricardo Baeza-Yates Gonzalo Navarro bla... bla... bla... Querying XML in Xyleme bla...

Поиск в HTML vs. XML 33 В HTML: ищут целые документы ранжируют целые документы близость слов определяется положением в тексте В XML: ищут XML-элементы ранжируют XML-элементы близость слов определяется ещё и положением в дереве

Принцип поиска Что ищем R0 – множество XML- элементов, содержащих все слова запроса. R1 – множество XML- элементов, таких, что 1 потомков содержат все слова запроса, 1 потомков содержат только часть слов Ранжирование результатов. ElemRank: 34

Качество ранжирования веб - страниц PageRank это алгоритм, позволяющий оценить, насколько данная интернет - страница популярна предложен Брином и Пейджем в 1998 г. идея : определять рейтинг страницы через количество ведущих на нее ссылок и рейтинг ссылающихся страниц 35

Поиск нечетких дубликатов документов MD5 TF TF*IDF TF*RIDF Long Sent Heavy Sent Megashingles Lex Rand Log Shingles Descr Words Opt Freq 36

Семантический поиск Семантический Веб новая концепция развития Веба и сети Интернет, принятая и продвигаемая W3C Проблема : большинство данных в Вебе хранится в форме, рассчитанной на восприятие человеком, их структура не очевидна роботу Семантический Веб это не отдельная сеть, а расширение уже существующей 37

Принципы работы Агент программа, работающая без непосредственного управления со стороны человека или другого постоянного контроля, созданная для достижения целей, поставленных перед ней пользователем Закажи для меня эту книгу в ближайшей библиотеке. Посмотри на расписание электричек и мое расписание и выбери билеты в театр, чтобы я мог успеть после работы. Скажи мне, какое вино нужно купить к каждому из блюд в этом меню. И кстати, я не люблю Сотерн. Микроволновка, сходи на сайт производителя и загрузи оптимальные параметры подогрева. 38

Сценарии использования Семантический поиск. Поисковая система сможет выдавать только те сайты, где упоминается в точности искомое понятие, а не произвольные страницы, в тексте которых встретилось данное многозначное ключевое слово. Объединение знаний ( интеграция баз данных ) Всепроникающие вычисления (ubiquitous computing). Расширение сферы влияния на физический мир 39

Основная цель Семантического Веба создание языка, на котором можно будет описать как данные, так и правила рассуждений об этих данных, так что правила вывода, существующие в какой - либо системе представления знаний, можно будет экспортировать в Веб синтаксис семантика XML – есть синтаксис, но не определена семантика ! Тим Бернерс - Ли 40

Структура языка RDF (Resource Description Framework) язык, отвечающий за синтаксис документов Семантического Веба. В нем широко используются ссылки на онтологии для определения смысла слов OWL (Ontology Web Language) язык описания онтологий. Онтология описание классов объектов, их свойств и взаимоотношений для какой - то предметной области ( домена ) 41

План реализации 1. Синтаксис для представления знаний, использующий ссылки на онтологии ( сделано : RDF) 2. Язык описания онтологий ( сделано : OWL) 3. Язык описания веб - сервисов ( начато : WSDL, OWL-S) 4. Инструменты чтения и разработки документов Семантического Веба ( начато : Jena, Haystack, Protege) 5. Язык запросов к знаниям, записанным в RDF ( начато : SPARQL) 6. Логический вывод знаний ( не сделано ). 7. Семантическая поисковая система ( начато : SHOE). 8. Агенты Семантического Веба ( не сделано ). 42

Архитектура 43

RDF: синтаксис Семантического Веба XML дает возможность создавать документы произвольной структуры, однако данный язык ничего не говорит о том, что означает эта структура RDF кодирует смысл при помощи деревьев глубины три (Notation3), где каждое дерево состоит из : субъекта ( подлежащее ) свойства ( сказуемое ) объекта ( дополнение ) « Небо голубого цвета » = субъект « небо », свойство « иметь цвет », объект « голубой » 44

Пример : RSS RSS семейство XML- форматов, предназначенных для описания лент новостей, анонсов статей, изменений в блогах и т. п. Информация из различных источников, представленная в формате RSS, может быть собрана, обработана и представлена пользователю в удобном для него виде специальными программами - агрегаторами. Под RSS может пониматься : Rich Site Summary богатая сводка сайта RDF Site Summary сводка сайта с применением инфраструктуры описания ресурсов Really Simple Syndication очень простая синдикация 45

Обработка естественного языка Natural Language Processing, NLP - технологии обработки естественных языков Question-Answering Systems, QAS - вопросно - ответные системы На вход такой системе подаётся запрос, сформулированный на естественном языке, после чего он обрабатывается с использованием методов NLP, и генерируется естественно - языковой ответ 46

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

Проблемы создания QAS Типы вопросов Обработка вопросов Контекстные вопросы Источники знаний для QA- системы Выделение ответов Формулировка ответа ( слияние ответов из разных документов ) Ответы на вопросы в реальном времени Многоязыковые запросы Интерактивность Механизм рассуждений ( вывода ) Профили пользователей QA- систем 48

Поиск изображений по содержанию англ. Content-based image retrieval (CBIR) раздел компьютерного зрения, решающий задачу поиска изображений, которые имеют требуемое содержание, в большом наборе цифровых изображений Алгоритм поиска должен анализировать содержание изображения, например, цвет представленных на нём объектов, их форму, текстуру, композицию сцены Термин «Content-based image retrieval» впервые был введен в употребление в 1992 г. Т. Като Альтернатива : методы, основанные исключительно на категоризации метаданных ( не подходит к автомтически созданным изображениям, камеры наблюдений ) 49

Области применения Поиск изображений в сети интернет Каталогизация изображений произведений искусства Организация работы с архивами фотографических снимков Организация каталогов розничной продажи товаров Медицинская диагностика заболеваний Предотвращение преступлений и беспорядков Военно - оружейное применение Вопросы контроля за распространением интеллектуальной собственности Получение информации о местоположении удаленных зондов и географическое позиционирование Контроль за содержимым массивов изображений 50

Общая схема система производит поиск на основе входного изображения, указываемого пользователем все результирующие экземпляры изображений должны иметь общие элементы с входом, указанным пользователем пользователь может подать на вход как существующее изображение, так и грубый набросок требуемого результата 51

Описание содержания. Цвет Поиск изображений с помощью сравнения цветовых составляющих производится с помощью построения гистограммы их распределения изображение делится на регионы по сходным цветовым характеристикам, и далее учитывается их взаимное расположение 52

Описание содержания. Текстура сравнение текстурных образцов, присутствующих на изображении, и их взаимного расположения текстоны - содержат не только информацию, описывающую текстуру, но и её местоположение на описываемом изображении 53

Описание содержания. Форма описание геометрической формы отдельных регионов изображения к региону сначала применяют сегментацию или выделение границ 54

Примеры поисковых систем Google Image Search Visual Image Search Chic Engine Visual Recognition Factory Empora Обратный поиск изображений TinEye.com Поиск людей по фотографиям PhotoDate.ru Поиск изображений по содержанию Immenselab.com 55

Источники Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск /The Art of Computer Programming, vol.3. Sorting and Searching./ 2- е изд. М.: « Вильямс », С MIT OpenCourseWare Школа анализа данных Яндекс Юрий Лифшиц - курс " Алгоритмы для Интернета " Илья Сегалович « Как работают поисковые системы »

Спасибо за внимание ! 57