Algoritmi di clustering - Panoramica

Introduzione al clustering

I metodi di clustering sono uno dei metodi ML senza supervisione più utili. Questi metodi vengono utilizzati per trovare la somiglianza così come i modelli di relazione tra i campioni di dati e quindi raggruppare quei campioni in gruppi aventi somiglianza basata sulle caratteristiche.

Il clustering è importante perché determina il raggruppamento intrinseco tra i dati presenti senza etichetta. Fondamentalmente fanno alcune ipotesi sui punti dati per costituire la loro somiglianza. Ogni ipotesi costruirà cluster diversi ma ugualmente validi.

Ad esempio, di seguito è riportato il diagramma che mostra il sistema di clustering raggruppato insieme il tipo simile di dati in diversi cluster:

Metodi di formazione dei cluster

Non è necessario che i cluster vengano formati in forma sferica. I seguenti sono alcuni altri metodi di formazione dei cluster:

Basato sulla densità

In questi metodi, i cluster si formano come la regione densa. Il vantaggio di questi metodi è che hanno una buona precisione e una buona capacità di unire due cluster. Ex. Clustering spaziale basato sulla densità di applicazioni con rumore (DBSCAN), punti di ordinazione per identificare la struttura di cluster (OTTICA) ecc.

Basato su base gerarchica

In questi metodi, i cluster vengono formati come una struttura ad albero basata sulla gerarchia. Hanno due categorie: Agglomerativa (approccio dal basso verso l'alto) e Divisiva (approccio dall'alto verso il basso). Ex. Clustering using Representatives (CURE), Balanced iterative Reducing Clustering using Hierarchies (BETULLA) ecc.

Partizionamento

In questi metodi, i cluster vengono formati suddividendo gli oggetti in k cluster. Il numero di cluster sarà uguale al numero di partizioni. Ex. K-means, raggruppamento di applicazioni di grandi dimensioni basato sulla ricerca randomizzata (CLARANS).

Griglia

In questi metodi, i cluster sono formati come una struttura a griglia. Il vantaggio di questi metodi è che tutte le operazioni di clustering eseguite su queste griglie sono veloci e indipendenti dal numero di oggetti dati. Ex. Griglia di informazioni statistiche (STING), Clustering in Quest (CLIQUE).

Misurazione delle prestazioni del clustering

Una delle considerazioni più importanti riguardo al modello ML è valutare le sue prestazioni o si può dire la qualità del modello. In caso di algoritmi di apprendimento supervisionato, valutare la qualità del nostro modello è facile perché abbiamo già etichette per ogni esempio.

D'altra parte, in caso di algoritmi di apprendimento senza supervisione non siamo così fortunati perché abbiamo a che fare con dati senza etichetta. Ma abbiamo ancora alcune metriche che danno al professionista una panoramica sull'avvenimento del cambiamento nei cluster a seconda dell'algoritmo.

Prima di immergerci in profondità in tali metriche, dobbiamo capire che queste metriche valutano solo le prestazioni comparative dei modelli l'una rispetto all'altra piuttosto che misurare la validità della previsione del modello. Di seguito sono riportate alcune delle metriche che possiamo implementare sugli algoritmi di clustering per misurare la qualità del modello:

Analisi della silhouette

Analisi della silhouette utilizzata per verificare la qualità del modello di clustering misurando la distanza tra i cluster. Fondamentalmente ci fornisce un modo per valutare i parametri come il numero di cluster con l'aiuto diSilhouette score. Questo punteggio misura quanto è vicino ogni punto in un cluster ai punti nei cluster vicini.

Analisi del punteggio della silhouette

La gamma del punteggio di Silhouette è [-1, 1]. La sua analisi è la seguente:

• +1 Score - Vicino a +1 Silhouette score indica che il campione è lontano dal cluster adiacente.

• 0 Score - 0 Silhouette score indica che il campione si trova o è molto vicino al confine di decisione che separa due cluster vicini.

• -1 Score & meno -1 Silhouette score indica che i campioni sono stati assegnati ai cluster errati.

Il calcolo del punteggio Silhouette può essere effettuato utilizzando la seguente formula:

= (-) / (,)

Qui, = distanza media dai punti nel cluster più vicino

E, = distanza media intra-cluster da tutti i punti.

Indice Davis-Bouldin

L'indice DB è un'altra buona metrica per eseguire l'analisi degli algoritmi di clustering. Con l'aiuto dell'indice DB, possiamo comprendere i seguenti punti sul modello di clustering:

• Meteo i cluster sono ben distanziati l'uno dall'altro o no?

• Quanto sono densi i grappoli?

Possiamo calcolare l'indice DB con l'aiuto della seguente formula:

$$ DB = \ frac {1} {n} \ displaystyle \ sum \ limits_ {i = 1} ^ n max_ {j \ neq {i}} \ left (\ frac {\ sigma_ {i} + \ sigma_ {j }} {d (c_ {i}, c_ {j})} \ right) $$

Qui, = numero di cluster

σ _i = distanza media di tutti i punti del cluster dal centroide del cluster.

Meno l'indice DB, migliore è il modello di clustering.

Indice di Dunn

Funziona come l'indice DB ma ci sono i seguenti punti in cui entrambi differiscono:

• L'indice Dunn considera solo il caso peggiore, ovvero i cluster vicini tra loro mentre l'indice DB considera la dispersione e la separazione di tutti i cluster nel modello di clustering.

• L'indice di Dunn aumenta all'aumentare delle prestazioni, mentre l'indice DB migliora quando i cluster sono ben distanziati e densi.

Possiamo calcolare l'indice di Dunn con l'aiuto della seguente formula:

$$ D = \ frac {min_ {1 \ leq i <{j} \ leq {n}} P (i, j)} {mix_ {1 \ leq i <k \ leq n} q (k)} $$

Qui, ,, = ogni indice per i cluster

= distanza tra i cluster

q = distanza intra-cluster

Tipi di algoritmi di clustering ML

I seguenti sono gli algoritmi di clustering ML più importanti e utili:

K-significa clustering

Questo algoritmo di clustering calcola i centroidi e itera finché non trova il centroide ottimale. Si presume che il numero di cluster sia già noto. È anche chiamato algoritmo di clustering piatto. Il numero di cluster identificati dai dati mediante algoritmo è rappresentato da "K" in K-mean.

Algoritmo di spostamento della media

È un altro potente algoritmo di clustering utilizzato nell'apprendimento senza supervisione. A differenza del clustering K-means, non fa presupposti, quindi è un algoritmo non parametrico.

Clustering gerarchico

È un altro algoritmo di apprendimento non supervisionato che viene utilizzato per raggruppare i punti dati senza etichetta con caratteristiche simili.

Discuteremo tutti questi algoritmi in dettaglio nei prossimi capitoli.

Applicazioni del clustering

Possiamo trovare il clustering utile nelle seguenti aree:

Data summarization and compression- Il clustering è ampiamente utilizzato nelle aree in cui è richiesta anche la sintesi, la compressione e la riduzione dei dati. Gli esempi sono l'elaborazione delle immagini e la quantizzazione vettoriale.

Collaborative systems and customer segmentation - Poiché il clustering può essere utilizzato per trovare prodotti simili o lo stesso tipo di utenti, può essere utilizzato nell'area dei sistemi collaborativi e della segmentazione della clientela.

Serve as a key intermediate step for other data mining tasks- L'analisi dei cluster può generare un riepilogo compatto dei dati per la classificazione, il test, la generazione di ipotesi; quindi, funge anche da passaggio intermedio chiave per altre attività di data mining.

Trend detection in dynamic data - Il clustering può essere utilizzato anche per il rilevamento delle tendenze nei dati dinamici creando vari cluster di tendenze simili.

Social network analysis- Il clustering può essere utilizzato nell'analisi dei social network. Gli esempi generano sequenze in immagini, video o audio.

Biological data analysis - Il clustering può essere utilizzato anche per creare gruppi di immagini, video quindi può essere utilizzato con successo nell'analisi dei dati biologici.