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



(Г ЧЧ- 1 •-

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

Алхасан Муса Мухамед

ДЕРЕВЬЯ РЕШЕНИЙ В ЗАДАЧАХ РАСПОЗНАВАНИЯ ОБРАЗОВ

Специальность 05.13.16. - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель-к.т.н.,доц. Геппенер В.В.

Санкт-Петербург - 1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.............................................................................................7

ГЛАВА 1. АЛГОРИТМЫ РАСПОЗНАВАНИЯ ОБРАЗОВ НА

ОСНОВЕ ДЕРЕВЬЕВ РЕШЕНИЙ...................................13

1.1. Качественное описание задачи распознавания образов......13

1.2. Формальное описание задачи распознавания образов.......16

1.3. Основные задачи распознавания образов.........................19

1.4. Методы построения решающих правил в задачах

распознавания......................................................................28

1.4.1. Статистические методы............................................28

1.4.2. Детерминистский подход.........................................30

1.4.3. Нечеткие методы.......................................................33

1.5. Деревья решений в задачах распознавания образов.......35

1.5.1. Деревья решений на основе логических решающих правил.......................................................38

1.5.2. Метод обучения на основе построения миноров-эталонов и его использования для построения деревьев решений........................................................43

1.5.2.1. Алгоритм обучения..........................................44

1.5.2.2. Представление решающего правила, алгоритма "Геконал" в виде

дерева решения..................................................47

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

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

1.5.5. Обучение на примерах и деревья решений..............62

1.6. Выводы...................................................................................65

ГЛАВА 2. ДЕРЕВЬЯ РЕШЕНИЙ НА ОСНОВЕ

ГРАФ-СХЕМ И ИХ СВОЙСТВА...................................66

2.1. Алгоритм построения..........................................................66

2.2. Граф-схемы на основе бинарных признаков.........................77

2.3. Классифицирующие свойства бинарной граф-схемы...........80

2.4. Распознавание с помощью граф-схем....................................81

2.5. Устранения неопределенности методом расширения

обучающей выборки...........................................................82

2.6. Идея бинаризации признаков...............................................85

2.6.1. Линейно-упорядоченные признаки..........................87

2.6.2. Граф-схема как наилучшее продолжение для случая линейно-упорядоченных признаков..............90

2.6.3. Монотонность граф-схемы.......................................92

2.6.4. Пример построения граф-схемы...............................93

2.6.5. Методы представления признаков при формировании граф-схем...........................................98

2.6.6. Использование деревьев решений на основе граф-схем в задаче автоматического построение базы знаний экспертной системы.............................104

2.7. Выводы..................................................................................106

ГЛАВА 3. НЕЧЕТКИЕ ДЕРЕВЬЯ РЕШЕНИЙ НА ОСНОВЕ

ГРАФ-СХЕМ.....................................................................107

3.1. Нечеткие события, классы и признаки...............................107

3.2. Пространство нечетких признаков......................................111

3.3. Условные вероятности нечетких событий..........................112

3.4. Признаки нечетких событий...............................................113

3.5. Пространство классов..........................................................113

3.6. Задача нечеткого обучения в распознавании

образов..............................................................................115

3.7. Нечеткие граф-схемы............................................................119

3.8. Алгоритм построения нечеткой граф-схемы......................122

3.9. Пример построения нечеткой граф-схемы

возможностей....................................................................124

3.10. Выводы...............................................................................130

ГЛАВА 4. ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ РАБОТЫ С

ДЕРЕВЬЯМИ РЕШЕНИЙ................................................ 131

4.1. Общее описание системы распознавания "GRAF"...........131

4.1.1. Обоснование выбора языка реализации................131

4.1.2. Вопросы реализации...............................................133

4.1.3. Структура системы распознавания образов "GRAF"......................................................................134

4.1.4. Описание модуля CONVERT.................................137

4.1.5. Описание модуля SYSTEM....................................137

4.1.6. Описание модуля GRAPH......................................139

4.1.7. Описание модуля LOGIC........................................141

4.1.8. Работа с программной системы "GRAF"...............141

4.2. Система автоматического приобретения знаний для

экспертной системы "ЭСТЕР" на основе программы

"GRAF"..............................................................................142

4.2.1. Основные характеристики экспертной системы "ЭСТЕР".........................................................................142

4.2.2. Состав инструментальной оболочки ЭС

"ЭСТЕР"...................................................................144

4.2.3. Язык описания базы знаний в системе

"ЭСТЕР"...................................................................145

4.2.4. Простой пример записи базы знаний.....................148

4.2.5. Структура системы автоматического приобретения знаний (автоматической разработки правил) для ЭС "ЭСТЕР"...................149

4.3. Выводы................................................................................154

ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МЕТОДОВ ПОСТРОЕНИЯ ДЕРЕВЬЕВ

РЕШЕНИЙ........................................................................156

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

5.1.1. Артефакты при электроэнцефалографических исследованиях..........................................................156

5.1.2. Описание использованных статистических

данных......................................................................158

5.1.3. Предварительная обработка экспериментальных

данных......................................................................162

5.1.4. Обнаружение феноменов ЭЭГ на основе

описания сигналов спектрами ДПФ.......................165

5.1.5. Эксперименты по автоматической классификации типов феноменов............................167

5.1.6. Эксперименты по классификации феноменов

ЭЭГ с использованием программы "GRAF"........168

5.1.7. Эксперимент по автоматической разработке базы знаний экспертной системы классификации артефактов......................................172

5.2. Применение граф-схем для распознавания

изображения.......................................................................176

5.3. Исследования нечеткого распознавания на модельных примерах...............................................................................185

5.3.1. Построение нечеткой граф-схемы на основе расширенных данных таблицы 4.1..........................185

5.3.2. Модельной пример: нечеткое распознавание качества яблок.........................................................189

5.4. Выводы.................................................................................193

ЗАКЛЮЧЕНИЕ..................................................................................194

СПИСОК ЛИТЕРАТУРЫ................................................................196

ПРИЛОЖЕНИЕ 1....................................................................................203

ВВЕДЕНИЕ

Актуальность темы. В рамках кибернетики во второй половине 50-х годов XX в, начало формироваться новое научное направление, связанное с разработкой теоретических основ и практической реализацией устройств, а затем и систем, предназначенных для распознавания неизвестных объектов, явлений, процессов. Новая научная дисциплина получила название "распознавание образов". Подобное название возникло в связи с тем, что процесс распознавания отождествляется с выявлением вопроса о том, к какому классу объектов (образу) может быть отнесен распознаваемый объект. При этом класс олицетворяет собой некоторую совокупность (подмножество) объектов, обладающих близкими свойствами.

Первая работа в области распознавание образов в России была выполнена одним из основоположников современной теории информации акад. А. А. Харкевичем. Значительный вклад в развитие теории и практики распознавания внесли также отечественные ученые В. М. Глушков, В. С. Михалевич, В. С. Пугачев, Н. П. Бусленко, Ю. И. Журавлев, Я. 3. Цыпкин, А. Г. Ивахненко, М. А. Айзерман, М. М. Бонгард, Э. М. Браверман, В. Н. Вапник, Н. Г. Загоруйко, JI. А. Растригин и др. Из зарубежных ученых следует отметить в первую очередь Ф.Розенблатта, предложившего в 1957 г. машину, обучающуюся распознаванию образов, названную им персептрон (от англ: "to percept"- воспринимать), в качестве простейшей модели деятельности мозга, связанной с распознаванием образов. Кроме того, необходимо назвать видных ученых Р. Гонсалеса, У. Гренандера, Р. Дуда, Г. Себестиана, Дж. Ту, К. Фу, П. Харта, основные работы которых переведены на русский язык.

В настоящее время теория распознавания образов является сложившейся научной дисциплиной охватывающей разнообразные методы решения задач распознавания [24,29,34,45], такие как статистические и синтаксические, методы детерминированного распознавания основанные на геометрических представлениях , логические и алгебраические методы, методы основанные на теории нечетких множеств.

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

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

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

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

ничить количество используемых признаков при распознавании конкретных объектов.

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

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

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

Цель и задачи работы.

Целью работы является:

• исследование методов построения деревьев решений в задачах распознавания образов;

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

• исследования применения деревьев решения в различных прикладных задачах распознавания образов.

В соответствии с указанными целями в диссертации решены следующие задачи:

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

2. Исследованы свойства граф-схем как решающих функций и предложены методы устранения отказов при принятии решений.

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

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

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

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

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

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

В качестве инструментальных средств использовались системы программирования Borland С++ v.4.5, Turbo Pascal v.7.0 , инструментальная оболочка экспертной системы "ЭСТЕР".

Научную новизну работы составляют:

1. Метод построения деревьев решений на основе граф-схемного подхода при детерминированном (четком) задании исходных данных.

2. Способ устранения отказов при использовании деревьев решений путем введения бинаризации признаков.

3. Метод построения граф-схемы для нечетких исходных данных , основанный на сведении к алгоритму построения четкой граф-схемы с выделенным последним слоем, содержащим характеристики нечеткости.

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

Практическая ценность.

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

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

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

Внедрение результатов работы. Работа выполнялась в рамках научно-технической программы "Университеты России" (подраздел 2.3) "Разработка математических методов и инструментальных средств построения нечетких деревьев решений в задачах распознавания образов", гранта РФФИ № 98-01-00578 "Методы визуализации и классификации подповерхностных объектов и структур на основе сверхширокополосного радиолокационного зондирования". Результаты работы были использованы в рамках НИР БФ-43, выполняемой по заказу НИИ Радиоэлектронных средств прогнозирования чрезвычайных ситуаций ("Прогноз") при СПбГЭТУ. Разработанные программные средства использованы в учебном процессе при проведении лабораторных работ по курсу "Системы искусственного интеллекта".

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на научно-технических конференциях СПбГЭТУ в 1996-1998 гг., на втором международном симпозиуме: "Интеллектуальные системы" (ИНТЕЛС'96), Санкт-Петербург 1996, на международной конференции "Biomedical Engineering and Medical Informatics" (BEMI'97) Gliwice Польша 1997, на Третьем международном симпозиуме: "Интеллектуальные системы" (ИНТЕЛС'98), Псков, 1998, на международной конференции по мягким вычислениям и измерениям (SCM - 98): Санкт-Петербург 1998, на Всероссийской конференции "Мониторинг и прогнозирование чрезвычайных ситуаций", Санкт-Петербург, 1998.

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

Глава 1. Алгоритмы распознавания образов на основе деревьев

решений.

1.1. Качественное описание задачи распознавания образов.

Распознавание образов (объектов, сигналов, ситуаций, явлений или процессов)- едва ли не самая распространенная задача, которую человеку приходится решать практически ежесекундно от первого до последнего дня своего существования. Для решения этой задачи человек использует огромные ресурсы своего мозга, включая одновременно около 10-12 млрд. нейронов. Именно это дает возможность людям мгновенно узнавать друг друга, с большой скоростью читать печатные и рукописные тексты, безошибочно водить автомобили в сложном потоке уличного движения, осуществлять отбраковку деталей на конвейере во время движения, дешфрировать аэро- и космические фотоснимки, разгадывать коды, древнюю египетскую клинопись и т. д.

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

Потребности в комплексной механизации и автоматизации производства, создании роботов, в необход�