Разработка и исследование генетических алгоритмов обучения в моделях вычисления оценок (стр. 3 )

Количество ошибок распознавания После применения решающих правил
Класс :	1	2	3	4	5	6	7	отказы
Ошибки (РП1)	2	1	11	22	15	1	7	0
Ошибки (РП2)	26	6	12	18	9	1	4	6
Всего ошибок (РП1):	59
Всего ошибок (РП2):	76

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

В четвертой главе рассматриваются детали имплементации разработанных алгоритмов. Разработанные в диссертационном исследовании алгоритмы и методы были реализованы автором в программном комплексе «Genesis» на языке Fortran-90, а также в качестве модуля к программному комплексу «Recognition» на языке Visual C++ 6.0. Первый программный комплекс «Genesis» содержит возможность задания пользователем типов генетических операторов, различных параметров ГА и решающих правил. Фактически, пользователь программы может с помощью набора входных файлов полностью определять структуру генетического алгоритма. Второй программный комплекс содержит, наряду с изложенным в работе методом, другие методы распознавания, прогнозирования и кластеризации, а также имеет графический интерфейс, через который можно задавать входные данные – набор параметров обучения и распознавания, а также обучающую и контрольную выборки. На рис 2 представлено окно задания параметров обучения для модуля Genesis программного комплекса «Recognition». Сам программный комплекс «Recognition» был представлен на многих отечественных и международных конференциях, а также применяется в учебном процессе кафедры информатики Московского физико-технического института.

Рис. 2 Задание параметров для этапа обучения в модуле Genesis программного комплекса «Recognition».

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

(4.1)

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

(4.2)

При это выражение дает операций, то есть порядка 1 секунды расчета на современном мощном ПК. При формула даст уже около 30 секунд расчета, при расчет займет около 15 минут, при - 7.5 часов и т. д. Для задач с , близких к единице, рост затрат машинного времени будет существенно большим. Кроме того, данные оценки занижены в 2-5 раз, так как каждая из элементарных процедур, количество которых оценивает формула (4.2), на самом деле содержит несколько вычислительных операций.

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

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

(4.3)

Для больших выборок использование этого метода дает многократное ускорение без какого-либо существенного ухудшения качества распознавания. В качестве примера была рассмотрена прикладная задача распознавания для космической техники, в обучающей выборке которой было 43500 объектов. Процесс обучения занял 44 минуты, а результаты распознавания попали в диапазон, заданный авторами таблицы.

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

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

· Алгоритм вычисления оценок

· Двумерные линейные разделители

· Линейный дискриминант Фишера

· Линейная машина

· Логические закономерности

· Многослойный перцептрон

· Q ближайших соседей

· Метод опорных векторов

· Статистически взвешенные синдромы

· Голосование по тупиковым тестам

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

Также было проведено исследование задачи прогнозирования кристаллической решетки химических соединений. В ходе исследования были удалены несущественные признаки задачи, также задача была разбита на 2 независимые составляющие – прогнозирование существования химического соединения и прогнозирование кристаллической решетки соединения при условии, что данное соединение существует. После удаления малозначимых признаков общее количество признаков задачи составило 30, число классов (типов кристаллической решетки) – 11. На предоставленных обучающей и контрольной выборках с помощью разработанного метода были получены высокие результаты, имеющие практическую ценность.

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

	Ошибочно отнесено в класс
Метод	1	2	Всего	В процентах
АВО	16	28	44	19.1%
ДЛР	32	10	42	18.3%
Дискриминант Фишера	26	28	45	23.5%
Линейная машина	18	15	33	14.3%
Логические закономерности	30	10	40	17.4%
Перцептрон	21	27	48	20.9%
Q ближайших соседей	28	11	39	17.0%
Метод опорных векторов	16	18	34	14.8%
СВС	35	6	41	17.8%
Тупиковые тесты	32	24	56	24.3%
Генетический метод	18	11	29	12.6%

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

	Ошибочно отнесено в класс
Метод	1	2	3	4	5	6	7	8	9	10	11	S	%
АВО	1	1	11	4	1	0	0	0	5	0	9	32	26.4
ДЛР	0	0	9	5	0	25	0	7	7	0	0	53	43.8
Дискриминант Фишера	0	0	25	18	0	0	0	0	5	0	0	48	39.7
Линейная машина	1	0	12	8	1	1	1	1	11	2	2	40	33.1
Логические закономерности	6	3	2	5	4	2	1	1	9	4	15	52	43
Перцептрон	0	0	26	1	0	6	0	4	0	0	20	57	47.1
Q ближайших соседей	1	0	0	5	1	0	2	1	15	1	6	32	26.4
Метод опорных векторов	1	0	8	2	0	0	1	0	11	1	3	27	22.3
СВС	1	1	1	4	2	3	0	0	9	14	11	46	38
Тупиковые тесты	0	4	9	0	10	3	0	1	0	10	16	53	46.8
Генетический метод	0	0	14	8	1	1	0	0	7	0	3	34	28

Таблица 3: прогнозирование кристаллической решетки химических соединений.

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

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

Основные результаты работы

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

2. Для предложенной модели разработаны генетические алгоритмы поиска экстремумов критерия оптимальности. В частности, разработан новый «кластерный» метод кроссовера, учитывающий взаимное расположение объектов классов.

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

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

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

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

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

Список публикаций по теме диссертации

1. , Генетический алгоритм поиска логических закономерностей по прецедентам для решения задач распознавания // Доклады 11-ой Всероссийской конференции «Математические методы распознавания образов» – М. – 2003, С. 106-108.

2. Kovshov, N. V. Moiseev, V. A. Ryazanov, V. V. Algorithms for Detecting Logical Dependences in Recognition by Precedents // Pattern Recognition and Image Analysis – 2005 – Vol.15, Part 1, P. 65-68.

3. Kovshov, N. V. Moiseev, V. A. Ryazanov, V. V. Algorithms for logical regularities search in supervised classification by precedents // Special Issue Proceedings of PRIA-7-2004 7th International Conference on Pattern Recognition and Image Analysis: New Information Technologies St. Petersburg, Russian Federation, October 18–22, Part I – 2004 – P. 65-69.

4. , , Математическое моделирование работы вычислительных сетей, использующих протоколы TCP и UDP // Современные проблемы фундаментальных и прикладных наук: Труды XLVIII научной конференции. – М.:МФТИ – 2005 – С. 30-32.

5. , Сетевая вычислительная модель интенсивных информационных потоков // Доклады конференции «Технологии Microsoft в теории и практике программирования» – М.: Ин-т. им. Баумана – 2005 – C. 96-97.

6. В. Расчет приливной волны (бора) в речных дельтах посредством одномерной модели на графах // Современные проблемы фундаментальных и прикладных наук: Труды 49 научной конференции МФТИ – М.: МФТИ – 2006 – С. 295-297.

7. Kovshov N. V., Ryazanov V. V. About One Approach for Detecting Logical Dependencies in Recognition by Precedents Based on the Genetic Algorithm // Proceedings of the 6th WSEAS International Conference on Applied Computer Science, Tenerife, Canary Islands, Spain – 2006 – P. 25-28.

8. Kovshov N. V., Ryazanov V. V. About One Approach for Detecting Logical Dependencies in Recognition by Precedents Based on the Genetic Algorithm // WSEAS transactions on computer research – 2006 – Issue 2, Vol.1 – P. 152-155.

Разработка и исследование генетических алгоритмов обучения

в моделях вычисления оценок

Автореферат

Подписано в печать 06.09.07 Формат 60x84 1/16. Печать офсетная.

Усл. печ. Л. 1,0. Уч.-изд. Л. 1,0. Тираж 80 экз. Заказ №ф-245

Государственное образовательное учреждение

высшего профессионального образования

Московский физико-технический институт

(государственный университет)

Отдел автоматизированных издательских систем

«ФИЗТЕХ-ПОЛИГРАФ»

Московская обл., г. Долгопрудный, Институтский пер., 9