Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 50
Текст из файла (страница 50)
6.10.3. ПОШАГОВАЯ ОПТИМАЛЪИАЯ ИЕРАРХИЧЕСКАЯ ГРУППИРОВКА Мы заметили раньше, что, если группы растут за счет слияния ближайшей пары групп, результат напоминает минимальную дисперсию. Однако, когда мера расстояния между группами выбрана произвольно, редко можно утверждать, что результирующее разделение приводит к экстремуму какой-либо конкретной функции критерия. В действительности иерархическая группировка определяет группу как какой-то результат после применения процедуры группировки. Однако простая модификация позволяет получить пошаговую процедуру оптимизации для получения экстремума функции критерия. Это делается простой заменой шага 3 в элементарной агломеративной процедуре группировки (разд. 6.16.2) на 3'.
Найти пару разделенных групп Я', и й;, слияние которых увеличит (или уменьшит) функцию критерия минимально. Это гарантирует нам, что на каждой итерации мы сделали лучший шаг, даже если окончательное разделение не будет оптимальным. Мы видели ранее, что использование г(,„вызывает наименьшее возможное увеличение диаметра разделения на каждомшаге. Приведем еще один простой пример с функцией критерия суммы квадратичных ошибок е,. С помощью анализа, очень сходного с использованным в разд.
6.9, мы находим, что пара групп, слияние которых увеличивает е', на минимально возможную величину, это такая пара, для которой «расстояние» г(,(Ю„Я'~) = У вЂ” )) тг — тг~) )гг и;+ и~ г57 6.10. Иериркичееиак группиревеи минимально. Следовательно, при выборе групп для слияния этот критерий учитывает как число выборок в каждой группе, так и расстояние между группами. В общем случае использование г1, приведет к тенденции увеличения размера групп за с гет присоединения одиночных или малых групп к большим, а не за счет слияния групп средних размеров.
Хотя окончательное разделение может не минимизировать Г„оно обычно дает хорошую начальную точку для дальнейшей йтерационной оптимизации. биоки ИЕРАРХИЧЕСКАЯ ГРУППИРОВКА И СООТВЕТСТВУЮЩАЯ МЕТРИКА Предположим, что мы не имеем возможности снабдить метрикой наши данные, но что можем измерить степень различия 6 (х, х') для каждой пары выборок, где 6(х, х'))О, причем равенство нулю выполняется тогда и только тогда, когда х = х'. Тогда все еще можно использовать агломеративную процедуру, учитывая, что пара ближайших групп — это пара с наименьшими различиями. Интересно, что если мы определяем различия между двумя группами как 6 ы(Я'г, .й'7) =- ш1п 6(х, х') ге йь х'е,к7 или 6,„(Юо .й7) = шах 6(х, х'), хе $0 х'гЯ7 то иерархическая процедура группировки даст функцию расстояния для данного множества из и выборок.
Более того, упорядочение расстояний между выборками будет инвариантно относительно любого монотонного преобразования величин различий. Чтобы увидеть, как это происходит, начнем с определения величины ои для группировки на уровне )г. Для уровня 1 имеем о,=О. Для всех более высоких уровней си равна минимальному различию между парами разных групп на уровне (7г — 1). При внимательном рассмотрении станет ясно, что как с 6 „, так и с б,„величина се либо остается такой же, либо увеличивается при увеличении й.
Более того, мы предполагаем, что нет двух одинаковых выборок в множестве, так что ое)О. Следовательно, 0 =ог(эе~(ог(...~(си. Теперь можно определить расстояние г((х, х') между х и х' как величину группировки на нижнем уровне, для которой х и х' находятся в одной группе.
Чтобы убедиться, что это действительно функция расстояния, или метрика, мы должны показать следующее: 1) г((х, х )=0 4гу х=х', 2) г1(х, х')=-д(х', х), 3) с((х, х")(г((х, х')+с((х', х"). Гл. б. Обучение бее учиигелл и груиииреека Легко видеть, что первое требование удовлетворяется. Самый низкий уровень, на котором х и х' могут быть в одной группе, это уровень 1, так что е((х, х')=о,=О. Обратно, если п(х, х')=О, то из о,=О следует, что х и х' должны быть в одной группе на уровне 1,' и поэтому х=х'. Правильность второго требования немедленно следует из определения г((х, х').
Остается третье требование — неравенство треугольника. Пусть е((х, х')=ое и е((х', х")=оп так что х и х' находятся в одной группе на уровне(, а х' и х" — в одной группе на уровне1. Изтза иерархического объединения групп одна из этих групп включает другую. Если А=шах(1, е), ясно, что на уровне й х, х' и х' находятся в одной группе, и, следовательно, что е((х, х")в од. Но так как значения аь монотонно не уменьшаются, то пи= шах (оо от), и поэтому е((х, х") шах(е((х, х'), г((х', х")).
Это называется ультраметрическим неравенством. Оно даже сильнее, чем неравенство треугольника, так как шах(г((х, х'), е((х', х'))а г((х, х')+г((х', х"). Таким образом, удовлетворяются все условия, и мы получили подлинную метрику для сравнения л выборок. 8.11. методы, использующие теОРию ГРАФОВ В двух или трех примерах мы использовали линейные графы, чтобы с иной точки зрения взглянуть на природу некоторых процедур группировки. Если формулы, использующие нормальные смеси и разделения на основе минимальной дисперсии, кажется, возвращают нас к изображению групп как изолированных скоплений точек, то язык и понятия теории графов дают возможность рассмотреть более скрытые структуры.
К сожалению, немногое из таких возможностей изучалось систематически, и пока не существует единого подхода к постановке задач группировки как задач теории графов. Таким образом, эффективное использование этих идей — это пока еще во многом искусство, и читатель, желающий исследовать такие возможности, должен быть достаточно изобретателен, Мы начнем наш краткий обзор методов теории графов, вернувшись к рассмотрению простой процедуры, которая строила графы, показанные на рис. 6.8. Здесь было выбрано пороговое расстояние е(е и считалось, что две точки находятся в той же группе, если расстояние между ними меньше е(е.
Эту процедуру легко обобщить для применения к произвольным мерам подобия. Предположим, что мы выбрали пороговое значение з„и будем говорить, что х подобен х', если з(х, х'))зе. Это определяет матрицу подобия 5=ЬО) размера б.11. Меюеаы, использующие аморию гра4юе пХн, где ( 1, если з(хез х1) ) з„ з11 = 1 0 в противном случае, 1, 1=1, ..., н. Эта матрица определяет граф подобия, в котором вершины соответствуют точкам и ребро соединяет вершины ь' и 1 тогда и только тогда, когда хм=1. Группировка, полученная при помощи алгоритма единственной связи и модифицированного алгоритма полной связи, легко описы- о 11иаметральеый ала влалааааметральеий путь ° Неааамеаральеый путе ° ° ° Ф у~» Рис.
6.19. Группы, образованные удзленнем несовместимых ребер (Цьнь, 1971) а — множество точек, б — миннмьльное покрывающее дерево, в — группы. вается при помощи этого графа. В случае алгоритма единственной связи две выборки х и х' находятся в одной группе тогда и только тогда, когда существует цепь х„х„..., хь, такая, что х подобен х„х, подобен х, и т. д. для всей цепи. Следовательно, такая грунпировка соответствует связанным компонентам в графе подобия. В случае алгоритма полной связи все выборки в данной группе должны быть подобны друг другу, и ни одна выборка не должна находиться более чем в одной группе.
Если мы опускаем второе требование, то тогда такая группировка соответствует максимальным полным нодграфам в графе подобия, причем в «наибольших» подграфах ребра объединяют все пары вершин. (В общем случае группы, полученные с помощью алгоритма полной связи, можно найти среди максимальных полных подграфов, но их нельзя определить, не зная степени подобия.) В предыдущем разделе мы заметили, что алгоритм ближайшего соседа можно рассматривать как алгоритм нахождения минимального покрывающего дерева. Обратно, при данном минимальном Гл. б. Обучение беа учипмлл и еруиаироека покрывающем дереве можно найти группировки, полученные по алгоритму ближайшего соседа. Удаление самого длинного ребра вызывает разделение на две группы, удаление следующего по длине ребра — разделение на три группы и т.
д, Это дает способ получения делимой иерархической процедуры и предлагает другие возможности деления графа на подграфы. Например, при выборе ребра — кандидата иа удаление мы можем сравнить его длину с длинами других ребер, прилегающих к его вершинам. Назовем ребро несовместимым, если его длина I значительно больше 7 — средней длины всех других ребер, прилегающих к его вершинам. На рис, бдй показаны минимальное покрывающее дерево для двумерного множества точек и группы, полученные систе.
матическим удалением всех ребер, чья длина 1 больше 2й Отметим чувствительность этого критерия к локальным условиям, дающую результаты, которые значительно отличаются от простого удаления двух самых длинных ребер. Когда точки данных располагаются в длинные цепочки, минимальное покрывающее дерево образует Рис. 6.2О минимальное покрывающее де- естественнЫй скелет для рево с бимодальным распределением длин цепочки.
Если мы опредеребер. лим диаметральньей путь как самый длинный путь по дереву, то тогда цепочка будет характеризоваться глубиной отклонения от диаметрального пути. Напротив, для большого, равномерно расположенного облака точек дерево не будет иметь явного диаметрального пути, а будет иметь несколько различных путей, близких к диаметральному. Для любого из ннх некоторое число вершин будет находиться вне пути. В то время как небольшие изменения в расположении точек данных могут вызвать 6.12. пробмма обоснованности значительное перераспределение минимального покрывающего дерева, онн обычно мало влИяют на такие статистики. Одной из полезных статистик, которую можно получить из минимального покрывающего дерева, является распределение длин ребер. На рнс. 6.20 представлен случай, когда плотное облако располагается внутри редкого.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
