СРАВНЕНИЕ АЛГОРИТМОВ КЛАСТЕРИЗАЦИИ DBSCAN и OPTICS - UPROGER

Поговорим сегодня о 2 популярных алгоритмах кластеризации — DBSCAN и OPTICS, посмотрим их особенности и сравним

Поехали!

TL;DR

Для самых нетерпеливых

DBSCAN	OPTICS
Время выполнения DBSCAN в худшем случае составляет , где — количество точек данных. Однако при использовании индексов пространственного поиска (например, KD-деревьев или R-деревьев) производительность может быть улучшена до в среднем случае.	Оптимизированная версия OPTICS также имеет временную сложность при использовании индексов пространственного поиска. Однако из-за необходимости построения упорядоченного представления данных (reachability plot) алгоритм может быть медленнее в реальных сценариях.
DBSCAN проще в реализации. Он требует настройки двух параметров: $\varepsilon$ (радиус поиска соседей) и (минимальное количество точек для формирования кластера).	OPTICS сложнее в реализации, так как включает дополнительный шаг упорядочивания точек по достижимости (reachability). Он также использует параметры $\varepsilon$ и , но результат не так чувствителен к выбору $\varepsilon$ , что упрощает настройку.
DBSCAN хорошо подходит для кластеризации данных с четко определенными плотными областями и шумом. Широко используется в различных областях, таких как географические информационные системы (ГИС) и анализ социальных сетей.	OPTICS предпочтителен при необходимости анализа кластерной структуры данных на различных масштабах плотности. Подходит для исследования данных, где кластеры имеют различные плотности.
Способен распознавать кластеры произвольной формы и размерности. Однако может не справляться с кластерами переменной плотности, так как использует фиксированное значение $\varepsilon$ .	Более гибок в отношении кластеров переменной плотности. За счет упорядочения точек по достижимости алгоритм может выявлять кластеры на разных уровнях плотности.
Эффективно идентифицирует и отбрасывает шум и выбросы.	Также эффективно справляется с шумом, но благодаря дополнительной информации о плотности позволяет лучше различать шум и кластеры.
Требует настройки двух параметров, которые могут существенно влиять на результаты. Неправильный выбор $\varepsilon$ может привести к объединению или разделению кластеров.	Менее чувствителен к параметру $\varepsilon$ ε. Основной параметр оказывает влияние на результаты, но не так критично, как в DBSCAN.
Результаты могут быть непосредственно визуализированы как кластеры и шумовые точки.	Результаты визуализируются с помощью графика достижимости (reachability plot), который может быть использован для определения кластера на различных уровнях плотности.

Немного о DBSCAN

Ну, DBSCAN в особом в представлении не нуждается, всё-таки один из самых популярных алгоритмов кластеризации. Поэтому по минимуму теории.

СРАВНЕНИЕ АЛГОРИТМОВ КЛАСТЕРИЗАЦИИ DBSCAN и OPTICS

DBSCAN (Density-based spatial clustering of applications with noise, плотностной алгоритм пространственной кластеризации с присутствием шума), как следует из названия, оперирует плотностью данных. На вход он просит матрицу близости точек и два параметра — радиус $\varepsilon$ -окрестности и количество соседей .

Эпсилон-окрестность для любого вектора в метрическом признаковом пространстве определяется как множество точек, отстоящих от не более чем на $\varepsilon$ :

$U_\varepsilon (x) = { u \in U : \rho(x, u) \le \varepsilon},$

где $\rho(x, u)$ — выбранная метрика (например, евклидовое расстояние).

В общих чертах, алгоритм DBSCAN можно представить как последовательность следующих этапов:

найти новые точки в $\varepsilon$ -окрестности каждой точки и определить основные точки с более чем соседями.
найти связные компоненты основных точек на графе соседей, игнорируя все неосновные точки.
назначить каждую неосновную точку ближайшему кластеру, если кластер является $\varepsilon$ -соседним, в противном случае считаем точку шумом.

Вот так можно использовать DBSCAN из Sci-Kit Learn + с интерактивными ползунками, работает в Colab’е (в Jupyter Notebook какие-то траблы с этим, если кто знает — please, help):

%matplotlib inline
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

data = pd.read_csv('распределение-2.csv', header=None)

# нормализуем данные
scaler = StandardScaler()
scaled_data = scaler.fit_transform(data)

from ipywidgets import interact
@interact(epsilon=(0, 1.0, 0.05), min_samples=(5, 10, 1))
def plot_dbscan(epsilon, min_samples):
    # epsilon - радиус окрестности
    # min_samples - минимальное количество точек в окрестности для формирования кластера
    
    dbscan = DBSCAN(eps=epsilon, min_samples=min_samples)
    clusters = dbscan.fit_predict(scaled_data)

    plt.figure(figsize=(6, 4), dpi=150)  # , dpi=300
    plt.scatter(data[0], data[1], c=clusters, cmap='viridis', s=40, alpha=1, edgecolors='k')
    plt.title('DBSCAN')
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.show()

С использованием DBSCAN в Julia и R особых проблем тоже не возникает —

— Julia:

using ClusterAnalysis, DataFrames, CSV, BenchmarkTools
using Plots, StatsPlots

df = CSV.read("распределение.csv", DataFrame);
X = df[:,1:2];
y = df[:,end];

ϵ = 0.15;
min_pts = 7;

m = dbscan(X, ϵ, min_pts);

scatter(X[:,1], X[:,2], zcolor=m.labels, 
        leg=false, 
        title="DBSCAN\n(ϵ=$(ϵ), minPts=$(min_pts))")

— R:

# install.packages("ggplot2")
# install.packages("dbscan")
library(ggplot2)
library(dbscan)

data <- read.csv("распределение-2.csv", header=FALSE)  # Предполагается, что файл называется "your_file.csv"

# преобразуем в матрицу
points_matrix <- as.matrix(data)

dbscan_result <- dbscan(points_matrix, eps = 0.1, minPts = 7)

clustered_data <- cbind(data, cluster=dbscan_result$cluster)
ggplot(clustered_data, aes(x=V2, y=V1, color=factor(cluster))) + geom_point() + theme_minimal()

В идеальном случае DBSCAN может иметь линейную сложность , но не стоит особо на это рассчитывать. Если не пересчитывать каждый раз точек, то ожидаемая сложность — . Худший случай (плохие данные или брутфорс-реализация) — . Наивные реализации DBSCAN любят отъедать памяти под матрицу расстояний — это явно избыточно. Многие версии DBSCAN умеют работать и с более щадящими структурами данных: sklearn и R реализации можно оптимизировать при помощи KD-tree прямо из коробки.

DBSCAN не вычисляет самостоятельно центры кластеров, однако вряд ли это проблема, особенно учитывая произвольную форму кластеров. Зато DBSCAN автоматически определяет выбросы, что довольно здорово.

Соотношение $\dfrac{m}{\varepsilon}$ , где — размерность пространства, можно интуитивно рассматривать как пороговую плотность точек данных в области пространства. Ожидаемо, что при одинаковом соотношении $\dfrac{m}{\varepsilon^n}$ , и результаты будут примерно одинаковы. Иногда это действительно так, но есть причина, почему алгоритму нужно задать два параметра, а не один. Во-первых типичное расстояние между точками в разных датасетах разное — явно задавать радиус приходится всегда. Во-вторых, играют роль неоднородности датасета. Чем больше и $\varepsilon$ , тем больше алгоритм склонен «прощать» вариации плотности в кластерах. С одной стороны, это может быть полезно: неприятно увидеть в кластере «дырки», где просто не хватило данных. С другой стороны, это вредно, когда между кластерами нет чёткой границы или шум создаёт «мост» между скоплениями. Тогда DBSCAN запросто соединит две разные группы. В балансе этих параметров и кроется сложность применения DBSCAN: реальные наборы данных содержат кластеры разной плотности с границами разной степени размытости. В условиях, когда плотность некоторых границ между кластерами больше или равна плотности каких-то обособленных кластеров, приходится чем-то жертвовать.

Существуют варианты DBSCAN, способные смягчить эту проблему. Идея состоит в подстраивании $\varepsilon$ в разных областях по ходу работы алгоритма. К сожалению, возрастает количество параметров алгоритма.

Ок, теперь давайте немного поговорим о плюсах и минусах DBSCAN.

Плюсы DBSCAN

• DBSCAN не требует указания числа кластеров в отличие, скажем, от метода k-средних

• DBSCAN может найти кластеры произвольной формы. Он может найти даже кластеры полностью окружённые (но не связанные с) другими кластерами.

• DBSCAN имеет понятие шума и устойчив к выбросам.

• DBSCAN требует лишь двух параметров ( и $\varepsilon$ ) и большей частью нечувствителен к порядку точек в датасете. Однако, точки, находящиеся на границе двух различных кластеров могут оказаться в другом кластере, если изменить порядок точек, а назначение кластеров единственно с точностью до изоморфизма.

Проблемы DBSCAN

• DBSCAN не полностью однозначен — краевые точки, которые могут быть достигнуты из более чем одного кластера, могут принадлежать любому из этих кластеров, что зависит от порядка просмотра точек (тут стоит сказать, что существует DBSCAN❋, который трактует краевые точки как шум и тем самым достигается полностью однозначный результат)

• Качество DBSCAN зависит от способа измерения расстояния. Наиболее часто используемой метрикой расстояний является евклидова метрика. В случае кластеризации данных высокой размерности эта метрика может оказаться почти бесполезной, что делает трудным делом нахождение подходящего значения $\varepsilon$ . Этот эффект, однако, присутствует в любом другом алгоритме, основанном на евклидовом расстоянии.

• DBSCAN не может хорошо разделить на кластеры наборы данных с большой разницей в плотности, поскольку не удается выбрать приемлемую для всех кластеров комбинацию и $\varepsilon$ .

Немного об OPTICS

Что ж, теперь давайте теперь переключимся на алгоритм OPTICS (Ordering Points To Identify the Clustering Structure).

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

Реализация OPTICS есть в библиотеке Sci-Kit Learn; вот как можно её импортировать и использовать:

import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import OPTICS
from sklearn.preprocessing import StandardScaler

data = pd.read_csv('распределение.csv', header=None)

# нормализуем данные
scaler = StandardScaler()
scaled_data = scaler.fit_transform(data)

min_samples = 25  # минимальное количество точек в окрестности для формирования кластера

optics = OPTICS(min_samples=min_samples)
clusters = optics.fit_predict(scaled_data)

plt.figure(figsize=(8, 6))
plt.scatter(data[0], data[1], c=clusters, cmap='viridis', s=50, alpha=1, edgecolors='k')
plt.title(f'OPTICS, {min_samples=}')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()

С R тоже проблем нет:

# install.packages("dbscan")
# install.packages("ggplot2")

library(dbscan)
library(ggplot2)

data <- read.csv("распределение.csv", header = FALSE)

mat <- as.matrix(data)

optics_result <- optics(mat, eps = 0.15, minPts = 7)  

ggplot(data, aes(x = V2, y = V1, color = "Cluster")) + 
  geom_point() + 
  theme_minimal()

Хорошо, давайте немного об особенностях OPTICS

Плюсы OPTICS:

Устойчивость к шуму (впрочем как и у DBSCAN): OPTICS способен обрабатывать данные с шумом и выбросами.
Способность обнаруживать кластеры любой формы
Не требует заранее заданного числа кластеров

Проблемы OPTICS:

Не всегда эффективен для плотных кластеров: OPTICS может иметь проблемы с эффективным обнаружением плотных кластеров, особенно если они имеют сложные формы.

А вот несколько сфер, где регулярно используется OPTICS:

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

Сравнение DBSCAN и OPTICS

Итак, пришло время сравнить DBSCAN и OPTICS

Вот DBSCAN:

import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

data = pd.read_csv('распределение.csv', header=None)

# нормализуем данные
scaler = StandardScaler()
scaled_data = scaler.fit_transform(data)

epsilon = 0.15  # радиус ε-окрестности
min_samples = 6  # минимальное количество точек в e-окрестности для формирования кластера

dbscan = DBSCAN(eps=epsilon, min_samples=min_samples)
clusters = dbscan.fit_predict(scaled_data)

plt.figure(figsize=(8, 6))
plt.scatter(data[0], data[1], c=clusters, cmap='viridis', s=50, alpha=1, edgecolors='k')
plt.title(f'DBSCAN, {epsilon=}, {min_samples=}')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()

…а вот и OPTICS:

import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import OPTICS
from sklearn.preprocessing import StandardScaler

data = pd.read_csv('распределение.csv', header=None)

# тоже нормализуем данные
scaler = StandardScaler()
scaled_data = scaler.fit_transform(data)

min_samples = 6  

optics = OPTICS(min_samples=min_samples)
clusters = optics.fit_predict(scaled_data)

plt.figure(figsize=(8, 6))
plt.scatter(data[0], data[1], c=clusters, cmap='viridis', s=50, alpha=1, edgecolors='k')
plt.title(f'OPTICS, {min_samples=}')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()

И давайте возьмём для начала $\varepsilon=0.1$ , , потом поменяем.

Что мы видим? Для данного датасета DBSCAN выделяет кластеры более логичным и понятным способов, но в кластеризации OPTICS тоже есть пара интересных моментов.
Как можно увидеть, точки вокруг главных кластеров DBSCAN безнадёжно отмечает как шум, в то время как OPTICS пытается нащупать кластеры и среди этих точек тоже.
Это одна из главных фишек OPTICS — метод способен видеть кластеры разной плотности одновременно за счёт того, что он менее чувствителен к параметру $\varepsilon$ .

Вот довольно показательный пример — и тут OPTICS тоже выделил кластер в точках, которые забраковал DBSCAN:

Ещё немного сравнения

DBSCAN	OPTICS
Время выполнения DBSCAN в худшем случае составляет , где — количество точек данных. Однако при использовании индексов пространственного поиска (например, KD-деревьев или R-деревьев) производительность может быть улучшена до в среднем случае.	Оптимизированная версия OPTICS также имеет временную сложность при использовании индексов пространственного поиска. Однако из-за необходимости построения упорядоченного представления данных (reachability plot) алгоритм может быть медленнее в реальных сценариях.
DBSCAN проще в реализации. Он требует настройки двух параметров: $\varepsilon$ (радиус поиска соседей) и (минимальное количество точек для формирования кластера).	OPTICS сложнее в реализации, так как включает дополнительный шаг упорядочивания точек по достижимости (reachability). Он также использует параметры $\varepsilon$ и , но результат не так чувствителен к выбору $\varepsilon$ , что упрощает настройку.
DBSCAN хорошо подходит для кластеризации данных с четко определенными плотными областями и шумом. Широко используется в различных областях, таких как географические информационные системы (ГИС) и анализ социальных сетей.	OPTICS предпочтителен при необходимости анализа кластерной структуры данных на различных масштабах плотности. Подходит для исследования данных, где кластеры имеют различные плотности.
Способен распознавать кластеры произвольной формы и размерности. Однако может не справляться с кластерами переменной плотности, так как использует фиксированное значение $\varepsilon$ .	Более гибок в отношении кластеров переменной плотности. За счет упорядочения точек по достижимости алгоритм может выявлять кластеры на разных уровнях плотности.
Эффективно идентифицирует и отбрасывает шум и выбросы.	Также эффективно справляется с шумом, но благодаря дополнительной информации о плотности позволяет лучше различать шум и кластеры.
Требует настройки двух параметров, которые могут существенно влиять на результаты. Неправильный выбор $\varepsilon$ может привести к объединению или разделению кластеров.	Менее чувствителен к параметру $\varepsilon$ ε. Основной параметр оказывает влияние на результаты, но не так критично, как в DBSCAN.
Результаты могут быть непосредственно визуализированы как кластеры и шумовые точки.	Результаты визуализируются с помощью графика достижимости (reachability plot), который может быть использован для определения кластера на различных уровнях плотности.