Модификация модели векторного пространства для ранжирования документов
Ручной подбор схемы взвешивания для коллекции документов. Вычисление полноты, точности и аккуратности алгоритма. Основные преимущества и недостатки модификации с генетическим алгоритмом. Эффективность использования векторной модели для ранжирования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 30.05.2017 |
| Размер файла | 455,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Модификация модели векторного пространства для ранжирования документов
С.П. Воробьев, М.Б. Хорошко
В модели векторного пространства документ и запрос представляются в виде векторов и релевантность рассчитывается по следующей формуле [1]:
где, - векторное представление запроса, - векторное представление документа. В качестве векторов в эксперименте использовалась оценка веса запроса и нормированный вес термина в документе - .
где частота термина в запросе, обратная документная частота, вычисляемая по формуле:
где - размер базы документов, - количество документов с данным термином.
В данном примере вес термина в документе учитывал только частоту термина, но возможны и другие варианты [2] взвешивания документа. Ручной подбор схемы взвешивания для коллекции документов займет большое время, проведем эксперимент для подбора схемы взвешивания используя одну из трех , , или c помощью генетического алгоритма, который получает на вход количество коэффициентов используемых в модели и возвращает подобранные коэффициенты. Общий алгоритм выглядит следующим образом:
1. Создается начальная популяция. Случайным образом из диапазона коэффициентов отдо (диапазон устанавливается для каждого алгоритма), подбираем наборов коэффициентов и переводим их в двоичный вид.
2. Вычисляем приспособленность хромосом. Оцениваем ошибку, для каждого набора коэффициентов.
3. Выбираем двух родителей с наименьшей ошибкой для операции скрещивания.
4. Выбор хромосом для операции мутации.
5. Оценка приспособленности нового набора коэффициентов.
6. Если ошибка - набора больше заданной ошибки , то переходим к пункту 3, иначе пункт 7.
7. Полученный набор коэффициентов, который минимизирует ошибку, возвращается в модель поиска.
Рассмотрены более детально основные аспекты:
· Все коэффициенты генерируются изначально случайным образом по равномерному закону при ограничении сверху и снизу. Затем переводятся в двоичный вид, чтобы можно было применять операции скрещивания и мутации.
· Ошибка оценивается по следующей формуле:
где, - средняя оценка документа экспертами, по запросу . - полученная релевантность документа , по запросу .
Для проверки эффективности применения генетического алгоритма (ГА), сравним полученные метрики оценки для двух систем по 30 запросам.
Полнота () вычисляется как отношение найденных релевантных документов к общему количеству релевантных документов:
Полнота характеризует способность системы находить нужные пользователю документы, но не учитывает количество нерелевантных документов, выдаваемых пользователю. Полнота показана на рисунке 1.
Рис.1. Полнота
В большинстве случаев ГА показывает лучшую полноту. Среднее значение полноты: ГА= 0,245; ВМ=0,153.
Точность () вычисляется как отношение найденных релевантных документов к общему количеству найденных документов.
Точность характеризует способность системы выдавать в списке результатов только релевантные документы. Точность алгоритмов показана на рисунке 2.
Рис.2. Точность
Среднее значение точности: ГА=0,207; ВМ=0,144.
Аккуратность () вычисляется как отношение правильно принятых системой решений к общему числу решений. Аккуратность алгоритмов показана на рисунке 3.
Рис.3. Аккуратность
Среднее значение аккуратности: ГА=0,87; ВМ=0,83.
Ошибка () вычисляется как отношение неправильно принятых системой решений к общему числу решений. Ошибка алгоритмов полказана на рисунке 4.
Рис.4. Ошибка
Среднее значение ошибки: ГА=0,153; ВМ=0,16.
F-мера () часто используется как единая метрика, объединяющая метрики полноты и точности в одну метрику. F-мера для данного запроса вычисляется по формуле:
Отметим основные свойства:
·
· если или , то
· если , то
·
F-мера алгоритмов полказана на рисунке 5.
генетический алгоритм векторный ранжирование
Рис.5. F-мера
Среднее значение f-меры: ГА=0,20; ВМ=0,14.
Модификация с генетическим алгоритмом обладает лучшими значениями метрик, по сравнению с базовым алгоритмом. Но при этом не оправдана сама эффективность использования векторной модели для ранжирования, т.к. вычисление косинусной меры сходства между вектором запроса и каждым вектором документа коллекции, сортировка по релевантности и выбор лучших документов является довольно затратным процессом и требует выполнения десятков тысяч арифметических операций.
Литература
1. Маннинг, Кристофер Д. Введение в информационный поиск. М. : Вильямс, 2011.
2.Дубинский А.Г. Некоторые вопросы применения векторной модели представления документов в информационном поиске // Управляющие системы и машины. 2001. № 4.
Размещено на Allbest.ru
...Подобные документы
Вероятностный подход к поиску. Основы теории вероятностей. Содержание правила Байеса. Проблема ранжирования документов, принцип вероятности. Бинарная модель независимости. Вывод функции ранжирования для терминов запросов. Okapi BM25: небинарная модель.
презентация [406,9 K], добавлен 06.01.2014Виды документов и их классификация. Правила оформления телефонограмм. Составление и оформление служебных документов. Понятие и назначение трафарета, разновидности предъявляемые требования. Необходимость соблюдения аккуратности при оформлении документа.
курсовая работа [45,9 K], добавлен 04.12.2010Разработка модели лифта, алгоритма и программы на языке JavaScript. Возможность использования модели при проектировании промышленных лифтов и отладки управляющих программ. Основные принципы построения модели лифта, выполнение вычислительного эксперимента.
курсовая работа [495,8 K], добавлен 09.06.2013Исследование основных концепций информационного поиска: булева и векторная модели, индексные термины. Реализация векторной модели в среде Matlab, расчет ранжированных списков документов, реализация оценок качества поиска и листинг программы в Matlab.
отчет по практике [444,8 K], добавлен 17.06.2012Алгоритм реализации векторного пространства, метод фильтрации шумов на изображении. Формально-логическая модель разработки программного обеспечения, выбор инструментальных средств его реализации. Анализ точности совпадения распознанного изображения.
дипломная работа [2,7 M], добавлен 13.02.2013Векторная и растровая графика: основные отличия, преимущества и недостатки. Компьютерные программы, используемые для создания растровой и векторной графики. Трехмерная графика, цветовое пространство и графический формат. Основные цветовые модели.
реферат [37,0 K], добавлен 20.12.2010Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
курсовая работа [1,5 M], добавлен 07.07.2013Межбиблиотечный абонемент и доставка документов входит в число важнейших средств функционирования информационного пространства. Проблема стандартизации технологии и терминологии в библиотечном деле. Перспективы развития электронной доставки документов.
контрольная работа [24,2 K], добавлен 17.11.2010Распределенная обработка данных. Двухуровневые модели распределения основных функций. Применение модели сервера приложений и баз данных. Основные пути распараллеливания запросов. Общая характеристика программных средств подготовки табличных документов.
отчет по практике [52,6 K], добавлен 30.09.2009Логическое проектирование реляционной модели данных для службы качества предприятия. Перечень документов, их реквизиты, номер по классификатору, форма их составления. Определение атрибутов электронных документов для их идентификации. Выбор режима доступа.
курсовая работа [54,8 K], добавлен 13.09.2009Поиск информации в Интернет: стратегия и методика. Глобальные и российские каталоги и поисковые машины: принцип работы, преимущества и недостатки. Аналитический обзор найденных документов по теме "Учет денежных средств, документов и переводов в пути".
курсовая работа [56,4 K], добавлен 03.11.2010Преимущества использования Word при создании веб-страниц. Его публикация Word в библиотеке документов. Преобразование документа Word в веб-страницу. Функции HTML-конвертора Word97. Пересмотр документа Word и веб-страницы. Отображение закладок в документе.
реферат [23,6 K], добавлен 06.04.2010Построение структурной схемы модели системы, укрупненной схемы моделирующего алгоритма. Проект математической модели информационно-поисковой библиографической системы, построенной на базе двух ЭВМ и имеющей один терминал для ввода и вывода информации.
курсовая работа [598,2 K], добавлен 21.06.2011Расчет тепловой схемы с применением методов математического моделирования. Разработка алгоритма реализации модели. Составление программы для ПЭВМ, ее отладка и тестирование. Проведение численного исследования и параметрическая оптимизация системы.
курсовая работа [2,8 M], добавлен 01.03.2013Общая характеристика закона Хипса и Ципфа. Особенности ранжированного поиска. Рассмотрение примеров косинусной близости. Анализ основных способов сокращения индекса. Знакомство с основными моделями векторного пространства. Проблемы отсечения кластеров.
презентация [565,1 K], добавлен 06.01.2014Анализ руководящих документов по антитеррору и проведению специальных операций. Анализ современных методов 3D-моделирования, его функциональные возможности и методы повышения оптимизации. Разработка имитационной 3D-модели, и базы данных филиала.
дипломная работа [5,0 M], добавлен 03.06.2013Построение концептуальной модели и метод имитационного моделирования. Определение переменных уравнений математической модели и построение моделирующего алгоритма. Описание возможных улучшений системы и окончательный вариант модели с результатами.
курсовая работа [79,2 K], добавлен 25.06.2011Типы документооборота: универсальный, операционный. Преимущества электронного документооборота. Модели информационного пространства. Построение модели предметной области (документооборота) для конкретного бизнеса, позиционирование в ней предприятия.
реферат [197,4 K], добавлен 23.06.2011Описание алгоритма и исходного кода программы формирования графовой модели заданного фрагмента принципиальной электрической схемы. Разработка схемы алгоритмов решения задачи. Результаты решения контрольных примеров, выполненные с помощью программы.
контрольная работа [47,8 K], добавлен 14.10.2012Достоинства и недостатки векторной графики, ее применение и основной принцип построения графических объектов. Объектно-ориентированный подход к пакетам векторной или иллюстративной графики. Основные программы, редакторы и форматы векторной графики.
курсовая работа [129,0 K], добавлен 30.05.2015
