Hierarchical clustering 🌳

Тема этого урока называется по-английски Hierarchical clustering — дальше по тексту используется прямой русский перевод «иерархическая кластеризация», и именно этот термин будет встречаться в каждом следующем абзаце. В прошлом уроке (320) ты разобрал k-means — один из самых популярных алгоритмов кластеризации, но с неудобным требованием на входе: число кластеров $k$ нужно знать заранее, ещё до того, как алгоритм увидел данные хоть раз. На практике это требование часто неисполнимо: если ты сегментируешь базу из ста тысяч клиентов интернет-магазина, ты обычно не знаешь заранее, три там естественных сегмента, семь или двадцать три, — это как раз то, что ты хочешь узнать по итогам анализа, а не задать самому себе на входе угадыванием.

Иерархическая кластеризация решает эту проблему принципиально иначе, чем метод локтя (elbow method) из прошлого урока, который перебирает разные значения $k$ и ищет точку перегиба на графике. Вместо того чтобы один раз разбить данные на фиксированное число групп, иерархическая кластеризация строит сразу всю иерархию возможных разбиений — от состояния, где каждая точка данных является собственным отдельным кластером, до состояния, где все точки объединены в один общий кластер, — и делает это за один проход. Результат такой процедуры — не одно разбиение, а целое дерево вложенных разбиений, которое можно «разрезать» на любом желаемом уровне детализации уже после того, как всё вычислено, и получить любое число кластеров постфактум. Это и есть главное практическое преимущество иерархической кластеризации перед k-means: число кластеров не нужно угадывать заранее — оно выбирается уже глядя на готовую структуру данных.

Существует два принципиально разных направления построения такой иерархии: агломеративное (снизу вверх, от отдельных точек к одному общему кластеру) и дивизивное (сверху вниз, от одного общего кластера к отдельным точкам через последовательные разбиения). Дивизивный подход комбинаторно значительно дороже — на первом шаге нужно перебрать экспоненциально много способов разбить весь датасет на две части, — поэтому на практике почти всегда используется агломеративный подход, и именно ему посвящён этот урок целиком.

Этот урок — прямое продолжение не только урока 320 про k-means, но и урока 265 про минимальное остовное дерево (MST) из блока алгоритмов на графах. Там было дано обещание: способ измерения расстояния между кластерами, называемый методом одиночной связи (single linkage), — это в точности та же самая конструкция, что и минимальное остовное дерево, построенное алгоритмом Крускала. Сегодня это обещание будет выполнено подробно, шаг за шагом, на конкретном числовом примере — ты увидишь, что дендрограмма single linkage и минимальное остовное дерево описывают буквально одни и те же рёбра в буквально том же порядке.

История

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

Формальный алгоритмический аппарат иерархической агломеративной кластеризации оформился в середине XX века в биологии и численной таксономии. В 1958 году британский статистик Джо Уорд (Joe H. Ward Jr.) предложил метод объединения кластеров, минимизирующий прирост внутрикластерной дисперсии на каждом шаге, — сегодня он известен как метод Уорда и остаётся одним из самых популярных способов измерения расстояния между кластерами. Годом ранее, в 1957 году, зоологи Роберт Сокал и Чарльз Мичнер предложили метод невзвешенного попарного среднего (UPGMA, unweighted pair group method with arithmetic mean) — то, что в этом уроке называется методом средней связи (average linkage), — специально для построения филогенетических деревьев, показывающих эволюционное родство видов по степени сходства их признаков.

Общая математическая рамка, объединяющая все способы измерения расстояния между кластерами в единую формулу (формула Ланса — Уильямса, 1967 год), появилась чуть позже и позволила реализовывать все методы линейно эффективным единым алгоритмом вместо отдельного кода под каждый метод. Сегодня иерархическая кластеризация — стандартный инструмент в биоинформатике (построение филогенетических деревьев по схожести генетических последовательностей), в анализе рынка (сегментация клиентов с визуальным исследованием структуры на разных уровнях детализации через дендрограмму) и в разведочном анализе данных в целом — везде, где число кластеров заранее неизвестно и хочется увидеть, как объекты группируются на разных масштабах одновременно. В Python эта функциональность стандартно доступна через модуль scipy.cluster.hierarchy, где метод Уорда — параметр method='ward' — используется как настройка по умолчанию в большинстве практических задач.

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

Интуиция

Представь комнату, в которой стоят пять человек, ещё не знакомых друг с другом. На старте каждый человек — это отдельная «группа» сам по себе. Дальше происходит следующее: два человека, оказавшиеся ближе всего друг к другу (в прямом физическом смысле — стоящие рядом), объединяются в пару и с этого момента двигаются и воспринимаются как единая группа. Затем снова находится ближайшая пара — либо два оставшихся одиночки, либо одиночка и уже образовавшаяся пара, либо две пары, — и они тоже объединяются. Процесс продолжается, пока в комнате не останется одна большая группа, включающая всех пятерых. Если записать, в каком порядке и на каком расстоянии происходило каждое объединение, получится полная история того, как из пяти изолированных точек постепенно выросла одна общая структура, — именно эта история и есть иерархическая кластеризация.

Ключевое отличие от k-means: агломеративный алгоритм ни разу не спрашивает, сколько всего должно получиться групп. Он просто жадно объединяет два ближайших кластера на каждом шаге, пока не останется один кластер, включающий все объекты, — и только потом, глядя на всю получившуюся историю целиком, можно решить, на каком именно этапе «остановить плёнку» и получить нужное число групп.

Алгоритм

Агломеративная иерархическая кластеризация.

1. Инициализировать $n$ кластеров — каждая из $n$ точек данных образует свой собственный, отдельный кластер.
2. Вычислить матрицу попарных расстояний между всеми кластерами (на старте — между всеми точками).
3. Пока кластеров больше одного:
   • найти пару кластеров с минимальным расстоянием между ними;
   • объединить эту пару в один новый кластер;
   • пересчитать расстояния от нового кластера до всех остальных по выбранному правилу linkage (способу измерения расстояния между кластерами, подробно разобран в следующем разделе);
   • записать это объединение (какие кластеры слились, на каком расстоянии, то есть на какой «высоте») как один узел дендрограммы.
4. Вернуть полную последовательность из $n-1$ объединений — это и есть дендрограмма, описывающая всю иерархию разбиений от $n$ кластеров до одного.

Обрати внимание на число объединений: ровно $n-1$, если исходных точек $n$. Это тот же самый инвариант, что был в уроке 265 про остовное дерево — дерево на $n$ вершинах всегда содержит ровно $n-1$ ребро, и, как станет ясно из раздела про связь с MST, это далеко не случайное совпадение чисел.

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

Пример 1 (матрица попарных расстояний — отправная точка алгоритма). Возьмём пять точек, расположенных на числовой прямой для простоты ручного счёта (одномерное евклидово расстояние — это просто модуль разности координат; всё, что доказывается на этом примере, без изменений переносится на любое число измерений — просто формула расстояния станет чуть сложнее): $A=1$, $B=2$, $C=4$, $D=7$, $E=8$. Этот же набор точек будет использоваться сквозным примером во всех разделах урока, чтобы сравнение методов было честным — на одних и тех же данных.

Матрица попарных расстояний между пятью точками:

Уже по этой матрице видно две естественные, интуитивно ожидаемые пары кандидатов на первое объединение: $A$ и $B$ (расстояние $1$) и $D$ и $E$ (тоже расстояние $1$) — это и подтвердится в следующем примере.

Пример 2 (полная трассировка агломеративного объединения методом одиночной связи). Возьмём тот же датасет и правило linkage «одиночная связь» (single linkage): расстояние между двумя кластерами — это минимальное расстояние среди всех пар точек, где одна точка берётся из первого кластера, а другая — из второго. Подробно про смысл и формулу этого правила — в следующем разделе; здесь важна именно механика объединения шаг за шагом.

Шаг 0. Кластеры: {A} {B} {C} {D} {E}
       Минимальное расстояние в матрице: 1, есть два варианта — A-B и D-E.
       Берём первый по порядку: A-B (1) → объединяем.

Шаг 1. Кластеры: {AB} {C} {D} {E}
       Пересчёт: d({AB},C)=min(3,2)=2, d({AB},D)=min(6,5)=5, d({AB},E)=min(7,6)=6.
       Минимальное расстояние: 1, пара D-E → объединяем.

Шаг 2. Кластеры: {AB} {C} {DE}
       Пересчёт: d(C,{DE})=min(3,4)=3, d({AB},{DE})=min(5,6)=5.
       Минимальное расстояние: 2, пара {AB}-C → объединяем.

Шаг 3. Кластеры: {ABC} {DE}
       Пересчёт: d({ABC},{DE})=min(d({AB},{DE}), d(C,{DE}))=min(5,3)=3.
       Минимальное расстояние: 3, единственная оставшаяся пара → объединяем.

Шаг 4. Кластеры: {ABCDE} — все точки в одном кластере, останавливаемся.

Итого выполнено ровно $4 = 5-1$ объединения — согласуется с общим правилом «$n-1$ объединение для $n$ точек» из алгоритма выше. Запишем историю объединений в виде текстовой дендрограммы, где высота — это расстояние, на котором произошло объединение:

Высота
  3  ─────────────┬─────────────
                   │
  2  ────┬────     │
         │         │
  1  ─┬─ │    ┌─┬─  │
      │  │    │ │   │
      A  B    C │   D  E
                └───┘ (высота 1: D-E)

Если читать снизу вверх: на высоте $1$ одновременно происходят два слияния ($A$ с $B$ и $D$ с $E$), на высоте $2$ кластер $\{AB\}$ присоединяет точку $C$, на высоте $3$ два оставшихся кластера $\{ABC\}$ и $\{DE\}$ сливаются в один общий. Такая диаграмма и называется дендрограммой — деревом объединений, где по вертикали отложено расстояние (или, в случае метода Уорда, прирост дисперсии), на котором произошло каждое слияние.

Пример 3 (почему полный перебор всех возможных иерархий невозможен). Возникает естественный вопрос: а что, если жадный алгоритм на каком-то шаге ошибается и есть более удачная иерархия объединений в целом? Чтобы понять масштаб проблемы, нужно оценить, сколько вообще существует различных бинарных иерархий (деревьев объединений) для $n$ объектов. Число различных таких деревьев (с точностью до порядка объединения на одной высоте) равно $(2n-3)!! = (2n-3)(2n-5)\cdots 3 \cdot 1$ — двойному факториалу. Для $n=5$ точек это $(2\cdot5-3)!! = 7!! = 7\cdot5\cdot3\cdot1 = 105$ различных деревьев. Для $n=10$ это уже $17!! = 34\,459\,425$ — свыше $34$ миллионов вариантов, а для $n=20$ число становится астрономическим, значительно превышающим $10^{18}$. Точно так же, как формула Кэли в уроке 265 показывала, почему нельзя перебирать все остовные деревья графа напрямую, эта оценка показывает: полный перебор всех возможных иерархий кластеризации нереализуем уже на скромных по размеру датасетах, и жадный агломеративный алгоритм — не просто удобное приближение, а единственный практически реализуемый способ построить дендрограмму за разумное время.

Почему это важно

Агломеративная схема «объединяй два ближайших кластера на каждом шаге, пока не останется один» — это не единственный технический выбор среди прочих, а решение, определяющее всю дальнейшую структуру урока: раз алгоритм не фиксирует число кластеров заранее, результатом его работы естественно становится не одно разбиение, а полная история всех возможных разбиений сразу — от $n$ до $1$ кластера. Именно эта история, визуализированная в виде дендрограммы, и даёт то практическое преимущество перед k-means, ради которого стоит разбираться в иерархической кластеризации отдельно: выбор количества кластеров откладывается на самый последний момент, когда уже видна вся структура данных целиком, а не делается вслепую на входе.

Как измерить расстояние между кластерами: linkage

Интуиция

В агломеративном алгоритме на каждом шаге нужно находить пару кластеров с минимальным расстоянием между ними — но расстояние между двумя отдельными точками определено однозначно (обычная евклидова метрика или любая другая метрика расстояния), а вот расстояние между двумя группами точек — понятие неоднозначное в принципе. Если в одном кластере пять точек, а в другом — семь, то какое из $5\times7=35$ возможных попарных расстояний между их точками считать «расстоянием между кластерами»? Именно этот выбор правила и называется linkage (способ связи, способ измерения расстояния между кластерами), и разные правила дают заметно разные по форме и по составу кластеры на одних и тех же исходных данных.

Представь два города, соединённые сетью просёлочных дорог, и вопрос: «какое расстояние между городом A и городом B?» Можно ответить «расстояние между двумя ближайшими друг к другу домами на окраинах» (это и есть логика одиночной связи), можно ответить «расстояние между двумя самыми удалёнными друг от друга домами» (логика полной связи), можно посчитать «среднее расстояние между всеми парами домов одного и другого города» (логика средней связи), а можно спросить не про расстояние вовсе, а про то, «насколько вырастет неоднородность объединённого мегаполиса, если слить два города в один» (логика метода Уорда). Все четыре ответа — разумные, ни один не является «правильным» универсально, и выбор между ними — содержательное решение аналитика, а не формальность.

Алгоритм (формулы всех четырёх методов)

Метод одиночной связи (single linkage). Расстояние между кластерами $A$ и $B$ — минимум среди всех попарных расстояний между их точками:

$$d(A,B) = \min_{x\in A,\, y\in B} \|x-y\|$$

Метод полной связи (complete linkage). Расстояние между кластерами — максимум среди всех попарных расстояний:

$$d(A,B) = \max_{x\in A,\, y\in B} \|x-y\|$$

Метод средней связи (average linkage, UPGMA). Расстояние между кластерами — среднее арифметическое всех попарных расстояний:

$$d(A,B) = \frac{1}{|A|\cdot|B|}\sum_{x\in A}\sum_{y\in B}\|x-y\|$$

Метод Уорда (Ward's method). Расстояние между кластерами — это не «расстояние» в геометрическом смысле, а прирост суммарной внутрикластерной дисперсии (increase in within-cluster sum of squares, ESS), который случится, если эти два кластера объединить:

$$\Delta SS(A,B) = \frac{|A|\cdot|B|}{|A|+|B|}\,\|\bar{x}_A - \bar{x}_B\|^2$$

где $\bar{x}_A$ и $\bar{x}_B$ — центроиды (средние точки) кластеров $A$ и $B$.

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

Пример 1 (сравнительная таблица всех четырёх методов на одном датасете). Возьмём тот же сквозной пример: $A=1, B=2, C=4, D=7, E=8$. Порядок объединений оказывается одинаковым для всех четырёх методов на этом конкретном датасете (сначала $A$-$B$ и $D$-$E$, затем $\{AB\}$-$C$, затем всё вместе) — это удобно, потому что позволяет сравнить именно высоты слияний, не отвлекаясь на разный порядок. Ниже — высоты четырёх последовательных объединений для каждого метода (первое число — высота слияния $A$-$B$/$D$-$E$, второе — $\{AB\}$ с $C$, третье — финальное слияние всех в одно):

Разница особенно заметна на последнем, финальном слиянии: single linkage считает, что до полного объединения «остаётся всего $3$» (потому что ближайшая пара точек между $\{ABC\}$ и $\{DE\}$ — это $C$ и $D$ на расстоянии $3$), тогда как complete linkage настаивает на $7$ (потому что где-то в кластерах есть и самая дальняя пара — $A$ и $E$, на расстоянии $7$). Это ключевое качественное отличие всех методов друг от друга: single linkage «оптимист», ищущий любую близкую пару, а complete linkage «пессимист», требующий, чтобы близки были все пары без исключения.

Пример 2 (пересчёт расстояний по методу полной связи — единственный метод, где локальный пересчёт после первого слияния меняет итоговую высоту относительно single linkage). После объединения $A$ и $B$ в $\{AB\}$ пересчитаем расстояние до $C$ по формуле максимума: $d(\{AB\},C) = \max(d(A,C), d(B,C)) = \max(3,2) = 3$. Сравни с single linkage, где на том же шаге получалось $d(\{AB\},C)=\min(3,2)=2$. Разница в единицу уже на первом пересчёте — и она будет только расти дальше, потому что каждое следующее объединение по complete linkage опирается на максимум, который неизбежно накапливает самые «неудобные», далёкие пары точек. К финальному слиянию $\{ABC\}$ с $\{DE\}$ разница вырастает с $1$ единицы до $4$ ($7$ против $3$) — небольшая локальная асимметрия на первом шаге превращается в существенное различие всей структуры дендрограммы.

Пример 3 (метод Уорда — расчёт через прирост дисперсии, а не через расстояние). На первом шаге для пары $A=1,B=2$: $\Delta SS(A,B) = \frac{1\cdot1}{1+1}\cdot(2-1)^2 = 0{,}5\cdot1 = 0{,}5$. После объединения в $\{AB\}$ его центроид — $\bar{x}_{AB} = \frac{1+2}{2} = 1{,}5$, размер кластера $2$. Прирост дисперсии при дальнейшем объединении $\{AB\}$ с $C=4$: $\Delta SS(\{AB\},C) = \frac{2\cdot1}{2+1}\cdot(4-1{,}5)^2 = \frac{2}{3}\cdot6{,}25 \approx 4{,}17$ — именно это число и стоит во второй колонке таблицы примера 1. Обрати внимание на содержательный смысл этой цифры: она не измеряет «расстояние» в привычном понимании, а отвечает на вопрос «насколько увеличится суммарный квадрат отклонений точек от центроидов своих кластеров, если объединить именно эти два кластера прямо сейчас». Это прямая связь с k-means из урока 320: там алгоритм тоже минимизировал внутрикластерную сумму квадратов $J=\sum_i\sum_{x\in C_i}\|x-\mu_i\|^2$ — метод Уорда на каждом шаге агломерации жадно выбирает то объединение, которое минимально портит именно эту величину, то есть является, по сути, «жадной версией» той же самой целевой функции, которую k-means оптимизирует итеративно и глобально.

Пример 4 (эффект цепочки — почему single linkage и complete linkage дают разную форму кластеров на вытянутых данных). Рассмотрим датасет, где точки образуют «гантель»: плотная группа $\{(0,0),(0,1),(1,0)\}$, затем цепочка близко расположенных «мостовых» точек $(3,0),(4,0),(5,0)$, затем вторая плотная группа $\{(7,0),(7,1),(8,0)\}$. Метод одиночной связи будет объединять кластеры «по звеньям цепочки»: сначала сольются соседние мостовые точки друг с другом и с ближайшими плотными группами, и в результате всё соединится в одну длинную вытянутую структуру задолго до того, как разница между «настоящими» двумя плотными группами станет заметна на дендрограмме, — это и называется эффектом цепочки (chaining effect), характерная слабость single linkage. Метод полной связи, наоборот, «штрафует» за любую дальнюю пару внутри объединённого кластера: он будет сопротивляться слиянию мостовых точек с плотными группами до последнего, потому что такое объединение сразу создаёт пару с большим расстоянием (например, между мостовой точкой $(5,0)$ и точкой плотной группы $(0,0)$), и в результате complete linkage склонен находить компактные, примерно сферические кластеры — качественно та же склонность, что была у k-means в прошлом уроке, только выведенная не из формулы центроидов, а из формулы максимума расстояний.

Почему это важно

Выбор linkage — не техническая деталь конфигурации, а содержательное решение, определяющее саму форму кластеров, которые алгоритм способен найти: single linkage умеет находить вытянутые, произвольной формы кластеры (и именно поэтому эквивалентен MST — подробности в отдельном разделе ниже), но уязвим к эффекту цепочки и к шумовым точкам-«мостикам»; complete linkage и average linkage дают более компактные, сбалансированные по размеру кластеры, но могут разрывать действительно вытянутые естественные структуры данных; метод Уорда на практике оказывается наиболее устойчивым выбором по умолчанию именно потому, что напрямую минимизирует ту же внутрикластерную дисперсию, которую специалисты по данным привыкли контролировать ещё со времён k-means. В scipy.cluster.hierarchy метод Уорда (method='ward') действительно используется как отправная точка в подавляющем большинстве практических задач — и понимание того, что именно он оптимизирует, объясняет, почему это разумный выбор по умолчанию, а не случайное соглашение.

Дендрограмма: карта всех возможных разбиений

Интуиция

Дендрограмма — это не просто иллюстрация к алгоритму, а полноценный, самостоятельно полезный результат анализа: она в сжатом виде кодирует все возможные разбиения датасета на кластеры одновременно, от $n$ (каждая точка сама по себе) до $1$ (все точки вместе). Чтобы получить конкретное разбиение на $k$ групп, достаточно провести горизонтальную линию на нужной высоте и посмотреть, сколько вертикальных «веток» она пересекает — это число и есть число кластеров при данном пороге. Причём сделать это можно после того, как дендрограмма уже построена, — то есть выбор числа кластеров откладывается на самый последний момент и делается уже глядя на полную картину структуры данных, а не вслепую до начала анализа, как в k-means.

Алгоритм

Разрезание дендрограммы (dendrogram cut) для получения $k$ кластеров.

1. Построить полную дендрограмму — последовательность из $n-1$ объединений с указанием высоты каждого.
2. Отсортировать высоты объединений по убыванию: $h_1 \ge h_2 \ge \dots \ge h_{n-1}$.
3. Чтобы получить ровно $k$ кластеров, провести горизонтальный разрез на любой высоте строго между $h_{k-1}$ и $h_k$ (то есть отменить $k-1$ последних, самых высоких объединений).
4. Кластеры — это связные поддеревья дендрограммы ниже уровня разреза.

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

Пример 1 (разрезание дендрограммы single linkage на разных уровнях). Вернёмся к дендрограмме single linkage из первого раздела, с высотами слияний $1, 1, 2, 3$ (отсортированы по возрастанию порядка выполнения). Разрежем на высоте $0{,}5$ (ниже всех слияний): получаем $5$ отдельных кластеров — каждая точка сама по себе. Разрежем на высоте $1{,}5$ (между первым и вторым уровнем слияний): получаем $3$ кластера — $\{AB\}$, $\{C\}$, $\{DE\}$ — оба слияния высоты $1$ уже произошли, а слияние высоты $2$ ещё нет. Разрежем на высоте $2{,}5$: получаем $2$ кластера — $\{ABC\}$ и $\{DE\}$. Разрежем на высоте $3{,}5$ (выше всех слияний): получаем $1$ кластер — все точки вместе. Это ровно тот эффект, ради которого нужна вся конструкция: одна построенная дендрограмма содержит в себе разбиения на $5$, $3$, $2$ и $1$ кластер одновременно, и выбор между ними — вопрос выбора одного числа (высоты разреза), а не перезапуска всего алгоритма заново, как пришлось бы делать с k-means при смене $k$.

Пример 2 (то же самое разбиение датасета, но линейкой другого метода linkage). Возьмём дендрограмму complete linkage того же датасета с высотами слияний $1, 1, 3, 7$ (из таблицы предыдущего раздела). Чтобы получить те же $2$ кластера $\{ABC\}$ и $\{DE\}$, разрез нужно делать между высотами $3$ и $7$ — то есть где угодно, например на высоте $5$. Численное значение высоты разреза ничего не говорит само по себе о «правильном» числе кластеров в отрыве от конкретного метода linkage: у single linkage порог между $2$ и $3$ кластерами находится на высоте около $2{,}5$, у complete linkage — на высоте около $5$. Разрез дендрограммы всегда нужно выбирать содержательно, глядя на форму конкретного дерева, а не по абсолютной шкале расстояний, перенесённой из другого метода или другого датасета.

Пример 3 (эвристика «самого длинного вертикального отрезка» — практический аналог метода локтя из урока 320). На практике число кластеров по дендрограмме часто выбирают так: смотрят на последовательность высот всех слияний, отсортированную по возрастанию, и ищут самый большой «скачок» — разницу между соседними высотами. Для single linkage из примера 1 разности высот последовательных слияний: $1\to1$ (скачок $0$), $1\to2$ (скачок $1$), $2\to3$ (скачок $1$) — здесь скачки одинаковы, разрез неочевиден. Для complete linkage: $1\to1$ (скачок $0$), $1\to3$ (скачок $2$), $3\to7$ (скачок $4$) — самый большой скачок $4$ происходит на последнем слиянии, что подсказывает: разбиение на $2$ кластера ($\{ABC\}$ и $\{DE\}$) значительно естественнее для этого метода, чем на $1$ кластер, — вертикальный отрезок, соответствующий финальному слиянию, заметно длиннее остальных. Эта эвристика — прямой аналог метода локтя (elbow method) для выбора $k$ в k-means: там искали точку перегиба на графике WCSS от $k$, здесь ищут точку самого резкого «скачка» высоты слияния на дендрограмме, — оба метода решают одну и ту же по сути задачу «где данные естественнее всего распадаются на группы» разными визуальными средствами.

Почему это важно

Дендрограмма превращает выбор числа кластеров из вопроса, который приходится решать вслепую на входе (как в k-means), в вопрос, который решается на выходе, уже глядя на всю структуру целиком, — и именно это делает иерархическую кластеризацию незаменимым инструментом разведочного анализа данных (exploratory data analysis), когда цель не «получить готовое разбиение», а «понять, как вообще устроены данные» на разных уровнях детализации одновременно. В биоинформатике при построении филогенетических деревьев по схожести генетических последовательностей число «естественных» групп видов заранее неизвестно в принципе — и именно способность иерархической кластеризации выдать сразу всю иерархию, а не одно фиксированное разбиение, делает её (обычно с методом Уорда или средней связи) стандартным инструментом в этой области.

Связь с минимальным остовным деревом: обещание урока 265

Интуиция

В уроке 265 было дано прямое обещание: метод одиночной связи (single linkage) в иерархической кластеризации — это, по сути, та же самая конструкция, что и минимальное остовное дерево, построенное алгоритмом Крускала, если рассматривать точки данных как вершины полного графа, а попарные расстояния между ними — как веса рёбер. Настало время выполнить это обещание не в общих словах, а на конкретных числах — на том же самом сквозном примере, который использовался во всех предыдущих разделах.

Вспомни алгоритм Крускала из урока 265: отсортировать все рёбра графа по неубыванию веса, затем последовательно добавлять каждое ребро, если оно не создаёт цикл (то есть если его концы принадлежат ещё не связанным между собой компонентам), пока не будет построено дерево на $n-1$ ребре. А теперь сравни с описанием single linkage из этого урока: на каждом шаге объединяются два кластера, между которыми находится пара точек с минимальным расстоянием, пока не останется один кластер. Формулировки почти дословно совпадают — разница только в терминах: «ребро» в графе — это «пара точек с расстоянием» в кластеризации, «компонента графа» — это «кластер», а «не создавать цикл» означает «объединяемые точки должны быть в разных, ещё не слитых кластерах».

Алгоритм (формальное сопоставление)

Эквивалентность single linkage и MST (алгоритм Крускала). Пусть точки данных $x_1,\dots,x_n$ рассматриваются как вершины полного графа $G$, а вес ребра между $x_i$ и $x_j$ равен расстоянию $\|x_i - x_j\|$. Тогда:

1. Порядок объединений кластеров в single linkage строго совпадает с порядком добавления рёбер в алгоритме Крускала при построении MST этого графа.
2. Высота каждого слияния в дендрограмме single linkage равна весу соответствующего ребра MST.
3. Множество рёбер, использованных для всех $n-1$ слияний single linkage, в точности совпадает с множеством рёбер минимального остовного дерева графа $G$.
4. Чтобы получить $k$ кластеров single linkage, достаточно удалить $k-1$ самых тяжёлых рёбер MST — оставшийся лес из $k$ компонент и есть искомая кластеризация.

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

Пример 1 (построение MST алгоритмом Крускала на том же датасете и прямое сравнение с single linkage). Возьмём тот же граф на пяти точках $A=1,B=2,C=4,D=7,E=8$ с весами рёбер, равными расстояниям из матрицы первого раздела. Применим алгоритм Крускала: сортируем все рёбра по весу — $AB(1)$, $DE(1)$, $BC(2)$, $AC(3)$, $CD(3)$, $CE(4)$, $BD(5)$, $BE(6)$, $AD(6)$, $AE(7)$ — и последовательно добавляем, если ребро не создаёт цикл.

AB(1): A и B в разных множествах → добавляем. {A,B} {C} {D} {E}
DE(1): D и E в разных множествах → добавляем. {A,B} {C} {D,E}
BC(2): B в {A,B}, C отдельно → разные → добавляем. {A,B,C} {D,E}
AC(3): A и C УЖЕ в одном множестве {A,B,C} → цикл, пропускаем.
CD(3): C в {A,B,C}, D в {D,E} → разные → добавляем. {A,B,C,D,E}

Добавлено 4 ребра (= 5-1), все вершины соединены — останавливаемся.

Итоговое MST — рёбра $AB(1), DE(1), BC(2), CD(3)$, суммарный вес $1+1+2+3=7$. Сравни это напрямую с трассировкой single linkage из первого раздела: там кластеры объединялись в порядке $A$-$B$ (высота $1$), $D$-$E$ (высота $1$), $\{AB\}$-$C$ (высота $2$), $\{ABC\}$-$\{DE\}$ (высота $3$) — и последнее слияние происходило именно через пару точек $C$ и $D$ (поскольку $d(\{ABC\},\{DE\})=\min(\dots)=d(C,D)=3$). Это в точности те же четыре ребра — $AB$, $DE$, $BC$, $CD$ — в точности в том же порядке и на тех же высотах $1,1,2,3$, что и веса рёбер MST. Никакого приближённого сходства — это буквально один и тот же набор чисел, полученный двумя формально разными процедурами.

Пример 2 (удаление самых тяжёлых рёбер MST даёт ту же кластеризацию, что и разрез дендрограммы). Чтобы получить $k=2$ кластера через MST, нужно удалить $k-1=1$ самое тяжёлое ребро — это $CD(3)$. После удаления остаются компоненты $\{A,B,C\}$ (связанные рёбрами $AB$ и $BC$) и $\{D,E\}$ (связанные ребром $DE$) — это в точности те же два кластера, что получались при разрезании дендрограммы single linkage на высоте между $2$ и $3$ в примере 1 предыдущего раздела. Чтобы получить $k=3$ кластера, нужно удалить $2$ самых тяжёлых ребра — $CD(3)$ и $BC(2)$: остаются компоненты $\{A,B\}$, $\{C\}$, $\{D,E\}$ — опять точное совпадение с разрезом дендрограммы на высоте между $1$ и $2$. Это не просто похожий результат — это одна и та же математическая операция, увиденная с двух разных сторон: «удалить $k-1$ самых тяжёлых рёбер дерева» и «разрезать дендрограмму на подходящей высоте» буквально означают одно и то же действие над одной и той же структурой данных.

Пример 3 (практическое следствие: как эффективные библиотеки реализуют single linkage). Раз single linkage — это в точности MST, то эффективная реализация single linkage может напрямую использовать эффективный алгоритм построения MST вместо наивного пересчёта всей матрицы расстояний на каждом шаге агломерации. Матрица попарных расстояний между $n$ точками — это плотный граф (все $\binom{n}{2}$ рёбер присутствуют), а для плотных графов, как было показано в уроке 265, алгоритм Прима с массивом расстояний (без явной сортировки всех рёбер) даёт асимптотику $O(n^2)$ — заметно эффективнее, чем наивная агломеративная реализация, пересчитывающая расстояния до всех кластеров на каждом из $n-1$ шагов ($O(n^3)$ в худшем случае, подробный разбор в следующем разделе). Именно поэтому во многих реализациях (в том числе в высокопроизводительных библиотеках вроде fastcluster, с которой умеет работать scipy.cluster.hierarchy) single linkage реализован буквально как вариант алгоритма Прима поверх матрицы расстояний, а не как отдельная, независимо написанная процедура агломерации.

Почему это важно

Эта эквивалентность — не красивое теоретическое совпадение ради совпадения, а рабочий инструмент понимания на два разных уровня. Во-первых, она объясняет качественное поведение single linkage: раз это MST, то single linkage умеет находить кластеры произвольной, сколь угодно вытянутой формы (ровно так же, как MST умеет соединять вершины произвольно расположенного графа минимальной суммарной ценой, не требуя от итоговой структуры никакой «компактности» или «сферичности») — но именно поэтому single linkage подвержен эффекту цепочки, разобранному в разделе про linkage: одна цепочка близко расположенных шумовых точек-«мостиков» может соединить два содержательно разных кластера, точно так же как одно дешёвое ребро может связать две удалённые части графа в MST. Во-вторых, эта эквивалентность даёт прямой алгоритмический выигрыш: понимание single linkage как MST превращает задачу иерархической кластеризации по этому методу в уже изученную, хорошо оптимизированную графовую задачу, для которой в уроке 265 разбирались конкретные, проверенные временем эффективные алгоритмы.

Вычислительная стоимость: почему иерархическая кластеризация хуже масштабируется, чем k-means

Интуиция

У k-means из урока 320 стоимость одной итерации линейна по числу точек: каждую из $n$ точек нужно сравнить с $k$ центроидами, и таких итераций до сходимости обычно требуется немного (на практике — десятки). Агломеративная иерархическая кластеризация устроена принципиально дороже: на каждом из $n-1$ шагов алгоритма нужно найти минимальное расстояние среди всех пар оставшихся кластеров, а после каждого объединения — пересчитать расстояния от нового кластера до всех остальных. Эта разница в вычислительной стоимости — не второстепенная деталь, а прямое практическое ограничение на размер датасета, для которого иерархическую кластеризацию вообще можно себе позволить.

Формула

Вычислительная сложность агломеративной иерархической кластеризации. Наивная реализация (полный перебор всех пар кластеров на каждом шаге, без специальных структур данных) требует $O(n)$ шагов агломерации, на каждом из которых поиск минимума в матрице расстояний размера порядка $n\times n$ стоит $O(n^2)$ — итоговая сложность по времени составляет $O(n^3)$, а хранение полной матрицы попарных расстояний требует $O(n^2)$ памяти уже на старте, до единого шага агломерации. Более аккуратные реализации с приоритетной очередью или с алгоритмом ближайшего соседа в цепочке (nearest-neighbor chain algorithm) снижают время до $O(n^2 \log n)$ или даже $O(n^2)$ для отдельных методов linkage (в том числе для single linkage — ровно за счёт эквивалентности MST, разобранной выше), но требование $O(n^2)$ памяти на хранение матрицы расстояний остаётся неустранимым почти для всех вариантов метода.

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

Пример 1 (во сколько раз иерархическая кластеризация дороже k-means на растущем датасете). Для датасета из $n=1\,000$ точек наивная иерархическая кластеризация потребует порядка $n^3 = 10^9$ операций и порядка $n^2=10^6$ ячеек памяти под матрицу расстояний. Для k-means с $k=10$ кластерами и, скажем, $50$ итерациями до сходимости — порядка $n\cdot k\cdot 50 = 1\,000\cdot10\cdot50=500\,000$ операций, то есть на три порядка меньше даже без учёта оптимизаций иерархической кластеризации. При росте $n$ до $10\,000$ точек разрыв только увеличивается: у k-means стоимость растёт линейно по $n$ (до $5\,000\,000$ операций), у наивной иерархической кластеризации — кубически (до $10^{12}$ операций) — вычислительно неподъёмно уже на этом масштабе без специальных оптимизаций.

Пример 2 (память как более жёсткое ограничение, чем время). Даже с наилучшими известными оптимизациями по времени (например, $O(n^2)$ для single linkage через MST) требование $O(n^2)$ памяти на матрицу попарных расстояний никуда не девается. Для $n=100\,000$ точек матрица расстояний размера $n\times n$ занимает порядка $10^{10}$ ячеек — при хранении в виде чисел с плавающей запятой двойной точности (8 байт на число) это порядка $80$ гигабайт оперативной памяти только под саму матрицу расстояний, без учёта дополнительных структур алгоритма. Для сравнения, k-means на том же датасете хранит только $n\times d$ координат точек и $k\times d$ координат центроидов — на много порядков меньше. Именно поэтому на практике иерархическую кластеризацию применяют к датасетам от десятков до нескольких тысяч точек (реже — до нескольких десятков тысяч со специализированными реализациями), а не к миллионам записей, для которых k-means или его масштабируемые варианты остаются практически единственным разумным выбором.

Пример 3 (практическое следствие для рабочего процесса аналитика). Когда датасет заведомо большой (сотни тысяч и более объектов), распространённая практика — не отказываться от иерархической кластеризации целиком, а применить её к предварительно уменьшенному представлению данных: например, сначала запустить k-means с относительно большим $k$ (скажем, несколько сотен «микрокластеров»), а затем применить иерархическую кластеризацию уже к центроидам этих микрокластеров, а не к исходным точкам напрямую. Такой гибридный подход (иногда называемый двухэтапной кластеризацией) объединяет масштабируемость k-means на первом этапе с богатой, детализированной структурой дендрограммы на втором — там, где число объектов уже сведено к вычислительно приемлемому размеру.

Почему это важно

Вычислительная стоимость — это не абстрактная характеристика алгоритма, а прямой критерий выбора между k-means и иерархической кластеризацией на практике: если данных много (от сотен тысяч объектов и выше) и есть разумное предположение о числе кластеров, k-means почти всегда предпочтительнее по чисто вычислительным причинам; если данных умеренно много (до нескольких тысяч, в отдельных случаях — десятков тысяч объектов) и число кластеров заранее неизвестно, а визуальное исследование структуры данных на разных уровнях детализации ценно само по себе, иерархическая кластеризация — оправданный и часто более информативный выбор, несмотря на более высокую вычислительную цену.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Даны четыре точки на числовой прямой: $P=2$, $Q=5$, $R=6$, $S=11$. Построй матрицу попарных расстояний между всеми четырьмя точками.

Задание 2. Используя матрицу из задания 1, определи, какая пара точек объединится первой при агломеративной кластеризации (любым методом linkage — на первом шаге все методы дают одинаковый результат, так как исходные кластеры состоят из одной точки).

Задание 3. После объединения $Q$ и $R$ в кластер $\{QR\}$ (используя данные из заданий 1–2) вычисли расстояние от $\{QR\}$ до $P$ и до $S$ по правилу single linkage.

Задание 4. Повтори вычисление из задания 3, но по правилу complete linkage.

Задание 5. Своими словами объясни, почему у обычного расстояния между двумя точками нет неоднозначности, а у расстояния между двумя кластерами (группами точек) неоднозначность есть.

Задание 6. Дендрограмма построена для $6$ объектов. Сколько всего объединений (слияний) она содержит?

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

Задание 8. Дана дендрограмма с высотами слияний (по порядку выполнения) $2, 2, 5, 9$ для $5$ объектов. Сколько кластеров получится при разрезе на высоте $6$?

Задание 9. Почему нельзя напрямую использовать «обычное евклидово расстояние» для двух кластеров, минуя выбор linkage?

Задание 10. Дана частично готовая дендрограмма с высотами слияний $1,1,1,4,4,10$ для $7$ объектов. Сколько кластеров получится при разрезе на высоте $2$? А на высоте $5$? А на высоте $12$?

Средние (задания 11–20)

Задание 11. Дан датасет из четырёх точек на плоскости: $A=(0,0)$, $B=(1,0)$, $C=(5,0)$, $D=(6,0)$. Выполни полную трассировку агломеративной кластеризации методом single linkage — найди все объединения и высоты, на которых они происходят.

Задание 12. Для того же датасета, что в задании 11, выполни трассировку методом complete linkage и сравни результат.

Задание 13. Для того же датасета из задания 11 выполни трассировку методом Уорда — вычисли прирост дисперсии $\Delta SS$ на каждом шаге.

Задание 14. Объясни на словах эффект цепочки (chaining effect) у single linkage и приведи признак, по которому его можно заподозрить на реальной дендрограмме.

Задание 15. Дан кластер $\{X, Y\}$ с центроидом $\bar{x}=3$ (два объекта) и точка $Z=9$. Вычисли прирост дисперсии $\Delta SS$ при объединении $\{X,Y\}$ с $Z$ по методу Уорда.

Задание 16. Дендрограмма для $8$ объектов имеет отсортированные по возрастанию высоты слияний $1, 1{,}2, 1{,}3, 1{,}5, 1{,}6, 8{,}0, 8{,}5$. По эвристике «самого длинного скачка» определи наиболее вероятное разумное число кластеров.

Задание 17. Дан граф на четырёх точках с рёбрами (весами-расстояниями) $WX=2$, $WY=7$, $WZ=8$, $XY=5$, $XZ=6$, $YZ=1$. Построй MST алгоритмом Крускала и сопоставь его с трассировкой single linkage на тех же точках.

Задание 18. Оцени число операций для наивной иерархической кластеризации ($O(n^3)$) и для k-means с $k=8$ и $40$ итерациями ($O(n\cdot k\cdot \text{итерации})$) на датасете из $n=2\,000$ точек. Во сколько раз иерархическая кластеризация дороже?

Задание 19. Допиши код на Python, который строит иерархическую кластеризацию методом Уорда с помощью scipy.cluster.hierarchy и получает ровно $3$ кластера из готовой дендрограммы.

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

X = np.array([[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]])

# 1. построй дендрограмму методом Уорда
Z = ___

# 2. получи ровно 3 кластера, разрезав дендрограмму
labels = fcluster(Z, t=___, criterion='maxclust')

Z = linkage(X, method='ward')
labels = fcluster(Z, t=3, criterion='maxclust')

Задание 20. В биоинформатике даны попарные расстояния (число различающихся позиций в выровненных последовательностях) между четырьмя видами: $d(1,2)=2$, $d(1,3)=8$, $d(1,4)=9$, $d(2,3)=7$, $d(2,4)=8$, $d(3,4)=3$. Построй филогенетическое дерево методом average linkage (UPGMA).

Продвинутые (задания 21–30)

Задание 21. Объясни, почему высота финального (последнего) слияния в дендрограмме single linkage равна весу самого тяжёлого ребра минимального остовного дерева, построенного на тех же точках.

Задание 22. Формула Ланса — Уильямса унифицированно пересчитывает расстояние от нового кластера $\{i\cup j\}$ до кластера $k$ по формуле $d(\{i\cup j\},k) = \alpha_i d(i,k) + \alpha_j d(j,k) + \beta\, d(i,j) + \gamma\,|d(i,k)-d(j,k)|$. Для single linkage коэффициенты — $\alpha_i=\alpha_j=0{,}5$, $\beta=0$, $\gamma=-0{,}5$. Проверь, что эта формула даёт то же самое, что прямое правило минимума, на числах $d(i,k)=3$, $d(j,k)=7$.

Задание 23. Объясни, почему метод Уорда можно рассматривать как «жадную», пошаговую версию той же целевой функции WCSS, которую k-means (урок 320) минимизирует глобально и итеративно.

Задание 24. Датасет содержит $n=50\,000$ точек. Оцени, сколько гигабайт памяти потребуется на хранение полной матрицы попарных расстояний в виде чисел двойной точности (8 байт на число), и сделай вывод о применимости иерархической кластеризации напрямую к такому датасету.

Задание 25. Опиши идею алгоритма ближайшего соседа в цепочке (nearest-neighbor chain algorithm), который позволяет построить дендрограмму для многих методов linkage (включая метод Уорда) за $O(n^2)$ времени вместо наивных $O(n^3)$.

Задание 26. Дан датасет из шести точек на прямой: $A=0$, $B=1$, $C=2$, $D=10$, $E=11$, $F=12$. Выполни трассировку average linkage до момента объединения всех точек в два кластера (то есть до предпоследнего шага).

Задание 27. В датасете есть одна точка-выброс, находящаяся далеко от двух плотных групп, но не образующая с ними никакой цепочки промежуточных точек. Опиши, как эта точка-выброс будет вести себя в дендрограмме single linkage и в дендрограмме complete linkage.

Задание 28. Кофенетический коэффициент корреляции (cophenetic correlation coefficient) измеряет, насколько хорошо высоты дендрограммы (кофенетические расстояния — высота, на которой два объекта впервые оказываются в одном кластере) согласуются с исходными попарными расстояниями между объектами. Объясни, зачем нужна эта метрика и как её можно использовать для выбора метода linkage.

Задание 29. Свяжи воедино три метода кластеризации курса — k-means (урок 320), минимальное остовное дерево (урок 265) и иерархическую кластеризацию (этот урок) — одним связным абзацем, объяснив, что их объединяет и чем они принципиально отличаются друг от друга.

Задание 30. Спроектируй (опиши шагами, без кода) пайплайн сегментации клиентов интернет-магазина по покупательскому поведению, используя иерархическую кластеризацию, если заранее неизвестно, на сколько сегментов естественно делится аудитория.

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

❌ Ошибка: «Иерархическая кластеризация не требует вообще никаких решений от аналитика — просто запускаем и смотрим результат»

✅ Правильно: нужно осознанно выбрать метод linkage (single, complete, average или Уорда) — от этого выбора зависит форма и состав получаемых кластеров

💡 Почему: разные методы linkage дают качественно разные кластеры на одних и тех же данных, как показано в разделе про эффект цепочки — выбор linkage не менее содержателен, чем выбор $k$ в k-means

❌ Ошибка: использовать single linkage по умолчанию, не проверив данные на наличие шумовых точек-мостиков между содержательно разными группами

✅ Правильно: проверять устойчивость результата single linkage к небольшим изменениям данных, либо изначально выбирать более устойчивый к шуму метод (complete linkage, average linkage или метод Уорда)

💡 Почему: эффект цепочки может «склеить» два разных кластера через одну случайную промежуточную точку, что часто не соответствует содержательной структуре данных

❌ Ошибка: запускать наивную иерархическую кластеризацию на датасете из миллионов записей без предварительной оценки вычислительных затрат

✅ Правильно: оценивать требуемую память ($O(n^2)$) и время ($O(n^2)$–$O(n^3)$ в зависимости от реализации) заранее и при необходимости применять предварительное сжатие данных

💡 Почему: матрица попарных расстояний на $100\,000$ точек уже требует порядка $80$ гигабайт памяти — без предварительной оценки легко упереться в нехватку ресурсов посреди вычисления

❌ Ошибка: забывать масштабировать признаки перед вычислением попарных расстояний

✅ Правильно: всегда приводить признаки к одному масштабу (например, StandardScaler) перед построением матрицы расстояний

💡 Почему: признак с большим числовым разбросом (например, годовой доход в рублях) будет доминировать над признаком с маленьким разбросом (например, возраст) при вычислении евклидова расстояния — ровно та же проблема, что уже разбиралась для k-means в уроке 320

❌ Ошибка: считать высоту разреза дендрограммы «универсальным порогом», переносимым между разными методами linkage или разными датасетами

✅ Правильно: выбирать высоту разреза содержательно для конкретной дендрограммы, ориентируясь на видимые скачки высоты именно на этом графике

💡 Почему: как показано в разделе про дендрограммы, одно и то же разбиение на кластеры у single linkage и complete linkage происходит на совершенно разных абсолютных высотах ($2{,}5$ против $5$ в сквозном примере урока) — абсолютное число без контекста метода и датасета ничего не значит

❌ Ошибка: путать иерархическую кластеризацию методом Уорда с k-means, считая их взаимозаменяемыми и выбирающими один и тот же результат

✅ Правильно: помнить, что метод Уорда — жадный и необратимый (однажды объединённые кластеры больше никогда не разъединяются), тогда как k-means может на каждой итерации свободно переприсваивать точки любому кластеру

💡 Почему: из-за необратимости жадных решений метод Уорда не гарантирует глобально оптимальное разбиение на $k$ кластеров даже при оптимальном выборе высоты разреза — в отличие от общей идеи k-means, который явно ищет (хоть и локальный) оптимум фиксированной целевой функции на каждой итерации

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

✅ Иерархическая кластеризация не требует заранее заданного числа кластеров $k$ — это её ключевое практическое преимущество перед k-means из урока 320

✅ Агломеративный подход строит иерархию снизу вверх: начинает с $n$ отдельных кластеров и объединяет два ближайших на каждом шаге, пока не останется один — всего $n-1$ объединение

✅ Способ измерения расстояния между кластерами (linkage) — содержательный выбор: single linkage берёт минимум попарных расстояний, complete linkage — максимум, average linkage — среднее, метод Уорда — минимальный прирост внутрикластерной дисперсии $\Delta SS$

✅ Метод Уорда — жадная, пошаговая версия той же целевой функции WCSS, которую k-means минимизирует глобально и итеративно, и потому наиболее устойчивый выбор по умолчанию на практике

✅ Дендрограмма кодирует сразу все возможные разбиения от $n$ до $1$ кластера одновременно — число кластеров выбирается разрезанием дендрограммы уже после того, как всё вычислено

✅ Метод одиночной связи (single linkage) математически эквивалентен минимальному остовному дереву (MST) из урока 265: порядок и высоты объединений single linkage в точности совпадают с порядком и весами рёбер MST, построенного алгоритмом Крускала

✅ Эта эквивалентность объясняет и сильную сторону single linkage (умение находить кластеры произвольной формы), и его слабость (эффект цепочки через шумовые точки-мостики)

✅ Наивная реализация агломеративной кластеризации стоит $O(n^3)$ по времени и $O(n^2)$ по памяти — заметно дороже, чем линейный по $n$ k-means, поэтому иерархическую кластеризацию напрямую применяют к датасетам умеренного размера, а не к миллионам записей

✅ Эффективные реализации (в том числе scipy.cluster.hierarchy с библиотекой fastcluster) используют формулу Ланса — Уильямса и алгоритм ближайшего соседа в цепочке, снижая время до $O(n^2)$ для большинства методов linkage

✅ Стандартный практический рецепт — метод Уорда через scipy.cluster.hierarchy.linkage(X, method='ward') с последующим визуальным и количественным (кофенетическая корреляция, самый длинный скачок высоты) выбором числа кластеров

Связь с темами курса

Назад, к уроку 320 (k-means): оба метода решают задачу кластеризации, но противоположным образом устроены во времени принятия решений — k-means фиксирует $k$ на входе и ищет глобально согласованное разбиение итеративно, иерархическая кластеризация не фиксирует $k$ вовсе и строит сразу всю иерархию, откладывая выбор числа кластеров на самый конец. Метод Уорда внутри иерархической кластеризации напрямую наследует ту же целевую функцию (внутрикластерную сумму квадратов), которую оптимизирует k-means, — только оптимизирует её жадно и необратимо, а не итеративным глобальным уточнением.

Назад, к уроку 265 (минимальное остовное дерево): это самая прямая и подробная связь всего урока. В уроке 265 было анонсировано, что метод одиночной связи в иерархической кластеризации — это, по сути, та же самая конструкция, что и MST, построенное алгоритмом Крускала. Этот урок выполнил обещание детально: на сквозном числовом примере показано, что порядок объединений, высоты слияний и итоговое множество рёбер single linkage совпадают с MST буквально один в один (пример 1 раздела «Связь с минимальным остовным деревом»), а удаление $k-1$ самых тяжёлых рёбер MST даёт ту же кластеризацию, что и разрезание дендрограммы на соответствующей высоте (пример 2 того же раздела). Понимание алгоритмов Прима и Крускала из урока 265 напрямую объясняет, почему эффективные реализации single linkage используют именно графовые алгоритмы построения MST, а не наивный пересчёт всей матрицы расстояний.

Вперёд, к уроку 322 (DBSCAN): иерархическая кластеризация уже частично решила проблему k-means «нужно знать $k$ заранее», но заплатила за это заметно возросшей вычислительной ценой ($O(n^2)$–$O(n^3)$ вместо линейной по $n$ у k-means) и всё ещё требует ручного, хоть и постфактум, выбора уровня разреза дендрограммы. Следующий урок про DBSCAN покажет ещё один, принципиально иной подход к той же проблеме — кластеризацию по плотности, которая не только не требует $k$ заранее, но и умеет автоматически выделять шумовые точки-выбросы, не относя их ни к одному кластеру насильно, — то, чего ни k-means, ни иерархическая кластеризация делать не умеют в чистом виде.

Связано также с: урок про метод локтя из курса про k-means (эвристика выбора $k$ через график WCSS — прямой аналог эвристики «самого длинного скачка высоты» на дендрограмме), урок про PCA (снижение размерности данных перед вычислением попарных расстояний — особенно полезно, когда признаков много и «проклятие размерности» делает евклидово расстояние менее информативным), и урок про сложность алгоритмов ($O$-нотация) — без которого сравнение $O(n^3)$ иерархической кластеризации с $O(n)$ k-means было бы лишь качественным утверждением, а не количественно обоснованным выводом.

Интересные факты

Метод Уорда, разработанный в 1958 году, изначально создавался не для анализа клиентов или биологии, а для задач военной психологии — Джо Уорд работал над классификацией профилей личности военнослужащих ВВС США, и ему требовался метод, который группировал бы похожие профили с минимальными потерями информации об их внутренней однородности.

Слово «дендрограмма» происходит от греческого dendron — «дерево»; та же самая греческая основа встречается в слове «дендрит» — древовидном отростке нервной клетки, и в слове «дендрохронология» — методе датировки по годичным кольцам деревьев, что отражает общую идею ветвящейся, иерархической структуры, лежащую в основе всех этих понятий.

В биоинформатике иерархическая кластеризация используется не только для филогенетических деревьев по целым организмам, но и для группировки генов по схожести паттернов активности (экспрессии) в разных условиях эксперимента — знаменитые «тепловые карты» (heatmaps) с дендрограммами по обеим осям, которые часто встречаются в статьях по молекулярной биологии, — это именно результат иерархической кластеризации, применённой одновременно к строкам (генам) и столбцам (образцам) таблицы данных.

Формула Ланса — Уильямса, унифицирующая пересчёт расстояний для всех методов linkage в единую схему, была опубликована в 1967 году — почти за десять лет до того, как вычислительные мощности стали позволять массово применять иерархическую кластеризацию к сколько-нибудь крупным реальным датасетам; теоретический аппарат в этой области, как это часто случается в информатике, заметно опередил практическую вычислительную возможность его широко использовать.

Лайфхаки

Начинай с метода Уорда как разумного значения по умолчанию (method='ward' в scipy.cluster.hierarchy.linkage), а не перебирай все четыре метода linkage вслепую — он напрямую минимизирует ту же внутрикластерную дисперсию, интуицию про которую ты уже наработал на k-means, и на практике даёт устойчивые, легко интерпретируемые результаты в большинстве задач.

Перед запуском на реальных данных прикинь ожидаемую память под матрицу расстояний по формуле $8n^2$ байт (для чисел двойной точности) — если результат превышает разумную долю доступной оперативной памяти, сразу планируй предварительное сжатие данных, а не запускай алгоритм «на удачу» и не жди аварийного завершения по нехватке памяти.

Не выбирай высоту разреза дендрограммы по одному-единственному числу — сначала визуализируй дендрограмму целиком и найди самый выраженный, визуально очевидный скачок высоты; только потом переводи этот визуальный выбор в конкретное число кластеров для fcluster.

Если подозреваешь эффект цепочки (данные содержат разреженные, но связанные цепочкой точки-мостики), запусти сразу два метода linkage — single и complete (или Уорда) — на одних данных и сравни получившиеся дендрограммы; сильное расхождение в структуре — явный сигнал, что single linkage сливает содержательно разные группы через шумовые промежуточные точки.

Для больших датасетов не пытайся героически ускорить наивную реализацию вручную — используй готовые оптимизированные библиотеки (fastcluster, поддерживаемую scipy.cluster.hierarchy), которые уже реализуют алгоритм ближайшего соседа в цепочке и формулу Ланса — Уильямса; ручная попытка переписать $O(n^3)$ алгоритм с нуля почти никогда не окупается по сравнению с использованием уже готового, тщательно оптимизированного инструмента.

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

Иерархическая кластеризация закрывает главный недостаток k-means — необходимость знать число кластеров заранее, — но платит за это возросшей вычислительной ценой и требует осознанного выбора linkage. Это не «более правильный» алгоритм, а другой инструмент с другими компромиссами, и умение выбрать между ними осознанно — уже само по себе признак зрелого понимания задачи кластеризации, а не просто знания синтаксиса очередной библиотечной функции.