DBSCAN (Density-Based Spatial Clustering of Applications with Noise, raggruppamento spaziale delle applicazioni basato sulla densità con rumore)

Come funziona DBSCAN

DBSCAN identifica i cluster basandosi sul concetto di raggiungibilità della densità. Considera i cluster come aree ad alta densità separate da aree a bassa densità. Il comportamento dell'algoritmo è controllato principalmente da due parametri:

1. Epsilon (eps): Questo parametro definisce la distanza massima tra due punti di dati affinché uno di essi venga considerato come vicino all'altro. In pratica crea un raggio intorno a ogni punto.
2. Punti minimi (minPts): Questo parametro specifica il numero minimo di punti dati richiesti all'interno del vicinato eps di un punto (incluso il punto stesso) affinché quel punto sia classificato come "punto centrale".

In base a questi parametri, i punti dati vengono classificati in tre tipi:

• Punti fondamentali: Un punto è un punto centrale se ha almeno minPts vicini all'interno del suo eps raggio. Questi punti sono tipicamente situati all'interno di un cluster.
• Punti di confine: Un punto è un punto di confine se è raggiungibile da un punto centrale (cioè, all'interno del eps raggio di un punto centrale) ma non ha minPts vicini a sé stessi. I punti di confine si trovano ai margini dei cluster.
• Punti di disturbo (Outlier): Un punto che non è né un punto centrale né un punto di confine è considerato rumore. Questi punti sono tipicamente isolati in regioni a bassa densità.

L'algoritmo inizia selezionando un punto dati arbitrario e non visitato. Verifica se il punto è un punto centrale esaminando il suo eps-vicino. Se si tratta di un punto centrale, viene formato un nuovo cluster e l'algoritmo aggiunge ricorsivamente tutti i punti raggiungibili dalla densità (punti centrali e di confine nel vicinato) a questo cluster. Se il punto selezionato è un punto di disturbo, viene temporaneamente contrassegnato come tale e l'algoritmo passa al punto successivo non visitato. Questo processo continua fino a quando tutti i punti sono stati visitati e assegnati a un cluster o contrassegnati come rumore. Per un approfondimento della metodologia originale, consulta il documento di ricerca: "Un algoritmo basato sulla densità per scoprire cluster in grandi database spaziali con rumore".

Vantaggi e svantaggi principali

DBSCAN offre diversi vantaggi:

• Gestisce forme arbitrarie: A differenza di algoritmi come K-means, DBSCAN può trovare cluster non sferici.
• Non è necessario definire il numero di cluster: Il numero di cluster viene determinato dall'algoritmo in base alla densità.
• Robusto ai valori anomali: Ha un meccanismo integrato per identificare e gestire i punti di disturbo.

Tuttavia, presenta anche dei limiti:

• Sensibilità dei parametri: La qualità dei risultati del clustering dipende in larga misura dalla scelta di eps e minPts. Trovare i parametri ottimali può essere una sfida. Strumenti come implementazioni di offerte scikit-learn che può essere messa a punto.
• Difficoltà con densità variabili: Si trova in difficoltà con i set di dati in cui i cluster hanno densità significativamente diverse, in quanto un singolo eps-minPts La combinazione potrebbe non funzionare bene per tutti i cluster.
• Dati ad alta dimensione: Le prestazioni possono peggiorare in spazi altamente dimensionali a causa della"maledizione della dimensionalità", in cui il concetto di densità diventa meno significativo.

DBSCAN contro altri metodi di clustering

DBSCAN viene spesso confrontato con altri algoritmi di clustering, in particolare con il clustering K-means. Le differenze principali includono:

• Forma dei cluster: K-means presuppone che i cluster siano sferici e di dimensioni uguali, mentre DBSCAN può trovare cluster di forma arbitraria.
• Numero di cluster: K-means richiede all'utente di specificare il numero di cluster (k) in anticipo, mentre DBSCAN lo determina automaticamente.
• Gestione degli outlier: K-means assegna ogni punto a un cluster, rendendolo sensibile agli outlier. DBSCAN identifica e isola esplicitamente gli outlier come rumore.
• Complessità computazionale: K-means è generalmente più veloce di DBSCAN, soprattutto su grandi insiemi di dati, anche se la complessità di DBSCAN può variare in base alla scelta dei parametri e alle ottimizzazioni della struttura dei dati come i KD-trees.

Applicazioni del mondo reale

La capacità di DBSCAN di trovare gruppi densi e di isolare i valori anomali lo rende adatto a diverse applicazioni:

• Rilevamento delle anomalie: Identificare modelli insoliti che si discostano dal comportamento normale. Ad esempio, l'individuazione di transazioni fraudolente con carta di credito che spesso appaiono come punti isolati rispetto a gruppi densi di spese legittime, o l'identificazione di intrusioni nei dati del traffico di rete per la sicurezza informatica. Esplora i concetti correlati in Vision AI per il rilevamento delle anomalie.
• Analisi dei dati spaziali: Analisi di dati geografici o spaziali. Ad esempio, il raggruppamento delle posizioni dei clienti per identificare i segmenti di mercato, l'analisi dei punti nevralgici della criminalità in una città(AI nelle smart city) o l'identificazione di modelli nell'analisi delle immagini satellitari per la classificazione dell'uso del suolo o il monitoraggio ambientale.
• Analisi dei dati biologici: Raggruppare i dati di espressione genica o identificare le strutture nei database delle proteine.
• Sistemi di raccomandazione: Raggruppare utenti con preferenze simili sulla base di dati di interazione scarsi(panoramica sui sistemi di raccomandazione).

DBSCAN e Ultralytics

La Ultralytics si concentra principalmente su modelli di apprendimento supervisionati, come ad esempio Ultralytics YOLO per compiti quali il rilevamento di oggetti, la classificazione di immagini e la segmentazione di immagini. Mentre DBSCAN, essendo un metodo non supervisionato, non è direttamente integrato nei cicli di addestramento principali di modelli come YOLOv8 o YOLO11i suoi principi sono rilevanti nel contesto più ampio della computer vision (CV) e dell'analisi dei dati. La comprensione della densità e della distribuzione dei dati è fondamentale quando si preparano e si analizzano i dataset per l'addestramento o quando si elaborano i risultati dei modelli, ad esempio raggruppando gli oggetti rilevati in base alla loro vicinanza spaziale dopo l'inferenza. Piattaforme come Ultralytics HUB forniscono strumenti per la gestione e la visualizzazione dei dataset, che possono integrare le tecniche di analisi esplorativa dei dati in cui possono essere applicati algoritmi di clustering come DBSCAN.