автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы построения смешанных диагностических тестов и принятия решений

На правах рукописи

Кузоваткин Андрей Николаевич

АЛГОРИТМЫ ПОСТРОЕНИЯ СМЕШАННЫХ ДИАГНОСТИЧЕСКИХ ТЕСТОВ И ПРИНЯТИЯ РЕШЕНИЙ

05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Томск-2005

Работа выполнена в Томском государственном университете.

Научный руководитель: доктор технических наук, профессор

Янковская Анна Ефимовна.

Официальные оппоненты: доктор технических наук, профессор

Матросова Анжела Юрьевна;

кандидат технических наук, доцент Ходашинский Илья Александрович.

Ведущая организация: Институт "Кибернетический центр"

Томского политехнического университета.

Защита состоится 24 февраля 2005 в 10 час. 30 мин. на заседании диссертационного совета Д 212.267.08 в 102 аудитории 2-го корпуса Томского государственного университета по адресу: г. Томск, пр. Ленина 36.

С диссертацией можно ознакомиться в библиотеке Томского государственного университета.

Автореферат разослан 21 января 2005 г.

Ученый секретарь диссертационного совета доктор технических наук, доцент

Скворцов А.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Основополагающие результаты в области распознавания образов, искусственного интеллекта и интеллектуальных систем получены Журавлевым Ю.И., Ларичевым О.И., Осиповым Г.С., Поповым Э.В., Поспеловым Г.С., Поспеловым Д.А., Финном В.К. Большой вклад в эти области внесены также Берштейном Л.С., Вагиным В.Н., Гладуном В.П., Еремеевым А.П., Загоруйко Н.Г., Закревским А.Д., Зенкиным А.А., Кобринским Б.А., Кузнецовым О.П., Курейчиком В.М., Лбовым Г.С., Мелиховым А.Н., Нариньяни А.С., Переверзе-вым-Орловым B.C., Печерским Ю.Н., Рудаковым К.В., Рязановым В.В., Стефа-нюком В.Л., Тарасовым В.Б., Хорошевским В.Ф., Янковской А.Е. и др.

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

Процедуры построения безусловных и условных тестов, используемых для распознавания образов, являются весьма трудоемкими, и их оптимизации уделяется большое внимание в трудах Журавлева Ю.И., Дюковой Е.В., Мош-кова М.Ю., Янковской А.Е. и ряда других ученых.

Таким образом, до сих пор весьма актуальными являются как разработка менее трудоемких алгоритмов тестового распознавания, приводящих к построению "хороших" тестов, то есть, обеспечивающих лучшее качество решений (по простоте решающих правил, точности принимаемых решений и минимизации затрат на их получение), так и создание на базе этих алгоритмов интеллектуальных систем, инвариантных к проблемным областям.

Именно на обеспечение лучшего качества принимаемых решений и направлена диссертационная работа, посвященная алгоритмам построения смешанных диагностических тестов (СДТ) и принятия решений. Обоснования целесообразности применения СДТ в интеллектуальных системах приводятся в работах А.Е.Янковской.

Актуальность исследований подтверждается поддержкой Российского фонда фундаментальных исследований (проекты: № 98-01-00295 "Логико-вероятностный вывод на основе оптимальных смешанных диагностических тестов, частичной импликации и средств когнитивной графики в интеллекту-

альных системах"; № 01-01-0772 "Логические тесты, логико-комбинаторно-вероятностный вывод и средства когнитивной графики в интеллектуальной системе"; № 01-01-01050 "Развитие интеллектуальной системы логико-комбинаторного принятия решений, основанной на матричном представлении знаний"; № 04-01-00144 "Технология решения связанных по экспертному заключению задач, основанная на логических тестах и средствах когнитивной графики в интеллектуальной системе", в выполнении которых принимал участие диссертант).

Цель работы. Развитие методов построения СДТ при матричном представлении данных и знаний в пространстве двоичных, троичных, номинальных, целочисленных признаков и реализация этих методов в интеллектуальном инструментальном средстве ИМСЛОГ (ИИС ИМСЛОГ), предназначенном для создания прикладных интеллектуальных систем выявления закономерностей в данных и знаниях и принятия решений для широкого круга проблемных областей.

Для достижения данной цели необходимо:

1. Для матричного представления данных и знаний в пространстве двоичных, троичных, номинальных, целочисленных признаков разработать алгоритмы построения СДТ и принятия решений на их основе, а также алгоритмы принятия решений непосредственно в процессе построения смешанного диагностического теста в пространстве троичных признаков.

2. Разработать алгоритмы построения безызбыточной двоичной матрицы импликаций (для интервального и константного задания значений целочисленных признаков), задающей различимость объектов из разных образов.

3. Осуществить программную реализацию перечисленных выше алгоритмов в виде программных модулей ИИС ИМСЛОГ.

4. Создать на базе ИИС ИМСЛОГ прикладные интеллектуальные системы для решения задач в следующих областях: "Генетические изменения (оценка состояния здоровья ребенка по генетическим и функциональным показателям)"; "Квалифицированная и специализированная помощь при лучевых поражениях"; "Организационно-управленческие решения при чрезвычайных ситуациях"; "Оценка научно-технических проектов".

Методы исследования. В диссертационной работе применялись методы дискретной математики, распознавания образов, искусственного интеллекта, прикладного и системного программирования.

Научная новизна содержится в следующих результатах:

1. Разработаны новые алгоритмы построения СДТ при представлении данных и знаний в пространстве троичных, номинальных и целочисленных признаков.

2. Разработаны новые алгоритмы принятия решений непосредственно в

процессе построения СДТ на основе безусловных тестов в пространстве троичных, номинальных и целочисленных признаков.

3. Получены формулы для вычисления коэффициента разделения, используемого при построении дерева СДТ.

4. Разработаны новые алгоритмы построения безызбыточной двоичной матрицы импликаций, используемой для выявления закономерностей в данных и знаниях в пространстве троичных, номинальных и целочисленных признаков.

Апробация работы. Основные положения и результаты диссертации представлены в докладах: 3-й Всероссийской конференции с международным участием "Новые информационные технологии в исследовании дискретных структур" (Томск, 2000); научной сессии МИФИ-2002 (Москва, 2002); Международной научной конференции "Интеллектуализация обработки информации (ИОИ-2002)" (Симферополь, 2002); Международном семинаре "Компьютерная лингвистика и интеллектуальные технологии (Диалог-2002)" (Протвино, 2002); международной научно-технической конференции "Интеллектуальные САПР" (Таганрог, 2002); Международной конференции "Информационные системы и технологии (ИСТ-2003)" (Новосибирск, 2003); второй Международной конференции по проблемам управления (Москва, 2003); VI международном конгрессе по математическому моделированию (Нижний Новгород, 2004).

Публикации. Основные результаты диссертации были опубликованы в 11 работах, две из которых журнальные публикации, а одна в периодическом сборнике.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав и заключения. Объем работы составляет 106 страниц. Список литературы содержит 91 наименование.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, дана общая характеристика работы.

В первой главе приведены модели представления знаний, основные подходы к принятию решений, а также методы и алгоритмы построения логических тестов.

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

В матричной модели знания представляются в виде: матрицы описаний (0, элементы которой принимают двоичные, троичные, Л-значные значения; целочисленных матриц различений (К) трех типов. Первый тип матрицы различений характеризуется вложенностью механизмов классификации, когда каж-

дый последующий столбец задает более подробное разбиение объектов на классы эквивалентности, чем предыдущий. Второй тип может интерпретироваться как совокупность действий, которые необходимо выполнить для данного объекта (данной ситуации). Третий тип служит для представления независимых механизмов классификации, где столбцы отражают, например, мнения различных экспертов. Наличие матрицы различений 1-го или 3-го типа, обязательно. Строка матрицы различений задает обобщенный класс (образ). Если имеется единственный механизм классификации, матрица различений вырождается в столбец, а обобщенный класс превращается в класс, что соответствует традиционному представлению знаний в задачах распознавания образов.

Для изложения алгоритмов используется вектор-столбец образов (Л1), строки которого сопоставлены объектам обучающей выборки (строкам матрицы 0, а значениями являются номера образов (обобщенных классов).

Данная модель позволяет представлять не только данные, но и знания экспертов, поскольку одной строкой матрицы описаний можно задавать в интервальной форме подмножество объектов, для которых характерны одни и те же решения, задаваемые строкой матрицы Я.

При обнаружении пересечения описаний образов матрица описаний должна быть доопределена.

На рис. 1 приведен пример матриц QжR, а также вектор-столбец образов Л* для представления знаний с использованием троичных (1,0,-) признаков, где символ "-" означает, что значение признака безразлично (признак может принимать как нулевое, так и единичное значение).

Рис 1. Матричное представление данных и знаний для троичных характеристических признаков

Рассмотрены следующие методы и алгоритмы построения логических тестов: алгоритм КОРА (Бонгард М.М.), методы построения тупиковых тестов (Журавлев Ю.И.), алгоритм построения безусловных тестов на основе нахождения минимальных столбцовых покрытий безызбыточной матрицы импликаций (Янковская А.Е., Гедике А.И.), алгоритмы построения безусловных тестов непосредственно по матрицам описаний и различений (шагово-циклические алгоритмы) (Янковская А.Е.), алгоритм синтеза граф-схем для распознавания образов (Орлов В .А.), алгоритмы построения смешанных диагностических тестов на основе безусловных (Янковская А.Е., Кузоваткин А.Н.).

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

В диссертации используется понятие закономерностей, предложенное А.Е. Янковской. К закономерностям относятся константные, устойчивые (кон-' стантные внутри образа), неинформативные (не различающие ни одной пары объектов), альтернативные (в смысле включения в диагностический тест), зависимые (в смысле включения подмножеств различимых пар объектов), несущественные (не входящие ни в один безызбыточный тест), обязательные (входящие во все безызбыточные тесты), псевдообязательные (входящие во множество используемых при распознавании безызбыточных тестов и не являющиеся обязательными) признаки, а также все минимальные и все (либо часть - при большом признаковом пространстве) безызбыточные различающие подмножества признаков, являющиеся, по сути, соответственно минимальными и безызбыточными (тупиковыми) логическими тестами. К закономерностям также относятся и весовые коэффициенты признаков, характеризующие их индивидуальный вклад в различимость объектов из разных образов.

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

Термин и понятие "смешанный диагностический тест" (СДГ), представляющий собой оптимальное сочетание безусловных и условных составляющих, введены в 1996 г. А.Е. Янковской.

СДГ представляет собой дерево, ярусам которого (за исключением первого) сопоставлены необязательные признаки, входящие в безусловный тест, ребрам - значения этих признаков, а каждой вершине (за исключением корня и концевых вершин) сопоставлена пара (£,/), где Ь - реакция матрицы описаний, ] - номер признака. Корню дерева сопоставляется пара (5, G), где 5- совокупность всех строк матрицы описаний, О - совокупность обязательных признаков. Ребрам первого яруса дерева сопоставляется множество возможных значе-

ний обязательных признаков. Каждая реакция, соответствующая вершине дерева, однозначно определяется значениями признаков на пути к этой вершине. Реакция, сопоставленная каждой концевой вершине, содержит множество строк матрицы описаний, описывающих объекты обучающей выборки, принадлежащие одному образу. Концевой вершине сопоставляется также номер образа, которому она соответствует.

Также приведем ряд определений и пример безызбыточной матрицы импликаций и выявленных закономерностей.

Для уменьшения степени неполноты смешанного диагностического теста вводится коэффициент разделения признаков.

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

(у- количество образов, входящих в реакцию предыдущего яруса; - количество образов, входящих в реакцию, соответствующую значеник .¡-го признака;

Т- множество значений _/-го признака.

Коэффициенты разделения не вычисляются для признаков, не входящих в безусловный тест, на основе которого строится СДТ, и для признаков, реакцией на значения которых является текущая реакция (реакция предыдущего яруса).

Алгоритм построения СДТ и принятия решений состоит из следующих шагов.

1. По матрице описаний и матрице различений осуществляются поиск различных закономерностей и построение безусловных (минимальных или безызбыточных) тестов.

2. Для каждого безусловного теста строится дерево СДТ.

3. Производится проход по построенным деревьям от корня к листьям в соответствии со значениями признаков исследуемого объекта. Тест отдает голос за образы, соответствующие листьям, лежащим на концах пути обхода дерева СДТ.

4. Применяется процедура голосования на множестве деревьев и принимается решение о принадлежности исследуемого объекта к тому образу, за который получено наибольшее число голосов.

Алгоритм принятия решений непосредственно в процессе построения

(О

где - коэффициент разделения признака на ярусе;

СДТ состоит из следующих шагов.

1. По представленной в виде матрицы описаний и матриц различений (3-х типов) обучающей выборке осуществляются поиск различных закономерностей и построение безусловных (минимальных или безызбыточных) тестов.

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

3. Применяется процедура голосования на множестве тестов и принимается решение о принадлежности исследуемого объекта к тому образу, за который получено наибольшее число голосов.

В третьей главе приводятся алгоритмы построения смешанных диагностических тестов и принятия решений для представления знаний в пространстве троичных признаков.

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

с,=тКкъ+к*), (2)

где Т- нормировочная константа, равная К"/2а'1;

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

К- количество образов в предыдущем ярусе;

- количество образов в реакциях на нулевое (равное 0) и единичное (равное 1) значение /-Г0 признака, соответственно.

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

Формула 2 позволяет учитывать как степень непересечения подмножеств образов, так и равномерность разбиения реакции предыдущего яруса. При коэффициенте а=1 получим формулу 1, учитывающую только непересечения; при росте увеличивается вклад равномерности разбиения реакции предыдущего яруса.

Обоснованием введения модифицированной формулы служит утверждение!.

Утверждение 1. Длина дерева СДТ минимальна, если

К,0+КЛ=К.

Для двоичного и троичного представления данных используется следующий алгоритм построения СДТ на базе построенных безусловных тестов.

1. Из матрицы описаний удаляются столбцы, соответствующие константным, неинформативным, несущественным и зависимым признакам.

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

3. Используется следующая рекурсивная процедура по каждому из безусловных тестов.

Пусть Ь - реакция матрицы описаний, сопоставленная вершине _/, находящейся на 1-м ярусе. Если Ь состоит из множества строк, описывающих один образ, то вершина - концевая. Иначе, вычисляются коэффициенты разделения признаков, производится выбор из безусловного теста следующего признака с максимальным коэффициентом разделения и разбиение X на реакции относительно значений выбранного признака на (г+1)-м ярусе.

Во второй части алгоритма осуществляется непосредственно принятие решения по построенным деревьям путем прохода от корня дерева к одной или нескольким концевым вершинам по следующему алгоритму.

1. Формируется: список голосов (О), отданных за каждый из образов (первоначально устанавливаются нулевые значения для элементов списка); список деревьев СДТ (7) (в начальный момент в него входят все построенные деревья); список указателей на вершины деревьев тестов (Р) (каждый указатель из Р содержит ссылку на вершину соответствующего дерева теста и величину голоса, отдаваемого после принятия решения с использованием этого указателя); список указателей на концевые вершины деревьев (¥) (в начальный момент список пуст).

2. Производится запрос значений всех обязательных признаков.

3. Производится выбор первого дерева из списка деревьев смешанных диагностических тестов. Создаются и заносятся в список Р указатели на вершины первого яруса, каждая из которых соответствует совокупности введенных значений всех обязательных признаков. Величина голоса, соответствующая каждому указателю, вычисляется по следующей формуле: g=(2fl) где А^ -количество реакций на значения обязательных признаков.

4. Производится выбор первого указателя (р) из списка Р.

5. Запрашиваются значения признака, соответствующего указанной вр-вершине.

6. Если значение признака исследуемого объекта нельзя определить (неизвестно), то указатель перемещается на вершину следующего яруса, соответствующую нулевому значению запрашиваемого признака; величина голоса уменьшается вдвое; создается и заносится в список Р указатель на вершину дерева теста, соответствующую единичному значению; вес голоса созданного указателя устанавливается равным половине голоса указателя на входе. Иначе, р перемещается на соответствующую вершину следующего яруса.

7. Если вершина v концевая, то указатель на нее заносится в список Ж и удаляется р из списка Р.

8. Если список Р не пуст, то переход к пункту 7. Иначе, голос, отданный за все образы, соответствующие входящим в список /'вершинам, увеличивается на величину где ¡V - вес теста, т - количество образов, соответствующих вершинам, входящим в список Ж. Из списка Т удаляется рассмотренное дерево и, если список Тне пуст, то переход к пункту 3, иначе, конец.

На рис. 2 приводится пример принятия решений для матриц описаний и различений, представленных на рис. 1. В безусловный тест входят признаки

{1,2,3,4,6,8}.

Рис, 2. Дерево смешанного диагностического теста

В разработанном в диссертационной работе алгоритме принятия решения непосредственно в процессе построения смешанного диагностического теста принятие решения осуществляется по следующему алгоритму.

1. Запрашиваются у пользователя значения всех обязательных признаков (процедура выполняется единожды при принятии решения по первому безусловному тесту).

2. Производится построение реакции матрицы описаний на множество обязательных признаков.

3. Упорядочивается множество столбцов матрицы описаний по неубыванию коэффициентов разделения.

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

5. Если значение выбранного признака известно (равно 0 или 1), то про-

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

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

7. В случае если у исследуемого объекта часть признаков не была определена, они доопределяются следующим образом. Создается группа из 2* (где к - количество неопределенных признаков) объектов, у которых все признаки определены. После этого производится принятие решения относительно каждого объекта из полученной руппы, но величина условного голоса за каждый образ уменьшается в раз.

В примере, приведенном на рис. 2, путь прохода по дереву, необходимый для принятия решения, показан пунктирными стрелками.

Также в третьей главе производится сравнение предложенных алгоритмов с методами и алгоритмами построения логических тестов, описанными в первой главе диссертации.

В четвертой главе приводятся алгоритмы построения матрицы импликаций и алгоритмы построения смешанных диагностических тестов и принятия решений для матричного представления знаний в пространстве целочисленных признаков, заданных в константном и интервальном виде.

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

1. Построение двоичной безызбыточной матрицы импликаций с одновременным вычислением весовых коэффициентов признаков на основе целочисленной матрицы описаний.

2. Поиск кратчайших столбцовых покрытий двоичной матрицы импликаций с одновременным выявлением закономерностей (алгоритм Янковской А.Е., Гедике А.И.)

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

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

ний по номерам образов. Формируется вещественная вектор-строка (В), элементами которой являются весовые коэффициенты признаков, используемых для построения матрицы импликаций. В начальный момент все компоненты этой строки равны 0.

2. Производится сравнение всех пар строк матрицы описаний, относящихся к разным образам. Для каждой пары строк производится построение двоичной строки матрицы импликаций и корректировка вещественной строки (В) по следующим правилам:

2.1. Если значения признака у сравниваемых строк совпадают, то соответствующему элементу формируемой двоичной строки присваивается значение "0", иначе, присваивается значение " 1".

I .явление к каждому элементу строки весов признаков величины

3. Производится проверка на избыточность (на поглощение) построенной строки с уже построенными строками матрицы.

3.1.Если в матрице импликаций есть строки, поглощающие построенную строку, то они удаляются, а построенная строка добавляется в матрицу импликаций.

3.2.Если построенная строка поглощает какую-либо строку матрицы импликаций, то она в матрицу импликаций не добавляется.

ЗЗ.Если построенная строка не поглощается другими строками матрицы импликаций и не поглощает ни одну из уже построенных строк, то она добавляется в матрицу импликаций.

ЗАЕсли рассмотрены все пары строк матрицы импликаций, то переход к пункту 4, иначе, производится сравнение следующей пары строк.

4. Производится нормировка элементов вектор-строки (В) по формуле:

Фг- количество объектов, принадлежащих г-му образу, где г е {_/',£}. Двоичную матрицу импликаций допустимо использовать для построения

где ^-значение /-ГО признака_/-Й строки;

-значение /-ГО признака к- Й строки; Р, - вес /-го признака;

(3)

где - максимальный интервал признака; - номер признака; у, А-номера строк },к е {1,...,с/}, где ¿-количество образов;

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

Для целочисленного матричного представления данных и знаний с использованием интервального задания значений признаков алгоритм построения безызбыточной матрицы импликаций отличается от алгоритма построения матрицы импликаций для целочисленного матричного представления данных и знаний с использованием константного задания значений признаков в следую-щихдеталях.

1. Вычисляется вес каждой строки матрицы описаний по формуле: где 1 - номер признака;

] - номер строки матрицы описаний уе{1,...,и} (и - количество строк матрицы описаний);

- величина интервала значений признака объекта, представленного строкой матрицы

2. При вычислении весов признаков к каждой компоненте вектор-строки весов признаков добавляется слеллттотттяя величина-

Р. Р, + (6^ + )гуг,кФ <Ьк ¡2 ,

где - разница между минимальными значениями интервалов признака у сравниваемых строк;

- разница между максимальными значениями интервалов признака у сравниваемьж строк;

- номера сравниваемых строк - количество строк

матрицы описаний).

3. Нормировка элементов вектор-строки весов признаков производится по следующей формуле:

/ к=}+\

где - максимальный интервал значений признака; I - номер признака;

у, к - номера строк },к 6 {1,...,и} (и - количество строк матрицы описаний);

Фу- вес _/-й строки; Р, - вес /-Г0 признака.

Также приводятся алгоритмы построения СДТ и принятия решений для матричного представления знаний в пространстве целочисленных признаков, заданных как в константном, так и в интервальном виде.

В пятой главе приводятся сравнительные характеристики алгоритмов построения СДТ и принятия решений и результаты их экспериментальных испытаний в прикладных интеллектуальных системах.

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

Утверждение 2. При принятии решений, осуществляемом при непосредственном построении СДТ, и принятии решения по предварительно построенным СДТ на основе безусловных диагностических тестов количество и последовательность запрашиваемых признаков совпадают.

Исследования проводились на следующих интеллектуальных системах, созданных на основе интеллектуальной системы ЭКСАПРАС, разработанной в лаборатории интеллектуальных систем ТГАСУ под руководством А.Е. Янковской.

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

Для испытаний была выбрана база знаний "Генетические изменения (оценка состояния здоровья ребенка по генетическим и функциональным показателям)".

2. ЭСМЕДИЧ - для принятия оптимальных решений в области медицины чрезвычайных ситуаций, включая постановку диагноза и определение комплекса лечебно-профилактических и сортировочно-эвакуационных мероприятий при оказании медицинской помощи пострадавшим с травмами груди, от лучевых поражений и отравлений сильно действующими ядовитыми веществами (СДЯВ), а также принятие организационно-управленческих решений в очаге поражения.

Для испытаний были выбраны две базы знаний:

а) "Квалифицированная и специализированная помощь при лучевых поражениях";

б) "Организационно-управленческие решения при чрезвычайных ситуациях".

3. Интеллектуальная система оценки научно-технических проектов на предмет целесообразности выделения грантов, а также очередности и объемов их финансирования.

В создании баз знаний для прикладных интеллектуальных систем, на основе которых проводились экспериментальные исследования, представленных в диссертации алгоритмов, принимали участие высококвалифицированные эксперты: Н.Н. Ильинских, Г.Э. Черногорюк, В.Ф. Бурматнов. Базы знаний, применяемые в прикладных интеллектуальных системах, основанных на интеллектуальном инструментальном средстве ЭКСАПРАС, конвертированы для создания прикладных интеллектуальных систем на основе ИИС ИМЛОГ.

Выбранный для исследования алгоритм реализован в ИИС ИМЛОГ.

Для иллюстрации работы алгоритмов принятия решений на основе СДГ приводится пример и таблица, характеризующая порядок и количество запрошенных признаков при принятии решения в базе "Генетические изменения". Для приведенного в примере исследуемого объекта, отношение количества запрашиваемых признаков в процессе принятия решения с использованием безусловных тестов к количеству запрашиваемых признаков при принятии решения с использованием смешанных тестов для данного объекта составило (38:21). При принятии решений на основе построения смешанного диагностического теста без выделения безусловной составляющей аналогичное отношение равно (38:30).

При тестировании алгоритма принятия решений на основе смешанных диагностических тестов было сгенерировано 1000 описаний случайных исследуемых объектов и проведено принятие решений для каждого из них. Исследования проводились на базах знаний, использующих для принятия решений множество безусловных тестов, мощность которого больше 1. Для тестирования брались реальные базы знаний прикладных интеллектуальных систем, разработанных на основе системы ЭКСАПРАС. Результаты тестирования представлены в таблице 1, в которой приняты следующие обозначения:

N - количество тестов;

М- количество обязательных признаков;

- количество характеристических признаков, входящих в каждый минимальный безусловный тест;

- количество признаков, вошедших в объединение множеств признаков, входящих в тесты;

Лср, | - среднее количество признаков, необходимое для принятия решений с использованием смешанных диагностических тестов, для каждого теста;

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

■Лобш, 1 - общее количество признаков, запрошенных для принятия решения по каждому объекту (берется средняя величина) с использованием смешанных диагностических тестов;

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

Таблица 1

Результаты тестирования алгоритма принятия решений непосредственно в процессе построения смешанного диагностического теста на различных базах знаний

Название базы N М Р1 \т Лот. 2 Лобш.1 Лобщ.2

Генетические изменения 146 3 10 38 5,29 5.01 21,39 30.1

Квалифицированная и 41 0 6 13 3,02 3,02 9,25 9,25

специализированная

помощь при лучевых

поражениях

Организационно- 586 9 20 38 12,91 11.45 19,04 24.06

управленческие реше-

ния при чрезвычайных

ситуациях

Оценка научно- 5 16 19 22 9,00 6.01 9 11.35

технических проектов

На основе проведенных экспериментальных исследований были выявлены следующие условия, позволяющие оптимизировать количество и порядок запрошенных признаков,

1. Больший выигрыш достигается, если количество признаков, входящих в объединение безусловных тестов, существенно больше (желательно в несколько раз) среднего количества признаков, входящих в безусловный тест (в этом случае, при принятии решения отсекается большее количество признаков).

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

3. При увеличении количества признаков, входящих в безусловную составляющую, появляется вероятность запроса у пользователя "лишнего" (не участвующего в принятии решения) признака.

4. Скорость работы алгоритмов существенно зависит только от количества смешанных тестов, на основе которых принимается решение.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработан и программно реализован в системе ИМСЛОГ алгоритм принятия решения непосредственно в процессе построения смешанных диагностических тестов на основе безусловных для представления данных и знаний в пространстве троичных признаков.

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

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

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

5. Созданы алгоритмы построения двоичной безызбыточной матрицы импликаций и вычисления весовых коэффициентов признаков при матричном представлении данных и знаний в пространстве целочисленных и номинальных признаков (для константного и интервального задания значений признаков).

6. Проведено тестирование алгоритма принятия решений непосредственно в процессе построения смешанного диагностического теста на 4-х реальных базах данных и знаний.

7. Реализованные алгоритмы внедрены в Сибирском государственном медицинском университете и в Томском медико-генетическом центре "ГЕНЕТИК".

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Янковская А.Е., Гедике А.И., Аметов Р.В., Блейхер А.М., Гергет О.М., Муратова ЕА, Кузоваткин А.Н. Интеллектуальная система ИМСЛОГ// Новые информационные технологии в исследовании дискретных структур. Доклады 3-й Всероссийской конференции с международным участием. -Томск: изд-во СО РАН, 2000. -С. 169-175.

2. Янковская А.Е. Кузоваткин АН. Принятие решений на базе построения целочисленных смешанных диагностических тестов// Научная сессия МИФИ-2002. Сборник научных трудов. - Т. 3. - Москва, 2002. - С. 53-54.

3. Янковская А.Е., Гедике А.И., Аметов Р.В., Кузоваткин А.Н. Принятие и обоснование решений в комплексе интеллектуальных систем// Интеллектуали-

зация обработки информации (ИОИ-2002). Тезисы докладов международной научной конференции. - Симферополь, 2002. - С. 97-98.

4. Янковская А.Е., Кузоваткин А.Н. Построение логических тестов в пространстве к-значных и номинальных признаков в системе распознавания образов// Интеллектуализация обработки информации (И0И-2002). Тезисы докладов международной научной конференции. - Симферополь, 2002. - С. 98-100.

5. Янковская А.Е., Гедике А.И., Аметов Р.В., Кузоваткин А.Н. Технология представления и обработки знаний на базе инструментального средства ИМСЛ0Г-2002// Компьютерная лингвистика и интеллектуальные технологии (Диалог-2002). Труды международного семинара. - Т. 2. - М.: Наука, 2002. - С. 555-567.

6. Янковская А.Е., Кузоваткин А.Н. Алгоритмы построения логических тестов в пространстве k-значных и номинальных признаков в системе распознавания образов// Искусственный интеллект. Украина, Донецк: II.II.III "Наука i освига". - 2002. - № 2. - С 330-337.

7. Кузоваткин А.Н., Янковская А.Е. Интеллектуальная система принятия решений на основе смешанных диагностических тестов// Известия Таганрогского государственного радиотехнического университета. Интеллектуальные САПР. Материалы Междунар. научно-технической конф.. - 2002. - № 3 (26). -С. 5-11.

8. Янковская А.Е., Кузоваткин А.Н. К вопросу минимизации длины смешанного диагностического теста для интеллектуальных распознающих систем// Вторая Международная конференция по проблемам управления. Тезисы докладов. - Т. 1. - М.: Институт проблем управления, 2003. - С. 158.

9. Янковская А.Е., Кузоваткин А.Н. Принятие решений в интеллектуальном инструментальном средстве ИМСЛ0Г-2002 на основе смешанных диагностических тестов// Информационные системы и технологии (ИСТ-2003). Материалы междунар. конференции. - Т. 3. - Новосибирск: изд-во НГТУ, 2003. - С. 182-186.

10. Yankovskaya A.E., KuzovatkinA.N. Approbation of constructing algorithms of mixed diagnostic tests and of real knowledge bases decision-making based on matrix model ofknowledge representation// Proceedings of 6* International Congress on Mathematical Modeling. -Nizhni Novgorod, 2004.

11. Янковская А.Е., Ильинских Н.Н., Черногорюк Г.Э., Кузоваткин А.Н. Результаты исследований алгоритма принятия решений непосредственно в процессе построения смешанных диагностических тестов, реализованного в интеллектуальных биомедицинских системах// Естествознание и гуманизм. Сб. научных трудов. - Т. 1, № 3. - Томск: Издание СибГМУ, 2004. - С. 95-99.

Изд лиц. № 02153от 31.10.03. Подписано в печать 14.01.05 Формат 60x90/16, усл.-печ. л. 1. тираж 100. Заказ № /У

Отпечатано с оригинал-макета в ООП ТГАСУ 634003 , г. Томск, ул. Партизанская, 15.

OS os: уз

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ ПОСТРОЕНИЯ ЛОГИЧЕСКИХ ТЕСТОВ И

ПРИНЯТИЯ РЕШЕНИЙ (ОБЗОР)

1.1. Основные определения и понятия

1.2. Модели представления знаний.

1.3. Методы и алгоритмы построения логических тестов.

1.4. Принятие решений.

1.5. Выводы.

ГЛАВА 2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ,

НЕФОРМАЛЬНЫЕ ОПИСАНИЯ АЛГОРИТМОВ

2.1. Основные определения и понятия

2.2. Коэффициент разделения.

2.3. Неформальное описание алгоритма построения смешанных диагностических тестов и принятия решений.

2.4. Неформальное описание алгоритма принятия решений непосредственно в процессе построения смешанного диагностического теста.

2.5. Выводы.

ГЛАВА 3. АЛГОРИТМЫ ПОСТРОЕНИЯ СМЕШАННЫХ

ДИАГНОСТИЧЕСКИХ ТЕСТОВ И ПРИНЯТИЯ РЕШЕНИЙ ДЛЯ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ В ПРОСТРАНСТВЕ

ТРОИЧНЫХ ПРИЗНАКОВ

-3-. 1'. Модифицированная формула вычисления коэффициента

разделения

3.2. Построение смешанных тестов и принятие решений.

3.3. Алгоритм принятия решений непосредственно в процессе построения смешанного диагностического теста

3.4. Сравнительные характеристики эффективности алгоритмов построения тестов.

3.5. Выводы.

ГЛАВА 4. АЛГОРИТМЫ ПОСТРОЕНИЯ СМЕШАННЫХ

ДИАГНОСТИЧЕСКИХ ТЕСТОВ И ПРИНЯТИЯ РЕШЕНИЙ

ДЛЯ МАТРИЧНОГО ПРЕДСТАВЛЕНИЯ ЗНАНИЙ В

ПРОСТРАНСТВЕ ЦЕЛОЧИСЛЕННЫХ ПРИЗНАКОВ,

ЗАДАННЫХ В КОНСТАНТНОМ И ИНТЕРВАЛЬНОМ ВИДЕ

4.1. Вычисление коэффициента разделения

4.2. Построение безызбыточной матрицы импликаций для представления данных и знаний в пространстве номинальных и целочисленных признаков, заданных в константной форме.

4.3. Построение безызбыточной матрицы импликаций для представления знаний в пространстве целочисленных признаков с интервальным заданием значения признаков

4.4. Алгоритм построения смешанных диагностических тестов и принятия решений для матричного представления знаний в пространстве целочисленных и номинальных признаков.

4.5. Алгоритм принятия решений непосредственно в процессе построения смешанного диагностического теста

4.6. Выводы.

ГЛАВА 5 . СРАВНИТЕЛЬНЫЕ ХАРАКТЕРИСТИКИ АЛГОРИТМОВ

ПОСТРОЕНИЯ СМЕШАННЫХ ТЕСТОВ И ПРИНЯТИЯ

РЕШЕНИЙ И ИХ ЭКСПЕРИМЕНТАЛЬНЫЕ ИСПЫТАНИЯ В

ПРИКЛАДНЫХ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ.

5.1. Сравнительные характеристики алгоритмов построения смешанных диагностических тестов

5.2. Описание прикладных интеллектуальных систем и баз знаний, выбранных для проведения исследований.

5.3. Тестирование и иллюстрация работы алгоритмов для базы знаний "Генетические изменения".

5.4. Результаты тестирования алгоритма принятия решений непосредственно в процессе построения смешанного диагностического теста на различных базах знаний.

5.5. Выводы.

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

Основополагающие результаты в области распознавания образов, искусственного интеллекта и интеллектуальных систем получены Журавлевым Ю.И., Ларичевым О.И., Осиповым Г.С., Поповым Э.В., Поспеловым Г.С., Поспеловым Д.А., Финном В.К. Большой вклад в эти области внесены также Берштейном JI.C., Вагиным В.Н., Гладуном В.П., Еремеевым А.П., Загоруйко Н.Г., Закревским А.Д., Зенкиным А.А., Кобринским Б.А., Кузнецовым О.П., Курейчиком В.М., Лбовым Г.С., Мелиховым А.Н., Нариньяни А.С., Перевер-зевым-Орловым B.C., Печерским Ю.Н., Рудаковым К.В., Рязановым В.В., Стефанюком В.Л., Тарасовым В.Б., Хорошевским В.Ф., Янковской А.Е. и др.

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

Процедуры построения безусловных и условных тестов, используемых для распознавания образов, являются весьма трудоемкими, и их оптимизации уделяется большое внимание в трудах Журавлева Ю.И., Дюковой Е.В., Мош-кова М.Ю., Янковской А.Е. и ряда других ученых.

Таким образом, до сих пор весьма актуальными являются как разработка менее трудоемких алгоритмов тестового распознавания, приводящих к построению "хороших" тестов, то есть, обеспечивающих лучшее качество решений (по простоте решающих правил, точности принимаемых решений и минимизации затрат на их получение), так и создание на базе этих алгоритмов интеллектуальных систем, инвариантных к проблемным областям.

Именно на обеспечение лучшего качества принимаемых решений и направлена диссертационная работа, посвященная алгоритмам построения смешанных диагностических тестов (СДТ) и принятия решений. Обоснования целесообразности применения СДТ в интеллектуальных системах приводятся в работах Янковской А.Е. [56,61-74,77-79,85,89,90].

Актуальность исследований подтверждается поддержкой Российского фонда фундаментальных исследований (проекты: № 98-01-00295 "Логико-вероятностный вывод на основе оптимальных смешанных диагностических тестов, частичной импликации и средств когнитивной графики в интеллектуальных системах"; № 01-01-0772 "Логические тесты, логико-комбинаторно-вероятностный вывод и средства когнитивной графики в интеллектуальной системе"; № 01-01-01050 "Развитие интеллектуальной системы логико-комбинаторного принятия решений, основанной на матричном представлении знаний"; № 04-01-00144 "Технология решения связанных по экспертному заключению задач, основанная на логических тестах и средствах когнитивной графики в интеллектуальной системе", в выполнении которых принимал участие диссертант).

Цель работы. Развитие методов построения СДТ при матричном представлении данных и знаний в пространстве двоичных, троичных, номинальных, целочисленных признаков и реализация этих методов в интеллектуальном инструментальном средстве ИМСЛОГ (ИИС ИМСЛОГ), предназначенном для создания прикладных интеллектуальных систем выявления закономерностей в данных и знаниях и принятия решений для широкого круга проблемных областей.

Для достижения данной цели были поставлены следующие задачи:

1. Для матричного представления данных и знаний в пространстве двоичных, троичных, номинальных, целочисленных признаков разработать алгоритмы построения СДТ и принятия решений на их основе, а также алгоритмы принятия решений непосредственно в процессе построения смешанного диагностического теста в пространстве троичных признаков.

2. Разработать алгоритмы построения безызбыточной двоичной матрицы импликаций (для интервального и константного задания значений целочисленных признаков), задающей различимость объектов из разных образов.

3. Осуществить программную реализацию перечисленных выше алгоритмов в виде программных модулей ИИС ИМСЛОГ.

4. Создать на базе ИИС ИМСЛОГ прикладные интеллектуальные системы для решения задач в следующих областях: "Генетические изменения (оценка состояния здоровья ребенка по генетическим и функциональным показателям)"; "Квалифицированная и специализированная помощь при лучевых поражениях"; "Организационно-управленческие решения при чрезвычайных ситуациях"; "Оценка научно-технических проектов".

Методы исследования. В диссертационной работе применялись методы дискретной математики, распознавания образов, искусственного интеллекта, прикладного и системного программирования.

Положения, выдвигаемые на защиту:

1. Алгоритмы построения смешанных диагностических тестов на базе безусловных и принятия решений на их основе при матричном представлении данных и знаний в пространстве троичных, номинальных и целочисленных признаков.

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

3. Формулы для вычисления коэффициента разделения, используемого в процессе построения дерева смешанного диагностического теста.

4. Алгоритмы построения двоичной безызбыточной матрицы импликаций и вычисления весовых коэффициентов признаков при матричном представлении данных и знаний в пространстве номинальных и целочисленных признаков (для константного и интервального задания значений целочисленных признаков).

5. Реализация в виде программного модуля ИИС ИМСЛОГ алгоритма принятия решений непосредственно в процессе построения смешанных диагностических тестов на основе безусловных при матричном представлении данных и знаний в пространстве троичных признаков.

Научная новизна. Научная новизна содержится в следующих результатах:

1. Разработаны новые алгоритмы построения смешанных тестов при представлении данных и знаний в пространстве троичных, номинальных и целочисленных признаков.

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

3. Получены формулы для вычисления коэффициента разделения, используемого при построении дерева смешанного диагностического теста.

4. Разработаны новые алгоритмы построения безызбыточной двоичной матрицы импликаций, используемой для выявления закономерностей в данных и знаниях в пространстве троичных, номинальных и целочисленных признаков.

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

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

2. Разработан новый алгоритм принятия решения непосредственно в процессе построения смешанного диагностического теста.

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

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

1. Реализация алгоритмов в системах ИМСЛОГ-ГЕНЕТОН и ИМСЛОГ-ЛУЧ позволила существенно сократить количество запрашиваемых признаков и, тем самым, снизить стоимость принятия решений.

2. Использование систем в учебном процессе позволило повысить качество и стимулы обучения студентов.

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

Апробация работы. Основное содержание работы отражено в следующих публикациях:

1. Янковская А.Е., Гедике А.И., Аметов Р.В., Блейхер A.M., Гергет О.М., Муратова Е.А., Кузоваткин А.Н. Интеллектуальная система ИМС ЛОГ// Новые информационные технологии в исследовании дискретных структур. Доклады 3-ей Всероссийской конференции с международным участием. -Томск: Изд-во СО РАН, 2000. - С. 169-175.

2. Янковская А.Е. Кузоваткин А.Н. Принятие решений на базе построения целочисленных смешанных диагностических тестов// Научная сессия МИФИ-2002. Сборник научных трудов. Т. 3. - Москва: Изд-во МИФИ, 2002.-С. 53-54.

3. Янковская А.Е., Гедике А.И., Аметов Р.В., Кузоваткин А.Н. Принятие и обоснование решений в комплексе интеллектуальных систем// Интеллектуализация обработки информации (ИОИ-2002). Тезисы докладов международной научной конференции. - Симферополь: Изд-во Крымского научного центра, 2002. - С. 97-98.

4. Янковская А.Е., Кузоваткин А.Н. Построение логических тестов в пространстве k-значных и номинальных признаков в системе распознавания образов// Интеллектуализация обработки информации (ИОИ-2002). Тезисы докладов международной научной конференции. - Симферополь: Изд-во Крымского научного центра, 2002. - С. 98-100.

5. Янковская А.Е., Гедике А.И., Аметов Р.В., Кузоваткин А.Н. Технология представления и обработки знаний на базе инструментального средства ИМСЛОГ-2002// Компьютерная лингвистика и интеллектуальные технологии (Диалог-2002). Труды международного семинара. Т. 2. - М.: Наука, 2002. - С. 555-567.

6. Янковская А.Е., Кузоваткин А.Н. Алгоритмы построения логических тестов в пространстве k-значных и номинальных признаков в системе распознавания образов// Искусственный интеллект. Украина, Донецк: ТПТТТТ "Наука i освгга". - 2002. - № 2. - С 330-337.

7. Кузоваткин А.Н., Янковская А.Е. Интеллектуальная система принятия решений на основе смешанных диагностических тестов// Известия Таганрогского государственного радиотехнического университета. Интеллектуальные САПР. Материалы Международной научно-технической конференции. - 2002. - № 3(26). - С. 5-11.

8. Янковская А.Е., Кузоваткин А.Н. К вопросу минимизации длины смешанного диагностического теста для интеллектуальных распознающих систем// Вторая Международная конференция по проблемам управления. Тез. докладов. Т. 1. - М.: Институт проблем управления, 2003. - С. 158.

9. Янковская А.Е., Кузоваткин А.Н. Принятие решений в интеллектуальном инструментальном средстве ИМСЛОГ-2002 на основе смешанных диагностических тестов// Информационные системы и технологии (ИСТ-2003). Материалы международной конференции. Т. 3. - Новосибирск: Изд-во НГТУ, 2003.-С. 182-186.

10. Yankovskaya А.Е., KuzovatkinA.N. Approbation of constructing algorithms of mixed diagnostic tests and of real knowledge bases decision-making based on matrix model of knowledge representation// Proceedings of 6th International Congress on Mathematical Modeling. - Nizhni Novgorod, 2004.

В публикациях 1, 3, 5 диссертантом изложены программные реализации алгоритма принятия решений непосредственно в процессе построения смешанного диагностического теста для различных версий системы ИМСЛОГ.

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

В публикации 4 диссертантом приводится формула коэффициента разделения признаков.

В публикации 6 диссертантом изложены алгоритм построения смешанных диагностических тестов и принятия решений и алгоритм принятия решений непосредственно в процесс построения смешанного диагностического теста для матричного представления данных и знаний в пространстве к-значных признаков.

В публикации 7 диссертантом изложены алгоритм построения смешанных диагностических тестов и принятия решений на их основе и алгоритм принятия решений непосредственно в процессе построения смешанного диагностического теста для матричного представления данных и знаний в пространстве троичных признаков.

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

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

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

Основные положения диссертационного исследования достаточно полно отражены в публикациях диссертанта.

Публикации. Основные результаты диссертации были опубликованы в 10 работах, две из которых - журнальные публикации.

Внедрение результатов

Результаты диссертационной работы были внедрены в Сибирском Государственном медицинском университете (г. Томск) и в Томском Медико-генетическом центре "ГЕНЕТИК".

Работа выполнялась в Томском государственном университете и в лаборатории интеллектуальных систем Томского государственного архитектурно-строительного университета.

Достоверность научных положений и выводов, изложенных в диссертации, подтверждается:

1. Доказательствами утверждений об эффективности предложенных алгоритмов построения смешанных диагностических тестов и принятия решений.

2. Проведенными экспериментальными испытаниями алгоритма принятия решений непосредственно в процессе построения смешанных диагностических тестов на базе безусловных.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав и заключения. Объем работы составляет 106 страниц. Список литературы содержит 91 наименование. Краткое содержание работы.

5.5. Выводы

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

1. Больший выигрыш достигается, если количество признаков, входящих в объединение безусловных тестов, существенно больше (желательно в несколько раз) среднего количества признаков, входящих в безусловный тест. В этом случае, при принятии решения отсекается большее количество признаков.

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

3. При увеличении количества признаков, входящих в безусловную составляющую появляется вероятность запроса у пользователя "лишнего" (не участвующие в принятии решения) признака.

4. Скорость работы алгоритмов существенно зависит только от количества смешанных тестов, на основе которых принимается решение.

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

ЗАКЛЮЧЕНИЕ

В процессе выполнения диссертационной работы получены следующие результаты.

1. Разработан и программно реализован в системе ИМСЛОГ алгоритм принятия решения непосредственно в процессе построения смешанных диагностических тестов на основе безусловных для представления данных и знаний в пространстве троичных признаков.

2. Разработаны алгоритмы построения СДТ на базе безусловных тестов и принятия решений на их основе для представления данных и знаний в пространстве троичных, номинальных и целочисленных признаков.

3. Создан алгоритм принятия решения непосредственно в процессе построения СДТ на основе безусловных при представлении данных и знаний в пространстве троичных, номинальных и целочисленных признаков.

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

5. Созданы алгоритмы построения двоичной безызбыточной матрицы импликаций и вычисления весовых коэффициентов признаков при матричном представлении данных и знаний в пространстве целочисленных и номинальных признаков (для константного и интервального задания значений признаков).

6. Проведено тестирование алгоритма принятия решений непосредственно в процессе построения смешанного диагностического теста на 4 реальных базах данных и знаний.

7. Реализованные алгоритмы внедрены в Сибирском государственном медицинском университете и в Томском медико-генетическом центре "ГЕНЕТИК".

1. Агафонов В. Н. Системы, базирующиеся на знаниях: принципы, подходы, инструментальные средства. Новосибирск: НФ ИТМИВТ, 1989. - 60 с.

2. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970. - 383 с.

3. Андерсон Т.В. Введение в многовекторный статистический анализ М.: Физматгиз, 1963. 500 с.

4. Бонгард М.М. Проблема узнавания. Москва.: Наука, 1967. - 320 с.

5. Боровков А.А. Математическая статистика. Новосибирск: Наука, 1997. - 772 с.

6. Вапник В.Н. Алгоритмы обучению распознаванию образов. М.: Сов. Радио, 1973.-200 с.

7. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974.-415 с.

8. Васильев В.И. Распознающие системы. Киев: Наукова думка, 1983.422 с.

9. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб.: Питер, 2000. - 382 с.

10. Гольдман Р.С., Москаленко Ю.С. Исследование вопросов различимости объектов по их признаковым описаниям// Логические методы диагноза. -Владивосток, 1975. С. 76-88.

11. П.Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. Некоторые аспекты. М.: Радио и связь, 1985.

12. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшаяшкола, 1989.-231 с.

13. Гренандер У. Лекции по теории образов: В 3 т. М.: Мир, 1979.

14. Гуревич И.Б., Журавлев Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания// Кибернетика. 1974. - № 3. - С. 16-20.

15. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений// Дискретный анализ. -Новосибирск, 1966.

16. Журавлев Ю. И. Туляганов Ш.Е. Меры важности объектов в сложных системах// Журнал Вычислительной математики и мат. физики. 1972. -Т. 12.-Ко 1.

17. Журавлев Ю.И. Корректные алгебры над множеством некорректных (эвристических) алгоритмов. I-III// Кибернетика. Киев. 1997. - № 4. - С. 14-21; 1977. - № 6. - С. 21-27; 1978. - № 2. - С. 35-43.

18. Журавлев Ю.И. О невозможности построения минимальных нормальных форм функции алгебры логики в одном классе алгоритмов// Докл. АН СССР.- 1960.-Т. З.-С. 132.

19. Журавлев Ю.И., Загоруйко Н.Г. Класс коллективно групповых решающих правил, основанных на дисперсионном критерии компетентности предикторов// Вычислительные системы. Новосибирск. 1998. - Вып. 163.-С. 82-90.

20. Загоруйко Н.Г. Линейные решающие функции, близкие к оптимальным// Вычислительные системы. Новосибирск. 1967. - Вып. 28. - С. 69-79.

21. Загоруйко Н.Г. Методы распознавания и их применения. М.: Сов. Радио, 1972.

22. Искусственный интеллект. В 3-х книгах. Кн. 2. Модели и методы: Справочник/ Под ред. Д.А. Поспелова М.: Радио и связь, 1990. - 304 с.

23. Ковалевский В.А. Корреляционный метод распознавания изображений// Журнал вычислительной математики и мат. физики. 1962. - Т. 2. - № 4. -С. 584-592.

24. Кузнецов И.П. Семантические представления. М.: Наука, 1986. - 290 с.

25. Ларичев О.Г. Теория и методы принятия решений, а также хроника событий в волшебных странах: Учебник. М.: Логос, 2000. - 296 с.

26. Лбов Г.С. Методы обработки разнотипных интеллектуальных данных. — Новосибирск: Наука, 1981. 157 с.

27. Логический подход к искусственному интеллекту: от классической логики к логическому программированию: Пер. с франц./ Тейз А., Гибомон П., Луи Ж. и др. М.: Мир, 1990. - 432 с.

28. Мазуров В.Д. Тягунов Л.И. Метод комитетов в распознавании образов. — Свердловск: изд. Уральск. Отделения АН СССР, 1974. С. 10-40.

29. Мазуров В.Д., Казанцев B.C., Белецкий Н.Г. и др. Вопросы обоснования и применения комитетных алгоритмов распознавания// Распознавание, классификация, прогноз. Математические методы и их применение. М.: Наука, 1989.-Вып. 1.-С. 114-148.

30. Малиновский Л.Г. Классификация объектов средствами дискриминантного анализа. М.: Наука, 1979. - 259 с.

31. Минский М. Фреймы для представления знаний: Пер. с англ. М.: Энергия, 1979.- 150 с.

32. Москаленко Ю.С. Алгоритмические методы построения логических моделей в задачах диагноза естествознания: Автореферат дис. канд. технических наук. Владивосток: ИАПУ, 1977. - 32 с.

33. Орлов В.А. Граф-схемы алгоритмов распознавания (с применением к геофизическим задачам). М.: Наука, 1982. - 120 с.

34. Патрик Э. Основы теории распознавания образов: Пер. с англ. М.: Сов. Радио, 1980.

35. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1998. - 264 с.

36. Попов Э. В. Экспертные системы решение неформализованных задач в диалоге с ЭВМ. М.: Наука, 1987. - 283 с.

37. Попов Э.В. Экспертные системы. М.: Наука, 1987. - 288 с.

38. Поспелов Д.А. Логико-лингвистические модели в системах управления. -М.: Энергоатомиздат, 1981. 232 с.

39. Поспелов Д.А. Моделирование рассуждений. Опыт анализа мыслительных актов. М.: Радио и связь, 1989. - 184 с.

40. Растригин Г.И., Эренштейн Р.Х., Метод коллективного распознавания. -М.: Энергоиздат, 1981. 79 с.

41. Растригин Л.А. Эренштейн Принятие решений коллективом решающих правил в задачах распознавания образов// Изв. АН СССР. Сер. Автоматика и телемеханика. 1975. - № 9. - С. 79-88.

42. Саймон Г. Науки об искусственном. М.: Мир. 1972. - 146 с.

43. Слепян В.А. О числе тупиковых тестов и о мере информативности столбца для почти всех таблиц// ДАН СССР, 1970. Т. 191. - № 1. - С. 35-38.

44. Ту Дж., Гонсалес Р. Принципы распознавания образов: Пер. с англ. М.: Мир, 1978.-411 с.

45. Фомин Я.А., Тарловский Г.Р. Статистическая теория распознавания образов: Пер. с англ. М.: Радио и связь, 1986.

46. Харкевич А.А. Борьба с помехами. М.: Наука, 1965.

47. Чегис И.А., Яблонский С.В. Логические способы контроля электрических схем// Сб. статей по математической логике и ее приложениям к некоторым вопросам кибернетики. Тр. Матем. ин-та им. В.А. Стеклова. — Т. 51.-С. 270-360.

48. Янковская А.Е. К задаче устранения избыточности в матрице кодирования внутренних состояний асинхронного автомата// Автоматизация обработки информации. Томск: Изд-во ТГУ, 1977. - С. 46-51.

49. Янковская А.Е. Оптимизирующие преобразования в процессе синтеза асинхронного автомата и их приложения// МТА SZTAKI TANULMANYOK. BUDAPEST, 99/1980. - С. 212-227.

50. Янковская А.Е. Сокращение числа признаков в распознающих системах// Автоматизированные системы управления хозяйством Томской области. -Томск, 1980.-С. 136-140.

51. Янковская А.Е. Функции различения при анализе БЗ интеллектуальных систем с матричным представлением знаний// Искусственный интеллект 90: Тез. докладов II Всесоюзной конференции - Т. 1. - Минск, 1990. С. 102-105.

52. Янковская А.Е. Представление знаний и алгоритмическое обеспечение для медицины экстремальных ситуаций// Вестник Всесоюзного общества информатики и вычислительной техники. 1991. - № 1. - С. 89-97.

53. Янковская А.Е. Тестовые распознающие медицинские экспертные системы с элементами когнитивной графики// Компьютерная хроника. -1994. № 8/9. - С. 61 -83.

54. Янковская А.Е. Об оптимальном сочетании условных и безусловных диагностических тестов в интеллектуальных системах// Искусственный интеллект 96: Сб. научных трудов V Национальной конференции с международным участием. Т. 1. - Казань, 1996. - С. 77-80.

55. Янковская А.Е. Об оптимальном сочетании условных и безусловных диагностических тестов в интеллектуальных системах// Искусственный интеллект 96. Сб. научных трудов V Национальной конференции с международным участием. Т. 1. - Казань, 1996. - С. 77-80.

56. Янковская А.Е., Гедике А.И., Журкина О.В., Ильинских Н.Н. Интеллектуальная система ГЕНЕТОН// Искусственный интеллект 96.

57. Сб. научных трудов V Национальной конференции с международным участием. Т. 3. Казань, 1996. - С. - 508-512.

58. Интеллектуальная система ИМСЛОГ/ А.Е. Янковская, А.И. Гедике, Р.В. Аметов, A.M. Блейхер, О.М. Гергет, Е.А. Муратова, А.Н. Кузоваткин//

59. Новые информационные технологии в исследовании дискретных структур: Доклады 3-ей Всероссийской конференции с международным участием. Томск: Изд-во СО РАН, 2000. - С. 169-175.

60. Янковская А.Е., Тетенев Ф.Ф., Черногорюк Г.Э. Отражение образных представлений специалиста в интеллектуальной распознающей системе патогенеза заболеваний// Компьютерная хроника. 2000. - № 6. - С. 7792.

61. Янковская А.Е. Основы построения и применения смешанных диагностических тестов в интеллектуальной распознающей системе// Сб. научных трудов сессии МИФИ-2001. М., 2001. - С. 98-99.

62. Янковская А.Е., Кузоваткин А.Н. Принятие решений на базе построения целочисленных смешанных диагностических тестов// Научная сессия МИФИ-2002. Сборник научных трудов. Т. 3. Москва, 2002. - С. 53-54.

63. Янковская А.Е., Кузоваткин А.Н. Алгоритмы построения логических тестов в пространстве k-значных и номинальных признаков в системе распознавания образов// Искусственный интеллект. Украина, Донецк: 1ПШ1 "Наука i освгга". 2002. - № 2. - С 330-337.

64. Янковская А.Е. Синтез смешанных логических тестов на основе ускоренных шагово-циклических алгоритмов спуска// Математические методы распознавания образов (ММРО-11). Доклады 11-й Всероссийской конференции. Москва, 2003. - С. 224-226.

65. Juravlev Yu.I. An algebraic approach to recognition or classification problems// Pattern recognition and Image Analysis. 1998. - No. 8 (10). - P. 59-100.

66. Yankovskaya A.Ye., Gedike A.I. Theoretical Base, Realization and Application of the Intelligent System EXAPRAS// Proceedings East-West Conference on Artificial Intelligence (EWAIC'93). From Theory to Practice. -Moscow, Russia, 1993. P. 248-252.

67. Yankovskaya A.Ye., Gedike A.I. Application of the Intelligent System EXAPRAS for Education// Proceedings of the International Conference on

68. Computer Technologies in Education (ICCTE'93). Ukraine, Kiev, 1993. - P. 168-169.

69. Yankovskaya A.E. An Automaton Model, Fuzzy Logic, and Means of Cognitive Graphics in the Solution of Forecast Problems// Pattern Recognition and Image Analysis. 1998. - Vol. 8, No. 2. - P. 154-156.

70. Yankovskaya A.E., Gedike A.I. Construction and Evaluation of Compressed Descriptions of Patterns in an Intelligent Recognizing System// Pattern Recognition and Image Analysis. 1999. - Vol. 9, No. 1. - P. 124-127.

71. Yankovskaya A., Gedike A. Finding of All Shortest Column Coverings of Large Dimension Boolean Matrices// Proceedings of the First International Workshop on Multi-Architecture Low Power Design (MALOPD). Moscow, 1999.-P. 52-60.

72. Yankovskaya A.E. The Test Pattern Recognition with Genetic Algorithms Use// Proceedings of the Pattern Recognition and Image Understanding. 5th Open German-Russian Workshop. Germany, Herrshing. - 1999. - P. 47-54.

73. Yankovskaya A.E. Logical Tests in Knowledge-Based recognizing system// Pattern Recognition and Image Analysis. 2001. - Vol. 11, No. 1. - P. 127.

74. Yankovskaya A.E. Bleikher A.M. Optimization of tests synthesis on the base of descent algorithms with the use of genetic transformations// Radioelectronics & Informatics. 2003. - No. 3 (24). - P. 51-55.

75. Yankovskaya A.E., Gedike A.I., Ametov R.V., Bleikher A.M. IMSLOG-2002 Software Tool for Supporting Information Technologies of Test Pattern Recognition// Pattern Recognition and Image Analysis. 2003. - Vol. 13. -No. 4. - P. 650-657.