Agglomerative Clustering: алгоритм иерархической кластеризации

Для кого эта статья:

• аналитики данных и статистики
• студенты и специалисты в области машинного обучения
• профессионалы в маркетинге и биоинформатике

Представьте, что вам нужно разделить клиентов интернет-магазина на группы со схожими покупательскими привычками. Как это сделать эффективно? Agglomerative Clustering — алгоритм, который постепенно объединяет отдельные точки данных в кластеры, строя иерархическую структуру, напоминающую перевёрнутое дерево. В отличие от популярного K-means, этот метод не требует предварительного указания числа кластеров и позволяет наглядно увидеть, как формируются группы на разных уровнях детализации. 🔍 Именно поэтому агломеративная кластеризация стала незаменимым инструментом в арсенале аналитиков данных, биологов, маркетологов и исследователей из разных областей.

Хотите освоить продвинутые методы анализа данных, включая иерархическую кластеризацию? Курс «Аналитик данных» с нуля от Skypro погружает студентов в реальные бизнес-задачи с применением алгоритмов кластеризации. Вы научитесь не только реализовывать Agglomerative Clustering в Python, но и интерпретировать полученные результаты, создавая визуально понятные дендрограммы для принятия бизнес-решений. Первые результаты — уже через 2 месяца обучения!

Основы Agglomerative Clustering и его место в анализе данных

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

Ключевые характеристики агломеративной кластеризации:

• Восходящий (bottom-up) подход: каждый объект изначально представляет собой отдельный кластер
• Итеративное объединение: на каждом шаге соединяются два ближайших кластера
• Иерархическая структура: результат можно представить в виде дендрограммы
• Не требует предварительного указания числа кластеров
• Работает с различными метриками расстояния между объектами

Алгоритм агломеративной кластеризации прост для понимания, но может быть вычислительно затратным для больших наборов данных. Его сложность составляет O(n³) в худшем случае, где n — количество объектов, хотя оптимизированные реализации могут достигать O(n²log(n)).

Андрей Корнилов, ведущий аналитик данных Когда я начинал работать с сегментацией клиентов в телекоме, мы использовали K-means, но постоянно сталкивались с проблемой выбора оптимального числа кластеров. Переход к агломеративной кластеризации стал настоящим прорывом. Анализируя дендрограмму, мы могли визуально определить естественное количество сегментов пользователей и их иерархические связи. Это позволило нам разработать многоуровневую стратегию маркетинга: от широких кампаний для крупных сегментов до узконаправленных предложений для мини-групп клиентов. Наш ARPU вырос на 17% за квартал после внедрения новой модели таргетирования.

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

Математический фундамент агломеративной кластеризации

В основе агломеративной кластеризации лежит понятие матрицы расстояний (или матрицы близости) между объектами. Для n объектов эта матрица имеет размер n×n и содержит попарные расстояния между всеми объектами. 📊

Процесс агломеративной кластеризации можно описать следующим образом:

1. Инициализация: каждый объект рассматривается как отдельный кластер (всего n кластеров)
2. Вычисление матрицы расстояний между всеми парами текущих кластеров
3. Поиск и объединение двух ближайших кластеров
4. Обновление матрицы расстояний с учетом образованного кластера
5. Повторение шагов 2-4 пока все объекты не объединятся в один кластер или не будет достигнуто заданное число кластеров

Математически расстояние между объектами x и y можно рассчитать разными способами, наиболее распространенные из которых:

# Евклидово расстояние
d(x, y) = sqrt(sum((x_i – y_i)² for i in range(dim)))

# Манхэттенское расстояние
d(x, y) = sum(|x_i – y_i| for i in range(dim))

# Косинусное расстояние
d(x, y) = 1 – cos(x, y) = 1 – (sum(x_i * y_i) / (sqrt(sum(x_i²)) * sqrt(sum(y_i²))))

Выбор метрики расстояния критически важен и зависит от специфики данных. Например, для текстовых данных часто предпочтительнее косинусная мера, в то время как для географических координат уместно евклидово расстояние.

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

Методы связывания кластеров в агломеративных алгоритмах

Методы связывания (linkage methods) определяют, как рассчитывается расстояние между кластерами, состоящими из нескольких объектов. Выбор метода связывания существенно влияет на форму получаемых кластеров и итоговую дендрограмму. 🔗

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

Полная связь (Complete linkage) использует максимальное расстояние между любыми двумя объектами из разных кластеров. Такой подход создает более компактные кластеры и менее подвержен эффекту цепочки, но может быть чувствителен к выбросам.

Средняя связь (Average linkage) вычисляет среднее расстояние между всеми парами объектов из разных кластеров, что делает этот метод более устойчивым к выбросам и обеспечивает компромисс между одиночной и полной связью.

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

# Пример расстояния с использованием метода Уорда в Python
def ward_distance(cluster1, cluster2):
n1, n2 = len(cluster1), len(cluster2)
centroid1 = np.mean(cluster1, axis=0)
centroid2 = np.mean(cluster2, axis=0)
merged = np.vstack([cluster1, cluster2])
merged_centroid = np.mean(merged, axis=0)

# Увеличение суммы квадратов
increase = np.sum(np.square(merged – merged_centroid)) – \
(np.sum(np.square(cluster1 – centroid1)) + 
np.sum(np.square(cluster2 – centroid2)))

return increase

Реализация Agglomerative Clustering в популярных библиотеках

Реализация агломеративной кластеризации доступна в большинстве популярных библиотек машинного обучения. Рассмотрим наиболее распространенные инструменты для Python. 💻

Мария Ковалёва, преподаватель алгоритмов машинного обучения На своих курсах я всегда сталкиваюсь с тем, что студенты, впервые погружаясь в иерархическую кластеризацию, переоценивают её вычислительные возможности. Один из моих студентов пытался применить агломеративную кластеризацию к набору из 100 000 строк логов сервера. Алгоритм работал несколько часов, а затем аварийно завершился из-за нехватки памяти. После этого мы провели небольшой эксперимент: разработали пайплайн, где сначала применили K-means для создания 500 прототипов, а затем использовали агломеративную кластеризацию уже для этих прототипов. Результаты оказались практически идентичными исходной задаче, но время выполнения сократилось с "бесконечности" до 2 минут. Этот опыт стал ценным уроком для всей группы о важности предварительной оценки вычислительной сложности алгоритмов.

В библиотеке scikit-learn реализация агломеративной кластеризации представлена классом AgglomerativeClustering:

from sklearn.cluster import AgglomerativeClustering
import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram

# Создаем случайные данные
np.random.seed(42)
X = np.random.rand(50, 2)

# Применяем агломеративную кластеризацию
model = AgglomerativeClustering(
n_clusters=3, # количество кластеров
affinity='euclidean', # метрика расстояния
linkage='ward' # метод связывания
)

# Получаем метки кластеров
labels = model.fit_predict(X)

# Визуализируем результаты
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=50)
plt.title('Agglomerative Clustering Results')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.colorbar(label='Cluster')
plt.show()

Для построения дендрограммы, которая является ключевым визуальным представлением результатов иерархической кластеризации, используется функция из библиотеки SciPy:

from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

# Вычисляем связи для дендрограммы
Z = linkage(X, method='ward')

# Строим дендрограмму
plt.figure(figsize=(12, 6))
dendrogram(Z)
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('Sample index')
plt.ylabel('Distance')
plt.axhline(y=1.2, c='k', linestyle='--', label='Cutoff for 3 clusters')
plt.legend()
plt.show()

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

• Предварительное уменьшение размерности данных (PCA, t-SNE)
• Выборка из исходного набора данных
• Двухэтапная кластеризация: сначала K-means, затем агломеративная кластеризация центроидов
• Использование реализаций с оптимизированными структурами данных, например HDBSCAN

Библиотека HDBSCAN предлагает оптимизированную реализацию иерархической кластеризации, особенно эффективную для больших наборов данных:

import hdbscan

# Создаем модель с агломеративным алгоритмом
clusterer = hdbscan.HDBSCAN(
algorithm='generic', # использовать общий агломеративный алгоритм
metric='euclidean',
min_cluster_size=5,
min_samples=1
)

# Применяем к данным
cluster_labels = clusterer.fit_predict(X)

R также предоставляет мощные инструменты для агломеративной кластеризации через функцию hclust в базовом пакете stats, а также расширенные возможности в специализированных пакетах, таких как cluster и fastcluster.

Практические применения агломеративной кластеризации

Агломеративная кластеризация находит применение в различных областях благодаря своей интерпретируемости и способности выявлять иерархические структуры в данных. 🚀

Основные сферы применения:

• Маркетинг и CRM: сегментация клиентов, иерархическая классификация потребительских предпочтений
• Биоинформатика: кластеризация генов, анализ белковых структур, филогенетические исследования
• Обработка естественного языка: кластеризация документов, тематическое моделирование, иерархические таксономии
• Изображения и компьютерное зрение: сегментация изображений, распознавание объектов
• Социальные сети: выявление сообществ, анализ иерархической структуры социальных связей
• Экономика: кластеризация финансовых инструментов, анализ рыночных сегментов

Рассмотрим конкретные примеры применения агломеративной кластеризации:

1. Сегментация клиентов

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

2. Анализ генетических данных

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

3. Организация документов

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

Хотите понять, какое направление в аналитике данных подходит именно вам? Тест на профориентацию от Skypro поможет определить, с какими алгоритмами анализа данных вам будет работать комфортнее всего. Возможно, ваши сильные стороны идеально подходят для работы с иерархическими методами кластеризации, включая Agglomerative Clustering. Пройдите тест и получите персональные рекомендации по развитию карьеры в аналитике данных!

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

• Возможность исследовать данные на разных уровнях грануляции
• Отсутствие необходимости заранее определять количество кластеров
• Визуальное представление результатов через дендрограмму
• Возможность работать с различными мерами сходства

Ограничения, которые следует учитывать:

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

Агломеративная кластеризация — это мощный инструмент аналитика данных, который раскрывает скрытые иерархические структуры в информации. Понимая математический фундамент и особенности различных методов связывания, вы можете превратить хаотичный набор точек в осмысленную структуру взаимосвязей. Будь то сегментация клиентов, анализ белковых последовательностей или организация документов — дендрограммы этого алгоритма позволяют увидеть мир данных в новом свете, где каждый объект занимает свое место в естественной иерархии. Освоив этот метод, вы получаете не просто способ кластеризации, но и инструмент для открытия многоуровневых закономерностей, недоступных при использовании плоских алгоритмов.