Алгоритм може починатися або з кожної точки у власному кластері з подальшим об'єднанням (агломеративне кластерування), або з усіх точок в одному кластері з подальшим розділенням на менші кластери (дивізивне кластерування).

Оскільки агломеративне кластерування є більш поширеним підходом, зосередимося саме на ньому.

Найпоширеніший тип ієрархічного кластерування — це підхід знизу вгору. Алгоритм виглядає так:

1. Ініціалізація: кожна точка даних розглядається як окремий кластер;

2. Обчислення матриці близькості: обчислення відстані між кожною парою кластерів;

3. Об'єднання кластерів: два найближчі кластери об'єднуються в один кластер;

4. Оновлення матриці близькості: повторний розрахунок відстаней між новим кластером та всіма іншими кластерами;

5. Повторення: кроки 3 і 4 повторюються, доки всі точки даних не будуть об'єднані в один кластер.

Типи зв'язків

Близькість між двома кластерами визначається типом зв'язку. Поширені методи зв'язку, які використовуються в ієрархічному кластеруванні:

• Одиничний зв'язок: відстань між найближчими двома точками у двох кластерах;

• Повний зв'язок: відстань між найвіддаленішими двома точками у двох кластерах;

• Середній зв'язок: середня відстань між усіма парами точок у двох кластерах;

• Метод Варда: мінімізує збільшення загальної внутрішньокластерної дисперсії при об'єднанні двох кластерів.

Вибір методу зв'язку може впливати на форму та структуру отриманих кластерів. Для вибору найкращого методу для ваших даних часто корисні експерименти та знання предметної області.

Дендограма

Результати ієрархічного кластерування часто візуалізують за допомогою дендограми.