Занятие 9

Лабораторная 9

In [ ]:
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.datasets import make_circles

from sklearn.cluster import AgglomerativeClustering
from sklearn.cluster import KMeans
from sklearn.cluster import DBSCAN

from sklearn.metrics import silhouette_score

1.1 Постановка задачи кластеризации

Дано:

$X$ - пространство объектов

$X^l$ - обучающая выборка

$\rho: X * X -> [0;\infty)$ - функция расстояния между объектами

Найти:

$Y$ - множество кластеров

$a : X -> Y$ - алгоритм кластеризации

При этом кластеры должны иметь следующии свойства:

  • объекты одного кластера должны быть похожи
  • объекты разных кластеров должны отличаться

Задача кластеризация — это задача обучения без учителя. В данной задаче у нас нет обучающей выборки и нет ответов(классов).

1.2 Проблема задачи кластеризации

Рассмотрим простой пример. У нас есть выборка из 300 экземпляров. Сколько здесь кластеров? Мы легко можем увидеть, что здесь присутствует 4 кластера.

In [ ]:
# Генерация случайных данных
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.30, random_state=0)

# Визуализация результатов
plt.scatter(X[:, 0], X[:, 1])
plt.show()

Рассмотрим более сложный пример. Сколько здесь кластеров? Возможно здесь 2, 3, 5 кластеров, а может быть ещё больше?.

In [ ]:
# Генерация случайных данных
X, _ = make_blobs(n_samples=300, centers=5, cluster_std=1.0, random_state=0)

# Визуализация результатов
plt.scatter(X[:, 0], X[:, 1])
plt.show()

Рассмотрим ещё один пример. Сколько здесь кластеров? Здесь вообще есть кластеры?

In [ ]:
# Генерация случайных данных
X, _ = make_blobs(n_samples=300, centers=6, cluster_std=2, random_state=0)

# Визуализация результатов
plt.scatter(X[:, 0], X[:, 1])
plt.show()

Данные примеры показывают одну из проблем задачи классификации - решение задачи кластеризации неоднозначно. Это связано с рядом причин:

  1. Количество кластеров неизвестно.
  2. Результат кластеризации сильно зависит от выбранной метрики.
  3. Нет единого критерия оценки качества кластеризации.
  4. Существует большое разнообразие методов кластеризации, не все из которых имеют строгое теоретическое обоснование.

1.3 Цели задачи кластеризации

  1. Упрошение данных: Кластеризация может помочь разбить данные на несколько кластеров, что позволит работать с каждым кластером по отдельности.

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

  3. Сжатие данных: Кластеризация может использоваться для уменьшения размерности данных путем замены экземпляров кластеров на их центры.

  4. Построение иерархии: С помощью кластеризации можно построить иерархию данных.

Существует несколько методов решения задачи кластеризации:

  1. K-средних (K-means): Этот метод разбивает данные на заранее заданное количество кластеров (K) и минимизирует среднее расстояние между объектами и их центрами в каждом кластере.
  2. Иерархическая кластеризация: Этот метод строит иерархию кластеров, начиная с того, что каждый объект начинает как отдельный кластер, и затем объединяет их постепенно в более крупные кластеры.
  3. DBSCAN: Этот метод основан на плотности данных и способен обнаруживать кластеры произвольной формы.

2.1 Метод K-средних

Процесс работы метода K-средних можно описать следующим образом:

  1. Инициализация центров: Сначала выбираются K случайных объектов из набора данных в качестве центра каждого кластера. Это означает, что мы предполагаем наличие K кластеров.

  2. Присвоение объектов к ближайшим центрам: Каждый объект назначается к одному из K кластеров на основе ближайшего расстояния до центра кластера.

  3. Пересчет центров: Для каждого кластера вычисляется новый центр.

  4. Повторение шагов 2 и 3: Шаги 2 и 3 повторяются до тех пор пока центры кластеров не перестанут изменяться или будут меняться незначительно.

  5. Конец: По завершении работы алгоритма каждый объект назначен к одному из K кластеров.

Рассмотрим пример работы данного алгоритма.

In [ ]:
# Наши данные
X, _ = make_blobs(n_samples=300, centers=3, cluster_std=1.0, random_state=0)

# Инициализация центров случайным образом
k = 3
np.random.seed(0)
centroids = X[np.random.choice(X.shape[0], k, replace=False)]

# Алгоритм
max_iterations = 10
for _ in range(max_iterations):
    # Шаг 1: Присвоение объектов к ближайшим центроидам
    distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))
    labels = np.argmin(distances, axis=0)

    # Визуализация текущих кластеров
    plt.figure()
    plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='plasma', s=50, alpha=0.5)
    plt.scatter(centroids[:, 0], centroids[:, 1], c='black', s=200, alpha=0.5)
    plt.title('Итерация {}'.format(_))
    plt.show()

    # Шаг 3: Пересчет центров
    new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])
    centroids = new_centroids

# Шаг 5
plt.figure()
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='plasma', s=50, alpha=0.5)
plt.scatter(centroids[:, 0], centroids[:, 1], c='black', s=200, alpha=0.5, label='центры')
plt.legend()
plt.title('Финальные результаты')
plt.show()

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

  1. Как выбрать начальные центры?
  2. Какую метрику использовать?

Ответы:

  1. Центры нужно выбирать случайным образом из объектов выборки, однако нужно стараться сделать так, чтобы расстояние между случайными объектами(начальными центрами) было большим.
  2. K-Means работает с Евклидовой метрикой.

2.2 метод K-средних в scikit-learn

Конечно же данный метод реализован в scikit-learn.

In [ ]:
# Наши данные
X, _ = make_blobs(n_samples=300, centers=3, cluster_std=1.0, random_state=0)

# Применение метода K-средних
kmeans = KMeans(n_clusters=3, random_state=42)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)

# Визуализация результатов
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')
centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=200, alpha=0.5)
plt.show()

Некоторые из гиперпараметров:

  1. n_clusters: количество кластеров
  2. init: метод инициализации начальных центров кластеров (например, "k-means++" или "random").
  3. n_init: количество запусков алгоритма с разными начальными центрами (по умолчанию 10).
  4. max_iter: максимальное количество итераций алгоритма в одном запуске (по умолчанию 300).
  5. tol: критерий остановки - минимальное изменение суммы квадратов в выбранных центрах, при котором алгоритм продолжает итерации.

3.1 Иерархическая кластеризация

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

  1. агломеративный (снизу вверх)

  2. дивизивный (сверху вниз)

Иерархическая кластеризация работает следующим образом:

  1. Создаём столько кластеров, сколько у нас объектов в выборке
  2. Повторяем итеративно слияние двух ближайших кластеров, пока не выполнится критерий останова.

Тут может возникнуть 2 вопроса:

  1. Как мы определяем расстояние между двумя кластерами?
  2. Что является критерием останова?

Ответы:

  1. Определяем как среднее расстояние между объектами кластеров, минимальное расстояние или максимальное.
  2. Критерием останова может быть: число кластеров или более сложные эвристики.

3.2 Иерархическая кластеризация в scikit-learn

Конечно же данный метод реализован в scikit-learn.

In [ ]:
# Генерация синтетических данных
X, _ = make_blobs(n_samples=30, centers=3, cluster_std=0.4, random_state=0)

# Применение иерархической кластеризации
agg_clustering = AgglomerativeClustering(n_clusters=3)
assignment = agg_clustering.fit_predict(X)

# Визуализация результатов
plt.scatter(X[:, 0], X[:, 1], c=assignment, s=50, cmap='viridis')
plt.show()

Кроме того в контексте иерархической кластеризации у нас есть возможность построить Дендрограмму.

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

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

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

In [ ]:
# Генерация синтетических данных
X, _ = make_blobs(n_samples=30, centers=3, cluster_std=0.4, random_state=0)

# Построение матрицы объединения
linked = linkage(X, 'single')

# Визуализация дендрограммы
plt.figure(figsize=(10, 7))
dendrogram(linked,
            orientation='top',
            distance_sort='descending',
            show_leaf_counts=True)
plt.show()

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

4.1 DBSCAN (Density-based spatial clustering of applications with noise)

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) - метод кластеризации, который может обнаруживать кластеры произвольной формы. Он может обрабатывать шум и не требует заранее заданного числа кластеров.

Все объекты(точки) можно разделить на три типа:

  • корневые - точки в окрестности которых есть как минимум некоторое число $N$ точек.
  • граничные - точки в окрестности корневой
  • шумовые - не корневые и не граничные точки
  1. Корневые точки, имеющие общую окрестность, соединяются ребрами.
  2. Таким образом получается граф, в котором выделяются компоненты связности.
  3. Граничная точка относится к кластеру, в котором содержится наиболее близкая корневая точка для данной граничной точки.
  4. Шумовые точки отбрасываются.

4.2 DBSCAN в scikit-learn

In [ ]:
# Генерация синтетических данных
X, _ = make_blobs(n_samples=300, centers=3, cluster_std=0.6, random_state=0)

# Применение DBSCAN
dbscan = DBSCAN()
clusters = dbscan.fit_predict(X)

# Визуализация результатов
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='plasma')
plt.show()

Можно наблюдать, что наш алгоритм выделил три кластера и шумовые точки(выделенные синим).

Некоторые из гиперпараметров:

  1. eps: радиус окрестности вокруг каждой точки.
  2. min_samples: минимальное количество точек, которые должны находиться в радиусе eps, чтобы точка считалась корневой.

5. Оценка качества кластеризации

Существует несколько оценок качества кластеризации:

  1. Среднее внутрикластерное растояние - сумма расстояний между точками из одного и того же кластера делится на количество пар точек, принадлежащих к одному кластеру.

  2. Среднее межкластерное расстояние - среднее расстояние между кластерами.

Очевидно, что чем ниже значение 1, тем лучше. Чем выше значение 2 тем также лучше.

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

Значение silhouette score находится в диапазоне от -1 до 1. Высокое значение silhouette score указывает на то, что объекты хорошо согласованы с их собственными кластерами и плохо согласованы с соседними кластерами. Значение близкое к 1 указывает на четкое разделение кластеров, в то время как значение близкое к -1 указывает на перекрытие кластеризации.

Формула для вычисления silhouette score для каждого объекта i выглядит следующим образом:

$s(i) = \frac{b(i) - a(i)}{\max{\{a(i), b(i)\}}}$

  • $a(i)$ - среднее расстояние от объекта i до всех остальных точек в том же кластере
  • $b(i)$ - минимальное среднее расстояние от объекта i до всех точек в любом другом кластере
In [ ]:
# Генерируем синтетические данные
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# Проводим кластеризацию
kmeans = KMeans(n_clusters=4, random_state=10)
labels = kmeans.fit_predict(X)

# Вычисляем silhouette score
silhouette_avg = silhouette_score(X, labels)
print("Silhouette Score:", silhouette_avg)

Silhouette Score: 0.5933677279312303

Задача 1(2,5 балла)

  1. Для заданных данных произведите кластеризацию с помощью Kmeans на 1,2 ... 12 кластеров.
  2. Постройте график зависимости оценки силуэта от числа кластеров.
  3. Найдите набор гиперпараметров n_clusters, tol, init при котором достигается максимум оценки силуэта.
In [ ]:
# Генерируем синтетические данные
X, _ = make_blobs(n_samples=1000, centers=6, cluster_std=0.80, random_state=0)
In [ ]:

Задача 2(2,5 балла)

  1. Для заданных данных произведите кластеризацию с помощью иерархической кластеризация на 1,2 ... 12 кластеров.
  2. Постройте график зависимости оценки силуэта от числа кластеров.
In [ ]:
# Генерируем синтетические данные
X, _ = make_blobs(n_samples=1000, centers=6, cluster_std=0.80, random_state=0)
In [ ]:

Задача 3(2,5 балла)

  1. Для заданных данных произведите кластеризацию с помощью DBSCAN.
  2. Найдите набор гиперпараметров eps, min_samples при котором достигается максимум оценки силуэта.
In [ ]:
# Генерируем синтетические данные
X, _ = make_blobs(n_samples=1000, centers=6, cluster_std=0.80, random_state=0)
In [ ]:

Задача 4(2,5 балла)

Что лучше работает на данном датасете? Алгоритм Kmeans или DBSCAN?

In [ ]:
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons

# Генерируем синтетические данные с двумя полумесяцами
X, _ = make_circles(n_samples=400, factor=0.5, noise=0.05, random_state=42)

# Визуализируем данные
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c='black', marker='o', edgecolors='k')
plt.title('Синтетический набор данных')
plt.xlabel('Признак 1')
plt.ylabel('Признак 2')
plt.show()
In [ ]: