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

РГ6 ол

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

Нагаев Ильяс Мансурович

КЛАССИФИКАЦИЯ ПРИ НЕПОЛНОЙ ИНФОРМАЦИИ О ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИКАХ КЛАССОВ

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

АВТОРЕФЕРАТ

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

УФА - 1996

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

Научные руководители: -

доктор технических наук, профессор Рудерман С.Ю.,

кандидат технических наук, доцент Орехов Ю.В.

Официальные оппоненты: - доктор технических наук,

профессор Хасанов М.М.

кандидат физико-математических наук, доцент Курмангалеева A.M.

Ведущая организация: - Уфимский государственный нефтяной

технический университет.

• г-

Защита состоится 28 января 1997 г. в /3_ час. на заседании

диссертационного совета Д-064.13.02 при Башкирском государственном университете по адресу: 450074, г. Уфа, ул. Фрунзе, 32, математический факультет.

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

Автореферат разослан декабря 1996 г.

Отзывы на автореферат, заверенные гербовой печатью, просим выслать по указанному адресу на имя ученого секретаря диссертационного совета Д-064.13.02 Морозкина Н.Д.

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

диссертационного совета Д-064.13.02 Морозкин Н.Д.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

На защиту выносятся:

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

2. Три схемы классификации с использованием предложенных подходов.

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

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

Научная новизна.

Новыми в работе являются:

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

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

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

асимптотические оценки условной вероятности ошибки классификации по предлагаемым схемам при неограниченном объеме обучающей выборки;

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

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

сравнительный анализ предложенных схем классификации с правилом ближайшего соседа (БС) и между собой.

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

Результаты исследований были использованы при разработке программного модуля для классификации и идентификации водных объектов, который создавался в рамках НИР "Разработка и внедрение математических, программных и аппаратных средств дистанционного мониторинга" при реализации программы по созданию единой государственной системы мониторинга Республики Башкортостан (№ ГР 01960003774; Инв. № 02.9.60003721).

Результаты работы использованы в учебном процессе в УГАТУ в рамках специального курса "Распознавание образов".

Апробация работы.

Основные результаты диссертации докладывались на: 2-ой Всероссийской с участием стран СНГ конференции "Распознавание образов и анализ изображений: новые информационные технологии" (1995, г. Ульяновск),

конференции "Проблемы экологического мониторинга" (1995, г. Уфа),

Всероссийской конференции "Повышение эффективности средств обработки информации на базе математического и машинного моделирования" (Тамбов, 1995),

Всероссийской молодежной научно-техническая конференции "Информационные и кибернетические системы управления и их элементы" (1995, г. Уфа),

на городском семинаре по прикладной математике и математической физике (1996, г. Уфа),

семинарах "Модели искусственного интеллекта" кафедры ВМиК УГАТУ (1994-1996, г. Уфа).

Публикации. По теме диссертации опубликовано 7 работ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и приложения. Полный ее объем составляет 99 страниц машинописного текста, включая 4 рисунка на 4 страницах, 4 таблицы на 1 странице, библиографию, содержащую 40 названий.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

Пусть X - наблюдаемая система случайных величин, реализация которой х рассматривается как объект;

Г={ук1,...,\ут} - множество классов, образующих полную группу несовместных событий;

имеется обучающая выборка для каждого из классов;

для группы классов Г,сГ известны (или оценены) условные законы распределения Р(хЛ^) и вероятности соответственно, через Г2

обозначается группа классов, для которых условные законы распределения Р(хЛ^) и вероятности неизвестны, т.е. Г2=Г\Г, (ш] -

количество классов в Гь тг - количество классов в Г2).

Требуется классифицировать объект с описанием х, т.е. отнести объект к одному из классов множества Г на основе анализа его описания.

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

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

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

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

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

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

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

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

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

1) по правилу БС выбрать класс из группы классов Г;

2) если выбранный на предыдущем этапе класс принадлежит группе

Г„

то из группы Г] выбрать класс с максимальной вероятностью P(wj/x) и к полученному классу отнести предъявленный к классификации объект,

иначе предъявленный к классификации объект отнести к классу, выбранному правилом БС на предыдущем этапе.

Найдена асимптотическая оценка условной вероятности ошибки классификации по схеме 1 при неограниченном объеме обучающей выборки:

P(eSI / х) = 1 - £ P2(wj / х) - Р( w / х) ■ £ Р( w, / х),

Ti Г,

где w = arg max P(w,/x). w.er,

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

Отмечено, что эти вероятности совпадают только в случае, если условные вероятности P(Wj/x) для классов из группы Ti равны, что случается довольно редко. В остальных же случаях вероятность ошибки классификации по схеме 1 меньше вероятности ошибки классификации правила ближайшего соседа.

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

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

1) из группы Г1 выбрать группу классов П;

2) из группы Г2иП выбрать класс по правилу БС и к полученному классу отнести предъявленный к классификации объект.

Найдена асимптотическая оценка условной вероятности ошибки классификации по схеме 1 при неограниченном объеме обучающей выборки:

г2<_п

Сформулирован алгоритм Аорт формирования группы О. Алгоритм Аорт-

шаг 0. Сформировать группу 0 = Г^ \/х)< /х)| (1),

где ш - количество классов в Г, а вероятности Р(лук/х) вычисляются по формуле Баиеса:

¿Р^О-РСх/уу,)

шаг 1. Найти класс \v, = arg min P(w=/x).

w.eft 1

i=i

г

шаг 2. Если Р(уу,/х)<Г^Р - - (2),

то £2=П\{лу,} , перейти к ша1"у 1, иначе перейти к шагу 3. шагЗ. Конец,

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

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

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

Схемы классификации 1 и 2 сравнены между собой. Показано, что достаточного условия того, что классификация по схеме 2 приведет к вероятности ошибки не большей, чем вероятность ошибки классификации по схеме 1, в рассматриваемом случае получено быть не может. Исключение составляет лишь совсем тривиальный случай, когда вероятности появления классов из группы Г! равны между собой. В этом случае асимптотические вероятности ошибки классификации по схемам 1 и 2 совпадают и равны асимптотической вероятности ошибки классификации по правилу ближайшего соседа. Однако, получено достаточное условие того, что классификация по схеме 2 приведет к не меньшей вероятности ошибки, чем при классификации по схеме 1:

-В + а/В2-4-А-С , V-. . ...

-—-С3)'

где

А=к- аке[1/ш2;1];

г,\п

В = £ Р2^,х)- £ Р(№„х)-Р(\у, х); п г,

п п

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

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

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

Сформулирована схема классификации 2, годная для практического применения, которая состоит из следующих двух этапов:

1) Из группы Г| выбрать группу классов Г2 по алгоритму А: шаг 0. Сформировать группу

n = rj\

1

1

m2 m2+m2-£kj

шаг 1. Найти класс w, = arg min k .

Wjm J

шаг 2. Если выполняется одно из двух неравенств:

В2 -4-А-С^О или

В — л/в2 -4-А-С

2-А

>1,

где

г> г) пь

п

В = —+kt, т2

С = —,

т2

то П:=0\(\у,} , перейти к шагу 1,

иначе перейти к шагу 3. шагЗ. Конец.

2) По правилу ближайшего соседа выбрать класс из классов группы Г2 и оставшихся в группе О. К полученному классу и отнести предъявленный объект.

Применение алгоритма А вместо алгоритма Аорт сохраняет свойство классификации по схеме 2 с алгоритмом Аорт - не превышать вероятности ошибки правила ближайшего соседа.

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

1) из группы Г| выбрать группу классов П;

2) из группы Г2иП выбрать класс по правилу БС;

3) если выбранный на предыдущем этапе класс принадлежит группе

П,

то из группы П выбрать класс с максимальной вероятностью Р(ууД) и к полученному классу отнести предъявленный к классификации объект,

иначе предъявленный к классификации объект отнести к классу, выбранному правилом БС на предыдущем этапе.

Схема 3 является комбинацией подходов, использованных в схеме 1 и схеме 2.

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

Р(с,2/х) = 1-

Г, о

Г2иП

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

■ъТ-,

1 »«

0 , если

I?_

Г, Г,

< Р(й^х)

а Р(\у,х)

Г,

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

шах

Р(И),Х)1 «^Г, /

Р(е*).

Показано, что схема 1 является частным случаем схемы 3 .когда

П=Г,.

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

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

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

Тестирование производилось на следующей модели. Число классов равно 9. Описание объекта состоит из 3 признаков. Условный закон распределения описания объектов для каждого класса - многомерный нормальный закон распределения. Признаки независимы. Стандартное отклонение для каждого признака из каждого класса равна 1. Объем обучающей выборки для каждого класса равен 100. Центры первых 8 классов расположены в вершинах куба со стороной 4, а центр последнего класса совпадает с центром куба. Предполагается, что число классов с известными законами распределения изменяется от 2 до 8. Предполагается, что классы с известными законами распределения расположены в начале.

Элементарный тест заключается в следующем:

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

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

а) разыгрывается класс, к которому принадлежит классифицируемый объект;

б) разыгрывается описание объекта, т.е. реализация системы случайных величин, подчиненных условному закону распределения для «выпавшего» класса.

3. Полученное описание классифицируется тестируемым правилом.

Полученное решение по каждому из правил сравнивается с истинной

принадлежностью классифицируемого объекта.

Элементарный тест повторяется 100000 раз.

Вероятность ошибки оценивалась отношением числа ошибок классификации, допущенных классификатором, к общему числу элементарных тестов 100000.

Кроме того, для демонстрации относительного уровня ошибки классификации на ряду со схемами 1 и 3 тестируются «идеальный классификатор» (байесовская решающая процедура, в предположении, что все законы распределения известны) и правило БС.

На рисунке 1 тест выполнен в предположении, что вероятность появления первого класса равна 0.9, а остальных равновероятна, т.е. по 0.0125. На рисунке 2 тест выполнен в предположении, что вероятность появления последнего класса равна 0.9, а остальных равновероятна, т.е. по 0.0125. На рисунке 3 тест выполнен в предположении, что вероятности появления всех классов равновероятны, т.е. по 1/9.

Анализ результатов тестирования показывает, что:

1) по мере увеличения количества классов, для которых известны их вероятностные характеристики вероятность ошибочной классификации по схемам 1 и 3 постепенно уменьшается от вероятности ошибки классификации правила БС к вероятности ошибки классификации байесовского решающего правила (наиболее выразительны в этом смысле результаты, приведенные на рис. 3);

2) в некоторых случаях (рис. 1) вероятность ошибочной классификации больше по схеме 3, чем по схеме 1, а в других ( рис. 2) -наоборот.

0,16 0,14 0,12 0,10 0.08 0,06 0,04 0,02 0,00

2 3 4 5 6 7 8

----байесовское правило---схема 1

.....схема 3 -правило БС

Рис.1

0,36

0,30

6

8

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

Рис. 2

----байесовское правило---схема 1

.....схема 3 -правило БС

Рис. 3

Таким образом, вероятности ошибки классификации по схемам 1 и 3 в каждом конкретном случае зависят от законов распределения классов и от количества классов, для которых известны их вероятностные характеристики.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Для всех трех схем получены асимптотические оценки вероятностей ошибочной классификации в случае неограниченного объема обучающей выборки.

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

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

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

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

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

9. Отмечено, что классификация по схеме 1 является частным случаем классификации по схеме 3, когда П=Г1.

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

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТЫ

1. Нагаев И.М. Об одной группе алгоритмов распознавания образов, применимых в случае неполной информации о вероятностных характеристиках классов // Математическое моделирование в решении научных и технических задач. Уфа: Издательство научно-производственной фирмы "Технология". 1994. - С.37-40.

2. Нагаев И.М. Об одной схеме классификации объектов при неполной информации о вероятностных характеристиках классов // 2-я Всероссийская с участием стран СНГ конференция "Распознавание образов и анализ изображений: новые информационные технологии". Тезисы докладов. Ульяновск. 1995, ч. 1. - С.62-64.

3. Нагаев И.М. Классификация при различной информации о вероятностных характеристиках классов // Материалы IV Всероссийской конференции "Повышение эффективности средств обработки информации на базе математического и машинного моделирования", Тамбов, 1995. -С.304-305.

4. Нагаев И.М. О применении комбинированного классифицирующего правила для обработки аэрокосмической информации // Материалы конференции "Проблемы экологического мониторинга", Уфа 1995, ч. 2. -С. 371-374.

5. Нагаев И.М. Об использовании комбинированного классифицирующего правила в автоматизированных системах и системах искусственного интеллекта // Всероссийская молодежная научно-техническая конференция "Информационные и кибернетические системы управления и их элементы". Тезисы докладов. Уфа, 1995. - С. 8-9.

6. Нагаев И.М., Орехов Ю.В. Классификация при неполной информации о вероятностных характеристиках классов. Уфа: Издательство научно-производственной фирмы "Технология". 1996 - 43 с.

7. Нагаев И.М. О применении комбинированного правила классификации // Принятие решений в условиях неопределенности. - Уфа: УГАТУ, 1996. - С.146-149.

Введение.

1. Классификации при вероятностно-статистическом подходе к распознаванию образов.

1.1. Байесовское решающее правило.

1.2 Минимаксное решающее правило.

1.3. Правило ближайшего соседа.

1.3.1 Вероятностно-статистическая модель для правила ближайшего соседа.

1.3.2. Достоинства и недостатки правила ближайшего соседа.

2. Классификация в случае неполной информации о вероятностных характеристиках классов.

2.1. Первая схема классификации.

2.1.1. Общая схема правила.

2.1.2. Оценка вероятности ошибки.

2.1.3. Сравнение оценок вероятностей ошибок классификации по схеме 1 и по правилу ближайшего соседа.

2.2. Вторая схема классификации.

2.2.1. Общая схема правила.

2.2.2. Оценка вероятности ошибки.

2.2.3. Алгоритм формирования группы О, минимизирующий оценку вероятности ошибки.

2.2.4. Сравнение оценок вероятностей ошибок классификации по схеме 2 и по правилу ближайшего соседа.

2.2.5. Сравнение оценок вероятностей ошибок классификации по схеме 1 и схеме 2.

2.2.6. Использование схемы 2 в случае неполной информации о вероятностных характеристиках классов.

2.2.6.1. Достаточное условие для выполнения неравенства, используемого на шаге 0 алгоритма Аорт.

2.2.6.2. Достаточное условие для выполнения неравенства, используемого на шаге 2 алгоритма Аорт.

2.3. Третья схема классификации.

2.3.1. Общая схема правила.

2.3.2. Оценка вероятности ошибки.

2.3.3. Критерий для формирования группы П.

2.3.4. Сравнение схемы 3 со схемой 2.

2.3.5. Сравнение схемы 3 и схемы 1.

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

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

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

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

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

Пусть х - описание объекта, т.е. совокупность доступной информации об объекте, набор признаков, описывающих объект (в дальнейшем для простоты будем отождествлять объект и его описание), а Г={У1,.,1Ут} -конечное множество классов, на которые разбито все множество объектов.

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

К середине 1970-х годов распознавание образов как самостоятельное научное направление достигло такой стадии развития, что возникла возможность создания математической теории распознавания. Одной из предпосылок явилось выделение и отработка ряда моделей распознавания.

Ключевым моментом при решении задачи распознавания явилось определение признаков, характеризующих объект или явление. Признаки объектов могут быть подразделены на детерминированные, вероятностные, логические и структурные [4].

Детерминированные признаки - признаки, принимающие конкретные числовые значения (например, размах крыла самолета 1=25 м, масса самолета в=70 тит. д.), которые могут рассматриваться в качестве координат точки в признаковом пространстве, соответствующей данному объекту. При рассмотрении признаков в качестве детерминированных ошибками измерений пренебрегают.

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

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

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

Как правило, модели распознавания образов ориентированы и используют только один вид признаков и игнорируют то, что в описании могут быть признаки разных видов. В зависимости от того, на языке каких признаков производится описание объектов, выделяются следующие модели алгоритмов распознавания.

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

Модели, основанные на использовании принципа разделения (Я-модели), различаются главным образом заданием класса поверхностей, среди которых выбирается поверхность (или набор поверхностей), в некотором смысле наилучшим образом разделяющая элементы разных классов [7, 12].

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

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

Логические модели основаны на использовании логики высказываний, в частности, на аппарате алгебры логики (Л-модели). В них классы и признаки объектов рассматриваются как логические переменные, а описание классов на языке признаков представляется в форме булевых соотношений [3, 11].

Структурные модели используются при лингвистическом подходе к распознаванию образов, когда описание объекта рассматривается как цепочка терминальных символов, образующих предложение. Каждому классу соответствует грамматика. Язык, порождаемый грамматикой, состоит из описаний объектов заданного класса. Задача классификации в этом случае сводится к определению принадлежности объекта с заданным описанием одному из языков, порождаемых грамматиками [14].

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

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

Несколько более общий подход реализован в моделях вычисления оценок (голосования) (Г-модели), которые основаны на принципе частичной прецедентное™. Анализируется "близость" между частями описаний ранее классифицированных объектов и объекта, который надо распознать. Наличие близости служит частичным прецедентом и оценивается по заданному правилу посредством числовой оценки; в качестве такого правила может служить и любое правило для классификации, построенное на основе одной из ранее названных моделей. По набору оценок близости вырабатывается общая оценка распознаваемого объекта для класса, которая и является значением функции принадлежности объекта классу [3,5,8,9]. Таким образом, эти модели являются в некотором виде голосованием различных алгоритмов по поводу принадлежности объекта к классу. Наиболее простым примером моделей данного типа является перцептрон [31].

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

• практически любое достаточно сложное явление или процесс в природе содержит в себе некий элемент случайности и, следовательно, вероятностное описание бывает вполне уместно;

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

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

Особый интерес в связи с этим возникает к правилу ближайшего соседа, для которого удалось построить вероятностно-статистическую модель для оценки асимптотической вероятности ошибки классификации при неограниченном объеме обучающей выборки [6,15,16]. Хотя правило ближайшего соседа не предусматривает использования знаний о законах распределения (или виде этих законов распределения) для части классов, тем не менее, созданная вероятностно-статистическая модель может служить предпосылкой для использования этой информации. При этом встает проблема поиска возможных путей применения знаний о законах распределения для части классов в правиле ближайшего соседа.

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

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

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

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

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

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

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

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

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

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

На защиту выносятся следующие основные результаты, полученные в диссертации:

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

2. Три схемы классификации с использованием предложенных подходов.

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

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

Основные материалы диссертации опубликованы в работах автора [33 - 37,40] и в соавторстве [38-39]. В работе [38] диссертантом написаны заключение, подразделы. 2.2, 3.1 и приложение. В работе [39] постановка задачи и определение общих подходов к ее решению и к получению асимптотических оценок вероятности ошибки классификации выполнена совместно с научным руководителем Ю.В. Ореховым, диссертанту принадлежат разработанные схемы классификации, асимптотические оценки вероятности ошибки классификации при применении разработанных схем классификации, алгоритмы формования подмножеств в рамках схемы 2, доказательство их оптимальности, сравнительный анализ разработанных схем классификации и правила ближайшего соседа с точки зрения эффективности классификации и требуемых вычислительных ресурсов.

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

• 2-ой Всероссийской с участием стран СНГ конференции "Распознавание образов и анализ изображений: новые информационные технологии" (1995, г. Ульяновск),

• конференции "Проблемы экологического мониторинга" (1995, г. Уфа),

• Всероссийской конференции "Повышение эффективности средств обработки информации на базе математического и машинного моделирования" (Тамбов, 1995),

• Всероссийской молодежной научно-технической конференции "Информационные и кибернетические системы управления и их элементы" (1995, г. Уфа),

• общегородском семинаре по математическому моделированию (1996, г. Уфа),

• семинарах "Модели искусственного интеллекта" кафедры ВМиК УГАТУ (1994-1996, г. Уфа).

Результаты исследований применялись при выполнении научно-исследовательской работы "Разработка и внедрение математических, программных и аппаратных средств дистанционного мониторинга" (№ гос. регистрации 01.9.60003774) и включены в спецкурс УГАТУ "Распознавание образов".

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

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

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

3. Для всех трех схем получены асимптотические оценки вероятностей ошибочной классификации в случае неограниченного объема обучающей выборки.

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

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

6. Предложен алгоритм А0рт выбора подмножества классов О в рамках схемы классификации 2. Доказано, что алгоритм А0рт минимизирует асимптотическую оценку вероятности ошибочной классификации в рамках схем 2.

7. В связи с невозможностью практического применения алгоритма А0рт, в силу неизвестности вероятностных характеристик для всех классов, предложен алгоритм, использующий вместо неравенств (1) и (2) достаточные условия для этих неравенств.

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

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

10. Отмечено, что классификация по схеме 1 является частным случаем классификации по схеме 3, когда П=Г1.

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

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

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

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

Результаты исследований применялись при выполнении научно-исследовательской работы "Разработка и внедрение математических, программных и аппаратных средств дистанционного мониторинга" (№ гос. регистрации 01.9.60003774) и включены в спецкурс УГАТУ "Распознавания образов".

Заключение

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

2. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974.-415с.

3. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. Некоторые аспекты. М.: Радио и связь, 1985.- 162 с.

4. Горелик А. Л., Скрипкин В. А. Методы распознавания: Учебное пособие для втузов.- 3-е изд., перераб. и доп. М.: Высшая школа, 1989.- 232с.

5. Гуревич И.Б., Журавлев Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания.// Кибернетика. 1974. - № 3. -с. 16-20.

6. Дуда Р., Харт П. Распознавание образов и анализ сцен/Пер. с англ. под ред. В. Л. Стефанюка.-М.:Мир, 1976.-511с.

7. Еремин И.И., Мазуров В.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. - 288 с.

8. Журавлев Ю. И. Экстремальные задачи, возникающие при обосновании эвристических процедур.// Проблемы прикладной математики и механики. М.: Наука, 1971.-е. 67-75.

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

10. Журавлев Ю. И., Гуревич И. Б. Распознавание образов и анализ изображений // Искусственный интеллект В 3-х кн. Кн. 2. Модели и методы: Справочник/ Под ред Д. А. Поспелова - М.: Радио и связь, 1990.- 304с.

11. Ледли Р.С. Программирование и использование цифровых вычислительных машин. М.: Мир, 1966. - 644 с.

12. Ту Дж., Гонсалес Р. Принципы распознавания образов/ Пер. с англ.; под ред Журавлева Ю. И. М.: Мир, 1976. - 511с.

13. Фомин Я. Ф., Тарловский Г. Р. Статистическая теория распознавания образов. М.: 1986. - 263с.

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

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

16. Cover Т. М., Hart P. Е. Nearest neighbor pattern classification. IEEE Trans. Inf. Theory, 1967, IT-13, 21-27.

17. Hart P.E. The condensed nearest neighbor rule. IEEE Trans. Information Theory, May 1968, IT-14, 515-156.

18. Hart P.E. An asymptotic analysis of the nearest neighbor decision rule, Stanford techn. rept. № 1828-2, Stanford electronic laboratories, Stanford, Calif., May 1966.

19. Cover T.M. Estimation by nearest neighbor rule. IEEE Trans. Information Theory, Jan. 1968, IT-14, № 1, 50-55.

20. Patrick E.A., Fischer F.P. Generalized k nearest neighbor decision rule. J. Information and control, 16, № 2, 128-152, April 1970.

21. Hellman M.E. The nearest neighbor classification rule with reject option, presented at IEEE International Convention on Information theory, Nourwisk, Holland, June 1970.

22. Патрик Э. Основы теории распознавания образов. М.: Советское радио, 1980-408 с.

23. Лапко А.В. Непараметрические методы классификации и их применение. Новосибирск: ВО Наука, Сибирская издательская фирма, 1993.- 152 с.

24. Wojciechowski T.J. Nearest neighbor classification rule for mixtures of discrete and continuons random variable. Journal of Mathematical methods in Biosciences. 1987. - 2, № 8. - 953-959.

25. Psaltis D., Snapp R.R., Venkatesh S.S. On the finite sample performance of the nearest neighbor classifier. IEEE Trans. Inf. Theory. - 1994. - 40, № 3. - 820-837.

26. Smith S.J., Boargoin M.O., Sims K., Voorhees H.L. Handwritten character classification using neighbor in lage database. IEEE Trans. Pattern Anal, and Mach. Intell. - 1994. - 16, № 9. - 915-929.

27. Trionas P.G., Tsalides P.G.Thanailakis A. A new, cellullar automation-based, the nearest neighbor pattern classifier and its VLSI implementation. -IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 1994. - 2, № 3. - 343-353.

28. Распознавание образов: состояние и перспективы: Пер. С англ./ Верхаген К.,Дейн Р., Грун Ф. И. и др. М.: Радио и связь, 1985.- 104 с.

29. Розенблатт Ф. Принципы нейродинамики.- М.: Мир, 1965.- 480 с.

30. Гусейнов П.М., Колесник М.И., Пятибрат Т.В., Сысоева Е.И., Усиков Д.А. Методы статистической классификации многозональнойвидеоинформации с обучением по тестовому участку/ Исследование Земли с Космоса, № 4, 1987.

31. Нагаев И.М. О применении комбинированного классифицирующего правила для обработки аэрокосмической информации // Материалы конференции "Проблемы экологического мониторинга", Уфа: 1995, ч 2, с 371-374.

32. Нагаев И.М., Орехов Ю.В. Классификация при неполной информации о вероятностных характеристиках классов. Уфа: Издательство научно-производственной фирмы "Технология". 1996 - 43 с.

33. Нагаев И.М. О применении комбинированного правила классификации // Принятие решений в условиях неопределенности Уфа: УГАТУ, 1996.-С.146-149.