🔴 Сложный ⏱️ 25 минут

Иерархическая кластеризация: строим дерево данных

Иерархическая кластеризация: строим дерево данных

🎯 Зачем это нужно?

Представь, что ты анализируешь музыкальные предпочтения в TikTok 🎵. У тебя есть 10000 пользователей, и ты хочешь понять, какие группы слушателей существуют. Но вот проблема - ты не знаешь, сколько должно быть групп!

Обычная k-means требует заранее задать количество кластеров. А что если их не 3, а 5? Или 17? Иерархическая кластеризация решает эту проблему элегантно - она строит дерево всех возможных разбиений и позволяет выбрать нужное количество кластеров уже потом!

🏥 В медицине: Классификация заболеваний по симптомам без знания точного количества типов 📊 В маркетинге: Сегментация клиентов для персонализации рекламы 🧬 В биоинформатике: Построение эволюционных деревьев видов 🛒 E-commerce: Группировка товаров для рекомендательных систем

📚 История вопроса

В 1963 году статистики столкнулись с проблемой: как группировать виды животных, не зная заранее их количество? Роберт Сокал и Питер Снит предложили революционную идею - строить не одно разбиение, а дерево всех возможных!

Интересный факт: метод Ward’а (1963) изначально создавался для оптимизации расположения больничных коек, но стал одним из самых популярных в ML! 🏥

💡 Интуиция

Представь семейное древо, но наоборот 🌳. В обычном дереве от предков идут потомки. В иерархической кластеризации мы начинаем с “детей” (отдельных точек) и постепенно объединяем их в “родительские” кластеры.

Агломеративный подход (снизу вверх):

  1. Каждая точка - отдельный кластер
  2. Находим два самых близких кластера
  3. Объединяем их в один
  4. Повторяем, пока не останется один большой кластер

Дивизивный подход (сверху вниз):

  1. Все точки - один кластер
  2. Разделяем на два самых далёких подкластера
  3. Повторяем для каждого подкластера
  4. Останавливаемся, когда каждая точка - отдельный кластер

[МЕДИА: image_01] Описание: Визуализация процесса агломеративной кластеризации с постепенным объединением точек в кластеры Промпт: “educational illustration showing agglomerative clustering process, data points gradually merging into clusters, step-by-step visualization, tree-like structure formation, modern ML visualization style, blue and orange colors”

📐 Формальное определение

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

Ключевые компоненты:

1️⃣ Метрика расстояния между объектами:

  • Евклидово: d(x,y) = ||x - y||₂
  • Манхэттенское: d(x,y) = ||x - y||₁
  • Косинусное: d(x,y) = 1 - (x·y)/(||x||·||y||)

2️⃣ Linkage - расстояние между кластерами:

  • Single linkage: d(A,B) = min{d(a,b) : a∈A, b∈B}
  • Complete linkage: d(A,B) = max{d(a,b) : a∈A, b∈B}
  • Average linkage: d(A,B) = (1/|A||B|)∑∑d(a,b)
  • Ward linkage: минимизирует внутрикластерную дисперсию

3️⃣ Дендрограмма - древовидная диаграмма, показывающая иерархию объединений

[МЕДИА: image_02] Описание: Дендрограмма с объяснением различных типов linkage методов Промпт: “comprehensive dendrogram illustration showing different linkage methods (single, complete, average, ward), mathematical formulas, color-coded branches, educational data science visualization, clean technical style”

🔍 Примеры с разбором

Пример 1: Кластеризация студентов по оценкам

Есть 5 студентов с оценками по математике и программированию:

  • A: (9, 8)
  • B: (8, 9)
  • C: (3, 4)
  • D: (4, 3)
  • E: (6, 7)

Шаг 1: Вычисляем матрицу расстояний (Евклидово)

    A    B    C    D    E
A   0   1.41  8.49  8.49  3.61
B  1.41  0   8.06  9.22  3.61  
C  8.49 8.06  0   1.41  4.47
D  8.49 9.22 1.41  0   5.00
E  3.61 3.61 4.47  5.00  0

Шаг 2: Single linkage агломерация

  1. Минимальное расстояние: d(A,B) = 1.41 → объединяем {A,B}
  2. Пересчитываем: d({A,B},C) = min(8.49,8.06) = 8.06
  3. Минимальное: d(C,D) = 1.41 → объединяем {C,D}
  4. Минимальное: d({A,B},E) = min(3.61,3.61) = 3.61 → получаем {A,B,E}
  5. Финальное объединение: {A,B,E} ∪ {C,D}

Результат: Два логичных кластера - “отличники” {A,B,E} и “отстающие” {C,D}

Пример 2: Ward метод vs Single linkage

Ward минимизирует внутрикластерную дисперсию: SSE(кластер) = ∑(xᵢ - μ)²

При объединении кластеров A и B в C: ΔSE = SSE(C) - SSE(A) - SSE(B)

Ward выбирает объединение с минимальным увеличением ошибки!

from scipy.cluster.hierarchy import dendrogram, linkage
import numpy as np

# Наши данные
X = np.array([[9,8], [8,9], [3,4], [4,3], [6,7]])

# Single linkage
Z_single = linkage(X, method='single')

# Ward method  
Z_ward = linkage(X, method='ward')

# Строим дендрограммы
dendrogram(Z_single)
dendrogram(Z_ward)

[МЕДИА: image_03] Описание: Сравнение дендрограмм для разных методов linkage на одних данных Промпт: “side-by-side comparison of dendrograms using different linkage methods, same dataset, clear differences in clustering structure, educational data visualization, matplotlib style”

🎮 Практика

Базовый уровень 🟢

Задание 1: У тебя есть 4 точки: A(1,1), B(1,2), C(5,5), D(6,6). Построй дендрограмму методом single linkage.

Задание 2: Объясни своими словами, в чём разница между single и complete linkage.

Задание 3: Почему иерархическая кластеризация лучше k-means для исследовательского анализа данных?

Задание 4: В каких случаях лучше использовать агломеративный, а в каких - дивизивный подходы?

Продвинутый уровень 🟡

Задание 5: Реализуй простую агломеративную кластеризацию с single linkage на Python (без библиотек).

Задание 6: У интернет-магазина есть данные о покупках пользователей. Как бы ты применил иерархическую кластеризацию для персонализации?

Задание 7: Сравни вычислительную сложность иерархической кластеризации и k-means. Когда какой алгоритм предпочтительнее?

Задание 8: Как выбрать оптимальное количество кластеров, глядя на дендрограмму?

Челлендж 🔴

Задание 9: Модифицируй Ward метод для работы с категориальными признаками. Какие изменения в формуле необходимы?

Задание 10: Реализуй дивизивную кластеризацию, используя k-means на каждом шаге разделения.

Задание 11: Как бы ты решил проблему “chaining effect” в single linkage для анализа социальных сетей?

⚠️ Частые ошибки

❌ Ошибка: Использование single linkage для всех задач ✅ Правильно: Single linkage склонен к “цепочечному эффекту” - создаёт длинные тонкие кластеры 💡 Почему: Для компактных кластеров лучше complete или ward linkage

❌ Ошибка: Не нормализация данных перед кластеризацией
✅ Правильно: Всегда приводи признаки к одному масштабу 💡 Почему: Признак “зарплата” (50000) будет доминировать над “возрастом” (25)

❌ Ошибка: Выбор количества кластеров только по дендрограмме ✅ Правильно: Используй дополнительные метрики: silhouette score, gap statistic 💡 Почему: Визуальная интерпретация может быть обманчивой

❌ Ошибка: Применение к большим данным без оптимизации ✅ Правильно: Для n > 10000 используй approximate методы или семплинг 💡 Почему: Классическая иерархическая кластеризация имеет сложность O(n³)

❌ Ошибка: Игнорирование интерпретируемости кластеров ✅ Правильно: После кластеризации анализируй профили получившихся групп 💡 Почему: Кластеры должны иметь бизнес-смысл, а не только математическую обоснованность

🎓 Главное запомнить

✅ Суть: Иерархическая кластеризация строит дерево всех возможных разбиений данных ✅ Ключевая формула: Linkage функции определяют расстояние между кластерами
✅ Применение: Исследовательский анализ данных, когда количество кластеров неизвестно

🔗 Связь с другими темами

Назад: Урок 320 заложил основы кластеризации и метрик расстояний Вперёд: Изучим DBSCAN (кластеризация по плотности) и спектральную кластеризацию Связано: Методы оценки качества кластеризации, визуализация высокомерных данных через PCA/t-SNE

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!