Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 48
Текст из файла (страница 48)
Их числовые значения выражают отношение межгруппового рассеяния к внутрнгрупповому в направлении собственных векторов, н обычно з) Зто следует из того факта, что ранг 31 не может превышать лг — 1, н, таким образом, ранг агу не может превышать Х (лг — 1)=л — с. Конечно, если выборки ограничены только подпространством меньшей размерности, возможно получить в качестве 5кг вырожденную матрицу, даже если л — с)В. В таких случаях нужно использовать какую-либо процедуру уменьшения размерности, прежде чем применять критерий на основе определителя (равд. 6.14). Из того, что масштабный-множитель )Т1з одинаков для всех разде- лений, следует, что Ул н .гл' дают одно н то же разделение, н, значит, оптимальная группировка, основанная на г'л, инвариантна отно- сительно линейных невырожденных преобразований данных.
6Я. Функции крипыригв дяя группировки 245 в 1Г 5й15 — — Х Х,. 1=1 (41) Используя соотношение 5г=5зк+5а, можно вывести следующие инвариантиые модификации для 1г 5„, и !5„,!: в (Г5т 5К ~Х~в 1 Х,в 1 + ! 1~р! тт !Зг! Ц ~+л,' (42) (43) Так как все эти функции критериев инвариантны относительно линейных преобразований, это же верно для разделений, которые приводят функцию к экстремуму. В частном случае двух групп только одно собственное значение не равно нулю, и все эти критерии приводят к одной и той же группировке. Однако, когда выборки разделены более чем на две группы, оптимальные разделения, хотя часто и подобные, необязательно одинаковы.
По отношению к функциям критерия, включающим 5г, отметим, что 5г не зависит от того, как выборки разделены на группы. Таким образом, группировки, которые минимизируют !5„,!/!5г!, в точности те же, которые минимизируют !5ж!. Если мы вращаем и масштабируем оси так, что 5 становится единичной матрицей, можно видеть, что минимизация 1г 5г'5и эквивалентна мини- з) другой инвариантный критерий !СБл! =Пхр ~=1 Однако, поскольку его значение обычно равно иулв, он мало полезен. желательно, чтобы разделение давало большие значения. Конечно, как мы отметили в разд. 4.11, тот факт, что ранг 5н не может превышать с — 1, означает, что не более чем с — ! этих собственных значений будут не равны нулю.
Тем не менее хброшими считаются такие разделения, у которых ненулевые собственные значения велики. Можно изобрести большое число инвариантных критериев группировки с помощью компоновки соответствующих функций этих собственных значений. Некоторые из них естественно вытекают из стандартных матричных операций. Например, поскольку след матрицы — это сумма ее собственных значений, можно выбрать для максимизации функцию критерия ') Гл. б.
Обучение без учирмлл и группироена мизации критерия суммы квадратов ошибок !г 5„, после этой нормировки. Рис. б.!4 иллюстрирует эффект такого преобразования. Ясно, что этот критерий страдает теми же недостатками, о которых мы предупреждали в равд. 6.7, и является, вероятно, наименее желательным критерием. Сделаем последнее предуприцдение об инвариантных критериях. Если можно получить очевидно различные группировки масштабированием осей или применением другого линейного преобразования, то все эти групуг пировки должны быть выделены инвариаитной процедурой. Таким образом, весьма х г и, вероятно, что инвариантные л функции критериев обладают у многочисленными локальны- I l l ми экстремумами и соответственно более трудно поддаются О выделению экстремума.
Разнообразие функций критериев, о которых здесь ,ке говорилось, и небольшие раза личия между ними не должны заслонить их существенной нг общности. В каждом случае основой модели служит то, что выборки образуют с хорошо разделенных облаков точек. Матрица внутригруппового l рассеяния Яч; используется l для измерения компактности ! этих точек, и основной целью ! ° является нахождение наибо! 1 †' лее компактной группировки.
аг Хотя этот подход оказался ч полезным во многих задачах, он ие универсален. Например, он не выделит очень плотное облако, расположенное в центд' ре редкого облака, или не Рис. 6.14, Результат преобразования к разделит переплетенные вытянормированным главным компонентам нутые группы. для таких слу( азделение, которое минимизнруег чаев нужно создать другие -гбм в а, минимизирует сумму квадра- тичных ошибок в б1, критерии, которые больше а — ненормированные, б — нормирован- подходят к структуре сущест- иые. вующей или искомой. 6.У. Итератиаиал аятилизааия 247 а.й.
итеРАтиВнАя ОптимизАция Когда найдена функция критерия, группировка становится корректно поставленной задачей дискретной оптимизации: найти такие разделения множества выборок, которые приводят к экстремуму функции критерия. Поскольку множество выборок конечно, существует конечное число возможных разделений. Следовательно, теоретически задача группировки всегда может быть решена трудоемким перебором. Однако на практике такой подход годится лишь для самых простых задач. Существует приблизительно сч/с! способов разделения множества из п элементов на с подмножеств '), и этот экспоненциальный рост при большом и просто давит.
Например, скрупулезный поиск лучшего набора из пяти групп в случае 100 выборок потребует рассмотрения более чем 10" разделений. Поэтому в большинстве применений перебор практически невозможен. Наиболее часто используемым подходом для поиска оптимального разделения является итеративная оптимизация. Основная идея заключается в нахождении некоторого разумного начального разделения и в «передвижении» выборок из одной группы в другую, если это передвижение улучшает функцию критерия. Как и процедуры подъема на вершину к общем случае, такой подход гарантирует локальный, но не глобальный максимум. Различные начальные точки могут привести к разным решениям, и никогда не известно, было ли найдено лучшее решение.
Несмотря на эти ограничения, вычислительные требования выполнимы, и такой подход приемлем. Рассмотрим использование итеративного улучшения для минимизации критерия суммы квадратов ошибок а'„записанного как здесь а 1 = ~ 11 х — ше 'йе, хеЯ' где Ш; = — „~Ч1' Х. 1 е.й1 з) Читателю, которому нравятся комбинаториые задачи, достанет удовольствие показать, что существует точно — ~Ч~~~ (с) ( 1)с-1гя 11 разделений а элементов на с непустых подмножеств (Феллер В., Введение в теорию вероятностей н ее приложения, т.
1, М., «Мир», 1964). Если лэьс, последний член наиболее существен. 248 Гл. б. Обучение бее учиеееля и еруияироени Предположим, что выборка х, находящаяся в данный момент в группе Я е, передвигается в группу Ют. Тогда еп; изменяется на х — иеу еп,' =еп.+— и +1 и 71 увеличивается на 11 — — ~ 11 х — ш1 (~е+ й'х — еп," 11е = хе.й'/ Е ~~ —; —,, ~~ +)~„,(х — )~~ = —.1 л ' 11 х — гп ()*.
Приняв предположение, что п1чь1 (одиночных групп в разбиении не должно быть), такое же вычисление показывает, что гпе изменяется на х — ин 1Пе =1П; —— я; — 1 и /е уменьшается: ~;=~,— „", ~~.-~,(~~. Эти соотношения значительно упрощают вычисления изменений функции критерия. Переход х из .й"е в Хэ положителен, если уменьшение У, больше, чем увеличение lт. Это случай, если и;1(п,— 1)11х — гпее ) а (и +1) 11х — т,.~~е, что обычно получается, когда х ближе к тл чем к гпь Если перераспределение выгодно, наибольшее уменьшение в сумме квадратов ошибок достигается выбором группы, для которой л;/(аэ+1)йх — 1пфе минимально.
Это приводит к следующей процедуре группировки; Прое(едура: Базовая Минимальная Квадратичная Ошибка 1. Выбрать первоначальное разделение выборок на группы и вычислить |, и средние пь,..., т,. Цикл: 2. Выбрать следующую выборку — кандидата на передвижение х. Предполагается, что х находится в Я',. 3. Если п;=1, перейти к Следующий; иначе вычислить не — 11' х — гп ~~е, 1 ~ 1; ил+1 ' и; 1 и; — 1 11 х — пз;11', 1=1.
249 6ЛО. ИЕРаРКи 4СКаЯ гР УприРОЕКа 4. Передвинуть х в л ю если р„(р! для всех /. 5. Вновь вычислить Г„т; н ть. Следующий: 6. Если У, не изменилось после п попыток, останов; иначе перейти к Цикл. Если эту процедуру сравнить с процедурой Базовые Изоданные, описанной в п. 6.4 4, то ясно, что первая процедура в основном представляет собой последовательный вариант второй. Тогда как процедура Базовые Изоданные ждет, пока все а выборок будут перегруппированы перед обновлением значений, процедура Базовая Минимальная Квадратичная Ошибка обновляет значения после перегруппировки каждой выборки, Экспериментально было замечено, что эта процедура более чувствительна к локальным минимумам; другой ее недостаток состоит в том, что результаты зависят от порядка, в котором выбираются кандидаты.
Однако это по крайней мере пошаговая оптимальная процедура, и ее легко модифицировать для применения к задачам, в которых выборки получаются последовательно, а группировка должна производиться в масштабе реального времени. Общая проблема для всех процедур подъема на вершину — это выбор начальной точки. К сожалению, не существует простого универсального решения этой проблемы. Один нз подходов — взять с произвольных выборок в качестве центров групп и использовать их для разделения данных на основе минимума расстояния.
Повторения с различными случайными выборками в качестве центров могут дать некоторое представление о чувствительности решения к выбору начальной точки. Другой подход состоит в нахождении начальной точки для с-й группы нз решения задачи с (с — 1) группами.
Решение для задачи с одной группой — это среднее по всем выборкам; начальная точка для задачи с с группами может быть средняя для задачи с (с — 1) группами плюс выборка, которая находится дальше всех от ближайшего центра группы. Этот подход подводит нас к так называемым иерархическим процедурам группировок, которые простыми методами дают возможность получить очень хорошие начальные точки для итерационной оптимизации. 0.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
