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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дендограма

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