Определения

Рассмотрим последовательность разделений n выборок на c групп. Первое из них - это разделение на n групп, причем каждая из групп содержит точно по одной выборке. Следующее разделение на n-1 групп, затем на n-2 и т.д. до n-го, в котором все выборки образуют одну группу. Будем говорить, что находимся на k-ом уровне в последовательности, когда c = n - k+1. Таким образом, первый уровень соответствует n-группам, а n-й одной группе. Если даны две любые выборки x и x’ , на некотором уровне они будут собраны в одну группу. Если последовательность обладает тем свойством, что, когда две выборки попадают в одну группу на уровне k, они остаются вместе на более высоких уровнях, то такая последовательность называется иерархической группировкой.

Дендрограмма иерархической группировки

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

Процедуры иерархической группировки можно разделить на два различных класса агломеративный и дивизимный (делимый). Агломеративные процедуры (снизу-вверх, объединяющие) начинают с c одиночных групп и образуют последовательность постепенно объединяемых групп. Дивизимные (сверху-вниз, разделяющие) процедуры начинают с одной группы, содержащей все выборки и образуют последовательность постепенно объединяемых групп. Вычисления, необходимые для перехода с одного уровня на другой, обычно проще для агломеративных процедур. Однако, когда имеется много выборок, а нас интересует только небольшое число групп, такое вычисление должно повториться много раз, в этом случае более оправданным может оказаться применение дивизимных алгоритмов.