6.10.3.     ПОШАГОВАЯ ОПТИМАЛЬНАЯ ИЕРАРХИЧЕСКАЯ ГРУППИРОВКА

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

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

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

Мы видели ранее, что использование d^ax вызывает наименьшее возможное увеличение диаметра разделения на каждом шаге. Приведем еще один простой пример с функцией критерия суммы квадратичных ошибок Jg. С помощью анализа, очень сходного с использованным в разд. 6.9, мы находим, что пара групп, слияние которых увеличивает J^ на минимально возможную величину, это такая пара, для которой «расстояние»

минимально. Следовательно, при выборе групп для слияния этот критерий учитывает как число выборок в каждой группе, так и расстояние между группами. В общем случае использование приведет к тенденции увеличения размера групп за счет присоединения одиночных или малых групп к большим, а не за счет слияния групп средних размеров. Хотя окончательное разделение может не минимизировать Jg, оно обычно дает хорошую начальную точку для дальнейшей итерационной оптимизации.