В этом уроке мы рассмотрим тему иерархической кластеризации в обучении без учителя. Мы обсудим концепцию иерархической кластеризации и ее отличия от других методов кластеризации, включая методы агломерации и разделения. Мы проведем вас через шаги, связанные с агломеративной кластеризацией, такие как инициализация, расчет расстояния, объединение кластеров, создание дендрограммы и определение количества кластеров. Чтобы помочь вам лучше понять процесс, также предоставляются примеры кода Python. Кроме того, мы рассмотрим преимущества и ограничения иерархической кластеризации по сравнению с другими алгоритмами кластеризации, такими как K-средние и смешанные модели Гаусса. Наконец, мы завершим обсуждением субъективного характера выбора значения координаты y для определения количества кластеров и важности определения правильного критерия кластеризации для достижения оптимальных результатов.

🦊Если вы хотите узнать больше о кластеризации в неконтролируемом обучении, вам может быть интересно прочитать мою другую статью «Методы кластеризации 101: Введение в неконтролируемые методы обучения». В этом руководстве представлен всесторонний обзор. различных методов кластеризации, включая иерархическую кластеризацию, кластеризацию на основе плотности и кластеризацию на основе моделей, и обсуждают их преимущества и недостатки. В нем также рассматриваются такие темы, как оценка и выбор кластера, и приводятся примеры приложений кластеризации в различных областях.

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

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

Между корнем и листьями дендрограммы наиболее похожие «одноточечные» кластеры итеративно объединяются в более крупные кластеры на каждом уровне дендрограммы, пока не будет достигнут кластер «вселенная», который представляет все точки данных в наборе данных. , как показано на следующем рисунке:

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

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

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

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

🔍 Рассмотрим подробнее процесс агломеративной кластеризации

Процесс агломеративной кластеризации можно разбить на несколько этапов, а именно:

  1. Инициализация. Алгоритм начинается с назначения каждой точки данных отдельному кластеру, в результате чего получается n кластеров для n точек данных.
  2. Вычисление расстояния: попарное расстояние между каждой парой одноточечных кластеров вычисляется с использованием метрики расстояния, такой как евклидово расстояние, манхэттенское расстояние или косинусное сходство. Этот шаг обычно является наиболее дорогостоящей и трудоемкой частью алгоритма, особенно для больших наборов данных.
  3. Объединение кластеров: два ближайших кластера объединяются для создания нового кластера. Расстояние между новым кластером и оставшимися кластерами пересчитывается, и процесс повторяется до тех пор, пока все точки данных не будут принадлежать одному кластеру.
  4. Генерация дендрограммы: процесс кластеризации генерирует дендрограмму, которая представляет иерархию кластеров. Дендрограмма представляет собой древовидную структуру, показывающую взаимосвязь между кластерами на каждом уровне иерархии. Листья дендрограммы представляют кластеры «одной точки», а крыша представляет кластер «вселенная», который содержит все точки данных.
  5. Определение количества кластеров: количество кластеров можно определить, разрезав дендрограмму на определенном пороге высоты или расстояния. Это позволяет исследователям выбирать количество кластеров, которые лучше всего соответствуют их исследовательскому вопросу и данным.

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

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

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

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

💡 Предположим, у нас есть набор данных с четырьмя точками:

Data Points: A(2,3), B(7,5), C(0,4), D(6,2)

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

  1. Инициализация: мы начинаем с назначения каждой точки отдельному кластеру, создавая в общей сложности 4 кластера (A, B, C, D) для 4 точек данных.

2. Расчет расстояния: мы вычисляем попарное расстояние между каждой парой одноточечных кластеров, используя евклидово расстояние. Матрица близости для заданных точек данных A (2,3), B (7,5), C (0,4) и D (6,2) может быть рассчитана с использованием формулы евклидова расстояния, которая определяется как:

d(A,B) = sqrt((xB — xA)² + (yB — yA)²)

Используя эту формулу, мы можем рассчитать расстояния между каждой парой точек следующим образом:

  • Расстояние от A до B: Расстояние между A и B: sqrt((7–2)² + (5–3)²) = 5,39.
  • Расстояние от А до С: 2,24
  • Расстояние от А до D: 4,12
  • Расстояние от B до C: 7,07
  • Расстояние от B до D: 3,16
  • Расстояние от C до D: 6,32

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

      A     B     C     D
A  0.00  5.39  2.24  4.12
B  5.39  0.00  7.07  3.16
C  2.24  7.07  0.00  6.32
D  4.12  3.16  6.32  0.00

🐍 С точки зрения Python код будет выглядеть так:

import matplotlib.pyplot as plt
from sklearn.metrics import euclidean_distances

# Define the points
points = {
    "A": [2, 3],
    "B": [7, 5],
    "C": [0, 4],
    "D": [6, 2]
}

# Calculate the proximity matrix
proximity_matrix = euclidean_distances(list(points.values()))

# Create the plot
fig, ax = plt.subplots()

# Plot the points
for label, coords in points.items():
    ax.plot(coords[0], coords[1], marker="o", markersize=10, label=label)

# Add labels and distances between points
for i in range(len(proximity_matrix)):
    for j in range(i+1, len(proximity_matrix)):
        p1, p2 = list(points.keys())[i], list(points.keys())[j]
        x = (points[p1][0] + points[p2][0]) / 2
        y = (points[p1][1] + points[p2][1]) / 2
        ax.annotate(str(round(proximity_matrix[i][j], 2)), xy=(x, y), ha="center", va="center")
        ax.annotate("", xy=points[p1], xytext=points[p2],
                    arrowprops=dict(arrowstyle="<->", color="gray"))

# Add legend
ax.legend()

# Show the plot
plt.show()

4. Объединение кластеров: мы объединяем два ближайших кластера, используя полную связь. Для этого мы сначала идентифицируем наименьшее расстояние в матрице близости. Мы видим, что наименьшее расстояние равно 2,24 между точками A и C.

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

Чтобы объединить точки A и C с использованием полной связи, нам нужно обновить матрицу близости, чтобы отразить расстояния между новым кластером и оставшимися отдельными точками. Например, расстояние между новым кластером AC и точкой B — это максимальное расстояние между любой точкой AC и B, которое равно max(5,39, 2,24) = 5,39. Расстояние между новым кластером AC и точкой D равно максимальному расстоянию между любой точкой AC и D, равному max(4.12, 2.24) = 4.12. Расстояние между B и D остается таким же, как и раньше.

Следовательно, обновленная матрица близости:

Clusters: AC, B, D

Proximity Matrix:
      AC     B    D
AC   0.00  7.07  6.32
B  7.07  0.00  3.16
D   6.32  3.16  0.00

Мы повторяем процесс, определяя наименьшее расстояние в матрице близости, которое теперь находится между кластерами B и D (расстояние 3,16). Мы объединяем кластеры B и D, чтобы сформировать новый кластер (BD), и обновляем матрицу близости:

Clusters: AC, BD

Proximity Matrix:
       AC     BD
A   0.00  7.07
BCD 7.07  0.00

На последнем этапе кластеры BD и AC (расстояние 7,07) объединяются в «универсальный» кластер (ABCD), который содержит все четыре точки данных.

5. Генерация дендрограммы. Теперь мы можем создать дендрограмму для представления иерархии кластеров. Дендрограмма показывает отношения между кластерами на каждом уровне иерархии. Листья дендрограммы представляют собой «одноточечные» кластеры, а корень представляет «вселенный» кластер, содержащий все точки данных. Дендрограмма для этого примера выглядит так:

                    A    B    C    D
                     \   |   /  
                      \  |  /   
                       \ | /    
                        \|/     
                         AC    
                       /  \     
                      /    \    
                     /      \   
                    /        \  
                  BD         |  
                 /  \        |  
                /    \       |  
               /      \      |  
              /        \     |  
             /          \    |  
            /            \   |  
          ABCD             \  
                             \  
                              \  
                           Euc. Dist.  
                         Comp. Linkage

🐍 С точки зрения Python код будет выглядеть так:

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

# Define the data points
X = np.array([[2, 3], [7, 5], [0, 4], [6, 2]])

# Define the distance metric and linkage method
dist_metric = 'euclidean'
linkage_method = 'complete'

# Perform hierarchical clustering
Z = linkage(X, method=linkage_method, metric=dist_metric)

# Plot the dendrogram
plt.figure(figsize=(8, 6))
dendrogram(Z, labels=['A', 'B', 'C', 'D'])
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('Data Points')
plt.ylabel('Distance')
plt.show()

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

6. Определение количества кластеров. Дендрограммы также важны, поскольку они помогают определить оптимальное количество кластеров в наборе данных. Это делается:

  • поиск самого длинного вертикального расстояния в дендрограмме, которое не пересекает ни один из других кластеров.
  • провести горизонтальную линию вдоль этой линии. Затем количество кластеров определяется путем подсчета количества вертикальных ветвей, пересекающих горизонтальную линию.
# Add a horizontal line to identify the optimal number of clusters
plt.axhline(y=6, color='gray', linestyle='--')

В этом случае горизонтальная линия рисуется на высоте 7, как указано командой plt.axhline(y=6) в коде. Эта линия разделяет дендрограмму на два отдельных кластера, первый кластер содержит точки данных A, C, а второй кластер содержит точки данных B, D.

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

🔍 Координата Y

Давайте подробнее рассмотрим координату y. Координата y линии представляет собой расстояние между кластерами, на котором они должны быть объединены, чтобы сформировать новый кластер. Это расстояние может быть определено исходя из характеристик данных и целей анализа.

В данном случае в качестве координаты y горизонтальной линии было выбрано значение 6. Это значение попадает в диапазон расстояний между кластерами, показанных на дендрограмме, который находится между 3,16 и 7,07. Значение 6 было выбрано потому, что оно визуально разделяет основные ветви дендрограммы (самые длинные вертикальные расстояния, которые не пересекают ни один из других кластеров) на два отдельных кластера. Это значение было выбрано, чтобы обеспечить четкое и интерпретируемое решение кластеризации, сохраняя при этом некоторый уровень детализации результатов кластеризации.

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

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

Преимущества

Иерархическая кластеризация имеет ряд преимуществ по сравнению с другими алгоритмами кластеризации. Во-первых, он может обрабатывать данные любого типа, включая категориальные, непрерывные и двоичные данные. Во-вторых, по сравнению с другими алгоритмами кластеризации, такими как К-средние и гауссовские смешанные модели (GMM), иерархическая кластеризация имеет ряд преимуществ. В то время как K-средние и GMM требуют предварительного знания количества кластеров, иерархическая кластеризация может определять количество кластеров автоматически. Кроме того, K-средние и GMM предполагают, что данные распределены нормально, в то время как иерархическая кластеризация может обрабатывать любой тип распределения данных. Наконец, иерархическая кластеризация создает дендрограмму, которая обеспечивает визуальное представление структуры кластеризации, что невозможно с K-средними и GMM.

Ограничения

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

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

🦊Если вы хотите узнать больше о кластеризации в неконтролируемом обучении, вам может быть интересно прочитать мою другую статью «Методы кластеризации 101: Введение в неконтролируемые методы обучения». В этом руководстве представлен всесторонний обзор. различных методов кластеризации, включая иерархическую кластеризацию, кластеризацию на основе плотности и кластеризацию на основе моделей, и обсуждают их преимущества и недостатки. В нем также рассматриваются такие темы, как оценка и выбор кластера, и приводятся примеры приложений кластеризации в различных областях.

🦊Я также приглашаю вас ознакомиться с моими руководствами по контролируемому и неконтролируемому обучению, которые можно найти в следующих списках тем: Темы по контролируемому обучению, Темы по неконтролируемому обучению, и Общие темы машинного обучения.