6.10.4. ИЕРАРХИЧЕСКАЯ ГРУППИРОВКА И СООТВЕТСТВУЮЩАЯ МЕТРИКА

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

или

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

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

При внимательном рассмотрении станет ясно, что как с 6n,j„, так и с величина либо остается такой же, либо увеличивается при увеличении к. Более того, мы предполагаем, что нет двух одинаковых выборок в множестве, так что і»2>0. Следовательно,

0=Уі<Уа<г;з<. . .<и„.

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

1)   d{\, х')=0 «Ф х=х',

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

3)   d{x, x")^d(x, x')+d(x', x").

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

Обратно, если с! (х, х')=0, то из Уг=0 следует, что х и х' должны быть в одной группе на уровне 1, и поэтому x==x^ Правильность второго требования немедленно следует из определения d{\, х'). Остается третье требование — неравенство треугольника. Пусть d(\, \')=Ѵі и d(\', x")=Vj, так что х и х' находятся в одной группе на уровне г, а х' и х" — в одной группе на уровне /. Из-за иерархического объединения групп одна из этих групп включает другую. Если k=max{i, /), ясно, что на уровне k х, \' и х" находятся в одной группе, и, следовательно, что

Но так как значения монотонно не уменьшаются, то ѵ^ = тах(ѵі, Vj), и поэтому

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