Принятие решений

ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ

Введение

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

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

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

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

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

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

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

3. Формализация процесса ПР (выбор целесообразного языка).

4. Взаимодействие человека и информационно-логических машин в процессе ПР.

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

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

1. Элементы теории эвристических решений (ЭР)

1.1 Строгие и эвристические методы ПР

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

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

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

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

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

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

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

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

Вся история науки повторяет приведенную схему:

накопление и систематизация знаний,

выработка «чутья» (интуиции),

формализация процесса,

алгоритм принятия решения.

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

1.2 Общая структура процесса принятия решения

Рассмотрим по Л.Д. Фогелю три типа решений, принимаемых человеком: дедуктивные, абдуктивные, индуктивные.

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

y_i=R(x_i),

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

2. Абдуктивные решения (АР) (abducere - отводить) входят как в класс строгих, так и в класс эвристических решений и отличаются большой неопределенностью. АР представляют собой процесс выявления наиболее вероятных исходных утверждений (посылок, причин) из некоторого заключительного утверждения на основе обратных преобразований. АР строятся на основе использования прошлого опыта. Пусть, например, между некоторыми множествами посылок x_i (x_iX) и следствий y_i (y_iY) обнаружена причинно-следственная связь R. Тогда наиболее вероятной причиной появления нового следствия y_i (y_iY) является посылка

x_i = R-¹(y_i).

Если оператор R известен, то известен и обратный оператор R-¹ и абдуктивное решение является строгим. АР часто встречается в науке и повседневном опыте. Пример: определение температуры тела t по длине столбика ртути в термометре l. Установлен физический закон: l=R(t), в практике: t= R^-1 (l). Другие примеры: анализ хозяйственной деятельности предприятия, изучение космических лучей (наблюдаем следствие Y, находятся исходные посылки, причины X).

3. Индуктивные решения (ИР) (inductio - наведение, побуждение) входят в класс эвристических решений, отличаются большой неопределенностью. ИР представляют процесс выявления наиболее вероятных закономерностей, связей, действий, существующих между исходными утверждениями. ИР выявляют оператор R по входным x_i и выходным y_i сигналам,

y_i = R(x_i).

ИР наиболее свойственно мышлению. Ребенок, поставив перед собой задачу построить домик y_i из кубиков x_i, предпринимает некоторые действия R, y_i=R(x_i). К этой же категории решений относятся действия врача при лечении больного, руководителя организации при выполнении задания. Выявляемый этим способом оператор 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₁,…, Хn₁} ?₁,

{Х1₂, Х2₂,…, Хn₂} ?₂, (2.1)

_{…………….}

{Х1_к, Х2_к,…, Хn_к} ?_к.

В распознавании без обучения данное множество объектов

Х⁽ⁿ⁾= {Х₁, Х₂,…, Х_n}

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

При этом возможны два случая: число классов k задано, число классов неизвестно.

В распознавании с частичным обучением нужно выяснить, есть ли среди данных классов объектов ?₁, ?₂,…, ?_к совпадающие (эквивалентные) классы или все они различны.

Классы ?_i, ?_s будем называть эквивалентными, если они состоят из очень близких в некотором смысле объектов (рис. 2.1). Не эквивалентные, различные классы ?_i, ?_s изображены на рис. 2.2.

?_i = ?_s ?_i ?_s

Рис. 2.1 Рис. 2.2

Примеры:

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

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

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

2.2 Условия применимости математических методов классификации

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

Для количественной оценки сходства объектов используют детальное описание их свойств, которые необходимо задать числами. Каждый объект Х_j из данного множества Х⁽ⁿ⁾ задается в виде вектора значений свойств-признаков,

Х_j=(x_j1, x_j2,…, x_jp), j=1, 2,…, n, p1. (2.2)

Получается матрица данных размерностью np,

, (2.3)

номер строки которой - номер объекта, номер столбца - номер признака каждого объекта.

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

Обычной математической основой для классификации объектов являются функции на парах элементов (X_i, X_j), i, j=1,2,…, n, вычисляемые по их признакам. В результате получается матрица сходства r_ij или различия u_ij между всеми возможными парами (X_i, X_j). Эти коэффициенты бывают трех видов.

1. Коэффициенты типа расстояния имеют общий вид

, (2.4)

где x_is - значение s-го признака для элемента X_i, p - число признаков, m - положительное целое число. При m = 1 - манхэттеновское расстояние, при m = 2 - евклидово расстояние.

2. Коэффициент ассоциативности (КА)

a(X_i, X_j)=p_c/p,

p_c - число совпадающих признаков элементов X_i, X_j, p - общее число признаков. КА используется для элементов, представленных в виде двоичного кода или словесных обозначений.

3. Коэффициент корреляции (КК) между векторами X_i, X_j определяет меру их угловой близости и выражается через их нормированное скалярное произведение

 i, j = 1,2,…, n, (2.5a)

или

, i, j =1,2,…, n. (2.5b)

4. Условная вероятность принадлежности элемента X к классам ₁,₂,…,_k, Р (X/_t), t =1,2,…, k, используется в том случае, когда известны, хотя бы приближенно, законы распределения вероятностей значений признаков объектов в каждом классе.

5. Линии регрессии применяются в том случае, когда элементы классов концентрируются вдоль некоторых линий (рис. 2.3), приближенные уравнения которых находятся по данным наблюдениям.

При решении различных задач классификации в зависимости от вида признаков, описывающих классы, используются и различные виды расстояний (метрик) r(X_i, X_j). Но все они должны удовлетворять следующим условиям:

r(X_i, X_j) 0 - неотрицательность,

r(X_i, X_j) = 0 тогда и только тогда, когда X_i=X_j - аксиома тождества,

r(X_i, X_j) = (X_j, X_i) - аксиома симметрии,

r(X_i, X_j) r(X_i, X_s) + r(X_s, X_j) - аксиома треугольника.

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

,

 (2.6a)

- расстояние Махаланобиса, в котором - ковариационная матрица каждого класса, значок «'» обозначает транспонирование, (X_i-X_j) - вектор-строка, (X_i-X_j)' - вектор-столбец. Если матрица диагональная, на главной диагонали ее стоят дисперсии признаков ₁²,₂²,…,_Р², то расстояние Махаланобиса принимает вид

(2.6b)

Далее для проведения классификации математическими методами необходимо задать математическое правило классификации, соответственно связанное с выбранной мерой близости объектов. Поэтому классификация проводится по расстояниям, коэффициентам ассоциативности и корреляции, по вероятностям, по линиям регрессии. Например, при классификации по расстоянию два объекта X_i, X_j относятся к одному классу _s, s{1,2,…, k}, если r(X_i, X_j)r₀, r₀ - заданное пороговое значение расстояния для каждого класса; при классификации по вероятности объект X относят к тому классу _i0, для которого условная вероятность максимальна,

(2.7)

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

2.3 Критерий оптимальной классификации

При проведении классификации данного множества объектов с использованием различных методов и алгоритмов, как правило, получаются различные результаты. Естественно оптимальным вариантом классификации считать тот вариант, который содержит наименьшее число ошибок. Поэтому за критерий качества классификации принимается минимум вероятности ошибки классификации Р_ош. Этот критерий применим лишь в случаях, когда можно найти оценку величины Р_ош. Но во многих ситуациях это невозможно, и тогда при выборе наилучшей классификации используют функционалы качества разбиения, среди которых выделим три основных вида: функционалы от внутриклассовых расстояний Ф(r_ij^(o)), функционалы от межклассовых расстояний U(r_ij⁽⁾), функционалы смешанного типа V(r_ij^(o), r_ij⁽⁾). Как правило, функционалы Ф(r_ij^(o)) минимизируются, а функционалы U(r_ij⁽⁾) максимизируются.

2.4 Основные условия, гарантирующие оптимальную классификацию

Для получения оптимальной классификации необходимо выполнение следующих условий:

Представление объектов в виде p-мерных векторов (р1) должно достаточно полно отражать основные свойства каждого класса. К примеру, если множество наблюдений содержит всю информацию, получаемую с черно-белого телевизора, то при этом невозможно построить алгоритм выделения «красных» входных сигналов.

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

При выборе расстояния (метрики) в пространстве наблюдений (пока неизвестным способом) объекты, относящиеся к одному классу, должны быть близки один к другому. На рис. 2.4, а представлен случай, когда расстояние Евклида неприемлемо, так как существуют точки, для которых внутриклассовые расстояние больше межклассовых, например r(X₁, X₂)>r(X₂, X₃), X₁, X₂₁, X₃₂.

Здесь целесообразно использовать расстояние Махаланобиса (2.6), которое ввиду диагональности ковариационной матрицы примет вид

Для всех точек представленного множества внутриклассовое расстояние Малаханобиса не больше межклассового.

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

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

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

а б

Рис. 2.4

На рис. 2.4 информативным признаком является признак x_2, а неинформативным - x_1. Неинформативный признак не содержит информации о различии классов.

2.5 Алгоритмы классификации в режиме с обучением

Задача классификации в режиме с обучением уже была сформулирована: имеется k классов

k , (2.8)

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

Для простоты и наглядности рассмотрим случай p = 2, k = 2. Пусть классы ₁, ₂ представлены своими обучающими выборками

(2.9)

n₁ - число наблюдений класса _1, n₂ - число наблюдений класса ₂. Новое наблюдение X нужно отнести только к одному классу ₁ или ₂. На рис. 2.5 представлена описанная ситуация.

Зададим на множестве Хⁿ X⁽ⁿ⁾ = расстояние r(X_i, X_j), X_i, X_j X⁽ⁿ⁾, n = n₁ + n₂, и вычислим среднее расстояние от испытуемой точки X до всех точек каждого класса:

,

.

Если имеем

r₁ < r₂, (2.10a)

то наблюдаемая точка X относится к классу ₁. Если

r₂ < r₁, (2.10b)

то точка Х относится к ₂. Если

r₂ = r₁, (2.11)

то точку X можно отнести к любому из имеющихся классов. Уравнение (2.11) есть уравнение границы классов Г. Граница Г делит пространство признаков R на два подпространства R₁ и R_2, которые содержат классы,

, .

Так что, если испытуемая точка X попадает в область R₁ (R₂), то естественно считать, что она принадлежит классу ₁ (₂).

Замечание. Если для испытуемой точки Y (рис. 2.5) имеет место одно из соотношений (2.10), (2.11) но значения r₁ и r₂ очень велики, например больше минимального диаметра классов d_1, d₂ min(r_1, r₂) min(d_1, d₂), то не следует относить ее к одному из данных классов. В этом случае правильным является решение: точка Y представляет новый класс _3. Поэтому для принятия правильного решения по соотношениям (2.10), (2.11) вводится порог r_пор для значений r_1, r_2,

min(r_1, r₂) r_пор,

Например, можно положить

r_пор = min(d_1, d₂), 0,5 < < 1.

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

Классы _{1, 2} представлены своими обучающими выборками (2.9), изображенными на рис. 2.6.

Эталоны классов _{1, 2} - их средние значения определяются по формулам

Корреляция объектов-векторов определяется косинусом угла между ними. Косинус угла между векторами находится из их скалярного произведения:

Отсюда имеем

 (2.12)

Скалярное произведение векторов

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

Вычислив по формулам (2.12), переходят к их сравнению. Если , то элемент X относится к классу ₁. Если , то элемент X относится к классу ₂ (рис. 2.6). Если

, (2.13)

то элемент X можно отнести к любому из классов ₁, _2. Уравнение (2.13) - уравнение границы классов Г.

Решения, получаемые с помощью корреляционного метода, базируются на угловой близости точек X, ?₁, ?₂. Метод полезен, если каждый из углов ₁, ₂, охватывающий подмножества наблюдений из одного класса, мал по сравнению с углом между эталонами (рис. 2.6),

(2.14)

Но если хотя бы одно из соотношений (2.14) не выполняется, то корреляционный метод неприменим, он может дать большие ошибки, так как часть точек из класса ₁ будет отнесена к классу ₂ (рис. 2.7).

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

Регрессионный алгоритм (РА) применяется в случае, когда обучающие выборки классов (2.9) сосредоточены вдоль некоторых линий, называемых линиями регрессий (рис. 2.3, 2.8). Если линии регрессий являются прямыми (рис. 2.8), то зависимость между координатами каждой точки из одного класса (₁ и ₂) можно представить в виде

где _i - отклонение ординаты точки от ординаты точки . Аналогично _j - отклонение ординаты точки от ординаты точки (рис. 2.8).

Каждая прямая регрессии (, ) проходит через средние точки соответствующего класса. Из уравнений (2.15) имеем

Неизвестные коэффициенты a, b и c, d в системах (2.16) определяются методом наименьших квадратов (МНК), минимизирующим сумму квадратов отклонений от каждой прямой регрессии.

Для системы уравнений (2.16a) имеем

. (2.17a)

Для удобства введем обозначение:

. (2.17б)

Минимум функции находится из необходимых условий ее экстремума:

, .

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

(2.18)

Из системы (2.18) легко находятся оценки параметров a и b, являющиеся функциями наблюдений:

, .

Доказано, что при значениях a и b, определяемых из уравнений (2.18), функция (2.17) имеет минимум.

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



Таким образом, получаются уравнения линий регрессий, описывающих классы ₁ и ₂,

_,

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

Если r (X,) < r (X,), то Х относится к классу ₁.

Если r (X,) < r (X,), то X относится к классу ₂.

Если

r (X,) = r (X,), (2.19)

то X можно отнести к любому из классов ₁, ₂. Уравнение (2.19) - уравнение границы классов ₁, ₂, уравнение биссектрис углов между прямыми и . Если линии регрессии и параллельны, то границей классов ₁, ₂ является прямая Г, параллельная прямым , и равноудаленная от них.

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

При в случае линейной регрессии имеем систему уравнений:

, i = 1, 2, …, n₁.

Оценки для неизвестных параметров a₁, a₂, …, a_p находятся методом наименьших квадратов.

Одна из основных задач регрессионного анализа - задание уравнения регрессии

, ,

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

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

2.6 Классификация как задача статистической проверки гипотез

Рассматривается классификация в режиме с обучением. Для простоты и наглядности положим k = 2, p = 2. Классы _{1, 2} представлены своими обучающими выборками (2.9). Кроме того, известен закон распределения вероятностей значений признаков в каждом классе, т.е. заданы функции распределений вероятностей:

, .

Предположим, что

, ,

где f₁(X), f₂(X) - функции плотностей вероятностей в классах _{1, 2} соответственно (рис. 2.10).

Наблюдаемый объект может принадлежать только одному из двух классов ₁ или _2. Необходимо сформулировать правило, по которому вектор X был бы отнесен к ₁ или к ₂ с минимальной вероятностью ошибки классификации P_ош.

В сформулированных выше условиях задача классификации сводится к задаче статистической проверки двух гипотез H₁ и H₂,

,

.

В процессе принятия решения возможны ошибки 1-го и 2-го родов. Вероятность ошибки 1-го рода - вероятность отклонить гипотезу Н₁ в то время, когда она истинна. Вероятность ошибки 2-го рода - вероятность принять гипотезу Н₂ в то время, когда истинной является гипотеза Н₁. Эти два вида ошибок часто неодинаково важны для лица, принимающего решение. Поэтому вводятся цены ошибок 1-го и 2-го рода. Пример из гидролокации: пусть ₁ - множество сигналов, создаваемых подводной лодкой, ₂ - множество других морских сигналов, не создаваемых подводной лодкой. Ошибка 1-го рода - пропустить сигнал подводной лодки (пропуск цели), ошибка 2-го рода - принять морской шум за сигнал подводной лодки (ложная тревога). В этом случае ошибка 1-го рода имеет бoльший вес, чем ошибка 2-го рода.

Пусть c₁ - цена ошибки 1-го рода, c₂ - цена ошибки 2-го рода, ₁ - априорная вероятность класса ₁, ₂ - априорная вероятность класса ₂, ₁+₂=1 (₁ - вероятность того, что любое наблюдение Х₁ без учета функции распределения F₁(X)). Проекция линии пересечения поверхностей f₁(x) и f₂(x) на плоскость R делит ее на две полуплоскости R₁ и R₂,

R=R₁R₂, R₁R₂=.

Тогда, если наблюдаемый вектор XR₁, то X будет отнесен к классу ₁, а если X, то X будет отнесен к классу ₂. Вычислим вероятность правильной и неправильной классификаций вектора X. Если X₁, то вероятность его правильной классификации равна

,

а вероятность его неправильной классификации равна

. (2.20)

Аналогично, если X₂, то вероятности его правильной и неправильной классификации равны соответственно

,

. (2.21)

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

.

Используя выражения (2.20), (2.21), имеем

. (2.22)

Так как

, R₂ = R \ R₁,

то первый интеграл в выражении (2.22) представим в виде

. (2.23)

На основании равенства (2.23) выражение (2.22) преобразуется к виду

.

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

.

Из последнего выражения имеем

,

или

. (2.24a)

Правая часть в (2.24а) - коэффициент подобия

,

который является постоянным для данного выбора с₁, с₂. Если , то Т=1. Если имеет место неравенство (2.24а), то наблюдаемый вектор Х относится к классу ₁. Если выполняется неравенство

, (2.24б)

то наблюдаемый вектор Х относится к классу ₂. Если выполняется равенство

, (2.24в)

то наблюдаемый вектор Х относится к одному из классов ₁, ₂. Уравнение (2.24в) - уравнение границы классов _{1, 2.} Сформулированное решающее правило относится к так называемым правилам Байеса.

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

.

Тогда вектор Х относится к тому классу , для которого значение апостериорной вероятности максимально. (2.7). Это правило не учитывает цен ошибок 1-го и 2-го родов .

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

Если функции неизвестны, то получают их оценки по обучающим выборкам аппроксимационными методами. Распознание базируется на сопоставлении уже полученных оценок для исследуемого объекта Х пространства R по правилам [2.24].

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

.

В этом случае уравнением границы (2.24в) является линейная функция. Прологарифмировав равенство (2.24в),

, (2.25)

и проведя в его левой части умножения матриц, после приведения подобных членов с учетом (2.25) получим линейное уравнение

.

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

.

Неравенство (2.24а) в этом случае принимает вид

Область наилучшей классификации определяется так:

, (2.26а)

. (2.26б)

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

, (2.27а)

, (2.27б)

. (2.27в)

Оценка ковариационной матрицы в (2.27в) получена по двум обучающим выборкам (2.9). Оценки параметров в (2.27) используются в правилах классификации (2.26). Области наилучшей классификации определяются неравенствами

,

.

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

i, s = 1,2,…, k.

Области оптимальной классификации определяются из неравенств



Классификационная функция связана с i-м и s-м классами. Так как каждая такая функция линейна, то область R_i ограничена гиперплоскостями
(рис. 2.11).

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

Для удобства в выражениях (2.26) введем обозначения:

,

Тогда неравенство (2.26) - правило классификации примет вид

,

где X=(x₁, x₂,…, x_p) - симптомы, признаки отдельного пациента, W' - коэффициенты, учитывающие диагностическую ценность признаков. Для исследуемого пациента Х имеем

.

Чтобы отнести пациента Х к одному из классов ₁ (рак) или к ₂ (не рак) достаточно сравнить полученное значение (Х, W') с пороговым значением и принять решение:

₁, если (, W')> a,

₂, если (, W') a.

Значение параметров W, a вычисляются по картам обследования пациентов в поликлинике из класса ₁ и класса ₂.

2.7 Алгоритмы автоматической классификации (АК)

Синонимами термина «автоматическая классификация» будем считать следующие термины: «классификация без обучения, без учителя», «самообучение», «кластерный анализ», «таксономия».

Постановка задачи АК. Имеется множество n объектов

, (2.28)

каждый из которых описан p числовыми признаками

X_j=(x_j1, x_j2, …, x_jp), p1, j = 1, 2,…, n.

Множество (2.28) будем считать выборкой из некоторой генеральной совокупности. Требуется разделить множество X⁽ⁿ⁾ на k классов (k < n) - непересекающихся подмножеств, каждое из которых состоит из элементов с похожими свойствами,

,, i, s {1,2,…, k}.

Выделение классов на множестве X⁽ⁿ⁾ позволяет значительно сократить его описание без большой потери информации. Вместо перечисления всех объектов можно дать список k (k<n) «типичных» или «эталонных» представителей классов, перечислить номера (имена) объектов, входящих в состав каждого класса, их средние или максимальные отличия их свойств от свойств «эталонных». При небольшом числе классов описание данных становится обозримым и легко интерпретируемым.

Алгоритмы АК отличаются друг от друга процедурой группировки и критерием качества классификации. Классы могут иметь различную форму. Классы простой сферической формы можно выделить, пользуясь алгоритмами семейства FOREL, а классы более сложной (произвольной) формы - алгоритмами семейства KRAB, JOINT.

Алгоритмы этого семейства выделяют классы простой сферической формы. Число классов задается исследователем или выбирается автоматически. Для проведения классификации множества X⁽ⁿ⁾ можно использовать евклидово расстояние между объектами. Объекты одного класса попадают в одну гиперсферу с определенным центром и заданным радиусом r₀. Изменяя радиус r₀, можно получить разное число классов k.

При фиксированном радиусе r₀ алгоритм FOREL работает следующим образом. Выбирается произвольная точка X_j X⁽ⁿ⁾, и в нее помещается центр гиперсферы S радиуса r₀, S₀(, r₀). Определяются внутренние точки гиперсферы:

.

Вычисляется центр тяжести внутренних точек

.

Строится новая гиперсфера радиуса r₀ с центром в точке , S₁(, r₀). Находятся внутренние точки гиперсферы S₁ и их центр тяжести

.

Процедура повторяется до тех пор, пока не перестанут изменяться координаты центра тяжести , т.е. до выполнения неравенства r(,), t = 1,2,…, - заданное малое положительное число. При этом гиперсфера останавливается в области локального экстремума плотности точек множества X⁽ⁿ⁾. Внутренние точки остановившейся гиперсферы S_t(^(t), r₀) образуют класс ₁, ₁=^(t). Элементы класса ₁ из дальнейшего рассмотрения исключаются.

Затем выбирается произвольная точка X_iX⁽ⁿ⁾ \ ₁, i{1, 2,…, n}, в нее помещается центр гиперсферы радиуса r₀, и процедура выделения классов повторяется до тех пор, пока все множество X⁽ⁿ⁾ не будет разделено на классы. Очевидно, количество полученных классов k тем больше, чем меньше радиус r₀. Желательное для исследователя количество классов k может быть найдено соответствующим подбором радиуса r₀.

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

, (2.29)

где _S - центр класса _S. Оптимальным вариантом классификации считается тот, при котором функционал Ф(X_j, _S) принимает наименьшее значение. Выбор такого критерия обосновывается распространенными интуитивными правилами «ручной» группировки. Обычно специалисты объединяют в одну группу объекты мало отличающиеся друг от друга или от «типичного» объекта (ближайшего к центру класса).

Из данной выборки (2.28) случайным образом отбирается k объектов, которые принимаются за центры классов, обозначим их через

.

Для каждого выбранного объекта находится ближайший элемент выборки X_ic (ближайший сосед):

.

объединяются в один класс, если расстояние между ними не больше заданного порогового значения r₀. При этом вычисляются новые центры классов. Если это расстояние больше r₀, то выбранный объект образует новый класс. Если расстояние между центрами двух классов меньше другого априорно заданного порогового значения r'₀ (r₀ > r'₀), то соответствующие классы объединяются.

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