Раскрытие скрытых шаблонов Введение в иерархическую кластеризацию

Открывая скрытые шаблоны введение в иерархическую кластеризацию

 

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

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

 

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

 

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

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

Существует два общих алгоритма иерархической кластеризации, каждый со своим подходом: 

  • Агломеративная кластеризация
  • Дивизионная кластеризация

 

Агломеративная кластеризация

 

Предположим, что в наборе данных представлено n различных точек данных. Агломеративная кластеризация работает следующим образом:

  1. Начинается с n кластеров, где каждая точка данных является кластером по отдельности.
  2. Объединение точек данных на основе их сходства. То есть, схожие кластеры объединяются в зависимости от расстояния.
  3. Повторение шага 2 до тех пор, пока не останется только один кластер.

 

Дивизионная кластеризация

 

Как следует из названия, дивизионная кластеризация пытается выполнить обратное агломеративной кластеризации:

  1. Все n точек данных находятся в одном кластере.
  2. Разделиние этого одного большого кластера на более мелкие группы. Обратите внимание, что объединение точек данных в агломеративной кластеризации основано на сходстве. Но разделение их на разные кластеры основано на несходстве: точки данных в разных кластерах не похожи друг на друга.
  3. Повторение до тех пор, пока каждая точка данных не будет кластером по отдельности.

 

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

 

Как уже упоминалось, сходство между точками данных количественно оценивается с использованием расстояния. Часто используемые метрики расстояния включают евклидово и манхэттенское расстояние.

Для двух точек данных в n-мерном пространстве признаков евклидово расстояние между ними задается:

  

Другая часто используемая метрика расстояния – манхэттенское расстояние, задается:

  

Расстояние Минковского является обобщением для общего случая при p >= 1 в n-мерном пространстве:

 

 

Расстояние между кластерами: Понимание критериев связи

 

Используя метрику расстояния, мы можем вычислить расстояние между любыми двумя точками данных в наборе данных. Но вам также необходимо определить расстояние, чтобы определить “как” объединять кластеры на каждом шаге.

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

  • Одиночная связь
  • Полная связь
  • Средняя связь
  • Связь Уорда

 

Одиночная связь

 

В одиночной связи или одиночном кластерном анализе, расстояние между двумя группами / кластерами принимается в качестве наименьшего расстояния между всеми парами точек данных в двух кластерах. 

Полная связь

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

Средняя связь

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

Связь Уорда

Связь Уорда стремится минимизировать дисперсию в объединенных кластерах: объединение кластеров должно минимизировать общий прирост дисперсии после объединения. Это приводит к более компактным и хорошо отделенным кластерам.

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

Когда мы кодируем иерархическую кластеризацию в Python, мы также используем связь Уорда.

Что такое дендрограмма?

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

В иерархической древовидной структуре листья обозначают экземпляры или точки данных в наборе данных. Соответствующие расстояния, на которых происходит объединение или группировка, могут быть выведены из оси Y.

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

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

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

Иерархическая кластеризация в Python с помощью SciPy

Далее мы будем выполнять иерархическую кластеризацию на встроенном наборе данных о вине – шаг за шагом. Для этого мы воспользуемся пакетом кластеризации scipy.cluster из SciPy.

Шаг 1 – Импортировать необходимые библиотеки

Сначала импортируем библиотеки и необходимые модули из библиотек scikit-learn и SciPy:

# импортбиблиотекimport pandas as pdimport matplotlib.pyplot as pltfrom sklearn.datasets import load_winefrom sklearn.preprocessing import MinMaxScalerfrom scipy.cluster.hierarchy import dendrogram, linkage

Шаг 2 – Загрузить и предобработать набор данных

Затем мы загружаем набор данных о вине в pandas dataframe. Это простой набор данных, который является частью datasets в scikit-learn, и полезен для исследования иерархической кластеризации.

# Загрузить набор данныхdata = load_wine()X = data.data# Преобразовать в DataFramewine_df = pd.DataFrame(X, columns=data.feature_names)

Давайте проверим первые несколько строк фрейма данных:

wine_df.head()

Усеченный вывод wine_df.head()

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

Давайте проверим форму фрейма данных:

print(wine_df.shape)

В наборе данных 178 записей и 14 функций:

Результат >>> (178, 14)

Поскольку набор данных содержит числовые значения, распределенные по разным диапазонам, давайте предварительно обработаем его. Мы будем использовать MinMaxScaler для преобразования каждой функции таким образом, чтобы она принимала значения в диапазоне [0, 1].

# Масштабирование функций с помощью MinMaxScalerscaler = MinMaxScaler()X_scaled = scaler.fit_transform(X)

Шаг 3 – Выполнить иерархическую кластеризацию и построить дендрограмму

Давайте вычислим матрицу связи, выполним кластеризацию и построим дендрограмму. Мы можем использовать linkage из модуля hierarchy для расчета матрицы связи на основе связи Уорда (установите метод в ‘ward’).

Как обсуждалось ранее, связь Уорда минимизирует разброс внутри каждого кластера. Затем мы строим дендрограмму для визуализации процесса иерархической кластеризации.

# Расчет матрицы связиlinked = linkage(X_scaled, method='ward')# Построение дендрограммыplt.figure(figsize=(10, 6),dpi=200)dendrogram(linked, orientation='top', distance_sort='descending', show_leaf_counts=True)plt.title('Дендрограмма')plt.xlabel('Образцы')plt.ylabel('Расстояние')plt.show()

Поскольку мы пока не усекли дендрограмму, мы можем визуализировать, как каждая из 178 точек данных объединена в один кластер. Хотя это кажется сложным для интерпретации, мы все же видим, что есть три различных кластера.

Усечение дендрограммы для удобной визуализации

На практике, вместо всей дендрограммы, мы можем визуализировать усеченную версию, которую проще интерпретировать и понять.

Для усечения дендрограммы можно установить режим усечения на “уровень” и p = 3.

# Расчет матрицы связиlinked = linkage(X_scaled, method='ward')# Построение дендрограммыplt.figure(figsize=(10, 6),dpi=200)dendrogram(linked, orientation='top', distance_sort='descending', truncate_mode='level', p=3, show_leaf_counts=True)plt.title('Дендрограмма')plt.xlabel('Образцы')plt.ylabel('Расстояние')plt.show()

При этом дендрограмма усекается так, чтобы включать только те кластеры, которые находятся на расстоянии не более 3 уровней от окончательного объединения.

В приведенной выше дендрограмме можно видеть, что некоторые точки данных, такие как 158 и 159, представлены индивидуально. В то время как некоторые другие указаны в круглых скобках; это не отдельные точки данных, а количество точек данных в кластере. (k) обозначает кластер с k образцами.

Шаг 4 – Определение оптимального количества кластеров

Дендрограмма помогает нам выбрать оптимальное количество кластеров.

Мы можем наблюдать, где расстояние по оси y резко увеличивается, выбрать усечение дендрограммы на этой точке и использовать расстояние в качестве порога для формирования кластеров.

В данном примере оптимальное количество кластеров составляет 3.

 

 

Шаг 5 - Формирование кластеров 

 

После того, как мы решили об оптимальном количестве кластеров, мы можем использовать соответствующее расстояние по оси y - пороговое расстояние. Это гарантирует, что выше порогового расстояния кластеры больше не объединяются. Мы выбираем пороговое расстояние threshold_distance равное 3,5 (как выведено из дендрограммы).

Затем мы используем fcluster с параметром criterion установленным на 'distance' для получения присвоения кластера всем точкам данных:

from scipy.cluster.hierarchy import fcluster# Выбор порогового расстояния на основе дендрограммыthreshold_distance = 3.5  # Обрезка дендрограммы для получения меток кластеровcluster_labels = fcluster(linked, threshold_distance, criterion='distance')# Присвоение меток кластеров DataFrame'уwine_df['cluster'] = cluster_labels

 

Теперь вы должны видеть метки кластеров (одно из {1, 2, 3}) для всех точек данных:

print(wine_df['cluster'])

 

Вывод >>>0      21      22      23      24      3      ..173    1174    1175    1176    1177    1Name: cluster, Length: 178, dtype: int32

 

Шаг 6 - Визуализация кластеров

 

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

plt.figure(figsize=(8, 6))scatter = plt.scatter(wine_df['alcohol'], wine_df['flavanoids'], c=wine_df['cluster'], cmap='rainbow')plt.xlabel('Алкоголь')plt.ylabel('Флавоноиды')plt.title('Визуализация кластеров')# Добавление легендыlegend_labels = [f'Кластер {i + 1}' for i in range(n_clusters)]plt.legend(handles=scatter.legend_elements()[0], labels=legend_labels)plt.show()

 

 

Заключение

 

Это и все! В этом руководстве мы использовали SciPy для выполнения иерархической кластеризации, чтобы подробнее рассмотреть этапы. В качестве альтернативы вы также можете использовать класс AgglomerativeClustering из модуля cluster библиотеки scikit-learn. Счастливого кодирования кластеризации!

 

Литература

 

[1] Введение в машинное обучение

[2] Введение в статистическое обучение (ISLR)  Бала Прия Чеера - разработчик и технический писатель из Индии. Ей нравится работа в области математики, программирования, науки о данных и создания контента. Ее интересы и экспертиза включают DevOps, науку о данных и обработку естественного языка. Она любит чтение, писание, программирование и кофе! В настоящее время она работает над изучением и передачей своих знаний сообществу разработчиков, создавая учебники, руководства, мнения и многое другое.