Дендрограмма

Дендрограмма (от греч. δένδρον — дерево и γράμμα — запись, рисунок) — это графическое представление результатов иерархической кластеризации, выполненное в виде дерева. Дендрограмма отображает порядок объединения объектов или кластеров и расстояние (меру сходства или различия) между ними на каждом этапе кластеризации. Она позволяет визуально оценить структуру данных, выявить естественные группы и определить оптимальное количество кластеров.

История

Понятие дендрограммы тесно связано с развитием методов кластерного анализа, которые зародились в биологии, психологии и антропологии в первой половине XX века. Одним из пионеров иерархической кластеризации считается американский психолог Роберт Трайон, который в 1939 году разработал метод, позволяющий визуализировать корреляции между переменными. Однако термин «дендрограмма» ввёл в научный обиход, по разным данным, в конце 1950-х — начале 1960-х годов.

Значительный вклад в популяризацию дендрограмм внёс британский биолог и статистик Питер Снис и американский информатик Роберт Себертет. В книге «Таксономия для численного анализа» (1963) они подробно описали процесс построения дендрограмм для классификации биологических видов. Впоследствии метод распространился на многие области науки, включая маркетинг (сегментация рынка), социологию, лингвистику, информатику (кластеризация документов) и медицину (группировка пациентов по симптомам).

Строение и принципы построения

Дендрограмма состоит из следующих элементов:

• Узлы (листья) — исходные объекты анализа (например, виды животных, города, товары). Они располагаются на самой нижней линии (оси X) графика.
• Ветви (кластеры) — линии, соединяющие отдельные объекты или группы объектов. Точки соединения ветвей называются узлами слияния (или вершинами).
• Высота узла слияния — значение на оси Y, которое соответствует расстоянию (или меры несходства) между двумя объединяемыми кластерами. Чем выше узел, тем более различны кластеры, которые он объединяет.

Шкала расстояний

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

Порядок построения

Процесс построения дендрограммы, основанный на иерархической агломеративной кластеризации, включает следующие шаги:

1. Каждый объект изначально считается отдельным кластером (N кластеров).
2. Вычисляется матрица расстояний между всеми парами кластеров.
3. На каждом шаге два самых близких (наименее различных) кластера объединяются в один новый кластер.
4. Расстояния между новым кластером и остальными пересчитываются (по одному из методов сшивания).
5. Процесс повторяется до тех пор, пока все объекты не окажутся в одном кластере.
6. Результат фиксируется в виде дендрограммы, где каждый шаг объединения отображается узлом слияния на соответствующей высоте.

Методы сшивания (Linkage Methods)

Выбор метода сшивания (способа вычисления расстояния между кластерами) существенно влияет на форму дендрограммы и получаемую классификацию.

Одиночное сшивание (Single linkage)

Расстояние между двумя кластерами определяется как минимальное расстояние между любыми двумя объектами из разных кластеров. Этот метод часто приводит к образованию длинных «цепочек» кластеров (эффект цепочки) и может быть чувствителен к выбросам.

Полное сшивание (Complete linkage)

Расстояние между двумя кластерами определяется как максимальное расстояние между любыми двумя объектами из разных кластеров. Метод стремится создавать компактные кластеры примерно равного диаметра, но может быть слишком жёстким.

Среднее сшивание (Average linkage, UPGMA)

Расстояние между двумя кластерами вычисляется как среднее арифметическое всех расстояний между парами объектов, где один объект берётся из первого кластера, а другой — из второго. Метод является компромиссным и часто используется в биологии.

Метод Уорда (Ward's method)

При объединении кластеров выбирается пара, дающая минимальный прирост общей суммы квадратов отклонений (внутрикластерной дисперсии). Метод стремится создавать кластеры примерно равного размера и является одним из наиболее популярных в социально-экономических исследованиях.

Метод центроидов (Centroid linkage)

Расстояние между кластерами определяется как расстояние между их центроидами (средними значениями по всем признакам). Метод может приводить к инверсиям (когда высота узла при объединении оказывается меньше, чем высота более ранних узлов).

Типы дендрограмм

Горизонтальная дендрограмма

Самый распространённый тип, где листья расположены вдоль оси X, а ветви растут вверх (или вправо). Такое представление удобно для анализа большого количества объектов.

Вертикальная (пологая) дендрограмма

Ветви растут вправо, а листья располагаются на вертикальной оси. Удобна для сравнения нескольких дендрограмм, построенных на разных данных.

Дендрограмма с боковой шкалой

Дополнительно отображает, сколько объектов содержит каждый кластер и на каком расстоянии происходит объединение.

Интерпретация и разрезание

Основная задача при работе с дендрограммой — выбор порога отсечения (cut), который определяет количество кластеров. Порог проводится параллельно оси X на определённой высоте. Все объекты, соединённые ветвями ниже этого порога, считаются принадлежащими одному кластеру. Чем выше выбран порог, тем меньше кластеров и наоборот.

Критерии выбора порога отсечения:

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

Пример использования

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

Ограничения

• Дендрограмма представляет результат иерархической кластеризации, который не всегда однозначен. Разные методы сшивания и метрики расстояния могут давать различные деревья.
• С увеличением объёма данных (сотен тысяч объектов) построение дендрограммы становится вычислительно сложным (классический алгоритм имеет сложность O(N²) по памяти и O(N³) по времени).
• Дендрограмма не показывает внутреннюю структуру кластеров (например, форму или плотность распределения точек).
• Выбор субъективного порога отсечения может привести к ошибкам в классификации.

Применение

• Биология и экология — классификация организмов по морфологическим, генетическим или экологическим признакам; анализ филогенетических связей.
• Маркетинг — сегментация потребительской базы, анализ товарных корзин.
• Медицина — группировка пациентов по симптоматике или эффективности терапии.
• Лингвистика — классификация языков, анализ лексических групп.
• Информатика — кластеризация текстовых документов, веб-страниц или изображений.
• Геоинформатика — выявление пространственных паттернов, группировка регионов по географическим характеристикам.

Источники

• Everitt, B., Landau, S., Leese, M., & Stahl, D. (2011). Cluster Analysis (5th ed.). Wiley.
• Кабаков Р. И. (2014). R в действии. Анализ и визуализация данных в программе R. ДМК-Пресс.
• Мастицкий С. Э., Шитиков В. К. (2015). Статистический анализ и визуализация данных с помощью R. ДМК-Пресс.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer.