6.10.3. Пошаговая оптимальная иерархическая группировка

Мы заметили раньше, что, если группы растут за счет слияние ближайшей пары групп, результат напоминает минимальную дис­персию. Однако, когда мера расстояния между группами выбран;. произвольно, редко можно утверждать, что результирующее разде­ление приводит к экстремуму какой-либо конкретной функции кри­терия. В действительности иерархическая группировка определяет группу как какой-то результат после применения процедуры группировки. Однако простая модификация позволяет получить пошаговую процедуру оптимизации для получения экстремума функции критерия. Это делается простой заменой шага 3 в элементарной агломеративной процедуре группировки (разд. 6.10.2) на

3'. Найти пару разделенных групп X_i X_j,, слияние которых увеличит (или уменьшит) функцию критерия минимально.

Это гарантирует нам, что на каждой итерации мы сделали лучший шаг, даже если окончательное разделение не будет оптимальным.

Мы видели ранее, что использованиеd_max вызывает наименьшее возможное увеличение диаметра разделения на каждом шаге. При­ведем еще один простой пример с функцией критерия суммы квад­ратичных ошибок /g. С помощью анализа, очень сходного с исполь­зованным в разд. 6.9, мы находим, что пара групп, слияние которых увеличивает J_e на минимально возможную величину, это такая па­ра, для которой «расстояние» минимально. Следовательно, при выборе групп для слияния этот критерий учитывает как число выборок в каждой группе, так и рас­стояние между группами. В общем случае использование d_e приведет к тенденции увеличения размера групп за счет присоединения оди­ночных или малых групп к большим, а не за счет слияния групп средних размеров. Хотя окончательное разделение может не мини­мизировать J_e, оно обычно дает хорошую начальную точку для дальнейшей итерационной оптимизации.

6.10.4. Иерархическая группировка и соответствующая метрика

Предположим, что мы не имеем возможности снабдить метрикой наши данные, но что можем измеритьстепень различия (х,х') для каждой пары выборок, где (х,х')>0, причем равенство нулю вы­полняется тогда и только тогда, когда х=х'. Тогда все еще можно использовать агломеративную процедуру, учитывая, что пара бли­жайших групп — это пара с наименьшими различиями. Интересно, что если мы определяем различия между двумя группами как

или

то иерархическая процедура группировки даст функцию расстояния для данного множества из п выборок. Более того, упорядочение расстояний между выборками будет инвариантно относительно лю­бого монотонного преобразования величин различий.

Чтобы увидеть, как это происходит, начнем с определения величины v_k для группировки на уровне k. Для уровня 1 имеем v₁=0. Для всех более высоких уровней v_k равна минимальному раз­личию между парами разных групп на уровне (k—1).

При внимательном рассмотрении станет ясно, что как с _min, так и с _max величина v_k либо остается такой же, либо увеличивает­ся при увеличении k. Более того, мы предполагаем, что нет двух одинаковых выборок в множестве, так что v₂>0. Следовательно, 0= v₁< v₂ v₃ … v_n.

Теперь можно определить расстояние d(x,х') между х и х' как величину группировки на нижнем уровне, для которой х и х' на­ходятся в одной группе. Чтобы убедиться, что это действительно функция расстояния, или метрика, мы должны показать следующее:

1) d(x, x')=0 x=x',

2) d(x, x')=d(x', x),

3) d(x, x")d(x, x')+d(x', x").

Легко видеть, что первое требование удовлетворяется. Самый низкий уровень, на котором х и х' могут быть в одной группе, это уровень 1, так что d(x, x')=υ1=0.

Обратно, если d(x, x')=0, то из υ₂=0 следует, что х и х' должны быть в одной группе на уровне 1, и поэтому х=х'. Правильность второго требования немедленно следует из определения d(x, x'). Остается третье требование — неравенство треугольника. Пусть d(x, x')= υ_i и d(x', x'')=υ_j, так что х и х' находятся в одной группе на уровне i, а х' и х" — в одной группе на уровне j. Из-за иерархиче­ского объединения групп одна из этих групп включает другую. Если k=max(i, j), ясно, что на уровне k х, х' и х" находятся в од­ной группе, и, следовательно, что

d(x', x'')≤ υ_k

Но так как значения υ_k монотонно не уменьшаются, то υ_k=max(υ_i, υ_j), и поэтому

d(x', x'')≤ max (d(x, x'), d(x', x'')).

Это называется ультраметрическим неравенством. Оно даже сильнее, чем неравенство треугольника, так как max(d(x, х'), d(x', x"))≤d(x, x')+d(x', х"). Таким образом, удовлетворяются все условия, и мы получили подлинную метрику для сравнения n вы­борок.