Содержание к диссертации
Введение
1. Анализ существующих систем поиска информации в полнотекстовых БД 12
1.1. Общее описание, задачи и основные требования к поисковым системам 12
1.2. Существующие модели информационного поиска 16
1.3. Информационно-поисковый язык 27
1.4. Обзор существующих поисковых систем 31
1.5. Обобщенная архитектура и недостатки существующих поисковых систем 46
1.6. Выводы 50
2. Разработка моделей представления знаний в интеллектуальной поисковой системе 51
2.1. Модель полнотекстового документа 53
2.2. Модель поискового образа документа 60
2.3. Модель поискового запроса 64
2.4. Модель базы знаний экспертов 68
2.5. Выводы 71
3. Разработка методов и алгоритмов поиска адекватной информации в полнотекстовых БД 73
3.1. Алгоритм построения поискового образа документа 73
3.2. Формальная грамматика поискового языка 91
3.3. Алгоритмы построения расширенного поискового запроса на основе предложенной грамматики 96
3.4. Алгоритм сравнения поискового образа и запроса 104
3.5. Алгоритм построения семантической сети предметной области 115
3.6. Общий алгоритм поиска релевантной информации 119
3.7. Выводы 122
4. Разработка архитектуры интеллектуальной поисковой системы 124
4.1. Особенности архитектуры полнотекстовой поисковой системы 124
4.2. Оценка временной сложности используемых алгоритмов 126
4.3. Архитектура поисковой системы 136
4.4. Результаты имитационного моделирования работы ИПС на коллекции технических документов 143
4.5. Выводы 151
Заключение 153
Литература 156
Приложение 1 165
- Обобщенная архитектура и недостатки существующих поисковых систем
- Модель поискового образа документа
- Алгоритмы построения расширенного поискового запроса на основе предложенной грамматики
- Результаты имитационного моделирования работы ИПС на коллекции технических документов
Введение к работе
Актуальность темы
Становление современного информационного общества немыслимо без использования информационных ресурсов в электронном виде. Переведенные в электронную форму и собранные в общую систему, информационные ресурсы приобретают новый статус, в котором реализуется качественно иной уровень хранения и распространения самой разнообразной информации, обеспечивая им более широкое распространение и эффективное использование [1-2]. Однако возникающие при этом коллекции документов имеют большую неоднородность. Как показывает статистика, доля структурированных данных в подобных архивах составляет не более 20%, остальные же 80% приходятся на долю различных документов, сканированных текстов и другой разрозненной информации [3]. При этом возникает проблема эффективного поиска адекватной информации, решение которой позволяет превратить разрозненные данные в целостную систему знаний [4]. Существующие поисковые системы первого поколения не могут в полной мере решить задачу поиска релевантной информации в полнотекстовых коллекциях, во многом по причине ориентированности на реляционные модели поиска, слабо применимые к поиску информации в коллекциях документов на естественном языке.
Именно поэтому в последние годы ведутся исследования и разработки поисковых систем нового поколения, с привлечением основных достижений искусственного интеллекта (ИИ), как наиболее подходящего инструмента для решения поставленной задачи - эффективного интеллектуального поиска информации в полнотекстовых базах данных.
Ряд авторитетных исследователей внесли своими научными трудами значительный вклад в развитие информационно-поисковых систем: И.С. Некрестьянов, Д.А. Поспелов, В.Ю. Добрынин, А.Г. Дубинский, И.Е. Кураленок, А.Е. Ермаков, М.Р. Когаловский, А.В. Сокирко, Ф.У. Ланкастер, G. Saltan, A. Singhal, М. Mitra, S. Lawrence, P. Foltz, E. Fox, J. Cho, R. Baeza-Yates, K. Tajima, C. Van Rijsbergen, L. Gravano, J. Kleinberg.
5 Кроме того, существуют коммерческие организации, занимающиеся не только вопросами исследований, но и вопросами внедрения информационных поисковых технологий, это такие известные организации как Яндекс, Рамблер, Апорт, НейрОК, Гарант-Парк-Интернет, Медиа Лингва, Галактика-Зум, ABB YY-FTR, Hummingbird, Convera и др.
Проблеме построения эффективных систем полнотекстового поиска информации с помощью прогрессивных методов искусственного интеллекта посвящена и данная диссертационная работа.
В работе предложено использование математических моделей поиска информации, описываемых нечеткими графами второго рода, что позволит учитывать семантику документа и повысить релевантность ответа за счет использования смыслового содержания документов и знаний экспертов о предметной области.
Объект исследования
В настоящей работе исследуется возможность и целесообразность применения новых методов и моделей интеллектуального поиска адекватной информации в полнотекстовых базах данных, а также разработка алгоритмов поиска релевантной информации с использованием полученных моделей. Цели и задачи работы
Целью настоящей диссертационной работы является разработка методов и моделей поиска адекватной информации в полнотекстовых базах данных, имеющих более высокую релевантность ответа по сравнению с существующими аналогами и позволяющую привлекать знания экспертов с целью повышения качества поиска. Для достижения поставленной цели предлагается использовать семантико-ориентированную модель поиска информации, основанную на использовании нечетких графов для представления смысла документов.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
1.. Анализ существующих методов и моделей поиска адекватной информации, выявление достоинств и недостатков этих методов.
Разработка математической модели поиска, включающей представление исходного текстового документа, его поискового образа и расширенного запроса пользователя с использованием одного из современных направлений искусственного интеллекта - нечетких семантических и фреймовых сетей.
Разработка алгоритмов и комплекса программ для поиска информации в полнотекстовых базах данных на основе разработанной математической модели. Разработка общей архитектуры полнотекстовой информационно-поисковой системы. Проведение имитационного моделирования.
Теоретическая и экспериментальная оценка быстродействия и ресурсоемкости разработанных алгоритмов.
Основные научные результаты
Разработана математическая модель информационного поиска, позволяющая достигнуть большей полноты и точности за счет использования семантического содержимого документов и возможности учета априорной информации о предметной области в виде знаний экспертов.
Разработаны алгоритмы построения поискового образа документа, позволяющие учитывать помимо словесного портрета документа, его семантику, выраженную в виде отношения ассоциативной связанности на множестве термов документа.
Разработан алгоритм повышения степени релевантности документов относительно определенных понятий, отличающийся от существующих наличием нескольких видов отношений, используемых при увеличении релевантности и возможностью управления полнотой и точностью поиска. Основные положения, выносимые на защиту
Модель представления знаний в интеллектуальной поисковой системе.
Алгоритм расширения поискового запроса пользователя.
Метод интеллектуального поиска информации в полнотекстовой базе данных.
Архитектура полнотекстовой интеллектуальной поисковой системы, учитывающая особенности построения полнотекстовых поисковых систем и предлагаемых моделей поиска.
Практическая ценность
Модели документа, поискового образа и расширенного запроса позволяющие получить более релевантный ответ за счет использования семантической составляющей документов и запроса.
Алгоритмы построения поискового образа документа и расширенного поискового запроса, соответствующие разработанной математической модели. Разработанные алгоритмы могут служить основой при построении поисковых систем нового поколения с более высокой точностью поиска, возможностью настройки на конкретную предметную область и привлечением знаний экспертов по предметной области для повышения точности и полноты поиска.
Результаты исследования трудоемкости и ресурсоемкости предлагаемых алгоритмов, указывающие на возможность программной реализации предлагаемых алгоритмов в рамках однопроцессорного вычислительного комплекса.
Разработанный вариант функциональной архитектуры полнотекстовой интеллектуальной информационно-поисковой системы, ориентированной на работу с учетом особенностей полнотекстовых баз данных и использующей предложенные алгоритмы поиска адекватной информации.
Методы исследования
При выполнении данной работы использовались элементы теории информационных систем, методы искусственного интеллекта, элементы теории нечетких множеств, теория графов, элементы теории принятия решений. В
8 качестве основных методов исследования использованы математические модели и имитационное компьютерное моделирование.
Апробация работы
Результаты работы докладывались и обсуждались на научно-практических конференциях:
Международная научная конференция «Интеллектуальные САПР» (Дивноморск, 2003).
Международная научная конференция «Системный подход в науках о природе, человеке и технике» (Таганрог, 2003).
Всероссийская научная конференция молодых ученых и аспирантов «Информационные технологии, системный анализ и управление» (Таганрог, 2003).
VI всероссийская научная конференция «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2003).
11-й Всероссийская межвузовская научно-техническая конференция «Микроэлектроника и информатика-2004» (Москва, 2004).
XI Всероссийская научно-методическая конференция "Телематика'2004" (С. Петербург, 2004)
Результаты, полученные в работе, нашли отражение в 10 печатных работах, четыре из которых были опубликованы в центральной печати. Шесть работ были опубликованы в сборниках научных трудов конференций, в том числе две работы были представлены на международных конференциях, четыре — на всероссийских конференциях.
Достоверность полученных в диссертации результатов основана на строгих математических выводах при указании соответствующих ограничений на входные данные, на корректном применении математического аппарата нечеткой логики, теории графов, и подтверждается разработкой действующего программного пакета индексирования и поиска адекватной информации, проведенными экспериментами.
Структура работы
Материал основной части диссертационной работы изложен на 164 страницах машинописного текста. Диссертация состоит из введения, четырех разделов, заключения и списка литературы из 101 наименований, содержит 21 рисунок, 4 таблицы и 5 приложений на 47 страницах. Содержание работы
В первом разделе работы рассмотрены основные концепции построения существующих полнотекстовых поисковых систем в разрезе требований, предъявляемых к идеальной информационно-поисковой системе. Сделано заключение о невозможности удовлетворения постоянно растущих требований к поисковым системам в рамках существующих моделей и алгоритмов поиска. В этом разделе приведены общие требования к разрабатываемым поисковым системам, показатели эффективности.
В разделе обоснована необходимость применения аппарата нечеткой логики при сравнении сложных структур, под которыми в данной работе понимаются семантические сети информационных объектов, заложенные в основу математической модели поиска информации.
Во втором разделе приведены основные математические модели, предлагаемые к использованию в данной диссертационной работе. Рассмотрена модель исходного документа, представленная в виде фреймовой сети. Предлагаемая модель позволяет абстрагироваться от формата документа, сохраняя при этом важную информацию о структуре документа. В этом разделе описаны предлагаемые модели поискового образа документа и расширенного запроса пользователя, основанные на применении математического аппарата нечеткой логики и семантических сетей. Предлагаемые модели отличаются от уже известных наличием семантической составляющей и ближе к моделям, применяемым при решении задачи анализа документов. Приведены примеры таких моделей.
В разделе также показана возможность применения знаний экспертов о предметной области, оформленных в виде соответствующей базы данных, для
10 повышения релевантности ответа и получения расширенного запроса. Рассмотрены различные операции нечеткой логики, проведен анализ их применимости для решения задачи построения и использования базы знаний экспертов.
Третий раздел диссертационной работы посвящен разработке алгоритмов построения расширенного поискового запроса, алгоритма построения поискового образа документа, алгоритма сравнения поискового образа документа с запросом, а также общего алгоритма поиска информации.
Расширение поискового запроса выполняется на основании интерактивного взаимодействия пользователя и информационно-поисковой системы с привлечением экспертной информации. В разделе указан шаблон такого диалога, приведены варианты грамматик языка запроса. Рассмотрены три типа запроса. Для каждого из типов составлен алгоритм его обработки и расширения.
Алгоритм построения поискового образа документа основан на описанных в главе 2 моделях и применяется для построения поискового индекса документа, сохраняемого затем в базе данных. Для сравнения поискового запроса и образа документа используются методы сравнения сложных структур. В этой главе также указан алгоритм выполнения такого сравнения с учетом модели хранения и представления запроса и образа документа.
В данном разделе также приведены основные результаты имитационного моделирования, демонстрирующие принципы построения информационно-поисковой системы с использованием предлагаемых алгоритмов. Результаты имитационного моделирования в свою очередь влияют на параметры работы некоторых алгоритмов, что и продемонстрировано в разделе 3.
В четвертом разделе рассмотрены особенности архитектуры полнотекстовых информационных систем. В разделе выполнен теоретический расчет предельной вычислительной сложности каждого из алгоритмов и приведены результаты имитационного моделирования. Выполнена оценка
требуемых для работы алгоритмов ресурсов и оценка объема памяти, необходимого для хранения индексов обработанных документов. Показан вариант архитектуры полнотекстовой информационно-поисковой системы с подробным описанием назначения и функционирования каждого блока в отдельности и системы в целом.
Приведен пример работы разработанной ИПС на коллекции документов и сравнение полученных результатов с результатами, полученными при использовании других поисковых систем. В завершении раздела приведено общее описание предлагаемого подхода в разрезе положительных и отрицательных моментов его использования. Очерчен круг задач, при решении которых целесообразно применять предлагаемые алгоритмы и методы поиска. Указаны присущие предлагаемому подходу недостатки и пути их устранения.
В заключении излагаются основные результаты диссертационной работы.
Приложения содержат исходные данные и результаты имитационного моделирования, результаты исследования нечетких операций, список терминов, применяемых в данной работе, исходный текст программы.
Обобщенная архитектура и недостатки существующих поисковых систем
Общей чертой всех рассмотренных систем является использование промежуточного представления данных — индекса, составляемого программой-роботом, автоматически сканирующим информационную среду в основном по принципу исчерпывающего поиска. Отдельный класс поисковых систем, выполняющих поиск информации непосредственно при обработке документов (различного рода поисковые роботы, основанные на самостоятельном поиске в коллекции документов) в рассмотрение не берется.
Обработка запросов пользователей осуществляется независимо от операции составления индекса, с помощью кластера высокопроизводительных рабочих станций, способных "просмотреть" обширный индекс за доли секунды. Иллюстрируемая рис. 1.2 архитектура классических ПС продиктована их происхождением: эти системы имеют своими предшественниками ПС предыдущего поколения, которые были ориентированы на работу с локализованными хранилищами данных. Современные ИПС, ориентированные на работу в полнотекстовых базах данных имеют некоторые отличные архитектурные особенности.
По сути, построение индекса есть упрощение исходной информации, хранимой в коллекции документов, до уровня централизованной (или распределенной на небольшом числе компьютеров) коллекции регулярных данных. Тем самым, решение задачи поиска информации сводится к давно отработанной задаче поиска информации в мощной, но вполне классической реляционной базе данных (пусть с добавлением некоторых нюансов, таких как вычисление степени релевантности документа по его индексу). Именно благодаря такому подходу ему удалось быстро построить работающие ПС, полезность которых ни у кого не вызывает сомнений.
Однако, данному подходу присущи принципиальные недостатки, которые, вытекают из неполного соответствия поискового индекса самому документу. Практически все существующие ПС обладают следующими недостатками. 1. Низкая интеллектуальность поиска документов в коллекции — как видно из сделанного обзора, индекс составляется с помощью простейших программ-роботов, использующих наибыстрейшие (а значит и самые простые) методы. Индекс составляется "на все случаи жизни", т.е. для произвольного запроса и, следовательно, не может быть ориентирован заранее на конкретную информацию или предметную область. Используемые в существующих системах модели индексирования не достаточно полно описывают документ. Из универсальности индекса вытекает его низкая точность при отработке конкретного запроса. Сжатие информационного содержимого документа в индекс, каким бы сложным методом оно не проводилось, неминуемо приводит к потере части информации, что принципиально снижает общность и точность поиска по сравнению с поиском, опирающимся на непосредственное сравнение полного содержимого документа с запросом пользователя. Однако чрезмерное расширение индекса так же не может быть использовано, ввиду ограничений, накладываемых на размер индекса (он должен физически храниться на компьютере или вычислительном кластере). Поэтому, при составлении индекса должен соблюдаться разумный баланс между сложностью и полнотой индекса и его размером. Необходимо использовать модели, несущие максимум информации, имеющие максимальную информационную емкость. 2. Упрощенность процедуры вычисления степени релевантности документа на основе индекса. Сложные интеллектуальные методы пока мало применимы ввиду их повышенной вычислительной сложности, недостаточной информационной насыщенности запроса пользователя и индекса. Даже мощные интеллектуальные алгоритмы не смогут повысить релевантность ответа на достаточно простые запросы пользователя. 3. Отсутствие средств для полноценного расширения запроса пользователя с целью повышения полноты поиска информации. В данном случае подразумевается использование различного рода словарей и баз данных, позволяющих в автоматическом или диалоговом режиме расширять запрос сходными по смыслу терминами, позволяющими захватывать релевантные документы даже при отсутствии в них термов, указанных в запросе. Подобные схемы применяются лишь в небольшом количестве систем (например Fulcurum) и пока еще не полностью отработаны все механизмы. Развитие данного подхода одной из мощных альтернатив развития технологий поиска информации, 4. Отсутствие средств для удобного уточнения результатов запроса. В существующих традиционных ИПС указание дополнительных параметров запроса сильно уменьшает полноту поиска, нет возможности гибкого управления параметрами запроса для регулирования соотношения критериев полноты/точности поиска. Роль пользователя в поиске информации недостаточна, пользователь практически выключен из процесса поиска. В указанной архитектуре имеется односторонний поток данных запроса пользователь - подсистема обработки запроса и подсистема выдачи результата - пользователь. Системы диалогового составления запросов не получили должного развития что сильно усложняет поиск информации неподготовленным пользователем, особенно при наличии у него неполной информации о предмете поиска.
Следствием перечисленных недостатков является общее низкое качество поиска, производимого классическими ПС в случае существования неоднозначности в описании предмета поиска (что присуще большинству предметных областей и является одной из особенностей литературной и технической письменной речи), при несовпадении моделей знаний о предметной области пользователя и ИПС (если такая модель вообще используется). Отсутствие полноценного диалога с пользователем сильно затрудняет задачу поиска и приводит к получению нерелевантных ответов вследствие составления некорректного или неполного запроса.
Модель поискового образа документа
Для построения подобной иерархии, необходимо осуществить сканирование исходного документа, выполнить разбиение на лексические единицы, с последующим их объединением в более крупные блоки, с учетом атрибутов оформления документов [43-45]. Вид атрибутов, указывающих на тот или иной уровень текстовой информации, зависит от формата документа, и может различаться в широких диапазонах или отсутствовать вообще. Так, например, для текстов, оформленных по стандарту html, xml для оформления текста используются теги, для документов Microsoft Word различные стили и т.д.
Простейший алгоритм построения подобной иерархической структуры на основе анализа документа может быть построен с использованием теории трансляторов [35,46-50]. Использование предложенной модели позволяет ввести дополнительный уровень абстракции, между исходным документом и алгоритмом построения поискового образа документа. Его введение позволяет при разработке алгоритма построения ПОДа не вдаваться в особенности конкретного типа документа. Алгоритм становится независимым от формата предоставления документа. Кроме того, алгоритм построения подобного иерархического объекта может быть далеко нетривиален, поэтому, в данной работе в качестве входных данных для алгоритма построения ПОДа выступает подобная структура, уже содержащая в себе всю необходимую для алгоритма информацию в удобном для использования виде. 2.2. Модель поискового образа документа Документ хранится в базе данных ИПС в виде своего образа, заменяющего текст документа при выполнении операции вычисления релевантности. Задача построения модели ПОД является одной из наиболее важных, так как именно ПОД определяет, насколько точно может быть восстановлено исходное содержание документа, необходимое для вычисления степени релевантности [51-53]. С целью повышения информативности ПО Да и учета семантики исходного документа в данной работе предлагается использовать аппарат семантических сетей, позволяющий максимально полно описывать семантику документов [39,40, 54-57].
К достоинствам семантических сетей относят естественность, наглядность и понятность по сравнению с другими подходами (например по сравнению с языком исчисления предикатов); способность представлять смысл фраз естественного языка; возможность выступать в роли семантической модели информации в банках данных [42]. Кроме того, язык семантических сетей однороден, что является важным его преимуществом по сравнению с другими, так как использование для записи информации в базу знаний языков со сложным синтаксисом связано с серьезными трудностями.
Поисковый образ документа представляется в виде неориентированного нечеткого графа второго рода [51, 52, 58, 59]: где Xd - нечеткое множество вершин, Xd={ jUxd(x)/x }, xeXd, Xd- носитель нечеткого множества Xd. Элементы множества Xd соответствуют термам, содержащимся в документе. Функция принадлежности /uxd(x) определяет степень принадлежности терма документу (его вес при описании документа списком термов). Нечеткое множество Ud={ ud(x,y)/(x,y) }, x.yeXd, описывает множество ребер, соответствующих отношению «ассоциативной связности» термов документа. Функция принадлежности juud(x,y) определяет степень связанности термов х и у в пределах документа и зависит от частоты совместной встречаемости термов в документе, близости их положения в тексте. Способы вычисления степени синтаксической близости приведены в следующей главе. Все степени принадлежности являются вещественными величинами со значениями, лежащими в диапазоне от 0 до 1.
Введение в модель документа помимо вершин еще и ребер, обозначающих связи между термами позволяет учитывать отношения термов между собой, выделять группы взаимосвязанных одной тематикой участков документа, экстрагировать минимальные по заданному критерию множества термов, характеризующих документ с определенной позиции, выявлять сверхфразовые взаимосвязи между термами [60].
Для пояснения, приведем фрагмент ПОД, описывающего конкретный документ с названием «Иерархия Хомского. Регулярные языки» (рис. 2.2).
Документ содержит классификацию грамматик по Холмскому, основанную на используемых правилах вывода. В тексте явно можно выделить обособленные блоки: блок термов «грамматика», «контекст», «язык» -описывающий типы языков и грамматик во взаимосвязи с контекстом (классификация на контекстно-свободные языки описываемые контекстно-свободные грамматиками, контекстно-зависимые языки), блок термов «грамматика», «класс», «иерархия» встречающиеся совместно при описании иерархии классов грамматик, и блок термов относящихся к описанию каждого класса - на основании правил, состоящих из цепочек символов. Между термами «грамматика» и «правила», также между «правила» и «цепочки» существует связь с весом «1», так как эти термы встречаются рядом в одном предложении. Связь между термами «грамматика» и «цепочки» имеет меньший вес, так как они встречаются в разных предложениях, но в пределах одного абзаца и имеют связь через третьи понятия.
Алгоритмы построения расширенного поискового запроса на основе предложенной грамматики
В описанной выше модели общения пользователя и ИПС при формировании расширенного запроса, имеются блоки типа «С» - выполнение вычислительной процедуры, подразумевающие действия по расширению запроса на стороне ИПС. Результатом этих действий должно являться расширение запроса синонимами и гипонимами, известными ИПС. Рассмотрим алгоритм работы ИПС при использовании каждого из трех типов рассматриваемых запросов.
При использовании языка, соответствующего грамматике (3.8) (например при работе ИПС без использования интерактивного расширения запроса) необходимо говорить не сколько о расширении запроса, сколько о повышении степени релевантности документов относительно определенных понятий. В работе [66] указана возможность подобного повышения релевантности с использованием транзитивного замыкания концептуальной матрицы — матрицы связи между концепциями (термами). Воспользуемся этим алгоритмом, модифицировав его для использования в рамках разработанной модели знаний ИПС, имеющей некоторые отличия от модели, рассматриваемой в работе [66]. Как описано в главе 2.4, знания экспертов представляются не одной, а двумя матрицами - матрицей отношения синоним и матрицей отношения гипоним, что вносит некоторые коррективы в использование указанного подхода.
Обозначим за N - количество документов, уже проиндексированных ИПС, N terms — количество термов в предметной области (размер словаря термов Г (2.1)), Ks — матрица отношения «быть синонимом», заданная на множестве термов Г (2.9), Кс - матрица отношения «быть синонимом», заданная на множестве термов Т (2.9), D — матрица термы-на-докмуненты, составляемая на основании объедения вершин ПОДов всех проиндексированных документов (2.5), h — величина порога, определяющая максимальную степень, в которую возводится объеденная матрица знаний экспертов. Последняя величина необходима для управления сходимостью операции нахождения матрицы транзитивного замыкания (ее существование зависит от выбранного базиса операций). В случае если матрица транзитивного замыкания не будет найдена за h шагов, вместо нее будет использоваться матрица h — ой степени.
Работа алгоритма заключается в нахождении матрицы, позволяющей повысить релевантность документов относительно определенных термов. Для этого вычисляется матрица транзитивного замыкания (или матрица h -ой степени) которая затем используется при модификации существующей матрицы термы-на-документы D. Вычисление степени релевантности с использованием подобной расширенной матрицы аналогично расширению запроса термами, связанными с указанными пользователем [66, 67]. где операция «+» соответствует логическому сложению матриц. В качестве операции «v» могут использоваться операции (2.14) - (2.16). При использовании формулы (2.14) в качестве значения элемента обобщенной матрицы выбирается максимум. Это означает, что если термы г, и /, являются синонимами со степенью принадлежности Ksy и терм tj является одним из частных понятий терма /, со степенью принадлежности Кс то в качестве степени связности между этими термами будет взято то значение, которое максимально. Это достаточно строгое утверждение, позволяющее повысить точность обобщенной матрицы [67]. Если же в качестве операции «v» используется (2.15) или (2.16), то степень связи в результирующей матрице превысит значения, взятые из каждой матрицы в отдельности. В этом случае одно отношение усиливает другое, что соответствует модели рассуждения «если термы являются в некоторой степени синонимами, к тому же еще один из термов является в некоторой степени частным понятием другого, то связь между ними даже выше чем каждая из степеней по отдельности». Использование формул (2.15), (2.16) позволяет повышать полноту результатов поиска, однако в ряде случаев это приведет к снижению точности (особенно при использовании формулы (2.16), которая очень быстро возрастает с увеличением степеней принадлежности операндов - смотри Приложение 2) [67]. Алгоритм 3.11 Исходные данные:
Замечание: использование матрицы транзитивного замыкания соответствует достаточно идеализированной модели знаний. Ее использования основано на допущении, приведенном в работе [66], что, если терм Г, является синонимом терма /,, а он в свою очередь является синонимом терма (с указанным значением веса связи между синонимами) то терм /Л также является синонимов терма tt с весом связи равным минимуму из весов связей между ti и tj, и tj и 4. Это рассуждение расширяется на цепочки синонимов любой длинны. Это замечание истинно далеко не всегда. В большинстве случаев, при использовании синонимических рядов большой длины, семантическое значение исходного терма может теряться или искажаться. Так, например, цепочка синонимов «граф» - «отношение» - «позиция» - «положение» - «поза» ярко демонстрирует искажение семантического содержания начального терма. Аналогичные рассуждения справедливы и для гипонимического отношения, но в несколько иной форме - чрезмерное углубление в частные понятия может привести к потере первоначального смысла.
В действительности, необходимо говорить об окружении терма группой синонимов с заданной длинной цепочки (3,5,10 связей). В этом случае, для расширения запроса будет использоваться не матрица транзитивного замыкания, а матрица достижимости [81]. В алгоритме (3.11) роль подобного регулятора играет порог h. Он указывает максимальную длину цепочки, рассматриваемую при построении списка синонимов [67]. При использовании некоторых вариантов операций нечеткой логики (в Приложении 2 приведено сравнение операторов) результат нахождения матрицы транзитивного замыкания схож с результатом, полученным при нахождении матрицы достижимостей [81].
В заключение следует отметить, что при использовании запроса, описываемого самой простой из рассматриваемых грамматик, для повышения степени адекватности ответа необходимо автоматически расширять запрос. Для этого необходимо использовать знания экспертов о предметной области. Разработанный алгоритм основан на работе [66], однако, в отличие от нее разработанный алгоритм учитывает несколько различных матриц, выполняя предварительно операцию нахождения обобщенной матрицы. Это позволяет использовать всю имеющуюся экспертную информацию, а не только матрицу синонимов (концептуальная матрица в терминах [66]). Кроме того, разработанный алгоритм позволяет варьировать трудоемкость и качественный результат расширения запроса путем изменения порога h, регулирующего максимальную степень матрицы. Кроме того, введение такого порога автоматически снимает проблему доказательства существования матрицы транзитивного замыкания. В случае ее несуществования используется матрица степени h. Разработанный алгоритм, в отличие от [66], может использовать расширенный базис операций, что позволяет в некоторых пределах регулировать соотношение между полнотой и качеством поиска путем выбора базиса.
Результаты имитационного моделирования работы ИПС на коллекции технических документов
С целью проверки работоспособности разработанных моделей, алгоритмов и архитектуры ИПС, а также анализа получаемых при помощи предлагаемых методов поиска результатов и сравнения этих результатов с аналогами, было проведено имитационное моделирование с использованием разработанной программной модели, текст которой приведен в приложении 5.
При анализе результатов, представляет интерес следующая информация: - распределение весов (суммарных) термов, попавших в ПОДы документов, позволяющее судить о тематическом содержании коллекции документов, выделить карту главных тем; - распределение весов (суммарных) связей между термами (база знаний предметной области (2.17)), позволяющая определить взаимосвязи между темами предметной области, выделить устойчивые в пределах предметной области словосочетания, проводить анализ термов на «синонимичность» в рамках предметной области; - результаты поиска в виде списка с установленными степенями релевантности, варианты расширения запроса; - оценка выдаваемого списка экспертами и сравнение полученных с помощью программы оценок с экспертными; - сравнение получаемых результатов с результатами работы других ИПС (по возможности). Для исследования была выбрана коллекция документов гипертекстовой организации, состоящая из электронной библиотеки центра дистанционного образования (курсы лекций, теоретическая информация) по ряду тематик, по большей части технического содержания: теория систем, информации, множеств, графов, математика, алгебра, геометрия, компьютерная графика, языки программирования, инженерия знаний, искусственный интеллект и т.д. Коллекция состоит из более чем 2,5 тысяч документов. Размер коллекции составляет порядка 50 Мб. Размер документов колеблется от I Кб до 2 Мб. Имитационное моделирование проводилось на компьютере с процессором Intel Celeron РШ 1000, объем ОЗУ 256 Мб. Операционная система Windows 98. В качестве СУБД использовался Microsoft Access. При моделировании использовались следующие параметры: - размер ПО Да в термах выбирался равный 50%; - максимальное число связей у одного терма в ПО Де - не более 20. В результате проведения индексирования и сохранения ПОДов в базу данных был получен индекс, содержащий около 500 000 вершин (термы, входящие в состав ПОДов) и 6 000 000 связей в этих ПО Дах. Общее количество словоформ, найденных в коллекции составило величину порядка 120 000 словоформ (включая русские и английские).
Анализ результатов распределение весов (суммарных) термов, попавших в ПОДы документов можно проводить по трем критериям: частоте встречаемости терма среди ПОДов, весу терма в ПОДе или общей частоте встречаемости терма (суммарная по всем ПО Дам). Анализ результатов моделирования позволил выявить список наиболее часто встречающихся в коллекции. Этот список приведен в таблице 4.1. приложения 4.
Очевидно, что с высоким значением частоты встречаются ключевые термы предметной области и слова, соответствующие описанию основных термов. Такие термы как множество, определение, элемент, нечеткий, расплывчатый, вершина, граф, ребро, порядок, связность, таблица, отношение, логика, соответствие встречаются достаточно часто. Достоверность полученной картины позволяет сделать вывод о правильности работы алгоритма присвоения весов термам, попадающим в ПОД. Применяемые алгоритмы позволяют получать достоверную картину о распределении термов по предметной области. Наиболее значимые терм, как и предполагалось, будут иметь более высокое значение веса, чем шумовые слова. Термы общих понятий «пример», «существовать», «образ», «произвольно» и некоторые другие демонстрируют, что, несмотря на высокую частоту встречаемости (они находятся в списке первых 10 наиболее встречаемых) их суммарный вес значительно меньше, чем других, более информативных, термов, что позволяет сделать вывод о корректном использовании модификации itf df метода (раздел 1.2) для определения степени значимости терма не только в документе, но по коллекции в целом.
Составленная на основании совокупности связей по всем ПО Дам семантическая сеть может дать представление о тематической карте коллекции, о взаимосвязях между термами предметной области и, как было описано в главе 3.5, является источником автоматического расширения запроса при отсутствии или недостаточной экспертной информации. Фрагмент такой семантической сети представлен на рис. 4.1. приложения 4.
Ее анализ позволяет сделать заключение о том, что предложенные алгоритмы построение семантической сети ПОДа позволяют получить представление о предметной области, однако алгоритм актуализации таких данных, к сожалению, не очевиден. В данной работе не рассматриваются алгоритмы анализа семантической сети на предмет выявления скрытых закономерностей, этим направлением занимается инженерия знаний. Однако предложенные алгоритмы позволяют получить исходную информацию, представленную в виде, удобным для анализа, как эксперту, так и автоматизированным средствам.
Развитие данного направления следует связывать с привлечением лингвистических алгоритмов, позволяющих выявлять дополнительные типизированные отношения в тексте (отношения времени, принадлежности, места и т.д.) что существенно повысит мощность предлагаемой модели и позволит, не меняя общего алгоритма работы и архитектуры ИПС, существенно увеличить качество поиска.
Для демонстрации результатов работы алгоритма построения расширенного поискового запроса было произведено несколько экспериментов, включающих как расширение на основании знаний экспертов, так и расширение на основании анализа предметной области. Для примера был выбран запрос: «Определение графа».
При наличии знаний экспертов о предметной области, и анализе проиндексированных документов, может быть получен расширенный вариант запроса. Покажем на примере запроса «Определение фафа», схему получения расширенного запроса. Схема работы ИПС по построению расширенного запроса приведена на рис. 4.3.
