Привет, Хабр)

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

Поехали!

Кстати, я веду телеграм-канал по ML, в котором описываю интересные фреймворки, библиотеки, open-source инструменты и не только
Вероятно, там вы сможете найти что-то полезное для себя, так что welcome)

TL;DR

Немного о DBSCAN

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

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

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

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

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

• найти новые точки в -окрестности каждой точки и определить основные точки с более чем соседями.

• найти связные компоненты основных точек на графе соседей, игнорируя все неосновные точки.

• назначить каждую неосновную точку ближайшему кластеру, если кластер является -соседним, в противном случае считаем точку шумом.

Вот так можно использовать 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 автоматически определяет выбросы, что довольно здорово.

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

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

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

Плюсы DBSCAN

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

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

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

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

Проблемы DBSCAN

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

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

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

Немного об 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:

1. Устойчивость к шуму (впрочем как и у DBSCAN): OPTICS способен обрабатывать данные с шумом и выбросами.

2. Способность обнаруживать кластеры любой формы

3. Не требует заранее заданного числа кластеров

Проблемы OPTICS:

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

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

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

2. Биоинформатика: OPTICS применяется в биоинформатике для кластеризации геномных данных, выявления генных паттернов и классификации биологических образцов.

3. Медицинская диагностика: 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()

И давайте возьмём для начала , , потом поменяем.

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

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

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

Полезные ссылки, что почитать/посмотреть

• Описание алгоритма DBSCAN от Sci-Kit Learn

• Описание алгоритма OPTICS от Sci-Kit Learn

• Наглядная визуализация DBSCAN

Что ж, надеюсь, статья была полезной)

Кстати, я веду телеграм-канал по ML, в котором описываю интересные фреймворки, библиотеки, open-source инструменты и не только
Вероятно, там вы сможете найти что-то полезное для себя, так что welcome)