Data Mining – Cluster Analysis

Cluster è un gruppo di oggetti che appartiene alla stessa classe. In altre parole, oggetti simili sono raggruppati in un cluster e oggetti dissimili sono raggruppati in un altro cluster.

Che cos’è il Clustering?

Il clustering è il processo di creazione di un gruppo di oggetti astratti in classi di oggetti simili.

Punti da ricordare

• Un cluster di oggetti dati può essere trattato come un unico gruppo.

• Durante l’analisi del cluster, partizioniamo prima il set di dati in gruppi in base alla somiglianza dei dati e quindi assegniamo le etichette ai gruppi.

• Il vantaggio principale del clustering rispetto alla classificazione è che è adattabile ai cambiamenti e aiuta a individuare funzioni utili che distinguono diversi gruppi.

Applicazioni di Cluster Analysis

• L’analisi di clustering è ampiamente utilizzata in molte applicazioni come ricerche di mercato, pattern recognition, analisi dei dati e elaborazione delle immagini.

• Il clustering può anche aiutare i marketer a scoprire gruppi distinti nella loro base di clienti. E possono caratterizzare i loro gruppi di clienti in base ai modelli di acquisto.

• Nel campo della biologia, può essere utilizzato per ricavare tassonomie vegetali e animali, categorizzare geni con funzionalità simili e ottenere informazioni sulle strutture inerenti alle popolazioni.

• Il clustering aiuta anche nell’identificazione di aree di uso del suolo simile in un database di osservazione della terra. Aiuta anche nell’identificazione di gruppi di case in una città in base al tipo di casa, valore e posizione geografica.

• Il clustering aiuta anche a classificare i documenti sul Web per la scoperta delle informazioni.

• Il clustering viene utilizzato anche in applicazioni di rilevamento di valori anomali come il rilevamento di frodi con carte di credito.

• Come funzione di data mining, l’analisi dei cluster serve come strumento per ottenere informazioni sulla distribuzione dei dati per osservare le caratteristiche di ciascun cluster.

Requisiti di Clustering nel Data Mining

I seguenti punti gettano luce sul perché il clustering è richiesto nel data mining −

• Scalabilità − Abbiamo bisogno di algoritmi di clustering altamente scalabili per gestire database di grandi dimensioni.

• Capacità di gestire diversi tipi di attributi − Gli algoritmi dovrebbero essere in grado di essere applicati su qualsiasi tipo di dati come dati (numerici) basati su intervalli, dati categorici e binari.

• Scoperta di cluster con forma di attributo − L’algoritmo di clustering dovrebbe essere in grado di rilevare cluster di forma arbitraria. Non dovrebbero essere limitati solo a misure di distanza che tendono a trovare cluster sferici di piccole dimensioni.

• Alta dimensionalità − L’algoritmo di clustering dovrebbe non solo essere in grado di gestire dati a bassa dimensione, ma anche lo spazio ad alta dimensione.

• Capacità di gestire dati rumorosi: i database contengono dati rumorosi, mancanti o errati. Alcuni algoritmi sono sensibili a tali dati e possono portare a cluster di scarsa qualità.

• Interpretabilità-I risultati del clustering dovrebbero essere interpretabili, comprensibili e utilizzabili.

Metodi di Clustering

metodi di Clustering possono essere classificati nelle seguenti categorie:

• Metodo di Partizionamento
• Metodo Gerarchico
• Density-based Method
• Griglia Metodo Basato su
• Modello Basato su Metodo
• Constraint-based Method

Metodo di Partizionamento

Supponiamo che abbiamo un database di ‘n’ oggetti e il metodo di partizionamento costrutti ‘k’ e una partizione di dati. Ogni partizione rappresenterà un cluster e k ≤ n. Significa che classificherà i dati in gruppi k, che soddisfano i seguenti requisiti:

• Ogni gruppo contiene almeno un oggetto.

• Ogni oggetto deve appartenere esattamente a un gruppo.

Punti da ricordare −

• Per un dato numero di partizioni (ad esempio k), il metodo di partizionamento creerà un partizionamento iniziale.

• Quindi utilizza la tecnica di rilocazione iterativa per migliorare il partizionamento spostando oggetti da un gruppo all’altro.

Metodi gerarchici

Questo metodo crea una scomposizione gerarchica del dato insieme di oggetti dati. Possiamo classificare i metodi gerarchici sulla base di come si forma la decomposizione gerarchica. Ci sono due approcci qui-

• Approccio agglomerativo
• Approccio divisivo

Approccio agglomerativo

Questo approccio è anche noto come approccio bottom-up. In questo, iniziamo con ogni oggetto che forma un gruppo separato. Continua a unire gli oggetti o i gruppi che sono vicini l’uno all’altro. Continua a farlo fino a quando tutti i gruppi non vengono uniti in uno o fino a quando la condizione di terminazione rimane valida.

Approccio divisivo

Questo approccio è anche noto come approccio top-down. In questo, iniziamo con tutti gli oggetti nello stesso cluster. Nell’iterazione continua, un cluster viene suddiviso in cluster più piccoli. È inattivo fino a quando ogni oggetto in un cluster o la condizione di terminazione rimane valida. Questo metodo è rigido, cioè una volta eseguita una fusione o una divisione, non può mai essere annullata.

Approcci per migliorare la qualità del Clustering gerarchico

Ecco i due approcci che vengono utilizzati per migliorare la qualità del clustering gerarchico:

• Eseguire un’attenta analisi dei collegamenti degli oggetti ad ogni partizionamento gerarchico.

• Integrare l’agglomerazione gerarchica utilizzando prima un algoritmo agglomerativo gerarchico per raggruppare gli oggetti in micro-cluster e quindi eseguire il macro-clustering sui micro-cluster.

Metodo basato sulla densità

Questo metodo si basa sulla nozione di densità. L’idea di base è di continuare a far crescere il cluster dato finché la densità nel quartiere supera una certa soglia, cioè, per ogni punto dati all’interno di un determinato cluster, il raggio di un determinato cluster deve contenere almeno un numero minimo di punti.

Metodo basato sulla griglia

In questo, gli oggetti insieme formano una griglia. Lo spazio oggetto è quantizzato in numero finito di celle che formano una struttura a griglia.

Vantaggi

• Il principale vantaggio di questo metodo è il tempo di elaborazione veloce.

• Dipende solo dal numero di celle in ogni dimensione nello spazio quantizzato.

Metodi basati su modelli

In questo metodo, viene ipotizzato un modello per ciascun cluster per trovare la migliore corrispondenza dei dati per un determinato modello. Questo metodo individua i cluster raggruppando la funzione di densità. Riflette la distribuzione spaziale dei punti dati.

Questo metodo fornisce anche un modo per determinare automaticamente il numero di cluster in base a statistiche standard, tenendo conto di outlier o rumore. Produce quindi robusti metodi di clustering.

Metodo basato su vincoli

In questo metodo, il clustering viene eseguito incorporando vincoli orientati all’utente o all’applicazione. Un vincolo si riferisce all’aspettativa dell’utente o alle proprietà dei risultati di clustering desiderati. I vincoli ci forniscono un modo interattivo di comunicazione con il processo di clustering. I vincoli possono essere specificati dall’utente o dal requisito dell’applicazione.