Иерархическая кластеризация

Представьте, что вы биолог и хотите классифицировать 200 видов бабочек по форме крыльев. Сколько групп задать? 5? 10? 30? А может, бабочки группируются на нескольких уровнях - виды внутри родов, роды внутри семейств? K-Means требует ответа заранее, но иерархическая кластеризация строит полное дерево родства и позволяет выбрать уровень детализации уже потом, глядя на данные.

• **Филогенетика:** биологи строят деревья эволюционного родства видов с помощью иерархической кластеризации по ДНК-последовательностям - именно так был реконструирован "общий предок" всех живых организмов (LUCA)
• **Сегментация клиентов:** маркетологи используют дендрограммы для многоуровневой сегментации: на верхнем уровне "премиум" и "масс-маркет", внутри каждого - микросегменты по поведению, что позволяет настраивать коммуникацию на нужном уровне детализации
• **Кластеризация генов:** в биоинформатике hierarchical clustering с heatmap - стандартный инструмент для анализа экспрессии генов: какие гены активируются вместе, какие группы генов связаны с конкретными заболеваниями

От численной таксономии к методу Уорда

Иерархическая кластеризация повзрослела в биологии, где стремление строить деревья жизни существует столетиями. Переломным стал 1963 год, когда Роберт Сокал и Питер Снит опубликовали «Principles of Numerical Taxonomy», доказывая, что виды следует группировать по измеримому сходству, вычисленному сразу по множеству признаков, а не по интуиции эксперта. Их книга дала биологам конкретные алгоритмы пошагового объединения наиболее похожих групп и превратила кластеризацию из расплывчатой идеи в воспроизводимую численную процедуру. В том же году статистик Джо Уорд предложил другое правило объединения в своей работе об иерархической группировке: на каждом шаге сливать те два кластера, чьё объединение меньше всего увеличивает суммарную внутрикластерную дисперсию. Метод Уорда и сегодня остаётся выбором по умолчанию в большинстве библиотек, а дендрограммы, которые популяризировала численная таксономия, теперь встречаются далеко за пределами биологии - в маркетинге, геномике и анализе документов.

Предварительные знания

• K-Means Clustering

Agglomerative: снизу вверх

В предыдущем уроке мы изучили K-Means, где нужно заранее указать количество кластеров K. Но что если вы не знаете, сколько групп в данных? Иерархическая кластеризация решает эту проблему: она строит **полное дерево вложенных кластеров** - от отдельных точек до одного общего кластера - и позволяет выбрать нужный уровень "обрезки" уже после обучения.

**Agglomerative clustering** (от латинского agglomerare - "собирать в кучу") - самый популярный вариант иерархической кластеризации. Он работает **снизу вверх (bottom-up)**: начинает с N отдельных кластеров (каждая точка - свой кластер) и на каждом шаге объединяет два ближайших кластера в один. Процесс повторяется, пока не останется единственный кластер, содержащий все точки.

Ключевое преимущество: **решение о количестве кластеров можно отложить**. Алгоритм строит полную иерархию слияний, а вы выбираете уровень "обрезки" постфактум, анализируя структуру данных. В K-Means же неправильный выбор K требует полного перезапуска алгоритма.

**Сложность алгоритма:** - **Время:** O(n^3) в базовой реализации (на каждом из n шагов ищем минимум в матрице расстояний n x n). С оптимизациями (min-heap) можно достичь O(n^2 log n). - **Память:** O(n^2) для хранения матрицы попарных расстояний. Для сравнения: K-Means работает за O(n * K * i), где i - число итераций (обычно 10-50). Поэтому для больших датасетов (> 10 000 точек) K-Means значительно быстрее.

На практике agglomerative clustering используют, когда размер данных умеренный (до ~10 000 точек) и важна именно **иерархическая структура** - например, таксономия видов в биологии, сегментация клиентов по уровням, или группировка документов по темам с подтемами.

Divisive: сверху вниз

Если agglomerative идёт снизу вверх, то **divisive clustering** работает в обратном направлении - **сверху вниз (top-down)**. Начинаем с одного кластера, содержащего все точки, и на каждом шаге разделяем наименее "связный" кластер на два. Процесс продолжается до тех пор, пока каждая точка не окажется в собственном кластере.

Наиболее известный divisive алгоритм - **DIANA (DIvisive ANAlysis)**, предложенный Кауфманом и Руссеувом в 1990 году. На каждом шаге DIANA выбирает кластер с наибольшим диаметром (максимальное расстояние между двумя точками внутри кластера) и разделяет его, пытаясь минимизировать среднее расстояние внутри получившихся подкластеров.

Главная проблема divisive подхода - **сложность оптимального разделения**. Чтобы разделить кластер из m точек на два, нужно перебрать 2^(m-1) - 1 вариантов разбиения. Для кластера из 20 точек это уже более 500 000 вариантов. Поэтому DIANA использует жадную эвристику, а не полный перебор, что не гарантирует оптимальный результат.

На практике **agglomerative используют в 95%+ случаев**. Divisive может быть полезен, если вы знаете, что данные имеют четкую иерархическую структуру сверху (например, деление на "развитые" и "развивающиеся" страны, а внутри - дальнейшее дробление). Но даже в таких случаях agglomerative обычно дает схожие результаты при меньших вычислительных затратах.

**Важное отличие от K-Means:** оба подхода иерархической кластеризации - и agglomerative, и divisive - являются **детерминированными**. При одних и тех же данных они всегда дают одинаковый результат. K-Means, в свою очередь, зависит от случайной инициализации центроидов и может давать разные результаты при разных запусках.

Дендрограмма: визуализация иерархии

Иерархическая кластеризация создает не просто набор кластеров, а **полное дерево слияний**. Для визуализации этого дерева используется **дендрограмма** (от греч. dendron - "дерево" и gramma - "запись"). Это диаграмма, где каждое слияние (или разделение) изображено как соединение двух ветвей, а **высота соединения** показывает расстояние, на котором произошло объединение.

Дендрограмма - главный инструмент для выбора количества кластеров. Ищите **большой скачок высоты** между последовательными слияниями: это означает, что объединяемые кластеры были далеко друг от друга, то есть "естественной" границей данных. Горизонтальная линия обрезки на этом уровне дает осмысленное разбиение.

**Что хранится в linkage matrix Z?** Каждая строка Z содержит 4 значения: - **Z[i, 0]** и **Z[i, 1]** - индексы объединяемых кластеров - **Z[i, 2]** - расстояние между ними при слиянии - **Z[i, 3]** - количество точек в новом кластере Индексы 0..n-1 - это исходные точки, индексы n, n+1, ... - новые кластеры, образованные слияниями. Это компактное представление всего дерева.

Дендрограмма дает информацию, которую K-Means дать не может: **многоуровневую структуру данных**. Например, в биологии виды объединяются в роды, роды в семейства, семейства в отряды - и дендрограмма показывает всю эту иерархию на одной диаграмме. В маркетинге клиенты группируются в микросегменты, те - в макросегменты, а те - в стратегические группы.

**Ловушка больших данных:** дендрограмма с 10 000+ точек становится нечитаемой - листья сливаются в сплошную полосу. Решение: 1. уменьшить выборку до 500-1000 точек 2. использовать `truncate_mode='level'` в scipy для показа только верхних уровней 3. вычислить кластеры программно через `fcluster()` без визуализации.

Методы связи (Linkage)

Ключевой вопрос agglomerative кластеризации: как измерить **расстояние между двумя кластерами**, если каждый из них содержит несколько точек? Ответ на этот вопрос - **метод связи (linkage)** - кардинально влияет на форму получаемых кластеров. Один и тот же датасет с разными linkage может дать совершенно разные результаты.

**Single linkage** измеряет расстояние между двумя ближайшими точками из разных кластеров. Это приводит к **"цепочечному эффекту" (chaining)**: если между двумя облаками точек есть "мост" из нескольких промежуточных точек, single linkage объединит эти облака в один кластер, протянув цепочку через мост. Это полезно для обнаружения кластеров произвольной формы (например, двух полумесяцев), но плохо работает с шумными данными.

**Complete linkage** измеряет расстояние между двумя самыми далекими точками из разных кластеров. Это дает **компактные, примерно сферические кластеры** и устойчиво к шуму, но плохо работает с вытянутыми формами. **Average linkage** берет среднее всех попарных расстояний - это компромисс между single и complete.

**Как выбрать метод связи?** - **Ward** - безопасный выбор по умолчанию. Дает компактные кластеры примерно одного размера. Работает как "иерархический K-Means". - **Complete** - если нужны компактные кластеры, но Ward не подходит (например, нужна другая метрика расстояния, не евклидова). - **Single** - если кластеры имеют сложную форму (цепочки, полумесяцы, кольца). Но чувствителен к шуму. - **Average** - золотая середина, когда не уверены.

Ключевые идеи

• **Agglomerative (bottom-up)** - основной метод: начинает с N кластеров, на каждом шаге объединяет два ближайших; не требует заранее задавать K
• **Divisive (top-down)** - обратный подход: начинает с одного кластера, последовательно разделяет; используется редко из-за экспоненциальной сложности оптимального разбиения
• **Дендрограмма** - главный инструмент анализа: дерево слияний, где высота = расстояние; горизонтальная линия обрезки определяет количество кластеров; большой скачок высоты указывает на естественную границу
• **Метод связи (linkage)** определяет форму кластеров: single - для сложных форм (цепочки), Ward - для компактных (как K-Means), complete/average - компромиссы
• **Иерархическая vs K-Means:** дерево родства 200 видов бабочек, о котором мы говорили в начале - это именно та задача, где иерархическая кластеризация незаменима, давая многоуровневую структуру вместо плоского разбиения; но для миллионов точек K-Means остается быстрее

Связанные темы

Иерархическая кластеризация - один из ключевых методов unsupervised learning. Дальше изучим другие подходы к кластеризации и снижению размерности:

• K-Means кластеризация — Базовый метод кластеризации, который мы уже знаем - иерархическая кластеризация решает его главную проблему (выбор K), но проигрывает в масштабируемости
• DBSCAN — Ещё один подход к кластеризации, не требующий K - находит кластеры произвольной формы через плотность точек и автоматически выявляет выбросы
• PCA (метод главных компонент) — Снижение размерности данных перед кластеризацией - полезно, когда признаков много и попарные расстояния теряют смысл (проклятие размерности)
• K-NN (K ближайших соседей) — Использует ту же идею расстояния между точками, но для классификации (supervised), а не кластеризации (unsupervised)

Вопросы для размышления

• Если agglomerative и divisive строят одну и ту же иерархию, но в разных направлениях - почему результаты могут отличаться? Подсказка: подумайте о жадности каждого решения на каждом шаге.
• Компания с 50 000 клиентами хочет многоуровневую сегментацию. Иерархическая кластеризация не масштабируется до таких объемов. Как можно скомбинировать K-Means и иерархическую кластеризацию, чтобы получить и скорость, и иерархию?
• Single linkage идеально находит два полумесяца, но "ломается" на шумных данных из-за chaining. Можно ли модифицировать подход, чтобы сохранить способность находить сложные формы, но снизить чувствительность к шуму?

Связанные уроки

• ml-16-clustering-kmeans — K-Means - базовый метод кластеризации, который это расширяет
• ml-18-dbscan — Плотностная кластеризация, другой способ обойтись без фиксированного K
• ml-19-pca — Снизить размерность перед вычислением попарных расстояний
• la-02-dot-product — Метрики расстояния строятся на скалярном произведении векторов
• ds-01 — Дендрограмма - буквально древовидная структура данных
• alg-17-mst