Иерархическая кластеризация: как читать дендрограмму

Иерархическая кластеризация - это способ группировки объектов, при котором результат представляют не фиксированным набором кластеров, а деревом слияний: дендрограммой. В отличие от k-means, где число кластеров нужно знать заранее, здесь алгоритм сам последовательно объединяет ближайшие объекты и кластеры, а число итоговых групп читатель выбирает уже после построения дерева - просто отсекая его на нужной высоте. Ниже разберём, как агломеративный алгоритм строит дендрограмму шаг за шагом, чем отличаются методы связывания single, complete и average, и как по порогу отсечения находить нужное число кластеров. Чтобы сразу увидеть, как это работает на конкретных числах, покрути калькулятор ниже: он строит дендрограмму для шести объектов и мгновенно пересчитывает кластеры при выбранном пороге.

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

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

Как строится дендрограмма шаг за шагом

Алгоритм работает по простой схеме: на каждой итерации ищем пару кластеров с минимальным межкластерным расстоянием, объединяем их в новый кластер, и повторяем, пока не останется один кластер. Для $n$ объектов потребуется ровно $n - 1$ слияний.

Рассчитать для своей задачи

Возьмём шесть объектов с одним числовым признаком: $A=2$, $B=3$, $C=9$, $D=12$, $E=20$, $F=21$. Расстояние между объектами - модуль разности координат, $d(i, j) = |x_i - x_j|$. Тогда $d(A, B) = 1$ и $d(E, F) = 1$ - это минимальные расстояния, и первым делом объединяются либо A с B, либо E с F (при равенстве берём пару с меньшими индексами, то есть A и B). Дальше среди оставшихся кластеров снова ищем минимум, объединяем E и F, затем C и D, и так далее, пока не получится один общий кластер на вершине дерева.

Методы связывания: single, complete, average

Когда объединяются не отдельные объекты, а уже составленные кластеры, нужно правило, как считать расстояние между двумя кластерами. Это и есть метод связывания:

$d_{single}(A, B) = \min_{i \in A,\, j \in B} d(i, j),$

$d_{complete}(A, B) = \max_{i \in A,\, j \in B} d(i, j),$

$d_{average}(A, B) = \frac{1}{|A|\,|B|} \sum_{i \in A} \sum_{j \in B} d(i, j).$

Single linkage берёт расстояние между самыми близкими представителями двух кластеров - из-за этого кластеры легко «цепляются» друг за друга через цепочку близких точек (эффект chaining). Complete linkage, наоборот, ориентируется на самых далёких представителей, поэтому получает более компактные и раздельные кластеры. Average linkage - компромисс: среднее по всем парам расстояний между объектами двух кластеров.

Рассчитать для своей задачи

Для нашего примера первые три слияния (A-B, E-F, C-D) дают одинаковую высоту $1, 1, 3$ при любом методе связывания - это естественно, ведь на первых шагах объединяются ещё одиночные объекты. Разница проявляется дальше: при объединении кластера $\{A, B\}$ с кластером $\{C, D\}$ single linkage даёт высоту 6, average linkage - 8, а complete linkage - 10. На последнем, финальном слиянии разброс ещё заметнее: 8 против 14 и 19 соответственно. Чем «жёстче» метод (complete строже single), тем выше и растянутее получается верхняя часть дендрограммы.

Как выбрать порог отсечения и найти число кластеров

Главное практическое умение - читать готовую дендрограмму. Проведите горизонтальную линию на высоте $h$ (порог отсечения) и посчитайте, сколько вертикальных ветвей она пересекает - это и есть число кластеров при данном пороге. Формально: кластеры - это компоненты связности дерева после удаления всех слияний с высотой больше $h$.

Рассчитать для своей задачи

Для дендрограммы single linkage из нашего примера (высоты слияний $1, 1, 3, 6, 8$) при пороге $h = 5$ линия проходит выше первых трёх слияний, но ниже двух последних - получаем три кластера: $\{A, B\}$, $\{C, D\}$, $\{E, F\}$. При пороге $h = 7$ пятое слияние (высота 8) ещё не пройдено, а четвёртое (высота 6) уже позади - линия пересекает две ветви, и single linkage объединяет левую половину в один кластер $\{A, B, C, D\}$, оставляя $\{E, F\}$ отдельно. При том же пороге $h = 7$ методы average и complete (у которых четвёртое слияние происходит на высоте 8 и 10) ещё не дошли до этого объединения, поэтому дают три кластера. Именно так на практике проявляется разница методов связывания: не в порядке слияний, а в том, при каком пороге кластеры «схлопываются» в более крупные группы.

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

Кофенетическое расстояние и когда метод даёт надёжный результат

Кофенетическое расстояние между двумя объектами - это высота того слияния, на котором они впервые оказались в одном кластере. Оно используется для проверки качества дендрограммы: чем ближе кофенетические расстояния к исходным попарным расстояниям объектов (коэффициент кофенетической корреляции), тем точнее дерево отражает структуру данных. Average linkage обычно даёт более высокую кофенетическую корреляцию, чем single или complete, поэтому его чаще используют, когда важна не столько компактность кластеров, сколько верность самому дереву. Отдельная тонкость: у некоторых методов связывания (например, у центроидного) высоты слияний не обязаны монотонно расти вверх по дереву - это называют инверсией и считается признаком некорректной дендрограммы. У single, complete и average linkage такой проблемы нет: высоты слияний всегда неубывающие.

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

• Путаница между single и complete linkage. Single берёт минимум расстояний между объектами кластеров, complete - максимум. Перепутав их местами, получите обратную по смыслу картину: слишком «цепкие» либо слишком «жёсткие» кластеры.
• Забыть, что порог отсечения - это высота, а не число объектов. Число кластеров определяется числом ветвей, которые пересекает горизонтальная линия на выбранной высоте, а не произвольно выбранным количеством.
• Сравнение дендрограмм разных методов связывания по одной и той же высоте. Масштаб высот у single, complete и average разный (в нашем примере финальная высота 8, 19 и 14 соответственно), поэтому одно и то же значение порога даёт разное число кластеров у разных методов.
• Игнорирование единиц измерения признаков. Если признаки объектов измерены в разных шкалах (например, метры и годы), расстояние $d(i, j)$ без нормировки будет доминировано признаком с большим разбросом значений.
• Ожидание единственно верного числа кластеров. Дендрограмма не отвечает на этот вопрос сама - порог отсечения выбирает исследователь, опираясь на задачу и на размер «разрывов» между высотами соседних слияний.

FAQ

Чем иерархическая кластеризация отличается от k-means? K-means требует заранее задать число кластеров $k$ и разбивает объекты на плоские, непересекающиеся группы за один проход. Иерархическая кластеризация строит дерево слияний, а число кластеров выбирается после построения - отсечением дендрограммы на нужной высоте.

Какой метод связывания выбрать: single, complete или average? Single linkage подходит, если ожидаются вытянутые, «цепочечные» кластеры, но чувствителен к выбросам. Complete linkage даёт компактные, хорошо разделённые кластеры. Average linkage - универсальный компромисс и чаще всего хороший выбор по умолчанию.

Как по дендрограмме понять, сколько кластеров в данных? Найдите на дендрограмме самый длинный вертикальный промежуток между высотами двух соседних слияний и проведите линию отсечения примерно посередине этого промежутка - число пересечённых ветвей и будет числом кластеров.

Коротко

Иерархическая кластеризация строит дендрограмму: дерево слияний, где на каждом шаге объединяются два самых близких по выбранному методу связывания кластера, а высота узла - расстояние, на котором произошло объединение. Методы single (минимум расстояний), complete (максимум) и average (среднее) для одного набора объектов обычно дают одинаковый порядок слияний, но разные высоты - поэтому и разное число кластеров при одном и том же пороге отсечения. Чтобы получить финальное разбиение, достаточно провести горизонтальную линию на выбранной высоте и посчитать пересечённые ветви.