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

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

Введение

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

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

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

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

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

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 и приравняв полученные выражения частных производных к нулю, после простых алгебраических операций получим систему нормальных уравнений

(2.18)

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

, .

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

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

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

,

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

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

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

Если

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

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

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

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

, i = 1, 2, …, n1.

Оценки для неизвестных параметров a1, a2, …, ap находятся методом наименьших квадратов.

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

, ,

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

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

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

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

, .

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

, ,

где f1(X), f2(X) - функции плотностей вероятностей в классах 1, 2 соответственно (рис. 2.10).

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

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

,

.

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

Пусть c1 - цена ошибки 1-го рода, c2 - цена ошибки 2-го рода, 1 - априорная вероятность класса 1, 2 - априорная вероятность класса 2, 1+2=1 (1 - вероятность того, что любое наблюдение Х1 без учета функции распределения F1(X)). Проекция линии пересечения поверхностей f1(x) и f2(x) на плоскость R делит ее на две полуплоскости R1 и R2,

R=R1R2, R1R2=.

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

,

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

. (2.20)

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

,

. (2.21)

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

.

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

. (2.22)

Так как

, R2 = R \ R1,

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

. (2.23)

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

.

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

.

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

,

или

. (2.24a)

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

,

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

, (2.24б)

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

, (2.24в)

то наблюдаемый вектор Х относится к одному из классов 1, 2. Уравнение (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-м классами. Так как каждая такая функция линейна, то область Ri ограничена гиперплоскостями
(рис. 2.11).

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

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

,

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

,

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

.

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

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

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

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

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

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

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

, (2.28)

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

Xj=(xj1, xj2, …, xjp), p1, j = 1, 2,…, n.

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

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

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

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

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

При фиксированном радиусе r0 алгоритм FOREL работает следующим образом. Выбирается произвольная точка Xj X(n), и в нее помещается центр гиперсферы S радиуса r0, S0(, r0). Определяются внутренние точки гиперсферы:

.

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

.

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

.

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

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

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

, (2.29)

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

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

.

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

.

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

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

Этот алгоритм предназначен для выделения классов довольно причудливой формы (рис. 2.12), которые не может выделить ни один из алгоритмов семейства FOREL. На рис. 2.12 человек довольно легко выделит три класса, три таксона. При этом интересно установить, какие критерии качества таксономии он использует, как он определяет наиболее «естественное» число таксонов, их форму и границы. Ответив на эти вопросы, можно составить алгоритм, моделирующий действия человека, проводящего классификацию на плоскости. Естественно предположить, что человек использует некоторую меру близости точек r, считая, что таксономия тем лучше, чем меньше расстояние между точками одного таксона. Он тем увереннее делает таксономию, чем дальше одни группы близких точек отстоят от других групп, т.е. мера взаимной удаленности таксонов тоже играет важную роль.

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

На рис. 2.13 пятая по счету слева точка ближе к четвертой точке, чем к шестой. Однако при разделении этого множества точек на два таксона люди обычно проводят границу Г между четвертой и пятой точками. По-видимому, человек обращает внимание на локальные изменения (скачки) плотности точек .

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

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

а б

Если разрезать k-1 ребер КНП (т.е. удалить их), то будет выделено k таксонов. Мерой близости объектов внутри одного таксона можно считать среднюю длину ребер КНП, соединяющего все точки данного таксона,

, s = 1, 2, …, k,

где - длина i-го ребра, - число объектов в таксоне .Общей мерой близости внутренних точек таксонов будем считать среднюю длину всех внутренних ребер

.

Среднее расстояние между таксонами определяется по КНП как средняя длина ребер, соединяющих таксоны

.

Через КНП определяется и мера локальной «неоднородности» расстояний между точками i. Для каждого i-го ребра длины i фиксируется прилегающее к нему ребро минимальной длины min, тогда

, i {1, 2, …, n - 1}.

Чем меньше i, т.е. чем больше различие в длинах соседних ребер, тем с большим основанием можно считать, что граница между таксонами пройдет по ребру i.

Задается пороговое значение 0 1. Если

i 0, i 1, 2, …, n-1, (2.30)

то граница между таксонами пройдет по ребру i, т.е.

, s1, 2, …, k-1.

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

.

Общий критерий качества в алгоритме KRAB - максимум функционала

. (2.31)

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

Алгоритм КРАВ работает так. Вначале проводится КНП между всеми точками данного множества. Если число таксонов задано, то путем перебора находятся такие k-1 ребер, проведение границ по которым дает максимальное значение функционала V в (2.31).

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

2.8 Предварительное обнаружение классов и оценивание их числа

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

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

Пусть множество Х(n) представляет собой одномерную выборку (р = 1):

(2.32a)

с плотностью вероятности . Упорядочив элементы множества Х(n) по возрастанию

, (2.32б)

получим вариационный ряд (ВР). Значения x(1), x(n) отложим на числовой оси, отрезок [x(1), x(n)] разделим на t равных частей, t 3 (рис. 2.15). Длина каждого полученного отрезка (xi, xi+1), i = 1, 2, …, t равна

.

Пусть ni - число членов ВР (2.32б), попавших в i-й полуинтервал (xi, xi+1), i = 1, 2, …, t. Тогда оценка вероятности pi попадания в i-й полуинтервал случайной величины равна

. (2.33)

Построим в каждом полуинтервале (xi, xi+1), прямоугольник с высотой hi и основанием такой, чтобы его площадь Si,

, (2.34)

была равна в (2.33).

. (2.35)

Из равенств (2.33) - (2.35) имеем

.

Так строится гистограмма плотности вероятности f(x) данных наблюдений, один из видов которой представлен на рис. 2.15. Отметим, что последним из полученных интервалов гистограммы должен быть отрезок [xt, xt+1], xt+1 = x(n), x1 = x(1).

Число интервалов, на которые делится отрезок [x(1), x(n)], задается исследователем. Эти интервалы могут быть разной длины.

При увеличении объема наблюдений n и уменьшении длины интервала гистограмма стремится к функции ,

.

Если исследуемое множество (2.32) состоит из классов, далеко отстоящих друг от друга (рис. 2.16), то его гистограмма имеет достаточно глубокий локальный минимум (ЛМ), изображенный на рис. 2.17.

Пусть ЛМ наблюдается в промежутке [xq, xq+1]. Фиксируются два ближайших к нему максимума, из которых выделяется наименьший, наблюдаемый в промежутке (xu, xu+1). Далее исследуется (xq, xu+1) полуинтервал.

Определение 2.1. ЛМ гистограммы называется статистически значимым (СЗЛМ), если на отрезке [xq, xu+1] отвергается гипотеза H0 о равномерном распределении подвыборки множества (2.32), принадлежащей полуинтервалу (xq, xu+1). H0: f(x) = f0(x),

Определение 2.2. ЛМ гистограммы называется статистически незначимым, если на отрезке [xq, xu+1] принимается гипотеза H0 о равномерном распределении подвыборки множества (2.32), принадлежащей (xq, xu+1).

Проверка гипотезы Н0 проводится с использованием известных статистических критериев 2, 2, Вилкоксона, знаков и др.

Если гистограмма исследуемого множества имеет хотя бы один СЗЛМ, то это множество содержит классы, далеко отстоящие друг от друга. Число классов k оценивается по числу СЗЛМ гистограммы : .

Число далеко удаленных друг от друга классов определяется равенством .

За границы классов принимаются середины тех отрезков гистограммы, в которых наблюдается ее СЗЛМ. На рис. 2.17 точка x* - граница классов 1, 2.

Если гистограмма исследуемого множества наблюдений не имеет ЛМ или все ее ЛМ статистически незначимы (рис. 2.18), то это множество однородно, т.е. представляет собою один класс, или содержит классы, недалеко отстоящие друг от друга.

Если число признаков p каждого объекта данного множества наблюдений (2.28) p 2, то предварительную информацию о наличии классов, их числе, степени их удаленности друг от друга и др. можно получить, по крайней мере, тремя способами.

1. Построение и анализ гистограммы каждого признака xs, s = 1, 2, …, p. Каждая такая гистограмма может дать оценку снизу для числа классов k, , ms - число СЗЛМ гистограммы s-го признака. Тогда имеем .

2. Построение и анализ многомерных гистограмм. Строятся t p-мерных интервалов, t = t1t2…tp, ts - число интервалов, на которое разбиваются значения s-го признака, s = 1, 2, …, p. Подсчитывается число точек множества (2.28), попавших в каждый p-мерный интервал ni, i = 1, 2, …, t. Затем выделяются интервалы, содержащие наибольшее число точек, по правилу ni n0, n0 - некоторое заданное пороговое значение. Вычисляются центры тяжести таких интервалов, эти интервалы объединяются в один класс по расстоянию между их центрами по правилу «ближний к ближнему». Кроме того, фиксируются интервалы, содержащие наименьшее число точек, , - другое пороговое значение. По таким интервалам проводятся границы между классами. Интервалы, для элементов которых имеет место неравенство , объединяются с интервалами с наибольшим содержанием точек по правилу «ближний к ближнему». Предварительный анализ многомерных интервалов - очень трудоемкий процесс, практически не осуществимый при больших значениях n и p.

3. Анализ одномерной гистограммы расстояний между всеми различными точками данного множества. Рассмотрим этот метод подробно.

На множестве x(n) в (2.28) задается подходящее расстояние r (метрика) и находятся расстояния между всеми его точками rij = r(xi, xj), i, j = 1,2, …, n, которые можно записать в виде квадратной матрицы

. (2.36)

В силу свойств расстояния имеем rii = 0, rij= rji, i, j = 1, 2, …, n.

Поэтому в матрице (2.36) достаточно исследовать множество элементов, стоящих выше или ниже главной диагонали, например

. (2.37)

Упорядочив элементы множества (2.37) по возрастанию, получим основной вариационный ряд (ОВР) множества X(n)

r(1) r(2) … r(s), (2.38)

Сначала предположим, что плотности классов множества Х(n) статистически равны, т.е. отличаются незначительно. Очевидно, если множество Х(n) имеет классы, далеко отстающие друг от друга, то гистограмма его ОВР имеет хотя бы один СЗЛМ.

Определение 2.3. Пара точек однородна, если эти точки принадлежат одному какому-то классу s, Xi, Xj s, s {1,2, …, k}.

Определение 2.4. Пара точек (Xi, Xj) неоднородна, если эти точки принадлежат разным классам, Xi s, Xj t, s = t, s, t {1,2, …, k}.

На рис. 2.19 изображено множество Х(n), состоящее из трех классов, далеко отстоящих друг от друга. Гистограмма ОВР множества Х(n) имеет один СЗЛМ (рис. 2.20), наблюдаемый на отрезке [rq, rq+1].

Расстояние между точками каждой однородной пары меньше расстояния между точками каждой неоднородной пары ,

< ,

так что некоторая точка отрезка [rq, rq+1] является границей множеств расстояний между точками однородных пар {} и неоднородных пар {}. Левый конец отрезка [rq, rq+1] можно считать оценкой (приближенным значением) наибольшего диаметра классов dmax,

. (2.39)

На рис. 2.21. представлено множество Х(n), состоящее из трех классов, далеко отстоящих друг от друга. Гистограмма ОВР такого множества имеет два СЗЛМ (рис. 2.22). Первый СЗЛМ (нумерация идет слева направо) наблюдается в промежутке [rq, rq+1]. Расстояние между точками почти каждой однородной пары лежит на отрезке [r1, rq], а расстояния между точками каждой неоднородной пары лежат на отрезке [rq+1, r(s)], причем на отрезке [rq+1, ru] находятся расстояния между точками из классов 1, 2 и 2, 3, а на отрезке [ru+1, r(s)] - расстояния между точками из классов 1, 3.

Можно привести пример, когда гистограмма ОВР множества Х(n), состоящего из трех далеко отстоящих друг от друга классов имеет три СЗЛМ.

Если данное множество Х(n) однородно или состоит из классов, близко расположенных друг другу (рис. 2.23), то гистограмма его ОВР не содержит ни одного СЗЛМ и имеет вид, аналогичный представленным на рис. 2.15, 2.18. Из наших рассуждений делаем следующие выводы:

1. Если гистограмма ОВР данного множества Х(n) имеет хотя бы один СЗЛМ, то в этом множестве есть классы, далеко отстоящие друг от друга, и оценка наибольшего диаметра таких классов определяется равенством (2.39).

2. Если гистограмма ОВР данного множества Х(n) не имеет ни одного СЗЛМ, то это множество однородно или состоит из классов, близко расположенных друг к другу.

3. Если гистограмма ОВР имеет «длинный хвост», то множество Х(n) содержит резко выделяющиеся наблюдения (рис. 2.24), которые можно считать классами с малым числом элементов (рис. 2.25).

Отметим, что исследование структуры множества Х(n) по ОВР можно проводить и в одномерном случае, предварительно задав на этом множестве подходящую метрику.

Полагаем, что классы исследуемого множества имеют статистически (почти) равные плотности точек, а на гистограмме ОВР этого множества наблюдается хотя бы один СЗЛМ (рис. 2.22).

Оценим число классов k множества Х(n) по числу СЗЛМ гистограммы его ОВР. Пусть - число наблюдаемых СЗЛМ на гистограмме ОВР, а m - максимальное число СЗЛМ этой гистограммы, которое обусловлено наличием k классов, далеко отстоящих друг от друга. Очевидно,

.

Тогда

.

Решая это квадратное неравенство, получим

. (2.40)

Переходя в неравенстве (2.40) к целочисленным решениям, получим

, (2.41)

где - малое положительное число, Е[Y] - целая часть Y.

Оценку снизу для числа классов можно получить другим способом, по числу однородных пар. Число пар точек множества Х(n) равно n2, пусть n0 - число его однородных пар. Тогда оценка вероятности того, что произвольная пара (Xi, Xj) точек множества Х(n) однородна, равна

. (2.42)

Оценим число однородных пар по ОВР. На гистограмме ОВР фиксируем первый СЗЛМ (нумерация идет слева направо), на рис. 2.22 первый СЗЛМ обнаруживается на отрезке [rq, rq+1]. Очевидно, все r(i) ОВР, которые удовлетворяют неравенству r(i) rq, i = 1, 2, …, i0, являются расстояниями между точками однородной пары. Тогда число однородных пар, оцениваемое по ОВР, равно i0, .

Учитывая, что в ОВР входят лишь все те элементы матрицы (2.36), которые стоят выше ее главной диагонали, имеем

, (2.43)

n в правой части (2.43) - это число однородных пар вида (Xi, Xi), i = 1, 2, …, n. В силу равенств (2.42), (2.43) имеем

. (2.44)

Найдем через априорные вероятности классов 1, 2, …, k.

i 0, . (2.45)

Вероятность того, что произвольная пара точек (Xi, Xj) однородна и обе точки Хi, Хj принадлежат одному какому-то классу s, s {1,2,…, k}, равна s2. Тогда вероятность того, что произвольная пара точек (Хi, Хj) однородна, равна . Функция обладает тем свойством, что ее минимум при условиях (2.45) равен 1/k и достигается в точке 1 = 2 = … = k = , .

Тогда имеем

 (2.46)

На основании соотношений (2.44), (2.46) получим

,

или в целочисленном виде

, (2.47)

где - некоторое малое положительное число, E[Y] - целая часть Y.

Неравенства (2.41), (2.47) оценивают число классов снизу. Дадим для числа k оценку сверху через число инвариантных пар.

Определение 2.5. Пара точек (Хi0, Хj0) инвариантна, если каждая из них является ближайшей соседней точкой для другой.

,

.

Каждое множество точек имеет хотя бы одну инвариантную пару. Например, в множестве X(n) инвариантной является та пара точек, расстояние между которыми равно r(1), r(1) - первый член ОВР этого множества. Каждый класс S X(n), s = 1, 2, …, k, имеет хотя бы одну инвариантную пару точек. Если ninv - число инвариантных пар множества X(n), то для числа его классов k имеем

k < ninv. (2.48)

Эксперименты показали, что каждый класс имеет не менее одной инвариантной пары точек и число инвариантных пар ninv растет с увеличением элементов n множества X(n), составляя от него 25-30%. Так что оценка (2.48) удобна лишь при небольших значениях n, n 30.

Отметим, что оценки для числа классов (2.41), (2.47), (2.48) можно использовать и в одномерном случае, если на данном множестве (2.32) предварительно задать подходящую метрику и построить гистограмму его ОВР.

Локальные минимумы гистограммы ОВР могут порождаться существованием в множестве X(n) как классов, далеко отстоящих друг от друга, так и классов с резко различающимися плотностями точек (РРПТ). Поэтому для корректного использования оценок для (2.41), (2.47) необходимо разделить множество X(n) на такие подмножества, в которых классы имеют статистически равные плотности точек.

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

Определение 2.6. Вариационный ряд минимальных расстояний ВРmin - это упорядоченное по возрастанию множество минимальных расстояний {ri min}, i = 1, 2, …, n, .

Для обнаружения классов с РРПТ при больших значениях n (n 30) строится гистограмма ВРmin. Если на этой гистограмме наблюдается хотя бы один СЗЛМ или «длинный хвост», то множество X(n) содержит классы с РРПТ (рис. 2.27, 2.24).

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

. (2.48)

Если в последовательности (2.48) есть элементы, удовлетворяющие соотношению

, i = 1, 2,…, n - 1, (2.49)

то множество Х(n) содержит классы в РРПТ. Если неравенство (2.49) выполняется раз, то множество Х(n) имеет не менее + 1 классов с РРПТ,

k + 1.

В этом случае для дальнейшего исследования структуры множества Х(n) его необходимо разделить на + 1 подмножеств с почти равными плотностями точек. Каждое из этих подмножеств может быть объединением классов.