Презентация "Введение в мультимедийные базы данных 6" - скачать презентации по Информатике онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему "Введение в мультимедийные базы данных 6" - скачать презентации по Информатике абсолютно бесплатно. Урок-презентация на эту тему содержит всего 35 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Информатика » "Введение в мультимедийные базы данных 6" - скачать презентации по Информатике
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:35 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:251.00 kB
- Просмотров:78
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Текстовые базы данных](/documents/9ec0b77e71072067c2b35a4e68cd643f/img1.jpg)
Содержание слайда: Текстовые базы данных
Содержат текстовую информацию/текстовые документы
Наиболее распространенные на сегодняшний день
«Зрелый» уровень развития; «первые шаги» в 60-70-х годах
Существует условное разбиение:
Структурированные (structured) бд: форматированные записи, объект задается структурой
Неструктурированные (unstructured) бд: например, полные тексты статей
Полуструктурированные (semi-structured) данные: (веб-страницы, XML-документы)
«Зрелый» уровень развития; «первые шаги» в 60-70-х годах
Области применения:
Электронный документооборот (автоматизация офиса)
Цифровые библиотеки
Юридические и патентные системы
Электронные словари/энциклопедии/справочники
Электронные газеты/журналы/книги
Библиотеки исходников программного обеспечения (source program libraries)
№3 слайд
![Текстовые базы данных](/documents/9ec0b77e71072067c2b35a4e68cd643f/img2.jpg)
Содержание слайда: Текстовые базы данных
Документ?
В зависимости от контекста, книга, одна глава, один параграф, одна статья, одни тезисы к статье, письмо, исходный код какой-нибудь программы, поле типа VARCHAR или TEXT в бд и т.д.
Задача: поиск в коллекции документов по их содержимому - ассоциативный поиск (associative search)
Используются ключевые слова (keywords) или термины (terms)
Поисковый запрос: совокупность ключевых слов, объединенная булевыми (или логическими) выражениями AND, OR, NOT
Индекс: механизм для нахождения заданного термина в тексте
№4 слайд
![Поиск без использования](/documents/9ec0b77e71072067c2b35a4e68cd643f/img3.jpg)
Содержание слайда: Поиск без использования индекса
Последовательное полнотекстовое сканирование текста
Достоинства:
Не требуется дополнительное место для индекса
Быстрые изменения/обновления (не нужно вносить изменения в индекс)
Нахождение частично совпадающих строк относительно простое (при помощи wildcard-символов: таких как *,? и т.д.)
Возможно приближенное сравнение (approximate matching) (путем задания порогового значения для расстояния Левенштейна (Levenshtein distance или edit distance)
№5 слайд
![Поиск без использования](/documents/9ec0b77e71072067c2b35a4e68cd643f/img4.jpg)
Содержание слайда: Поиск без использования индекса
Алгоритмы1 для нахождения точного соответствия (exact matching) в общей памяти:
Knuth-Morris-Pratt: алгоритм линейной сложности (O(n) time); основан на предварительной обработке строки поиска (строка поиска – образец который ищется в тексте)
Boyer-Moore: поиск происходит быстрее для более длинных строк; на практике скорость работы сублинейна; основан на предварительной обработке строки поиска
Aho-Corasick: одновременный поиск нескольких терминов; основан на теории конечных автоматов (finite automata)
Rabin-Karp: используется специальная хеш-функция – хеш-значения последовательно вычисляются для всех подстрок текста и потом сравниваются с хеш-значением строки поиска
1 Более подробно описаны здесь:
Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ, 2-ое издание, Вильямс, 2005
http://en.wikipedia.org/wiki/String_searching_algorithm (с текстами исходников)
№6 слайд
![Инвертированный индекс](/documents/9ec0b77e71072067c2b35a4e68cd643f/img5.jpg)
Содержание слайда: Инвертированный индекс
Традиционный способ, широко используется в поисковых машинах
Инвертированный?
Каждый документ - это список терминов (index terms), а инвертированный индекс каждому термину ставит в соответствие список документов в которых встречается данный термин; т.е. получаем обратное (инвертированное) соответствие – у каждого термина есть список документов
Лексикон: термины, используемые в документе(-ах)
Правила построения лексикона:
Все символы переводятся в нижний регистр (case folding);
Удаление суффиксов, в индекс идут корневые формы слов (stemming)
В индекс не включаются так называемые стоп-слова: (например, для английского языка не включаются the, is, as, that, и ряд других)
№7 слайд
![Разрешение индекса Разрешение](/documents/9ec0b77e71072067c2b35a4e68cd643f/img6.jpg)
Содержание слайда: «Разрешение» индекса:
«Разрешение» индекса:
Степени детализации индекса (granularity of the index) – «разрешение» индекса: разрешение с которым индекс определяет местоположение термина в документе
Три степени детализации индекса:
Крупноструктурный индекс (coarse-grained index): каждый термин указывает на блок(-и) текста (а блок включает в себя несколько документов);
Среднеструктурный индекс (moderate-grained): указывает на документы, содержащие термин (список id-номеров документов);
Мелкоструктурный индекс (fine-grained): может указывать на предложение, в котором есть данный термин, или порядковый номер термина внутри документа или даже точную байтовую позицию термина.
№8 слайд
![Инвертированный индекс Плюсы](/documents/9ec0b77e71072067c2b35a4e68cd643f/img7.jpg)
Содержание слайда: Инвертированный индекс
Плюсы и минусы крупноструктурного индекса:
Маленький размер
Легко поддерживать (обновлять, вносить изменения)
Требует значительного полнотекстового сканирования
Нерелевантен при поиске нескольких терминов одновременно (например, искомые слова могут находиться в одном и том же блоке, но необязательно в одном и том же документе)
Плюсы и минусы мелкоструктурного индекса:
Позволяет находить слова, расположенные рядом (proximity queries)
Большой размер индекса
Тяжело поддерживать
Если запросов в которых ищут близко расположенные слова немного, то используют среднеструктурный индекс
№9 слайд
![Инвертированный индекс Сжатие](/documents/9ec0b77e71072067c2b35a4e68cd643f/img8.jpg)
Содержание слайда: Инвертированный индекс
Сжатие:
Инвертированные файлы - ориентировочно 50-100% от размера суммарного текста
Лучшее сжатие, если:
Индекс без потери общности можно задать в виде целых чисел; например, лексикон сортируется в алфавитном порядке, и затем каждому термину из лексикона ставится в соответствие число - номер по списку; указатели на документы - id-номера документов
Храним неполные id-номера документов; например, <8: 3, 5, 19, ...> , где 8 – это номер термина в лексиконе, а 3, 5, 19 – id-номера документов, можно упростить до <8: 3, 2, 14, ...>
Располагаем термины лексикона в алфавитном порядке, тогда общие префиксы расположенных рядом терминов можно представлять более компактно
Для мелкоструктурного индекса: вместо сохранения полных указателей на термины в документе, можно хранить интервалы между последовательно встречающимися терминами
№10 слайд
![Инвертированный индекс](/documents/9ec0b77e71072067c2b35a4e68cd643f/img9.jpg)
Содержание слайда: Инвертированный индекс
Составные запросы:
AND: выполняется путем извлечения для каждого термина списка документов и нахождения пересечения
OR: аналогично, но возвращаем объединение списков
NOT: обычно сочетается с оператором AND, затем вычисляется логическая разность между списками
Структуры данных для инвертированного индекса:
B+-дерево, где термины являются ключами, а списки указателей листьями
Организация в виде хеша, обычно динамическая версия:
Линейный хеш (linear hash)
Расширяемый хеш (extendible hash)
Бор-структура или трай-структура («trie-structure» от retrieval, «бор» от выборка: на каждый узел приходится только один символ, термин находится движением по бору (дереву) с вершины до соответствующего листа
Список документов находится в структуре данных либо локально, либо (предпочтительно) от нее обособлен
№11 слайд
![Инвертированный индекс](/documents/9ec0b77e71072067c2b35a4e68cd643f/img10.jpg)
Содержание слайда: Инвертированный индекс
Алгоритм построения индекса:
Для каждого документа в коллекции, сформировать список терминов, где для каждого термина есть список указателей на месторасположение данного термина(-ов) в документе. Итог - большой последовательный файл S.
Отсортируем S, с помощью например mergesort (сортировка слиянием).
Объединим последовательные элементы, представляющие один и тот же индекс-термин.
На основе выбранной структуры данных (B+-дерево, хеш, ...) сформировать индекс. При этом пусть листья содержат указатели на хранящиеся обособлено списки id-номеров документов (и указателей на месторасположение терминов в документах, если строится мелкоструктурный индекс). Сами же списки хранятся как записи переменной длины.
Резюме:
Очень эффективный и популярный метод извлечения данных
Несмотря на минусы (большой размер и сложность поддержки индекса) широко используется для коллекций статичных документов
№12 слайд
![Битово-матричное](/documents/9ec0b77e71072067c2b35a4e68cd643f/img11.jpg)
Содержание слайда: Битово-матричное индексирование
Еще один способ представления инвертированного индекса: в матричной форме
Крупноструктурная или среднеструктурная степень детализации
Битовая матрица – матрица, в которой число строк соответствует числу терминов в индексе (размер лексикона), число столбцов = число документов в коллекции. <i,j> равен 1, если термин i встречается в документе j, иначе <i,j> равен 0.
Эффективно для запросов с логическими выражениями: AND, OR, NOT могут быть реализованы в «железе» (например, с параллельной обработкой по 64 бита)
Проблема: индекс занимает много места (размер матрицы = число терминов*число документов, матрица разреженная (нолей много больше чем единиц)
Комбинация индексов: инвертированный индекс для не часто встречающихся терминов и бинарная матрица для более часто встречающихся терминов
Сжатие индекса: кодирование с переменной длиной строки (или метод RLE); заменяет последовательности нолей на их количество
№13 слайд
![Битово-матричное](/documents/9ec0b77e71072067c2b35a4e68cd643f/img12.jpg)
Содержание слайда: Битово-матричное индексирование
Иерархическое сжатие битовых строк:
Разбиваем строку на блоки символов одинакового размера
Для каждого блока применим к битам данного блока операцию дизъюнкции (OR - операция логического сложения), результат даст нам бит следующего уровня; операция OR примененная к блоку со одними нулями даст ноль, если в блоке имеется хоть одна единица, то получим единицу
Рекурсивно повторяем процесс на всех уровнях иерархии
Каждый бит легко определяется построением
соответствующего пути от вершины дерева
№15 слайд
![Сигнатурное индексирование](/documents/9ec0b77e71072067c2b35a4e68cd643f/img14.jpg)
Содержание слайда: Сигнатурное индексирование
Вероятностная техника
Сигнатура – битовый массив, генерируемый путем хеширования терминов в массив индексов (о генерации ниже); длина сигнатуры обычно как минимум несколько сотен бит
Сигнатуры хранятся в отдельном (сигнатурном) файле; его размер меньше чем размер всей коллекции документов
Сигнатурный файл - фильтрующий механизм, уменьшающий количество данных, которые просматриваются во время поиска
Возможен поиск по частичному совпадению
Поисковый запрос рассматривается как самостоятельный документ (состоящий из терминов, заданных в запросе); у запроса есть своя сигнатура; при поиске сигнатура запроса Q сравнивается с сигнатурами документов Di; если единичные биты Q есть в сигнатуре документа Dj, то Dj является возможным результатом (candidate result)
Сигнатура приблизительное описание документа; документы нерелевантные запросу (их называют false drops) должны быть устранены
№16 слайд
![Сигнатурное индексирование](/documents/9ec0b77e71072067c2b35a4e68cd643f/img15.jpg)
Содержание слайда: Сигнатурное индексирование
Достоинства сигнатурных файлов:
Меньший размер (в сравнении с мелко-структурным инвертированным индексом); типичный размер – 10-20% от общего размера коллекции документов
Более удобны чем многомерные индексы (о них будет рассказано позже)
Два основных метода генерации сигнатур:
Метод сигнатур слов (word signature method): каждому термину хеш-функция ставит в соответствие определенную битовую комбинацию (bit pattern) заданной длины; получившиеся композиции соединяют вместе, что дает сигнатуру документа; метод сохраняет информацию о последовательности с которой термины встречаются в документе; в тоже время, дает более высокую вероятность появления нерелевантных запросу документов
Суперпозиционное кодирование (superimposed coding): каждому термину ставится в соответствие битовая комбинация такой же длины, что и полная сигнатура; получившиеся комбинации логически складывают (выполняют OR), получая итоговую сигнатуру; метод по умолчанию далее
Как уменьшить число false drops?
Количество нолей и единиц в сигнатуре должно быть примерно одинаковым (вес сигнатуры - количество битовых единиц в ней)
Ноли и единицы должны быть однородно распределены по сигнатуре
№17 слайд
![Сигнатурное индексирование](/documents/9ec0b77e71072067c2b35a4e68cd643f/img16.jpg)
Содержание слайда: Сигнатурное индексирование
Пример:
Есть три документа со следующими терминами:
D1: база данных, объект, программирование, схема
D2: алгоритм, компьютер, программирование
D3: алгоритм, структура данных, программирование
Длина сигнатуры 8 бит, хеш-функция возвращает позицию бита с единицей (остальные семь бит – 0)
hash(“алгоритм ”) = 3 (т.е. 00100000);
hash(“компьютер”) = 1 (10000000);
hash(“база данных”) = 7 (00000010);
hash(“структура данных”) = 5;
hash(“объект ”) = 6;
hash(“программирование”) = 4;
hash(“схема”) = 1.
Сигнатура D1 – 10010110, сигнатура D2 – 10110000, D3 – 00111000
Запрос: найти документы с «алгоритм» и «программирование»
Запрос Q задается сигнатурой 00110000; единичные биты Q есть у D2 и D3 (технически, выполняется побитовая операция AND);
для получения окончательного результата нужно проверить D2 и D3 на наличие «алгоритм» и «программирование»
№18 слайд
![Сигнатурное индексирование](/documents/9ec0b77e71072067c2b35a4e68cd643f/img17.jpg)
Содержание слайда: Сигнатурное индексирование
Организация сигнатурного файла:
Основные принципы:
Неизбыточный размер файла
Минимизация операций ввода/вывода при выполнении запросов
Простая поддержка (изменение, удаление, добавление) индекса
(1) Сингулярный файл:
Составлен из списка сигнатур для всех документов из коллекции
Выполнение запроса: генерирование сигнатуры запроса; ее сравнение (выполнение побитовой операции AND) с каждой сигнатурой, имеющейся в сигнатурном файле (т.е. приходится сканировать весь сигнатурный файл); найденные документы (возможные результаты) затем просматриваются полностью, чтобы исключить false drops
Скорость выполнения запросов невелика
Замечание: для физического представления сигнатурного файла B-деревья не подходят
№19 слайд
![Сигнатурное индексирование](/documents/9ec0b77e71072067c2b35a4e68cd643f/img18.jpg)
Содержание слайда: Сигнатурное индексирование
(2) Транспонированный сингулярный файл:
Сингулярный файл – матрица (таблица) в которой число строк равно числу сигнатур (= числу документов), число столбцов длине сигнатуры. Обеспечивается прямой доступ к любому из столбцов матрицы (столбец матрицы также называют битовым срезом, англ. bit-slice).
Выполнение запроса: рассматриваются только те столбцы (битовые срезы), что соответствуют позициям единиц в сигнатуре запроса (и доступ требуется только к этим столбцам). Затем, эти столбцы логически перемножаются (AND) и единицы в получившемся столбце укажут на документы (см.след.слайд).
Поддержка трудоемка (например, добавление нового документа в индекс может вызвать изменения во всех столбцах). В целом, время добавление нового термина в индекс в случае транспонированного сигнатурного файла сравнимо со временем вставки нового термина в файл инвертированного индекса.
№21 слайд
![Сигнатурное индексирование](/documents/9ec0b77e71072067c2b35a4e68cd643f/img20.jpg)
Содержание слайда: Сигнатурное индексирование
(3) Двухуровневые сигнатурные файлы:
Два уровня (типа) сигнатур: высшего и низшего уровня
Сигнатура высшего уровня является фильтром для низшего уровня
Генерация сигнатуры высшего уровня:
а) Разбить документы на группы и генерировать сигнатуры для групп; сигнатуры больше в длину, но суммарный размер меньше
б) Генерировать сигнатуры путем логического сложения (OR) сигнатур низшего уровня; недостаток - в силу OR будет расти число единиц и, значит, количество false drops
№22 слайд
![S-деревья Многоуровневые](/documents/9ec0b77e71072067c2b35a4e68cd643f/img21.jpg)
Содержание слайда: S-деревья
Многоуровневые сигнатурные файлы (multi-level signature file)
Обобщение двухуровневых сигнатурных файлов: сигнатуры в каждом узле получаются логическим сложением (OR) сигнатур, содержащихся в дочерних узлах (см. «двухуровневые сигнатурные файлы», способ б)
S-деревья:
S-деревья и B-деревья имеют несколько общих свойств
S-дерево - сбалансированное по высоте дерево с множественным ветвлением (height balanced multiway tree)
Каждый узел соответствует странице (page) (блоку данных)
У корня дерева (корневого узла) не менее двух и не более K (= емкость страницы) дочерних узлов (если корень не является листом (leaf) дерева)
Все узлы за исключением корневого имеют не менее k и не более K дочерних узлов (1 <= k <= K, например k=K/2)
Каждый узел (за исключением возможно корневого) содержит не менее k сигнатур
Листья дерева содержат указатели на документы
Отличия S-дерева от B-дерева:
Сигнатуры в узлах не упорядочены
Одна и та же сигнатура может присутствовать в нескольких местах (сигнатуры разных документов могут совпадать)
Запросу вполне может соответствовать несколько путей движения по дереву
№24 слайд
![S-деревья Выполнение запросов](/documents/9ec0b77e71072067c2b35a4e68cd643f/img23.jpg)
Содержание слайда: S-деревья
Выполнение запросов с помощью S-деревьев:
Сгенерировать сигнатуру запроса путем суперпозиционного кодирования терминов
Обход дерева начнем с вершины
Для каждого узла просматриваем содержащиеся в нем сигнатуры; если 1-биты сигнатуры запроса совпадают с 1-битами сигнатур узла, то переходим к соответствующим дочерним узлам
Дойдя до листьев дерева, получим указатели на документы, которые нужно просмотреть для устранения false drops
Вставка сигнатуры в S-дерево:
Основная идея: логическое сложение (OR) всех сигнатур в узле должно иметь как можно меньший вес; тогда достигается наивысшая избирательность (selectivity)
Для определения подходящего узла для вставки осмотр начинают с вершины дерева, переходя на наиболее «близкие» дочерние узлы; под наиболее «близким» узлом может пониматься:
Узел, сигнатуры которого, имеют наименьшее расстояние Хемминга (Hamming distance) с сигнатурой вставляемого документа, или
Узел, имеющий наименьшее увеличение веса (weight increase), когда сигнатуры узла и добавляемую сигнатуру логически складывают (OR)
После вставки нужно внести изменения во все выше лежащие узлы
№25 слайд
![S-деревья Переполнение узла](/documents/9ec0b77e71072067c2b35a4e68cd643f/img24.jpg)
Содержание слайда: S-деревья
Переполнение узла:
Узел разбивают на два, стараясь при этом минимизировать весы новых получающихся сигнатур и уменьшить перекрытие между ними
Используют следующий эвристический алгоритм для разбиения узла S-дерева:
(1) Выбирается сигнатура имеющая наибольший вес; она добавляется в группу 1; в группу 2 добавляется та сигнатура, что имеет наибольшее увеличение веса по отношению к сигнатуре из группы 1
(2) Каждая из оставшихся сигнатур добавляются в ту группу в которой достигается наименьшее увеличение веса при логическом сложении сигнатур уже добавленных в группу и рассматриваемой сигнатуры
В равнозначных случаях используется следующие правила (по порядку):
а) добавить в меньшую группу;
б) добавить в группу с меньшим весом;
в) добавить в случайно выбранную группу.
Если на каком-то шаге в одной из групп K-k сигнатур, добавить остающиеся сигнатуры в другую группу
Распространение:
Как и у B-деревьев, разбиение узлов может быть распространено на выше
лежащие узлы вплоть до вершины
После разбиения узла все выше лежащие узлы должны быть
соответствующим образом изменены
Обновление документа: индекс обновляется путем последовательного удаления и вставки сигнатуры
№26 слайд
![Расширенный информационный](/documents/9ec0b77e71072067c2b35a4e68cd643f/img25.jpg)
Содержание слайда: Расширенный информационный поиск
Основные принципы:
Результаты поиска не обязательно точно соответствуют запросу
Ранжирование (ranking) документов, т.е. все документы из коллекции могут быть расставлены в определенном порядке на основе ранга каждого документа; ранг документа определяется на основе «расстояния» от документа до запроса
Учитываются семантические связи между терминами
№27 слайд
![Расширенный информационный](/documents/9ec0b77e71072067c2b35a4e68cd643f/img26.jpg)
Содержание слайда: Расширенный информационный поиск
Важные понятия:
Синонимия (synonymy): различные термины имеют одинаковое или
близкое значение
Полисемия (многозначность) (polysemy): один термин имеет несколько значений
Вес (weight) термина: указывает на важность термина в документе
Добротность (качество) поиска:
Точность (precision) поиска: отношение количества извлеченных документов, релевантных (удовлетворяющих условиям поиска) поиску, к общему количеству извлеченных документов
Полнота (recall) поиска: отношение количества извлеченных документов, релевантных поиску, к общему количеству релевантных документов
Часто происходит объединение этих двух понятий в одно – релевантность; релевантность поискового запроса - степень соответствия искомого (запроса) и найденного (результатов запроса), уместность результата; релевантность - субъективное понятие
№28 слайд
![Расширенный информационный](/documents/9ec0b77e71072067c2b35a4e68cd643f/img27.jpg)
Содержание слайда: Расширенный информационный поиск
Коллекцию документов можно представить в виде матрицы D (обобщение битово-матричного индекса).
Dt,i = значение веса термина t в документе i (вес термина может задаваться как количество раз, которое термин встречается в документе).
Столбцы матрицы (векторы) характеризуют документы.
Запрос – документ: запрос -> вектор (при построении веса входящих в запрос терминов как правило не учитываются).
Задача информационного поиска: Найти k документов, вектора которых наиболее «близки» к вектору запроса.
Вопрос: как измерять «расстояние» между документами (между запросом и документом)?
Первой попытка: меры похожести (similarity), скалярное произведение векторов запроса и документа:
similarity(Q, Di) = Q • Di = tTermsQtDt,i.
№29 слайд
![Расширенный информационный](/documents/9ec0b77e71072067c2b35a4e68cd643f/img28.jpg)
Содержание слайда: Расширенный информационный поиск
Сложности:
Если вес термина задается как количество экземпляров данного термина в документе, то широко используемые термины (слова) будут иметь избыточный вес
Длинные документы (содержат больше терминов) будут в более привилегированном положении чем короткие
Закон Ципфа (Zipf’s law): Формулировка закона - если все слова некоторого языка (или достаточно длинного текста) упорядочить по убыванию частоты их использования, то частота n-го слова в таком списке окажется приблизительно обратно пропорциональной его порядковому номеру n. Можно записать: f * r = c, где f – частота слова в документе, r – ранг слова, c – константа.
Следствия: небольшое количество слов встречается очень часто; среднее количество слов встречается со средней частотой; большинство слов встречается очень редко
№30 слайд
![Расширенный информационный](/documents/9ec0b77e71072067c2b35a4e68cd643f/img29.jpg)
Содержание слайда: Расширенный информационный поиск
Если какое-то слово встречается часто, то это слово хорошо передает смысл документа (бОльший вес)
Слова, которые часто встречаются во многих документах, не несут существенную информацию
Правило TF*IDF (TF*IDF rule, TF*IDF – term frequency times inverse document frequency):
Dt,i = tf*idf = ft,i*log(1+N/ft), где tf = ft,i - частота термина t в документе i
tf и idf могут вычисляться по разному – например, частота термина (tf) может быть нормализована
№31 слайд
![Расширенный информационный](/documents/9ec0b77e71072067c2b35a4e68cd643f/img30.jpg)
Содержание слайда: Расширенный информационный поиск
Геометрические расстояния в векторном пространстве:
Евклидово расстояние (Euclidean distance):
Выделяет длинные документы; степень подобия (similarity)
документа и запроса может определяться по мере обратной
евклидовому расстоянию
Определение угла (косинуса угла):
степень подобия –
Вместе с правилом TF*IDF:
№32 слайд
![Латентное семантическое](/documents/9ec0b77e71072067c2b35a4e68cd643f/img31.jpg)
Содержание слайда: Латентное семантическое индексирование
Матрица, которая ставится в соответствие коллекции документов, обычно разреженная (большинство элементов ноли).
Альтернатива: латентное семантическое индексирование (LSI)
LSI позволяет представить термины и документы в «семантическом пространстве», выявляя скрытые (внутренние) семантические связи между терминами и документами.
Процедура для LSI:
Создать частотную матрицу D для искомой коллекции документов
Вычислить сингулярное разложение (singular value decomposition - SVD) матрицы D; D = A x S x B (см.след.слайд)
Уменьшить размер матриц путем удаления малозначащих строк/столбцов
Сохранить получившиеся матрицы с помощью какого-нибудь метода индексирования
Выполнение запроса: вектор запроса преобразуется в трансформированный вектор; получившийся вектор сравнивается (определяется степень подобия) с векторами одной из уменьшенных матриц разложения
№33 слайд
![Латентное семантическое](/documents/9ec0b77e71072067c2b35a4e68cd643f/img32.jpg)
Содержание слайда: Латентное семантическое индексирование
Сингулярное разложение:
Широко используется во многих областях
Для любой матрицы D существует разложение
D = A * S * BT:
Матрицы А размером M*R и B размером N*R ортогональные, т.е. A*AT = I, B*BT = I; матрица S, сингулярная матрица, размером R*R является диагональной, причем диагональные элементы (они также являются сингулярными числами матрицы А) не возрастают (sj,j >= sj+1,j+1)
Базовая идея сингулярного разложения – уменьшить размер матрицы S, c R до k; уменьшив матрицу S до размера k*k (удалив R-k сингулярных значений справа внизу), получим что матрица D может быть представлена в виде произведения матриц Ak (M*k), Sk (k*k), Bk (N*k)
№34 слайд
![Латентное семантическое](/documents/9ec0b77e71072067c2b35a4e68cd643f/img33.jpg)
Содержание слайда: Латентное семантическое индексирование
Сингулярное разложение:
Эффект: удаление «шума», выявление скрытых (неявных) семантических связей
Вектор запроса подвергается следующей трансформации: Qk = QT * Ak * Sk-1; затем, вычисляется степень подобия между Qk и векторами матрицы Bk (без доказательства)
Слабая сторона LSI: метод требует значительных матричных преобразований и вычислений
LSI подходит для статичных (или редко обновляющихся) коллекций документов
№35 слайд
![Упражнения Объясните более](/documents/9ec0b77e71072067c2b35a4e68cd643f/img34.jpg)
Содержание слайда: Упражнения
Объясните более подробно почему число false drops уменьшается, если ноли и единицы однородно распределены по сигнатуре и вес сигнатуры равен примерно половине ее длины.
Объясните почему B-дерево не подходит для физического представления сигнатурного файла.
Проверить закон Ципфа для большого текста (>200 000 слов) на русском и английском языках. Для подсчета слов использовать, например, программу QB Text Analyzer.
Докажите что при выполнении запросов трансформированный вектор запроса Qk должен сравниваться с векторами матрицы Bk (см.«Латентное семантическое индексирование").
Пусть документы состоят из следующих терминов:
D1: база данных, объект, программирование, схема
D2: алгоритм, компьютер, программирование
D3: алгоритм, структура данных, программирование
Хеш-функция для терминов такая же как на слайде «Сигнатурное индексирование (пример)».
Следовательно, сигнатура D1 – 10010110, сигнатура D2 – 10110000, D3 – 00111000.
Выполните следующие запросы:
Q1: Найти документы с "компьютер" и "программирование".
Q2: Найти документы с "компьютер" или "алгоритм".
Q3: Найти документы, не содержащие "компьютер".
Скачать все slide презентации "Введение в мультимедийные базы данных 6" - скачать презентации по Информатике одним архивом:
Похожие презентации
-
"Введение в мультимедийные базы данных" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 14" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 13" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 12" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 11" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 10" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 9" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 8" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 7" - скачать презентации по Информатике
-
"Введение в мультимедийные базы данных 5" - скачать презентации по Информатике