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

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

Ковшов Николай Вадимович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ОБУЧЕНИЯ В МОДЕЛЯХ ВЫЧИСЛЕНИЯ ОЦЕНОК

специальность 05.13.18

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических

наук

□ОЗ 1Б8Б"75

Москва-2007

003158575

Работа выполнена на кафедре вычислительной математики Московского физико-технического института (государственного университета)

Научный руководитель

доктор физико-математических наук, член-корреспондент РАН, профессор Холодов Александр Сергееви"

Официальные оппоненты

доктор физико-математических наук Обухов Юрий Владимирович

кандидат физико-математических наук Виноградов Александр Петрович

Ведущая организация

Факультет вычислительной математики и кибернетики Московского государственного университета имени М В Ломоносова (ВМК МГУ)

Защита состоится «Лэ » октября 2007 г. в часов на заседании диссертационного совета К 212 156.02 при Московском физико-техническом институте (государственном университете), по адресу 141700, Московская область, г Долгопрудный, Институтский пер , д 9, ауд 903 KLM

С диссертацией можно ознакомиться в библиотеке МФТИ

Автореферат разослан « сентября 2007 г

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

Федько О С

Общая характеристика работы

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

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

Цель работы

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

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

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

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

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

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

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

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

5. Разработаны новые типы оценок объекта за классы и построены решающие правила для этих оценок.

Публикации

Результаты диссертации опубликованы в [1-8], работа [2] - из списка изданий, рекомендованных ВАК РФ. В совместных работах автору принадлежит разработка и исследование математических моделей обучения и распознавания по прецедентам, модификации генетического алгоритма, а также их программная реализация и тестирование

Апробация

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

• Математические Методы Распознавания Образов ММРО-11 (Пущино 2003),

• 7th International Conference on Pattern Recognition and Image Analysis PRIA-7 (St. Petersburg, Russian Federation 2004),

• Научные конференции МФТИ (Долгопрудный, 2005-2006),

• Технологии Microsoft в теории и практике программирования (Москва, 2005),

• 6th WSEAS Int Conf. on Applied Computer Science ACS06 (Tenenfe, Canary Islands, Spain 2006),

• Научные семинары кафедр вычислительной математики и информатики МФТИ (Долгопрудный, 2003-2007),

• Научные семинары отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного центра РАН (Москва, 2004-2007).

Структура и объем диссертации

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

Краткое содержание работы

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

В первой главе приводится общая постановка рассматриваемой задачи Предполагается, что исследуемое множество объектов (ситуаций, процессов, событий или явлений) М представимо в виде объединения / подмножеств

К1, называемых классами. М. Задана начальная информация 10 о

классах и описание /(5) произвольного объекта £ из М Требуется по

информации /0 и /(5) для г =1,2,...,/ определить значения свойств

- характеристик принадлежности объекта классу Предполагается, что описания объектов /(5) определяются наборами значений р числовых

признаков [хх,х2а начальная информация /0 (обучающая, эталонная

информация) задается выборкой описаний £/(|У1),/(5,2),...,/(5')Я)], где

/(5) = (х,(5),х2(5) хДЗ)), в виде числовой таблицы Трт1, в которой

представлены объекты всех / классов с известным распределением их по классам

Задача распознавания произвольного объекта 5 некоторым алгоритмом распознавания Аг записывается в следующем виде

Аг^,1{8)) = аЛ,аА=(а^а^, /(5))6{0,1,А} Здесь

• а^ =1 соответствует отнесению объекта в класс К1

• а* = 1 - решению 5 е К,

• а* -1 - отказу от распознавания данного объекта

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

Здесь -оо <с^<с2 <оо,^=1,2,.., п, - параметры предикатов Определение Предикат

(1 1)

называется допустимым для класса , если

Р(с\с2,8,) = 1

Предикат называется логической закономерностью класса К, если

3Б,еКл Р(с1,с2,5'/)=1 У8,£Ка^Р(С1,С2,5,) = 0 (13)

где ^(-Р) - критерий оптимальности предиката Критерий

Р^сКс^х))^, .Б,еКл,Р(с\с\Б,)=1}\ (1.1)

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

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

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

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

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

- Принцип построения покрытия класса Кх признаковыми интервалами (предикатами), в том числе определение критерия оптимальности для предикатов

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

- Принцип вычисления оценок

- Применение решающих правил

Пусть фиксирован некоторый класс, содержащий Ык обучающих объектов Предлагается рассматривать предикаты определенного типа, а именно предикаты, которым соответствуют признаковые интервалы минимального объема, содержащие при этом некоторый фиксированный (свой для каждого предиката) набор объектов Устанавливается взаимное соответствие между предикатами данного типа и бинарными векторами

длины Л^ При этом каждому предикату будет соответствовать бинарный вектор, в котором на 1-й позиции будет стоят «1», если объект находится внутри соответствующего признакового интервала и «О», иначе Рис 1-а, 1-6 и комментарий к ним иллюстрируют принцип создания и кодирования предикатов, а также показывают, что установленное соответствие не является взаимно однозначным

Рис 1-а Рис 1-6

Рис. 1-а, 1-6 иллюстрация принципа построения и кодирования предикатов. Точками обозначены объекты рассматриваемого класса, крестиками -объекты остальных классов На рис 1-6 изображены объекты двух классов, причем объекты первого класса пронумерованы Изображенному на рис 1-6 предикату будет соответствовать бинарный вектор (limo), а сам изображенный предикат будет соответствовать векторам (llllio), (llOUO), (шою), (иоою).

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

p(P,(cV2,;t)) = |{Sy -.Sj&K^PXc1 ,С2,57) = 1}|,если

3}:У1<1^Р,(с\с2,3,)=Ъ P¡(é,c2,Sj) = 0,uHü4e (1.5)

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

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

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

Кодирование хромосом генетического алгоритма осуществляется согласно принципу, обозначенному в главе 1 Хромосомами представлены проекции предикатов на множество бинарных векторов фиксированной длины Гены хромосом соответствуют объектам обучающей выборки Целевая функция ГА соответствует критерию оптимальности (1.4).

Задача поиска оптимального предиката в признаковом пространстве с ЦФ вида (14) обладает несколькими характерными особенностями, требующими особого подхода к получению решения Среди характерных особенностей задачи следует отметить

1) Сильное взаимное влияние генов друг на друга. Наличие или отсутствие некоторого гена может отличать лучшую хромосому популяции от хромосомы с нулевой ЦФ

2) Сравнительно малое число хромосом ГА, на которых ЦФ отлична от нуля Для подавляющего большинства задач общее количество хромосом с нулевым значением ЦФ будет многократно превышать количество хромосом с ненулевой ЦФ

3) Большое количество локальных экстремумов задачи

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

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

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

(2.1)

Далее для сравнения приводятся результаты, полученные методом простого перебора на выборках небольшого (N<25) размера Сравнительный анализ показывает, что формула (2 1) хорошо описывает поведение числа локальных экстремумов задачи, хотя и является несколько заниженной

Количество признаков р Количество объектов N

5 10 16 24 50 100

2 22 5.1 10.8 18 47 100

5 1 8 5 1 24.4 52 873 4324

10 1 2 3.4 18.8 109 4394 9.1е+5

15 1 2.1 8.4 69 5624 1.1е+7

25 1 12 3.2 20 5139 3.6е+7

50 1 1 1.1 3 698 3.1е+7

100 1 1 1 1 10 5 Зе+5

Таблица 1 Зависимость значения теоретической оценки количества локальных экстремумов от параметров N к р В ячейках таблицы -значения, полученные по формуле (2.1).

Количество признаков р Количество объектов N

5 10 16 24

2 3,1,3 5,7,8 15,9,9 19,19,21

5 3,5,1 9,5,4 33, 34, 24 89,75,114

10 1,1,1 4,5,4 37,14,50 307,241,144

15 1,1,1 1,1,3 7,1,10 149,115,295

25 1,1,1 1,1,1 1,3,1 8,31,16

50 1,1,1 1,1,1 1,1,1 1,1,1

Таблица 2 Значения экспериментального количества локальных экстремумов при различных параметрах N и р В каждой из ячеек таблицы содержатся 3 значения, полученные в трех независимых запусках (на трех различных случайно сгенерированных выборках).

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

показало надежность данного метода кроссовера и его преимущество перед другими, классическими схемами

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

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

Глава 3 содержит описание алгоритма распознавания. Результатом процесса обучения на обучающей выборке является построение покрытий классов некоторым набором допустимых предикатов Р, (Э). Процесс распознавания некоторого нового объекта Я, чья принадлежность тому или иному классу неизвестна, сводится в простейшем случае к процедуре взвешенного голосования по предикатам В рамках данной процедуры вначале вычисляются оценки предиката за каждый из классов задачи С?, =£^/>'(5), где р\ - некоторые параметры После расчета оценок за 1

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

1

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

Первый из методов назван оценкой «по принадлежности снаружи»

В рамках данного метода рассчитывается оценка б,2 = ')

1

Здесь предикат />', определяется следующим образом

РЖ,с\х) = &Р(с[,с1,хк),к = \2, ,п

к

я.)

(3 1)

к

Функция й(Р') определяется следующим образом: о(Р')=1, если предикат Р' является допустимым для класса К' и й(Р')=0 в противном случае

На практике приведенные формулы означают следующее Строится, соответствующий признаковой окрестности минимального объема, который одновременно содержит внутри себя объект 5 и предикат Р) В случае, если построенный предикат Р']3 является допустимым для класса К', полагаем, что объект 5 принадлежит предикату Р^ «снаружи» Общая оценка за класс для объекта складывается из значений всех предикатов класса.

Второй из методов получения оценки объекта за класс назван оценкой «по частичной принадлежности». Он может быть сформулирован следующим образом.

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

2 5

количества признаков следует брать в пределах -п<5<-п При меньших

3 6

значениях порога качество распознавания несколько ухудшается, а при больших существует опасность потерять «уникальность» данной оценки, так как она практически повторяет «каноническую» оценку (3.1), переходя в нее при 8 = п-\

Пусть имеются 3 оценки в],в?,О} , полученные разными методами -традиционной оценкой, оценкой «по принадлежности снаружи», оценкой «по частичной принадлежности» Предлагается использование двух различных решающих правил, из которых следует отнесение объекта к тому или иному классу

(3 2)

где функция Н определяется

некоторое

Решающее правило 1 Суть первого правила заключается в сравнении результатов голосования для трех типов оценок и выборе из них наиболее достоверного результата исходя из априори заданного порядка приоритетности оценок Пусть методом голосования получены номера классов, к которым относят объект оценки трех различных типов - G\G2,G} Результирующая оценка G(S) выводится из трех полученных оценок согласно следующему решающему правилу.

- Если голосование по оценкам двух типов относит объект к некоторому классу, объект следует отнести к этому классу

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

- Если все 3 метода дали отказ от распознавания, алгоритм дает отказ от распознавания

Наилучшим порядком приоритетности предлагается считать G\G3,G2 в порядке убывания

Решающее правило 2 Второй вариант построения решающего правила заключается в голосовании по взвешенным суммам трех оценок Пусть для некоторого объекта получены значения оценок трех типов за разные классы G],Gf,G' Нормализуем оценки таким образом, чтобы сделать их сравнимыми, то есть так, чтобы границы всех оценок лежали на отрезке [0,1]. Для оценок G',Gf2 введем значения коэффициентов р\=Мп,, а для оценки Gf G3

положим G] = —— Окончательная оценка за класс является в общем случае п-8

взвешенной суммой трех нормализованных оценок

(з.з)

».1

В дальнейшем, принятие решения относительно того, к какому классу отнести объект, производится посредством простого голосования по оценкам объекта за классы Gi (S) Если не указано обратного, полагается, что а* = 1.

Ниже приводится пример, иллюстрирующий улучшение качества распознавания, достигаемое введением решающих правил, учитывающих оценки разных типов. Итоговое количество ошибок получается значительно меньшим, чем количество ошибок, полученное по каждой отдельно взятой оценке В качестве тестовой задачи взята прикладная задача распознавания сегментированного изображения В задаче 7 классов, соответствующих следующим объектам, кирпичная кладка, листва, небо, бетон, окно, грунтовая дорога, трава В каждом из классов контрольной и обучающей выборки по 150 объектов Объекты описываются 18-ю вещественнозначными признаками.

Голосование по оценке С

Отнесено в класс. 1 2 3 4 5 6 7 отказы

Из класса 1 133 0 0 0 0 0 0 17

Из класса 2 0 129 0 1 0 0 0 20

Из класса 3 0 0 117 8 11 0 1 13

Из класса 4 0 0 1 135 1 0 1 12

Из класса 5 0 0 3 1 134 0 2 10

Из класса 6 0 0 0 0 0 142 0 8

Из класса 7 0 0 1 2 0 0 137 10

Ошибочно отнесено 0 0 5 12 12 0 4 90

Голосование по оценке йг

Отнесено в класс. 1 2 3 4 5 6 7 отказы

Из класса 1 63 0 0 0 0 0 0 87

Из класса 2 0 133 0 0 0 0 0 17

Из класса 3 26 2 95 12 8 0 2 5

Из класса 4 17 7 1 115 0 5 1 4

Из класса 5 29 0 2 0 114 1 0 4

Из класса 6 0 0 0 0 0 149 0 1

Из класса 7 7 0 0 0 0 0 106 37

Ошибочно отнесено 79 9 3 12 8 6 3 155

Голосование по оценке в3

Отнесено в класс: 1 2 3 4 5 6 7 отказы

Из класса 1 146 1 0 1 1 0 0 1

Из класса 2 0 146 0 4 0 0 0 0

Из класса 3 1 1 109 20 9 0 7 3

Из класса 4 0 1 2 143 0 0 4 0

Из класса 5 0 0 13 2 131 0 2 2

Из класса 6 0 0 0 0 0 150 0 0

Из класса 7 0 0 1 9 0 0 140 0

Ошибочно отнесено 1 3 16 36 10 0 13 6

Итого, первой оценкой допущена 121 ошибка, второй оценкой допущено 120 ошибок и третьей оценкой допущено 85 ошибок

Количество ошибок распознавания После применения решающих правил

Класс 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 С++ 6.0 Первый программный комплекс «Genesis» содержит возможность задания пользователем типов генетических операторов, различных параметров ГА и решающих правил Фактически, пользователь программы может с помощью набора входных файлов полностью определять структуру генетического алгоритма Второй программный комплекс содержит, наряду с изложенным в работе методом, другие методы распознавания, прогнозирования и кластеризации, а также имеет графический интерфейс, через который можно задавать входные данные — набор параметров обучения и распознавания, а также обучающую и контрольную выборки. На рис 2 представлено окно задания параметров обучения для модуля Genesis программного комплекса «Recognition». Сам программный комплекс «Recognition» был представлен на многих отечественных и международных конференциях, а также применяется в учебном процессе кафедры информатики Московского физико-технического института

Генетический метод

- Множитель размера популяции-

Множитель мутации ¡2 500 Множитель размера популящм |р Б00 Количество шагов генезиса без улучшения [ЭО Максимальное количество шагов генезиса |150

-Параметры гпогаблиц--

Г" Использовать разбиеже таблицы обучен« (для больших выборок) Повторять разбение. раз |ю

Объектов в постаблице |5Q

- Скользящий контроль-

Г" Производить скользяща контроль Процент деления (0<«к <»0.5) |0.50

г Уровень значимости доверительного интервала-

Г S9X С 95« Г 902

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

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

Т = О jl5(Oy2+a[]p[/a j (41)

где параметр 0<а<1 зависит от «сложности» задачи и равен отношению количества предикатов, составляющих покрытие класса, к количеству объектов в классе Положив наиболее характерные значения параметров а =1/2,1 =10,/7=50, можно получить следующую оценку

Т' = 0(2500(Ш25) (4 2)

При jV=100 это выражение дает Г' = 2.5*109 операций, то есть порядка 1 секунды расчета на современном мощном ПК При ¿V=400 формула даст уже около 30 секунд расчета, при TV=1600 расчет займет около 15 минут, при N = 6400 -75 часов и т д Для задач с а, близких к единице, рост затрат машинного времени будет существенно большим. Кроме того, данные оценки занижены в 2-5 раз, так как каждая из

элементарных процедур, количество которых оценивает формула (4 2), на самом деле содержит несколько вычислительных операций

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

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

= In М

1-ехр

1-7

N

,-Iln

1 -п

N

=hn М

N

1-

■ч)

(4 3)

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

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

оценка количества машинных операции

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

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

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

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

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

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

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

• О ближайших соседей

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

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

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

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

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

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

Ошибочно отнесено в класс

Метод 1 2 Всего В процентах

ABO 16 28 44 19 1%

ДЛР 32 10 42 18 3%

Дискриминант Фишера 26 28 45 23 5%

Линейная машина 18 15 33 143%

Логические закономерности 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 I %

ABO / 1 11 4 1 0 0 0 5 0 9 32 264

ЦАР 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 331

Логические закономерности б 3 2 5 4 2 1 1 9 4 15 52 43

Перцегпрон 0 0 26 1 0 6 0 4 0 0 20 57 471

Q ближайших соседей I 0 0 5 / 0 2 1 15 1 6 32 264

Метод опорных векторов 1 0 8 2 0 0 1 0 и 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 прогнозирование кристаллической решетки химических соединений

Разработанный метод дал наилучшие результаты при решении первой части задачи При решении второй части задачи результаты метода несколько уступают результатам, полученным с помощью метода вычисления оценок, метода О ближайших соседей и метода опорных векторов, при этом дополняя их в области 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 m 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 Северов Д С, Ковшов H В, Миненко МИ Математическое моделирование работы вычислительных сетей, использующих протоколы TCP и UDP // Современные проблемы фундаментальных и прикладных наук. Труды XLVIII научной конференции - М -МФТИ - 2005 - С. 30-32.

5. Ковшов НВ, Миненко МИ Сетевая вычислительная модель интенсивных информационных потоков // Доклады конференции «Технологии Microsoft в теории и практике программирования» - М • Ин-т им Баумана - 2005 -С. 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, Tenenfe, Canary Islands, Spam - 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. 152155

Ковшов Николай Вадимович

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

Автореферат

Подписано в печать 06 09 07 Формат 60x84 1/16 Печать офсетная Уел печ Л 1,0 Уч-изд Л 1,0. Тираж 80 экз Заказ №ф-335

Государственное образовательное учреждение высшего профессионального образования

Московский физико-технический институт (государственный университет) Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ» 141700, Московская обл , г Долгопрудный, Институтский пер , 9

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ И МЕТОД

КОДИРОВАНИЯ ПРЕДИКАТОВ.

1.1. Общая постановка задачи.

1.1.1. Общая формулировка.

1.1.2. Структура алгоритма распознавания.

1.2.0бщий принцип кодирования предикатов.

1.3.Создание покрытия класса и критерий оптимальности.

1.4.Обработка неизвестных значений признаков.

1.4.1. Осторожный подход.

1.4.2. Жадный подход.

1.5.Расширение границ предиката.

2.1.1. Оператор селекции.29

2.1.2. Оператор кроссовера.31

2.1.3. Оператор мутации.33

2.1.4. Оператор отбора.33

2.1.5. Старт и завершение ГА.34

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

2.2.Применение ГА к решению поставленной задачи.39

2.3.Фундаментальная теорема ГА.40

2.4.Исследование характерных особенностей задачи.45

2.4.1. Оценка количества локальных экстремумов задачи.46

2.5.Исследование операторов ГА и их применимости при решении поставленной задачи.51

2.5.1. Оператор кроссовера.52

2.5.1.1. Вероятность сохранения шаблона.53

2.5.1.2. Метод кроссовера, учитывающий взаимное расположение объектов обучающей выборки.55

2.5.1.3. Экспериментальное сравнение различных механизмов кроссовера.58

2.5.2. Размер популяции.62

2.5.3. Вероятность мутации.63

2.5.4. Критерий остановки ГА.63

2.5.4.1. ЭСС-критерий остановки ГА.66

2.5.4.2. Экспериментальное подтверждение адекватности авторского критерия остановки.66

2.6.Основные результаты и выводы по главе 2.74

ГЛАВА 3. ОПИСАНИЕ АЛГОРИТМА РАСПОЗНАВАНИЯ.76

3.1.Вычисление оценок за классы.76

3.1.1. Вычисление оценок «по принадлежности снаружи».77

3.1.2. Вычисление оценок «по частичной принадлежности.78

3.1.2.1. Роль порогового значения.78

3.2.Решающее правило.79

3.2.1. Решающее правило 1.79

3.2.2. Решающее правило 2.79

3.2.3. Тестирование РП1 на задачах распознавания.80

3.2.4. Тестирование РП2 на задачах распознавания.86

3.2.5. Сравнительный анализ РП1 и РП2.87

3.3.Основные результаты и выводы по главе 3.88

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ И ОПТИМИЗАЦИЯ ЗАТРАТ МАШИННОГО ВРЕМЕНИ. ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ.89

4.1. Программная реализация.89

4.2. Оценка сложности алгоритмов.93

4.2.1. Оценка вычислительной сложности обучения.94

4.2.1.1. Экспериментальное подтверждение оценки сложности обучения.99

4.2.2. Оценка вычислительной сложности распознавания.101

4.3.Метод дробления выборки.102

4.4. Основные результаты и выводы по главе 4.105

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

5.1.Тестовые задачи.106

5.1.1. Модельная задача 1.106

5.1.2. Модельная задача 2.107

5.1.3. Модельная задача 3.108

5.1.4. Опознавание кредитных карт.109

5.1.5. Распознавание радиосигналов.110

5.1.6. Распознавание фоновых изображений.110

5.1.7. Диагностика космической техники.111

5.1.8. Распознавание сортов вин.111

5.1.9. Распознавание изображений автомобилей.112

5.1.10. Диагностика рака груди.112

5.2.Сравнение с другими методами.113

5.2.1. Перечень методов для сравнения.113

5.2.2. Результаты вычислений.116

5.2.3. Модельная задача 2.116

5.2.4. Модельная задача 3.118

5.2.5. Прочие прикладные задачи.119

5.2.6. Прогнозирование типа кристаллической решетки неорганических соединений.121

5.3.0сновные результаты и выводы по главе 5.122

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.128

ВВЕДЕНИЕ

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

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

В течение достаточно продолжительного времени проблема распознавания привлекала внимание специалистов в области прикладной математики, а затем и информатики. Так можно, в частности, отметить работы Р.Фишера, выполненные в 20-х годах и приведшие к формированию дискриминантного анализа, как одного из разделов теории и практики распознавания. В 40-х годах А.Н.Колмогоровым и А.Я.Хинчиным поставлена задача о разделении смеси двух распределений. Наиболее плодотворными явились 50-60-е годы XX века. В это время на основе массы работ появилась теория статистических решений. В результате были найдены алгоритмы, обеспечивающие отнесение нового объекта к одному из заданных классов, что явилось началом планомерного научного поиска и практических разработок. В рамках кибернетики начало формироваться новое научное направление, связанное с разработкой теоретических основ и практической реализации устройств, а затем и систем, предназначенных для распознавания объектов, явлений, процессов. Это направление и получило название «распознавание образов».

К настоящему времени разработано несколько основных направлений в теории распознавания, объединяющих сотни конкретных алгоритмов и методов. В качестве таковых следует отметить перцептрон Розенблата [24], метод потенциальных функций [1], статистические модели распознавания [6, 34], модели распознавания, основанные на построении кусочно-линейных (или более сложных) разделяющих поверхностей в признаковом пространстве [3, 23], алгоритмы, основанные на построении решающих деревьев [5, 22, 31], структурные (лингвистические) методы [33], модели частичной прецедентности [2, 4, 10, 11], алгебраический подход [10], нейросетевые алгоритмы [39], основанные на теории нечетких множеств методы [40], и другие. Основанные на различных идеях, гипотезах и принципах, а также их сочетаниях, они имеют свои достоинства и недостатки, различные требования к исходным данным, ограничения на области применения.

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

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

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

Проведенные эксперименты на таблицах данных, взятых из реальных, прикладных задач распознавания образов [12,14], показали высокое качество предложенного метода по сравнению с другими алгоритмами распознавания [12, 84, 85]. Представленные в работе методы могут быть применены и в решении задач, традиционно решаемых численными методами, таких как прогнозирование поведения речных систем, вычислительных сетей, свойств химических соединений [14,16,17, 29].

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

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

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

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

• Математические Методы Распознавания Образов ММРО-11 (Пущино 2003);

• 7th International Conference on Pattern Recognition and Image Analysis PRIA-7 (St. Petersburg, Russian Federation 2004);

• Научные конференции МФТИ (Долгопрудный, 2005-2006);

• Технологии Microsoft в теории и практике программирования (Москва, 2005);

• 6th WSEAS Int. Conf. on Applied Computer Science ACS06 (Tenerife, Canary Islands, Spain 2006);

• Научные семинары кафедр вычислительной математики и информатики МФТИ (Долгопрудный, 2003-2007);

• Научные семинары отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного центра РАН (Москва, 2004-2007).

Публикации

По теме диссертации опубликовано 8 работ, в том числе одна из списка изданий, рекомендованного ВАК РФ.

Кратко изложим основное содержание работы.

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

Во второй главе дается обзор генетических операторов и наиболее известных современных имплементаций ГА. Представлена схема работы генетического алгоритма. Представлены функции кодирования и декодирования, связывающие пространство предикатов с бинарным пространством размерности N, где N - число объектов в рассматриваемом классе. Данные функции позволяют проводить поиск оптимальных предикатов посредством генетического поиска глобального экстремума целевой функции, определенной в бинарном пространстве. В п. 2.4 дан обзор характерных особенностей рассматриваемой задачи, а также дана теоретическая оценка количества локальных экстремумов для определенного подкласса задач. Приводится сравнение экспериментальных результатов и теоретической оценки количества локальных экстремумов. В п. 2.5.2.1 предлагается новый метод кроссовера, учитывающий взаимное расположение объектов друг относительно друга и осуществляющий скрещивание хромосом по вероятностным правилам, основанным на расстояниях между объектами выборки. Предложены механизмы автоматического выбора размера популяции и коэффициента мутации в зависимости от параметров задачи. В п. 2.5.4 предложен комплексный критерий остановки ГА. В отличие от «стандартных» критериев остановки, завершающих работу ГА после выполнения определенного количества итераций либо после выполнения некоторого числа итераций без улучшения лучшей ЦФ популяции, предложенный критерий адаптируется к конкретной задаче. Это позволяет сократить количество итераций для простых, малоэкстремальных задач и повысить при решении сложных.

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

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

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

Четвертая глава содержит детали программной реализации предложенных алгоритмов. Алгоритмы реализованы автором в программе «Genesis» на языке Фортран-95, а также в качестве модуля в программном комплексе «Recognition» на языке Visual С++ 6.0. Программа «Genesis» позволяет пользователю строить генетический алгоритм, варьируя типы генетических операторов, а также все значимые параметры ГА. Кроме того, включена возможность построения новых решающих правил на основе оценок за классы. Дана спецификация форматов входных данных.

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

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

В пятой главе представлены результаты тестирования разработанных методов на прикладных задачах из области распознавания образов. Дан сравнительный анализ качества распознавания для авторского метода и для методов распознавания, реализованных в программном комплексе «Recognition». Большинство из представленных к сравнению методов основаны на широко известных «классических» методах классификации - К ближайших соседей, линейный дискриминант Фишера, алгоритм вычисления оценок, перцептрон Розенблата и проч. Практически на всех представленных прикладных задачах авторский метод дал стабильно высокие результаты, а для некоторых задач результаты распознавания авторским методом оказались наилучшими среди представленных алгоритмов.

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

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

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

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

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

5. Разработаны новые типы оценок объекта за классы и построены решающие правила для этих оценок.

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

Личный вклад:

1. Постановка задач диссертационного исследования выполнена автором совместно с А.С. Холодовым и В.В. Рязановым.

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

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

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

5. Новые способы получения оценки объекта за классы, а также соответствующие решающие правила разработаны и протестированы автором.

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

Основные положения, выносимые на защиту:

1. Процедура кодирования и генетического поиска логических закономерностей в признаковом пространстве.

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

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

4. Способы построения оценок объекта за классы и основанные на данных оценках решающие правила.

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

Автор выражает глубокую благодарность научному руководителю, члену-корреспонденту РАН, доктору физико-математических наук профессору А.С. Холодову, а также научному консультанту, доктору физико-математических наук профессору В.В. Рязанову за помощь в написании работы, ценные советы, замечания и доброжелательную критику.

3.3 Основные результаты и выводы по главе 5

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

2. Баскакова JI.B., Журавлев Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // Журн. вычисл. матем. и матем. Физики, 1981, Т.21, № 5, с. 1264-1275.

3. Вапник В.Н. Восстановление зависимостей по эмпирическим данным // М.: Наука, 1979, 448 с.

4. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений. // Сб. "Дискретный анализ". Вып. 7. Новосибирск, ИМ СО АН СССР. 1966. С. 3-11.

5. Донской В.И. Алгоритмы обучения, основанные на построении решающих деревьев // Журнал выч. мат. и матем. физики. 1982, т.22, №4, с. 963-974.

6. Дуда Р., Харт П., Распознавание образов и анализ сцен. // Издательство "Мир", Москва, 1976,511 с.

7. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания//Проблемы кибернетики. М.: Наука, 1982. Вып. 39. С. 165-199.

8. Емельянов В.В., Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моделирования // М.:ФИЗМАТЛИТ, 2003.

9. Журавлев Ю.И. ИЗБРАННЫЕ НАУЧНЫЕ ТРУДЫ. // М.: Издательство Магистр, 1998. 420 с.

10. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. //Проблемы кибернетики. М.: Наука, 1978. Вып.33. С.5-68.

11. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок// Кибернетика. 1971. №3. С. 1-11.

12. Журавлев Ю.И., Рязанов В.В., Сенько О.В. «Распознавание». Математические методы. Программная система. Практические применения. // М.:ФАЗИС, 2006, 176 с.

13. Киселева Н.Н. Компьютерное конструирование неорганических соединений -использование баз данных и методов искусственного интеллекта. // М.: Наука, 2005, 289 с.

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

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

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

17. Кузнецов В.А., Сенько О.В., Кузнецова А.В. и др. Распознавание нечетких систем по методу статистически взвешенных синдромов и его применение для иммуногематологической нормы и хронической патологии. // Химическая физика, 1996, т.15.№1. С. 81-100.

18. Курейчик, В.М. Генетические алгоритмы // М.: Физматлит, 2006.

19. Лазарев В.Б., Киш 3.3., Переш Е.Ю., Семрад Е.Е. Сложные халькогениды в системах Ai-Bin-Civ // М.:Металлургия, 1993, 240 с.

20. Лазарев В.Б., Беруль С.И., Салов А.В. Тройные полупроводниковые соединения в системах Ai-Bv-Cvi // М.:Наука, 1982, 148 с.

21. Лбов Г.С. Методы обработки разнотипных экспериментальных данных // Новосибирск, Наука, 1981,160 с.

22. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации // М.гНаука, 1990, с. 69.

23. Минский М., Пейперт С. Персептроны // М.:Мир, 1971, 262 с.

24. Обухов А.С., Рязанов В.В. Применение релаксационных алгоритмов при оптимизации линейных решающих правил. // Доклады 10-й Всероссийской конференции "Математические методы распознавания образов (ММРО-Ю)", Москва, 2001, 102-104.

25. Рез И.С., Поплавко Ю.М. Диэлектрики: основные свойства и применения в электронике // М.: Радио и связь, 1989. 288 с.

26. Савицкий Е.М., Киселева Н.Н. Кибернетическое прогнозирование существования фаз состава АВХг // Изв. АН СССР. Неорган. Материалы. 1979. Т. 15, №6. С. 11011102.

27. Савицкий Е.М., Грибуля В.Б., Киселева Н.Н. и др. Прогнозирование в материаловедении с применением ЭВМ // М.:Наука, 1990, 87 с.

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

29. Сенько О.В. Использование процедуры взвешенного голосования по системе базовых множеств в задачах прогнозирования // М. Наука, Ж. вычисл. матем. и матем. физ. 1995, т. 35, № 10, С. 1552-1563.

30. Сироджа И.Б. Структурно-аналитический метод машинного распознавания объектов с разнотипными признаками // Теория R-функций и актуальные проблемы прикладной математики. Киев: Наукова думка, 1986, с.212-243.

31. Уоссермен Ф. Нейрокомпьютерная техника//М.,Мир, 1992.

32. Фу К. Структурные методы в распознавании образов // М. Мир, 1977.

33. Фукунага К. Введение в статистическую теорию распознавания образов // М.:Наука, 1979, 367 с.

34. Хомич А.В. Анализ и оптимизация операций мутации и кроссовера в генетических алгоритмах // Материалы Докладов V Всероссийской конференции «Новыеинформационные технологии в исследовании сложных структур». Томск, Вестник ТГУ.-2004.-С. 111-114.

35. Alander J.T. On optimal population size of genetic algorithms // CompEuro '92 . 'Computer Systems and Software Engineering', proceedings, 1992.

36. Back T. Evolutionary Algorithms in Theory and Practice // Oxford University Press, 1996.

37. Baeck T. Evolutionary computation // Berlin Heidelberg: Springer-Verlag, 2000.

38. Bezdek J.C. A review of probabilistic, fuzzy, and neural models for pattern recognition // FUZZY LOGIC AND NEURAL NETWORK HANDBOOK, Chen C.H. eds, ch.2, McGraw-Hill, 1996.

39. Bezdek J.C. Pattern Recognition with Fuzzy Objective Function Algorithms // Plenum Press, New-York, 1981.

40. Blickle Т., Thiele L. A Comparison of Selection Schemes used in Genetic Algorithm // 1995, 2 Edition.

41. Box G.E.P., Miiller E.M., A Note on the Generation of Random Normal Deviates // The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610-611

42. Christopher J.C., A Tutorial, on Support Vector Machines for Pattern Recognition // Data Mining and Knowledge Discovery 2,121-167,1998.

43. Darrel W. A Genetic Algorithm Tutorial //1993.

44. Davis L. Handbook of Genetic Algorithms // Van Nostrand Reinhold, 1991.

45. Dawei L. A study on the optimal population size of genetic algorithm // Li Wang Intelligent Control and Automation, proceedings of the 4th World Congress, 2002.

46. De Jong K.A., Kenneth A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems // Doctoral Thesis, Department of Computer and Communication Sciences, University of Michigan, Ann Arbor, 1975.

47. De Jong K.A., Spears W. M. An analysis of interacting role of population size and crossover in genetic algorithms // In Parallel Problem Solving from Nature, 1991.

48. De Jong K.A. A formal analysis of the role of multi-point crossover in genetic algorithms // Annals of Mathematics and Artificial Intelligence, 1992, Vol. 5, no.5, P. 1-26.

49. De Jong K.A. Generation Gaps Revisited. Foundations of Genetic Algotihms 2. // 1993, P. 19-28.

50. Eshelman, L.J. Biases in the crossover landscape // Proceedings of the Third International Conference on Genetic Algorithms. 1989. - P. 10-19.

51. Eschelman L.J., Caruana R., Schaffer D. Biases in the Crossover Landscape // Proc. 3rd Int'l Conference on Genetic Algorithms, Morgan Kaufman Publishing, 1989.

52. Forina M. PARVUS An Extendible Package for Data Exploration, Classification and Correlation. // Institute of Pharmaceutical and Food Analysis and Technologies, Via Brigata Salerno, 16147 Genoa, Italy.

53. Goldberg D.E. Genetic algorithms in search, optimization and machine learning // Addison-Wesley, 1989.

54. Goldberg D.E. Optimal population size for binary-coded genetic algorithms. // TCGA Report, No. 85001,1985.

55. Goldberg D.E., Deb K., Clark J.H. Genetic Algorithms, Noise, and the Sizing of Populations // IlliGAL Report, No. 91010,1991.

56. Hesser, J. Towards an optimal mutation probability for genetic algorithms // Proceedings of the 1st Conference on Parallel Problem Solving from Nature. Berlin: Springer-Verlag, 1990. -P.23-32.

57. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence // University of Michigan, 1975.

58. Kiselyova N.N. Search for efficient methods of prediction of multicomponent inorganic compounds (final report) // EOARD SPC-00-4014, 2001. 46 p.

59. 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.

60. 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.

61. Mangasarian O.L., Wolberg W.H. Cancer diagnosis via linear programming // SIAM News, Volume 23, Number 5, September 1990, pp 1 -18.

62. Martin H.C., Law Mario A.T., Figueiredo A., Jain K. Simultaneous Feature Selection and Clustering Using Mixture Models // Pattern analysis and machine intelligence. Vol. 26, No. 9, pp. 1154-1166.

63. Nowak, M. Error thresholds of replication in finite populations: Mutation frequencies and the onset of Muller's ratchet // Theoretical Biology. 1989. - No. 137 - P.375-395.

64. Reeves C.R. Using genetic algorithms with small populations // In Forrest 7., pages 9299.

65. Ryazanov V.V., Senko O.V., and Zhuravlev Yu. I. Methods of recognition and prediction based on voting procedures.// Pattern Recognition and Image Analysis, Vol. 9, No. 4,1999, p.713—718.

66. Ryazanov V.V. About some approach for automatic knowledge extraction from precendent data // Proceedings of the 7th international conference "Pattern recognition and image processing", Minsk, May 21-23, 2003, vol. 2, pp. 35-40.

67. Ryazanov V.V. Recognition Algorithms Based on Local Optimality Criteria // Pattern Recognition and Image Analysis. 1994. Vol.4, no.2. P.98-109.

68. Sen'ko O.V. A Prediction Algorithm Based on the Procedure of Weighted Voting Using a System of Hyperparallelepipeds in a Multidimensional Feature Space // Pattern Recognition and Image Analysis, 1993, vol.3, no. 3, pp.283-284.

69. Siebert J.P. Vehicle Recognition Using Rule Based Methods // Turing Institute Research Memorandum TIRM-87-018 March 1987.

70. Siebentritt S. Wide gap chalcopyrites: Material properties and solar cells // The Solid Films. 2002. Vol. 403-404. P. 1-8.

71. Sigillito V.G., Wing S.P., Hutton L.V., Baker K.B. Classification of radar returns from the ionosphere using neural networks. // Johns Hopkins APL Technical Digest, 10, 262266,1989.

72. Smith R.E. Population sizing// Institute of Physics Publishing, 2000, P. 134-141.

73. Spears W.M. Evolutionary algorithms: the role of mutation and recombination // Berlin Heidelberg: Springer-Verlag, 2000.

74. Spears, W., De Jong K.A. An Analysis of Multi-point Crossover // Proceedings of the Foundations of Genetic Algorithms Workshop, Bloomington, Indiana, 1990.

75. Syswerda, Gilbert Uniform Crossover in Genetic Algorithms // Proc. 3rd Int'l Conference on Genetic Algorithms, Morgan Kaufman Publishing, 1989.

76. Whitley, D., Kauss, J. GENITOR: a different genetic algorithm // Proceedings of the Rocky Mountain conference on Artificial Intelligence, Denver, CO, 1998, pp. 118-130

77. Whitley D., Starkweather T. Genitor II: a distributed genetic algorithm. Journal // Expt. Theor. Artif. Intel., 1991, 2:189-214