Analisi dei Cluster con DBScan

Il progetto Python, che comprende gli script mostrati in questo post, e quelli relativi alla creazione dei grafici Matplotlib e Plotly, è disponibile assieme al corso Introduzione al Machine Learning.

Dimmi di Più

Introduzione

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) è un algoritmo di clustering non supervisionato che risulta particolarmente efficace nel riconoscere cluster di forma arbitraria e nell’identificare osservazioni di rumore, ovvero punti che non appartengono a nessun gruppo ben definito.

Rispetto ad algoritmi come K-Means o Hierarchical Clustering, DBSCAN non richiede di specificare a priori il numero di cluster, e si dimostra più robusto in presenza di rumore e strutture non sferiche.

L’idea centrale di DBSCAN è quella di identificare i cluster sulla base della densità delle osservazioni nello spazio delle feature. In questo contesto, un cluster viene interpretato come una regione dello spazio in cui i punti sono sufficientemente densi, separata da altre regioni a densità inferiore.

La densità viene formalmente definita come il numero di osservazioni contenute all’interno di un intorno di raggio prefissato ($\epsilon$-vicinato) attorno a un punto. In base a questa nozione, DBSCAN è in grado di distinguere automaticamente tra punti appartenenti a cluster e punti isolati, classificati come rumore.

L’Algoritmo DBSCAN

L’algoritmo DBSCAN si basa su due parametri fondamentali, che permettono di definire formalmente il concetto di densità nello spazio dei dati: $\require{boldsymbol}$

$\boldsymbol{\epsilon}$ (epsilon):
rappresenta il raggio di vicinanza entro il quale vengono cercate le osservazioni considerate “vicine” a un punto dato. Due punti sono detti “vicini” se la distanza tra di essi è minore o uguale a $\epsilon$. L’insieme di tutti i punti entro questo raggio prende il nome di $\boldsymbol{\epsilon}$-vicinato del punto.
$\textbf{minPts}$:
indica il numero minimo di punti che devono essere presenti all’interno dell’$\epsilon$-vicinato affinché una regione dello spazio possa essere considerata sufficientemente densa.

Sulla base di questi due parametri, DBSCAN classifica ogni osservazione del dataset in una delle seguenti categorie:

Core Point:
un punto che ha almeno $\text{minPts}$ punti vicini (incluso il punto stesso), che ricadono nel raggio $\epsilon$ specificato. Un Core Point rappresenta il centro di una regione densa, e quindi la presenza di un nuovo potenziale cluster. Se indichiamo $\text{minPts} = 3$, allora un Core Point deve avere almeno 3 punti nel suo $\epsilon$-vicinato, incluso sé stesso. Quindi, in pratica, $1$ è il Core Point; $2$ sono altri punti nel suo $\epsilon$-vicinato.
Border Point:
un punto che non è un Core Point, che ha meno di $\text{minPts}$ punti nel proprio $\epsilon$-vicinato, ma che si trova nell’$\epsilon$-vicinato di almeno un Core Point.
Noise Point (Outlier ):
tutti gli altri punti che non sono Core o Border Point.

Per comprendere meglio il funzionamento dell’algoritmo DBSCAN, è utile approfondire nel dettaglio i concetti appena introdotti, e osservarne una rappresentazione grafica. Le visualizzazioni aiutano infatti a chiarire come la nozione di densità permetta di distinguere tra Core Point, Border Point e Noise Point, rendendo più intuitivo il processo di formazione dei cluster.

L’$\boldsymbol{\epsilon}$-vicinato

Dato un dataset $\mathbf{X} = \{ \mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \cdots, \mathbf{x}^{(m)} \}$, fissato un raggio $\epsilon$ (epsilon), l’$\epsilon$-vicinato ($\boldsymbol{\epsilon}$-neighborhood) di un punto $\mathbf{x}^{(i)}$ è l’insieme dei punti $\mathbf{x}^{(j)}$ la cui distanza da $\mathbf{x}^{(i)}$ è minore o uguale a $\epsilon$:

$$ \begin{align} N_\epsilon\left(\mathbf{x}^{(i)}\right) = \left\{ \mathbf{x}^{(j)} \in \mathbf{X} \mid \text{dist}\left(\mathbf{x}^{(i)}, \mathbf{x}^{(j)}\right) \leq \epsilon \right\} \label{neighborhood}\tag{1}\\[6pt] \end{align} $$

L’$\epsilon$-vicinato rappresenta quindi la zona di influenza locale di un punto, ed è alla base della definizione di densità utilizzata dall’algoritmo.

I Punti Vicini (Neighbors)

I punti appartenenti all’$\epsilon$-vicinato di $\mathbf{x}^{(i)}$ sono detti “punti vicini” (neighbors) di $\mathbf{x}^{(i)}$.

In linea generale, un punto è un neighbor se si trova a distanza minore o uguale a $\epsilon$ dal punto di riferimento scelto, che può essere qualsiasi punto del dataset.

Questa nozione è relativa al punto considerato e al valore di $\epsilon$, e non rappresenta una categoria di punti distinta all’interno di DBSCAN, a differenza dei Core Point, Border Point e Noise Point. La metrica di distanza usata, $\text{dist}$, solitamente è la distanza Euclidea:

$$ \begin{align} \text{dist}\left(\mathbf{x}^{(i)}, \mathbf{x}^{(j)}\right) & = \lVert \mathbf{x}^{(i)} - \mathbf{x}^{(j)} \rVert_2 \label{norm-1}\tag{2}\\[6pt] & = \sqrt{ \sum_{f=1}^{n}{\left(x^{(i)}_f - x^{(j)}_f\right)^2 }} \label{dist-1}\tag{3}\\[6pt] \end{align} $$

Core Point

Un punto $\mathbf{x}^{(i)}$ è definito Core Point se il suo $\epsilon$-vicinato contiene almeno $\text{minPts}$ osservazioni, incluso il punto stesso. In termini formali:

$$ \begin{align} \bigg| N_\epsilon\left(\mathbf{x}^{(i)}\right) \bigg| \ge \text{minPts} \label{neighborhood-2}\tag{4}\\[6pt] \end{align} $$

dove $\bigg| N_\epsilon\left(\mathbf{x}^{(i)}\right) \bigg|$ indica il numero di punti appartenenti all’$\epsilon$-vicinato di $\mathbf{x}^{(i)}$ :

Border Point

Un punto $\mathbf{x}^{(i)}$ è definito Border Point se non ha una densità sufficiente per essere un Core Point, ma si trova all’interno dell’$\epsilon$-vicinato di almeno un Core Point. In altre parole, un Border Point si trova ai margini di una regione densa, perchè attorno a quel punto ci sono meno punti di quelli richiesti dal parametro $\text{minPts}$:

Un Border Point da solo non soddisfa il requisito minimo di densità, ma è abbastanza vicino a un Core Point da essere incluso nel cluster. Tutti i Border Point sono neighbors di almeno un Core Point, ma non tutti i neighbors sono Border Point, perché molti neighbors possono essere Core Point a loro volta.

Formazione di un Cluster

Un punto $\mathbf{x}^{(j)}$ è direttamente raggiungibile-in-densità da un punto $\mathbf{x}^{(i)}$ se:

$\mathbf{x}^{(i)}$ è un Core Point;
$\mathbf{x}^{(j)}$ si trova nell’$\epsilon$-vicinato di $\mathbf{x}^{(i)}$.

In questo caso, $\mathbf{x}^{(i)}$ può essere considerato un punto di partenza valido per l’espansione del cluster verso $\mathbf{x}^{(j)}$ :

Un punto $\mathbf{x}^{(j)}$ è raggiungibile-in-densità da un punto $\mathbf{x}^{(i)}$ se esiste una sequenza di punti $\mathbf{x}^{(i)}, \mathbf{x}^{(k_1)}, \mathbf{x}^{(k_2)}, \cdots, \mathbf{x}^{(j)}$ tale che ogni punto della sequenza (eccetto eventualmente l’ultimo) è direttamente raggiungibile-in-densità dal precedente. In altre parole, anche se $\mathbf{x}^{(j)}$ non si trova nell’$\epsilon$-vicinato di $\mathbf{x}^{(i)}$, può comunque far parte dello stesso cluster se è collegato a $\mathbf{x}^{(i)}$ attraverso una catena di punti che parte da regioni sufficientemente dense. Tutti i punti raggiungibili-in-densità da un Core Point costituiscono un cluster:

L’Algoritmo

L’algoritmo DBSCAN funziona in questo modo:

selezioniamo casualmente un punto dati non visitato.
recuperiamo tutti i suoi punti vicini, entro la distanza $\epsilon$.
se il numero di punti vicini è maggiore o uguale a $\text{minPts}$, questo indica che il punto considerato è un nuovo Core Point, ovvero il centro di un nuovo cluster. Quindi:
1. creiamo un nuovo cluster, e lo assegnamo al punto selezionato.
2. espandiamo il cluster, aggiungendo ricorsivamente tutti i punti direttamente raggiungibili-in-densità dal punto inizialmente selezionato.
se il numero di punti vicini è inferiore a $\text{minPts}$, contrassegniamo il punto come outlier (rumore).
ripetiamo il processo per il punto non visitato successivo, fino a quando tutti i punti sono stati visitati.

Il risultato dell’algoritmo DBSCAN è un insieme di cluster, dove un cluster include i Core Point che sono vicini (cioè raggiungibili l’uno dall’altro), e tutti i Border Point di questi Core Point. La condizione necessaria per formare un cluster è la presenza di almeno un Core Point. Anche se è molto improbabile, si può avere un cluster con un solo Core Point e i suoi Border Point.

Implementazione del Modello

La Classe DBSCAN

Implementiamo l’algoritmo di cui sopra tramite l’omonima classe DBSCAN. I parametri più importanti del costruttore sono:

eps: indica la distanza massima tra due osservazioni, affinchè una possa essere considerata come nelle vicinanze dell’altra. Questo è il parametro più importante, e la scelta del suo valore deve essere appropriata per il dataset di riferimento, e la metrica di distanza usata (in questo caso, la classe implementa solo la distanza euclidea).
min_samples: indica il numero minimo di osservazioni che devono essere presenti nelle vicinanze del punto $\mathbf{x}^{(i)}$, affinchè esso possa essere considerato un Core Point (il centro di un nuovo cluster).

import numpy as np
from scipy.spatial import distance

class DBSCAN:
    """
    Perform DBSCAN clustering from vector array or distance matrix.
    DBSCAN - Density-Based Spatial Clustering of Applications with Noise.
    Finds core samples of high density and expands clusters from them.
    Good for data which contains clusters of similar density.
    """
    def __init__(self, eps=0.5, min_samples=None, metric="euclidean"):
        """
        Constructor.

        Parameters
        ----------
        eps: float, default=0.5
            The maximum distance between two samples for one to be considered as
            in the neighborhood of the other. This is not a maximum bound
            on the distances of points within a cluster.
            This is the most important DBSCAN parameter to choose appropriately
            for your data set and distance function.
        min_samples: int, default=5
            The minimum number of samples in a neighborhood for a point
            to be considered as a core point. This includes the point itself.
            If min_samples is set to a higher value, DBSCAN will find denser clusters,
            whereas if it is set to a lower value, the found clusters will be more sparse.
        metric: str, default="euclidean"
            The metric to use when calculating distance between instances in a feature array.
            Supported values are:
            "euclidean" to use the Euclidean distance.
        """
        self.eps = eps
        self.min_samples = min_samples
        self.metric = metric
        self.labels_ = None

Il Metodo Fit

Il metodo fit calcola la matrice delle distanze per ogni punto del dataset di input, e chiama il metodo __expand_cluster per far partire l’algoritmo di clustering. Quest’ultimo metodo ritorna l’array di label che indica il cluster di appartenenza di ogni osservazione del dataset:

    def fit(self, X):
        """
        Perform DBSCAN clustering from features.

        Parameters
        ----------
        X: ndarray of shape (n_examples, n_features)
            Training instances to cluster.

        Returns
        -------
        self
            This class' instance.
        """
        dist_matrix = self.__distance_matrix(X)
        cluster_id = 1  # id of the first cluster
        n_examples = X.shape[0]
        X_ids = np.arange(n_examples)
        labels = np.zeros(n_examples)

        # start the algorithm
        labels = self.__expand_cluster(X_ids, dist_matrix, cluster_id, labels, create_new_cluster=True)

        # to be compatible with Scikit-Learn, label values for valid clusters must start from 0.
        # Noisy examples are given the label -1.
        self.labels_ = labels.astype(int) - 1

        return self

    def __distance_matrix(self, X):
        """
        Compute the distance matrix for the input dataset.

        Parameters
        ----------
        X: ndarray of shape (n_examples, n_features)
            Training instances to cluster.

        Returns
        -------
        ndarray of shape (n_examples, n_examples)
            The distance matrix for the input dataset.
        """
        # a condensed distance matrix is a flat array
        # containing the upper triangular of the distance matrix
        cond_dist_matrix = distance.pdist(X, self.metric)

        # squareform converts a condensed distance matrix into a full distance matrix.
        # Distance between point i,j is stored in dist_matrix[i, j]
        dist_matrix = distance.squareform(cond_dist_matrix)
        return dist_matrix

Il Metodo Expand Cluster

Il metodo ricorsivo __expand_cluster implementa effettivamente l’algoritmo di clustering precedentemente descritto. Esso cicla su tutti gli esempi presi in considerazione, non precedentemente visitati. Per ognuno di questi, recupera tutti gli esempi vicini ad esso, entro la distanza self.eps. Se il numero di esempi vicini è maggiore o uguale a self.min_samples, vuol dire che il punto corrente è un nuovo Core Point, che identifica il centro di un nuovo cluster. Identificato tale Core Point, l’algoritmo definisce un nuovo cluster, ed inizia l’espansione dello stesso, aggiungendo ricorsivamente tutti gli esempi direttamente raggiungibile-in-densità, a partire dall’esempio inizialmente selezionato (ma senza creare nuovi cluster). Di contro, se il numero di punti vicini è inferiore a self.min_samples, il punto correntemente considerato viene contrassegna come Outlier:

    def __expand_cluster(self, X_ids, dist_matrix, cluster_id, labels, create_new_cluster):
        """
        Expand the cluster by recursively adding all directly density-reachable examples
        from the initially selected example.

        Parameters
        ----------
        X_ids: ndarray of shape (n_examples, )
            The array containing the indices of the examples to process.
        dist_matrix: ndarray of shape (n_examples, n_examples)
            The distance matrix for the input dataset.
        cluster_id: int
            the index of the current cluster.
        labels: ndarray of shape (n_examples, )
            Cluster labels.
        create_new_cluster: bool
            True to create a new cluster, false otherwise.

        Returns
        -------
        ndarray of shape (n_examples, )
            Cluster labels.
        """

        # if an example x belongs to a cluster c, the other examples that can belong
        # to the same cluster c are those that are close to x.
        # In turn, if the neighbors of x belong to the cluster c,
        # the neighbors of the neighbors may also belong to c.
        #
        # 1) select an example
        for i in X_ids:

            # skip this example if it is already visited
            if labels[i] != 0:
                continue

            # 2) retrieve all of its neighboring examples within distance ε
            neighbor_idxs = self.__find_neighbors(dist_matrix, i)

            # 3) if the number of neighboring examples is greater than,
            #    or equal to min_samples, we identified a new Core Point,
            #    that is, the center of a new cluster. Thus:
            if len(neighbor_idxs) >= self.min_samples:

                # 3.1) create a new cluster and assign it to the selected example
                labels[i] = cluster_id

                # 3.2) expand the cluster by recursively adding all directly density-reachable examples
                #      from the initially selected example (do NOT create new clusters)
                labels = self.__expand_cluster(neighbor_idxs, dist_matrix, cluster_id, labels,
                                               create_new_cluster=False)
                # create a new cluster
                if create_new_cluster:
                    cluster_id = cluster_id + 1

            # 4) if the number of neighboring points is less than minPts (min_samples),
            #    mark the point as noise
            #else:
            #    labels[i] = 0

        return labels

    def __find_neighbors(self, dist_matrix, i):
        """
        Find the indices of all the examples within distance eps from the current example.

        Parameters
        ----------
        dist_matrix: ndarray of shape (n_examples, n_examples)
            The distance matrix computed for the current dataset.
        i: int
          the index of the current example.

        Returns
        -------
        ndarray of shape (n_neighbors, )
            The indices of all the examples within distance eps from the current one.
        """
        # distances from the current example to all the other examples
        dists = dist_matrix[i]

        # return the indices of the array elements that satisfy the given condition
        return (dists <= self.eps).nonzero()[0]

Il Metodo Fit Predict

Il metodo fit_predict richiama fit, e ritorna le label che indicano il cluster di appartenenza di ogni osservazione di input:

    def fit_predict(self, X):
        """
        Compute clusters from a data or distance matrix and predict labels.

        Parameters
        ----------
        X: ndarray of shape (n_examples, n_features)
            Training instances to cluster.

        Returns
        -------
        labels: ndarray of shape (n_examples, )
            Cluster labels. Noisy samples are given the label -1.
        """
        self.fit(X)
        return self.labels_

Esempi di Utilizzo

Questa volta, come esempio, confrontiamo tra loro i risultati ottenuti dai modelli K-Means, Hierarchical e DBSCAN clustering su un paio di dataset “impegnativi”, e vediamo quale algoritmo riesce ad identificare con successo le forme come cluster separati. Come prima cosa, definiamo alcune funzioni di supporto per la generazione dei dataset:

# avoid memory leak when dealing with KMeans:
# https://stackoverflow.com/a/73445664
import os
os.environ["OMP_NUM_THREADS"] = '1'
import warnings
warnings.simplefilter(action='ignore', category=DeprecationWarning)
import numpy as np
import math
from sklearn.datasets import make_moons

def make_data(dataset_id, random_state=0):
    """Create 'moons' or 'concentric circles' clustered data."""
    # clustering parameters for "moons" and "circle" datasets;
    n_clusters = [2, 3]
    eps = [0.2, 32]
    min_samples = [5, 5]

    # 'moons' or 'concentric circles'
    if dataset_id == 0:
        X, y = make_moons(n_samples=200, noise=0.05, random_state=random_state)
    else:
        X, y = __make_circle(random_state=random_state)
    return X, y, n_clusters[dataset_id], eps[dataset_id], min_samples[dataset_id]

def __make_circle(random_state=1234):
    """Create a dataset defined by 3 concentric circles."""
    np.random.seed(random_state)

    small_circle  = __circle(100, 300, 10)
    medium_circle = __circle(300, 700, 20)
    big_circle    = __circle(500, 1000, 30)
    noise = [(np.random.randint(-600, 600),
              np.random.randint(-600, 600))
             for i in range(300)]

    # define data-points and labels
    X = np.vstack((small_circle, medium_circle, big_circle, noise))
    y = np.concatenate((
        np.full((len(small_circle),), 0),
        np.full((len(medium_circle),), 1),
        np.full((len(big_circle),), 2),
        np.full((len(noise),), 3))
    )
    return X, y

def __circle(r, n, noise=30):
    """
    Create a 2D dataset of data points arranged along a circle.
    Args:
        r     : the radius of the circle (int)
        n     : number of data-points (int)
        noise : noise coefficient (int)
    Returns:
        Array of shape (n, 2) with (x, y) coordinates.
    """
    # draw n points on the circumference, where each point is separated from the next by 2π/n radians:
    # x = x0 + r*cos(θ_k) , x0 = 0
    # y = y0 + r*sin(θ_k) , y0 = 0
    # θ_k = (2π/n)*k
    return np.array(
        [(math.cos(2 * math.pi / n * k) * r + np.random.normal(-noise, noise),  # x
          math.sin(2 * math.pi / n * k) * r + np.random.normal(-noise, noise))  # y
         for k in range(1, n + 1)]
    ).reshape(-1, 2)

Definiamo le funzioni di generazione dei grafici:

import matplotlib.pyplot as plt
import matplotlib.colors as mcolors

def plot_scatters(X, title1, y_pred1, title2, y_pred2, title3, y_pred3, title4, y_pred4):
    """Draw 4 scatter plots, displaying the results of each clustering model."""
    f, axes = plt.subplots(2, 2, figsize=(8, 6))
    __plot_scatter(X, title1, y_pred1, axes[0, 0])
    __plot_scatter(X, title2, y_pred2, axes[0, 1])
    __plot_scatter(X, title3, y_pred3, axes[1, 0])
    __plot_scatter(X, title4, y_pred4, axes[1, 1])
    plt.tight_layout()
    plt.show()

def __plot_scatter(X, title, y_pred, ax):
    """Display the clustering model results, on a specified Matplotlib axes."""
    markers = {-1: "X", 0: "o", 1: "s", 2: "p", 3: "h"}
    ct = mcolors.TABLEAU_COLORS
    colors = {0: ct["tab:blue"], 1: ct["tab:orange"], 2: ct["tab:green"], 3: ct["tab:red"],
              -1: ct["tab:purple"]}
    for i in np.unique(y_pred):
        s = 20 if i == -1 else 40
        ax.scatter(X[y_pred == i, 0], X[y_pred == i, 1],
                   c=colors[i], edgecolor='black', marker=markers[i], s=s, zorder=2,
                   label=f"Cluster {i}")
    ax.set_xlabel("Feature 1")
    ax.set_ylabel("Feature 2")
    ax.set_title(title)
    ax.legend()
    ax.grid(linestyle="--", alpha=0.3)
    ax.set_aspect("equal", adjustable="datalim")

Vediamo un primo confronto con il dataset ritornato dalla funzione make_moons:

from sklearn.cluster import KMeans, AgglomerativeClustering
from sklearn.cluster import DBSCAN as sk_DBSCAN

def make_predictions(X, n_clusters, eps, min_samples):
    # make predictions using a KMeans model
    kmeans = KMeans(n_clusters=n_clusters, random_state=0)
    y_pred_km = kmeans.fit_predict(X)

    # make predictions using an AgglomerativeClustering model
    agg_cluster = AgglomerativeClustering(n_clusters=n_clusters, linkage="complete")
    y_pred_agg = agg_cluster.fit_predict(X)

    # make predictions using our DBSCAN model
    my_dbscan = DBSCAN(eps=eps, min_samples=min_samples, metric="euclidean")
    y_pred_my_dbscan = my_dbscan.fit_predict(X)

    # make predictions using Scikit Learn's DBSCAN model (as comparison)
    sk_dbscan = sk_DBSCAN(eps=eps, min_samples=min_samples, metric="euclidean")
    y_pred_sk_dbscan = sk_dbscan.fit_predict(X)

    return y_pred_km, y_pred_agg, y_pred_my_dbscan, y_pred_sk_dbscan

# supported values: 0; 1
X, y, n_clusters, eps, min_samples = make_data(0)
y_p_km, y_p_agg, y_p_my_dbscan, y_p_sk_dbscan = make_predictions(X, n_clusters, eps, min_samples)
plot_scatters(X,
              "K-Means Clustering", y_p_km,
              "Agglomerative Clustering", y_p_agg,
              "My DBSCAN Clustering", y_p_my_dbscan,
              "SK-Learn DBSCAN Clustering", y_p_sk_dbscan)

Confronto tra modelli KMeans, AHC e DBSCAN (1)

Sulla base dei risultati di clustering visualizzati, possiamo vedere che i modelli K-Means e AgglomerativeClustering non sono riusciti a separare i due cluster, mentre il modello DBSCAN è in grado di rilevare con successo le forme a mezzaluna. Eseguiamo un altro confronto con il dataset “Cerchi concentrici”:

X, y, n_clusters, eps, min_samples = make_data(1)
y_p_km, y_p_agg, y_p_my_dbscan, y_p_sk_dbscan = make_predictions(X, n_clusters, eps, min_samples)
plot_scatters(X,
              "K-Means Clustering", y_p_km,
              "Agglomerative Clustering", y_p_agg,
              "My DBSCAN Clustering", y_p_my_dbscan,
              "SK-Learn DBSCAN Clustering", y_p_sk_dbscan)

Confronto tra modelli KMeans, AHC e DBSCAN (2)

Anche in questo caso, DBSCAN è l’unico algoritmo che riesce a rilevare correttamente i tre cluster, ed i punti outlier.

Sfortunatamente, l’algoritmo DBSCAN ha bisogno di due iperparametri ($\epsilon$ e $\text{minPts}$), che devono essere ottimizzati per ottenere buoni risultati di clustering. Trovare una buona combinazione ti dali valori può essere problematico, se le differenze di densità nel dataset sono relativamente grandi.

In pratica, non è sempre ovvio quale sia l’algoritmo di clustering migliore per un certo dataset, soprattutto se i dati si presentano in più dimensioni, e non possono essere visualizzati senza fare pre-elaborazione dei dati. Inoltre, è importante sottolineare che il successo di un modello di clustering dipende anche dalla scelta di una metrica di distanza appropriata, e dall’utilizzo di conoscenze di dominio, che possono aiutare a guidare l’impostazione sperimentale.

Nel contesto relativo alla curse of dimensionality, prima di eseguire il clustering, è prassi comune applicare tecniche di riduzione della dimensionalità, come PCA e t-SNE. Inoltre, è prassi comune comprimere i dataset in sottospazi bidimensionali, che ci permette di visualizzare i cluster e le label assegnate alle varie osservazioni, utilizzando scatterplot bidimensionali per valutare i risultati.

I Pro e i Contro del Modello

Pro

Identificazione di Cluster di Forma Arbitraria:
a differenza di altri algoritmi di clustering come K-Means, DBSCAN può identificare cluster di varie forme e dimensioni, che non sono necessariamente sferici o di forma predefinita. Inoltre, DBSCAN non assegna necessariamente ogni punto a un cluster, ma è in grado di rimuovere gli outlier dal dataset.
Tolleranza al Rumore:
DBSCAN è in grado di gestire efficacemente il rumore e gli outlier nei dati. Etichetta le osservazioni che non appartengono a nessun cluster come rumore, consentendo di identificare ed escludere le osservazioni irrilevanti.
Nessuna Pre-specificazione del Numero di Cluster:
DBSCAN non richiede di specificare in anticipo il numero di cluster. Può determinare automaticamente il numero di cluster in base alla densità delle osservazioni, e questo è vantaggioso quando il numero di cluster non è noto a priori.
Efficiente per Grandi Dataset:
la complessità computazionale di DBSCAN è generalmente migliore di quella degli algoritmi di clustering gerarchico. DBSCAN è in grado di scalare bene su grandi insiemi di dati, ed è adatto ad applicazioni in cui l’efficienza è importante.

Contro

Sensibilità alla Selezione dei Parametri:
sebbene DBSCAN sia relativamente robusto alla selezione dei parametri, la scelta di valori appropriati per $\epsilon$ (epsilon) e $\text{minPts}$ può essere impegnativa. Le prestazioni dell’algoritmo possono variare a seconda del dataset e dei parametri scelti, e la regolazione di questi parametri può richiedere varie prove ed errori.
Difficoltà con Dataset a Densità Variabile:
DBSCAN parte dal presupposto che i cluster siano aree a maggiore densità separate da aree a minore densità. Se la densità dei punti di dati varia in modo significativo all’interno del dataset, il modello può avere delle difficoltà nell’identificare con precisione i cluster. La clusterizzazione può risultare una sotto-segmentazione o una sovra-segmentazione dei dati.
Non Adatto per Dataset ad Alta Dimensionalità:
le prestazioni di DBSCAN tendono a peggiorare con l’aumentare della dimensionalità dei dati. In spazi con un gran numero di dimensioni, il concetto di densità diventa meno significativo, e l’algoritmo può faticare a trovare i cluster.