Содержание к диссертации
Введение
Глава 1. Анализ моделей и систем поиска и обработки информации в базах знаний 13
1.1 Основные модели представления и обработки знаний 13
1.2 Анализ информационных моделей гипертекстовой информации 24
1.3 Классификация, основные характеристики и критерии эффективности информационно-поисковых систем 29
1.4 Обзор функциональных возможностей современных информационно-поисковых систем 37
1.5 Анализ моделей поиска информации в БЗ 45
1.6 Постановка целей и задач диссертационного исследования 56
Выводы по главе 1 59
Глава 2. Разработка моделей обработки и расширенного поиска информации в иерархических базах знаний 60
2.1 Разработка модели предварительной обработки документов по критерию тематической близости 60
2.2 Создание модели автоматизированного анализа текста документа в иерархических базах знаний 64
2.3 Формализация задачи поиска информации в иерархических БЗ 69
2.4 Разработка фреймовой модели шаблона полнотекстового документа 81
2.5 Разработка модели поискового образа документа 87
Выводы по главе 2 92
Глава 3. Алгоритмическая реализация моделей поиска и обработки информации в иерархических базах знаний 94
3.1 Разработка алгоритма построения поискового образа документа 94
3.2 Разработка алгоритма построения расширенного поискового запроса 100
3.3 Разработка архитектуры полнотекстовой информационно-поисковой системы 103
3.4 Моделирование экспертной системы поиска документированной информации в БЗ 107
Выводы по главе 3 115
Глава 4. Разработка иерархической базы знаний с динамически управляемой структурой и результаты экспериментальных исследований механизмов поиска в ней 116
4.1 Особенности моделирования иерархических баз знаний на основе теории графов 116
4.2 Разработка графовой модели иерархической базы знаний с динамически управляемой структурой 121
4.3 Моделирование процесса обучения на основе иерархической базы знаний с динамически управляемой структурой 128
4.4 Имитационное моделирование и результаты экспериментальных исследований эффективности предложенных механизмов поиска информации в иерархических базах знаний 132
Выводы по главе 4 146
Заключение 147
Список литературы 149
- Основные модели представления и обработки знаний
- Разработка модели предварительной обработки документов по критерию тематической близости
- Разработка алгоритма построения поискового образа документа
- Особенности моделирования иерархических баз знаний на основе теории графов
Введение к работе
Постоянное развитие и совершенствование информационных технологий оказывает существенное влияние на все научные и технологические направления, связанные с использованием вычислительной техники, сложных информационных систем и приборов. Эволюция информационных технологий и систем все в большей степени определяется их интеллектуализацией, которая обеспечивает, во-первых, расширение круга задач, решаемых с помощью компьютеров, особенно в слабоструктурированных предметных областях, и во-вторых, повышает уровень интеллектуальной информационной поддержки современного специалиста. Одним из важных направлением в области современных интеллектуальных информационных технологий является проблема наполнения, структурирования, обработки и поиска информации в различных информационных хранилищах и прежде всего базах знаний.
В настоящее время существует и активно развивается целая отрасль интеллектуальных информационных систем, предназначенных для поиска, обработки и управления знаниями: в частности системы распознавания образов (OCR-системы), экспертные системы, системы автоматического реферирования и аннотирования, системы обработки естественноязыковых текстов (NLP-системы); система интеллектуального анализа данных, нейронные семиотические системы и т.д.
Теоретическим исследованиям и разработке фундаментальных основ интеллектуальных информационных систем, созданию математического аппарата, моделей и методов обработки и управления знаниями посвящены труды видных российских и зарубежных ученых Н. Винера, М. Минского, Л. Заде, Д. Маккарти, Ж.-Л. Лорьера, Р. Шенка, Д. Кнута, Н.Дж. Нильсона, Г. Сэлтона, Д. А. Поспелова, А.П. Ершова и многих других.
Интеллектуальные базы знаний в настоящее время широко используются при проведении научных исследований, проектировании и разработке информационно-управляющих систем и приборов, в процессах дистанционного обучения специалистов и многих других сферах научной и практической деятельности. Одной из основных тенденций в развитии и совершенствовании технологий представления и обработки информации в БЗ является обеспечение возможности для пользователя получения максимально полной, актуальной и достоверной информации о заданной предметной области. Указанные тенденции делают необхо-
димым с одной стороны - представление современных баз знаний в виде иерархических многомодульных, динамически реконфигурируемых структур, ориентированных на информационные потребности различных групп пользователей, а с другой стороны - создание эффективных систем и механизмов поиска и обработки информации, представленной в базах знаний.
Современные информационно-поисковые системы обладают рядом недостатков, в частности: низкая интеллектуальность поиска документов в БЗ и неэффективное индексирование информации, не учитывающее конкретную предметную область; упрощенность процедуры вычисления степени релевантности документа; отсутствие средств полноценного расширения запроса пользователя и удобного уточнения результатов запроса.
Таким образом, актуальными являются диссертационные исследования, направленные на разработку моделей и алгоритмов эффективного поиска и обработки информации в иерархических базах знаний с динамической управляемой структурой.
Целью диссертационного исследования является разработка моделей и алгоритмов эффективного поиска и обработки информации в иерархических базах знаний с динамической управляемой структурой, обеспечивающих повышенную точность и полноту находимой релевантной информации без заметного снижения быстродействия поиска. Указанная цель достигается разработкой моделей и алгоритмов обработки и поиска информации в БЗ; созданием модели иерархической базы знаний с динамически управляемой структурой; имитационным моделированием и программной реализацией предложенных моделей и алгоритмов.
В соответствии с указанной целью в работе решаются следующие задачи.
Исследование современных моделей обработки и поиска информации в базах знаний, анализ функциональных возможностей информационно-поисковых систем.
Разработка моделей предварительной обработки и анализа текста документа в структурированных базах знаний.
Формализация задачи поиска информации в полнотекстовых БЗ
Разработка моделей и алгоритмов полнотекстового запроса и поискового образа документов (ПОД).
Имитационное моделирование, программная реализация и экспериментальное исследование эффективности предложенных
моделей и алгоритмов. 6. Создание модели иерархической базы знаний с динамически
управляемой структурой. Методы исследования. В диссертационной работе использованы методы системного анализа, теории информационных систем, элементы теории принятия решений, элементы теории вероятности, математический аппарат предикатной алгебры, методы математического и имитационного моделирования.
Научная новизна работы состоит в создании новых моделей и алгоритмов, обеспечивающих повышенную точность и полноту находимой релевантной информации без заметного снижения быстродействия поиска в иерархических базах знаний с динамически управляемой структурой. При этом получены следующие научные результаты.
Предложены модели предварительной обработки и автоматизированного анализа информации в БЗ, обеспечивающие сужение рамок предметной области и позволяющие более эффективно структурировать и извлекать информацию из иерархических баз знаний.
Предложена и обоснована формализация задачи поиска информации в структурированных БЗ, основанная на сравнении поискового образа полнотекстового документа и расширенного запроса пользователя.
На основе теории фреймов и семантических сетей созданы и исследованы математические модели полнотекстового запроса и ПОД, обеспечивающие более высокую информативность поискового запроса пользователя по сравнению с традиционными моделями поиска информации.
Алгоритмически реализовано построение расширенного запроса, фактически заключающееся в последовательном просмотре термов запроса с последующим поиском и уточнением тематически близких понятий для каждого из них.
Разработана графовая модель многомодульной иерархической базы знаний с динамически конфигурируемой структурой и предложена схема алгоритма процесса обучения, основанного на иерархическом ранжировании модулей БЗ и вероятностном характере обращения к ним, адаптированного под индивидуальные способности обучаемого.
Создана и верифицирована имитационная модель поиска информации в структурированных иерархических базах знаний на основе разработанных моделей и алгоритмов. В ходе экспериментального исследования показаны преимущества их использования для многомодульных баз знаний.
Практическая значимость работы заключается в новых возможностях создания эффективных методов и средств обработки и поиска информации в иерархических базах знаний с динамически обновляемой информацией, адаптированных к запросу пользователей и обеспечивающих высокую полноту и точность выдаваемой релевантной информации. Гибкость предложенных решений делает возможным их применение в компьютерных системах обучения, в системах поддержки принятия решений, интеллектуальных информационно-аналитических системах, диагностических экспертных системах и многих других.
Представленные в работе модели и алгоритмы расширенного поиска информации повышенной релевантности направлены на решение практических задач поиска информации в массивах электронных хранилищ и баз знаний. Результаты имитационного моделирования подтверждают повышение эффективности поиска информации на основе предложенных моделей и алгоритмов по сравнению с традиционными.
Разработанная система обучения в предметной области рассчитана на 120 человек, работающих одновременно, и обеспечивает гибкость процесса обучения с возможностью ранжирования информации в зависимости от уровня обучаемого. Результаты экспериментальных исследований показали, что смоделированная на основе предложенных в работе моделей и алгоритмов информационно-поисковая система обеспечивает повышение коэффициента полноты поиска в среднем на 2,5 %, коэффициента точности на 7,5% при снижении быстродействия на 1 % .
Достоверность определяется корректным применением строго математического аппарата и подтверждается результатами имитационного моделирования, доказавшими преимущества предложенных в работе моделей и алгоритмов обработки и полнотекстового поиска информации в иерархических БЗ, выразившиеся в повышении точности и полноты находимых релевантных документов.
Личный вклад автора. Все основные результаты получены автором лично. Главными из них являются:
проведение аналитического обзора функциональных возможностей современных информационно-поисковых систем, моделей представления, обработки и поиска знаний;
разработка модели предварительной обработки документов, основанной на вычислении оценок тематического подобия ;
создание модели автоматизированного анализа текста документа в структурированных базах знаний, основанной на коррелированности различных понятий в тексте;
формализация задачи поиска информации в структурированных БЗ, основанная на сравнении поискового образа полнотекстового документа и расширенного запроса пользователя;
разработка фреймовой модели шаблона полнотекстового документа, использование которой позволяет строить поисковые образы документов, не зависящие от форматов документов;
создание модели поискового образа документа, представленной в виде неориентированного нечеткого графа второго рода;
разработка и программная реализация алгоритмов построения расширенного поискового запроса и поиска информации в иерархических БЗ;
имитационное моделирование и экспериментальное исследование эффективности предложенных моделей и алгоритмов;
разработка графовой модели иерархической базы знаний с динамически конфигурируемой структурой и алгоритма процесса обучения, основанного на ней;
внедрение результатов диссертационной работы в учебный процесс кафедры МИЭТ.
Внедрение результатов работы. Все работы по реализации и внедрению проводились при непосредственном участии автора. Результаты диссертационной работы используются в учебном процессе кафедры ИПОВС Московского государственного института электронной техники в лекционных и практических занятиях по дисциплинам "Операционные системы, среды и оболочки", "Компьютерные технологии в науке и образовании".
В результате проведенных исследований получены и выносятся на защиту следующие основные научные результаты:
аналитический обзор функциональных возможностей современных информационно-поисковых систем, моделей представления, обработки и поиска знаний;
модель предварительной обработки и автоматизированного анализа текста документа в структурированных базах знаний;
формализация задачи поиска информации в структурированных БЗ; фреймовая модель шаблона полнотекстового документа;
графовая модель поискового образа документа;
алгоритм построения расширенного поискового запроса и поиска информации в иерархических БЗ;
результаты имитационного моделирования и экспериментального исследования эффективности предложенных моделей и алгоритмов;
графовая модель иерархической базы знаний с динамически конфигурируемой структурой и алгоритм процесса обучения, основанный на ней;
результаты внедрения и апробации материалов диссертационной работы.
Апробация работы. Основные положения и результаты диссертационной работы были доложены на Всероссийских межвузовских научно-технических конференциях "Микроэлектроника и информатика" (Москва, Зеленоград, МИЭТ, 2005- 2008 г.г.), Научной сессии МИФИ (Москва, МИФИ, 2007-2008 г.г.) Всероссийской межвузовской научно-практической конференции "Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем" (Москва, Зеленоград, МИЭТ, 2007 г.).
Публикации. Основное содержание диссертации отражено в 13 опубликованных работах, в том числе 2 статьи в ведущих научных журналах входящих в перечень, утвержденный ВАК. Без соавторов опубликовано 7 работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 148 страниц основного текста, включая 33 рисунка, 5 таблиц, а также список литературы из 109 наименований и 3 приложения. СОДЕРЖАНИЕ РАБОТЫ
Основные модели представления и обработки знаний
В настоящее время существует устойчивая тенденция интеллектуализации компьютеров и их программного обеспечения (ПО), связанная с решением задач все в большей степени невычислительного характера, в том числе логический вывод, управление базами знаний (БЗ), обеспечение интеллектуальных интерфейсов и др. При этом одной из определяющих задач, связанных с реализацией современных интеллектуальных систем, является функция представления и обработки знаний о некоторой предметной области [15].
В данной трактовке знания представляют собой совокупность сведений об объектах этой ПрО, их существенных свойствах и связывающих их отношениях, процессах, протекающих в данной ПрО, а также методах анализа возникающих в ней ситуаций и способах разрешения ассоциируемых с ними проблем.
Создание БЗ и в теории, и в практике ИИ сегодня является проблемой такой же важности, как в свое время в информационных технологиях проблема создания БД [15, 16].
Под базой знаний понимается семантическая модель, предназначенная для представления в ЭВМ знаний, накопленных человеком в определенной ПрО. На технологическом уровне БЗ рассматривается как хранилище (репозиторий) сложно структурированных информационных единиц (знаний).
Говоря о БЗ, мы всегда будем соотносить ее со знаниями о некоторой ПрО (одной или нескольких). При этом под ПрО может пониматься и некоторый класс решаемых задач.
По аналогии с технологией БД будем различать собственно информационное хранилище знаний (БЗ) и систему управления БЗ (СУБЗ), обеспечивающую набор типовых функций хранения и манипулирования знаниями [15]. С парой БЗ—СУБЗ может взаимодействовать прикладная интеллектуальная система, использующая содержимое БЗ и средства СУБЗ для решения каких-либо предметных задач [16-19].
Обобщенная структура БЗ изображена на рисунке 1.1. Математически она представляется шестеркой: БЗ = (Mh М2 М3, Ih I2,13}, (1.1) где Mi - база глубинных знаний, представляющая понятийные структуры ПрО; М2- база фактов; М3- база метазнаний; /у— интерфейсы между Mj и М2,12- интерфейсы между М2 и Мз, Із- интерфейсы между Мз и М].
Одна из ключевых проблем, возникающих при построении интеллектуальных систем, состоит в необходимости выбора и реализации способа представления знаний. Важность данной задачи обусловливается тем, что именно представление знаний в конечном итоге определяет характеристики системы.
В настоящее время в научной практике применяются семь классов моделей представления и обработки знаний (рисунок 1.2): логические, продукционные, фреймовые, сетевые, объектно-ориентированные, специальные и комплексные. Коротко проанализируем каждый из перечисленных классов [15-19].
Простейшей логической моделью является исчисление высказываний. Аксиоматический базис исчисления высказываний (множество А из (1.2)) составляет совокупность правильно построенных формул, являющихся тождественно истинными. К системе аксиом предъявляют требования непротиворечивости, независимости и полноты. Названным требованиям удовлетворяет систе ма из четырех аксиом, предложенная Д. Гильбертом [20]. В качестве правил вывода исчисления высказываний (множество R из (1.2)) обычно используют два: правило отделения (если X и {X — Y) — истинные формулы, то Y также истинна) и правило подстановки, разрешающее в правильно построенных формулах заменять все вхождения одного высказывания на другое.
Развитие логики высказываний нашло отражение в исчислении предикатов.
Пусть имеется некоторое множество объектов, называемое предметной областью. Выражение Р(Х1, Х2, ..., Хп), где Х„ i l,...,n - так называемые предметные переменные, а Р принимает значения 0 или 1, называется логической функцией или предикатом. Предикат Р(Х1, Х2, ..., Хп) задает отношение между элементами Xj,X2, ...,Хп и обозначает высказывание, что XhX2, ...,Х„ находятся между собой в отношении Р.
Положительными чертами логических моделей знаний в целом являются: высокий уровень формализации, обеспечивающий возможность реализации системы формально точных определений и выводов; согласованность знаний как единого целого, облегчающая решение проблем верификации БЗ, оценки независимости и полноты системы аксиом и т. д.; единые средства описания как знаний о ПрО, так и способов решения задач в этой ПрО, что позволяет любую задачу свести к поиску логического вывода некоторой формулы в той или иной ФС [15].
Отметим следующие недостатки логических моделей: представление знаний в таких моделях ненаглядно- логические формулы трудно читаются и воспринимаются; ограничения исчисления предикатов первого порядка не допускают квантификации предикатов и использовании их в качестве переменных; обоснованность обозначения свойств и отношений однотипными препозиционными функциями вызывает сомнения; описание знаний в виде логических формул не позволяет проявиться преимуществам, которые имеются при автоматизированной обработке структур данных.
Пути повышения эффективности логических моделей знаний связаны с использованием многоуровневых и специальных логик [6].
Следует заметить, что (1.2) определяет закрытую ФС, соответствующую аксиоматической системе, все аксиомы которой тождественно истинны вне зависимости от рассматриваемой ПрО. В базирующихся на таких ФС логических моделях используются процедуры монотонного вывода в закрытых БЗ. Свойство монотонности означает, что истинность полученных в процессе вывода утверждений (формул) сохраняется при расширении множества посылок. Иными словами, поступающие в систему новые факты не могут изменить истинностные значения выведенных ранее утверждений.
Разработка модели предварительной обработки документов по критерию тематической близости
Удобство работы и извлечения информации из БЗ во многом определяется эффективностью структурирования в соответствии с тематическим содержанием документов.
Предлагаемая модель основана на вычислении оценок тематического подобия двух документов [68]. Вообще, понятие тематической близости документов относительно и определяется контекстом, в рамках которого близость оценивается. Поэтому, в описываем методе оценка тематической близости определяется не только самими документами, но и зависит от всей коллекции документов.
Известно, что словарный запас и частоты использования слов зависят от тематики. Поэтому при вычислении оценок тематической близости будут учитываться только те слова, которые более специфичны для тематики рассматриваемого документа. Такие слова выделяются по результатам анализа аппроксимированного тематического окружения данного документа. Представим каждый документ как последовательность частей (параграфов), каждая из которых отражает некоторый тематический аспект документа.
Предлагаемый метод состоит из следующих основных этапов: Для каждого документа определяется некоторое (относительно небольшое) множество документов, представляющее его (аппроксимированное) тематическое окружение. о Построенные тематические окружения анализируются с целью формирования множеств ключевых слов, характеризующих тематику исходного документа относительно остальных документов БЗ. Полученные наборы ключевых слов используются для дальнейшего вычисления относительных оценок тематического подобия. Предварительная обработка включает следующие операции: Лексический анализ, включающий стандартные операции: удаление пунктуации, цифр, преобразование всех букв в прописные, и т. п. Исключение стоп-слов Стоп-слова - это широко употребительные слова, не несущие смысловой нагрузки (например, местоимения). Выделение основ слов Разбиение документа на "параграфы"
Целью этого разбиения является представление документа d в виде последовательности Q (d) тематически однородных фрагментов документа Qf.
Отметим, что таким образом учитывается некоторая информация об относительной близости термов в тексте документа, т. е. используем некоторую разновидность методов анализа локального контекста .
Применим эвристический подход, основанный на желаемом размере получаемого фрагмента Е.
Данный подход обусловлен тем, что использование сильно отличающихся в размере параграфов имеет ряд недостатков: словарь коротких параграфов значительно беднее словаря длинных параграфов, благодаря чему термы в профайлах коротких параграфов в среднем имеют больший вес. Все это приводит к излишним помехам при вычислении оценки близости.
Для построения профайлов параграфов применяется векторная модель, в рамках которой профайлы представляют собой векторы. В данном случае для каждого параграфа Qj формируется так называемый -профайл, сопоставляющий каждому терму t частоту его встречаемости в данном параграфе tFq(t).
Тематическое окружение документа используется для выявления тех особенностей, которые характеризуют тематическую ориентацию рассматриваемого документа dt относительно рассматриваемого набора документов D. Поэтому важно, чтобы доля документов, тематически близких данному документу была в построенном тематическом окружении выше, чем в рамках всей коллекции D [68].
В тематическое окружение Р (dt) документа dt включаются все документы dp, которые признаются тематически подобными заданному документу следующим алгоритмом:
Последовательность значений - sim(s, s + l) используется для разбиения виртуального документа на тематически однородные группы параграфов границы групп соответствуют тем значениям s, при которых значение функции sim значительно меньше значений этой функции в соседних точках, т. е. sim(s -1) a&im{s) sim(s +1). (2.4)
Окончательно, документ dp считается тематически близким документу dh если для обоих виртуальных документов ни одна из границ между тематически однородными группами параграфов не совпала с границей между документами dpndt.
Множество ключевых слов К (dp) для документа dp - это подмножество термов, встречающихся в dp, которое характеризует тематику этого документа. Формирование множества происходит на основе сравнительного анализа статистики использования термов в рамках коллекции в целом и в рамках тематического окружения заданного документа.
Исходя из предположения о том, что доля релевантных документов для dp выше в его тематическом окружении 4х (dp) , чем в БЗ в целом, мы полагаем, что характерные для тематики документа dp термы также встречаются в построенном тематическом окружении чаще, чем в среднем.
Для формирования множества ключевых слов документа dp используется следующий подход. Для каждого терма / документа dp вычисляется вероятность появления этого терма в случайно выбранном документе из тематического окружения Р (dp) .
Разработка алгоритма построения поискового образа документа
Во второй главе диссертационной работы были разработаны модель поискового образа документа, представленная в виде неориентированного нечеткого графа второго рода и коррелированная с ней модель расширенного поискового запроса в терминах семантических сетей. Далее рассмотрим алгоритмическую реализацию предложенных моделей.
Алгоритм построения ПОД разбивается на 2 независимые части: алгоритм выделения термов документа с вычислением их весов и алгоритм нахождения весов связей между термами. Первый алгоритм выделяет в документе список семантически значимых термов и приписывает им веса. Несмотря на то, что в данной работе используется теоретико-множественный подход к описанию математической модели поиска, воспользуемся некоторыми приемами алгебраического подхода, позволяющего получить информацию о значимости каждого терма в описании документа. Наиболее распространенным методом определения веса термов является частотный метод [91,92].
Вес термина частотным методом оценивается исходя из того, в каких документах и сколько раз этот термин встречается. Для его вычисления вводятся такие характеристики как частота термина и частота документа.
Частота термина - это отношение количества раз, которое термин встретился в документе к общему количеству терминов в документе. Эта характеристика позволяет определить, какие термины содержаться в документе, и отражает насколько часто термин встречается в документе. Для ее оценки используют выражение: N terms- " количество появлений j -го терма в і-м документе ; N terms- " общее количество термов в і-м документе ; Np- общее количество документов в БЗ; Nterms— общее количество термов в БЗ.
Частота документа - это отношение количества документов набора, в которых термин встретился, к общему количеству документов в наборе. Эта характеристика позволяет определить, насколько термин помогает отличить один документ набора от другого, и отражает насколько часто терм встречается в документах набора. Так как вес терма увеличивается с уменьшением частоты документа, т.е. вес термина больше, если термин встречается в меньшем количестве документов БЗ, то при вычислении веса используют величину обратную частоте документа .
Таким образом, объединив частоту терма и величину обратную частоте документа, можно вычислить вес терма:
Недостатком данного метода является то, что он не учитывает распределение терма внутри всех документов БЗ. Другие известные методы, например дискриминирующей переменной, требуют большого количества вычислений, связанного с расчетом плотности всего пространства документов, особенно при большом количестве термов [91,92].
Для того чтобы учесть распределение терма во всех документах БЗ без усложнения алгоритма, предлагается добавить дополнительную характеристику.
Она должна быть максимальной, если терм встречается только в одном рассматриваемом документе БЗ и не встречается в оставшихся документах, и убывать с увеличением частоты терма в оставшихся документах набора.
Для этого удобно использовать величину, обратную средней частоте терма в оставшихся документах набора, ее легко определить, зная частоты термов в документах:
В этом случае, сложность возникает, когда термин не встречается ни в одном из документов БЗ кроме рассматриваемого, тогда средняя частота терма равна нулю и обратная ей величина не определена, эксперименты показали, что для оценки этой величины можно воспользоваться следующим выражением:
При таком подходе, формула расчета усложняется незначительно, и предложенная характеристика соответствует предъявленным к ней требованиям, принимает максимальное значение равное единице, когда терм содержится только в рассматриваемом документе и убывает с увеличением частоты терма в оставшихся документах.
Особенности моделирования иерархических баз знаний на основе теории графов
В автоматизированном обучении модель предметной области приобретает особую роль, т.к. качество обучения практически определяется алгоритмом управления процессом обучения, который базируется на МПО. Модель предметной области можно использовать как для управления процессом обучения, так и для обоснованного решения вопроса о включении тех или иных фрагментов знаний в базу знаний [97-98].
Предметная область (ПО) характеризуется сущностями и связями между ними. В качестве сущностей ПО в обучающих системах можно рассматривать понятия или темы, каждой из которых соответствует единица учебного материа ла, не требующая деления на подтемы. Каждая тема описывается набором параметров (атрибутов), существенных для управления обучением.
Связь между темами / и у подразумевает зависимость между ними, которую можно интерпретировать так: для понимания темы j нужно знать тему і. Таким образом, связи могут определять последовательность изучения тем. Связи могут иметь также различную семантику и взаимозависимости.
В большинстве существующих обучающих программ учебный материал имеет линейную структуру, соответствующую последовательности изложения материала [99]. Такой подход не может считаться оптимальным.
Рассмотрим возможный вариант организации модели предметной области произвольной структуры. Для этого сначала определим требования, которым она должна удовлетворять.
На основании вышеизложенного понимания структуры предметной области ее модель должна удовлетворять следующим требованиям: возможность отражать различные типы связей между элементами; возможность получения целостного образа знаний; возможность объединения процедурных и декларативных знаний.
Этим требованиям удовлетворяют фреймовая и семантическая модели представления знаний . Семантические сети и фреймовые модели близки друг другу, но механизм вывода в семантических сетях более прозрачен. Отчасти поэтому семантические сети можно назвать традиционным способом организации модели предметной области [55,57,100-103].
Преставление этой модели в виде семантической сети позволяет проводить анализ предметной области по таким параметрам, как: связность (достижимость любой вершины); наличие циклов; степень важности определенной темы (понятия), определяемая количеством тем, зависящих от данной темы. Семантическая сеть в работах, затрагивающих вопрос организации модели предметной области, рассматривается в классическом понимании, т.е. как направленный граф с помеченными вершинами и дугами, в котором вершинам соответствуют объекты, а дугам - семантические отношения между ними [6].
Поэтому для разработки архитектуры обучающей базы знаний кратко остановимся на основных положениях теории графов.
Пусть V непустое множество, например, V— {Vj, V2 3 4, 5} Запишем множество всех его двухэлементных подмножеств V" . Для нашего примера это множество
Пару y,Ej называют неориентированным графом G, в котором V это множество вершин, а Е - множество ребер, являющееся подмножеством множества V . В более компактной форме это определение обычно формулируется так: пара (V, Е) называется неориентированным графом, если V - непустое множество элементов, называемых вершинами, а Е - множество неупорядоченных пар различных элементов из V, называемых ребрами
Определим матрицу смежности как симметричную квадратную матрицу A— [aij] порядка п, в которой элемент йц = 1, если в графе есть ребро (Vj, Vj} , aij - О, если такого ребра нет. , т.е. количество единиц в любой строке или столбце матрицы смежности равно степени соответствующей вершины графа d(Vj) , а общее количество единиц равно удвоенному числу его ребер.
Любому простому графу G можно поставить в соответствие ориентированный, придав каждому ребру одну из двух возможных ориентации. В качестве примера на рисунке 4.1 представлен ориентированный граф (4.1).
