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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: Курсовик. Предмет: Менеджмент. Добавлен: 19.11.2010. Сдан: 2010. Страниц: 2. Уникальность по antiplagiat.ru: --.

Описание (план):


ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ
Введение
Теория принятия решений (ТПР) - новое научное направление, объединяющее, казалось бы, далекие друг от друга области научного знания (психологию, нейрофизиологию, биологию, кибернетику, математику и др.).
Проблема принятия решения (ПР) проявилась как научно-практическая задача при построении автоматизированных систем управления (АСУ) в различных отраслях народного хозяйства (промышленности, транспорте, строительстве и др.). При построении АСУ возникла необходимость воспроизведения мыслительных функций мозга на вычислительных машинах, т.е. проблема построения искусственного интеллекта. При этом центром внимания естественно встала проблема выявления и познания механизмов мозга на всех этапах его функционирования (от восприятия к действиям), построение на этой основе непротиворечивых теорий, проверяемых через наблюдение и эксперименты.
В решении проблемы воспроизведения высших мыслительных функций мозга на вычислительных машинах наиболее существенный вклад может дать естественнонаучный, системно-структурированный подход, эффективность которого подтверждалась в разное время выдающимися результатами (синтез мочевины, самосборка некоторых вирусов и пр.). Первоначально проблема ПР рассматривалась как раздел общей теории управления, но постепенно она приобрела самостоятельное значение. Это повлекло за собой выделение и разработку разных уровней и аспектов ПР, а именно: биологических, психологических, кибернетических, нейрофизиологических и т.д. При биологическом подходе к проблеме ПР рассматриваются вопросы функциональной целесообразности и адаптивного поведения живых систем. Психологический аспект принятия решения человеком затрагивает целый комплекс проблем: соотношения процесса ПР с нейрофизиологическим и поведенческим уровнями жизнедеятельности человека.
При кибернетическом подходе к проблеме ПР исследуются принципы функционирования различных систем, принимающих решения (живые системы, системы «человек-машина», коллективы людей, автоматы), рассматриваются подходы к построению кибернетических моделей таких систем.
Заинтересованность представителей различных областей научного знания в разработке теории ПР создает определенные трудности (в каждой науке формируется свой специфический подход к проблеме, используется свой язык, понятийный аппарат и методы исследования). Но, с другой стороны, объединение в рамках общей теории представителей разных наук создает благоприятные условия для плодотворных научных исследований. Существует ряд общих вопросов, требующих совместных исследований специалистами различных областей, к ним относятся:
1. Определение понятия «принятие решения». Специалисты разных наук вкладывают в этот термин различный смысл. Область явлений, о которых можно говорить как о принятии решений, еще не определена достаточно строго.
2. Познание механизмов ПР в деятельности человека и в биологических системах. Изучение поведения биологических систем и целенаправленной деятельности человека должно быть основной линией в разработке проблемы ПР. Существенная роль принадлежит исследованиям коллективных решений, процессов и механизмов ПР группами людей, объединенных совместной деятельностью.
3. Формализация процесса ПР (выбор целесообразного языка).
4. Взаимодействие человека и информационно-логических машин в процессе ПР.
Комплексные исследования по проблеме ПР у нас в стране в течение многих лет возглавлял академик П.К. Анохин.
В этой работе кратко освещены такие разделы ПР, как элементы теории эвристических решений, принятие решений в распознавании образов, общая математическая теория принятия решений с использованием байесовского подхода.
1. Элементы теории эвристических решений (ЭР)

1.1 Строгие и эвристические методы ПР
Среди методов ПР выделяют два основных вида: строгие и эвристические методы. Эффективное использование ЭВМ для решения научно-технических задач основано, главным образом, на ряде допущений, упрощающих представления о моделируемых реальных процессах. Такое абстрагирование позволяет подобрать для рассматриваемого физического процесса адекватную математическую модель, разработать на этой основе соответствующие алгоритмы, составить программу и с помощью ЭВМ получить приемлемое решение. Существенный момент в таком способе решения - простота моделируемого процесса, однозначность решения и точное знание степени его применимости.
Но в ряде случаев трудно, а иногда и невозможно построить адекватную математическую модель исследуемого процесса, что связано с его сложностью, отсутствием необходимой и достаточной информации. При этом всякое упрощение такого процесса, его идеализация, попытка абстрагирования для использования подходящего математического аппарата часто выхолащивает сущность исследуемого процесса и снижает ценность результата.
Между тем человек, встречаясь в своей повседневной практике с подобными задачами, решает их без применения сложных математических средств и без достаточного количества текущей информации. Более того, иногда принимаемые им решения оказываются лучше и эффективнее решений, полученных с помощью математических методов. Эти соображения выдвигают необходимость разработки качественно новых методов решения задач с помощью ЭВМ путем моделирования отдельных сторон процесса творческого мышления человека, методов, обеспечивающих эффективное решение особо сложных задач, в частности, в условиях неполной текущей информации. Такие задачи возникают в экономике, медицине, при исследовании Космоса, где мы имеем дело с функционированием систем, зависящих от многих разнообразных переменных.
Методы решения таких задач в условиях, когда из-за их сложности и недостаточности информации нельзя точно очертить границы их применимости и оценить допустимые ошибки, называются эвристическими.
Эвристические методы предполагают изучение принципов переработки информации, осуществляемой человеком на различных этапах его деятельности при решении конкретной задачи, и построение на этой основе программ, реализуемых на ЭВМ. Этот процесс - эвристическое программирование.
Характерная особенность эвристического программирования - широкое изучение приемов работы человека при решении задач в условиях неполной информации, накопление особенностей о процессах решения аналогичных задач (формирование опыта) и моделирование всего процесса переработки информации человеком путем расчленения его на так называемые элементарные информационные процессы.
Поскольку в основе эвристических методов лежит процедура поиска, эвристическое программирование иногда обеспечивает решение задачи в условиях неопределенности. Однако после выбора перспективного направления следует строгое решение, которое и приводит к окончательному результату. Именно сочетание обоих методов (эвристического и строгого) обусловливает эффективность рассматриваемого процесса в рамках конкретной человеческой деятельности.
Нет резкой и четкой границы между эвристическими и строгими методами. Более того, по мере развития науки многие эвристические методы решения формализуются, приобретают необходимую строгость и переходят в класс строгих. Пример: решение задач кавалером де Мере (XVII в.), эвристические приемы, интуиция которого по отгадыванию очков при игре в кости базировались на наблюдениях. Создание теории вероятностей позволило формализовать этот процесс отгадывания, дало ему количественную оценку. (Задача кавалера де Мере: что вероятнее, при одном бросании четырех игральных костей хотя бы на одной получить единицу или при 24 бросаниях двух игральных костей хотя бы один раз получить две единицы).
Вся история науки повторяет приведенную схему:
накопление и систематизация знаний,
выработка «чутья» (интуиции),
формализация процесса,
алгоритм принятия решения.
Это не означает, что эвристические методы исчерпали себя: с расширением круга наших знаний неизбежно расширяется и область вновь возникающих проблем.
1.2 Общая структура процесса принятия решения
Рассмотрим по Л.Д. Фогелю три типа решений, принимаемых человеком: дедуктивные, абдуктивные, индуктивные.
1. Дедуктивные решения (ДР) (deductio - выведение), входящие в класс строгих, отличаются полной определенностью. ДР представляют собой процесс выведения некоторого заключительного утверждения (следствия) из одного или нескольких исходных утверждений, посылок по некоторому правилу, закону (например, в соответствии с законами логики). Обычная функциональная зависимость, когда по заданному значению аргумента xi и оператору R определяется значение функции
yi=R(xi),
является примером ДР. Дедуктивные решения охватывают широкий класс преобразований, осуществляемых в технике, природе и обществе. При ДР теоретически возможно по заданным операторам и известным значениям входов определить выходные реакции. ДР достаточно подробно описаны в специальной литературе (теория автоматического регулирования, теория конечных автоматов и др.).
2. Абдуктивные решения (АР) (abducere - отводить) входят как в класс строгих, так и в класс эвристических решений и отличаются большой неопределенностью. АР представляют собой процесс выявления наиболее вероятных исходных утверждений (посылок, причин) из некоторого заключительного утверждения на основе обратных преобразований. АР строятся на основе использования прошлого опыта. Пусть, например, между некоторыми множествами посылок xi (xiX) и следствий yi (yiY) обнаружена причинно-следственная связь R. Тогда наиболее вероятной причиной появления нового следствия yi (yiY) является посылка
xi = R-1(yi).
Если оператор R известен, то известен и обратный оператор R-1 и абдуктивное решение является строгим. АР часто встречается в науке и повседневном опыте. Пример: определение температуры тела t по длине столбика ртути в термометре l. Установлен физический закон: l=R(t), в практике: t= R-1 (l). Другие примеры: анализ хозяйственной деятельности предприятия, изучение космических лучей (наблюдаем следствие Y, находятся исходные посылки, причины X).
3. Индуктивные решения (ИР) (inductio - наведение, побуждение) входят в класс эвристических решений, отличаются большой неопределенностью. ИР представляют процесс выявления наиболее вероятных закономерностей, связей, действий, существующих между исходными утверждениями. ИР выявляют оператор R по входным xi и выходным yi сигналам,
yi = R(xi).
ИР наиболее свойственно мышлению. Ребенок, поставив перед собой задачу построить домик yi из кубиков xi, предпринимает некоторые действия R, yi=R(xi). К этой же категории решений относятся действия врача при лечении больного, руководителя организации при выполнении задания. Выявляемый этим способом оператор R неоднозначен, при его определении возможен некоторый произвол, уменьшающийся по мере накопления опыта и рассмотрения решения на нескольких уровнях.
Мозг рассматривается как самоорганизующаяся система и считается, что в его основе лежит иерархия соподчиненных алгоритмов, в которой выделяют три уровня:
нижний - уровень систем условных и безусловных рефлексов,
средний - уровень системы правил процесса обучения,
высший - уровень, формирующий и корректирующий предыдущий уровень.
Эвристические способности человека - результат одновременного обобщения данного события на различных уровнях. При этом решение, полученное на более высоком уровне, доминирует над решением более низкого уровня, отбрасывая его, если оно оказывается неверным, и направляя усилия на поиски новых решений.
Пример: дана последовательность
1, 2, 3,…. (1.1)
Найти следующую цифру этой последовательности. Если эта цифра 4, то имеем 1, 2, 3, 4,…, последовательность целых чисел. Но если будет сообщение «неверно», то возможно решение 1, 2, 3, 5,…, последовательность простых чисел.
Живой организм использует абстракцию того уровня, который порождает модель, адекватную ситуацию, в которой он находится.
Важное значение в теории ЭР представляет исследование элементарных информационных процессов (ИЭИП) на разных уровнях. ИЭИП - факторизация, дробление, программирование мыслительного процесса. Главная задача этого исследования - выявление правил объединения элементарных информационных процессов в сложные программы. Иерархия соподчиненных алгоритмов головного мозга позволяет выделить правила переработки информации, которые обеспечивают формирование целесообразного поведения живого организма при изменении среды. При более детальном рассмотрении внешней среды и ее связей с живым организмом возможно построение формальной модели эвристической деятельности - теории поиска в абстрактном лабиринте, постановки проблемы отбора достоверной и непротиворечивой информации, непосредственно связанной с целью. При этом рассматриваются не только процессы, происходящие в мозге, но и те изменения, которые происходят во внешней среде в результате активных действий живого организма.
Дадим схематическую классификацию рассмотренных видов решений.
ТР

Дедуктивные
решения ДР
Абдуктивные
решения АР
Индуктивные
решения ИР
Теория строгих решений
Теория эвристических решений
1.3 Центральная проблема теории ЭР
Центральное место в теории ЭР занимает проблема опознавания ситуаций и явлений окружающего мира, представляющая собой обобщение частных проблем распознавания образов (РО).
Суть этих проблем: 1) живому организму генетически передается наследственная информация только в общих чертах с чрезвычайно малой степенью организации мозга; 2) в дальнейшем при активном общении с внешней средой тем или иным способом (обучения, проб и ошибок и пр.) происходит некоторая организация мозга, накопление опыта. Эти соображения о работе головного мозга обычно кладутся в основу устройств, предназначенных для РО. Отметим общие черты функционирования устройств по распознаванию образов:
1. Устройство (первоначально с помощью извне, например человека) обеспечивает разбиение рассматриваемых объектов на классы (множества похожих объектов). Сведения о том, по какому принципу в данной задаче необходимо осуществить разбиение на классы, устройство выявляет самостоятельно, обобщая отдельные примеры, предъявляемые ему на стадии «обучения».
2. В процессе «экзамена» устройство производит классификацию новых объектов, а высокая оценка («поощрение», производимое извне) улучшает классификацию.
Положительное решение этой проблемы связано с решением многих актуальных проблем нашего времени (медицинской и технической диагностики, образования понятий и т.д.).
1.4 Краткая история развития ЭР
Первые попытки формализации творческой деятельности относятся к глубокой древности. Созданием формализованных методов решения математических задач занимались ученые древней Греции (Платон, Евклид, Аполоний, Аристей и другие, V-III в. до н.э.).
Позднее попытки создания стройной системы эвристических методов (ЭМ) принадлежат Декарту во Франции, Лейбницу в Германии, XVII в. Известная работа Декарта «Правила для направления ума» представляет интерес и в наши дни.
Далее вопросами формализации творческой деятельности интересовались такие ученые, как Больцано, Гельмгольц (XIX в.), Пуанкаре (XIX-XX вв.), один из авторов теории относительности.
Сложность проблематики, тесная взаимосвязь между точными и общественными науками, отсутствие широких экспериментальных возможностей не позволили этим крупнейшим ученым дать стройное и систематическое изложение ЭМ.
Бурное развитие ЭМ в XX в. связано с созданием и использованием ЭВМ. Быстродействие, гибкая логика, большая память и другие качества ЭВМ обусловливают их успешное применение.
В нашей стране развитие теории ЭМ принадлежит таким ученым, как академики А.И. Берг, В.М. Глушков (проблемы дедуктивного вывода), Д.Е. Охоцимский (проблемы построения роботов), Н.М. Амосов, Л.Г. Кузин (модели личности), Г.С. Поспелов (искусственный интеллект), А.В. Напалков (алгоритмический анализ мозга), В.Н. Пушкин (сопоставление возможностей ЭВМ и человека) и др.
2. Принятие решений в распознавании образов
2.1 Понятие о распознавании образов, классификации
Под распознаванием образов (РО), или классификацией понимается упорядочивание объектов по их схожести, выделение групп объектов с общими свойствами. Под объектами подразумеваются предметы, явления, процессы, ситуации, действия и т.д. Такие термины, как распознавание образов, классификация, кластер-анализ, таксономия, ботриология, будем считать в первом приближении синонимами.
Множество объектов с похожими свойствами соответственно называется образом, классом, кластером, таксоном. Общепринятого строгого определения класса, кластера не существует. Интуитивно ясно, что элементы одного кластера ближе друг к другу в каком-то смысле, чем к другим элементам, не принадлежащим этому кластеру.
РО - научное направление, возникшее около 40 лет назад и получившее бурное развитие в связи с использованием ЭВМ. РО можно считать одной из ветвей кибернетики.
Классификация является фундаментальным свойством всех живых организмов. Если бы живые организмы не были способны собирать сходные раздражители в группы (классы), для которых нужна та или иная реакция, то они были бы плохо приспособлены к выживанию. Поэтому классификация - вполне естественная деятельность всех живых организмов. Пример: все домашние животные разделяют людей на два класса: хозяев, не хозяев.
С другой стороны, классификация - интеллектуальная деятельность высокого уровня, необходимая для понимания природы. Факты и явления должны быть упорядочены прежде, чем мы можем их понять, разработать общие принципы, объясняющие их появление и видимый порядок. Поэтому и утверждается, что классификация - один из фундаментальных процессов в науке и практике.
Примеры:
1. Распознавание слов, произносимых разными дикторами. Здесь класс - одно слово, произносимое разными дикторами (число классов равно числу слов).
2. Распознавание диктора по голосу не зависимо от того, что он говорит. Здесь класс - множество слов, произносимых одним диктором.
3. Распознавание болезни - медицинская диагностика. Здесь класс - множество людей, переболевших одной болезнью. Нового пациента нужно отнести к одному из известных классов (поставить диагноз).
В распознавании образов можно выделить два основных этапа.
1. Обучение - выделение общего образа, класса как совокупности признаков объектов, его составляющих.
2. Распознавание - отнесение объекта к одному из известных классов (классификация).
Различают три основных режима классификации или распознавания:
1. Распознавание с обучением, с учителем.
2. Распознавание без обучения, без учителя или самообучение, автоматическая классификация.
3. Распознавание с частичным обучением.
В распознавании с обучением все классы ?1, ?2,…, ?к заданы, описаны своими характерными признаками. Некоторый объект Х нужно отнести к одному из имеющихся классов. Самое простое описание классов - представление их обучающими выборками:
{Х11, Х21,…, Хn1} ?1,
{Х12, Х22,…, Хn2} ?2, (2.1)
…………….
{Х1к, Х2к,…, Хnк} ?к.
В распознавании без обучения данное множество объектов
Х(n)= {Х1, Х2,…, Хn}
нужно разделить на классы - непересекающиеся подмножества с общими свойствами,
При этом возможны два случая: число классов k задано, число классов неизвестно.
В распознавании с частичным обучением нужно выяснить, есть ли среди данных классов объектов ?1, ?2,…, ?к совпадающие (эквивалентные) классы или все они различны.
Классы ?i, ?s будем называть эквивалентными, если они состоят из очень близких в некотором смысле объектов (рис. 2.1). Не эквивалентные, различные классы ?i, ?s изображены на рис. 2.2.
?i = ?s ?i ?s
Рис. 2.1 Рис. 2.2
Примеры:
1. Медицинская диагностика - распознавание в режиме с обучением. Один класс - признаки какой-то одной болезни. Постановка диагноза новому пациенту - отнесение его к одному из имеющихся классов по совокупности признаков, характеризующих состояние его организма.
2. Классификация людей по внешним признакам, классификация растений, животных - классификация без обучения, в режиме самообучения.
3. Среди множества образцов рукописных текстов выделить образцы, написанные одним и различными почерками, - классификация с частичным обучением.
2.2 Условия применимости математических методов классификации
При разработке методов классификации на ЭВМ необходимо оценить сходство между объектами количественно. Для этого можно использовать мнения людей, что часто применяется социологами. Но непрактично и ненаучно получать оценки таксономического сходства внутри множества объектов с помощью группы субъектов. В научной практике избегают использовать суждения, основанные на большинстве голосов или популярности.
Для количественной оценки сходства объектов используют детальное описание их свойств, которые необходимо задать числами. Каждый объект Хj из данного множества Х(n) задается в виде вектора значений свойств-признаков,
Хj=(xj1, xj2,…, xjp), j=1, 2,…, n, p1. (2.2)
Получается матрица данных размерностью np,
, (2.3)
номер строки которой - номер объекта, номер столбца - номер признака каждого объекта.
От природы основных признаков объекта зависят важные теоретические выводы. Объекты, подлежащие классификации, представлены в пространстве признаков. Формально это признаковое пространство является p-мерным. Но в связи с корреляцией (зависимостью) между признаками оно может быть преобразовано в пространство меньшей размерности.
Обычной математической основой для классификации объектов являются функции на парах элементов (Xi, Xj), i, j=1,2,…, n, вычисляемые по их признакам. В результате получается матрица сходства rij или различия uij между всеми возможными парами (Xi, Xj). Эти коэффициенты бывают трех видов.
1. Коэффициенты типа расстояния имеют общий вид
, (2.4)
где xis - значение s-го признака для элемента Xi, p - число признаков, m - положительное целое число. При m = 1 - манхэттеновское расстояние, при m = 2 - евклидово расстояние.
2. Коэффициент ассоциативности (КА)
a(Xi, Xj)=pc/p,
pc - число совпадающих признаков элементов Xi, Xj, p - общее число признаков. КА используется для элементов, представленных в виде двоичного кода или словесных обозначений.
3. Коэффициент корреляции (КК) между векторами Xi, Xj определяет меру их угловой близости и выражается через их нормированное скалярное произведение
i, j = 1,2,…, n, (2.5a)
или
, i, j =1,2,…, n. (2.5b)
4. Условная вероятность принадлежности элемента X к классам 1,2,…,k, Р (X/t), t =1,2,…, k, используется в том случае, когда известны, хотя бы приближенно, законы распределения вероятностей значений признаков объектов в каждом классе.
5. Линии регрессии применяются в том случае, когда элементы классов концентрируются вдоль некоторых линий (рис. 2.3), приближенные уравнения которых находятся по данным наблюдениям.
При решении различных задач классификации в зависимости от вида признаков, описывающих классы, используются и различные виды расстояний (метрик) r(Xi, Xj). Но все они должны удовлетворять следующим условиям:
r(Xi, Xj) 0 - неотрицательность,
r(Xi, Xj) = 0 тогда и только тогда, когда Xi=Xj - аксиома тождества,
r(Xi, Xj) = (Xj, Xi) - аксиома симметрии,
r(Xi, Xj) r(Xi, Xs) + r(Xs, Xj) - аксиома треугольника.
Кроме отмеченных выше видов расстояний в классификаии используются следующие:
,
(2.6a)
- расстояние Махаланобиса, в котором - ковариационная матрица каждого класса, значок «'» обозначает транспонирование, (Xi-Xj) - вектор-строка, (Xi-Xj)' - вектор-столбец. Если матрица диагональная, на главной диагонали ее стоят дисперсии признаков 12,22,…,Р2, то расстояние Махаланобиса принимает вид
(2.6b)
Далее для проведения классификации математическими методами необходимо задать математическое правило классификации, соответственно связанное с выбранной мерой близости объектов. Поэтому классификация проводится по расстояниям, коэффициентам ассоциативности и корреляции, по вероятностям, по линиям регрессии. Например, при классификации по расстоянию два объекта Xi, Xj относятся к одному классу s, s{1,2,…, k}, если r(Xi, Xj)r0, r0 - заданное пороговое значение расстояния для каждого класса; при классификации по вероятности объект X относят к тому классу i0, для которого условная вероятность максимальна,
(2.7)
Итак, для проведения классификации объектов математическими методами необходимо составить их описание числовыми признаками, задать меру их близости и правило классификации.
2.3 Критерий оптимальной классификации
При проведении классификации данного множества объектов с использованием различных методов и алгоритмов, как правило, получаются различные результаты. Естественно оптимальным вариантом классификации считать тот вариант, который содержит наименьшее число ошибок. Поэтому за критерий качества классификации принимается минимум вероятности ошибки классификации Рош. Этот критерий применим лишь в случаях, когда можно найти оценку величины Рош. Но во многих ситуациях это невозможно, и тогда при выборе наилучшей классификации используют функционалы качества разбиения, среди которых выделим три основных вида: функционалы от внутриклассовых расстояний Ф(rij(o)), функционалы от межклассовых расстояний U(rij()), функционалы смешанного типа V(rij(o), rij()). Как правило, функционалы Ф(rij(o)) минимизируются, а функционалы U(rij()) максимизируются.
2.4 Основные условия, гарантирующие оптимальную классификацию
Для получения оптимальной классификации необходимо выполнение следующих условий:
Представление объектов в виде p-мерных векторов (р1) должно достаточно полно отражать основные свойства каждого класса. К примеру, если множество наблюдений содержит всю информацию, получаемую с черно-белого телевизора, то при этом невозможно построить алгоритм выделения «красных» входных сигналов.
Должны быть заданы представительные (репрезентативные) подмножества наблюдений каждого класса. Если наблюдения, по которым изучаются характеристики класса, не представляют множество других элементов класса, то после обучения будут получены очень неполные (и возможно ошибочные) знания об этом классе и нельзя ожидать хорошего распознавания.
При выборе расстояния (метрики) в пространстве наблюдений (пока неизвестным способом) объекты, относящиеся к одному классу, должны быть близки один к другому. На рис. 2.4, а представлен случай, когда расстояние Евклида неприемлемо, так как существуют точки, для которых внутриклассовые расстояние больше межклассовых, например r(X1, X2)>r(X2, X3), X1, X21, X32.
Здесь целесообразно использовать расстояние Махаланобиса (2.6), которое ввиду диагональности ковариационной матрицы примет вид
Для всех точек представленного множества внутриклассовое расстояние Малаханобиса не больше межклассового.
Для сближения точек каждого класса можно задать преобразование - сжатие пространства к внутренним точкам (рис. 2.4б). Если бы пространство наблюдений было упругим и гибким, как резина, то это преобразование отражало бы характер деформации различных областей пространства, при котором точки одного класса максимально сближаются. Вопрос о выборе наилучшей метрики или наилучшего преобразования, сближающего точки одного класса, остается открытым.
Среди имеющихся решений (вариантов классификации) можно указать наилучшее. В практике оптимальное решение неизвестно, и применяются хорошие решения.
При формировании набора признаков, описывающих классы, предпочтение следует отдавать информативным признакам. Признак называется информативным, если он содержит информацию о различии классов.
а б
Рис. 2.4
На рис. 2.4 информативным признаком является признак x2, а неинформативным - x1. Неинформативный признак не содержит информации о различии классов.
2.5 Алгоритмы классификации в режиме с обучением
Задача классификации в режиме с обучением уже была сформулирована: имеется k классов
k , (2.8)
описанных своими основными признаками, новый объект X нужно отнести к одному из имеющихся классов. Дадим описание нескольких алгоритмов, по которым проводится классификация в этом режиме.
Для простоты и наглядности рассмотрим случай p = 2, k = 2. Пусть классы 1, 2 представлены своими обучающими выборками
(2.9)
n1 - число наблюдений класса 1, n2 - число наблюдений класса 2. Новое наблюдение X нужно отнести только к одному классу 1 или 2. На рис. 2.5 представлена описанная ситуация.
Зададим на множестве Хn X(n) = расстояние r(Xi, Xj), Xi, Xj X(n), n = n1 + n2, и вычислим среднее расстояние от испытуемой точки X до всех точек каждого класса:
,
.
Если имеем
r1 < r2, (2.10a)
то наблюдаемая точка X относится к классу 1. Если
r2 < r1, (2.10b)
то точка Х относится к 2. Если
r2 = r1, (2.11)
то точку X можно отнести к любому из имеющихся классов. Уравнение (2.11) есть уравнение границы классов Г. Граница Г делит пространство признаков R на два подпространства R1 и R2, которые содержат классы,
, .
Так что, если испытуемая точка X попадает в область R1 (R2), то естественно считать, что она принадлежит классу 1 (2).
Замечание. Если для испытуемой точки Y (рис. 2.5) имеет место одно из соотношений (2.10), (2.11) но значения r1 и r2 очень велики, например больше минимального диаметра классов d1, d2 min(r1, r2) min(d1, d2), то не следует относить ее к одному из данных классов. В этом случае правильным является решение: точка Y представляет новый класс 3. Поэтому для принятия правильного решения по соотношениям (2.10), (2.11) вводится порог rпор для значений r1, r2,
min(r1, r2) rпор,
Например, можно положить
rпор = min(d1, d2), 0,5 < < 1.
Этот метод состоит в определении корреляции рассматриваемого объекта с каждым из эталонов, представляющих классы. Эталоны - векторы средних значений элементов каждого класса. Решающее правило: объект X относится к тому классу, для которого коэффициент корреляции наибольший.
Классы 1, 2 представлены своими обучающими выборками (2.9), изображенными на рис. 2.6.
Эталоны классов 1, 2 - их средние значения определяются по формулам
Корреляция объектов-векторов определяется косинусом угла между ними. Косинус угла между векторами находится из их скалярного произведения:
Отсюда имеем
(2.12)
Скалярное произведение векторов
и их модули выражаются через их координаты:
Вычислив по формулам (2.12), переходят к их сравнению. Если , то элемент X относится к классу 1. Если , то элемент X относится к классу 2 (рис. 2.6). Если
, (2.13)
то элемент X можно отнести к любому из классов 1, 2. Уравнение (2.13) - уравнение границы классов Г.
Решения, получаемые с помощью корреляционного метода, базируются на угловой близости точек X, ?1, ?2. Метод полезен, если каждый из углов 1, 2, охватывающий подмножества наблюдений из одного класса, мал по сравнению с углом между эталонами (рис. 2.6),
(2.14)
Но если хотя бы одно из соотношений (2.14) не выполняется, то корреляционный метод неприменим, он может дать большие ошибки, так как часть точек из класса 1 будет отнесена к классу 2 (рис. 2.7).
Корреляционный метод часто применяют при распознании букв машинописного текста.
Регрессионный алгоритм (РА) применяется в случае, когда обучающие выборки классов (2.9) сосредоточены вдоль некоторых линий, называемых линиями регрессий (рис. 2.3, 2.8). Если линии регрессий являются прямыми (рис. 2.8), то зависимость между координатами каждой точки из одного класса (1 и 2) можно представить в виде
где i - отклонение ординаты точки от ординаты точки . Аналогично j - отклонение ординаты точки от ординаты точки (рис. 2.8).
Каждая прямая регрессии (, ) проходит через средние точки соответствующего класса. Из уравнений (2.15) имеем
Неизвестные коэффициенты a, b и c, d в системах (2.16) определяются методом наименьших квадратов (МНК), минимизирующим сумму квадратов отклонений от каждой прямой регрессии.
Для системы уравнений (2.16a) имеем
. (2.17a)
Для удобства введем обозначение:
. (2.17б)
Минимум функции находится из необходимых условий ее экстремума:
, .
Продифференцировав функцию по a и b и приравняв полученные выражения частных производных к нулю, после простых алгебраических операций получим систему и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.