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

Актуальность темы

В рамках кибернетики во второй половине 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−578 «Методы визуализации и классификации подповерхностных объектов и структур на основе сверхширокополосного радиолокационного зондирования». Результаты работы были использованы в рамках НИР БФ-43, выполняемой по заказу НИИ Радиоэлектронных средств прогнозирования чрезвычайных ситуаций («Прогноз») при СПбГЭТУ. Разработанные программные средства использованы в учебном процессе при проведении лабораторных работ по курсу «Системы искусственного интеллекта» .

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

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

5.4. Выводы.

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

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

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

ЗЛ КЛЮЧЕЙ НЕ.

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

Основные научные и практические результаты работы можно сформулировать следующим образом:

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

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

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

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

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

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

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

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

По материалам работы опубликованы 7 печатных и 1 депонированная работа, подготовлены доклады на 8-и научно-технических конференциях и семинарах.

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