L’analisi dei cluster o semplicemente il clustering è essenzialmente una tecnica di apprendimento non assistita che suddivide l’informazione su vari gruppi o raggruppamenti espliciti, con l’obiettivo finale che l’informazione si focalizzi in raggruppamenti simili con proprietà comparabili e l’informazione si focalizzi in raggruppamenti diversi con proprietà diverse in un certo senso. Contiene una vasta gamma di strategie che dipendono da vari progressi.
Per esempio K-Means (separazione tra i fuochi), Liking proliferation (separazione del diagramma), Mean-move (separazione tra i fuochi), DBSCAN (separazione tra i fuochi più vicini), miscele gaussiane (separazione Mahalanobis ai fuochi), Unearthly grouping (separazione del diagramma) e così via.
A livello molto elementare, tutte le tecniche di raggruppamento utilizzano una metodologia simile, per esempio, prima calcoliamo le similitudini e poi le usiamo per raggruppare le informazioni in modo che si concentrino sui raggruppamenti o sulle ciuffi. Qui ci concentreremo sul raggruppamento spaziale basato sullo spessore degli usi con la strategia del raggruppamento a grappolo (DBSCAN).
I gruppi sono spessi locali nello spazio dell’informazione, isolati da aree di minore spessore dei fuochi d’artificio. Il calcolo del DBSCAN dipende da questa idea naturale di “grappoli” e “confusione”. La chiave però è che per ogni scopo di un gruppo, l’area di una data spazzata deve contenere in ogni caso un numero base di focolai.
Perché DBSCAN?
Strategie di parcellizzazione (K-implies, PAM bunching) e lavoro di raggruppamento progressivo per trovare mazzi di forma circolare o ad arco. Come tali, sono ragionevoli solo per i grappoli conservatori e ben isolati. Inoltre, sono inoltre seriamente influenzati dalla vicinanza di confusione e da anomalie nelle informazioni.
Le informazioni originali possono contenere anomalie, in quanto –
I) I grappoli possono essere di forma discrezionale, ad esempio quelli che appaiono nella figura sottostante.
ii) Le informazioni possono contenere clamore.
le figure sottostanti mostrano un indice informativo contenente gruppi non convessi e anomalie/clami. Date tali informazioni, k-implica problemi di calcolo per distinguere questi gruppi con forme discrezionali.
Il calcolo del DBSCAN richiede due parametri –
In questo algoritmo abbiamo 3 tipi di punti dati.
Punto centrale: Un punto è un punto centrale se ha più di punti MinPts all’interno di eps.
Punto di confine: Un punto che ha meno di MinPts all’interno di eps ma che si trova nelle vicinanze di un punto centrale.
Rumore o anomalia: Un punto che non è un punto centrale o un punto di confine.
eps: Caratterizza l’area intorno ad un punto informativo, ad esempio nel caso in cui la separazione tra due punti è inferiore o equivalente a ‘eps’ in quel punto sono considerati vicini. Nella remota possibilità che la stima dell’eps sia raccolta troppo poco, a quel punto una parte enorme dell’informazione sarà considerata come un’eccezione. Nella remota possibilità che sia estremamente enorme, a quel punto i gruppi si consolideranno e la maggior parte delle informazioni si concentreranno in gruppi simili. Un approccio per scoprire la stima dell’eps dipende dal diagramma di k-separazione.
Di seguito è riportato l’algoritmo di clustering DBSCAN in pseudocodice:
DBSCAN(dataset, eps, MinPts){
# Indice dei cluster
C = 1
per ogni punto p non visitato del dataset {
segna p come visitato
# Trova i vicini
Vicini N = trovare i punti vicini di p
se |N|>>=MinPts:
N = N U N’
se p’ non è un membro di nessun cluster:
aggiungere p’ al gruppo C