Иерархическая кластеризация — это метод машинного обучения без учителя, который объединяет похожие объекты в вложенные группы и показывает их отношения в виде дерева. Такой подход помогает увидеть структуру данных, не задавая классы заранее.
Метод применяют, когда нужно понять, какие объекты близки друг к другу, где проходят естественные границы между группами и сколько таких групп вообще может быть. Результат обычно визуализируют дендрограммой — схемой, где видно, как кластеры объединялись или делились.
Содержание статьи
Как работает иерархическая кластеризация
Иерархическая кластеризация строится на оценке расстояния между объектами или группами объектов. Алгоритм шаг за шагом либо объединяет близкие кластеры, либо делит общий кластер на более мелкие.
В основе лежит матрица несходства. В ней хранится, насколько один объект отличается от другого по выбранной метрике расстояния. Это может быть евклидово расстояние, расстояние Манхэттена, Хэмминга, Махаланобиса и другие варианты — выбор зависит от типа данных.
Дальше алгоритм использует правило связи, или linkage criterion. Именно оно определяет, как считать расстояние уже не между двумя точками, а между двумя кластерами. От этого выбора сильно зависит итоговая форма групп.
Какие бывают виды иерархической кластеризации
Существует два основных подхода: агломеративный и дивизимный. Первый идет снизу вверх, второй — сверху вниз.
При агломеративной кластеризации каждый объект сначала считается отдельным кластером. Затем алгоритм последовательно объединяет самые близкие группы, пока не останется один крупный кластер или не сработает условие остановки.
При дивизимной кластеризации всё начинается с одного общего кластера, который затем поэтапно разбивается на более мелкие части. Деление продолжается до тех пор, пока не будет достигнуто нужное число кластеров или пока каждый объект не окажется в своей собственной группе.
Оба подхода жадные. Это значит, что на каждом шаге алгоритм принимает локально лучшее решение: что объединить сейчас или что разделить сейчас. Уже сделанный шаг потом не пересматривается.
Что такое агломеративная кластеризация
Агломеративная кластеризация — самый распространенный вариант иерархического метода, при котором данные постепенно собираются в более крупные группы. Каждый объект стартует отдельно.
Этот подход часто обозначают как bottom-up. Он удобен тем, что хорошо показывает, какие элементы были ближе всего на ранних шагах, а какие группы сформировались только на поздних этапах.
Как проходят шаги агломеративного алгоритма
Алгоритм работает последовательно: считает расстояния, объединяет ближайшие кластеры, обновляет матрицу расстояний и повторяет процесс.
- Выбирается метрика расстояния между объектами.
- Каждый объект объявляется отдельным кластером.
- Находятся два самых близких кластера.
- Эти кластеры объединяются.
- Расстояния пересчитываются с учетом нового кластера.
- Процесс повторяется до выполнения условия остановки.
Условием остановки может быть один общий кластер или заранее заданное число групп. Это удобно, если аналитик уже знает, сколько сегментов ему нужно рассмотреть.
Что такое дивизимная кластеризация
Дивизимная кластеризация начинает работу с одного общего кластера и последовательно делит его на части. Это подход сверху вниз.
Такой метод встречается реже, потому что он обычно тяжелее по вычислениям. Зато он может лучше учитывать общую структуру набора данных уже с первого шага, так как стартует со всей выборки сразу.
Как проходят шаги дивизимного алгоритма
На каждом этапе выбирается кластер, который нужно разделить, а затем внутри него выполняется разбиение. После этого процесс повторяется для следующих групп.
- Все объекты помещаются в один кластер.
- Выбирается кластер, который нужно разделить.
- Кластер делится на две или более частей с помощью метода плоской кластеризации.
- Алгоритм повторяет деление для следующих групп.
- Процесс останавливается при достижении нужной детализации.
Для такого разбиения нередко используют дополнительные методы, например k-средних. В этом случае иерархическая схема сочетается с более простым способом деления внутри текущего кластера.
Какие методы связи используются чаще всего
Метод связи определяет, как считать расстояние между кластерами. Один и тот же набор данных при разных правилах связи может дать разную структуру групп.
Выбор зависит от формы кластеров, плотности данных, наличия выбросов и шума. Ниже — основные варианты, которые применяют чаще других.
Метод ближайшего соседа
Метод ближайшего соседа, или single linkage, берет минимальное расстояние между двумя точками из разных кластеров. Если хотя бы одна пара точек близка, кластеры считаются близкими.
Он подходит для вытянутых и неэллиптических форм. Но есть слабое место: эффект цепочки. Несколько промежуточных точек могут связать две группы в одну, хотя визуально они выглядят раздельными.
Метод дальнего соседа
Метод дальнего соседа, или complete linkage, использует максимальное расстояние между точками из двух кластеров. Кластеры считаются близкими только тогда, когда даже самые удаленные точки не слишком далеки друг от друга.
Такой подход меньше реагирует на отдельные шумовые точки, чем single linkage. При этом он часто формирует более компактные, почти сферические группы.
Средняя связь
Средняя связь считает расстояние между кластерами как среднее значение расстояний между всеми парами точек из двух групп. Это компромисс между ближайшим и дальним соседом.
На практике используют несколько вариантов, включая UPGMA и WPGMA. Разница между ними связана с тем, как именно учитываются расстояния при объединении кластеров.
Связь по центроидам
В этом случае расстояние измеряется между центрами кластеров, то есть между их центроидами. Метод опирается на усредненное положение точек внутри каждой группы.
Подход удобен для данных, где центр группы действительно хорошо описывает её положение. Если форма кластера сложная, такой способ может скрыть важные детали.
Метод Уорда
Метод Уорда объединяет те кластеры, при слиянии которых суммарный внутрикластерный разброс растет меньше всего. На практике он часто дает аккуратные и хорошо отделенные группы.
Его обычно выбирают для количественных признаков. Он менее чувствителен к шуму, чем некоторые другие правила связи, и часто используется в прикладном анализе.
Что показывает дендрограмма
Дендрограмма — это древовидная схема, которая показывает порядок объединения или деления кластеров и расстояния между ними. По ней можно понять, как устроена иерархия групп в данных.
По горизонтали обычно расположены объекты или уже сформированные кластеры. По вертикали — уровень расстояния, на котором произошло объединение. Чем выше соединяются ветви, тем менее похожими были соответствующие группы.
Дендрограмма полезна тем, что не навязывает одно фиксированное число кластеров. Аналитик может мысленно провести горизонтальную линию на нужной высоте и посмотреть, сколько отдельных ветвей она пересекает. Это и будет число кластеров на выбранном уровне детализации.
Как выбрать количество кластеров
В иерархической кластеризации число кластеров часто выбирают по дендрограмме, находя естественный уровень разреза дерева. Чем заметнее разрывы между ветвями, тем легче отделить группы друг от друга.
Если горизонтальная линия пересекает мало вертикальных ветвей и при этом проходит через крупный промежуток без новых слияний, такое разбиение обычно выглядит более устойчивым. Если же линия проходит там, где ветви сливаются очень плотно, выбор числа кластеров будет менее очевидным.
Дополнительно смотрят на предметную логику данных: насколько полученные группы интерпретируемы, не слишком ли они малы, не смешаны ли в них явно разные объекты.
- Размер кластеров — группы не должны быть случайным набором единичных наблюдений без смысла.
- Форма данных — разные методы связи лучше работают с разной геометрией кластеров.
- Выбросы — отдельные точки могут искажать картину.
- Тип признаков — числовые, бинарные и категориальные данные требуют разного подхода к расстояниям.
- Предметная область — статистически выделенная группа не всегда полезна с практической точки зрения.
В чем плюсы и ограничения иерархической кластеризации
Иерархическая кластеризация хорошо показывает структуру данных и связи между объектами, но требует заметных вычислительных ресурсов. Она особенно полезна там, где важна не только итоговая группировка, но и путь её формирования.
Плюсы связаны с интерпретируемостью. Дендрограмма позволяет увидеть данные на разных уровнях детализации. Необязательно заранее задавать число кластеров. Кроме того, метод помогает исследовать скрытую структуру выборки.
Ограничения тоже существенны. При больших наборах данных растут затраты по памяти и времени. Итог чувствителен к метрике расстояния и правилу связи. Жадный характер алгоритма означает, что ранние ошибки могут повлиять на всё последующее дерево.
Где применяют иерархическую кластеризацию
Иерархическая кластеризация используется там, где нужно найти естественные группы и понять отношения между ними. Метод подходит для анализа клиентов, биологических данных, текстов, изображений и сетевых структур.
В бизнес-аналитике с его помощью сегментируют клиентов по поведению, продуктовым предпочтениям, демографическим признакам и другим характеристикам. В исследованиях пациентов этот подход помогает выделять более однородные подгруппы по клиническим или генетическим признакам.
В биоинформатике метод применяют для группировки видов и биологических объектов по сходству признаков. В обработке изображений — для объединения похожих символов или элементов по форме. В информационном поиске — для тематической группировки документов и результатов поиска.
Чем иерархическая кластеризация отличается от k-средних
Иерархическая кластеризация строит дерево вложенных групп, а k-средних сразу делит данные на заранее заданное число кластеров. Это разные подходы к одной задаче.
| Критерий | Иерархическая кластеризация | k-средних |
| Число кластеров | Можно выбрать после построения дерева | Нужно задать заранее |
| Результат | Иерархия кластеров и дендрограмма | Плоское разбиение на группы |
| Подход | Объединение или деление по шагам | Итеративное перераспределение объектов |
| Чувствительность к инициализации | Обычно не связана со случайным стартом | Зависит от начального выбора центров |
| Масштабируемость | Часто хуже на больших данных | Обычно проще для крупных выборок |
Как интерпретировать результат без ошибок
Хороший результат кластеризации — это группы с высокой внутренней похожестью и заметными различиями между собой. Но в реальной задаче качество нельзя оценить только по красивой дендрограмме.
Нужно проверить, насколько выбранная метрика расстояния соответствует типу данных. Для бинарных признаков и для непрерывных числовых переменных один и тот же способ измерения расстояния может работать по-разному.
Дальше стоит сравнить несколько вариантов связи. Single linkage, complete linkage, average linkage и метод Уорда нередко дают разные деревья на одной и той же выборке. Если структура сохраняется при нескольких разумных настройках, выводы обычно выглядят убедительнее.
Отдельное внимание уделяют выбросам. Иногда одна необычная точка висит на дендрограмме отдельно и визуально притягивает к себе слишком много внимания. Это не всегда значит, что найден новый осмысленный кластер.
Когда иерархическая кластеризация особенно уместна
Метод особенно полезен, когда нужно исследовать данные, а не просто быстро получить разбиение. Он хорошо подходит для задач, где важны вложенные уровни сходства.
Если аналитик хочет понять, какие группы существуют на грубом уровне, а какие появляются только при более детальном разрезе, дендрограмма дает такой обзор сразу. Это удобно в исследовательском анализе данных, биоинформатике, сегментации аудиторий и разборе сложных наборов объектов.
Если же данных очень много и нужна быстрая масштабируемая модель с фиксированным числом кластеров, часто рассматривают более простые методы. Иерархический подход в таких случаях используют на подвыборке или для последующего анализа уже полученных сегментов.
Кратко: что нужно запомнить
Иерархическая кластеризация объединяет или делит данные в виде дерева вложенных кластеров. Главные элементы метода — метрика расстояния, правило связи и дендрограмма.
- Агломеративный подход идет от отдельных объектов к общему кластеру.
- Дивизимный подход идет от общего кластера к отдельным группам.
- Метод связи влияет на то, как именно формируются кластеры.
- Дендрограмма помогает увидеть структуру данных и выбрать число групп.
- Результат нужно интерпретировать с учетом типа данных, выбросов и предметного смысла.
