Выявление скрытых закономерностей: введение в иерархическую кластеризацию

Выявление скрытых закономерностей: введение в иерархическую кластеризацию

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

Бала Прия С., KDnuggets, 6 октября 2023 г., Машинное обучение

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

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

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

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

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

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

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

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

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

     Начните с n кластеров; каждая точка данных сама по себе является кластером.
     Сгруппируйте точки данных по сходству между ними. Это означает, что подобные кластеры объединяются в зависимости от расстояния.
     Повторяйте шаг 2, пока не останется только один кластер.

Разделительная кластеризация

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

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

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

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

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

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

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

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

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

Одинарное соединение

При односвязной или односвязной кластеризации расстояние между двумя группами/кластерами принимается как наименьшее расстояние между всеми парами точек данных в двух кластерах.
Раскрытие скрытых закономерностей: введение в иерархическую кластеризациюРаскрытие скрытых закономерностей: введение в иерархическую кластеризацию

Полная связь

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

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

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

Связь Уорда

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

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

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

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

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

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

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

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

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

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

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

Шаг 1. Импортируйте необходимые библиотеки.

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

# imports  import pandas as pd  import matplotlib.pyplot as plt  from sklearn.datasets import load_wine  from sklearn.preprocessing import MinMaxScaler  from scipy.cluster.hierarchy import dendrogram, linkage

Шаг 2. Загрузите и предварительно обработайте набор данных.

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

# Load the dataset  data = load_wine()  X = data.data    # Convert to DataFrame  wine_df = pd.DataFrame(X, columns=data.feature_names)

Давайте проверим первые несколько строк кадра данных:Lets check the first few rows of the dataframe:

wine_df.head()    

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

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

print(wine_df.shape)

Всего 178 записей и 14 функций:There are 178 records and 14 features:

Output >>> (178, 14)

Поскольку набор данных содержит числовые значения, разбросанные по разным диапазонам, давайте предварительно обработаем набор данных. Мы будем использовать MinMaxScaler для преобразования каждой функции так, чтобы она принимала значения в диапазоне [0, 1]. to transform each of the features to take on values in the range [0, 1].

# Scale the features using MinMaxScaler  scaler = MinMaxScaler()  X_scaled = scaler.fit_transform(X)

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

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

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

# Calculate linkage matrix  linked = linkage(X_scaled, method='ward')    # Plot dendrogram  plt.figure(figsize=(10, 6),dpi=200)  dendrogram(linked, orientation='top', distance_sort='descending', show_leaf_counts=True)  plt.title('Dendrogram')  plt.xlabel('Samples')  plt.ylabel('Distance')  plt.show()

Because we haven't (yet) truncated the dendrogram, we get to visualize how each of the 178 data points are grouped together into a single cluster. Though this is seemingly difficult to interpret, we can still see that there are three different clusters.

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

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

Чтобы усечь дендрограмму, мы можем установить truncate_mode на «уровень» и p = 3.б.

# Calculate linkage matrix  linked = linkage(X_scaled, method='ward')    # Plot dendrogram  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('Dendrogram')  plt.xlabel('Samples')  plt.ylabel('Distance')  plt.show()

Doing so will truncate the dendrogram to include only those clusters which are within 3 levels from the final merge. 

In the above dendrogram, you can see that some data points such as 158 and 159 are represented individually. Whereas some others are mentioned within parentheses; these are not individual data points but the number of data points in a cluster. (k) denotes a cluster with k samples.

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

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

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

Для этого примера оптимальное количество кластеров — 3.

Шаг 5 – Формируем кластеры

Как только мы определились с оптимальным количеством кластеров, мы можем использовать соответствующее расстояние по оси Y — пороговое расстояние. Это гарантирует, что кластеры, находящиеся выше порогового расстояния, больше не будут сливаться. Мы выбираем пороговое расстояние 3,5 (как следует из дендрограммы).

Затем мы используем fcluster с критерием, установленным на «расстояние», чтобы получить назначение кластера для всех точек данных:

from scipy.cluster.hierarchy import fcluster    # Choose a threshold distance based on the dendrogram  threshold_distance = 3.5      # Cut the dendrogram to get cluster labels  cluster_labels = fcluster(linked, threshold_distance, criterion='distance')    # Assign cluster labels to the DataFrame  wine_df['cluster'] = cluster_labels

Теперь вы сможете увидеть метки кластера (одну из {1, 2, 3}) для всех точек данных:You should now be able to see the cluster labels (one of {1, 2, 3}) for all the data points:

print(wine_df['cluster'])

Output >>>  0      2  1      2  2      2  3      2  4      3        ..  173    1  174    1  175    1  176    1  177    1  Name: 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('Alcohol')  plt.ylabel('Flavonoids')  plt.title('Visualizing the clusters')    # Add legend  legend_labels = [f'Cluster {i + 1}' for i in range(n_clusters)]  plt.legend(handles=scatter.legend_elements()[0], labels=legend_labels)    plt.show()

Подведение итогов

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

Рекомендации

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

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