ВВЕДЕНИЕ
Актуальность темы
Становление современного информационного общества немыслимо без использования информационных ресурсов в электронном виде. Переведенные в электронную форму и собранные в общую систему, информационные ресурсы приобретают новый статус, в котором реализуется качественно иной уровень хранения и распространения самой разнообразной информации, обеспечивая им более широкое распространение и эффективное использование [1-2]. Однако возникающие при этом коллекции документов имеют большую неоднородность. Как показывает статистика, доля структурированных данных в подобных архивах составляет не более 20%, остальные же 80% приходятся на долю различных документов, сканированных текстов и другой разрозненной информации [3]. При этом возникает проблема эффективного поиска адекватной информации, решение которой позволяет превратить разрозненные данные в целостную систему знаний [4]. Существующие поисковые системы первого поколения не могут в полной мере решить задачу поиска релевантной информации в полнотекстовых коллекциях, во многом по причине ориентированности на реляционные модели поиска, слабо применимые к поиску информации в коллекциях документов на естественном языке.
Именно поэтому в последние годы ведутся исследования и разработки поисковых систем нового поколения, с привлечением основных достижений искусственного интеллекта (ИИ), как наиболее подходящего инструмента для решения поставленной задачи - эффективного интеллектуального поиска информации в полнотекстовых базах данных.
Ряд авторитетных исследователей внесли своими научными трудами значительный вклад в развитие информационно-поисковых систем: И.С. Некрестьянов, Д.А. Поспелов, В.Ю. Добрынин, А.Г. Дубинский, И.Е. Кураленок, А.Е. Ермаков, М.Р. Когаловский, A.B. Сокирко, Ф.У. Ланкастер, G. Salton, А. Singhai, M. 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 и др.
Проблеме построения эффективных систем полнотекстового поиска информации с помощью прогрессивных методов искусственного интеллекта посвящена и данная диссертационная работа.
В работе предложено использование математических моделей поиска информации, описываемых нечеткими графами второго рода, что позволит учитывать семантику документа и повысить релевантность ответа за счет использования смыслового содержания документов и знаний экспертов о предметной области.
Объект исследования
В настоящей работе исследуется возможность и целесообразность применения новых методов и моделей интеллектуального поиска адекватной информации в полнотекстовых базах данных, а также разработка алгоритмов поиска релевантной информации с использованием полученных моделей. Цели и задачи работы
Целью настоящей диссертационной работы является разработка методов и моделей поиска адекватной информации в полнотекстовых базах данных, имеющих более высокую релевантность ответа по сравнению с существующими аналогами и позволяющую привлекать знания экспертов с целью повышения качества поиска. Для достижения поставленной цели предлагается использовать семантико-ориентированную модель поиска информации, основанную на использовании нечетких графов для представления смысла документов.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
6
1. Анализ существующих методов и моделей поиска адекватной информации, выявление достоинств и недостатков этих методов.
2. Разработка математической модели поиска, включающей представление исходного текстового документа, его поискового образа и расширенного запроса пользователя с использованием одного из современных направлений искусственного интеллекта - нечетких семантических и фреймовых сетей.
3. Разработка алгоритмов и комплекса программ для поиска информации в полнотекстовых базах данных на основе разработанной математической модели. Разработка общей архитектуры полнотекстовой информационно-поисковой системы. Проведение имитационного моделирования.
4. Теоретическая и экспериментальная оценка быстродействия и ресурсоемкое™ разработанных алгоритмов.
Основные научные результаты
1. Разработана математическая модель информационного поиска, позволяющая достигнуть большей полноты и точности за счет использования семантического содержимого документов и возможности учета априорной информации о предметной области в виде знаний экспертов.
2. Разработаны алгоритмы построения поискового образа документа, позволяющие учитывать помимо словесного портрета документа, его семантику, выраженную в виде отношения ассоциативной связанности на множестве термов документа.
3. Разработан алгоритм повышения степени релевантности документов относительно определенных понятий, отличающийся от существующих наличием нескольких видов отношений, используемых при увеличении релевантности и возможностью управления полнотой и точностью поиска. Основные положения, выносимые на защиту
1. Модель представления знаний в интеллектуальной поисковой системе.
2. Алгоритм расширения поискового запроса пользователя.
7
3. Метод интеллектуального поиска информации в полнотекстовой базе данных.
4. Архитектура полнотекстовой интеллектуальной поисковой системы, учитывающая особенности построения полнотекстовых поисковых систем и предлагаемых моделей поиска.
Практическая ценность
1. Модели документа, поискового образа и расширенного запроса позволяющие получить более релевантный ответ за счет использования семантической составляющей документов и запроса.
2. Алгоритмы построения поискового образа документа и расширенного поискового запроса, соответствующие разработанной математической модели. Разработанные алгоритмы могут служить основой при построении поисковых систем нового поколения с более высокой точностью поиска, возможностью настройки на конкретную предметную область и привлечением знаний экспертов по предметной области для повышения точности и полноты поиска.
3. Результаты исследования трудоемкости и ресурсоемкости предлагаемых алгоритмов, указывающие на возможность программной реализации предлагаемых алгоритмов в рамках однопроцессорного вычислительного комплекса.
4. Разработанный вариант функциональной архитектуры полнотекстовой интеллектуальной информационно-поисковой системы, ориентированной на работу с учетом особенностей полнотекстовых баз данных и использующей предложенные алгоритмы поиска адекватной информации.
Методы исследования
При выполнении данной работы использовались элементы теории информационных систем, методы искусственного интеллекта, элементы теории нечетких множеств, теория графов, элементы теории принятия решений. В
8
качестве основных методов исследования использованы математические модели и имитационное компьютерное моделирование.
Апробация работы
Результаты работы докладывались и обсуждались на научно-практических конференциях:
- Международная научная конференция «Интеллектуальные САПР» (Дивноморск, 2003).
- Международная научная конференция «Системный подход в науках о природе, человеке и технике» (Таганрог, 2003).
- Всероссийская научная конференция молодых ученых и аспирантов «Информационные технологии, системный анализ и управление» (Таганрог, 2003).
- VI всероссийская научная конференция «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2003).
- 11-й Всероссийская межвузовская научно-техническая конференция «Микроэлектроника и информатика-2004» (Москва, 2004).
- XI Всероссийская научно-методическая конференция "Телематика'2004" (С. Петербург, 2004)
Результаты, полученные в работе, нашли отражение в 10 печатных работах, четыре из которых были опубликованы в центральной печати. Шесть работ были опубликованы в сборниках научных трудов конференций, в том числе две работы были представлены на международных конференциях, четыре — на всероссийских конференциях.
Достоверность полученных в диссертации результатов основана на строгих математических выводах при указании соответствующих ограничений на входные данные, на корректном применении математического аппарата нечеткой логики, теории графов, и подтверждается разработкой действующего программного пакета индексирования и поиска адекватной информации, проведенными экспериментами.
Структура работы
Материал основной части диссертационной работы изложен на 164 страницах машинописного текста. Диссертация состоит из введения, четырех разделов, заключения и списка литературы из 101 наименований, содержит 21 рисунок, 4 таблицы и 5 приложений на 47 страницах. Содержание работы
В первом разделе работы рассмотрены основные концепции построения существующих полнотекстовых поисковых систем в разрезе требований, предъявляемых к идеальной информационно-поисковой системе. Сделано заключение о невозможности удовлетворения постоянно растущих требований к поисковым системам в рамках существующих моделей и алгоритмов поиска. В этом разделе приведены общие требования к разрабатываемым поисковым системам, показатели эффективности.
В разделе обоснована необходимость применения аппарата нечеткой логики при сравнении сложных структур, под которыми в данной работе понимаются семантические сети информационных объектов, заложенные в основу математической модели поиска информации.
Во втором разделе приведены основные математические модели, предлагаемые к использованию в данной диссертационной работе. Рассмотрена модель исходного документа, представленная в виде фреймовой сети. Предлагаемая модель позволяет абстрагироваться от формата документа, сохраняя при этом важную информацию о структуре документа. В этом разделе описаны предлагаемые модели поискового образа документа и расширенного запроса пользователя, основанные на применении математического аппарата нечеткой логики и семантических сетей. Предлагаемые модели отличаются от уже известных наличием семантической составляющей и ближе к моделям, применяемым при решении задачи анализа документов. Приведены примеры таких моделей.
В разделе также показана возможность применения знаний экспертов о предметной области, оформленных в виде соответствующей базы данных, для
10
повышения релевантности ответа и получения расширенного запроса. Рассмотрены различные операции нечеткой логики, проведен анализ их применимости для решения задачи построения и использования базы знаний экспертов.
Третий раздел диссертационной работы посвящен разработке алгоритмов построения расширенного поискового запроса, алгоритма построения поискового образа документа, алгоритма сравнения поискового образа документа с запросом, а также общего алгоритма поиска информации.
Расширение поискового запроса выполняется на основании интерактивного взаимодействия пользователя и информационно-поисковой системы с привлечением экспертной информации. В разделе указан шаблон такого диалога, приведены варианты грамматик языка запроса. Рассмотрены три типа запроса. Для каждого из типов составлен алгоритм его обработки и расширения.
Алгоритм построения поискового образа документа основан на описанных в главе 2 моделях и применяется для построения поискового индекса документа, сохраняемого затем в базе данных. Для сравнения поискового запроса и образа документа используются методы сравнения сложных структур. В этой главе также указан алгоритм выполнения такого сравнения с учетом модели хранения и представления запроса и образа документа.
В данном разделе также приведены основные результаты имитационного моделирования, демонстрирующие принципы построения информационно-поисковой системы с использованием предлагаемых алгоритмов. Результаты имитационного моделирования в свою очередь влияют на параметры работы некоторых алгоритмов, что и продемонстрировано в разделе 3.
В четвертом разделе рассмотрены особенности архитектуры полнотекстовых информационных систем. В разделе выполнен теоретический расчет предельной вычислительной сложности каждого из алгоритмов и приведены результаты имитационного моделирования. Выполнена оценка
и
требуемых для работы алгоритмов ресурсов и оценка объема памяти, необходимого для хранения индексов обработанных документов. Показан вариант архитектуры полнотекстовой информационно-поисковой системы с подробным описанием назначения и функционирования каждого блока в отдельности и системы в целом.
Приведен пример работы разработанной ИПС на коллекции документов и сравнение полученных результатов с результатами, полученными при использовании других поисковых систем. В завершении раздела приведено общее описание предлагаемого подхода в разрезе положительных и отрицательных моментов его использования. Очерчен круг задач, при решении которых целесообразно применять предлагаемые алгоритмы и методы поиска. Указаны присущие предлагаемому подходу недостатки и пути их устранения.
В заключении излагаются основные результаты диссертационной работы.
Приложения содержат исходные данные и результаты имитационного моделирования, результаты исследования нечетких операций, список терминов, применяемых в данной работе, исходный текст программы.
12 1. АНАЛИЗ СУЩЕСТВУЮЩИХ СИСТЕМ ПОИСКА ИНФОРМАЦИИ В
ПОЛНОТЕКСТОВЫХ БД
1.1. Общее описание, задачи и основные требования к поисковым системам
Общая задача поиска ставится максимально широко - помочь пользователю найти нужную ему информацию [4]. Однако полноценное описание информационного запроса - задача далеко нетривиальная. Для этих целей обычно используется описание запроса с использованием некоторого языка или модели запроса.
Классическая постановка задачи информационного поиска - это поиск документов, удовлетворяющих запросу, в рамках некоторой статической (на момент выполнения поиска) коллекции документов. Примером таких систем служат большинство современных справочных систем, электронные энциклопедии и т.д. Однако в течение последних нескольких десятков лет исследований список задач информационного поиска значительно расширился и теперь включает вопросы моделирования, классификации и кластеризации документов, проектирования архитектур поисковых систем (ПС) и пользовательских интерфейсов, языки запросов, и т. д. [5, 6].
ПС играет роль посредника между пользователем и информационной средой. Пользователь обращается к ПС, формулируя запрос на интересующую его информацию (форма запроса зависит от конкретной реализации ПС и состоит, как правило, из ключевых слов и словосочетаний интересующей тематики, с возможными логическими связками типа "И", "ИЛИ", "НЕ"). На основе полученного запроса ПС производит, тем или иным способом, поиск информации среди обработанных системой документов. Результатом поиска является список ссылок на найденные документы, содержащие требуемую информацию.
Базируясь на приведенном выше описании, перечислим задачи и общие требования, предъявляемые к разрабатываемым полнотекстовым поисковым системам.
13
Основной задачей ПС является эффективная трансляция запроса пользователя по требуемой информации на список проиндексированных ресурсов, где эта информация содержится.
Идеализированная ПС должна отвечать следующим требованиям:
- требование удобства и полноты представления запросов для пользователя — форма входного запроса должна позволять легко выражать любые требования, относящиеся к интересующей информации, будучи при этом интуитивно понятной и простой в применении;
- требование точности проводимого поиска — все адреса, возвращаемые ПС, должны быть релевантны запросу пользователя;
- требование полноты осуществляемого поиска — идеальная ПС должна возвращать список, включающий абсолютно все полезные документы, хранящиеся в коллекции;
- высокая скорость работы — время обработки запроса должно быть приемлемым для пользователя.
Определим понятия точности и полноты поиска формально [7, 8]. Точность поиска (precision, accuracy) — отношение числа релевантных документов, предъявленных пользователю, к общему числу документов, предъявленных ПС в результате проведенного поиска. Минимальное (худшее) значение этого параметра — "О" (ни одного релевантного документа не найдено), максимальное (лучшее) — "1" (все предъявленные ПС документы релевантны);
Precision = \RrA\/\A\, (1.1)
где R - множество истинно релевантных документов, А - множество документов, идентифицированных ПС как релевантные.
Общность поиска (generality) — отношение релевантных документов, предъявленных пользователю, к общему числу релевантных документов в коллекции. Минимальное (худшее) значение — "О",
14
максимальное (лучшее) — "1" (в последнем случае найдены абсолютно все хранимые в коллекции релевантные документы);
Recall = \RnA\/\R\ (1.2)
Смысл последних терминов иллюстрируется рис. 1.1, отображающем некоторую ситуацию, возникшую при работе ПС. На рисунке черным показан сектор непросмотренных при поиске нерелевантных документов (73%), темно-серым — доля просмотренных нерелевантных документов 0.05 (5%), белым —непросмотренные релевантные документы (10%), светло-серым — просмотренные релевантные документы 0.12 (12%). Общая доля релевантных документов в коллекции составляет 0.22 (22%), нерелевантных документов 1-0.22 = 0.78 (78%). Тогда точность поиска Precision и общность поиска Recall будут равны:
Precision^----—----= 0.71 (71%),
0.12 + 0.05
Recall = — = 0.55 (55%). 0.22 V
Следует отметить, что приведенные требования относятся к «идеализированной» ПС. Ни одна из существующих в настоящий момент ПС не отвечает предъявленным требованиям в полной мере. Список возвращаемых ссылок на ресурсы, как правило, содержит много нерелевантной запросу информации. С другой стороны, далеко не все имеющиеся в коллекции полезные документы будут найдены. Одной из причин этого является то, что требования общности и точности поиска являются в известной мере противоречивыми: если мы хотим выбрать из коллекции все релевантные документы (т.е. повысить общность поиска), то, как правило, при поиске будет захвачена большая доля нерелевантных документов (пострадает точность поиска). Наоборот, при стремлении к высокой точности поиска, "за бортом" окажется большая доля релевантных документов, отвергнутых из стремления не захватить ненужные документы. На практике, между этими параметрами
15
соблюдают разумный компромисс. Поэтому, в большинстве случаев, полученные через ПС ссылки используются лишь как отправная точка для последующего "ручного" поиска.
10% -
12% /
L 5% 1
1 ^Г 73%
Рис 1.1 Диаграмма состояния коллекции документов при поиске
релевантной информации
Кроме описанной выше постановки задачи, можно выделить некоторые особенности формулировки, актуальные при поиске информации в полнотекстовых БД. Существует два подхода решения этой задачи. Первый заключается в том, что информация из различных источников загружается в специальную "систему управления знаниями". В данном случае информация хранится внутри системы и доступ к ней осуществляется только средствами специализированных поисковых средств. Примером такого подхода служит СУБД Oracle с подсистемой RCO фирмы Тарант-Парк-Интернет" [9] и большинство современных СУБД.
Другим подходом является подход, при котором на сеть существующих источников накладывается единая информационно-поисковая система, обеспечивающая прозрачный поиск и категоризацию документов (шведская система Fulcrum или отечественная Следопыт 3.0) [10]. Взяв в качестве примера использования этого подхода технологию Fulcrum, можно сказать, что подобное решение характеризуется большей гибкостью и универсальностью
16
системы. Ключом к пониманию технологий Fulcrum можно считать девиз, сформулированный более десяти лет назад: "Одна точка доступа к любой информации через любую платформу, на любом языке". Действительно, эти технологии поддерживают широкий спектр аппаратно-программных платформ, работу с различными источниками данных и более чем 200 форматами документов, а также обработку многоязыковых документов (практически все европейские языки, арабский, японский, корейский и многие другие) [11].
При сравнении описанных технологий, необходимо отметить, что использование для хранения данных специализированных средств позволяет унифицировать алгоритмы работы с документами, использовать четкие алгоритмы работы бизнес-процесов при работе с документами [6, 12].
Ф Подобные системы обычно легко масштабируются до любых размеров (вопрос
масштабирования решается ну уровне СУБД, поисковая система, встроенная в СУБД масштабируется вместе с базой данных, претерпевая при этом минимальные изменения). Плюсом второго подхода является одновременно минус первого. Это, прежде всего, гибкость и универсальность системы. Использование внешнего для массива информации поискового средства позволяет работать с уже готовыми (наработанными ранее) массивами документов, упростить ввод новых документов в систему, работать с разнородной информацией. Минусом такой схемы является ее худшая масштабируемость и скорость работы. В жертву универсальности в данном случае приносится скорость. Однако на современном этапе расвития подобные системы широко внедряются и используются, что говорит о том, что скорость их работы является достаточной для эксплуатации в реальных условиях [11]. 1.2. Существующие модели информационного поиска Несмотря на то, что многие поисковые системы функционируют без
^ какой либо явно выраженной математической модели, в тех случаях, когда речь
идет о повышении качества поиска, необходимо рассматривать процесс поиска не только с алгоритмической позиции, но и с точки зрения математической модели функционирования программы. Модель информационного поиска
17
включает в себя две составляющие: методы автоматической индексации и методы определения степени релевантности текстовых документов запросу на основе анализа составленного индекса.
Классические модели информационного поиска рассматривают документы как множества представляющих эти документы ключевых слов, в дальнейшем называемых термами. Терм - это просто слово, семантика которого помогает описать основное содержание документа.
Формально, описание любой модели информационного поиска может быть записано в виде четверки [13]:
- D - множество используемых типов представлений документов;
- Q - множество используемых типов описаний информационных № потребностей пользователя, т. е. запросов;
- F - общий каркас, в рамках которого происходит моделирование описаний документов и запросов, а также описание взаимосвязей между ними;
- R(q,di) - функция ранжирования, которая паре документ/запрос сопоставляет некоторое вещественное число.
Модели информационного поиска делятся на три класса:
. 1. Теоретико-множественные модели. Модели этого класса используют в
качестве каркаса теорию множеств. Классический пример - булева модель. В рамках этой модели документы и запросы представляются в виде множеств термов.
2. Вероятностная модель. Каркасом для таких моделей выступает теория вероятностей. В качестве оценки релевантности документа запросу пользователя используется вероятность того, что пользователь признает документ истинно релевантным.
3. Алгебраическая модель. В рамках алгебраических моделей документы и запросы описываются в виде векторов в многомерном пространстве. Каркасом для таких моделей выступают алгебраические методы.
|
