Содержание к диссертации
Введение
Глава I. Постановка задачи исследования кусочно-линейного классификатора по минимуму расстояния 15
1.1. Задача классификации при ограниченном объеме выборки 15
1.2. Кусочно-линейный классификатор по минимуму расстояния. Общие сведения. 23
1.3. Проблемы построения кусочно-линейного классификатора по минимуму расстояния при ограниченном объеме обучающей выборки 31
Глава II. Вероятность ошибки классификации кусочно-линейного классификатора по минимуму расстояния 41
2.1. Условная вероятность ошибки классификации... 44
2.2. Ожидаемая вероятность ошибки классификации .. 48
2.3. Асимптотическая вероятность ошибки классификации 55
2.4. Вычислительные аспекты определения вероятности ошибки классификации 56
2.4.1. Упрощенные способы вычисления вероятности ошибки классификации 57
2.4.2. Вычисление ожидаемой вероятности ошибки классификации способом моделирования условной вероятности ошибки классификации 66
Глава III. Влияние ограниченности обучающей выборки на вероятность ошибки кусочно-линейного юіассишкатора по минимуму расстояния 68
3.1. Влияние ограниченности объема обучающей выборки. Случай М = 2 69
3.2. Влияние ограниченности объема обучающей выборки. Случай М > 2 97
3.3. Эксперименты с реальными данными 100
3.4. Сравнение с линейным классификатором "евклидова расстояния" 106
Глава ІV. Построение кусочно-линейного юіассишкатора по минимуму расстояния в условиях ограничен ного объема обучающей выборки 112
4.1. Оценка вероятности ошибки классификации ИЗ
4.1.1. Модифицированный метод "скользящего экзамена" 113
4.1.2. Модифицированный метод "переклассификации" 115
4.2. Подбор числа эталонов 120
4.3. Определение представительности обучающей выборки 125
4.4. Упрощенный способ определения эталонов 127
4.5. Испытание методики построения кусочно-линейного классификатора решением конкурсной задачи по распознаванию 130
4.6. Решение практических задач построения кусочно-линейного классификатора 137
4.6.1. Решение двух задач по построению алгорит
мов распознавания шумящих механизмов 140
4.6.2. Синтез алгоритма распознавания функционального состояния сердечно сосудистой системы по ритмограмме 148
Заключение 162
Литература 164
Приложения 17
- Задача классификации при ограниченном объеме выборки
- Проблемы построения кусочно-линейного классификатора по минимуму расстояния при ограниченном объеме обучающей выборки
- Ожидаемая вероятность ошибки классификации
- Влияние ограниченности объема обучающей выборки. Случай М = 2
Введение к работе
Одним из основных направлений в сфере автоматизированной обработки информации является использование устройств, которые по измерениям параметров объектов или процессов производят классификацию их по классам. Потребность в таких устройствах возникает при распознавании печатных и рукописных знаков, сигналов речи, летающих аппаратов и подводных объектов, состояния организма человека и диагностике болезней. Использование распознающих устройств позволяет избавиться от ручной обработки информации, повышает скорость и качество принимаемых решений.
Распознающие устройства используют разнообразные методы классификации [12,37]. Эти методы различаются способами описания классов и правилами классификации. В случае, когда классы имеют сложную структуру, широкое распространение получили кусочно-линейные (КЛ) правила классификации [l2,19,27,51,66,69, 83,98], в частности, Ю1 классификатор по минимуму расстояния [27,50,52]. Он основан на разбиении классов на подклассы, которые могут быть разделены линейными гиперплоскостями. Принадлежность объекта к классу определяется по минимуму евклидова расстояния до эталонов. Реализация этого классификатора очень проста, но вместе с тем, он является мощным инструментом для решения задач классификации сложных образов [l9,32,44,9б].Однако, несмотря на известность и многочисленность применений КЯ классификатора по минимуму расстояния, вопросы его построения к настоящему времени разработаны недостаточно. В реальной ситуации о подклассах, обычно, известно очень мало. Основная информация извлекается из обучающей выборки. Построение КЛ классификатора по минимуму расстояния в таких условиях связано с рядом проблем. Этими проблемами являются: оценка вероятности ошибки классификации, подбор числа эталонов, определение представительности обучающей выборки. Известные способы решения этих проблем могут быть использованы лишь при большом объеме обучающей выборки. Однако во многих практических применениях объем выборки невелик и эти способы не пригодны. Поэтому разработка методики построения КЛ классификатора по минимуму расстоя ния при ограниченном объеме обучающей выборки является актуальной задачей.
Для построения этой методики необходимы сведения о влиянии ограниченности выборки на вероятность ошибки классификации. К сожалению, влияние ограниченности выборки на качество классификации не исследовано. Кроме того, отсутствуют аналитические выражения и конструктивные способы определения вероятности ошибки классификации. Поэтому при разработке методики построения КЛ классификатора по минимуму расстояния возникает необходимость определить эти выражения и исследовать влияние ограниченности выборки на вероятность ошибки классификации.
Цель и задачи исследования. Цель работы: а) исследование влияния ограниченности обучающей выборки на качество классификации КЛ классификатора по минимуму расстояния и разработка методики его построения; б) применение этой методики при решении практических задач. Задачами работы являются:
- определение выражений и способов вычисления вероятности ошибки классификации;
- исследование влияния ограниченности обучающей выборки на вероятность ошибки классификации;
- разработка способов оценки вероятности ошибки классификации, подбора числа эталонов и определения представительности объема обучающей выборки;
- разработка программного обеспечения для построения кусочно-линейного классификатора по минимуму расстояния и его апробация путем решения практических задач.
Основные результаты работы. Впервые проведено исследование точности классификации и проблем построения КЛ классификатора по минимуму расстояния в условиях ограниченного объема обучающей выборки. При этом:
- получены выражения для условной, асимптотической и ожидаемой вероятностей ошибок классификации. Эти выражения являются обобщением соответствующих формул для линейного классификатора "евклидова расстояния" [41] на случай, когда классы описываются не одним, а несколькими эталонами;
- разработаны приближенные способы вычисления вероятности ошибки классификации при большом числе эталонов и показана их практическая полезность;
- определено влияние ограниченности обучающей выборки на вероятность ошибки классификации с учетом размерности пространства признаков, величины асимптотической вероятности ошибки классификации, числа подклассов и их взаимного расположения;
- проведено сравнение точности КЛ и линейного классификаторов.
Практическую ценность работы представляют разработанные способы оценки вероятности ошибки классификации, подбора числа эталонов и определения представительности обучающей выборки. Они учитывают влияние ограниченности обучающей выборки и позволяют выбрать наилучшие условия работы КЛ классификатора по минимуму расстояния. Создано программное обеспечение для построения КЛ классификатора по минимуму расстояния в условиях ограниченной выборки. Оно включено в систему для оперативной разра - II ботки распознающих алгоритмов СОРРА [45] и может быть использовано исследователем, не являющимся профессиональным программистом.
Внедрение работы. Результаты работы использованы при выполнении договорных работ с предприятием п/я A-I427 по теме "Разработка алгоритмов динамической классификации акустических нестационарных сигналов и повышение качества распознавания по их фазовым изображениям на базе ЭВМ БЭСМ-6", с предприятием п/я A-II73 по теме "Исследование возможности автоматического распознавания нестационарных сигналов", а также при построении системы автоматизированного анализа ритмограмм согласно комплексной программе СЭВ по теме 2.2.9 "Разработка и усовершенствование методов автоматического анализа электро-кардиосигналов на базе вычислительных машин". С использованием результатов работы построены алгоритмы распознавания, дающие по сравнению с другими классификаторами меньшую вероятность ошибки. Условный экономический эффект от внедрений составил 67000 рублей.
Публикации и апробация работы. Основные результаты работы опубликованы в [16,44,45,57-63] и докладывались на:
- республиканских научно-технических конференциях (Каунас, 1972-1983 гг.);
- республиканских семинарах "Статистические проблемы управления" (Вильнюс, 1972-1984 гг.);
- всесоюзном рабочем семинаре "Проблемы малых выборок в распознавании образов" (Друскининкай, 1975 г.);
- 4-ой всесоюзной научно-технической конференции по автоматизации ввода письменных знаков в ЦВМ (Каунас, 1977 г.);
- общемосковском семинаре по прикладной статистике (Москва,
- 12 1977 г.);
- всесоюзной научно-технической конференции "Применение многомерного статистического анализа в экономике и оценке качества продукции" (Тарту, 1977 г.);
- симпозиуме специалистов стран - членов СЭВ по теме 2.2.9 комплексной проблемы "Сердечно-сосудистые заболевания" (Каунас, 1981 г.).
На защиту выносятся:
- точные и приближенные способы определения вероятности ошибки классификации для ЮІ классификатора по минимуму расстояния, учитывающие ограниченность объема обучающей выборки;
- результаты исследования влияния ограниченности объема обучающей выборки на вероятность ошибки классификации;
- способы оценки вероятности ошибки классификации, подбора числа эталонов, определения представительности обучающей выборки;
- использование созданной методики построения Ю1 классификатора по минимуму расстояния для разработки алгоритмов распознавания шумящих механизмов, синтеза правила классификации функционального состояния сердечно-сосудистой системы, а также при решении международной задачи по распознаванию образов.
Связь с научной тематикой института. Работа выполнена в отделе процессов распознавания Института математики и кибернетики АН Литовской ССР в соответствии с плановыми темами "Исследование автоматизации опознавания случайных процессов" (№ гос.per. 75015204), "Исследование автоматизации опознавания многомерных случайных процессов" (№ гос.per. 78014897), согласно особо целевой программе 0.Ц.027 по теме "Развить и ввести в эксплуатацию автоматизированную систему научных исследований коллективного пользования для институтов Академии наук Литовской ССР" (№ гос.per. 81064739) и согласно комплексной программе СЭВ "Сердечно-сосудистые заболевания" по теме 2.2.9 "Разработка и совершенствование методов автоматического анализа электрокар-диосигналов на базе вычислительных машин".
Структура работы и краткое содержание отдельных глав. Диссертационная работа состоит из аннотации, введения, четырех глав, заключения, списка литературы и приложений.
В первой главе приводится общая формулировка задачи построения классификатора при ограниченном объеме обучающей выборки и используемая терминология, представляются сведения о КП классификаторе по минимуму расстояния, рассматриваются проблемы его построения, приводятся известные способы их решения, определяются задачи настоящего исследования.
Во второй главе выводятся формулы для условной, ожидаемой и асимптотической вероятностей ошибок классификации. Формулы выводятся основываясь на предположении, что распределения признаков в классах описываются смесью сферически нормальных распределений. Рассматриваются вычислительные аспекты определения вероятности ошибки классификации. Приводятся два упрощенных способа вычисления, позволяющие оценить вероятность ошибки классификации при большом числе подклассов (снизу и сверху). Описываются результаты экспериментов по оценке практической полезности этих способов.
В третьей главе приводятся результаты исследования влияния на вероятность ошибки классификации ограниченности объема обучающей выборки. Исследование проведено с учетом размерности пространства признаков, величины асимптотической вероятности ошибки классификации, числа и взаимного расположения подклассов. Рассмотрены случаи классифицированной и неклассифицированной выборки. Полученные результаты исследования сравниваются с результатами экспериментов, проведенных с использованием реальных данных.
Приводятся результаты сравнения точности ЮІ классификатора по минимуму расстояния с точностью линейного классификатора.
В четвертой главе решаются задачи построения КЛ классификатора по минимуму расстояния. Приводятся два способа оценки вероятности ошибки классификации. Описываются результаты экспериментов по оценке точности этих способов. Излагаются способы подбора числа эталонов. Описывается методика решения задачи определения представительности обучающей выборки. Приводятся результаты экспериментов по оценке влияния на качество классификации замены метода максимального правдоподобия, при оценке эталонов, более простым методом минимизации внутригруппового рассеивания. Излагаются результаты испытания созданной методики построения кусочно-линейного классификатора по минимуму расстояния решением международной конкурсной задачи по распознаванию образов. Приводится краткое описание программного обес печения для построения КЛ классификатора по минимуму расстояния. Излагаются результаты решения практических задач: двух задач по построению алгоритмов распознавания шумящих механизмов, задачи синтеза правила классификации функционального состояния сердечно-сосудистой системы.
Задача классификации при ограниченном объеме выборки
Будем рассматривать задачу классификации в следующей статистической постановке [27]. Имеется совокупность объектов JQ , которая является разделенной на два класса си и LOz . Каждый объект описывается р -мерным вектором признаков Л Гх . Хр) . Вектор признаков является случайным и в каждом классе Ш-. ха-растеризуется плотностью распределения -flX I 60-) . Вероятность появления объекта из класса 60 равна Р(сО ) . Ставится задача — на основе имеющейся информации о классах — построить классификатор ( решающее правило классификации, алгоритм классификации), позволяющий "наилучшим" образом классифицировать реализации совокупности. Обычно строится дискриминантная (решающая) функция (ДФ) 0 (Л) И классификация неизвестного вектора У производится по знаку О (X) . ДФ, как правило, зависит от различных параметров, их будем рассматривать как компоненты вектора параметров 8=(0 ,...,QS) . При необходимости подчеркнуть эту связь, ДФ будем обозначать как о(Х18) или о(Х;9).
В случае, если плотности -ИХІбО/) и вероятности Р(бОг) известны, задача построения "наилучшего" классификатора решается однозначно. В этом случае можно построить оптимальный классификатор, обеспечивающий минимум средней вероятности ошибки классификации (ВОК). Таким классификатором является бейесовый классификатор [2] . Дискриминантная функция бейесового классификатора определяется следующим выражением oam = P(w,)f(XlwJ-P(w2)f(Xlw.,). (I.I) - 16 Если ge (X) 0 , вектор X относится к классу и) , в противном случае — к классу U)z . Вероятность ошибки классификации для бейесового классификатора (бейесовая ВОК) определяется как Бейесова BOK является минимально возможной вероятностью, какая вообще может быть достигнута при решении данной задачи. Она зависит лишь от параметров плотности распределения f (XI Од J и вероятностей Р(м-) .
К сожалению, в большинстве практических задач плотности j (XlkjJ неизвестны. В общем случае неизвестны и вероятности Р(бО ) . Поэтому при построении классификатора приходится идти другими путями. Общеизвестный подход состоит в том, что классификатор строится по бейесовой схеме, подставляя в (I.I) вместо неизвестных "f(XI ) и Р( U)-J их оценки 2] . Однако этот путь не является единственным. Имеется, например, целая группа алгоритмов классификации, основанных на различных предположениях о виде дискриминантных функций. Примером могут служить классификаторы, минимизирующие функцию эмпирического риска [юз] . Большую группу составляют также эвристические алгоритмы классификации, такие как, например, кусочно-линейные классификаторы [27]. Согласно Ш.Ю.Раудису [41], в настоящее время известно более ста статистических алгоритмов классификации, построение которых основано на различных принципах. Обзоры этих алгоритмов приведены в[і2,І7,37.Несмотря на разнообразие подходов, всех их объединяет то, что при построении классификатора исполь - 17 зуются некоторая модель (напр., распределения признаков или дискриминантной функции) и обучающая выборка. Обучающая выборка представляет собой набор реализаций вектора Л л4Г..,Х ,)(,,...,/,,,, где Хи - I -ая реализация из класса 6d- , N-L - их число. Будем предполагать, что выборочные реализации выбраны из генеральных совокупностей случайным образом и между собой независимы. С использованием обучающей выборки находится оценка вектора Д Л параметров ДШ в . Так как 0 является функцией выборочных реализаций, то зависимым от обучающей выборки является и качество классификации. Качество классификатора, обучаемого с использованием выборки, характеризует ВОК нескольких видов[41,70, юо]. ВОК классификатора, обучаемого по конкретной выборке, называется условной вероятностью ошибки классификации. Она определяется по формуле (2-РЦ)[ f(XlwjdX+P(wi f(Xloi2)dX. (1.3) аІХЮХО o(XlS) 0
Символ N " в обозначении ВОК f подчеркивает тот факт, что классификатор построен по обучающей выборке ограниченного объема. Так как обучающая выборка является случайной, то случайной является и условная ВОК Р . Распределение 1 является основной характеристикой качества классификации при ограниченном объеме обучающей выборки. Это распределение зависит от вида и параметров распределения признаков f (XI 60-) , вероятностей PiUi i , вида и способа построения классификатора, объема обучающей выборки. Численной характеристикой качества классификации, не связанной с конкретной обучающей выборкой, является математическое ожидание условной ВОК - 18 . E=5 PN% de (1.4) л W где (DN (9) - плотность распределения 8 , W - область значений 6 , F - условная ВОК, выражаемая формулой (1.3). Математическое ожидание условной ВОК ЕР будем называть ожидаемой вероятностью ошибки классификации.
При неограниченном росте объема обучающей выборки (mill N-— ) , классификатор обучается все лучше, ожидаемая ВОК ЕР уменьшается и стремится к асимптотической вероятности ошибки классификации а=Н,ЕЕ (1-5)
Асимптотическая ВОК F характеризует потенциальные возможности классификатора при неограниченном объеме обучающей выборки. Если оценки параметров модели классов являются состоятельными, асимптотическая ЮК Р, может быть определена по формуле условной ВОК (1.3), подставляя вместо оценок параметров их истинные значения. В случае, если классификатор строится по бейесовой схеме, модель классов соответствует действительности и оценки параметров модели являются состоятельными, асимптотическая ВОК совпадает с бейесовой ЮК. В противном случае — всегда F ( . Отношение ЕР / Р представляет собой среднее относительное увеличение ЮК, из-за недостаточно хорошего обучения классификатора, и характеризует как степень обученности классификатора, так и его чувствительность к ограниченности 00В. Согласно (1.5) ІІГП. ЕР/Р =4 . При ограниченном 00В обычно t J /г 0 /1 , хотя при несоответствии модели и реальности, могут быть и исключения. [41].
Проблемы построения кусочно-линейного классификатора по минимуму расстояния при ограниченном объеме обучающей выборки
Однако, в большинстве случаев о подклассах нет никаких сведений. Принадлежность выборочных реализаций к подклассам неизвестна (обучающая выборка неклассифицирована). Обычно неизвестно и число подклассов. В этом случае эталоны классов определяются при помощи методов автоматической классификации (о них см. [іІ,І2,25,7б] ). При помощи этих методов в обучающей выборке выделяются "компактные" группы реализаций, "сгустки" реализаций. В качестве эталонов классов используются "центры" этих групп. Для выделения "компактных" групп реализаций при построении КЛ классификатора, в принципе, может быть использован любой алгоритм, действие которого направлено на поиск сферообразных подклассов. К таким алгоритмам можно отнести: эвристический алгоритм поиска мод [ІЗ,27,90,91] , алгоритм для минимизации внут-ригруппового рассеивания[54,64,74] , алгоритм для разделения смеси сферически нормальных распределений (частный случай алгоритма разделения нормальных смесей[12,25,68,76,102] ). Последний (приводится в приложении 5) отличается тем, что позволяет выделить пересекающиеся подклассы.
Основной проблемой, которая возникает при определении эталонов по неклассифицированной выборке является подбор их числа. Критерием подбора числа эталонов обычно является величина ВОК, хотя немалую роль при этом могут играть и экономические соображения. Зависимость ВОК от числа эталонов при фиксированном 00В определяется двумя противоположными тенденциями. С одной стороны, чем число эталонов больше, тем детальнее описание классов. По этой причине при увеличении эталонов, ВОК обычно уменьшается. С другой стороны, при увеличении числа эталонов (а значит и числа выделяемых "компактных"групп), уменьшается число реализаций, отнесенных к одной группе. Стабильность эталонов ухудшается и ВОК, в среднем, увеличивается. Суммарная зависимость ВОК (ЕР или Р) от числа эталонов определяется соотношением этих тенденций и может иметь минимум. Оценка числа эталонов, соответствующего минимуму ВОК (это число будем называть оптимальным), представляет большой практический интерес. Аналогичная задача сформулирована Г.Я.Волошиным, С.Т.Косенковой в [б] для бейесового классификатора, основанного на описании распределения признаков смесью нормальных распределений.
В случае, если объем выборки достаточно большой, проблемы по подбору числа эталонов нет. В этом случае может быть получена довольно точная оценка ВОК, например, по контрольной выборке и непосредственно по ее значениям, определенным при различном числе эталонов, может быть подобрано наиболее подходящее число эталонов. Проблема возникает в случае, если число выборочных реализаций невелико. Оценка ВОК в этом случае имеет большой разброс и результаты подбора числа эталонов, непосредственно по значениям оценки ВОК, являются очень неточными.
Рекомендаций по подбору числа эталонов для Кй классификатора по минимуму расстояния нет. Обычно число эталонов задается, исходя из "здравого смысла". Исключение составляет работа [89] , в которой предложен алгоритм автоматического определения их числа в зависимости от структуры данных. Хотя работа этого алгоритма, в неявной форме, и направлена на минимизацию ошибок классификации, однако она проводится по обучающей выборке, не учитывая ограниченности 00В. Вследствие этого, при небольшом 00В и большом числе эталонов на обучающей выборке могут быть получены очень хорошие результаты. В тоже время истинная точность классификации может быть неудовлетворительной. Для определения числа эталонов необходимы способы, учитывающие ограниченность 00В.
Оценка вероятности ошибки классификации. Оценка ВОК является одной из важнейших задач, решаемых при построении KJI классификатора. От точности оценки ВОК зависит как точность оценки оптимального числа эталонов, так и точность оценки представительности ООВ. Для определения оценок ВОК, к настоящему времени предложено много различных способов (см. обзоры[зб,41,100J ). Условно их можно разделить на параметрические и непараметрические. Параметрические методы отличаются тем, что оценки ВОК вычисляются по аналитическим выражениям ВОК. Эти выражения определяются при заданном виде плотности распределения признаков
. Неизвестные параметры в аналитических выражениях для ВОК оцениваются по выборке. Использование в параметрических методах, кроме выборки, информации о виде плотности распределения признаков позволяет получить оценки ВОК, более точные, чем при использовании непараметрических методов. Однако, это справедливо лишь в том случае, если заданный вид плотности не слишком отличается от истинного вида. Как показывают результаты исследований [41], параметрические методы являются чувствительными к отклонениям от заданной модели распределения. Это является одним из основных недостатков этих методов. Для ряда классификаторов применение параметрических методов ограничивается также из-за того, что аналитические выражения для ВОК сложны и трудно вычисляемы. Как будет видно по результатам исследований главы II, это относится и к КД классификатору по минимуму расстояния.
Ожидаемая вероятность ошибки классификации
Ожидаемая ВОК Е Р определяется как математическое ожидание условной вероятности ошибки классификации F по всем возможным обучающим выборкам заданного объема !\L ,N2 0 использованием вспомогательных Д (2.3) она может быть представлена в виде, который аналогичен виду условной ВОК Р (2.5), т.е.
Индексы "X, p" в обозначении вероятности Pzoby ... 1 указывают на то, что при ее определении, во вспомогательных ДФ QZj,r-i QZM. Рас о Ос сматриваются в качестве случайных величин, не только вектор Л KL ,АМ) л (2) но и оценки средних Нл,..., Мм . Распределение вектора б в этом случае является очень сложньм и точного выражения для Е Р получить не удается. Поэтому построим приближенное выражение для ожидаемой ВОК, заменив истинное распределение век тора Ge , при условии, что Х&С0-- , нормальным распреде лением со средним
Аппроксимация истинного распределения вектора Qz нормальным законом со средним (2.16а) и ковариационной матрицей (2.166) основана на асимптотической нормальности распределения G Чем N , N2 и р больше, тем эта аппроксимация, а вместе с тем и выражение (2.18), являются точнее. Относительная точность (2.18) увеличивается также с ростом f . В пределе, когда ЩІП N-— »о и/или р- »оо , аппроксимирующее распре-деление и выражение (2.18) становятся точными.
Для того, чтобы воспользоваться формулой (2.18) необходимо определить математические ожидания Hf и ковариационные матри J цы STl, K,t = 4,2, КФ1 =4,..., Мк, j=4,..., t ДРивеДем выражения для этих характеристик: сначала для случая, когда обучающая выборка является классифицированной, далее рассмотрим случай неклассифицированной обучающей выборки. K/f J делена согласно нормальному закону N(W.-,-JT б І) [20] . Случай классифицированной обучающей выборки. В этом случае каждая из оценок МП и- (=4,2,1 = 4,...,1 ), представляющая арифметическое среднее выборочных реализаций подкласса Ш{- , распре Iі N
Оценки средних из различных подклассов независимы, т.е. взаим А (К) Л(1 ная ковариационная матрица любых двух векторов и и f4 , если ТФ ъ , равна
Выражение (2.18) вместе с (2.19) определяет формулу, которая является обобщением выражения ожидаемой ВОК для классификатора "евклидова расстояния" (приведенного в[35] ) на случай, когда классы описываются не одним, а несколькими эталонами. В случае М = М она полностью совпадает с выражением, приведенным в [35] .
Случай неклассифицированной обучающей выборки. Как уже говорилось в введении главы, в этом случае оценки МП U ,..., Йм определяются совместно, решая систему уравнений правдоподобия итеративными методами. Распределение получаемых оценок неизвестно. Поэтому истинное распределение оценок МП М4 ,...,М . заменим аппроксимацией. В качестве аппроксимации используем _ 1Г_ Л() Л(і) асимптотическое распределение оценок. Оценки МП и ,..., и асимптотически (при неограниченном увеличении 00В) распределены нормально со средним U = (JU ,..., MU ) и ковариационной - 53 матрицей, обратной к информационной матрице Фишера [20] Согласно исследованиям [58], в случае, когда компоненты смеси(2.1) равновероятны, эта аппроксимация, при расстоянии Махаланобиса между средними компонент Н 2 » является приемлемой, даже при небольших W-/M; (порядка нескольких десятков).
Влияние ограниченности объема обучающей выборки. Случай М = 2
В ходе эксперимента определялись: - точное значение асимптотической ВОК F — путем непосредственного интегрирования (2.1) в КЇЇ области. Р вычислялось способом, который описан в приложении I; - оценка асимптотической ВОК PJ первым упрощенным способом. Она определялась при Щ =1,2,...,8; - оценка асимптотической ВОК ( вторым упрощенным способом. Она определялась при Z = 1,2,...,6.
Функция нормального распределения при вычислении оценок ВОК bo и оо определялась следующим образом: Q — используя стандартную подпрограмму БЭСМ-6 [7] , F — используя выражения Оувена [8б] , F — используя выражения Стека [97] , Р , О О — методом Монте-Карло по выборке объема NbWB = 1000.
Полученные в ходе эксперимента значения асимптотической ВОК приведены: PJ - в табл.2.1; Р 1 - в табл.2.2; Р - в табл.2.3. Анализ приведенных результатов показывает, что оценка Ь является близкой к точному значению Уэ в случаях расположения подклассов AI, А2, Б уже при ГЛ. = 4,5, а в случае В - при 171 = 2. Это значит, что используя первый упрощенный способ, кратность интегрирования при определении г , кото-Трое в данном случае равно Q =15, можно уменьшить в три и даже больше раз без существенной потери точности.
Второй упрощенный способ, как показывает табл.2.3, является не столь эффективным: существенное уменьшение объема вычислений может быть получено лишь в случаях расположения подклассов А2, Б. В случае А2 число используемых подклассов при вычислении асимптотической ВОК может быть уменьшено без существенной потери точности до М =5;М2=5 ,в случае Б - до М«3, м2в, = з.
Эксперименты показывают, что оба упрощенных метода являются работоспособными и могут быть практически использованы при оценке ВОК в случае больших М. и Ма
Приближенное выражение для ожидаемой ВОК (2.18) пригодно для вычисления ЕР лишь при достаточно больших INLjN,, р и Р . Если N,p и F , недостаточно велики, разность между получаемыми значениями Е 1 и истинными значениями Е Р может быть неприемлемо большая. В этом случае ожидаемая ВОК может быть определена, используя способ моделирования условной вероятности ошибки классификации. Он сводится к многократному повторению формирования на ЭВМ оценок JU ,..., JUM и вычисления по (2.13) условной ВОК. Оценки ріЛ ,...7jwjjl могут быть сформированы, используя псевдослучайные числа. В результате вычисля А і S ется оценка ожидаемой ошибки классификации Е Р =- 2_. R.L , _ . -, N - условная ВОК, вычис ленная на І -ом шаге. Моделирование условной ВОК тре бует больших затрат времени, чем вычисление EF при помощи (2.18), однако эти затраты гораздо меньше, чем при вычислении ЕР используя непосредственное моделирование (см. приложе N ние 2). Точность вычисленного результата, хотя и грубо, может л л ЕР быть оценена по оценке среднеквадратического отклонения Ег
С использованием этой оценки точ N \?1 -и fcll,N U,N ности, могут быть определены условия применимости (2.18). В разделе 3.1 приведены данные об условиях применимости (2.18) в t (f EPf1 случае МА = М = 2. Выводы по второй главе
1. Выведены выражения для ЮК КИ классификатора по минимуму расстояния: для условной ЮК, асимптотической ЮК и приближенная формула для ожидаемой ЮК. Полученные выражения являются обобщением соответствующих формул для линейного классификатора "евклидова расстояния" на случай, когда классы описываются не одним, а несколькими эталонами. Они действительны при любом расположении подклассов, оценок их центров. В случае небольшого числа подклассов (М (М,) 2-5), полученные выраже-ния могут быть непосредственно использованы для вычисления ЮК.
2. Построены два упрощенных способа определения ЮК при большом числе подклассов. Первый способ дает гарантированную оценку сверху, второй - оценку снизу. Путем проведения расчетов на ЭВМ показана их практическая полезность.
3. Для вычисления ожидаемой ЮК ЕР предложен метод моделирования условной ЮК.
