Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 49
Текст из файла (страница 49)
ИЕРАРХИЧЕСКАЯ ГРУППИРОВКА 6.10,!. ОПРЕДЕЛЕНИЯ Рассмотрим последовательность разделений и выборок на с групп. Первое из них — это разделение на и групп, причем каждая из групп содержит точно по одной выборке. Следующее разделение на а — 1 групп, затем на и — 2 и т. д. до п-го, в котором все выборки образуют одну группу. Будем говорить, что находимся на А-м уровне в последовательности, когда с=п — А+1. Таким образом, первый уровень соответствует и группам, а и-й — одной группе. Если даны любые две выборки х и х', на некотором уровне они будут собраны вместе в одну группу.
Если последовательность обладает тем свойством, что, когда две выборки попадают в одну группу на уровне й, они остаются вместе на более высоких уровнях, то такая последовательность называется иерархической группировкой. Классические примеры иерархической группировки можно найти в биологии, где индивидуумы группируются в виды, виды — в роды, роды— аг хг ае хо аг Уроуеоь 7- У~оубеоь ~ Уробеоь Ч ч 700 90 Уробооь 5 Уробеоь б- 90 в семейства и т. д. Вообще группировки такого рода проникают и в другие науки.
Для любой иерархической классификации существует соответствующее дерево, называемое дендрогралшой, которое показывает, как группируются выборки. На рис. 6.16 представлена дендрограмма для гипотетической задачи, содержащей шесть выборок. Уровень 1 показывает шесть выборок как одиночные группы. На уровне 2 выборки х, и х, были сгруппированы в группу, и они остаются вместе на всех последующих уровнях. Если возможно измерить подобие между группами, то дендрограмма изображается в масштабе, чтобы показать подобие между группами, которые объединяются.
На рис. 6.16, например, подобие между двумя группами выборок, которые объединенй на уровне 6, имеет 'значение 30. Значения подобия часто используются для определения того, было ли объединение Гл. б. Обучение бео учинили и груиииуоони Ркс. 6.15. Декдрограмма иерархической груивкровкв. 70 бу ~д О 50 и 00 50 251 б.!О. Иерарличеатл груррироека естественным или вынужденным. Для нашего гипотетического примера можно сказать, что объединения на уровнях 4 и 5 естественны, но значительное уменьшение подобия, необходимое для перехода на уровень 6, делает обьединенне на этом уровне вынужденным.
Мы вскоре увидим, как получить такие значения подобия. Благодаря простоте понятий иерархические процедуры группировки находятся среди наиболее известных методов. Процедуры можно разделить на два различных класса: агломеративный и делимый. Агложрапшеные (процедуры снизу-вверх, объединяющие) процедуры начинают с с одиночных групп и образуют последовательность постепенно обьединяемых групп. Делимые (сверху-вниз, разделяемые) процедуры начинают с одной группы, содержащей все выборки, и образуют последовательность постепенно расщепляемых групп. Вычисления, необходимые для перехода с одного уровня на другой, обычно проще для агломеративных процедур.
Однако, когда имеется много выборок, а нас интересует только небольшое число групп, такое вычисление должно повториться много раз. Для простоты ограничимся агломератнвными процедурами, отсылая читателя к литературе по делимым процедурам. 6.!0.2. АГЛОМЕРАТИВНАЯ ИЕРАРХИЧЕСКАЯ ГРУППИРОВКА Основные шаги в агломеративной группировке содержатся в следующей процедуре: Процедура: Базовая Агломеративная Группировка 1. Пусть сг и и Я"~=(х1), 1=1, ..., и.
Цикл: 2. Если Й с, останов. 3. Найти ближайшую пару групп, скажем Я', и Я'1. 4. Объединить Я'1 и Я'л уничтожить Я"1 и уменьшить с на единицу. 5, Перейти к Цикл. Описанная процедура заканчивается, когда достигнуто заданное число групп. Однако, если мы продолжим до с=1, то можем получить дендрограмму, подобную изображенной на рис. 6.15. На любом уровне расстояние между ближайшими группами может дать значение различия на этом уровне. Читатель обратит внимание на то, что мы не сказали, как измерять расстояние между двумя группами. Рассуждения здесь очень схожи с рассуждениями при выборе функции критерия. Для простоты ограничимся следующими мерами расстояния, предоставляя другие возможные меры воображению Гл. б.
Обучение бее учителя и групяироена читателя е( ы(Я"о Я')= пип ~~х — х'~~, Х,Яих ЕЯ/ Й,„(Я;, Я~) = гпах рх — х'ц, хеЯ"»ч х еЯ'т е(„е(Я'и Я~)= — '~ ~~» )~х — х'ц, ХЕЯ» Х' ЕЯ/ спеха (Я»' Я~) = »» еп; — гпу»». Все этн меры напоминают минимальную дисперсию, и они обычно дают одинаковые результаты, если группы компактные и хорошо Рис. 6Л6, Три примера. разделены. Однако, если группы близки друг к другу или их форма в основном не гиперсферическая, могут получиться разные резуль- б.!О. Иерархическая аруалироеха таты. Мы используем двумерные множества точек, показанные на рис. 6.16, для иллюстрации этих различий.
6.10.2.1. Алгоритм «ближайший сосед» Рассмотрим сначала случай, когда используется Н ~в»). Предположим, что мы рассматриваем точки данных как вершины графа, причем ребра графа образуют путь между вершинами в том же подмножестве й"»). Когда для измерения расстояния между подмножествами используется д ш, ближайшие соседи определяют ближайшие подмножества. Слияние й'з и й'! соответствует добавлению ребра между двумя ближайшими вершинами в Я', и й"!. Поскольку ребра, соединяющие группы, всегда проходят между различными группами, результирующий граф никогда не имеет замкнутых контуров или цепей; пользуясь терминологией теории графов, можно сказать, что эта процедура генерирует дерево.
Если так продолжать, пока все подмножества не будут соединены, в результате получим покрывающее дерево (остов) — дерево с путем от любой вершины к любой другой вершине. Более того, можно показать, что сумма длин ребер результирующего дерева не будет превышать суммы длин ребер для любого другого покрывающего дерева для данного множества выборок. Таким образом, используя с! ш в качестве меры расстояния, агломеративная процедура группировки превращается в алгоритм для генерирования минимального покрывающего дерева.
Рис. 6.17 показывает результат применения этой процедуры к данным из рис. 6.16. Во всех случаях процедура заканчивалась при с=2. Минимальное покрывающее дерево можно получить, добавляя самое короткое ребро между двумя группами. В первом случае, где группы компактны и хорошо разделены, найдены явные группы. Во втором случае наличие некоторых точек, расположенных так, что между группами создан некоторый мост, приводит к довольно неожиданной группировке в одну большую продолговатую группу и в одну маленькую компактную группу. Такое поведение часто называют «цепным эффектом» и иногда относят к недостаткам этой меры расстояния.
В случае, когда результаты очень чувствительны к шуму или к небольшим изменйниям в положении точек данных, такая критика вполне законна. Однако, как иллюстрирует третий случай, та же тенденция формирования цепей может считаться преимуществом, если группы сами по себе вытянуты или имеют вытянутые отростки.
х) В литературе результирующую процедуру часто называют алгоритмом ближайшего соседа или алгоритмом минимума. Если алгоритм заканчивается, когда расстояние между ближайшими группами превышает произвольный порог, его называют алгоритмом единичной связи. ») Хотя мы не будем широко использовать теорию графов, однако предполагается, что читатель в общих чертах знаком с втой теорией. Ясная, четкая трактовка дана в кинге О. Оре, Графы и их применение, М., «Мнр», )965.
Гл, б. Обушние без училмля и груллироека Рнс. блт. Результаты алгоритма «ближайший сосед». 6А0.2.2. Алгоритм «дальний сосед» Когда для измерения расстояния между группами используются й,„, возникновение вытянутых групп является нежелательным '). Применение процедуры можно рассматривать как получение графа, в котором ребра соединяют все вершины в группу. Пользуясь терминологией теории графов, можно сказать, что каждая группа образует полный подграф. Расстояние между двумя группами определяется наиболее удаленными вершинами в этих двух группах. Когда ») В литературе результирующую процедуру часто называют алгоритмом максимума или дальнею соседа.
Если он заканчивается, когда расстояние между двумя ближайшими группами превышает произвольный порог, его называют алгоритмом ладных с«язей. 6.10. Иерархическая груилирозка 255 Рис. 6Л8. Результаты алгоритма «дальний сосед». ближайшие группы объединяются, граф изменяется добавлением ребер между какдой парой вершин в двух группах.
Если мы определяем диаметр группы как наибольшее расстояние между точками в группе, то расстояние между двумя группами — просто диаметр их обьедннения. Если мы определяем диаметр разделения как наиболь. ший диаметр для группы в разделении, то каждая итерация увеличивает диаметр разделения минимально. Как видно из рис. 6.18, это является преимуществом, когда истинные группы компактны н примерно одинаковы по размерам. Однако в других случаях, как, например, в случае вытянутых групп, результирующая группировка бессмысленна. Это еще один пример наложения структуры на данные вместо нахождения их структуры. Г*. б. Обучение бее учингееи и груиииреена 6.10.2,3. Компромиссы Минимальная и максимальная меры представляют два крайних подхода в измерении расстояния между группами. Как все процедуры, содержащие максимумы и минимумы, они оказываются слишком чувствительными к различным отклонениям.
Использование усреднения — очевидный путь по возможности избежать этого, и е(,ч и д „„являются естественным компромиссом между г(;„и г(,„. С вычйслительной точки зрения Н „„— наиболее простая из всех мер, так как все другие требуют вычйсления всех пг пе пар расстояний ))х — х')). Однако такую меру, как г(,„е, можно использовать, когда расстояния 1~х — х'й заменены на меру подобия, а меру подобия между средними векторами трудно или невозможно определить. Мы оставляем читателю разобраться, как использование «(,„е или г( „„может изменить группировку точек на рис. 6.16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
