Иерархические методы кластеризации. 
Агломеративная кластеризация. 
Разделяющая, или дивизивная, кластеризация. 
Дендрограмма

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

Алгоритмы упорядочивания данных указанного типа исходят из того, что некое множество объектов характеризуется определённой степенью связности. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы, в свою очередь, подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации. Как и большинство визуальных способов представления зависимостей графы быстро теряют наглядность при увеличении числа объектов. Существует ряд специализированных программ для построения графов.

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

Далее необходимо выбрать метод построения дендрограммы, который определяет способ пересчёта матрицы сходства (различия) после объединения (или разделения) очередных двух объектов в кластер.

В работах по кластерному анализу описан довольно внушительный ряд способов построения (англ. sorting strategies) дендрограм^]:

• 1. Метод одиночной связи Также известен, как «метод ближайшего соседа».
• 2. Метод полной связи Также известен, как «метод дальнего соседа».
• · Метод средней связи
• · Взвешенный (
• 1. Центроидный метод (англ. pair-group method using the centroid average).
• · Невзвешенный.
• · Взвешенный (медианный).
• 1. Метод Уорда (англ. Ward’s method).

Для первых трёх методов существует общая формула, предложенная А. Н. Колмогоровым для мер сходства.

где — группа из двух объектов (кластеров) и; — объект (кластер), с которым ищется сходство указанной группы; — число элементов в кластере; — число элементов в кластере. Для расстояний имеется аналогичная формула Ланса — Вильямса^[4].

Центроидный метод использует для пересчёта матрицы расстояний^[5]. В качестве расстояния между двумя кластерами в этом методе берётся расстояние между их центрами тяжести.

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