Процесс накопления информации

⇐ Назад
• 1
• 2
• 3
• 4
• 567
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• Далее ⇒

В автоматизированных системах обработки информации и управления данные являются основой для формирования концептуаль­ной модели реального производственного процесса. Обработка ин­формации при наличии алгоритмов управления требует входных данных, в процессе обработки формируются промежуточные и вы­ходные данные. При структуризации данных могут возникать новые знания, формироваться информационный ресурс с целью оптималь­ного управления производством. При известном наборе функци­ональных задач автоматизированной системы, составляющих ее функциональную структуру, и совокупности алгоритмов решения вычислительных задач, входящих в алгоритмическую структуру АСУ, возникает проблема создания информационного обеспечения. Информационная технология в управлении производством, науч­ных исследованиях, проектировании, обучении требует целенаправленного накопления данных. В основе этого процесса должны лежать формализованные модели, позволяющие синтезировать ин­формационную базу АСУ.

Инфологическая модель предметной области. Исходная инфор­мация для синтеза информационной базы формально представляется в виде инфологической модели предметной области. Эта модель совместно с наборами хранимых данных и алгоритмами обработки информации позволяет построить каноническую схему информаци­онной базы, от которой можно перейти к логической схеме, а от нее - к физическому уровню реализации информационного обес­печения. Таким образом, процесс обработки сопровождается накоп­лением данных. Построение инфологической модели предусматри­вает определение:

1) множества данных и функциональных отноше­ний между ними;

2) значений данных и функциональных отношений, задающих способы обращения к ним при реализации алгоритмов;

3) выбор оптимальных вычислительных схем алгоритмов.

Будем считать, что вычислительный алгоритм известен и запи­сан на алгоритмическом языке высокого уровня. Обозначим множе­ство данных, используемых в алгоритме, через D, тогда элемент множества dÎD. Если выделить множества D₁, ..., D_n, то между ними могут существовать определенные отношения. Выберем кор­тежи

(d₁, ..., d_n, b₁)ÎF; (d₁, ... , d_n, b₂)ÎF.

Подмножество F называют функциональным отношением, если b₁=b₂, при этом между элементами множеств (d₁, ..., d_n)ÎD₁´D₂, ..., D_n и bÎB возникает однозначное соответствие. Функциональное отношение определяется совокупностью кортежей (d₁, ..., d_n) и имеет область значений bÎB. Инфологическую модель предмет­ной области задают следующие параметры: {D_k} - множество имен элементов данных d_k с длиной l_k; z_k - количество изменений значения данных за определенный интервал времени; a_j - множест­во алгоритмов; f_j - частота реализации j-го алгоритма; N=N₁ÈN₂ÈN₃ - множество наборов данных, где N₁, N₂, N₃ - со­вокупности входных, промежуточных и выходных данных соответ­ственно; F - совокупность функциональных отношений.

Если алгоритм управления, записанный на алгоритмическом языке высокого уровня представлен в виде граф-схемы, это означа­ет, что заданы процедуры, которые реализуются с помощью либо стандартного, либо разрабатываемого программного обеспечения. Процедура включает в себя совокупность алгоритмов и определяет данные, необходимые для ее реализации. Выполнение процедуры означает вычисление с помощью некоторого оператора значения функционального отношения Ф, что осуществляется за счет задания его аргумента. При укрупнении граф-схемы алгоритма в вершинах располагаются не процедуры, а вычислительные модули. Форм­ирование вычислительных модулей в соответствии с последователь­ностью их функционирования позволяет получить вычислительную схему алгоритма. Как было рассмотрено выше, объединение вычислительных схем приводит к вычислительному графу системы об­работки. Однако вычислительный граф не вскрывает потоков дан­ных и порядок их использования. Поэтому полезно перейти к ин­формационному графу, вершинами которого будут наборы данных, используемых в вычислительном модуле.

Информационный граф системы обработки. Набор данных есть совокупность данных, передаваемых между двумя вычислительны­ми модулями. На логическом уровне выделяют связи по управле­нию и связи по данным. Такие связи существуют как внутри вычис­лительного модуля, так и между модулями различных уровней вычислительного графа системы обработки. Для любого модуля выделяют входные и выходные данные.

Входные данные отобразим матрицей Н, элемент которой h_ik=1, если входной набор данных N_1i используется вычислительным модулем k. Этот же элемент h_ik=0, если это не имеет места.

Выходные данные формально отобразим матрицей Е, элемент которой е_kj=1, если набор данных N_3i получен в результате работы вычислительного модуля k. Элемент матрицы е_kj=0 - в против­ном случае.

Матрица взаимосвязи входных и выходных данных Q=HÄE. Элемент матрицы q_ij=1, если входной набор данных N_1i используется для получения выходного набора данных N_3j. Элемент матрицы q_ij=0, если это не имеет места. Рассмотрим связь вычислительного модуля ВМ_k с входным набором данных N_1i и вы­ходным набором данных N_3j. Структура модуля по преобразованию данных задается матрицей Q, связь модуля с набором данных N_1i определяется матрицей Н, связь модуля с набором данных N_3j - матрицей Е. Матрица Q соответствует ориентированному графу взаимосвязей между данными - информационному графу системы. Вершинами графа являются входные, промежуточные и выходные наборы данных. Дуги графа отображают информационные связи между этими наборами.

В информационном графе системы можно выделить входные вершины, которые не имеют входных дуг и отображают первичные (входные) наборы данных. В концевых вершинах графа, которые не имеют исходящих дуг, располагаются выходные наборы данных, являющиеся результатами обработки информации и используемые для принятия решения в системе. В остальных вершинах графа располагаются промежуточные наборы данных, которые являются внутренними по отношению к пользователю и возникают в процес­се вычислений как промежуточный результат. Отметим, что в от­личие от вычислительного графа системы информационный граф может иметь контуры и петли, что объясняется необходимостью повторного обращения к отдельным наборам данных. Входные данные являются первичными, поскольку они возникают при изуче­нии производства и характеризуют исходное состояние управля­емой системы. Промежуточные и выходные данные относятся ко вторичным данным. Вторичные данные возникают в результате процесса обработки, т.е. выполнения отдельных процедур над первичными данными.

Вычислительный граф системы обработки и информационный граф системы позволяют формализовать инфологическую модель предметной области. В процессе обработки и накоп­ления данных формируются новые наборы данных, при этом можно различать два крайних случая.

1. Формирование набора данных на основе вычислительного алгоритма, т.е. для имеющихся входных наборов данных на основе вычислений получают выходные данные. Последовательность ис­пользования вычислительных модулей для формирования выход­ного набора данных определяется вычислительной граф-схемой ал­горитма в виде ориентированного графа без петель. В вершинах графа располагаются вычислительные модули, а дуги графа отоб­ражают отношение предшествования между ними.

2. Вычисление значений набора данных по имеющимся старым значениям и по совокупности изменений, возникающих в первичном наборе данных. Эти процедуры осуществляются на основе алгорит­мов корректировки набора данных. Корректировка возможна в том случае, если корректируемый набор данных уже ранее был запро­шен и хранится в информационной базе.

Таким образом, в модели накопления данных может быть выяв­лено два основных типа алгоритма нахождения новых наборов: вычислительный алгоритм и алгоритм корректировки набора дан­ных. Реализация вычислительного алгоритма при запросе обычно необходима тогда, когда запрашиваемый набор данных не хранится в информационной базе. При наличии этого набора более удобно использовать алгоритм корректировки. Вычислительный алгоритм реализуется на базе информационного графа системы, алгоритм корректировки базируется на списке изменений, вносимых в первич­ный набор данных.

Независимо от используемого алгоритма вычислительный мо­дуль выполняет определенные процедуры, включающие в себя действия над данными. На логическом уровне возникает задача специ­фикации действий, т.е. определение входных и выходных наборов данных для действий, а также взаимосвязей между различными действиями. При этом можно выделить два типа функциональных (логических) элементов: элементы - действия Q и элементы - объекты действий D. Элементы действия Q характеризуются внешними связями и ресурсами. Такой элемент реализует определенное преобразование над данными с использованием в качестве ресурсов элементов типа Q и элементов типа D. В качестве объектов действий выступают данные, которые характеризуются именем, типом и значением. Тип определяет множество значений, которые принимают объекты данного типа. Объект действий задается струк­турой, т.е. составом компонентов и связей между ними. Элемент Q взаимодействует с элементами D₁, D₂, D₃, через связи типа: 1 - "вход", 2 - "выход", 3 - "вход - выход".

Совокупность элементов действий Q и элементов объектов дей­ствий, т.е. данных D, образует информационную схему. Естествен­но, что одни и те же данные могут быть использованы различными элементами действий. Рассмотрим информационную систему, включающую элементы действий Q₁...Q₃ и элементы данных D₁...D₄. В схеме присутствуют связи типа 1 - "вход" и типа 2 - "выход". Связи первого типа формально записываются в виде D in Q, а второго типа - D out Q. Информационная схема отображается матрицей

B=(D in Q)È (D out Q)=
				.

Матрица В построена непосредственно по информационной схе­ме. Данные D₁ используются действиями Q₁ и Q₂, что соответствует первой строке матрицы. Данные D₂ формируются действием Q₃, что отображается второй строкой матрицы. Данные D₃ вычисляются действием Q₁ и используются действием Q₂, что соответствует третьей строке. Данные D₄ вырабатываются действием Q₂ и исполь­зуются действием Q₃, (четвертая строка). Исключим из информаци­онной схемы элементы действия Q и найдем связи по данным, что на логическом уровне соответствует информационному графу си­стемы. Учтем при этом частоту активизации действий. При одиноч­ном запросе суммарное количество действий, использующих дан­ные d_i, обозначим через z_ii, а суммарное количество действий, использующих данные d_j совместно с данными d_i, определим как z_ij. Члены z_ii, z_ij являются элементами матрицы Z = B ´ B^т. Вводя в матрицу Z частоту активизаций действий f, получим матрицу ZF=(B×f)´B'. Элемент матрицы z×f_ii показывает частоту использования дан­ного d_i с учетом частоты активизации действий. Соответственно элемент z×f_ij отображает частоту совместного использования данных d_i, d_j. По значениям этих частот данные могут объединяться в записи, а записи - в массивы. При этом обеспечивается минимизация числа обращенийк записям в процессе обработки и корректировки информации.

Каноническая структура информационной базы. При известной инфологической модели предметной области, наличии вычисли­тельного и информационного графов возникает проблема создания модели накопления данных, в основе которой лежит задача выбора хранимых данных. Пусть совокупность используемых наборов дан­ных N разделена на N₁ первичных (входных), N₂ промежуточных и N₃ выходных наборов данных, т.е. N=N₁ÈN₂ÈN₃. Получение наборов данных N₃ осуществляется на основе вычислительных ал­горитмов и алгоритмов корректировки. Вычислительный алгоритм представляется вычислительной схемой, т.е. подграфом вычисли­тельного графа. Алгоритм корректировки базируется на множестве первичных данных N₁. Даже при наличии лишь двух классов ал­горитмов возникает задача выбора типа алгоритма в соответствии с запросом пользователя. Если по запросу необходимо получить некоторый набор данных, то в качестве критерия выбора типа алгоритмов можно использовать полное время создания этого на­бора по данному запросу. При использовании вычислительного алгоритма это время складывается из времени, которое затрачива­ется на получение входных наборов данных для выбранного вычис­лительного модуля, и времени вычислений набора данных этим модулем. Для сравнения необходимо найти время, которое затрачи­вается в случае применения алгоритма корректировки. Корректи­ровка набора целесообразна, если структура данных уже ранее была задана в одном из предыдущих запросов. В качестве дополнитель­ного ограничения при решении задачи выступает объем использу­емой памяти. Рациональное сочетание вычислительных алгоритмов и алгоритмов корректировки данных позволяет уменьшить суммар­ное время реализации всех запросов при накоплении данных.

Инфологическая модель предметной области позволяет подойти к решению двух задач: задачи синтеза информационной базы и за­дачи управления вычислительным процессом. При синтезе инфор­мационной базы необходимо установить ее структуру. Представле­ние информации пользователя дает каноническая структура ин­формационной базы, поэтому построение модели накопления дан­ных должно базироваться на синтезе канонической структуры. Это проводится при следующих требованиях: единство инфологической модели для множества предметных областей, обслуживаемых ин­формационной базой; выбор безызбыточного набора информацион­ных элементов и связей между ними; реализация интерфейса пользователя с информационной базой в терминах инфологической модели предметной области; возможность простого перевода поня­тий канонической структуры в понятия логического и физического уровней представления информационной базы. Решение задачи синтеза канонической структуры информационной базы предполагает выбор и упорядочение ключевых реквизитов для множества бинарных отношений, хранимых в информационной базе; формирование логических записей на основе объединения значений реквизитов; определение множества логических записей и связей между ними на основе критерия минимума суммарного времени работы с наборами данных как в режиме вычислительных алгоритмов, так и в режиме алгоритмов корректировки.

Упорядочение ключевых реквизитов отношений должно базиро­ваться на возможности физической реализации информационной базы. Учитывая, что современные СУБД не могут реализовать бинарные отношения между данными, представим любое отношение в виде совокупности бинарных отношений. Это означает упорядочение реквизитов, входящих в ключ каждого функционального отношения F, что можно осуществить на основе построения графа, отображающего (d_i d_j)², где i ¹ j; i, j = 1 - N; 1 £ r £ N - 1. Построим матрицу Q, отображающая взаимосвязь между отдельными данными и группами данных. В общем случае под d_i, d_j можно понимать некоторые обобщен­ные информационные элементы, представляющие собой элементы данных либо группы, составленные из этих элементов: q_ij=1, если существует взаимосвязь (в том числе возможна и семантическая) между элементами d_i, d_j; q_ij=0 при отсутствии взаимосвязи. Если строка матрицы Q содержит все нулевые элементы, то этой строкой отображаются входные данные. В информационном графе эти данные соответствуют корневым вершинам. Если столбец матрицы Q содержит все нулевые элементы, то он отображает терминальные, т.е. выходные, данные. На информационном графе эти данные соответствуют концевым вершинам. Остальные информационные элементы, отображаемые строками и столбцами матрицы Q, отне­сем к групповым элементам. На информационном графе они располагаются в промежуточных вершинах. Объединение множеств значе­ний реквизитов можно выполнить на основе оценки взаимосвязи групповых элементов с подчиненными им выходным. Тогда для группы конечных вершин - терминальных элементов выделяется множество групповых висячих вершин d^rÎD. Для множества d^r может быть построена матрица достижимости вида Q^r, представляющая собой квадратную матрицу с числом строк и столбцов, соответствующим количеству элементов в выделенном множестве d^r. При переходе к логическому уровню представления информацион­ной базы информационные элементы и взаимосвязи между ними упорядочиваются по уровням иерархии. Для этого определим мно­жество предшествования и множество достижимости. Для информационного элемента d_j матрицы Q множество предшествования P(d_j) определяется из совокупности информационных элементов d_i, соот­ветствующих единичной записи в j-м столбце. Анализируя множест­во P(d_j), устанавливают базовые типы структурных элементов, на основе которых формируются информационные группы. Элементам, для которых P(d_j)=Æ, соответствуют промежуточные вершины графа. Из матрицы Q для элемента d_j выявляют и множество достижимости этих данных D(d_j). Это множество формируется за счет элементов d_i, которым соответствуют единичные записи в j-йстроке матрицы Q. Тогда элементы данных d_j принадлежат группе r, т. с. определяются как d_j^r, если D(d_j^r)ÇP(d_j^r)=D(d_j^r). На основе этого условия группы итеративно разбиваются по уровням иерархии, начиная с верхнего. Группы самого верхнего уровня называютcя корневыми, поскольку они располагаются в корне­вые вершинах графа. Группы следующих рангов располагаются в промежуточных вершинах, доступ к ним возможен через корневые группы. Поэтому с помощью корневых групп определяются точки входа к данным информационной базы. Состав информационных элементов, входящих в группу d_j^r, можно определить, включив в нее элементы d_i, которым соответствуют единичные записи в j-м столбце матрицы Q. Упорядочивая таким способом элементы матрицы Q, получают структурированный граф, в котором возможные точки входа соответствуют групповым элементам первого уровня, конеч­ные вершины - выходным данным. В промежуточных вершинах располагаются групповые элементы различных уровней иерархии.

Выбор ключевых реквизитов. Выделение групповых элементов из состава информационных элементов в группах позволяет с помощью ориентированного графа построить траекторию доступа к ка­ждому информационному элементу группы. Доступ осуществляется через корневую вершину графа. Для построения ключевых реквизитов необходимо проанализировать отношения между групповыми информационными элементами. Поиск информационных элементов в базе осуществляется по требованиям пользователя. Если k - e требование пользователя содержит D_k элементов, выбираемых из общего числа структурных элементов инфологической модели предметной области, то можно построить матрицу смежности s_k для информационного требования D_k. Элемент этой матрицы s_ij=1,если существует связь между элементами d_i, d_j в требовании D_k. На основании элементов s_ij^k могут быть названы элементы s_ij^r,соответствующие групповым информационным элементам базы. В зависи­мости от характера групп выделяют s_ij^r=11, s_ij^r=M1. Этим элементам будут соответствовать простые группы. Если s_ij^r=MM, s_ij^r=1M, то получим группы - массивы. Для простых групп образуют про­стой ключ, для групп массивов - составной ключ, включающий в себя основной и вспомогательный ключи. При этом основной ключ определяется терминальным, конечным элементом, входящим в состав группы массива. Выделение основных ключей должно быть неизбыточным, поэтому необходимо установить и устранить дуб­лируемые терминальные конечные элементы данных.

Пусть групповому элементу d_i^r соответствует множество тер­минальных элементов D(d_i^r), а групповому элементу d_j^r - множест­во терминальных элементов D(d_j^r). Известно, что групповые элементы семантически связаны, если D(d_i^r)ÇD(d_j^r)¹Æ. Соответственно семантическая независимость групповых элементов удовлетворяет условию D(d_i^r)ÇD(d_j^r)=Æ. Если последнее условие выполняется для всех попарно выбираемых групповых элементов данного уровня иерархии, а затем и для всех более высоких уровней, то дублирова­ние отсутствует. Если условие не выполняется, то имеют место дублируемые терминальные, конечные элементы. Устранение дуб­лируемых терминальных элементов достаточно легко осуществля­ется, если групповые элементы построены на одном и том же типе отношений.

Пусть групповой элемент d_j^r принадлежит уровню иерархии n, а элемент d_i^r - уровню иерархии m, причем m<п. При наличии пути на графе из элемента d_i^r к элементу d_j^r следует убрать дублиру­емые терминальные элементы из множества d_i^r. Удаление терминального элемента должно быть отражено и в матрице Q. Это означает, что коэффициент q_ij=1, показывающий ранее связь между элементами d_i, d_j, становится равным нулю. Если групповые элементы d_i^r, d_j^r построены на разных типах отношений, то устранение терминальных элементов осуществляется эвристически с исполь­зованием той же идеи: расположением терминального элемента на более высоком уровне иерархии и устранением дублируемого эле­мента на нижнем уровне. Размещение терминальных элементов на более высоких уровнях иерархии в графе обеспечивает уменьшение времени доступа к конечному элементу, так как сокращается путь от корневой вершины до терминального элемента в графе.

При построении канонической структуры информационной базы необходимо устранить также избыточные связи между групповыми элементами. При наличии таких связей по одному и тому же ключу могут вызываться разные групповые элементы данных, что являет­ся недопустимым. Избыточная связь между группами d_i^r, d_j^r может на графе представляться непосредственно дугой (i, j), соединяющей групповые элементы данных, либо путем, включающим в себя ряд дуг. Если избыточной оказывается дуга (i, j), то она легко об­наруживается по матрице Q для элемента q_ij=1. Заменяем этот элемент на нулевой, что соответствует устранению избыточной дуги. Если путь, связывающий групповые элементы данных, вклю­чает несколько дуг, то необходимо найти матрицу Q^k, где k = 2, ... , N_k; N_k - максимальное число групповых элементов данных. Тогда получим квадратную матрицу, элемент которой q_ij^k показывает чис­ло путей, ведущих из группы d_i^r в группу d_j^r. Если в исходной матрице Q элемент q_ij = 1, а в полученной матрице Q^k элемент q_ij^k = 1, то связь является избыточной. Для удаления этой связи заменяем q_ij = 1 на нулевой элемент. Граф, получаемый после удаления избы­точных терминальных элементов и избыточных связей между груп­повыми элементами данных, определяет каноническую структуру информационной базы. Выделение групповых элементов данных в канонической структуре позволяет объединить множество значений конечных элементов (реквизитов) в логические записи и тем самым упорядочить их в памяти ЭВМ. Структура логических записей и связей между ними должна быть такова, чтобы обеспечить минимум суммарного времени работы с наборами данных как при решении функциональных задач, так и при их корректировке. Поэтому необходимо установить характеристики канонической структуры информационной базы.

Существенными являются длины групповых элементов данных, представляющие собой сумму длин терминальных элементов, вхо­дящих в данную группу. Для группы d_i^r длина группового элемента l_i = S l_i⁰, где l_i⁰ - длина терминального элемента данных. Интеграль­ная оценка длин логических записей может быть произведена на основе вектора l={l₁, ..., l_i, ..., l_Nk}. Любая информационная база характеризуется таким параметром, как время доступа пользова­теля к данным. Однако на этапе создания канонической структуры физическая организация базы данных неизвестна, поэтому реальное время поиска данных не удается определить. Тем не менее нужно оценить минимальное значение времени обращения к базе данных как в процессе решения функциональной задачи, так и в процессе корректировки базы. Для групповых элементов данных в каноничес­кой структуре может быть задана матрица Т= ||t_i||, где t_i - мини­мальное время доступа к терминальным элементам d_i, входящим в группу d'_i. Если функциональная задача решается на основе вычис­лительного алгоритма a_j, то время работы алгоритма с реквизита­ми d_i определяется как t_j^b=S_diÎd'i t_i^j, где t_i^j - время поиска реквизита d_i при решении задачи на основе алгоритма a_j. Значение этого времени зависит от вида обработки реквизита d_i в выбранном алгоритме (возможна последовательная обработка значений дан­ных либо обработка по ключу). При использовании алгоритмов коррекции корректируются все отношения, которые содержат изме­няемый ключевой реквизит и зависимые от него реквизиты. Значе­ние времени работы алгоритма с данными t_j^k определяется количе­ством копий, присутствующих в корректируемых реквизитах. На уровне канонической структуры число копий задается количеством экземпляров терминальных элементов, входящих в группу d_rⁱ. Обыч­но алгоритм коррекции имеет возможность обращаться по ключу к информационным элементам базы данных t_kj=S_dit_i^jb_i^k, где b_i^k = 1, если d_iÎd_i^r; b_i^k = 0. если это не имеет места. Методика построения канонической структуры информационной базы практически не меняется в зависимости от того, строится централизованная либо распределенная информационная база. При создании распре­деленной информационной базы матрица Q раскрывается для каждого пользователя. На графе для каждого пользователя формируются групповые и терминальные элементы данных. Полное множество групповых элементов находится путем пересечения групповых элементов данных отдельных пользователей. Таким образом, каноническую структуру информационной базы можно считать универсальной формой представления инфологической модели предметной области и безизбыточной формой модели накопления данных.

От канонической структуры переходят к логической структуре информационной базы и к физической организации информацион­ных массивов. Каноническая структура является также основой автоматизации основных процессов предпроектного анализа предметных областей пользователей.

Представление знаний

В условиях информационной технологии процесс накопления данных в информационной базе должен быть нацелен на формирование знаний. Особое значение этот процесс приобретает при решении неформализуемых задач, т.е. задач, которые не имеют формальных методов решения, описанных в соответствующей лите­ратуре. Тогда способность хранить, накапливать и формировать знания берет на себя ЭВМ, а способность применить знания в соот­ветствии с поставленной целью для решения требуемых задач воз­лагает на себя пользователь. Несмотря на значительное влияние на решение неформализуемых задач эвристической составляющей, необходимо развитие технологии их решения в условиях использования средств вычислительной техники и прежде всего персональных ЭВМ. Эта технология по существу представляет собой технологию автоформализации профессиональных знаний, на основе ее реализа­ции лежит модель представления знаний. Такая модель может быть выбрана на базе моделей имитации интеллектуальной деятельности человека, разработанных в теории искусствен­ного интеллекта. К настоящему времени в искусственном интеллек­те разработано большое число моделей представления знаний. В ос­нове этих моделей лежит утверждение, что на "некотором глубоком уровне все типы представления знаний эквивалентны между собой" [5].

В идеологическом плане представить знания в ЭВМ - это зна­чит определить некоторые исходные нерасчленяемые объекты, пра­вила формирования на их основе новых объектов и в итоге получить описание знаний. Формальный способ описания и есть модель представления знаний. В качестве исходных нерасчленяемых объектов выступают значения данных. Отношения между данными определяют правила образования новых объектов. Выполняя от­дельные процедуры над отношениями между данными, структури­руют данные и формируют знания. Структуризация данных в форм­альной модели должна быть представлена в виде конкретного конструктивного процесса, различные интерпретации элементов этого процесса приводят к разным моделям представления. Исполь­зование знаний, хранимых в ЭВМ для решения конкретных задач, требует соответствия модели представления знаний и модели пред­ставления задач. В теории искусственного интеллекта получили применение различные представления знаний. Среди них прежде всего следует выделить продукционные модели, которые могут быть одновременно отнесены к декларативному и процедурному способам представления знаний. Подход к формализации знаний в этих моделях осуществляется на базе представления нерасчленяемых объектов в виде букв. Множество букв объединяется в ал­фавит, конструктивный процесс реализуется путем написания и гра­фического сопоставления отдельных слов, а также заменой вхождения одних слов в другие с помощью новых слов. Модель представления задачи отображается здесь графом пространства состояний. Вершина графа - это состояние процесса поиска решения, ду­ги - это связи между состояниями. Если провести разметку вершин графа с помощью букв, то путь поиска решения представляет собой слово, состоящее из меток вершин графа. Конструктивный процесс определяется как последовательность подстановок, задава­емых продукциями. Если подграф графа состояний содержит лишь одну вершину, то эта вершина отображает элементарную задачу и для представления знаний можно воспользоваться редукционной моделью. В основе этой модели лежит сведение задачи к подзадачам, т.е. редукция. Эта модель отображается И-ИЛИ-графом, на основе которого задача разбивается на подзадачи. Если известно, что для решения необходимо использовать какой-либо один из выделенных подграфов, то дуги, входящие в вершины, называются дугами типа "ИЛИ", и отношение между вершинами определяется ИЛИ-структурой взаимосвязей подзадач. Если для решения задачи должно использоваться несколько выделенных подграфов, то дуги, входящие в вершины, определяющие эти задачи, помечаются в виде гипердуг типа "И", отношение между такими вершинами определя­ется в редукционной модели как И-структура взаимосвязей подзадач. Наличие двух типов взаимосвязей, т.е. типов "ИЛИ", "И", позволяет представлять граф пространства состояния в виде дерева без циклов. Таким образом, сведение задачи к подзадачам на основе формального представления процесса поиска решений в виде И-ИЛИ-графа реализует конструктивный процесс также на основе подстановки различных символов.

Логическая модель представления знаний. Значительное примене­ние в теории искусственного интеллекта получила также логическая модель представления знаний. Знания, необходимые для решения, и решаемая задача описываются в этой модели определенными утверждениями на некотором логическом языке. Тогда знания составляют множество аксиом, а решаемая задача представляет собой доказываемую теорему. Процесс доказательства теоремы и составляет логическую модель представления знаний. Описание модели основывается на так называемой конструктивной логике. Значительную группу моделей представления знаний составляют проце­дурные модели. К этим моделям можно отнести языки логического программирования, функциональные языки, итеративные языки. Про­цесс формализации знаний хорошо прослеживается в методологии структурного программирования. В структурном программирова­нии нетрудно выделить языки, которые тождественны И-, ИЛИ-структурам взаимосвязей отдельных подзадач. Для формализации знаний могут быть использованы и специальные модели их представления. Сюда можно отнести семантические сети, фрейм-сети, в которых используются графовые способы описания конструктивных процессов. При этом фрейм-сеть может быть рас­смотрена как разновидность семантической сети и сводится к обычному И-ИЛИ-графу.

Рассмотрим логическую модель представления знаний. Зададим логическую модель четверкой M = <T, Р, A, F>, где Т - множество базовых элементов модели; Р - множе­ство правил; А - множество истинных выражений (аксиом); F - правило вывода.

Логическая модель может быть задана И-ИЛИ-графом, знания в ней представляются множеством продукций на основе специаль­ных символьных подстановок. В этой модели формулы интуици­онистского исчисления высказываний связывают задачи как пропорциональные переменные: АÇВ означает решите задачи А и В, AÈВ означает решить хотя бы одну из этих задач, А®В означает свести решение А к решению В. Логическая модель описания задачи включает в себя язык, аксиомы, правила выхода. Прежде чем перейти к содержанию описания составляющих логической модели, определим концептуально понятие задачи. Будем считать, что зада­ча включает в себя множество подзадач и взаимосвязей между ними. На нижнем уровне иерархии существует некоторая элемен­тарная задача, для которой известна программа, выполняемая вы­числительным средством без участия пользователя. Отсюда реше­ние задачи есть нахождение правил, которые задают последователь­ность решения элементарных задач в зависимости от требуемого результата и исходных данных, имеющихся у пользователя. Исход­ные данные в нашей терминологии - это входные, а результаты решения задачи - это выходные данные. По существу, для задачи известными являются исходные данные и результаты решения сово­купностей элементарных задач, входящих в состав данной задачи. В процессе решения необходимо получить значение выходных дан­ных по значениям исходных данных, что осуществляется на основе выполнения программ их решений. Так как задачи пользователя являются не элементарными задачами, то это возможно путем поиска решений на базе использования логических моделей описа­ния задач. На основе концептуального представления понятий "за­дача", "поиск решения" определим язык системы. Перечень сим­волов системы составляет ее алфавит

T = T₁È ... È T₅,

где множество T₁ включает в себя имена задач и подзадач, т.е. T₁={И₁, И₂, ...}, T₂ определяет структуру взаимосвязей подзадач: T₂={&, v}; T₃ включает в себя символ сведения задачи к подзада­чам: T₃={®}; T₄ включает вспомогательные символы: T₄={(,)}; T₅ включает символы истинности и ложности результатов решения задачи: T₅={t, f}. На основе символов алфавита строятся формулы логической модели, т.е. множество правил Р. К правилам относят следующие:

1) имя задачи есть ее описание;

2) обозначим описание задач А, В, тогда А&В есть описание задачи, при котором необходимо решить задачу с описанием А и за­дачу с описанием В. AÈВ - это описание задачи, для решения которой достаточно решить задачу с описанием А либо задачу в описанием В;

3) если описанием задачи является ее имя, то эта задача называ­ется элементарной. Если задача с именем И сводится к задаче с описанием А, то И®А. При этом элементы описания А являются описаниями подзадач, входящих в задачу с именем И;

4) символы 1, Æ означают описание задач с результатами их решения, символ 1 означает A = t, символ Æ означает A = f.

Поиск решения задачи на основе логической модели представле­ния знаний базируется на использовании ряда аксиом:

(1)AÈB=BÈA;

(2)(AÈB)ÈC=AÈ(BÈC);

(3)(А&В)&С=А&(В&С);

(4)A&(AÈB)=A;

(5)AÈ(A&B)=A;

(6)(АÈВ)&С=А&СÈВ&С;

(7)А&Æ=Æ&А=Æ;

(8)АÈÆ=А;

(9)А&1=1&А=А;

(10)АÈ1=1.

Приведенные аксиомы задают преобразования, позволяющие получать описание исходной задачи, эквивалентное заданному. Эти преобразования используются в процессе поиска решения исходной задачи. Путь получения решения задается правилами вывода (множеством F): исходная задача А сводится к задаче В, поэтому для решения задачи А необходимо решить задачу В. Последовательность описания решаемой задачи определяется правилами подстановки описаний составляющих ее подзадач. Смысл применения правил подстановки заключается в том, что для получения описа­ния некоторой задачи необходимо дать описание последовательно составленных вложенных друг в друга подзадач с особым выделением элемента описания конечной подзадачи.

Логической модели представления знаний и задач соответствует графическое отображение в виде графа редукции и графа пространства состояний. Вершины графа редукции соответствуют именам задач. Имя корневой вершины есть имя исходной задачи, имена дочерних вершин - это имена подзадач. Связи между подзадачами отображаются дугами, для конъюнкции используется гипердуга типа "И", для дизъюнкции - дуги типа "ИЛИ". По мере решений и перехода к последующим подзадачам осуществляется построение графа редукции сверху вниз. В концевых вершинах располагаются элементарные подзадачи, для которых существуют программы решения на ЭВМ. Поиск решения исходной задачи отображается на графе редукции последовательностью обхода его вершин.

Граф редукции может быть преобразован в граф пространства состояний. Вершинами этого графа являются процессы решения элементарных подзадач либо процессы решения задач с ИЛИ-структурой взаимосвязей составляющих их подзадач. Вершины, определяющие элементарные подзадачи, имеют лишь одну исходящую дугу, а вершины, определяющие задачи с ИЛИ-структурой, имеют столько исходящих дуг, сколько данная задача содержит подзадач с ИЛИ-структурой. На этом графе должен существовать путь корневой вершины в одну из концевых, что и задает получение решения задачи в виде последовательности обхода вершин графа пространства состояний. Рассмотрим на примере доказательство существования решения для некоторой исходной задачи А и отобразим эту задачу на графе редукции. Пусть задача А задана следующими утверждениями:

А®ВÈО, B®C&J, C®DÈE, E®F&G, J®KÈL, L® M&N, O®PÈQ, Q®R&S.

Доказательство существования решения для задачи А выполним на основе раскрытия решения этой задачи через решение составляющих ее подзадач. Для этого воспользуемся приведенными выше аксиомами и правилами вывода:

A®BÈOÞ{B®C&J}ÞC&JÈOÞ{C®DÈE}Þ(DÈE)&JÈOÞ

ÞD&JÈE&JÈO=D&JÈE&JÈO={D=t}=[D]&JÈE&JÈO{J®KÈL}Þ

Þ [D]&(KÈL)ÈE&JÈO=[D]&KÈ[D]&LÈE&JÈOÞ

Þ{k=f}=[D]&Æ È[D]&LÈE&JÈO=[D]ÈLÈE&JÈOÞ

Þ [D]&M&NÈE&JÈO={M=t}=[D]&[M]&NÈE&JÈO={N=t}=[D]&M&[N]ÈE&JÈ0.

Видно, что решение задачи А сводится к решениям подзадачD, M, N, которые являются элементарными (в квадратных скобках указаны имена этих подзадач). Процесс поиска решения задачи A может быть отображен на графе редукции в виде пунктирного пути обхода соответствующих вершин графа (обход осуществляется слева направо). Из графа редукции видно, что обход вершин завершается в вершинах D, М, N, что соответствует решению элементарных подзадач на основе программ, заложенных в ЭВМ.

Преобразуем для рассматриваемой задачи А граф редукции в граф пространства состояний, отображающий процессы решения элементарных задач или процессы решения задач с ИЛИ-структурой. Исключим из графа редукции вершины с гипердугами. Тогда в корневой вершине будет расположена исходная задача А, вершина B исключается. В связи с исключением вершины В за вершиной D располагаем вершину J с соответствующей ИЛИ-структурой подзадач K, М. Процесс поиска решений отобразим пунктиром, обозначающим последовательность обхода вершин до попадания в конечную вершину N. Следует отметить, что логическая модель представления задачи, граф редукции и граф пространства состояний являются эквивалентными представлениями процесса по­иска решения исходной задачи. Реализация этой модели на ЭВМ с целью формализации знаний возможна на основе языка Пролог и ему подобных языков логического программирования.

Алгоритмическая модель представления званий. В процессе форм­ализации знаний зачастую используются средства "алголоподобных" языков программирования. При этом формируется алгорит­мическая модель представления знаний. Такая модель может отоб­ражаться формальной системой, графом редукции и графом про­странства состояний задачи. Формальная система задает описание решения задачи в виде программы вычисления. В основе формаль­ной системы лежат алфавит используемого языка, правила форм­ирования выражений из элементов этого алфавита, аксиомы и пра­вила вывода. Алфавит определяется множеством

T=T₁È T₂È T₃,

где T₁={A₁, ..., A_n}, A₁, ..., A_n - имена подзадач, используемых для решения исходной задачи.

Если под A₁, ..., A_n понимать описание подзадач, то последо­вательность A₁, ..., A_n есть описание исходной задачи; T₂={; case, of, while, do} включает в себя слова, позволяющие строить синтаксические конструкции описания последовательности решения задачи. Значения этих слов следующие:

case A of A₁, ..., A_n; - описание исходной задачи, для получения результата решения которой необходимо и достаточно решить одну из ее подзадач:

A₁, ..., A_n; while A do В - описание исходной задачи А, для получения решения которой необходимо многократно решать ее подзадачу;

T₂={begin, end} - определяет вспомогательное обозначение, символы "begin", "end" употребляются в соответствии с правилами подстановки.

Семантическая модель представления знаний. Возможности про­дукционных моделей могут быть значительно расширены на основе использования аппарата семантических сетей. Семантическая мо­дель представления знаний позволяет оперировать с понятиями, выраженными в естественном языке, и поэтому находит широкое применение в экспертных системах. Семантическую сеть можно представить в виде графа

G = {N₁, ..., N_n, b₁, ..., b_m),

где N₁, ... , N_n - узлы (вершины графа), отображающие некоторые су­щности (объекты, события, процессы, явления); b₁, ... , b_m - дуги гра­фа, представляющие собой отношения между сущностями, задан­ные на множестве вершин.

Для определения типа используемой сети необходимо устано­вить ограничения на описание вершин и дуг. Сеть называют про­стой, если вершины ее не имеют собственной внутренней структуры. Вершины могут отображать при этом сущности разной степени общности, их упорядочение осуществляется по определенным ви­дам отношений. Простые сети нашли применение на начальном этапе конструирования экс­пертных систем. При последующем развитии перешли к иерархичес­ком сетям, в которых вершины обладают собственной внутренней структурой. Возникает возможность отображения предметной об­ласти как совокупности сущностей и отношений между ними, что удается выполнить в терминах естественного языка. Это становится особенно актуальным при автоматизированном построении модели предметной области на основе сформированных разработчиком понятий объектов и отношений. Результаты обследования предпри­ятия обычно представляются в виде конкретных объектов, обобща­емых при формировании модели предметной области. Аппарат семантических сетей предоставляет пользователю любые виды от­ношений. Введя связь "является представителем", можно определить знание в виде "конкретный объект является представителем обобщенного объекта". При этом предполагается, что конкретный объект обладает определенной группой свойств, принадлежащих обобщенному объекту. Семантическая модель представления зна­ний может быть успешно применена, если в предметной области сформулированы фундаментальные понятия объектов и отношений.

Выделяют конкретный объект как единичную (индивидуальную) сущность, обобщенный, представляющий собой класс объектов, и агрегатный, формируемый из нескольких объектов. Последний по содержанию является обобщенным или конкретным. Фундаментальные типы объектов должны быть сформулированы в терминах понятий предметной области в целях общения пользователя с базой знаний на естественном языке. Между объектами должны быть определены и фундаментальные типы связей. К ним можно отнести родовую и обратную ей - видовую связь. Обобщенный объект узла сети N₁ имеет родовую связь с обобщенным объектом узла N₂, если любой отображаемый понятием N₂ объект отображается также понятием N₁. При этом обратное утверждение является неверным, т.е. понятие N₁ является более общим, чем понятие N₂. Объект, отображаемый узлом N₁, является родом для объекта, отобража­емого узлом N₂. Соответственно в терминах видовой связи - "N₂ является видом N₁". Отметим, что все свойства родового понятия должны быть присущи видовому, однако последнее может обладать дополнительными свойствами. Между обобщенным и конкретным объектами существует связь "быть представителем", тогда конкретный объект входит в класс, определяемый обобщенным объектом. Между агрегатным объектом и другим, входящим в него, существует отношение вида "является частью".

Рассмотренные семантические отношения формально могут отображаться различными классами связей, в том числе логическими, теоретико-множественными, лингвистическими, квантификационными. Логические связи базируются на алгебре логики и наглядно отображаются в графе семантической сети. В квантификационных сетях наряду с логическими кванторами присутствуют нелогические, а также числовые характеристики выделяемых объектов. Связи между агрегатными объектами и составляющими их частями хорошо описываются на основе теоретико-множественных отношений. Интеллектуализация доступа пользователя к знаниям может быт реализована на основе лингвистических связей. Родовые, видовые отношения и отношения типа "является частью" обладают свойствами транзитивности. Это позволяет хранить в базе знаний не все фундаментальные типы отношений, а лишь часть их, получая остальные путем вывода из имеющихся.

Построение моделей предметной области и математических моделей на базе аппарата семантических сетей означает изменение конфигураций сети, т.е. удаление составляющих либо дополнение ее новыми вершинами и дугами. Для иерархических сетей допустимо разделение на подсети (пространства), которые могут отображать отдельные фрагменты модели. Между подсетями могу быть установлены отношения, и по запросу вызываться участки сети, формируя текущие знания. Обращение пользователя к базе знаний, построенной на основе семантической модели, представляется сетью, формируемой по таким же правилам. При этом реализуется операция сопоставления сети запроса с отдельными подсетями, входящими в семантическую модель. Положительные результаты процедуры формируются в виде фрагментов. Фрагмент проектируемой пользователем модели отображается подсетью, т.е. совокупностью вершин. Смысловое содержание его задается упорядочением вершин по уровням иерархии в соответствии с выбранными фундаментальными типами отношений. Вершины семантической сети по типу разделяются на экстенсиональные, отображающие понятия, и интенсиональные, представляющие процедуры оценки принадлежности фактов и явлений к этим понятиям. В результате оценки формируется значение. Таким образом, в семантической сети выделяются два типа вершин: "понятия" и "значения". Нахождение любого фрагмента целесообразно вести по некоторому обобщенному понятию, которое отображается корневой вершиной. Таким образом, можно считать, что любой фрагмент определяется фиксированным набором вершин семантической сети и может быть идентифицирован по корневой вершине.

Формирование моделей возможно путем формальных процедур образования фрагментов, которые могут быть выполнены в терминах алгебраической системы. Преобразование возможно также на уровне полных фрагментов, тогда формальные процедуры осуществляются с использованием корневых вершин. Зачастую необходимо вносить изменения в структуру фрагмента, что можно реализовать за счет удаления либо добавления отдельных вершин графа. Алгебраическая система служит основой автоматизированного проектирования модели предметной области на базе семантической сети при диалоговом взаимодействии проектировщика с базой знаний. Семантическая модель может быть эффективно использована на этапе предпроектного анализа и концептуального проектирования АСОИУ. Семантические сети находят применение в случае фреймового представления знаний.

Фреймовая модель представления знаний. Фреймовая модель в своей теоретической основе базируется на психологических понятиях восприятия человеком окружающего мира. Поведение человека во многом определяется внешними условиями, т.е. ситуацией, в которую он попадает. При этом он идентифицирует новую ситуацию некоторой типовой структурой, называемой фреймом. Фрейм - это декларативное представление стандартной ситуации, дополненное процедурной информацией о возможностях и путях его использования. Фрейм представляется сетью. Верхние ее уровни отображают сущности, истинные для типовой ситуации, задавая тем самым абстрактную конструкцию фрейма. Нижние уровни заканчиваются пустыми слотами, означивание которых осуществляется при вызове фрейма в соответствии с конкретной ситуацией из предметной области. Таким образом, фреймовая модель позволяет сформировать иерархическую структуру отношений типа "абстрактное - конкретное". Можно считать, что по отношению к семантическому представлению фреймовый подход является частным случаем, позволяя при этом более эффективно использовать процедурные знания.

При фреймовом подходе выделяются также обобщенные, единичные и агрегатные объекты. Фрейм отображает объект, который является представителем обобщенного. Значения конкретного объекта могут быть получены при запросе за счет реализации определенных процедур. Сложный объект отображается комбинацией нескольких фреймов, что соответствует фреймовой сети. Фреймовая модель по сравнению с семантической обеспечивает более детальное выделение объектов и различных ситуаций при описании предметной области. В этой модели, с одной стороны, находят представление достаточно крупные обобщенные единицы знаний, а с другой - конкретные факты и ситуации, что позволяет систематизированно описать постановку задачи. Структурно фрейм включает в себя набор слотов

F=[(С₁, d₁), ..., (С_n, d_n)],

где F - имя фрейма; С_{1 ,} ..., С_n - имена слотов; d_{1 ,} ..., d_n - значения слотов.

При объединении фреймов в значения слотов подставляют имена подсоединяемых фреймов. Система, объединяющая фреймы должна содержать описание причинных, временных и других зависимостей между входящими в нее частями. Фреймовая система обеспечивает достаточно простое описание процесса перехода объектов из одного состояния в другое. Для этого не обязательно вычислять значения всех слотов, а достаточно перечислить только изменившиеся. Особый интерес представляет использование в этой модели концепции "умолчания", которая предусматривает присвоение пустым слотам некоторых заданных значений, если конкретные из анализа предметной области неизвестны. По мере возникновения знаний стандартные значения могут быть скорректированы. Если в процессе изучения предметной области не удалось присвоить слотам значения, удовлетворяющие условиям задачи, то необходимо сконструировать новый фрейм. Это удается осуществить, если система фреймов организована в информационно-поисковую сеть.

При наличии в модели необходимой совокупности фреймов внесение новой информации осуществляется путем сопоставления, в ходе которого определяется правильность выбора фрейма. Обычно фрейм содержит условия, ограничивающие пределы возможных значений входящих в него слотов. Процесс сопоставления часто реализуется интуитивно, результат оценивается выполнением соответствующих ограничений, содержащихся во фрейме. Если этот процесс оказался неуспешным, то осуществляется запрос к другому фрейму. Отсутствие и в последующем желаемого результата означает, что задача в данном представлении не может быть решена.

Структура данных фреймовой модели представления знаний включает в себя:

1) имя фрейма, представляющее собой идентификатор, который однозначно определяет его в данной системе. Фрейм включает в себя произвольное число слотов, большая часть которых заполняется данными пользователя, а некоторые имеют функциональный характер, определяя фрейм-родителя, дочерние фреймы, дату, имя пользователя, комментарии и т.д. Слоты обладают своей структурой данных;

2) имя слота, представляющее собой идентификатор, который позволяет найти каждый из них в данном фрейме. Часть имен не имеет смыслового характера, однако некоторые из них, например системные, отражают выполняемые процедуры;

3) указатели наследования, обозначающие отношения между объектами во фреймовых системах иерархического типа. Слоты фреймов разных уровней иерархии могут иметь одинаковые имена, но включают в себя указатель наследования, который отражает характер связи данных, содержащихся в слотах;

4) указатели атрибутов слота, показывающие форму представления и назначение данных в слоте. Представление возможно в виде слота или числовых значений, назначением слота может являться реализация присоединенной процедуры, на основе которой фреймы связываются в систему. С помощью присоединенной процедуры эффективно формируется любая программа управления выводом знаний из системы, представленной фреймовой моделью;

5) демоны, т.е. процедуры, автоматически запускаемые при выполнении определенных условий. Они разделяются по типу, имеют имена и запускаются при работе пользователя с данными слота. Таким образом, фреймовую модель можно рассматривать как некоторую идеологию представления знаний, которая может по-раз­ному реализовываться в конкретных языках. Разработаны формальные языки и системы программирования, поддерживающие аппарат фреймов и семантических сетей. Фреймовая модель может с успехом применяться для представления знаний при формировании модели предметной области.

Перспективным путем совершенствования и дальнейшего развития экспертных систем является создание инструментальных средств, базирующихся на совместном использовании различных моделей представления знаний. Интеграция моделей прежде всего обусловлена разными целями, преследуемыми на отдельных стадиях создания, проектирования, внедрения и эксплуатации систем. Возможности отдельных моделей представления сильно различаются между собой: в одних моделях более сильно выражена семантическая составляющая, в других - логические правила вывода и т.д. При формировании модели предметной области наилучшие результаты дает использование семантической и фреймовой моделей, при автоматизированном построении математической модели решения задачи более эффективным может оказаться применение логической и алгоритмической в силу имеющихся типовых программных средств. Совместное использование различных моделей при построении интеллектуальных систем позволяет наилучшим образом использовать достоинства одних и скомпенсировать недостатки других.

Объединение процедурных и логических методов представления знаний реализуется при объектно-ориентированном подходе к программированию. Программа представляется в виде самостоятель­ных объектов, которые в процессе функционирования обмениваются между собой сообщениями. В объект включается совокупность данных и действий над ними. Отображением объектов могут быть фреймы, содержащие декларативные и процедурные знания. Одновременно имеется возможность представить объекты в виде логических высказываний и соответственно формул. Таким способом осуществляется совместное использование фреймовой и логической моделей. Интеграция модели не ограничивается этим примером. Рассмотренные модели являются математическим средством построения перспективных интеллектуальных АСОИУ.

---

⇐ Назад
• 1
• 2
• 3
• 4
• 567
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• Далее ⇒