Содержание к диссертации
Введение
Глава 1. Анализ предметной области. постановка задач исследования 14
1.1. Определения используемых терминов 14
1.2. Постановка задачи уточнения поисковых запросов 18
1.3. Подходы к решению задач полнотекстового информационного поиска 22
1.3.1, Виды полнотекстового информационного поиска 22
1.3.2, Классификация моделей полнотекстового поиска 24
1.3.3, Обзор моделей полнотекстового поиска 26
1.4. Подходы к решению задачи уточнения поисковых запросов . 33
1.4.1. Классификация методов уточнения поисковых запросов . 33
1.4.2. Обзор методов уточнения поисковых запросов , . 35
1.5. Выводы по главе 40
Глава 2. Контекстно-ассоциативная модель текстовых документов 42
2.1. Модель смысловых контекстов текста 44
2.1.1. Построение словаря терминов 44
2.1.2. Определение смысловых контекстов текстового документа 52
2.1.3. Свойства смысловых контекстов текстового документа , . 57
2.2. Контекстно-ассоциативная модель текста 63
2.3. Алгоритм решения задачи уточнения запросов 70
2.4. Выводы по главе : 71
Глава 3. Оценка эффективности метода уточнения поисковых запросов 73
3.1. Планирование экспериментов 73
3.1.1. Тестовые коллекции электронных документов 73
3.1.2. Тестовые наборы заданий 75
3.1.3. Выбор информационно-поисковой системы 76
3.1.4. Критерии оценки 77
3.2. Эффективность решения задачи уточнения поисковых запросов 81
3.2.1. Оценка оптимальных параметров 83
3.2.2. Анализ влияния уровня контекстно-ассоциативной сети . 89
3.2.3. Оценка устойчивости к ошибкам пользователей 90
3.3. Эффективность решения задачи поиска пр документу-образцу 92
3.4. Сравнительный анализ применения контекстно-ассоциативного метода 102
3.4.1. Подготовка и проведение экспериментов 102
3.4.2. Результаты экспериментов 104
3.5. Выводы по главе 109
Заключение
Список использованных источников
- Подходы к решению задач полнотекстового информационного поиска
- Подходы к решению задачи уточнения поисковых запросов
- Определение смысловых контекстов текстового документа
- Эффективность решения задачи уточнения поисковых запросов
Введение к работе
Теоретические исследования в области автоматизированных полно-текстовых информационно-поисковых систем (ИПС) начались в связи с появлением первых компьютерных хранилищ электронных текстовых документов [39, 50, 21, 100]. В настоящее время миллиарды документов стали доступными в электронной форме, созданы десятки тысяч электронных библиотек практически по всем областям человеческих знаний, многие из которых носят распределенный характер. Важную роль в этом процессе сыграло появление и развитие глобальных сетей передачи данных, и, в первую очередь, сети Интернет.
Большинство существующих в настоящее время современных ИПС основаны на хорошо известных и апробированных методах информационного поиска [33, 49, 50, 18]. Эти методы ориентированы, прежде всего, на решение общей задачи информационного поиска в хранилищах электронных документов, расположенных в компьютерных сетях общего пользования, и учитывают специфику и тенденций развития этих сетей [80, 44]. К таким тенденциям можно отнести: быстрый рост числа новых документов и высокие темпы изменения уже имеющихся, низкую степень структурированности документов и избыточность (дублирование) информации [47, 13] и т.д.
По типу и целевому назначению хранилища электронных документов можно условно разделить на несколько видов:
электронные средства массовой информации, такие как , , ленты новостей (, и т.д.), электронные версии традиционных "бумажных" периодических изданий (, и т.д.);
_5-
электронные библиотеки — книжно-журнальная продукция, хранящаяся в электронном виде в фондах обычных или полностью электронных библиотек — электронные каталоги и хранилища Российской государственной библиотеки (), Государственной публичной научно-технической библиотеки России (GPNTB.Ru), других библиотек, фондов, таких как Научная электронная библиотека, созданная при содействии РФФИ (), а также электронные библиотеки ряда высших учебных заведений, охватывающих большой объем публикаций в виде научных статей, книг, рефератов научно-технических журналов, патентной информации и учебной литературы;
коллекции документов целевого назначения — тексты, вводимые в компьютер специально для информационного обеспечения определенных видов деятельности (например, информационно-поисковые правовые системы "Консультант Плюс", "Кодекс", "Гарант" и т.п.)
Одной из наиболее известных электронных библиотек общего доступа в сети Интернет является архив научных статей из области компьютерных и информационных технологий CiteSeer (), созданный в NEC Research Institute и содержащий библиографические ссылки, тексты и индекс цитирования публикаций, сделанных в этой области за последние 20 лет.
Тенденции быстрого роста числа и объема электронных хранилищ текстов обуславливают интерес к решению задач полнотекстового поиска в предметно-ориентированной литературе, которые имеют свою специфику и требуют разработки новых или модификации уже имеющихся информационно-поисковых методов, использующих анализ особенностей терминологического состава и структуры хранилищ электронных документов [31, 29, 26, 27].
В России проблемами исследования методов информационного по-
иска занимается достаточно большое число групп специалистов, среди которых И.Е. Кураленок, И.С. Некрестьянов, В.Ю. Добрынин (СПбГУ, Санкт-Петербург), М.С. Агеев (НИВЦ МГУ, Москва), Б.В. Добров (УИС РОССИЯ, Москва), П.И. Браславский (ИМаш УрО РАН, Екатеринбург), В.В. Плешко, А.Е. Ермаков ("Гарант-Парк-Интернет", Москва), М. Губин ("Кодекс", Санкт-Петербург), М.Р, Когаловский (ИПР РАН, Москва), А.В. Сокирко ("АОТ", Москва), И.В. Сегалович ("Яндекс", Москва), И.С. Ашманов, В.И. Шабанов ("Рамблер", Москва), А.В. Антонов, B.C. Мешков ("Галактика", Москва), А.Н.Федоровский ("", Москва), ОТ. Чанышев (ИИТПМ СО РАН, Омск), В.Л. Чугреев (ЛЭТИ, Санкт-Петербург) и др.
Вопросам исследований в области информационного поиска посвящены всероссийская конференция "Электронные библиотеки: перспективные методы и техиологии"^СОЬ), являющаяся одной из секций АСМ SIGMOD, международная конференция по компьютерной лингвистике и интеллектуальным технологиям "Диалог", а также Российский семинар по Оценке Методов Информационного Поиска (РОМИП), начавший свою ежегодную работу в 2003 году и ставший российским аналогом международных конференций по исследованиям, анализу и оценке методов информационного поиска: Text Retrieval Conference (TREC, США), Cross Language Evaluation Forum (CLEF, EC), ACM Special Interest Group on Information Retrieval (SIGIR), NII-NACSIS Test Collection for IR Systems (NTCIR, Япония).
Несмотря на достаточно высокий современный уровень исследований, в теории информационного поиска остается ряд открытых проблем, одной из которых является проблема неоднозначного выбора терминов, используемых пользователями ИПС в поисковых запросах. Эта проблема состоит в том, что пользователи ИПС часто применяют для описания
_7-
клгочевых понятий термины, отличные от терминов, которые используют авторы для описания тех же понятий в текстах [24]. Эта проблема является особенно актуальной в случае поиска в технической и специализированной литературе. В общем случае данную проблему можно сформулировать следующим образом: новые или неопытные пользователи неверно или неточно выражают свою информационную потребность ключевыми словами и, как следствие, получают информацию, не соответствующую их информационным потребностям [74].
В большинстве случаев найденные в ходе поиска документы оказываются нерелевантными (т.е. не соответствующими по смыслу или требованиям) информационной потребности пользователя ИПС, что обусловлено:
неумением большинства пользователей ИПС сформулировать запрос, используя средства языка запросов конкретной ИПС;
отсутствием у ряда пользователей ИПС предметных знаний, позволяющих подобрать правильные ключевые термины;
различием между поисковой релевантностью, являющейся оценкой степени соответствия найденных документов запросу, и релевантностью, которая является мерой соответствия этих документов информационной потребности пользователя ИПС.
Несмотря на то, что ключевые термины не всегда хорошо описывают смысловое содержание искомых документов, подавляющее большинство ИПС основываются исключительно на поиске по ключевым словам. Это объясняется тем, что пользователям ИПС проще выразить свою информационную потребность на привычном им естественном языке в виде нескольких, по их мнению - ключевых, терминов.
Однако, практика показывает, что в общем случае два различных человека (автор искомого документа и пользователь ИПС) используют один и тот же термин для описания одного и того же понятия менее чем в 20%
случаев [74].
Эта проблема стоит еще более остро для коротких поисковых запросов: чем длиннее запрос, тем больше вероятность того, что наиболее важные термины из искомых документов попадут в поисковый запрос. Тем не менее, пользователи ИПС обычно не склонны выражать свою информационную потребность в виде длинных поисковых запросов или использовать специальные средства, позволяющие более точно формулировать запрос (например, языки поисковых запросов). Практика показывает, что поисковые запросы, включающие более 2-х терминов, встречаются реже чем в 25% от общего числа случаев, а запросы из 4-х и более терминов — менее чем в 2% случаев [13].
В большинстве случаев решение этой проблемы сводится к работе, связанной с итерационным переформулированием исходного запроса, которую пользователь ИПС берет на себя. Несмотря на высокий уровень исследований в теории информационного поиска, методики уточнения поисковых запросов "вручную" в настоящее время играют ключевую роль для эффективного применения ИПС. Тот факт, что в настоящее время проводятся соревнования среди специалистов по поиску в Web (например, "Кубок Яндекса"), лишний раз показывает актуальность подобных методик и сложность их практического использования.
Вышеперечисленное обуславливает актуальность разработки и внедрения специальных средств, связанных с решением задачи уточнения поисковых запросов, в связи с чем в теории информационного поиска возникло направление, связанное с исследованием, методов автоматизации процесса уточнения поисковых запросов. В рамках этого направления актуальной остается проблема разработки модели естественно-языковых текстов, которая бы позволила проводить их совместный анализ с целью выделения и оценки значимости общих ключевых терминов, что, в частности, позволило
бы применять ее в алгоритмах уточнения поисковых запросов с обратной связью по релевантности с пользователями ИПС.
Цель работы — разработка независимого от применяемой ИПС метода уточнения поисковых запросов с использованием обратной связи по релевантности (т.е. по соответствию результатов поиска информационным потребностям пользователей ИПС), основанного на анализе найденных в результате поиска по исходному запросу документов, которые пользователь ИПС выделил в качестве релевантных его информационным потребностям.
Для достижения цели диссертационной работы решаются следующие основные задачи:
Выделение смысловых контекстов текстовых документов, представляющих собой фрагменты текста, в которых наблюдаются устойчивые связи между определенными группами терминов.
Построение контекстно-ассоциативной модели для структурированной коллекции документов, позволяющей оценить значимость смысловых контекстов в рамках текстового документа, определить ключевые термины документа и дать количественную оценку их смысловой значимости в анализируемом текстовом документе.
Разработка метода уточнения запросов посредством использования ключевых терминов из документов, помеченных пользователем ИПС как релевантные исходному запросу.
Планирование и проведение экспериментальной оценки эффективности метода уточнения поисковых запросов путем анализа результатов поиска с использованием критериев оценки точности и полноты поиска, а также сравнительного критерия оценки качества поиска по исходному и уточненному запросам.
На защиту выносятся следующие результаты:
1. Модель смысловых контекстов текстового документа.
Контекстно-ассоциативная модель текстового документа.
Алгоритм определения ключевых терминов документа и количественной оценки их смысловой значимости в анализируемом текстовом документе.
Метод уточнения поисковых запросов посредством обратной связи по релевантности с применением контекстно-ассоциативной модели.
Научная новизна полученных результатов состоит в разработке контекстно-ассоциативной модели текстовых документов и исследовании эффективности ее применения для решения задачи уточнения поисковых запросов методом обратной связи по релевантности.
Методы исследования. При проведении исследований был использован математический аппарат алгебры множеств и методов прикладной лингвистики.
Практическая ценность работы позволяет использовать полученные модели, алгоритмы и метод для решения задач уточнения поисковых запросов при разработке прикладных информационно-поисковых систем, а также в задачах, связанных с анализом терминологического состава исследуемых текстов.
Пакет программ, реализующий разработанные в диссертационной работе методы и алгоритмы, автономен, не требует от пользователей предварительного изучения применяемых в нем методов и может использоваться в качестве модуля уточнения поисковых запросов в информационно-поисковых системах, реализующих полнотекстовые методы информационного поиска по ключевым словам.
Результаты работы внедрены в качестве математического и программного обеспечения:
модуля информационного поиска в электронной библиотеке учебно-методических пособий кафедры N805 "Математическая кибернети-
ка" МАИ;
подсистемы информационного поиска "Медицинской
информационно-консультационной системы (МИС)" (патент на изоб
ретение N 2207623 от 16.02.2001).
Апробация работы. Основные положения и результаты диссертационной работы обсуждались и докладывались на:
VIII Международном научно-техническом семинаре "Современные технологии в задачах управления, автоматики и обработки информации" (Алушта, 1999);
Научной сессии "МИФИ-2000" (Москва, 2000);
III Международной конференции "Авиация и космонавтика-2004" (Москва, 2004);
XIV Международной конференции по Вычислительной Механике и Современным Прикладным Программным Системам (ВМСППС'2005, Алушта).
Экспериментальная проверка эффективности применения разработанного метода на различных тестовых коллекциях электронных документов была осуществлена в рамках участия в III Российском семинаре по Оценке Методов Информационного Поиска (РОМИП'2005, Ярославль).
Публикации. По теме диссертационной работы опубликовано 9 печатных работ.
Структура и объем работы. Диссертационная работа состоит из введения, 3 глав, заключения, списка использованных источников из 108 наименований и 2 приложений. Общий объем работы - 135.страниц. Основной текст работы изложен на 1-12 страницах, из которых 8 страниц занимают графики и таблицы.
В первой главе дан обзор истории развития и оценка современного состояния исследований методов полнотекстового информационно-
го поиска. Выделен ряд задач, решение которых представляет исследовательский интерес в области теории построения информационно-поисковых систем и указана их специфика. Рассмотрена математическая модель информационно-поисковой системы и дана математическая постановка задачи уточнения поисковых запросов.
На основе сделанного обзора продемонстрирована актуальность решения задачи выбора ключевых терминов и применения универсальных методов уточнения поисковых запросов, не требующих знаний о специфике искомых документов и не использующих в ходе своего применения тезаурусов или иных моделей знаний предметных областей, к которым относятся искомые документы.
Приведена формулировка цели исследования, состоящая в разработке и оценке эффективности применения метода уточнения поисковых запросов с использованием обратной связи по релевантности, основанного на локальном контекстном анализе найденных в результате поиска по исходному запросу документов.
Вторая глава посвящена разработке математической модели смысловых контекстов, учитывающей терминологический состав произвольных текстов на естественном языке и отражающая наличие смысловых связей между терминами и предложениями, позволяющей более точно оценить контекст, в которых встречаются различные термины документа, отражающий смысловую направленность документа в целом, перейти от анализа вхождения отдельных терминов к более комплексному анализу групп терминов и их устойчивых сочетаний в анализируемом документе.
Описана контекстно-ассоциативная модель, позволяющая количественно оценивать значимость ассоциативных связей между смысловыми контекстами и выделять ключевые термины.
Изложен метод уточнения поисковых запросов с обратной связью по
релевантности, использующий свойства контекстно-ассоциативной модели и позволяющий строить уточненные поисковые запросы, улучшающие качество поиска.
В третьей главе описывается планирование и проведение экспериментальной оценки эффективности применения предложенного алгоритма уточнения поисковых запросов с обратной связью по релевантности и оценена эффективность применимости предложенного алгоритма для уточнения поисковых запросов при поиске в различных коллекциях электронных документов.
Изложены результаты анализа влияния параметров предложенной контекстно-ассоциативной модели па эффективность работы алгоритма уточнения поисковых запросов, а также оценка влияния ошибок пользователей ИПС на результаты работы алгоритма.
В заключении приводятся основные выводы и результаты, полученные в ходе диссертационной работы.
Подходы к решению задач полнотекстового информационного поиска
В настоящее время существует два основных подхода к решению основной задачи информационного поиска [28];
1. Поиск электронных документов по дескриптору.
Этот подход основан на поиске в коллекции по дескриптору — набору определенных характеристик электронных документов: автору электронного документа, дате его публикации, названию, тематической принадлежности к какой-либо категории (например, по принадлежности к разделу УДК) и т.п.
Моделями электронных документов в таком подходе являются их дескриптор (набор метаданных) -— иерархические структуры или упорядоченные списки, характеризующие электронные документы и задающие структуру поискового индекса.
Информационная потребность пользователя выражается в виде задания вариантов значений одного или нескольких метаданных, по которым осуществляется поиск, например, автора электронного документа и его УДК.
Основным преимуществом поиска по дескриптору является возможность использования реляционных хранилищ данных и соответствующих языков запросов, а также получение гарантированного результата поиска за определенное время, которое зависит от структуры и объема каталога, что позволяет указать верхнюю границу времени поиска.
Главными недостатками поиска по каталогу являются: необходимость проведения большого объема подготовительных работ, связанных с определению состава метаданных и их выделению в ин дексируемых документах; возникновение ошибок, совершенных в процессе построения поискового индекса, что может привести к снижению точности поиска и повышению его трудоемкости; сложность поддержания поискового индекса в актуальном состоянии в условиях регулярного поступления новых или обновления имеющихся электронных документов; высокие требования к однородности хранимой информации, в частности, изменение состава метаданных электронных документов может потребовать изменения структуры всего индекса и, как следствие, осуществление ревизии всех хранимых в нем электронных документов.
Наиболее удачным формализованным подходом к постановке и решению задачи библиографического поиска в хранилищах электронных документов, позволяющим автоматизировать работу с электронными каталогами, был предложен на симпозиуме, состоявшемся в 1995 в Дублине (США), где в качестве стандартного дескриптора электронных документов в библиотечных компьютерных системах было предложено Дублинское Ядро (Dublin Core) — структурированный набор метаданных для описания электронных документов, хранящихся в электронных библиотеках [68].
2. Поиск электронных документов по ключевым словам.
Поиск по ключевым словам — это полнотекстовый информационный поиск по вхождению ключевых слов из поискового запроса в текстовое содержание электронных документов в целом или их частей: заголовкам и подзаголовкам, аннотациям, определенным их частям: введению, заключению, выводам и т.д.
Основная задача полнотекстового поиска по" запросу предусматривает поиск по вербальным компонентам электронных документов. Поиск по их невербальным компонентам, таким как иллюстрации, формулы и т.п., как правило осуществляется посредством выделения и анализа их вербальных атрибутов, например, подписей и комментариев к рисунками, а также их вербальному контексту, например, тексту, окружающему ссылку на невербальный компонент. Так, при индексировании Web-страниц и графических иллюстраций часто используются вербальные контексты гиперссылок, указывающих на индексируемую страницу или иллюстрацию.
Преимуществом полнотекстового поиска является отсутствие необходимости предварительного построения их дескриптора и извлечения из индексируемых электронных документов метаданных. При этом, пользователь ИПС может не располагать какими-либо библиографическими данными искомых электронных документов.
Главным недостатком поиска по запросу является сложность оценки соответствия найденных электронных документов информационным потребностям поиска. Это прежде всего объясняется сложностью смысловой интерпретации документов, написанных на естественном языке и отсутствием в них какой-либо регулярных структур.
Наиболее эффективным является подход, совмещающий поиск по дескриптору электронных документов и поиск по ключевым словам в тексте электронных документов и текстовых полях их дескрипторов: названии документа, списке авторов и т.п.
Подходы к решению задачи уточнения поисковых запросов
Методики уточнения поисковых запросов "вручную" появились в начале 70-х годов XX века одновременно с появлением первых ИПС на коллекциях электронных документов. Однако их исследования были впервые проведены и опубликованы существенно позже [51, 79; 89].
Применение подобных методов требует от пользователей ИПС хорошее знаний языка ее запросов, механизма индексирования документов, состава и специфики проиндексированных документов, владения терминами и понятиями из предметной области, к которой относятся искомые документы, а также возможными различиями в их употреблении (например, в случае различных научных школ одни и те же понтия могут обозначаться разными терминами).
Это привело к возникновению автоматизированных методов уточнения поисковых запросов, направленных на решение следующих задач: задачи расширения поисковых запросов, состоящей в добавлении в исходный поисковый запрос синонимов или словоформ входящих в него ключевых терминов без изменения смыслового содержания исходного запроса; задачи уточнения (или переформулирования) поисковых запросов, состоящей в изменении исходного запроса посредством учета ключевых терминов из релевантных документов с целью уточнения смыслового содержания запроса и, как следствие, улучшения результативности поиска.
Методы решения задач расширения и уточнения поисковых запросов можно разделить на два больших класса: автоматические методы, не требующие участия пользователей ИПС в процессе уточнения запросов, т.е. методы, в большинстве которых релевантная выборка DTqel либо не строится совсем, либо в качестве Drqel выбираются документы из отклика ИПС, которые на основе специальных критериев принимаются в качестве релевантных [48]; методы, использующие механизм обратной связи по релевантности с пользователями ИПС, как правило, посредством анализа релевантной выборки Dqd, сформированной пользователем ИПС вручную [101, 97, 46, 56].
Использование автоматических методов уточнения запросов предполагает умение пользователей ИПС правильно выражать свою информационную потребность в виде исходного запроса. Таким образом, запрос полагается априори правильным, что ограничивает область применения этих методов системами, с которыми работают преимущественно специалисты в соответствующих предметных областях.
Методы с обратной связью по релевантности позволяют более точно учитывать в ходе поиска информационные предпочтения пользователей ИПС и позволяют сделать процесс поиска итерационным, применяя алгоритм уточнения поисковых запросов практически неограниченное число раз. Однако здесь приходится учитывать тот факт, что в большинстве случаев пользователи ИПС (и в первую очередь — непрофессиональный пользователи ИПС в Web) не предрасположены к поиску в несколько итераций [103].
В зависимости от объема и состава используемой информации, методы уточнения поисковых запросов подразделяются на глобальные и локальные: методы глобального анализа, основанные на использовании ин формации обо всей коллекции электронных документов и базирующиеся на гипотезе о том, что контекст ключевых терминов в поисковом запросе (т.е. их сочетание с другими терминами поискового запроса) может служить мерой смысловой близости релевантных документов [105]. методы локального анализа, работающие с документами, найденными в ходе поиска по исходному поисковому запросу [107]; при этом анализ документов проводится без какой-либо дополнительной информации о составе и специфике всей коллекции электронных документов в целом.
Определение смысловых контекстов текстового документа
Предлагаемая модель смысловых контекстов позволяет выявить характер взаимодействия терминов внутри текстового документа. На ее основе в дальнейшем будет построена контекстно-ассоциативная модель текстового документа, которая позволит дать количественные оценки взаимодействия терминов в произвольном текстовом документе.
Так как смысл терминов произвольного взятого текстового документа d может быть определен не только вне документа d, но и вне коллекции текстовых документов D, то, анализируя документ dt в большинстве случаев невозможно в полной мере оценить смысл присутствующих в нем терминов. Например, термин "ключ" благодаря собственной полисемии в различных контекстах может обозначать разные понятия. В текстах, относящихся к предметной области архитектуры и строительства в сочетании с терминами "замбк", "дверь" он обозначает средство отпирания замкбв, а в текстах из области природоведения в сочетании с терминами "вода", "река" он обозначает место, являющееся источником воды. Однако, посредством учета особенностей структуры исследуемого документа d и его терминологического состава можно попытаться оценить соотношение смысловой значимости входящих в него терминов и получить локальную (в пределах документа) качественную оценку этих соотношений.
Контексты, в которых встречаются термины, могут уточнять или корректировать смысл обозначаемых ими понятий. Например, термин "функция" является достаточно общим понятием в предметной области математики. Однако его сочетание с терминами "распределение" и "плотность" достаточно точно указывает на более узкую область математики — теорию вероятностей.
Определим смысловой контекст терминов документа d посредством анализа их совместной встречаемости с другими терминами этого документа.
Так как минимальным фрагментом текста с законченным смысловым содержанием является предложение, рассмотрим анализируемый текстовый документ d (или его некоторый фрагмент — главу, раздел, подраздел и т. п.) как последовательность предложений (7Гь7Г2,...,7Г„) и представим его в виде множества предлооїсений Я {7ГЬ7Г2,...,7ГП}, (2.2) пронумерованных в порядке их следования в документе d, где п — число предложений документа.
Пусть Td — словарь терминов объема т = \Td\, полученный в процессе последовательного терминологического разбора каждого из предложений документа d. Заметим, что согласно формализму рекурсивной сети, распознающей именные группы, в случае, если 1 і j т, возможен один из двух вариантов: либо термин U появляется раньше термина tj в документе d, либо термин tj является подтермином термина tj.
В дальнейшем будем считать, что #d включает те и только те предложения документа d, в которых встречается, по крайней мере, один из терминов, входящих в Td.
Введем на множестве Td х IJd отношение вхождения терминов в предложения, задаваемое матрицей вхождения 5)d = 5у размерности mxn, где: 1, ЄСЛИ терМИН t{ ВСТречаеТСЯ.В ПреДЛОЖеНИИ 7Tj, Sij = О, иначе. Множество предложений Щ С IId, в которых встречается термин t Є Td, назовем носителем этого термина в документе d: Щ = {ЇЇ Є Л : 4id(i)ind(7r) = 1}, где ind(t) — индекс термина t в Td, ind(Tr) — индекс предложения 7Г в #d, и введем оператор носителя терминов как отображение Td — 2я : vt є Td SuPP{f} = nt: (2.3)
Определение (2.3) задает оператор носителя только для одноэлементных подмножеств множества Td. Продолжение оператора носителя терминов на все множество подмножеств Td может быть задано в виде отображения 2Т — 2я следующим образом: ( П Пи если Тф0, Supp(T) - I ter (2.4) [ Я , если Г=0, где Т С ТЧ
Эффективность решения задачи уточнения поисковых запросов
Экспериментальная проверка эффективности предложенного контекстно-ассоциативного метода уточнения поисковых запросов в задаче уточнения поисковых запросов с обратной связью по релевантности, позволившая исследовать зависимость качества поиска от выбора параметров работы метода, проводилась на тестовых коллекциях "Lenta.Ru" и "CITForum.Ru". Электронные документы коллекций были представлены для индексирования в виде отдельных Web-страниц.
Задачи экспериментальной оценки включали:
1. Оценку эффективности применения предложенного метода уточнения поисковых запросов в зависимости от числа ключевых терминов в уточненном запросе — Term, длины релевантной выборки пользователя ИПС — Doc и уровня контекстно-ассоциативной сети — Level.
2. Оценку оптимальных параметров работы метода (Term, Doc и Level).
3. Оценку устойчивости к ошибкам пользователей, связанным с включением в релевантную выборку нерелевантных документов.
4. Сравнительную оценку эффективности работы метода на коллекциях электронных документов различной тематики (при поиске в новостной коллекции и при поиске в коллекции технической документации).
5. Решение вопроса о правомерности применения критерия Aquality для оценки эффективности решения задачи уточнения поисковых запросов на основе его сравнения с общепринятыми критериями точности и полноты поиска.
В ходе экспериментальной проверки для каждой из 2-х текстовых коллекций было проведено 3 эксперимента по уточнению запросов:
с различным числом ключевых терминов и длинами релевантных выборок при фиксированном уровне контекстно-ассоциативной сети;
с различными уровнями контекстно-ассоциативной сети при оптимальном выборе числа ключевых терминов и длине релевантной выборки;
с наличием в релевантной выборке пользователей нерелевантных документов при фиксированной длине релевантной выборки.
Параметры, при которых проводились прогоны, приведены в таблице 3.3.
Из графиков зависимости изменения качества поиска от длины релевантной выборки (рис. 3.1) видно, что большинство из достигают сво их наибольших значений с ростом длины релевантной выборки. При этом дальнейший рост числа указанных релевантных документов приводит к заметному снижению качества уточненных запросов.
Исходя из поведения оценки Aquality можно сделать вывод, что рекомендуемое число документов, которые пользователь ЙПС должен указать в качестве релевантных при уточнении запроса для получения наилучших результатов, составляет 3 или 4 документа.
В свою очередь из графиков зависимости изменения качества поиска от числа ключевых терминов (рис. 3.2) видно, что улучшение качества поиска достаточно быстро достигает наибольших значений при 4-5 ключевых терминах.
Относительно высокую эффективность алгоритма уточнения запросов (свыше 60%) можно объяснить сравнительно низким качеством исходных запросов, длина которых не превышала 3 слов, что не позволяет в полной мере выразить информационную потребность поиска.
Подробные результаты оценки эффективности алгоритма уточнения поисковых запросов при значениях Док—3 и Терм=4 приведены, соответственно в таблицах 3.4 и 3.5.
Тот факт, что при выборе оптимальных параметров можно достигнуть достаточно высокого числа улучшенных запросов (до 80% от общего числа запросов, поступивших в ИПС) говорит о возможности применения предложенного алгоритма в прикладных ИПС.
При этом судить о результативности применения алгоритма к конкретному запросу можно на основе величины изменения оценки качества поиска (1,2) при Q — {q}. Об истинности такого предположения можно судить исходя из 11-точечных графиков зависимости полноты от точности поиска (рис. 3.3 и 3.4), построенных при при значениях Док=3 и Терм—4.
Вопрос о правомерности использования величины изменения оценки качества для оценки эффективности метода уточнения поисковых запросов можно решить, рассмотрев матрицу корреляций между экспериментальными величинами, описывающими процентом улучшенных запросов, средний процент изменения качества поиска и изменение средней точности поиска для обеих тестовых коллекций (табл. 3.6).
