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

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

История

Истоки иерархической кластеризации лежат в биологической таксономии, где необходимо было классифицировать виды организмов по степени их родства. Одним из первых алгоритмов, формализовавших этот процесс, считается метод одиночной связи (single linkage), предложенный в 1950-х годах. В 1963 году Дж. Х. Уорд-младший (Joe H. Ward Jr.) опубликовал метод минимизации дисперсии (метод Уорда), который стал одним из наиболее популярных агломеративных алгоритмов. Развитие вычислительной техники во второй половине XX века позволило применять иерархическую кластеризацию к большим массивам данных в таких областях, как биоинформатика, маркетинг, геология и социальные науки.

Классификация методов

Иерархическая кластеризация делится на два основных подхода: агломеративный (восходящий) и дивизивный (нисходящий).

Агломеративные методы

Агломеративные методы начинают работу с того, что каждый объект данных считается отдельным кластером. На каждом следующем шаге два наиболее близких (по заданной метрике) кластера объединяются. Процесс повторяется до тех пор, пока все объекты не будут объединены в один кластер. Результатом является дендрограмма, на которой можно «обрезать» дерево на любом уровне, чтобы получить желаемое количество кластеров. Основное различие между агломеративными алгоритмами заключается в способе вычисления расстояния между кластерами (критерии связи):

• Метод одиночной связи (Single linkage): Расстояние между кластерами определяется как минимальное расстояние между любыми двумя объектами из разных кластеров. Этот метод хорошо выделяет вытянутые, цепочечные кластеры, но чувствителен к шуму и может приводить к эффекту «цепочки» (chaining), когда объекты присоединяются к кластеру по одному, образуя длинные, некомпактные группы.
• Метод полной связи (Complete linkage): Расстояние между кластерами определяется как максимальное расстояние между любыми двумя объектами из разных кластеров. Этот метод стремится создавать компактные, сферические кластеры одинакового диаметра. Он менее чувствителен к шуму, чем одиночная связь.
• Метод средней связи (Average linkage, UPGMA — Unweighted Pair Group Method with Arithmetic Mean): Расстояние между кластерами определяется как среднее арифметическое всех попарных расстояний между объектами из разных кластеров. Этот метод является компромиссом между одиночной и полной связью и часто используется в биоинформатике.
• Метод Уорда (Ward’s method): Объединение двух кластеров происходит таким образом, чтобы минимизировать увеличение общей внутрикластерной дисперсии (суммы квадратов отклонений от центра кластера). Этот метод также стремится создавать компактные, равномерно заполненные кластеры и считается одним из наиболее эффективных для многих типов данных.

Дивизивные методы

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

Метрики расстояния

Выбор метрики расстояния между объектами является ключевым для результата кластеризации. Наиболее распространённые метрики для количественных данных:

• Евклидово расстояние: Наиболее часто используемая метрика, геометрическое расстояние между точками в многомерном пространстве.
• Квадрат евклидова расстояния: Используется в методе Уорда и некоторых других алгоритмах для придания большего веса удалённым объектам.
• Манхэттенское расстояние (городских кварталов): Сумма модулей разностей координат. Менее чувствительно к выбросам, чем евклидово расстояние.
• Расстояние Чебышёва: Максимальная разность координат.
• Косинусное расстояние: Определяется как 1 минус косинус угла между векторами признаков. Используется для анализа текстов и других данных, где важна ориентация, а не длина вектора.

Для категориальных данных могут применяться специальные метрики, такие как расстояние Хэмминга (число несовпадающих признаков) или меры сходства на основе коэффициента Жаккара.

Применение

Иерархическая кластеризация находит применение в самых разных областях:

• Биоинформатика и генетика: Построение филогенетических деревьев (эволюционных связей между видами) на основе генетических последовательностей. Кластеризация генов и белков по функциональной активности.
• Маркетинг и анализ потребителей: Сегментация клиентов по поведению, предпочтениям и демографическим признакам для разработки таргетированных рекламных кампаний.
• Обработка естественного языка: Кластеризация документов по тематикам (тематическое моделирование), построение иерархий понятий и терминов (онтологий).
• Геология и экология: Классификация типов почв, горных пород, растительных сообществ на основе измеренных характеристик.
• Медицина: Классификация заболеваний на основе симптомов или генетических маркеров, выявление подтипов раковых опухолей.

Достоинства и недостатки

Достоинства

• Отсутствие необходимости задавать количество кластеров: Дендрограмма позволяет исследователю выбрать уровень детализации, наиболее подходящий для решаемой задачи.
• Визуализация: Дендрограмма даёт наглядное представление о структуре данных и взаимосвязях между объектами.
• Интерпретируемость: Результаты кластеризации легко интерпретировать, особенно при небольшом объёме данных.

Недостатки

• Вычислительная сложность: Большинство агломеративных алгоритмов имеют временную сложность O(n³) или O(n² log n), где n — число объектов. Это делает их неприменимыми для очень больших наборов данных (миллионы объектов).
• Необратимость: Агломеративные методы не могут пересматривать принятые решения об объединении кластеров на более поздних шагах. Ошибка, сделанная на раннем этапе, может повлиять на всю последующую иерархию.
• Чувствительность к шуму и выбросам: Выбросы могут существенно исказить результаты, особенно в методе одиночной связи.
• Субъективность выбора метрики и критерия связи: Разные комбинации могут приводить к совершенно разным результатам, и выбор часто определяется эмпирически или исходя из предметной области.

Примеры

1. Классификация животных: На основе набора признаков (наличие позвоночника, количество конечностей, среда обитания и т.д.) иерархическая кластеризация может воспроизвести биологическую таксономию, разделив животных на млекопитающих, птиц, рептилий, рыб и т.д., а затем — на более мелкие группы.
2. Анализ текстов: При кластеризации новостных статей по ключевым словам, иерархический метод может сначала выделить крупные темы (политика, экономика, спорт), а затем — более узкие подтемы (внешняя политика, внутренняя политика, фондовый рынок, футбол, хоккей).

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

• Дендрограмма как способ визуализации была впервые предложена в 1960-х годах и с тех пор стала стандартом в таксономии и кластерном анализе.
• В некоторых областях, например, в археологии, иерархическая кластеризация используется для классификации артефактов (керамики, орудий труда) по стилям и периодам.
• Алгоритм BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) является одним из немногих иерархических методов, способных эффективно обрабатывать большие объёмы данных, за счёт построения сжатого представления данных в виде CF-дерева.

Источники

1. Ward, J. H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301), 236-244.
2. Jain, A. K., & Dubes, R. C. (1988). Algorithms for Clustering Data. Prentice-Hall.
3. Kaufman, L., & Rousseeuw, P. J. (2009). Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons.
4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer.