Содержание к диссертации
Введение
1. Анализ известных методов диагностики состояния радиотехничечской системы без отключения из рабочего режима .
1.1. Известные методы диагностики состояния, параметрическое оценивание 13
1.2. Модели сигналов используемых при диагностических исследованиях для предварительного обучения системы диагностики 17
1.3. Анализ методов теории распознавания образов, применяемых для решения задач диагностики 26
1.4. Методы распознавания, основанные на теории статистических решений Выводы по материалам первой главы 36
2. Постановка задачи диагностики и анализ структуры радиотехнической системы .
2.1. Постановка задачи диагностики 38
2.2. Анализ структуры радиотехнической системы с учётом системы диагностики сё состоянии 44
2.3. Рассмотрение методики оценивания параметров системы диагностики 55
2.4. Вопросы оптимизации временных и пространственных параметров диагностической системы 64
Выводы по материалам второй главы 78
3. Разработка алгоритмов параметрического распознавания состояния радиотехнической системы .
3.1. Формирование моделей сигналов различных классов для оценки значении признаков каждого класса 80
3.2. Выбор вектора признаков для распознавания состояния системы 84
3.3. Выбор и обоснование разделяющих поверхностен и решающих правил 88
3.4. Исследование влияния размерности вектора признаков на эффективность классификации 100
Выводы но материалам третьей главы 105
4. Исследование алгоритмов параметрической классификации с целью диагностики состояния системы .
4.1. Методы моделирования устройств обработки сигналов 107
4.2. Моделирование работы системы диагностики 112
4.3. Моделирование алгоритмов параметрического распознавания 124
4.4. Сравнительный анализ показателей качества алгоритмов параметрической классификации 128
4.5. Оценка статистической погрешности результатов моделирования 133
4.6. Определение вероятности ошибок но классам 138
Выводы по материалам четвёртой главы 141
Заключение 143
Литература
- Модели сигналов используемых при диагностических исследованиях для предварительного обучения системы диагностики
- Анализ структуры радиотехнической системы с учётом системы диагностики сё состоянии
- Исследование влияния размерности вектора признаков на эффективность классификации
- Сравнительный анализ показателей качества алгоритмов параметрической классификации
Введение к работе
Актуальность темы:
Одним из основных направлений радиоэлектроники, которое предназначено для сбора и обработки информации на основе приема искусственных и естественных радиоизлучений является радиоконтроль (РК).
Для обеспечения высоких оперативности и достоверности РК все более широкое применение находят методы пространственно-временной обработки информации при решении таких задач как поиск, обнаружение, разрешение, пеленгование, определение местоположения источников радиоизлучений (ИРИ).
Для решения большинства из перечисленных задач РКвозникает необходимость в использовании многоканальных технических средств. К числу основных устройств, определяющих основные характеристики многоканальных технических средств, следует отнести фазированные антенные решетки (ФАР) и многоканальные супергетеродинные приемные устройства (МСПУ).
Вопросы построения одноканальных супергетеродинных приемных устройств в интересах РК в настоящее время хорошо отработаны как в теоретическом, так и практическом планах.
Однако при построении МСПУ состояние как теории, так и практики не в полной мере удовлетворяет требованиям настоящего времени. При этом одной из наиболее актуальных проблем является задача устранения неидентичности характеристик каналов МСПУ за счет неидеальности аппаратурной реализации и влияния климатических и механических воздействий.
Широко используемые в настоящее время пути решения данной задачи связаны: 1) с использованием схемотехнических и конструкторско-технологических приемов, 2) а также с использованием методов диагностики состояния радиотехнической системы (РТС) в рабочем режиме.
Первый из вышеперечисленных путей является малоперспективным, поскольку требует создания прецизионной аппаратуры в условиях, когда темпы достижений в области схемотехники и технологии отстают от темпов ужесточения технико-эксплуатационных требований к МСПУ.
Второй путь широко используется и приводит к решению поставленной задачи, но только в условиях стационарной радиообстановки при невысоких требованиях к пропускной способности комплекса радиоконтроля (КРК). КРК в настоящее время как обязательную составную часть аппаратуры включают в себя диагностические средства (комплексы).
Среди известных работ, посвященных данной тематике, можно выделить направление, использующие принцип разделения во времени режимов работы и измерения (контроля), отражённые в работах В.А.Долгова, А.С.Касаткина, В.Н.Сретенского, В.Д. Кудрицкого и других. Существенным недостатками разделения во времени режимов работы и контроля является снижение готовности КРК, потеря информации о РО на период проведения контроля, уменьшение достоверности контроля из-за получения оценок в КРК и диагностической системе эпизодически. Жёсткие требования к готовности и надёжности современных КРК обуславливают переход к распараллеливанию выполнения задач диагностики и работы.
Вопросам построения диагностических систем, позволяющих классифицировать состояния РТС в рабочем режиме, в литературе уделено недостаточно внимания. Данные обстоятельства указывают на необходимость разработки и анализа моделей систем диагностики состояния РТС без использования режимов разделения во времени.
Таким образом, тема диссертации, посвященная компьютерному моделированию и анализу алгоритмов диагностики состояния радиотехнических систем в рабочем режиме, является достаточно актуальной.
Целью работы является:
Построение математических моделей алгоритмов диагностики состояния линейной системы в рабочем режиме; формирование набора эффективных признаков, используемых в устройствах классификации состояния линейных трактов; исследование возможности оптимизации временных и пространственных параметров классификаторов состояний линейных систем.
Основные задачи диссертации вытекают непосредственно из её цели:
1. Формирование и обоснование системы эффективных признаков используемых в моделях алгоритмов классификации состояния линейной системы без отключения из рабочего режима.
2. Синтез и обоснование решающего правила для классификатора состояния линейной системы.
3. Исследование возможности оптимизации временных и пространственных параметров классификаторов состояний линейной системы.
4. Построение модели диагностической системы и экспериментальная проверка качества диагностики на её основе.
5. Разработка пакета программ для экспериментального исследования предложенных моделей и методов.
Решение поставленной задачи проводится в несколько этапов:
1. Определение моделей сигналов РТС
2. Разработка алгоритма формирования классификационных признаков.
3. Исследование влияния времени обучения и распознавания и размерности признакового пространства на показатели эффективности классификатора.
4. Экспериментальное исследование показателей качества разработанных алгоритмов при классификации математических моделей сигналов РТС.
Научная новизна. В работе получен ряд новых результатов, которые сводятся к следующему:
1. Разработана методика формирования системы признаков на основе корреляционного метода измерения импульсной характеристики модели линейного тракта радиотехнической системы.
2. Предложена методика диагностики состояния модели линейного тракта радиотехнической системы без отключения её из рабочего режима.
3. Разработан комплекс программ математического моделирования диагностики состояния линейной системы в рабочем режиме.
4. Выявлены закономерности показателей эффективности классификатора от времени обучения и распознавания, от размерности признакового пространства.
Практическая ценность состоит в возможности использования результатов работы для решения практических задач техники и науки:
– определены условия целесообразности использования предложенных алгоритмов в компьютерных системах диагностики состояния РТС;
– обеспечено получение улучшенных точностных характеристик при использовании программ параметрической классификации шумоподобных сигналов.
Реализация результатов работы. Результаты, полученные в работе, были использованы в учебном процессе при проведении лабораторных работ, курсовом проектировании по дисциплинам: “Устройства приёма и преобразования сигналов”, “Радиоприёмные устройства сверхвысоких частот”, “Основы компьютерного проектирования” на кафедре Радиоприёмных устройств и Телевидения Технологического института Южного федерального университета.
Результаты, полученные в кандидатской диссертации, реализованы в разработках отдела 24 НКБ моделирующих и управляющих систем ЮФУ (г. Таганрог) в рамках х/д 324057 при создании радиолокационного измерителя характеристик морского волнения (РИВ200), предназначенного для снабжения гидросамолёта Бе-200.
Методы исследования основаны на использовании численных методов, методов теории вероятности и математической статистики, статистической теории распознавания образов, функционального анализа.
Основные положения, выносимые на защиту, следующие:
- математические модели сигналов линейных трактов радиотехнических систем;
- алгоритм формирования системы эффективных признаков на основе корреляционного метода измерения импульсной характеристики линейной системы;
- зависимости дисперсий оценок признаков и ошибки распознавания от времени обучения, размерности признакового пространства;
- результаты моделирования разработанных алгоритмов диагностики состояния линейных трактов без отключения из рабочего режима.
Апробация работы. Основные положения диссертационной работы обсуждались и докладывались:
-на VIII Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, ТРТУ, 2006 г.)
- на международной научной конференции «Статистические методы в естественных, гуманитарных и технических науках».(Таганрог, ТРТУ, 2006 г.)
- на LII научно-технической конференции.(Таганрог, ТРТУ, 2006 г.)
- на 6-й Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных «Молодёжь XXI века–будущее Российской науки» (Ростов на Дону, ЮФУ, 15 мая 2008г.)
- на Всероссийской научно-технической конференции с международным участием: “Компьютерные и информационные технологии в науке, инженерии и управлении”«КомТех-2008»( Таганрог, ТТИ ЮФУ, 6.06.2008)
Публикации. Основные научные результаты диссертации опубликованы в 5-ти статьях, 3-х тезисах докладов.
Структура диссертации. Диссертационная работа состоит из введения, четырёх разделов, заключения и приложений, включающих 5 наименований.
Работа изложена на 151 стр. текста, 36 рисунках, 7 таблицах, списка литературы из 114 наименований и приложений.
Модели сигналов используемых при диагностических исследованиях для предварительного обучения системы диагностики
Развитие средств автоматизации, переход к новым методам управления производством выдвинули целый ряд новых задач, успешное решение которых требует и новых методов обработки информационных потоков, которые учитывали бы свойства, законы и динамику процессов, протекающих в системах.
Развитие науки и техники происходит по пути усложнения процессов и систем. В связи с этим усложняются естественные и искусственные сигналы как переносчики информации о процессах и системах. Особенно резко возрастает сложность человеко-машинных информационных и управляющих систем, играющих все более важную роль в производстве, разработках и исследованиях. Следует отметить, что усложнение функций информационных и управляющих систем, улучшение их качественных характеристик должно производиться наиболее экономным образом, в соответствии с общим направлением развития общества (страны) [1]. В связи с этим все более актуальной становится задача оптимизации систем управления и информационных систем и, следовательно, задача оптимального построения моделей управляющих сигналов в системах.
В частности, возникает необходимость в разработке простых, эффективных и достаточно надежных методов диагностики (распознавания) объектов и систем по текущей информации о выходных сигналах. Это сводится к выбору определяющих параметров-признаков, подлежащих измерению и контролю, и методов обработки полученной информации.
Обзор имеющихся публикаций показывает, что к настоящему времени предложено довольно большое число методов диагностики сигналов и образов. Однако практическая реализация их наталкивается на значительные трудности, суть которых в следующем:
Определение текущих значений параметров объектов требует в большинстве случаев множества косвенных измерений и последующей, их обработки. При достаточно большом числе параметров объем вычислений велик, а сам процесс . обработки настолько громоздок, что даже применение средств вычислительной техники не позволяет существенно уменьшить неизбежные потери времени на обработку исходной информации, исключая тем самым возможность получения результатов контроля в реальном масштабе времени.
При разработке диагностических систем указанное затруднение стараются обойти путем упрощения вычислительных операций, либо ограничением числа контролируемых параметров, либо использованием для вычислений приближенных зависимостей вместо точных формальных выражений, связывающих величины косвенных измерений с параметрами объекта. И в том и в другом случаях вносится элемент неопределенности в процесс диагностирования, что снижает достоверность диагностики и приводит к существенным экономическим потерям.
Из сказанного следует, что при решении задач диагностирования выходных сигналов функциональных систем основной задачей является выбор такого метода диагностики, который позволил бы получать достоверные результаты при достаточно простой технической реализации.
Несмотря на несомненную актуальность проблемы диагностирования (распознавания) сигналов, имеется относительно небольшое (по сравнению с распознаванием геометрических фигур) число работ, посвященных этому вопросу. В основу большинства известных исследований положены методы теории статистических решений при изучении многомерных векторов преобразованных сигналов. Отличаясь стройностью и законченностью теоретических результатов, эти методы обладают и рядом неудобств практического характера, в частности, они требуют обработки большого объема выборок реализаций при эмпирическом определении законов распределения признаков диагностируемых процессов.
Из анализа литературных источников можно заключить, что рассмотренные непараметрические методы (гистограммный, К-ближайших соседей, полигональный, Парзеновского ядра и др.) являются асимптотическими, то есть обеспечивают достаточную точность оценивания только лишь при неограниченном увеличении объема обучающих выборок.
При произвольных (в том числе и малых) размерах выборок эта точность (достоверность диагностирования) становится недопустимо низкой. Учитывая, что оценки вероятностей ошибок диагностирования для непараметрических методов, как правило, отсутствуют, следует заключить, что непараметрическое диагностирование (распознавание) находится еще в начале своего развития [2, 3, 4,5].
Значительно дальше продвинулось параметрическое диагностирование, где разработаны процедуры обучения, принятия решения и понижения размерности признакового пространства. Однако оценки вероятностей ошибок, получающихся при параметрическом диагностировании, являются асимптотическими, то есть справедливыми в редко встречающихся случаях неограниченного возрастания объема обучающих выборок. Подавляющее большинство результатов получено только для двухальтернативного диагностирования, тогда как многие практические задачи принципиально являются многоальтернативными.
Из-за отсутствия оценок вероятностей ошибок или их асимптотического характера в существующих работах мало внимания уделено важной проблеме построения систем статистического диагностирования, а именно, проблеме оптимизации временных и пространственных параметров систем при заданном уровне достоверности диагностирования. Последнее обстоятельство, по-видимому, явилось основной причиной того, что вопросы практических приложений статистического диагностирования в большинстве работ не рассмотрены, либо рассмотрены только лишь в постановочном плане [2,6,7,8]
В то же время стремительно растущие запросы практики ставят новые задачи, которые не могут быть решены на основе традиционных методов и средств либо принципиально, либо вследствие технических и экономических ограничений.
Широкий класс новых задач, порожденных тенденцией усложнения и повышения информационной производительности систем обработки сигналов, связан с переходом от простых сигналов с базой порядка единицы к сложным — с базой - десятки - тысячи, и даже более десяти тысяч.
При приеме сигналов пассивной локации с помощью фазированных антенных решеток требуется обрабатывать сигналы в полосе до нескольких килогерц при длительностях десятки секунд в десятках, сотнях каналов, при этом эквивалентный сигнал будет обладать базой порядка 104 - 106. Следует отметить, что, хотя в приведенном примере определена количественная мера сложности (база сигнала), само понятие сложности является качественным [9] и в рассматриваемых аспектах обусловливает возможность выявления в анализируемых процессах и объектах новых взаимосвязей, обеспечение инвариантности по отношению к любым не вырожденным преобразованиям и многие другие свойства сложных сигналов.
Анализ структуры радиотехнической системы с учётом системы диагностики сё состоянии
Техническая диагностика изучает методы получения и оценки диагностической информации, диагностические модели и алгоритмы принятия решений. Целью технической диагностики является повышение надежности и ресурса технических систем [34].
Задача технической диагностики состоит в определении степени ухода характеристик диагностируемой системы от их номинальных значений по данным измерений ряда косвенных параметров. Одной из важных особенностей технической диагностики является распознавание в условиях ограниченной информации, когда требуется руководствоваться определенными приемами и правилами для принятия обоснованного решения.
Состояние системы описывается совокупностью (множеством) определяющих ее параметров (признаков). Разумеется, что множество определяющих параметров (признаков) может быть различным, в первую очередь, в связи с самой задачей распознавания.
Распознавание состояния системы — отнесение состояния системы к одному из возможных классов (диагнозов). Число диагнозов (классов, типичных состояний, эталонов) зависит от особенностей задачи и целей исследования.
Часто требуется провести выбор одного из двух диагнозов (дифференциальная диагностика или дихотомия); например, «исправное состояние» и «неисправное состояние». В других случаях необходимо более подробно охарактеризовать неисправное состояние. В большинстве задач технической диагностики диагнозы (классы) устанавливаются заранее, и в этих условиях задачу распознавания часто называют задачей классификации.
Так как техническая диагностика связана с обработкой большого объема информации, то принятие решений (распознавание) часто осуществляется с помощью электронных вычислительных машин (ЭВМ).
Совокупность последовательных действий в процессе распознавания называется алгоритмом распознавания. Существенной частью . процесса распознавания является выбор параметров, описывающих состояние системы. Они должны быть достаточно информативны, чтобы при выбранном числе диагнозов процесс разделения (распознавания) мог быть осуществлен. В задачах диагностики состояние системы часто описывается с помощью комплекса признаков. Во многих алгоритмах распознавания удобно характеризовать систему параметрами х,- образующими v-мерный вектор или точку в v-мерном пространстве: X=(xi, Х2, ...xJt ...xj.
В большинстве случаев параметры х, имеют непрерывное распределение. С помощью признака kj получается дискретное описание, тогда как параметр xt дает непрерывное описание. Отметим, что при непрерывном описании обычно требуется значительно больший объем предварительной информации, но описание получается более точным. Если известны статистические законы распределения параметра, то необходимый объем предварительной информации сокращается.
Принципиальных отличий при описании системы с помощью признаков или параметров нет, и в дальнейшем будут использованы оба вида описания.
Как указывалось, в задачах технической диагностики возможные состояния системы - диагнозы Д - считаются известными. Существуют два основных подхода к задаче распознавания: вероятностный и детерминистский. Постановка задачи при вероятностных методах распознавания такова. Имеется система, которая находится в одном из п случайных состояний Д. Известна совокупность признаков (параметров), каждый из которых с определенной вероятностью характеризует состояние системы. Требуется построить решающее правило, с помощью которого предъявленная (диагностируемая) совокупность признаков была бы отнесена к одному из возможных состояний (диагнозов). Желательно также оценить достоверность принятого решения и степень риска ошибочного решения. При детерминистских методах распознавания удобно формулировать задачу на геометрическом языке. Если система характеризуется v-мерным вектором X, то любое состояние системы представляет собой точку в v-мерном пространстве параметров (признаков). Предполагается, что диагноз D, соответствует некоторой области рассматриваемого пространства признаков. Требуется найти решающее правило, в соответствии с которым предъявленный вектор Л (диагностируемый объект) будет отнесен к определенной области диагноза. Таким образом, задача сводится к разделению пространства признаков на области диагнозов.
При детерминистском подходе области диагнозов обычно считаются «непересекающимися», т. е. вероятность одного диагноза (в область которого попадает точка) равна единице, вероятность других равна нулю. Подобным образом предполагается, что и каждый признак либо встречается при данном диагнозе, либо отсутствует.
Вероятностный и детерминистский подходы не имеют принципиальных различий. Более общими являются вероятностные методы, но они часто требуют и значительно большего объема предварительной информации. Детерминистские подходы более кратко описывают существенные стороны процесса распознавания, меньше зависят от избыточной, малоценной информации, больше соответствуют логике мышления человека.
Рассмотрим обобщенную структуру системы автоматизированной диагностики.
Первичные преобразователи (ПП) - это в общем случае устройства, выполняющих однозначное преобразование исходных процессов в электрические сигналы, заключающие в себе информацию о состоянии диагностируемой системы. В некоторых случаях элемент ПП на схеме рис.2.1 может представлять собой отдельную систему, включающую в себя ряд элементов, обозначающих различные процедуры (преобразование сигналов в вид, удобный для дальнейшей обработки).
Исследование влияния размерности вектора признаков на эффективность классификации
При наличии двух или большего числа классов цель выбора признаков состоит в определении таких признаков, которые являются наиболее активными с точки зрения разделимости классов. Разделимость классов зависит не только от распределений объектов в классах, но также и от используемого классификатора [3]. Для упрощения задачи будем искать набор эффективных признаков для классификаторов.
С теоретической точки зрения достоверность классификации является лучшим критерием эффективности признаков. Кроме того, на практике одним из наиболее распространенных критериев является вероятность ошибки, полученная экспериментально; а именно, интуитивно выбрав набор признаков, строят классификатор и экспериментально подсчитывают число ошибок классификаций. Эта процедура является гибкой, не зависит от вида распределения, теоретически позволяет найти оптимальное решение. Кроме того, с точки зрения машинного времени она может успешно конкурировать с процедурами минимизации многих других критериев, которые задаются явными математическими выражениями, но оказываются сложными для минимизации.
Главный недостаток критерия вероятности ошибки заключается в том, что, исключением очень небольшого числа частных случаев, для него не существует явного математического выражения, даже для нормальных распределений вычисление вероятности ошибки требует численного интегрирования.
Будем строить критерий разделимости двух классов в виде [3] c((oi,cOj,y1,...,yn) = c(o)i,tOj,YN) (3.2) N случайных величин yi-..ун используются в качестве признаков. Кроме того, предположим, что лучшей разделимости классов соответствует большее значение критерия. Также желательно, чтобы критерии удовлетворяли следующим требованиям ]: - Монотонная связь с вероятностью ошибки. Обычно трудновыполнимое условие. - Монотонная связь с нижней и верхней границами вероятности ошибки. Качество критерия при этом можно оценить в соответствии с тем, как близко эти границы находятся к вероятностям ошибки.
Инвариантность относительно взаимно однозначных отображений: Вероятность ошибки байесовского классификатора инвариантна относительно любого преобразования, сохраняющего взаимно однозначное соответствие. Аддитивность по отношению к независимым признакам: если YN взаимно независимы, то Следует отметить, что все эти условия являются не обязательными, а желательными.
В литературе предложено несколько критериев: на основе расстояния Бхатачария [3], на основе дивергенции [3, 29], матриц рассеяния [29, 3], на основе понятия внутреннего расстояния множеств [29], минимума энтропии [3,29,44]. Недостатком большинства из этих методов является их сложность и необходимость знания многомерной функции плотности вероятностей признаков.
В работе [22] предложено использование в качестве критерия эффективности к-го признака при классификации классов і и j критерия Фишера где mki, my - математические ожидания к-го признака для і-го и j-ro класса; о /, oji — среднеквадратические отклонения к-го признака для і-го и j-ro класса.
При распознавание двух одномерных нормальных случайных процессов, критерий (3.8) удовлетворяет условиям (3.4), (3.5), (3.6), (3.7). Построим критерий разделимости на основе выражения (3.8) для многомерных нормальных совокупностей. Для признаков имеющих слабую корреляционную связь в качестве критерия разделимости можно предложить N Выражение (3.9) удовлетворяет (3.3-3.7). Выражение (3.9) будем в дальнейшем использовать в качестве критерия разделимости классов.
Преобразование исходных сигналов с целью получения признаков для классификации может быть реализовано в виде вычисления энергетического спектра сигнала или корреляционной функции. В случае исследования гауссовых процессов, включая процессы со случайными параметрами, данные характеристики полностью определяют их статистические свойства, и можно надеяться, что экспериментальные оценки спектра или корреляционных моментов являются той информационной системой признаков, которая обеспечит распознавание сигналов в различных ситуациях.
Так как гипотеза о нормальности распределения выходного сигнала линейной системы предполагает искать систему эффективных признаков в рамках корреляционной теории, — необходимо определить автокорреляционную функцию Ryy(x) выходного процесса y(t). Корреляционные функции выходных сигналов линейных систем могут быть определены из общего выражения, связывающего корреляционную функцию Яуу(т) выходного сигнала y(t) и корреляционную функцию R T) входного сигнала x(t). Учитывая, что в данном случае входной сигнал x(t) — "белый шум", то для линейных систем с постоянными параметрами можно определить корреляционную функцию на выходе системы с точностью до постоянного множителя по её импульсной характеристике. Mr) = G0 ]h(s)h(s + r)dr, (ЗЛО) где GQ — постоянный коэффициент (спектральная плотность мощности шума в заданной полосе), h(x) - импульсная характеристика диагностируемой линейной системы. Корреляционная функция линейной системы весьма информативна и оказывается полезной при определении амплитудной характеристики, затухания и критических частот. Методами анализа Фурье с её помощью получают частотные характеристики.
Сравнительный анализ показателей качества алгоритмов параметрической классификации
Целью данного подраздела является объективное сравнение характеристик предлагаемых алгоритмов и известными алгоритмами параметрической классификации.
В литературе [6] достаточно подробно описаны методы распознавания образов с помощью функций расстояния и их использования для построения оптимальных решающих правил. Выбор функции расстояния в качестве инструмента классификации является естественным следствием того обстоятельства, что наиболее очевидный способ введения меры сходства для векторов образов, интерпретируемых как точки в евклидовом пространстве -определение их близости. Можно рассчитывать на получение удовлетворительных практических результатов при классификации образов с помощью функций расстояния только в тех случаях, когда классы образов обнаруживают тенденцию к проявлению кластеризованных свойств. Классификация образов по критерию минимума расстояния подразумевает несколько случаев: случай единственности эталона, множественности эталонов. Остановимся на правиле классификации, основанном на принципе ближайшего соседа.
Рассмотрим выборку образов с известной классификацией {si5 s2, ..., SN}, причем предполагается, что каждый образ выборки входит в один из классов тх,сог,...,(ом. Можно определить правило классификации, основанное на принципе ближайшего соседа (БС-правило); это правило относит классифицируемый образ к классу, к которому принадлежит его ближайший сосед, причем образ st є {з1,з2,...,5м}называется ближайшим соседом образа х, если где D - любое расстояние, определение которого допустимо на пространстве образов. , Эту процедуру классификации можно назвать 1-БС-правилом, так как при ее применении учитывается принадлежность некоторому классу только одного ближайшего соседа образа х.
Допустим, что классифицируемый образ х принадлежит классу coi. При этом применение 1-БС-правила приведет к ошибке только в том случае, если ближайший сосед образа х входит в класс cOj и, следовательно, расположен в круге Rj. С другой стороны, если образ х принадлежит классу соп а его ближайший сосед находится в круге Rj, то в этом круге должны быть расположены все образы, что абсолютно очевидно из рис. 4.8. Это означает, что вероятность ошибки при применении 1-БС-правила равна в этом случае вероятности . принадлежности всех образов классу d)j, которую можно определить [6]:
Подобным же образом можно определить вероятность совершить ошибку при использовании q-БС-правила. Это правило зачисляет классифицируемый образ в класс, к которому принадлежит большинство его q ближайших соседей.
Поскольку рассматривается случай разделения на два класса, в качестве q можно выбрать нечетное целое число, и следовательно, принцип большинства всегда будет работать.
Допустим, что образ х принадлежит классу сог, и он, следовательно, расположен в круге R,. В таком случае применение г-БС-правила приведет к неправильной классификации только при условии, что в круге І?, находится (q—1)/2 или меньшее количество образов. При этом нельзя располагать большинством, превышающим (q—1)/2 ближайших соседей из круга Rh необходимым для подтверждения правильности зачисления образа х в класс у,. Соответствующая вероятность, являющаяся, по существу, вероятностью ошибки при использовании q-БС-правила, равна сумме вероятностей вхождения 0, 1, 2,..., (q— 1)/2 элементов выборки в круг R,. Следовательно, воспользовавшись уравнением (4.10), получаем выражение для вероятности ошибки gpH использовании q-ЪС-правила:
Сопоставление вероятностей ошибки классификации р„и р„ показывает, что в данном случае 1-БС-правило характеризуется строго меньшей вероятностью ошибки, чем любое q-БС-правило (q Ф 1).
От этого примера можно прийти к общему случаю, указав, что при задании М классов 1-БС-правило работает лучше, чем q-БС-правило (q&l), если все расстояния, разделяющие образы одного класса, меньше всех расстояний между образами, принадлежащими различным классам. Можно также показать, что в случае выборок большого объема (N - оо) и при выполнении некоторых благоприятных условий вероятность ошибки 1-БС-правила заключена в следующих пределах: где рв—байесовская вероятность ошибки. Как будет показано в следующей главе, байесовская вероятность ошибки - наименьшая вероятность ошибки, достижимая в среднем.
Неравенство (4.12) показывает, что вероятность ошибки для 1-БС-правила превышает вероятность ошибки для правила Байеса не более чем в два раза. Это выражение устанавливает теоретические верхний и нижний пределы качества классификации с помощью 1-БС-правила.
С целью получения количественных соотношений, устанавливающих зависимость эффективности непараметрического классификатора, работающего по методу 1-БС, от временных параметров системы было поведено цифровое моделирование. Методом статистических испытаний были получены зависимости вероятности ошибки классификации от количества объектов обучения при фиксированном общем объеме обучающей выборки и с использованием тех же обучающих и контрольных статистик, которые были задействованы в статистическом эксперименте с разработанной моделью классификатора. Алгоритм классификации представлен в приложении 4, графики зависимости Рош(п) -нарис. 4.9 [21].
Анализируя полученные результаты можно сделать следующие выводы: результаты моделирования алгоритма 1-БС подтверждают теоретические выкладки и показывают, что вероятность ошибки для 1 -БС-правила превышает вероятность ошибки для правила Байеса не более чем в два раза. Практическим препятствием для реализации правила 1 -БС является то обстоятельство, что для достижения указанных в (4.12) границ необходимо сохранять в памяти большое число образов, о которых известна принадлежность их некоторому классу. Кроме того, при осуществлении классификации необходимо вычислять расстояния между каждым классифицируемым образом и всеми образами, хранящимися в памяти системы. При больших объемах обучающих выборок это обстоятельство вызывает серьезные вычислительные трудности.
