Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 56
Текст из файла (страница 56)
Предположим, что при М = 2 имеется несколько разных классификаций, дающих почти минимальное значение 1. Если эти классификации отличаются лишь классификацией нескольких объектов, то нет причины предполагать наличие белее чем двух классов. Однако, если классификации отличаются намного то очевидно, что в деиствительности имеется несколько классов. На рис.
11.1 показаны две возможные дихотомии множества объектов, состоящего из трех классов А~, Ад и Аз. Первая дихотомия делит объекты на два класса А1ЦА2 и Аз, вторая — на классы А1 и А2 ц Аз. Таким образом, видно, что Аз, А1 и А1 О Аз —— А, — это три разных класса (через А здесь обозначепо дополнение множества А). Рассмотрим теперь болев общий случай, когда имеется й дихотомий совокупности объектов, состоящей тдз М классов. Каждая дихотомия разделяет эти объекты на две группы. 'Пусть Яи— множество всех объектов, отнесенных к группе / в результате .т'-й дихотомии (1 = 1, 2; 1= 1,,, й).
Предположим, что выполнядотся следующие два условия: $11.1. АЛГОРИТМ АВТОМАТИЧЕСКОИ КЛАССИФИКАЦИИ ф у У-х Рлжаюаи Рис. 11.1. Многократная дихото- мия трех классов объектов. (11.9) где каждое 1 принимает значения 1 или 2. Каждое непустое множество С есть класс. Возвра- щаясь к нашему примеру, имеем Я,1 — А, 0 А2, Яд — — Аз, 521= А1, Я'2 = А2 0 Аз, (11.10~ таким образом, С'(1, 1) = Ядд П 821 = А„С (1, 2) = Я П 522 = А„1 С (2, 1) = 512 Ц Я,д — 8, С (2, 2) = Яд, Ц 522 = Аз1 (11. 11~ что согласуется с нашим предыдущим рассуждением.
Метод многократной дихотомии имеет более прочную теоретическую основу, чем процедура объединения и расщепления Кроме того, он не использует никакого другого численного критерия, кроме 1. Однако практическая реализация метода многократной дихотомии может оказаться трудной, особенно в тех случаях, когда истинное число классов велико. Эта трудность может быть отчасти преодолена путем организации иерархической структуры на множестве классов. Объекты делятся на небольшое число классов, каждый класс делится в свою очередь, и т.
д. При использовании этой стратегии не возникает необхо- а) дихотомия относит каждый класс целиком в одну группу, т. е. классы нерасщепляются дпхотомией; б) для каждой пары классов имеется по крайней мере одна дихотомия, которая пе относит оба класса к одной и той же группе. Выберем по одной группе пз каждой дихотомии и образуем подмножество С, являющееся пересечением всех к групп. По условию а), если подмножество С содержит один объект, то оно должно содержать все объекты того же класса. По условию б) для любого другого класса имеется по крайней мере одна из й выбранных групп, такая что этот класс к ней не 1 А~ А принадлежит. Поэтому, если С у непусто, то С содержит один и только один класс.
Следовательно, для того, чтобы построить все М классов, необходимо рассмотреть 2" подмножеств вида ".У С91~ 12, ° ф1~) = П Я;,~~ 1=1 ГЛ. 11. АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ % 11.2. ПАРАМЕТРИЧЕСКИЕ КРИТЕРИИ КАЧЕСТВА димости находить все возможные дихотомии всей совокупности объектов. В этом месте мы отклонились от рассмотрения алгоритма .автоматической классификации.
Очевидно, это рассмотрение не закончено, однако основа для построения процедур автоматической классификации у нас ух1е есть. Нам недостает лишь той уверенности в правильности нашего метода, которая была у нас при решении задач распознавания образов с учителем. Обратимся поэтому к детальному рассмотреншо критериев качества классификации. 5 11.2. Параметрические критерии качества классификации Очень часто критерии качества классификации задают в виде функций от параметров, возникающих в других задачах математической статистики. Вначале мы дадим некоторое обоснование этих критериев, а затем изучим их свойства. Будет показано, что при использовании одного из этих критериев алгоритм предыдущего параграфа принимает особенно простой вид. Мы рассмотрим также идею инвариантного преобразования и некоторые результаты, которые можно из нее получить.
М ~ Р (®') (Л~1 ~~а)(л~. — '1.1а) 1-1 (11.13) 11.2.1. Матрицы рассеяния и разделимость классов в задаче .автоматической классификации. Задачу автоматической классификации можно рассматривать как задачу поиска такой группировки объектов, при которой макспмизируется разделимость классов. Тогда все критерии, рассмотренные в гл. 9, можно использовать в качестве критериев качества классификации. В этом параграфе мы ограничимся рассмотрением только функций матриц рассеяния. Такое ограничение обусловлено следующими причинами: 1) критерии этого типа.
непосредственно обобщаются на случай многих классов; 2) они имеют более простой вид, чем расстояние Бхатачария или дивергенция. Простота в данном случае необходима, так как в задачах автоматической классификации возникают дополнительные сложности, связанные с отнесением объектов к заранее не известным жлассам. Выберем в качестве матриц рассеяния матрицы Я„, Яц и Я, определенные выражениями (9.7), (9.8) и (9.12). Обобщение на случай многих классов производится следующим образом: м Я„= ~ Р (а,.) Х„ (11.12) 1=1 '(11. 14)' Здесь Я„, Я~~ и Я,„— соответственно матрицы рассеяния внутри классов, между классами и совместная матрица рассеяния.
Когда качество классификации оценивается разделимость1о построенных классов, то процедура автоматической классификации должна обладать свойством инвариантности по отношению к линейному преобразованию системы координат, т. е. давать одну и ту же классификацию данного множества объектов независимо от системы координат, в которой производится измерение. Как было указано в гл. 9, критерии (9.13) и (9.14) не зависят от системы координат. Выбирая Я1 и Я2 в соответствии с (9.13) и (9.14), имеем следу1ощпе критерии качества классификации: (11.15) (11.16) (11.17) (минимизировать) „ (максимизировать)т (максимизировать) .
Более простые вырах1епия получаются, если использовать совместную нормировку (4.53): АЯ„А' = 1, '(11.18)' ~~~0 О э (11.19)' где А — невырожденное линейное преобразование. Соответственно преобразуются переменные, матрицы рассеяния и векторы математических ожиданий. В преобразованной системе координат они имеют вид АХ=Ъ', ЛЛХ, = О„ (11.20) (11.21)' (11.22) АЗ,А' = К, и удовлетворяют условиям и Ктд = К,о + Кы —— ,, Р (ю;) 1К1 + О10',1 = У„(11.23) 1 — 1 и ~-~0 Х Р (®1) 01 (11.
21) Следует отметить, что результат совместной нормировки яе зависит от распределения объектов по классам. Критерии (11.15)— т. — 1 (11.17) мо)кно переписать в виде функций от матриц К, и Ка1 т.~ — 1 т.~ и собственных значений Х1, Х2, ..., Х„матрицы Ка Кь1 (которые 1'т К. Фукунага 5 11.2. ПлРлметРические кРитеРии клчествл Гл. 11. лйтомлтическля кллссиФикл11ия ззя -! совпадают с собственными значениями матрицы Я Я,д): л У, = $г К = ~~ 1/(1+ Х;) (минимизировать), (11.25) 1-1 л У1 = $г К„, 'К,д —,~' Х; (максимизировать), 1 1 и У2 = — 1п ~ К, ~ =- ~ 1п (1 + л;) (максимизировать).
(11.27) 1 — 1 (11 26) Приведенные выше критерии приводят к более или менее одинаковым классификациям, а в случае двух классов все они сводятся к одному критерию. Для двух классов ранг матрицы К~1 равен 1, потому что Кы — — Р (1о,) 0,О1 + Р (ог2) В2'02 ——— (11. 28) — (о'1) (Р ( '2)~~ (1о1)) 7~27~2+ Р (о'2) ~~2~2~ где вторая строчка получается из (11.24). Поэтому Х, = — - 1г К„'Кы ~ О, 1~2 = 1.3 = ...
— Хч ' — О. (11.20) (11.30) Таким образ»м, ° /1 — — 1 (1+ Х1) + (и — 1) (минимизировать), (11.31) У1 = Х, (максимизировать),. ° /2 — — 1п л1 (максимизировать). (11. 32) (11.33) ЛУ, (г, /, У) = (1/Х) ~ ~)У, — О, (У) (/2 — //У1 — 1)л. (/) ~~2~. (11.34) Так как второй член (11.34) не зависит от /, решающее правило на /-й итерации имеет вид ~~~,. — В1®~~= ш;1 ~~~., — В,®~~, (11.35) а алгоритм может быть описан следующим образом.
Все эти выражения оптимизируются при максимизации Х1. Следовательно, в задаче с двумя классами эти три критерия дают в точности один и тот же результат. Хотя все три критерия можно оптимизировать описанным в предыдущем параграфе алгоритмом, использование критерия /1 позволяет построить особенно простой алгоритм автоматической классификации. Предположим, что на 7-й итерации число векторов, отнесенных и каждому классу, достаточно велико, так что при переброске одного вектора из класса в класс средние векторы изменяются незначительно. Тогда формула для приращения Ы1(г, /, /) (см. параграф 11.1) принимает особенно простой вид.' 11.2.2. Сходимость процедуры, основанной на правиле ближайшего среднего.
Полученные выше результаты приводят и следующей процедуре автоматической классификации [Фукунага, 1!)70 г1. 1. Прпмеппть совместную нормировку. 2. Классифицировать объекты, используя правило ближайшего среднего. Эффективность этой процедуры можно оценить аналитически, если объекты генерируются в соответствии с двумя нормальными распределениями. Мы найдем условия, при которых разделяющая гиперплоскость сходится к гиперплоскости, перпендикулярной к вектору разности средних векторов этих распределений. В случае равных ковариационных матриц это будет байесовская оптимальная гиперплоскость.
Нормальные распределения с равными ковариационными матрицами. Если два нормальных распределения имеют одинаковые коварпацпонные матрицы К1 = К2 —— К, байесовская оптимальная разделяющая поверхность прп условии совместной нормировки представляет собой гпперплоскость вида (О1 — О2) 'К ' У + сонэк = О. '(11.36) Действуя так же, как в (4.68), можно привести (11.36) к виду '1Р (ог,) — Р (огг) В2В21 В2У + сопв1 = О. (11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
