Технологии поиска информации

Технологии обработки информации. Лекция 10. Технологии поиска информации Содержание  Понятие поиска  Виды поиска  Оценка эффективности  Методы и стратегии поиска  Алгоритмы (индексы, деревья, графы, хеширование)  Поиск изображений 2 Поиск (в широком смысле) 1) действия субъекта, направленные на получение нового или утерянного (забытого):     новой информации, данных, сведений, знаний открытие закономерностей действия по раскрытию (осознанию) скрытых содержаний, недостающих для целостного состояния (действие по восстановлению целостности) 2) один из способов обучения, обеспечивающих возможность получения знаний через самостоятельные мыслительные действия для решения возникающих задач  3 http://ru.wikipedia.org/ Понятия поиска (2) Поиск данных — раздел информатики, изучающий алгоритмы для поиска и обработки информации как в структурированных (базы данных) так и неструктурированных (текстовый документ) данных Информационный поиск (англ. Information retrieval) — процесс поиска неструктурированной документальной информации, удовлетворяющей информационные потребности, и наука об этом поиске Поиск информации — процесс выявления в массиве информации записей, удовлетворяющих заранее определенному условию поиска или запросу Термин был впервые введён Кельвином Муром в 1948     4 Поиск как наука Алгоритмы и структуры данных. Машинное обучение (Machine Learning) - обширный подраздел искусственного интеллекта, изучающий методы построения моделей, способных обучаться, и алгоритмов для их построения и обучения.       5 Web-графы и поиск. Алгоритмы и структуры данных для поиска. Анализ символьных последовательностей. Многомерный статистический анализ. Поиск как процесс последовательность операций, направленных на сбор, обработку и предоставление информации:  формулировка запроса определение источников извлечение информации предоставление и оценка результатов 6 Виды поиска полнотекстовый - поиск по всему содержимому документа; по метаданным - поиск по атрибутам документа (название, дата создания, размер, автор и т. д.); поиск по изображениям – распознавание объектов, лиц;    Существует путаница, связанная с понятиями поиска данных, поиска документов, информационного поиска и текстового поиска.  7 Методы поиска Адресный поиск – знаем точный адрес документа (URL, библиографическая ссылка и т.д.) Семантический поиск – по содержанию. Документальный поиск. Фактографический поиск.     8 Стратегии поиска. Классификация. Индексы Классификатор (индекс) — систематизированный перечень наименованных объектов, каждому из которых в соответствие дан уникальный код (индекс). Методы:     иерархический; фасетный. Кодирование - присвоение кода классификационной группировке или объекту классификации. Методы:      9 порядковый; серийно-порядковый; последовательный; параллельный. Пример: индекс в БД    объект базы данных, создаваемый с целью повышения производительности поиска данных. Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет искать строки, удовлетворяющие критерию поиска. Ускорение работы с использованием индексов достигается за счёт того, что индекс имеет структуру, оптимизированную под поиск — например, сбалансированного дерева, В-дерева и т.д. 10 Стратегии поиска. Деревья   Двоичное дерево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей) Двоичное дерево поиска — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):    11 Оба поддерева — левое и правое, являются двоичными деревьями поиска У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X Двоичное дерево поиска (2)   Двоичное дерево состоит из узлов— записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Данные (data) обладают ключом (key), на котором определена операция сравнения "меньше". В конкретных реализациях это может быть пара (key, value) - (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё. 12 Двоичное дерево поиска (3)     Поиск элемента (FIND) Дано: дерево Т и ключ K Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел Алгоритм:   Если дерево пусто, сообщить, что узел не найден, и остановиться Иначе сравнить K со значением ключа корневого узла X    13 Если K=X, выдать ссылку на этот узел и остановиться Если K>X, рекурсивно искать ключ K в правом поддереве Т Если K David Carmel, Yoelle Maarek, Aya Soffer Ricardo Baeza-Yates Gonzalo Navarro bla... bla... bla... bla... bla... bla... bla... bla... bla... bla... 36 Поиск в HTML vs. XML В HTML: • ищут целые документы • ранжируют целые документы • близость слов определяется положением в тексте 37 В XML: • ищут XML-элементы • ранжируют XML-элементы • близость слов определяется ещё и положением в дереве Принцип поиска  Что ищем    R0 – множество XML-элементов, содержащих все слова запроса. R1 – множество XML-элементов, таких, что ≥1 потомков содержат все слова запроса, ≥1 потомков содержат только часть слов Ранжирование результатов. ElemRank: 38 Качество ранжирования веб-страниц  PageRank — это алгоритм, позволяющий оценить, насколько данная интернет-страница популярна;   предложен Брином и Пейджем в 1998 г. идея: определять рейтинг страницы через количество ведущих на нее ссылок и рейтинг ссылающихся страниц. 39 Поиск нечетких дубликатов документов            MD5 TF TF*IDF TF*RIDF Long Sent Heavy Sent Megashingles Lex Rand Log Shingles Descr Words Opt Freq 40 Семантический поиск    Семантический Веб — новая концепция развития Веба и сети Интернет, принятая и продвигаемая W3C Проблема : большинство данных в Вебе хранится в форме, рассчитанной на восприятие человеком, их структура не очевидна роботу Семантический Веб — это не отдельная сеть, а расширение уже существующей 41 Принципы работы  Агент — программа, работающая без непосредственного управления со стороны человека или другого постоянного контроля, созданная для достижения целей, поставленных перед ней пользователем:     42 Закажи для меня эту книгу в ближайшей библиотеке. Посмотри на расписание электричек и мое расписание и выбери билеты в театр, чтобы я мог успеть после работы. Скажи мне, какое вино нужно купить к каждому из блюд в этом меню. И кстати, я не люблю Сотерн. Микроволновка, сходи на сайт производителя и загрузи оптимальные параметры подогрева. Сценарии использования    Семантический поиск. Поисковая система сможет выдавать только те сайты, где упоминается в точности искомое понятие, а не произвольные страницы, в тексте которых встретилось данное многозначное ключевое слово. Объединение знаний (интеграция баз данных) Всепроникающие вычисления (ubiquitous computing). Расширение сферы влияния на физический мир 43 Основная цель Семантического Веба  создание языка, на котором можно будет описать как данные, так и правила рассуждений об этих данных, так что правила вывода, существующие в какой-либо системе представления знаний, можно будет экспортировать в Веб.     Синтаксис. семантика. XML – есть синтаксис, но не определена семантика! Тим Бернерс-Ли: 44 Структура языка    RDF (Resource Description Framework) — язык, отвечающий за синтаксис документов Семантического Веба. В нем широко используются ссылки на онтологии для определения смысла слов OWL (Ontology Web Language) — язык описания онтологий. Онтология — описание классов объектов, их свойств и взаимоотношений для какой-то предметной области (домена) 45 План реализации 1. 2. 3. 4. 5. 6. 7. 8.46 Синтаксис для представления знаний, использующий ссылки на онтологии (сделано: RDF) Язык описания онтологий (сделано: OWL) Язык описания веб-сервисов (начато: WSDL, OWL-S) Инструменты чтения и разработки документов Семантического Веба (начато: Jena, Haystack, Protege) Язык запросов к знаниям, записанным в RDF (начато: SPARQL) Логический вывод знаний (не сделано). Семантическая поисковая система (начато: SHOE). Агенты Семантического Веба (не сделано). Архитектура 47 RDF: синтаксис Семантического Веба   XML дает возможность создавать документы произвольной структуры, однако данный язык ничего не говорит о том, что означает эта структура RDF кодирует смысл при помощи деревьев глубины три (Notation3), где каждое дерево состоит из:      субъекта (подлежащее) свойства (сказуемое) объекта (дополнение) «Небо голубого цвета» = субъект — «небо», свойство — «иметь цвет», объект — «голубой» 48 Пример: RSS   RSS — семейство XML-форматов, предназначенных для описания лент новостей, анонсов статей, изменений в блогах и т. п. Информация из различных источников, представленная в формате RSS, может быть собрана, обработана и представлена пользователю в удобном для него виде специальными программами-агрегаторами. Под RSS может пониматься:    49 Rich Site Summary — богатая сводка сайта RDF Site Summary — сводка сайта с применением инфраструктуры описания ресурсов Really Simple Syndication — очень простая синдикация Обработка естественного языка    Natural Language Processing, NLP - технологии обработки естественных языков Question-Answering Systems, QAS - вопросно-ответные системы На вход такой системе подаётся запрос, сформулированный на естественном языке, после чего он обрабатывается с использованием методов NLP, и генерируется естественно-языковой ответ 50 Схема процесса отбор документов • например поиск по ключевым словам фильтрация документов • выделение фрагментов текста потенциально содержащих ответ синтез ответа 51 Проблемы создания QAS            Типы вопросов Обработка вопросов Контекстные вопросы Источники знаний для QA-системы Выделение ответов Формулировка ответа (слияние ответов из разных документов) Ответы на вопросы в реальном времени Многоязыковые запросы Интерактивность Механизм рассуждений (вывода) Профили пользователей QA-систем 52 Поиск изображений по содержанию     англ. Content-based image retrieval (CBIR) — раздел компьютерного зрения, решающий задачу поиска изображений, которые имеют требуемое содержание, в большом наборе цифровых изображений Алгоритм поиска должен анализировать содержание изображения, например, цвет представленных на нём объектов, их форму, текстуру, композицию сцены Термин «Content-based image retrieval» впервые был введен в употребление в 1992 г. Т. Като Альтернатива: методы, основанные исключительно на категоризации метаданных – использование тегов (не подходит к автоматически созданным изображениям) 53 Области применения           Поиск изображений в сети интернет Каталогизация изображений произведений искусства Организация работы с архивами фотографических снимков Организация каталогов розничной продажи товаров Медицинская диагностика заболеваний Предотвращение преступлений и беспорядков Военно-оружейное применение Вопросы контроля за распространением интеллектуальной собственности Получение информации о местоположении удаленных зондов и географическое позиционирование Контроль за содержимым массивов изображений 54 Общая схема    система производит поиск на основе входного изображения, указываемого пользователем все результирующие экземпляры изображений должны иметь общие элементы с входом, указанным пользователем пользователь может подать на вход как существующее изображение, так и грубый набросок требуемого результата 55 Описание содержания. Цвет   Поиск изображений с помощью сравнения цветовых составляющих производится с помощью построения гистограммы их распределения изображение делится на регионы по сходным цветовым характеристикам, и далее учитывается их взаимное расположение 56 Описание содержания. Текстура   сравнение текстурных образцов, присутствующих на изображении, и их взаимного расположения текстоны - содержат не только информацию, описывающую текстуру, но и её местоположение на описываемом изображении 57 Описание содержания. Форма   описание геометрической формы отдельных регионов изображения к региону сначала применяют сегментацию или выделение границ 58 Примеры поисковых систем         Google Image Search Visual Image Search Chic Engine Visual Recognition Factory Empora Обратный поиск изображений TinEye.com Поиск людей по фотографиям PhotoDate.ru Поиск изображений по содержанию Immenselab.com 59 Источники      Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск /The Art of Computer Programming, vol.3. Sorting and Searching./ — 2-е изд. — М.: «Вильямс», 2007. — С. 824. MIT OpenCourseWare http://ocw.mit.edu Школа анализа данных Яндекс http://shad.yandex.ru/ Юрий Лифшиц - курс "Алгоритмы для Интернета" http://yury.name/internet/ Илья Сегалович «Как работают поисковые системы» http://download.yandex.ru/company/iworld-3.pdf 60