Введение
Иерархическая кластеризация - это еще один алгоритм машинного обучения без учителя, который используется для группировки немаркированных наборов данных в кластер и также известен как иерархический кластерный анализ или HCA.
В этом алгоритме мы развиваем иерархию кластеров в виде дерева, и эта древовидная структура известна как дендрограмма. Иногда результаты кластеризации K-средних и иерархической кластеризации могут выглядеть одинаково, но оба они различаются в зависимости от того, как они работают. Поскольку нет необходимости заранее определять количество кластеров, как мы это делали в алгоритме K-средних.
Метод иерархической кластеризации имеет два подхода:
- Агломеративный. Агломеративный подход - это восходящий подход, при котором алгоритм начинается с принятия всех точек данных как отдельных кластеров и их объединения до тех пор, пока не останется один кластер.
- Divisive: алгоритм разделения - это противоположность алгоритму агломерации, поскольку это нисходящий подход.
Агломеративная иерархическая кластеризация
Алгоритм агломеративной иерархической кластеризации является популярным примером HCA. Чтобы сгруппировать наборы данных в кластеры, используется восходящий подход. Это означает, что этот алгоритм вначале рассматривает каждый набор данных как единый кластер, а затем начинает объединять вместе ближайшую пару кластеров. Это происходит до тех пор, пока все кластеры не будут объединены в один кластер, содержащий все наборы данных.
Эта иерархия кластеров представлена в виде дендрограммы.
Как работает агломеративная иерархическая кластеризация?
Шаг 1. Создайте каждую точку данных как единый кластер. Допустим, имеется N точек данных, поэтому количество кластеров также будет N.
Шаг 2: возьмите две ближайшие точки данных или кластера и объедините их, чтобы сформировать один кластер. Итак, теперь будет N-1 кластеров.
Шаг 3: Снова возьмите два ближайших кластера и объедините их вместе, чтобы сформировать один кластер. Будет N-2 кластера.
Шаг 4: Повторяйте шаг 3, пока не останется только один кластер. Итак, мы получим следующие кластеры. Обратите внимание на изображения ниже:
Шаг 5: Как только все кластеры объединены в один большой кластер, разработайте дендрограмму, чтобы разделить кластеры в соответствии с проблемой.
Измерьте расстояние между двумя кластерами
Как мы видели, самое близкое расстояние между двумя кластерами имеет решающее значение для иерархической кластеризации. Существуют различные способы вычисления расстояния между двумя кластерами, и эти способы определяют правило кластеризации. Эти меры называются методами связывания. Некоторые из популярных методов связывания приведены ниже:
Одинарное соединение: это кратчайшее расстояние между ближайшими точками кластеров. Рассмотрим изображение ниже:
Полная связь: это наибольшее расстояние между двумя точками двух разных кластеров. Это один из популярных методов связывания, поскольку он формирует более плотные кластеры, чем одинарное соединение.
Средняя связь. Это метод связи, при котором расстояние между каждой парой наборов данных складывается и затем делится на общее количество наборов данных для расчета среднего расстояния между двумя кластерами. Это также один из самых популярных методов связи.
Привязка к центроиду: это метод связи, при котором вычисляется расстояние между центроидом кластеров. Рассмотрим изображение ниже:
Работа дендрограммы в иерархической кластеризации
Дендрограмма представляет собой древовидную структуру, которая в основном используется для хранения каждого шага в виде памяти, которую выполняет алгоритм HC. На графике дендрограммы ось Y показывает евклидовы расстояния между точками данных, а ось X показывает все точки данных данного набора данных.
Работу дендрограммы можно пояснить с помощью приведенной ниже диаграммы:
На приведенной выше диаграмме левая часть показывает, как кластеры создаются в агломеративной кластеризации, а правая часть показывает соответствующую дендрограмму.
- Как мы обсуждали выше, во-первых, точки данных P2 и P3 объединяются вместе и образуют кластер, соответственно создается дендрограмма, которая соединяет P2 и P3 прямоугольной формой. Высота определяется в соответствии с евклидовым расстоянием между точками данных.
- На следующем этапе P5 и P6 образуют кластер, и создается соответствующая дендрограмма. Это выше, чем в предыдущем случае, так как евклидово расстояние между точками P5 и P6 немного больше, чем между точками P2 и P3.
- Опять же, создаются две новые дендрограммы, которые объединяют P1, P2 и P3 в одной дендрограмме и P4, P5 и P6 в другой дендрограмме.
- Наконец, создается финальная дендрограмма, которая объединяет все точки данных вместе.
Приступим к реализации использования Python в коллаборации Google.
Импорт библиотек
import pandas as pd
import numpy as np
from google.colab import files
uploaded = files.upload()Загрузить набор данных
import io
train_data = pd.read_csv(io.StringIO(uploaded['Mall_Customers.csv'].decode('utf-8')))Отображение первых 5 записей из набора данных
Определите значения X
Оценка годового дохода и расходов.
X= train_data.iloc[:,3:].values
X
Поиск оптимального количества кластеров с помощью дендрограммы
Теперь найдем оптимальное количество кластеров с помощью дендрограммы для нашей модели. Для этого мы собираемся использовать библиотеку scipy, поскольку она предоставляет функцию, которая будет напрямую возвращать дендрограмму для нашего кода.
from matplotlib import pyplot as mtp
import scipy.cluster.hierarchy as shc
dendro = shc.dendrogram(shc.linkage(X, method="ward"))
mtp.title("Dendrogram Plot")
mtp.ylabel("Euclidean Distances")
mtp.xlabel("Customers")
mtp.show()
Используя эту дендрограмму, мы теперь определим оптимальное количество кластеров для нашей модели. Для этого мы найдем максимальное расстояние по вертикали, которое не пересекает горизонтальную полосу. Итак, оптимальное количество кластеров будет 5, и мы обучим модель на следующем шаге, используя то же самое.
Применение иерархической модели кластеризации
from sklearn.cluster import AgglomerativeClustering
hc= AgglomerativeClustering(n_clusters=5, affinity='euclidean', linkage='ward')
y_pred= hc.fit_predict(X)
y_predКластеризация принимает следующие параметры:
- n_clusters = 5: определяет количество кластеров, и мы взяли здесь 5, потому что это оптимальное количество кластеров.
- affinity = ’euclidean’: это показатель, используемый для вычисления связи.
- linkage = ’ward’: он определяет критерии связи, здесь мы использовали связь «ward». Этот метод является популярным методом связывания, который мы уже использовали для создания дендрограммы. Это уменьшает дисперсию в каждом кластере.
Визуализация
mtp.scatter(X[y_pred == 0, 0], X[y_pred == 0, 1], s = 100, c = 'blue', label = 'Cluster 1')
mtp.scatter(X[y_pred == 1, 0], X[y_pred == 1, 1], s = 100, c = 'green', label = 'Cluster 2')
mtp.scatter(X[y_pred == 2, 0], X[y_pred == 2, 1], s = 100, c = 'red', label = 'Cluster 3')
mtp.scatter(X[y_pred == 3, 0], X[y_pred == 3, 1], s = 100, c = 'cyan', label = 'Cluster 4')
mtp.scatter(X[y_pred == 4, 0], X[y_pred == 4, 1], s = 100, c = 'magenta', label = 'Cluster 5')
mtp.title('Clusters of customers')
mtp.xlabel('Annual Income (k$)')
mtp.ylabel('Spending Score (1-100)')
mtp.legend()
mtp.show()
Кластеризация DBSCAN
По сути, все методы кластеризации используют один и тот же подход, то есть сначала мы вычисляем сходства, а затем используем его для кластеризации точек данных в группы или пакеты. Здесь мы сосредоточимся на методе кластеризации приложений на основе пространственной плотности с шумом (DBSCAN).
Кластеризация на основе плотности относится к неконтролируемым методам обучения, которые идентифицируют отличительные группы / кластеры в данных, основываясь на идее, что кластер в пространстве данных представляет собой непрерывную область с высокой плотностью точек, отделенную от других таких кластеров смежными областями с низкой плотностью точек. .
Пространственная кластеризация приложений с шумом на основе плотности (DBSCAN) - это базовый алгоритм кластеризации на основе плотности. Он может обнаруживать кластеры разных форм и размеров из большого количества данных, содержащих шум и выбросы.
Параметры алгоритма
Алгоритм DBSCAN использует два параметра:
- minPts: минимальное количество точек (порог), сгруппированных вместе, чтобы область считалась плотной.
- eps (ε): мера расстояния, которая будет использоваться для определения местоположения точек в окрестности любой точки.
Эти параметры можно понять, если мы исследуем две концепции, называемые плотностью достижимости и плотностью связи.
Достижимость с точки зрения плотности определяет точку, которую можно достичь с другой стороны, если она находится на определенном расстоянии (eps) от нее.
Связность, с другой стороны, включает в себя цепочный подход на основе транзитивности для определения того, находятся ли точки в определенном кластере. Например, точки p и q могут быть соединены, если p- ›r-› s- ›t-› q, где a- ›b означает, что b находится рядом с a.
После завершения кластеризации DBSCAN есть три типа точек:
- Ядро - это точка, имеющая не менее m точек на расстоянии n от самой себя.
- Граница - это точка, у которой есть хотя бы одна центральная точка на расстоянии n.
- Шум - это точка, которая не является ни ядром, ни границей. И он имеет менее m точек на расстоянии n от себя.
Как это работает?
- Выберите произвольную точку данных p в качестве вашей первой точки.
- Отметьте p как посещенное.
- Извлеките все точки, присутствующие в его окрестности (до расстояния eps от точки), и назовите его набором nb
- Если nb ›= minPts, то
a. Считайте p первой точкой нового кластера
b. Считайте все точки в пределах расстояния eps (члены nb) как другие точки в этом кластере.
c. Повторите шаг b для всех точек в nb - иначе обозначьте p как шум
- Повторяйте шаги 1–5 до тех пор, пока не будет помечен весь набор данных, т. Е. Кластеризация не будет завершена.
После выполнения алгоритма в идеале мы должны иметь набор данных, разделенный на несколько кластеров, и некоторые точки, помеченные как шум, которые не принадлежат ни одному кластеру.
Пример
Эти моменты можно лучше объяснить с помощью визуализаций.
В этом случае minPts равно 4. Красные точки - это основные точки, потому что в их окрестностях есть как минимум 4 точки с радиусом eps. Эта область показана на рисунке кружками. Желтые точки - это пограничные точки, потому что они достижимы из центральной точки и имеют менее 4 точек в пределах своего окружения. Достижимость означает нахождение в непосредственной близости от основной точки. Точки B и C имеют две точки (включая саму точку) в пределах их окрестности (т. Е. Окружающая область с радиусом eps). Наконец, N является выбросом, потому что это не основная точка и не может быть достигнута из базовой точки.
Реализация с использованием Python
Импортировать библиотеки
Copyimport numpy as np
import matplotlib.pyplot as plt
from sklearn import metrics
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN
Применение алгоритма DBSCAN
CopyX, y = make_blobs(n_samples=500,n_features=2,
centers=4, cluster_std=1,
center_box=(-10.0, 10.0),
shuffle=True, random_state=1)
X = StandardScaler().fit_transform(X)
y_pred = DBSCAN(eps=0.3, min_samples=30).fit_predict(X)
plt.scatter(X[:,0], X[:,1], c=y_pred)
print('Number of clusters: {}'.format(len(set(y_pred[np.where(y_pred != -1)]))))
print('Homogeneity: {}'.format(metrics.homogeneity_score(y, y_pred)))
Понятно, что 4 кластера обнаружены как положено. Черные точки - это выбросы или шум согласно модели DBSCAN. Поскольку анализируемый набор данных был создан нами, и мы знаем основную правду о нем, мы можем использовать такие показатели, как оценка однородности (проверка того, имеет ли каждый кластер только члены одного класса) и оценка полноты (проверка того, всем ли членам класса назначен один и тот же кластер).
Надеюсь, вы получите лучшее представление об иерархической кластеризации и DBSCAN.
Спасибо за чтение, надеюсь, вам понравилось!
Ссылка
