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

РОССИЙСКАЯ ШДЕХШ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦШР

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

Рязанов Владимир Васильевич

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

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

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

Москва - 1994

Работа выполнена в Вычислительном центре Российское Акадэжи Наук.

Офриаальиив оппоненти:

доктор технических нале, профессор

С.В.АСламеЯко

академик РАО, доктор {цзико-матвматкческих наук, профессор В.Л.Матросов

доктор (Щзико-математических наук, профессор

р.А.влеро»

Ведущая оргашзация: Московский физико-технический институт

{¿И

Зашита состоятся '3&' 1994 г. в часов

на заседании специализированного Совета Д 002.32.06 при Вычислительном Центре РАН по адресу:

117967, Москва, ГСП-1, ул, Вавилова 40

С диссертацией морю ознакомиться в библиотеке МИ РАН

Автореферат разослан" 1994 г.

Учений секретарь

специализированного .Совета Д 002.32.06 кандидат физико-матеыэтачесюп наук

С"'ШваРтин/

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

3 то же время дои математического моделирования явлений, ситуация, объектов или1 процессов необходам определенный ■уровень знаний и информации, связанных с объектами исследований. Прежде всего необходимо иметь качественную модель объекта исследования, то есть знать, какие факторы являются определяющими и каковы связи между ниш. Необходимо знать систему закономерностей, уравнений, функционалов и т.п., описывающих адекватно исследуемый объект. Наконец, необходим определенный объем информации' и уровень еб точности для точного вычисления в математических моделях различных величин, решения уравнений и т.п. Отсутствие каких-либо из данных условий зачастую приводит к непреодолимым в рамках математического моделирования проблемам.

Здесь можно отметить следующие две типичные практические ситуации: "

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

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

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

ческсго моделирования отмечено академиком А.А.Дородницыным1 „

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

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

- создание параметрических моделей распознавания, основанных на эмпирических закономерностях;

- оптимизация параметрических моделей распознавания;

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

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

1 Дородницын А.А. Проблемы математического моделирования в описательных науках// Кибернетика. 1983, Ы, С.6-Ю.

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

вые , результаты получена Ю.й.Журавлевым (алгебраическая теория распознавания) и его учениками, правде всего академиком РАО В.Л.Магросовым и чл^н.-корр. РАЕН К.В.Рудаковым; данные вопросы в настоящее раОотэ не рассматриваются.

Известные модели распознавания, основанные на поиске по обучающим данным а;лгарических закономерностей, ориентированы обычно на определенный тип признаков, требуют выполнения некоторых условий или гипотез на начальной информации или ограничены использованием эвристических и локальных средств. Таким образом, актуальным направлением является создание новых, обобщающее, известные моделей распознавания с эмпирическими закономерностями, существующие метода оптимизации сложных многопараме-рических моделей как правило связаны либо с построением локальных решений в отдельных параметрических подоросграю. убвх, либо с оптимизацией линейных решающих правил. Поэтом;, исследование оптимизационных проблем в '¿_. многопараметричесю» с, существенно нелинейных моделях с разнотипными параметрами, разработка методов оптимизации моделей в полных параметрических пространствах является ' ■ также актуальной «мой исследований. Третьим актуальным направлешоч, разгшаемом в настоящей работе, является разработка аьзлогов алгебраического подхода в теории классификации (таксономии), с целью автоматизации построения оптимальных решений задач классификации на базе имещихся коллективов эвристических процедур.

Соответствие исследовательским планам. Диссертация выполнена в соответствии с плановыми НИР : Ц РАН "Развитие алгоритмического и программного обеспечения для применения вычислительных машин при решении задач прогнозирования и диагностики на базе алгебраических и . огических методов"(НГР 0Г.86.0 130490), Дискретные и неклассичесние модели обработки информации и принятия решений (Тема 1.13.12.6), Алгебраические метода в теории распознавания и прогнозирования (Программа "Перспективные информационные технологии", решение ГККГ * 836), Грантом РФШ * 93-012-457: Математические метода синтеза решений неклассических задач экстраполяции (в том числе гад1ч распознавания, классификации и прогнозирования ), тремя хозяйственными договорами.

Цель работы. Реальностью настоящего этапа развития теории распознавания к классификации (кластерного анализа,

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

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

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

Научная новизна. I. Предложен новый общий подход к формализации понятия "эмпирическая закономерность" для задач распознавания со стандартными начальны.-.. информациями, как коллективов специальных подмножеств пространства допустишь признаковых описаний - оптимальных систем признаковых окрестностей. Разработаны параметрические и непараметричзс-кие способы их описания. Задачи нахождения оптимальных систем признаковых окрестностей пол юмиально сведены к решению специальных линейных (БМС-ЦЛП) и билинейных задач целочисленного программирования. Исследована взаимосвязь мевду размэрностью задачи БМС-ВДП и величиной оптимума функционала качества системы -.окрестностей. Разработан новый класс распознающих алгоритмов - основанных на локальных критериях оптимальности.

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

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

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

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

5. Впервые предложена и реализована в программных системах ДИСАРО и ОБРАЗ идеология последовательно-параллельного исследования стандартных информация и решения задач распознавания и классификации.

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

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

- создание новых моделей распознавания, основанных на поиске эмпирических закономерностей;

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

- решение задач диагностики, классификации, прогноза, .

распознавания и контроля ® медицине, геологии, технике, социологии и других областях. •

Апробация. Основные результаты диссертации докладывались и обсувдались на I Всесоюзном совещании по статистическому и дискретному анализу нечисловое информации, экспертным оценкам и дискретной оптимизации (Алма-Ата, IS8I г.). Советско-Гермаяских семинарах "Дискретная математика и ев приложения в кибернетика" (Росток, 1977 г., Москва, 1903 г., Алма-Ата, 1985 г., Тбилиси, 1986 г., Самарканд, 1987 г.), Первой - пятой Всесоюзны! конференциях "Математические методы распознавания образов" (Москва, 1983 г.. Дшппкан , 1985 г., Львов, 1987 г», Рига, 1989 г., Москва,. 1991 г.), Всероссийской конференции "Математические методы распознавания образов"(Москва, 1993 г.), Международных конференциях "Проблемы искусственного интеллекта и распознавания образов" (Киев, 1984 г.), Советско-йшском семинаре по практическому распознаванию (Тбилиси, 1987 г.), "Информационные технологии в обработке изображений и распознавании образов" (Львов, 1990 г.),"Информатика-88" (Гавана, 1988 г. ),"Информатиха-90" (Гавана, 1990 г.), Международных школах-семинарах по биокибернетике (Варшава, 1986 г., 1987 г.), Российско-Германском семинаре "Понимание изображений и распознавание образов" (Зрланген, 1993 г.), семинарах Вычислительного центра РАН (1977 г., 1981 г., 1987 г., 1994г.), факультета БЫК ШУ (1977 г.). Института Социально-экономических проблем РАН (Санкт-Петербург, 1989 г.), Московского физико-технического института (1977 г., 1994 г.), Белорусского Государственного университета (Минск, 1986 г.). Сибирского научно-исследовательского института нефтяной промышленности (Тюмень,1992 г.), Института математики АН ГДР (Берлин, 1985 г.), Гумбольд--университета (Берлин, 1983 г.), Вильгельм Пик- университета (Росток, 1983 г.), Высшей технической школы (Магдебург, 1985 г.), Института математики, кибернетики и физики АН Кубы (Гавана, IS88 г., 1990 г.).

Реализация. Разработанные в диссертации метода, алгоритмы и программные системы были использованы при решении различных прикладных задач (более 20 наименований) и внедрены в П/0 "ЮГАНСКНЕФТЕГАЗ" (Нефтеюганск, Г986 г.), СибНШНП (Тюмень, 1992 г.), "ПШРПРОГРтсКСТМ" (Тверь, 1989 г. ), рядэ научных и производственных учреждения МО, Министерства

здравохранения, Министерства сельского хозяйства.

Публикации. Результаты опубликованы в 41 печатной работа.. Личный вклад автора в совместных работах, имепцих прикладной характер, состоит в формальных постановках, разработке алгоритмов и программ, связанных с реализацией методов построения оптимальных коллективных решений в задачах распознавания и классификации. В статье /35/ автором написаны первые две глав».

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

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы исследований и приводится краткая характеристика реботы в целом.

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

Рассматривается задача распознавания в стандартной постановке, когда исследуемое множество объектов К представимо в виде объединения I подмножеств К;, Кг,..., К1Р называемых классами, заданы начальная информация 10 о классах и описание 1(5) произвольного объекта 3 из *.

Требуется по информации 10 и 1(8) для I = 1,2.....г

определить значения свойств 5 е Предполагается, что описания ГСЯ; определяются наборами п числовых (что для нас в принципе не■существенно ) признаков, начальная информация Г0 (обучающая информация) задается выборкой описаний 1(31),1(32),...г1(3т), 1(Зу)=(аи1,аиг,...,ат), в виде числовой таблицы Т в которой представлены объекты всех X классов с известным распределением их по классы. Для задачи классификации метки классов для объектов обучающей информации не требуются.

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

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

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

Алгоритмы распознавания, основанные на локальных критериях оптимальности, базируются на понятиях признаковых окрестностей - [0} и систем признаковых окрестностей - (0), критериев качества окрестностей - критериев качества систем окрестностей - Р, распознающих операторов - Я и решающих правил - г. Модель распознавания, основанная на локальных критериях оптимальности, определяется конкретизацией элементов набора <С0),(О)

Признаковой окрестностью О (или просто окрестностью) называется произвольное подмножество пространства допустимых описаний объектов распознавания, для которого О Л 10 Ф 0. Критерием качества окрестности 0 (локг 'ьным функционалом) называется функционал /: (О) —*■ Критерием качества

/V "

системы окрестностей 0 = (О,,02,...,0^) (глобальным функционалом) называется функционал Р: (О) —>- Я .

Вводятся определения эквивалентных окрестностей, допустимых и монотонных систем окрестностей.

Распознающим оператором называется оператор Е((0},1о,К8)}={Г1(5),Т2(3),...,Г1(3)), где Г^З; - числовая величина (оценка), характеризующая блир-сть в к классу К(. Как обычно, под реиаюдим правилом понимается оператор

.....гг(3)) = (а1(8),аг(8),...,а1(8)). Значения

а{(5;€<0,м ,/>)' соответствуют принятию решений 3 ^ £ , г е к и отказу от приятия решения для Э относительно

Задача целочисленного линейного программирования называется задачей с блочно-монотонными столбцами коэффициентов системы ограничений и целевого функционала (БМС-ЦШ задача), ее д ока формулируется в следующем виде:

н

_v

F(y} • l l w — ***

h

I. I.<fvu > .....

»(?, tAt ^ ^

y^ifO.n. V'1.2,...k, .....

где к эффициенгы целевого функционала я матрицы ограничений удовлетворяют условиям:

'vh > {v цЧ >

а^ > а* > О, а*^ €fO,tJ, v-r,2,...k, ц=Г,2.....hv-J.

В SS 2-5 описаны различные способы - определения элементов поднзбора <Ю),{0),/,Р>. Оптимальные системы признаковых окрестностей интерпретируются как оптимальные эмпирические закономерности исследуемых классов.

В $2 описан експергно-таксономический подход к определению окрестностей и систем окрестностей. Исходные монотонные системы окрестностей Ov, v=1,2,....к, являются

семействами окрестностей О = О CS, ,d ) » fS: pfS.S. J <

v »v

d .....ftv» где S, - эталоны (задастся экспертом

^ v

или как решение задачи таксономии), р-мэтрика в пространстве признаковых описаний, вычисляются по информации 10, < dv(i+>, \i=1,2,...,hv-1. Локальный функционал /ГО^.) =

= где р - произвольная метрика на Я1,

о(0)=(о),аг,...,о1) - вектор частот представительности, а{ = = ¡IJlK{noi/IIonoi, 2*га=(ог,ог,...,аг), оte(0,n, |о|=П.

Л» „

Глобальный функционал определяется как F(0) - 2

о (5

•v V^L

где Q=(0 . ,0. ,...,0 } - произвольная система окрестностей. Задача поиска оптимальной системы признаковых окрестностей сведена к решению некоторой задачи БМС-1Щ1 (теорема 2.1), единичным компонентам решения которой соответствуют окрестности оптимальной системы окрестностей.

В §3 рассматриваются параметрические методы синтеза систем окрестностей. Предполагается, что Я{ПЯ^ПГо=0.

Рассматриваются параметрические семейства окрестностей (С*/), е^О), J=1,2.....т , Х=1,2г...,п,'гдв =

= i\r=i г,.....r^;: - с<д_: <: e^J, и монотонно возрастание

последовательности Сх = 0*=О, П=П(К), всевозможных значения (при фиксированном .....п)

для заданной информации 10. Вводятся семейства окрестностей

- ( .....п. ¡'1,2.....я. Локальный

функционал определяется как 9*{(ех) +

P'Pjx-OKI* *х •

первое

1,в противном случае,

суммирование проводится по всем С: a(Sl)=a(Sj), второе - по остальным, х(, %г - неотрицательные константы.

Пусть .....п), H(K)=(1,2,...,h(k)}.

(ш,е) - фрагмент произвольного вектора е € С'«С2«...»СП, соответствующий набору и. Определяются окрестности O^fu.e) =

« Л Oj(e.), J*1.2,...,m, и система окрестностей Ofu.e) =

\Cu * ~

= {O^Cu.eJ, /=7,2,...,m). Система окрестностей Oiu.eJ называется разделяющей классы по оСучапдэй выборке, если Offu,e; П Oj(u,e) П 10 * 0 для произвольных пар S{, S^: o?St; / a(Sj). Пусть 5 = {OCu.aj) - множество всевозможных

разделяющих классы систем окрестностей. Глобальный

и

функционал определяется как ?(Ofu,sJ)= ]> J f(0^(£K)).

«u J='

Описаны три алгоритма полиномиальной сложности для сокращения последовательностей 0х". Доказано, что задача

л» _

F(0fu,Ej) —»• min эквивалентна некоторой задаче БМС-ЦЛП

Sfu.eKD

(теорема 2.2), коэффициенты которой находятся последовательным применением первого и третьего алгоритмов сокращения к с\ Пара (и*,е*), определяющая оптимальное решение, задает несократимую систему признаков, разделяющую с точностью е* классы и обледаадуп определенным свойством оптимальности. В силу прямой аналогии с тупиковыми тестами, набор столбцов таблицы Т^ с номерами (J1,Jz,..,Jk) = ш* называется оптимальным £*- тестом, а модели распознавания, в основу которых положено использование оптимальных тестов - моделями распознавания с оптимальными тестами.

Далее описан второй параметрический класс систем окрестностей, в котором с каждым эталоном S, связан индиви-

дуальный вектор параметров tJ. Рассматриваются последовательности CJX, параметрапескже семейства окрестностей (О^Чф. £¿€ О**), J-Í.2.....я. Ъ»1,2,...,п, наборы

, окрестности o'íw'.e-') ■

(0*'л(е*). JUw', - образуйте для окрестности О* (и/,£•')),

множества 0jr-{0'(w,.EJ): и£сff.2.....nJ, eJcC-"«C-'2«...»C,'n)

и системы окрестностей 0({(о),е)}), являющиеся аналогами введенных ранее предметов и связанные с соответствующими эталонами Sj. Рассматривается параметрическое семейство локальных функционалов: i %

f(0>\e{})=J * *>0. где

1 a(St)=a(S ), f 0. |с

. Р

1. в противном случае.

Р*2» * * • »*Х * 31 1 = .....г» К > 0' 0СЛИ aVíSJ',=r,•

Задача поиска оптимальной разделяющей классы системы

т

окрестностей ?(5({(и,е)))) = £ £ /(О^Се^Л —» п1п

' д«(ы.е)))(0

полиномиально сводится к решению ш независимых задач БМС-ЦЛП

(теорема 2.3), коэф8ициенты которых находятся последовательным применением первого и третьего алгоритмов сокращения. Фрагмент объекте в*, соответствующий набору и* оптимального решения задачи БМС-ЦЛП, называется оптимальным представительным £*•'- набором.

Взаимосвязь размерности возникающих задач БМС-ЦЛП и минимальных значений локального функционала показана для случая *£=Г, х?0 =. 0, |а1Х-с -а |,

41*1,1,Цг=1,2,...,т.

Получена оценка $ аш /(е^ < п1п (П-1.т-М

(следствие 2.1 из теоремы 2.4), где г - длина последовательности, полученной из применением первого и третьего алгоритмов сокращения, П - число элементов таблицы обучения: а^) = а(З^). Показана достижимость вершей и нижней оценок. Следствие 2.1 имеет полезную наглядную интерпретацию: "чем хуже признак Л" и больше переменных в

задаче БМС-ИЛП, тем Сольиую оценку снизу имеет величина

В б 4 язлохен непараметрический иерархический метод построения параллелепипедных систем окрестностей. Разработана обратная в определенном смысле процедура их синтеза по отношению к методам $3. Для каждого класса К( и признака ху строится специальная признаковая окрестность, покрывающая все объекты *<П10. Далее строится иерархическая процедура ев разбиения. Построенные таким образом для каждого класса ж признака монотонные семейства окрестностей служат исходной базой для построения оптимальных систем окрестностей. Системы окрестностей определяются как объединения по классам пересечений окрестностей из различных монотонных 0"' при фиксированном I. Задача нахождения оптимальной системы признаковых окрестностей также сводится к решению задачи БЫС-ЦШ; процесс вычисления еб коэффициентов имеет полиномиальную сложность и явно описан.

В §5 продолжено описание параметрических методов формирования систем признаковых окрестностей, удовлетворяющих различным видам ограничений. В разделе 5.1 вводится понятие равномерно оптимальных разделяющих классы систем окрестностей и, соответственно, равномерно оптимальных представительных наборов (используются обозначения §3).

Пусть фиксированы некоторые е-'ХЗ, и^-И...Д^ и набор г}= .....т. Окрестности

А. € и/, называются х* - эквивалентными, если

(локальные) и Л0(((и,£)]),2'.....г*)= 5 У )

¡ = 13

(глобальный) функционалы.

Задача Найти минимум ?(0(((<^,е)}).....гт) по множеству "опустимых значений параметров ]=1,2,...,т)

при ограничениях: I. ^ ) О, £ {7,2.....п), ^ Е"1; 2.

<Ж(ы,'-))) - разделяющая классы система окрестностей; 3. окрестности А. £ для кэвдого фиксированного

J=1,...,m п и3 являются г1 - эквивалентным.

Системы окрестностей оявлящнвся рвяенхяш задача называются равномерно овлиадышма раздампЦвк классы системам*. Рассматриваются следупциэ задача:

n bíX> 1 *V

tí?; ц íwíH

¿, Jf hx^Mt > '« t-'. — .«. a<St) *a<Sj), « n «n aía;

,1, J. ,1. w**«. • ,¡, 1¿

J»rx>

I I/¿í < I, A«í,2....,rt, y{t i I0.1).

¿оказано (теорема 2.5), что репешэ задачи поиска равномерно оптимальной разделяпцей системы окрестностей 0(((ы*,е*)>) =

= 10*(v*J,e*J), J=i,2,:..,n), о*(u>*J,b*sлo^fe*') с z*J -

-эквивалентными окрестностями o'x(e*J). X^'u*-', однозначно определяется решениями (z*J,y*Ji т сформулированных выше независимых билинейных задач целочисленного программирования, причем:

1) коэффйциёнты t*1,2r...,¡t(K,j), получены в результате применения первого и второго алгоритмов сокращения к последовательностям CJX;

Ж(\)

2) значениям у"х\=1 соответствуют ^ =1>.

Набор (J;uv)=(aft ,aJt ,---aJi ),где (ú*J=(t;,í2,...,tfc),

называется равномерно оптимальным представительным e*J-набором. Используя в задаче Z3 различные другие варианты ограничений на множества допустимых систем окрестностей вводятся понятия равномерно оптимальных систем окрестностей, оптимальных систем окрестностей и соответствующие им понятия равномерно оптимальных e-наборов фиксированной длины и оптимальных е-наборов фиксированной длины. Методы их поиска . аналогичны методам решения задачи . _ ,

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

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

Глава 3 посвящена проблеме оптимизации сложных

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

моделями понимаются модели, использующие в своих описаниях

наборы многомерных разнотипных параметров. Исследуется

задача оптимизации моделей, основанных на принципе частичной

прецэдентности (алгоритмы вычисления оценок, модель с

тупиковыми тестами, модель с представительными наборами) в

стандартной ■ постановке. Данные модели оперируют с

параметрами, характеризующими точности измерения признаков -

Е=(е;,е2,..,,ел),информативность признаков- р=(р,,р2,...,ря),

представительность эталонных объектов - 7=(7),72,...,7т),

параметрами решающего правила в^, 1=1,2,...,!, )=1,2.....1+2

(или б(, б2 при использовании голосования "по большинству").

В §1 приводится постановка задачи г оптимизации линейного

1 г

функционала качества £ (доля правильных отве-

1=1J=1

тон), где = I при правильном прогнозе и %lJ =0 при неправильном прогнозе или отказе от распознавания алгоритмом А объекта Б1 контрольной выборки = (в^Б^... ,5^} по отношению к классу К}. Задача 2, состоит в поиске максимальной совместной подсистемы системы неравенств, левые части которых являются полилинейными формами от р,7,С, а коэффициенты - функциями параметров е. Известно, что данная задача может быть сведена к задаче поиска максимального верхнего нуля специальной трудновычислимой монотонной булевой функции и относится к классу сложных комбинаторных задач. Привод.--ся ссылки на существующие локальные и эвристические метода оптимизации.

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

В<*>'- <|а„Л.п. 1<СЛ„Я} —1" *<*> '

распознающего оператора В(р,1)• ВСЕ) —► |Г^(£,р,7) ¡^г и гГ|в^:'|Г^<е.р.т>| > " решающего

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

В §2 вводятся критерии оптимальности операторов близости, как расстояния матриц близости В(е) до "потенциально- наилучшей" матрицы близости (при специальных ограничениях на множества допустимых <В(е)}) в различных метрических пространствах. Если ^-п" то метР!по1

порождают, соответственно, критерии <р7(е1, Фг(е). Критерии оптимальности распознающих операторов определяются как расстояния матриц оценок 1 (б - сояз£) до

множеств "потенциально - наилучших" матриц оценок для контрольной информации I при заданном уровне осторожности д в пространстве числовых матриц д-1 с метрикой р; (задача Ъ2, минимизация функционала О), или как расстояния в той же метрике до "абсолютно-наилучшей матрицы оценок" (задача %3, минимизация функционала ?). Ъг является задачей минимизации билинейной Форш при билинейных ограничениях с положительными коэффициентами, Ъ3 - задачей минимизации билинейной формы при ограничениях: 12120. Критерием

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

§3 посвящен качественному исследованию рассматриваемых экстремальных задач и взаимосвязи их оптимальных решений. Рассматриваются монотонно возрастающие последовательности Сх=0,с*,с*,... всевозможных значений величин

!а{я~а^л1 Л~1,2... .,т, 3=1,2...Доказано, что для модели вычисления оценок ЯИЛ,р,£,-у,С;,й.,) справедливы соотношения:

■« /(p.i.ej - au /(p.7.«V ml» «(p.T.eJ • sta ®rp.7.e.>. (p,y.*)(D (p.j.mHS (p.f,*)iJ) (p.f.e)tt

* refTJ4 г<ША

■in ?fp,7.ej - Bis P(p,y,t). где D-{p,7.e:Y^»0.r>7»0.c»0},

<p.y.*)tD (p.y.m)tt .

В - (p,7,e:f)f»0,t»T)0.e(E). E-E(«E2« ...«En, E^ - подаосж-довательвости (7х, построенные в результате применения первого в второго алгоритмов сокращения, р.7 - фиксированы. Дм частного случая fXiO.U'V, показано,

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

Задачам Z,,Z_, Z_ можно поставить, в соответствие их

> < <3 < 1 __ . .

дискретные аналэгх Z};Z2,Z3, в которых 7£3", ptfi, «<Е . Данные задача имеют самостоятельный интерес, поскольку единичные компоненты векторов р я 7 оптимальных решений позволяют выделять информативную часть таблицы обучения одновременно го признакам и по »талонам. Показано, что для модели вычисления оценок решение задачи Z3

на £ достигается в одной из точек множества

Обозначим p't-r, 7J-*. e'j9U ./*»>.

Теореад з.Б-3,7 показывают взаимосвязь между задачей оптимизации оператора близости и задачами оптимизация распознающего оператора я распознающего алгоритма. Доказано, что для модели вычисления оценок Я(Ь,р,е,7,в) справедливы

соотношения: F(1,p' ,а*,7') - я1п Р(1,р' ,е,7'),

•

f(A(1,p ,е*,г.П) > 1- "In <p,(£)/oql.

если ein o-mn(«in((av-«v_f

o-conat. Таким образом, оптимальные значения параметров е* для оператора близости являются оптимальными для распознатих операторов при "естественном" выборе параметров р, 7 и дают вившо оценку для максимума f(A(k,p,e,f,0)), причем чем меньше значение «in тем более высокая

точность.распознающего алгоритма нам гарантируется.

Далее рассматривается взаимосвязь оптимальных распознающих операторов ж распознай х алгоритмов. Для систем линейных неравенств вида (Ък,х) < о„, Ш, (dl,х) >.of, UIt и связанной с ними задачи линейного/ программирования Ч(Ь,г? —* vliii при ограничениях » о., icl, й= J ьс1,

вводится понятие согласованности. 'Георема 3.8 утверждает,

' . V - 17 - ■ ' .

- что «сп приведенные система а задаче ЛИ является согдасовавяша. тр ревввхе эадачя т удовлетворяет некоторой максимальной. совместной подсистеме системв (Ь1.х) < а2. Ш* (¿1,х) > о,. 1<Х. Из данного вахта непосредственно следуют утверждения о взаимосвязи оптимальных решений задачи %г по параметрам р, щж фиксированных значениях остальных параметров (или по параметрам 7 при вихсированных значениях остальных параметров) с решением задач» г}: если возникающие систеад линейных неравенств в задаче 2Г ж задача Ш в задаче Ъг являются согласованными, то оптимальные решения задач 1г будут локвльно-оптииалышмиреаениями задач в соответствующих параметрмческих подпространствах.

В $4 описаны методы оптимизации оператора близости, распознающего оператора и распознающего алгоритма.

Оптимизация оператора близости основана на использовании теоремы 3.11 (для функционала ф((£Л я теоремы 3.12 (для функционала ц>2(е)). обеспечивающих полиномиальное сведение задач оптимизации оператора близости к задачам ЕМС-ЦЛП; "длй решения последней использовалась локальные методы наискорейшего спуска.

Ддя оптимизация распознающего оператора предложены численные метода решения задач 1'г, 2'3.

Задача 1г сводится к решений последовательности систем нелинейных неравенств, методы решения которых разработаны в главе 4. Для решения ев дискретного аналога 1'г использовздась локальные градиентные методы, учитывающие ев специфику. Для решения задачи 2'3 (решение 13 является одним из решений ?.'3) были разработаны специальные локальные метода, основанные на использовании полученной линейной по вариациям параметров верхней оценки вариаций функционала Р(р,7) в допустимой точке (р.т) на окрестностях произвольного радиуса. Из текуией точки (р,7) осуществляется переход в точку (р' ,7'), которая находится за 0Шг1о& п *■ тт?1<щ я) операций и обеспечивает минимальную верхами оценку для

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

за 0{\гс^) операций. /':' •'•.<'..,..' ' ' ..

В §5 приведенврезультаты оптимизации модели вычисления

оценок на примере одной задачи медицинской диагностики, а также сравнение полученных оптимальных алгоритмов (76% правильных ответов и S% отказов) с классическими статистическими методами (метод "к ближайших соседей"- 54S и 12%, соответственно; линейный дискриминант Фишера- 705» и 8%).

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

В §1 приводятся основные принципы релаксационных алгоритмов решения систем выпуклых неравенств, разработанных в работах Еремина И.И.

Рассматривается задача нахождения некоторого решения

совместной системы норавенств f} (х) $ О, J=1,2.....m, где

fj (х) - выпуклые гладкие функции, определенные на Я", Ы -

множество её решений. Определяется отображение ф(х):Яп—*■ Rn

(х - Ш(хМхУ1Ш)1г , I(x)*fl,

Ф(х) = ! [■т ,

где 6с(0,2), 1(:гЫ(| f{(x) > 0 ), а скалярная функция d(x) и вектор-функция ы(х) вычисляются одним из следующих трех способов :

1. d(x) = шах /Лх)=/ fxj. ы(х) = v/ (U,

JiZ(x) J JiX} J(x)

2. d(x) = £ f](x), u(r,'= \ /j(r)v/f(x),

' JiZ(x) ' Jil(x)

3. d(x) = \ U(X) = 5 y/jd),

Jtl(x> Jih'x)

Xj>u - фиксированные числа. Функции a¡(xi, dfx) достаточно считат«- определенными на Rn\M. В зависимости от выбора пары и(т), будем различать отображения <р( i.x), ф?(х) и ф3(х), соответственно.

Строится последовательность х',лг2.....xv,...: xv*г=ф(х"),

х1 £ И, которая сходится к одному из решений системы при условии Inf eN>0. Для случаев ф,(х) и фд(г) доказана линейная скорость еб сходимости ' (слабой) при ограниченности градиентов vfj (х) и существовании x°iU, /^(х°)<0, J=1,2,...,п.1 Соответственно выбору ф(г) будем различать алгср-тш Д(, Аг и А3. f 1втрудно привести примеры распространенных ситуаций, когда вычислительные затраты при работе приведенных алгоритмов могут быть сколь угодно велики (при высоких затратах на вычисления значений функций или их градиентов, при больших размерностях' задачи, или наличии "овражных" ситуаций).

В §2 предложен один подход к ускорении сходимости релаксационного метода. Вводится параметрическое множество отображений (ф(9Д)>, являющееся расширением отображений ф,, <р2 и <р3, и бесконечномерное параметрическое множество релаксационных алгоритмов (А). Каждый алгоритм из CA) на каждой итерации использует определенное отображение из (р).

Набор Ks = CXj| > О, JtJ(x)=il j ft(x) ^ О )) называется допустимым, если > 0> Л I(x) t ¡3. Допустимым направлением в точке х / ä называется направление ы(х) = = £ г), где допустимый набор для точки х, Л(х)-JtJ(x)

- множество допустимых в х наборов \х.

Шаг ге(\ v)= ]> Ä. / (rv)/\m(xv)\, вычисленный в точке

V * "

JiJ<x ).

xv0 для допустимого в х" направления u(xv), называется оптимальным гарантированным шагом (ОВД. Определяется множество отображений Ф = (ф), ф=ф<,0-Л,):

'х - 8ae(\)u(x;/|ujfx)|, 1(х)*0

X , 1(Х)=0,

где 96(0,2), \ > О,

Через A(9ylAv; v=I,2,...) обозначается релаксационный алгоритм , определяющий последовательность х' ,-Г2,...,xv,...

1 Еремин И.И. О скорости сходимости- в методе фейероЕоких приближений// Мат. заметки. 1968. Т. 4, Ж. С. 53-61.

озгласно 4>fev'x"J. v»I,2,... (x' - произвольно). где XK«XJr» - допустимые наборы. 9V<(0,2), 111* ву > О, - OIJD *

ufxvj > допустимые направления. Релаксационный алгоритм A*kA(Qv,\v; называется оптимальным, веял вv «1а

значения находятся из условия ж(А.г») —» авх .

Для оптимального алгоритма Л справедлива минимальная верхняя оценка |xv* '-*|2 < |xv-*|2 ais(X v)* относительно других вариантов релаксационного сдвига из х". Показано, что xv*' является проекцией xv на многогранник K(xv):Wj(xv),x-xu)+fJlxv) i О, JtJ(xv). и, следовательно,

монет быть найден также путем ревения задачи |xv-x| —•> вйп.

' xat(*v)

Через А обозначим приближение алгоритма Л, под которым понимается произвольный релаксационный алгоритм с условием: ОПП a(\fv)> пах( xf(kxv), здесь ае, и являются

0Ш,- соответствующие алгоритмам А, и А3 в точхе xv. Сходимость и оценка скорости сходимости А и А* следуют из сходимости л,:и при этом справедлива оценка: jxv+,-tf| < < e^lx"-*!. e^U-sf/Nfcf)"*, tt > 1, где 0Ш \ > 1, fft, Ct - const, t=i, 3-

B J3 предлагаются алгоритмы типа л, не требующие решения вспомогательных задач квадратичного программирования. Алгоритм Л4 на каждом ваге последовательности итераций осуществляет релаксационный сдвиг согласно тому алгоритму из iAJtA2,A3), который обеспечивает максимальное относительно других значение x(Kxv). Показано, что для случаев "очень тупых", "прямоугольных" и "очень острых" конусов, на вершины которых проецируется xv оптимальным алгоритмом 4*. алгоритм Л4 работает как А* или (в последнем случае) предпочтительнее чем А;, а£. Алгоритм а5 является обобщением А, и проецирует

xv if. (х")=0) на наиболее удаленное от ху множество

{г| / (rv) « о, / (xv) $ 0>, JeJ(xv>. * *>

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

В §5 рассмотрен случай плоских систем, под которыми

n

понимаются сястеш ft(x)* J la*!»».

j=t

со еле лущима свойствами:

(a'.a-') > »-е, С l.J) i i'-l'li I2-I¿.

(a'.cr') <-í+e. (l.J) í Г'-Гг, где

V*(1,Z.....HtJ, I2=(n1*t,m^e!,,..,mi, e > О, |£|</. ( для

нелинейных систем вместо a' используется v/{(x)). Показано, что при оптимизации моделей распознавания имеют место системы данного вида. В произвольной точке j/f* имеет место одна из двух возможных ситуаций:

I.либо Лх)ПГ'=0, либо ЛхЮГЧэ; 2. «Г(х)П1г^0,

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

оптимальному (теорема 4.2). При наличии второй ситуации использование алгоритма типа ' А3 обеспечивает большую величину ОШ. Получены оценки сверху для |х'-а|, где а -- проекция х на *'■=fx" | fj(z') < О, JeJ(x)), х'=ф(х).

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

В §1 приводятся формализации классифицирующего алгоритма и комитетного синтеза коллективных решений. Алгоритмом таксономии называется алгоритм, переводящий описания JAS) объектов 5, ,Sn, ...,S в класс эквивалентности

I «г tu

lC(|at;lw-l), a(J<;{0.I,M, 1 = 1.2.....m, J=1,2.....1. Матрица

являются эквивалентными, если они равны с точностью до перестановки столбцов, каздая информационная матрица Ia,j 1ж, ¡ опредэляет класс эквиваленгности Отметим, что

результатом применения произвольного эвристического алгоритма таксономии к Jm(S) является покрытие (но обязательно разбиение) выборки таксонами.

Пусть заданы результаты применения п эвристических алгоритмов таксономии <4®, к выборке S;,S2,...,Se:

tyjjs» = ш„>. , ..........п.

V

Предполагается, что Iv не содержат равные или нулевые столбцы. Е" едятся обозначения: L= jaaxíl rlz,...,ln); Dv- множество числовых матриц |-г удовлетворяющих ограничени-

- 22 -\ X. ям: ТхГ, J'1.2.....L, J х"..*1,1*1,2.....1

- информационная матрица, полученная из добавлением справа L-lv нулевых столбцов; I'v - произвольный элемент множества JC(I*J. Можно считать» что каждый алгоритм v=f,2,...,n, вычислил K<X*J. Между множествами К{1*) я Dv устанавливается взаимо-однозначное соответствие.

Через 3 - (Г } я D «■ Ш обозначаются прямые произведения множеств JC(Г*; и Dv,v*1,2,....п, соответственно:

I -(It,I2,....l'n). X ~(Х'.Хг.....ХГ-). Xv(Dy.

Оператор В : 3(Г )~В. Г&, где В = Ib^l^, btJ?0.

называется сумматором, если Ъ = J а'*. Матрицы В называются

' VI / ■

матрицами оценок. Комитетным синтезом информационной матрицы на элементе Г<3 называется ев вычисление

G~r(B(T)) при условиях: В - сумматор, г- пороговое решающее •1, 1*1,2,...,m;

правило, ctJ « A, e^>btJ>e[, J=1,2,...,L;

U e|>b{J.

где oJ.Oj, t=1,2,...,m - параметры решающего правила.

Показано, что оператор гЗ ("произведение операторов В и

г) осуществляет отображение 3 на некоторое множество Kc*<*:(lc{jln,L)), где lc{Jln,L=r(B(r)), 143. Фиксируя

произвольное Г'сЭ , получаем алгоритм таксономии

A®t(Jm(S)) = K(rB(í')), Г-(Г,.Гг.....rnU i;€A^(Je(S)).

Задача нахождения оптимального комитетного решения задачи таксономии коллективом алгоритмов Л®,Л®,...,Л® состоит в поиске наилучшего элемента из К0 (или, наилучшего 1'сЗ).

В $2 вводятся меры качества коллективных решений задачи таксономии при комитетом их синтезе. Ясно, что О < b{J а п. Вводятся понятия контрастных ' эсли b(JfJO,n)) и размытых

(еспи bt¿=Pt. матриц оценок S=|b{J|wi(i. Множества

всех контрастных и размытых матриц оценок размерности ra«L обозначаются через Ю т и К ,, соответственно, или

ÍV - Ш, ±J fll.jj

просто К и JR. Внделяются специальные подмножества множеств 91 и К. Рассматриваются метрические пространства матриц: R™'1 с

метрикой р.(В,,Я2)= мах пах lb!,-bf.l; R*,i,p с метрикой

7 n L tili* tüliL <J lJ 2

* 1 ' ft

Пусть p«Cp( ,p2,p3>, GdR, C-ta». Вводятся следующие критерии качества матриц оценок: I. Фр a(B)=p(B,G);

2. ®p>s(B)=piB,CJ; 3. ^р.а,0(В)=«р.0(В)-«р.б(в). Матрица В*

называется оптимальной по критерии Фр а(В) (критерии

> _ я{В)) в классе матриц (В), если Ф„ _(В*)= *1п ф (В)

р.сг весв> р'

(если F _ х(В*)= min (Ф„ _(В)-Ф я(В))). Матрица В* называется оптимальной по критерию фр в классе матриц (В), если 5 Л(В*)= аах Фл «(В).

Показано существование таких множеств С.Си метрики р (теорема 5.3.), при которых множества оптимальных матриц оценок из произвольного (В) по критериям Фр 0. ®p'g и Fp Q g совпадают.

Коллективное решение задачи таксономии JC(C*)=x:(|c* I „),

ж ж « п ■ IJ'fllMlj

С €D(C), С =г(В(1'(Х ))), X iD, называется оптимальным на D по критерию ф, если матрица оценок B*=B(I'(X*)) оптимальна на множестве СB(I(X)), X£D) по критерию ф (здесь условие С*ей(С) является ограничением на выбор параметров решающего правила).

Качественная взаимосвязь функционалов при различных способах выбора метрик исследована в §3._ Доказано (теорема 5.4), что решение задачи минимизации Ф*(Х) = Ф _ (В(Х))

р2' m.L

при р=р0= )mL] + 1 будет решением задачи минимиза-

ции Ф5(Л при pzpn и задачи минимизации Ф,(Х)=Ф _ (В(Х)).

Р' m'L „.

Теорема S.5. утверждает, что Ф3(Хр)=т1п ®3(Х), если Ф£(*р) =

XiD

= min &;(Х), для любого р, О <р $ р0< losxlmL/(mL-1)] (здесь ZlD

Ф,(Х) = Ф _ (В(Х))). В §4 описан алгоритм поиска оптимального коллективного

решения задачи таксономии при комитетном синтезе матриц ■

оценок &ля функционала ф (Я) при р=р„ р=г, В

р.а и г г ш.1

данном случав * «г(Я) = ][ £ (>111 (Ь^.п-й^)).

Пусть V*!.2,... ,п - некоторая перестановка набора чисел ■к°=<1,2.....!>,*=<«',т2.....тп>- набор

перестановок, однозначно определяющий матрицу оценок

п

В'-»Ь'«Л.1' Ъ'и^**^)' а<Х»у Пзлучена ввРшяя

оценка вариации функционала при применении набора перестало-

вок г: дФ,

-2,п-четное, -/,л-нечегн. 3

О,п-четное, -/,п-нечетн.^

Здесь величина зависит только от перестановки тс1"; Ы2},

KЛJ с <7,2,...,т>. Задача поиска перестановки минимизи-

рупцей Д , сводится к решению известной задачи о назначениях, л

Условие £ А„<° является достаточным для уменьшения функционала при переходе от Ъ^От) к Ь'^ = Ь^!х>. Для решения задачи Ф_(В(*)) -«■ и1п разработан алгоритм наискорейшего

* 1С

спуска, основанный нч независимой минимизации (%") для каждого V, и имеющий общую сложность 0(15т) выполнения на каждой итерации.

Аналогичный метод оптимизации создан для функционала С(В) при 0=р2, р=1, С=К* х - мнохество контрастных матриц с единственным ненулевым элементом в каждой строке.

Приводятся результаты численных экспериментов на модельных задачах. Эксперименты показали как эффективность алгоритма оптимизации функционала Ф2(В). так и хорошую устойчивость оптимальных коллективных решений при некоторых случайных возмущениях исходных классификаций С{11(),у=7.....п.

В главе 6 обсуждаются особенности разработки систем анализа и распознавания образов, приводятся описания диалоговой системы анализа и распознавания образов - ДИСАРО, и аннотации пакета алгоритмов таксономии ТАХ(Ж и системы ОБРАЗ. Данные программные средства успешно использовались при решении многих практических задач и внедрены в ряде научных и производственных организаций.

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

прежде, всего на специфике подходов и методов теории распознавания относительно других областей прикладной математики; необходимость наличия разнообразных методов, двухуровневый характер решения задач распознавания или таксономии, наличие интерфейса "метод-метод", "ЭВМ-пользователь-ЭВКг и возможностей управления постановками задач распознавания и таксономии. Описываются основные вида преобразования данных, которые выполняются в разработанных программмных системах.

Описанию Диалоговой система анализа и распознавания образов (ДИСАРО) посвящен §2. ДИСАРО решает следующие задачи: нахождение различных оптимальных алгоритмов распознавания в многопараметрических семействах алгоритмов вычисления оценок; распознавание объектов различными методами; сценка информативности при: .аков; оценка информативности эталонных объектов; оцени-! точности измерения признаков; минимизация признакового пространства; нахозкдекие информативных подсистем признаков; нахождение эталонных описаний классов; вычисление мер близости объектов к каждому из классов; вычисление оптимального числа таксонов и решение задачи таксономии; оценка качества распознающего алгоритма. Решение задач осуществляется либо в диалоговом, либо в пакетном режиме. Система реализована Ни ЭВМ БЭСМ-6 . Методы поиска множеств тупиковых >сгов и тупиковых представительных наборов, а также прог~ ммные реализации некоторых алгоритмов разработаны Е.В.Дюковой.

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

В 53 описан патет программ таксономии ТАХОМ. Пакет состоит из восьми р~ристических алгоритмов, основанных на идеях покрытия заданной выборки гиперсферами и иерархической группировки, а такта алгоритма поиска коллективного решения задачи таксономии.

Краткому описанию програмшой система анализа я распознавания ОБРАЗ, разработанной для ЭВМ серея ВС. посвящая {4. В практической программной реализация систем* ОБРАЗ участвовал коллектив сотрудников отдела проблем распознавания я методов комбинаторного анализа ВЦ РАН. Автор настоящей диссертации являлся научным руководителем разработки и автором ряда алгоритмов и программ.

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

В последнем параграфе главы перечислены основные, реализованные в системах ДИСАРО и ОБРАЗ, принцпы и идеи распознавания.

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

Заключение (основные результаты).

I, Предложен нощй подход для формализации и нахождения (па} метрические и непараметрические методы) по прецедентной информации эмпирических закономерностей различного типа в виде ОмДмалъных систем признаковых окрестностей, обобщающих известные поняда тупиковых тестов- и • тупиковых

представительных наборов. Задачи поиска оптимальных' систем окрестностей полиномиально сведены к решению специальных задач целочисленного линейного программирования с блочно-монотонными столбцами коэффициентов системы ограничений и целевого функционала (задач БМС-ВДП), и задач билинейного целочисленного программирования. Показана прямая связь между размерностью задач БМС-ШШ. и минимальными значениями локальных функционалов.

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

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

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

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

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

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

8. Разработаны программные системы анализа и распознавания образов ДКСЛРЭ и ОБРАЗ, пакет программ классификации- TAXON. В системах реализованы основные идеи и алгоритмы диссертации, а также методология последовательно-параллельного процесса исследования и решения' задач распознавания.

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

возрастных распределений.

Публикации.

1. Ахназарова Р.Б., Веселов E.H., Рязанов В.В. Разработка диалоговых систем распознавания. Оптимизация моделей распознавания в диалоговом режиме. М.:ВЦ АН СССР. 1983. 15 с.

2. Богачбв A.B., Булавин Е.С., Рязаног В.В. Анализ материалов многозональной събмки с целью определения преобладающих пород. Экономико-математическое моделирование ласохозяй'гвенных мероприятий. Л.:Лен.НШЛХ. 1980. С.58-62.

3. Богомолов В.П.,Бушманов О.Н.,Кочетков Д.В., Рязанов В.В., Сенько О-В. Система анализа и распознавания образов -СБРАЗ-2 //Тез.докл. 4 Всесоюзной конференции "Математические методы распознавания".Рига: МИПКРРиС при СМ ЛатвССР. 1989. Часть 6. С.П-ГЗ.

4. Богомолов В.П., Бунманов О.Н., Рязанов В.В., Сенько О.В. Программная система для гна.теза данных методами распознавания таксономии. М.: ВЦ АН СССР. 1990. 31 с.

5. Бушманов О.Н., Д*жоза Е.В., Куравлёв Ю.И., Кочетков Д.В., Рязанов В.В. Система анализа и распознавания образов //Распознавание, классификация, прогноз: Мат. методы и их применение. М.:Наука, 1983. Вып.2. С.250-273.

6. Бушманов О.Н., Дюкова Е.В., Рязанов В.В. Система распознавания, таксономии и анализа стандартных данных // Тез.III

Всесоюзной конф. "Мат. метода распознавания образов". Львов: Иэд-во АН УССР, Г987. С.8-9.

7. Дородницына В.В. .Рязанов В.В. Решение медицинских задач диагностики методами " распознавания //Тез. докл. III Всесоюзной конференции "Математические метода распознавания образов" Львов. 190/. С.196-19Т.

8. Дюкова е.В. , Журавлев ю.л., Рязанов В.В. Диалоговая система анализа к распознавания образов.М.: ВЦАН СССР, 1988, 40 с.

9. Дпкова Е.В.,Рязанов В.В. О решении прикладных задач алгоритмами распознавания, основанными но принципе голосования. М.: ВЦ АН СССР. 1986. 26с.

10. Дккова Е.В., Рязанов В.В. Исследование задач распознавания в диалоговых распознающих системах //Тез. докл. II Всесоюзн. конф. "Матем. методы распознавания образов". Дили-жан. Изд.-во АН Арм. ССР, 1985. С. Т6-78.

11. Куравлбз D.H., Зенкин A.A., Зенкин А.И., Исаев И.В., ' Кольцов П.П., Кочетков Д.В., Рязанов В.В. Задачи распознавания и классификации со стандартной обучающей информацией //ЖВМиМФ. 1980. Том 20, Яб. 1980. С.1294-1309.

12. Журавлбв D.M., Зенкин A.A., Зенкин А.И., Исаев И.В., Кольцов П.П., Кочетков Д.В., Рязанов В.В. Пакет прикладных программ для решения задач распознавания и классификации (ПАРК). М.: ВЦ АН СССР. 1981. 24 с.

13. Журавлбв Ю.И., Зенкин А.И., Рязанов В.В. Алгоритм прогнозировали производственных процессов // Вопросы радиоэлектроники, серия АСУ, Вып. I. М. :197с. С. 32-42.

14. Журавлбв D.M., Рязанов В.В. Интеллектуальная система построения оптимальных алгоритмов для решения задач диагностики, распознячания, классификации данных и принятия решений по прецедентам. В кн. "Фундаментальные науки -народному хозяйству". Москва. Наука. 1990.

1С. Зенкин А.И., Миропник С.Н., Рязанов В.В. Некоторые экстремальные алгоритма распознавания и их применение в геологическом прогнозировании. История геолсгии. Подготовка специалистов в области геологии. Математическая геология и геологическая информация. М.:Недра, 1980. С. 115-121. 16. Зенкин А.И., Рязанов В.В. Алгоритмы прогнозирования состояний контролируемых объектов//МШиМФ. 1977. Ток 17, Х6. C.I564-I573.

- зо -

17. Кузоваткин Р.И., Зенкин А.И., Рязанов В.В,,Егоров П.И. Распознавание солеобразупцей способности нефтяных сквахин по эксплуатационным признакам // Проблемы нефти и газа Тгчени: Научн.техн. сб. Тюмень. 1978. Вып. 38. С. 39-41.

18. Кузоваткин Р.И., Зенкин А.И., Рязанов В,В.,Егоров П.И. Прогнозирование процесса солеобразованз i при эксплуатации нефтяных скважин // Там ке. 1979. Вып.42. С. 42-44.

19. Ларин С.Б. Рязанов В.В, Об одном подходе к оптимизации моделей распознавания с представительными наборами// Тезисы Всероссийской конференции "Математические методы распознавания образов (ММЮ-6)".г. Москва, 1993 г. С. 39-40.

20. Нанси Лопес, Рязанов В.В. Оптимизация моделей распознавания с билинейными функционалами качества. М.: ВЦ АН СССР: 1990. 23 с.

21. Нанси Лопес, Рязанов В.В. Об оптимизации моделей распознавания с билинейными функционалами качества /-/Тез. докл. 4 Всесоюзной конференции "Математические метода распознавания образов". Рига: МИПКРРиС при СМ ЛатвССР. 1989, Часть 2. С. 123-125.

22. Рязанов В.В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк //ЖВЫИМФ. 1976. Том 16, *6. С. 1559-1570.

23. Рязанов В.В. О выборе релаксационнь.. алгоритмов решения систем линейных неравенств //Сб. работ по матем. кибернетике. М.: ВЦ АН СССР, Вып. 2. 1977. C.I7I-I92.

24. Рязанов В.В. Оптимизация некоторых многопараметрических моделей распознавания//; Rostock. Math. Kolloq. 11, С.93-96 (1979). -

25. Ряьанов В.В. Об алгебраическом подходе к решению '.адачи классификации (таксономии)// Тез. докл.1 Всесоюзного С<зеща-ния "Статистический и дискретный анализ нечисловой информации, экспертные оценки и дискретная оптимиз ция". Алма-ата. Изд.-во Каз.ГУ, 1981. С.367-368. • ;

26. Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации //ЖВЫиМФ. 1981. Том 21, J66. С Л533-154".

27. Рязанов В.В. О синтезе классифицирующих алгоритмов на конечных множествах алгоритмов классификации (таксономии) // ЖВМиЫФ. 1982. Том 22, JK. С.429-440, ' '

28. Рязанс В.В. О решении прикладных задач в диалоговых системах распознавания //Тез. докл.Научной конференции с

участием ученых из соц. стран "Проблемы искуственного интеллекта и распознавания образов". Киев. Наукова думка, 1984. С. 112-114. .

29. Рязанов В.В. О построении оптимальных вл-оритмов распознавания и таксономии (классификации) при решении прикладных задач// Распознавание, классификация, прогноз: Матем. методы и их применение. М.: Наука, 1988. Вып.1, С.229-279.

30. Рязанов В.В. Об одном подходе к оптимизации многопараметрических моделей распознавания //Тез.докл. 5 Всесоюзн.

. конф. "Мат.метода распозн. сэбразов", Москва, 1991.С.100.

31. Рязанов В.В. Алгоритмы распознавания, основанные на локальных критериях оптимальности// Тезисы Всероссийской конференции "Математические методы распознавания образов (ММРО-6)". Г. Москва, 1993. С. 57-58.

32. Рязанов В.В.,Ромасевич А.Н., Кузнецов Н.П. Опыт решения инженерно-технических задач на основе методов таксономии и распознавания. Применение прогрессивных технологий в добыче нефти на месторождениях Западной Сибири// Сб. научных- трудов. Тюмень. СибНИИНП, 1988, С.62-66.

33. Рязанов В.В., Рязанова Н.В., Смольянинова З.А. Прогноз урожайности сельскохозяйственных культур с использованием методов распознавания образов //Метода моделирования в сельском хозяйстве. Сб.. научн. трудов. М.: ВНИПТИК. 1982. С. 50-60.

34. Рязанов В.В..Сенько О.В. О двух методах обработки информации в теории распознавания и классификации // Тез. докл. III Всесоюзной конференции "Математические методы распознавания образов". Часть 2. Львов. 1987. С.153.

35. Рязанов В.В.,Сенько О.В. О некоторых моделях распознавания и методах их оптимизации //Распознавание, классификация, прогноз: математические методы и их применение. М.: Наука. 1990. Вып.З, С.Юб-145.

36. B0g0r;:jl0Y V.P., BuahmanoT O.K., Ryazanov 7.V., Senco O.Y. Zhuravler Yu.I. Data Analysis and Recognition Systems: Algorithms, Programs and. Applications //Pattern Recognition and Image Analysis. 1991. Vol.1. no.3. P.335-346.

37. Bushmanov O.N..Bogomolov V.P., Ryazanov V.V., Senko O.V. // The System for Analysis and Pattern Recognition (OBRAZ). First Intern. Conf. on Information 'Technologies for Image Analysis and Patt. Recogn. Lviv, 1990. Vol.2. P.13-14.

38. Ryazanov 7.V. Cn the Optimization oí a Clasa of Recognition Models //Pattern Recognition and Image Analysis, Vol.1. i!o.1. 1991. P.108-113.

39. Ryazanov 7.V. On an Approach to Complex Problems of Recognition learning //Pattern Recognition and Image Analysis. ¡993. VoL.3. 110.3. P.248-252.

40. Riasanov V.V., Lopez IX. Acerca de los modelos de reconocimiento basados en funciones bllineales de 'cercanía // "INFORJíATICA-90". Tesis II Congreso Internacional de Informática, • resúmenos. T. II.(febrero, 1990). Ciudad Habana: Palacio de las Convenciones. 1990. 431 pag.

41. Ryazanov V.V. Recognition Algorithms Based on local Optlmality Criteria //Pattern Recognition and Image Analysis. 1994. Vol.4, no.2. P.98-109.