Data Mining 1 - Appunti

DM1 – PART2 – CLUSTERING

L’analisi dei clusters divide i dati in gruppi (clusters) significativi (per poi fare classificazione), utili (per

fornire un’astrazione di oggetti dai clusters) o entrambi. In alcuni casi, questa analisi è solo il punto di

partenza per altri scopi, come la sintetizzazione dei dati. L’analisi dei clusters raggruppa gli oggetti in

base alle informazioni trovate nei dati che descrivono gli oggetti e le loro relazioni. L’obiettivo è quello di

trovare gruppi in cui all’interno gli oggetti siano simili (o correlati) tra loro e diversi (o non correlati) dagli

oggetti in altri gruppi. Maggiore è la similarità (o omogeneità) all’interno di un gruppo e maggiore è la

differenza tra altri gruppi, migliore o più “distinto” è il clustering. Le distanze intra-cluster sono

minimizzate, mentre sono massimizzate le distanze inter-cluster. La definizione di cluster è imprecisa

(perché ci sono diverse maniere per fare clustering) e quindi dipende dalla natura dei dati e dai risultati

desiderati. Il clustering può essere considerato una forma di classificazione in quanto crea

un’etichettatura di oggetti con etichette di classe (che sarebbero i numeri del cluster corrispondente),

ma deriva queste etichette solo dai dati. Il clustering, infatti, viene spesso definito come classificazione

non supervisionata. Con il clustering l’obiettivo cambia, rispetto alla classificazione perché non abbiamo

etichette. L’obiettivo è di trovare le strutture dei dati, non cercando di riconoscere una struttura

predefinita (ad esempio un buon cliente o un cattivo cliente), ma si guarda cosa suggerisce la struttura

dei dati.

L’analisi dei clusters è utile quando non si hanno molte informazioni né sui dati né su ciò che si sta

cercando, infatti ci aiuta ad esplorare. Non è una semplice segmentazione perché non conosciamo i

gruppi e non li creiamo basandoci su conoscenze esterne (li creiamo basandoci sui dati stessi)

Applicazioni della clustering analysis:

- Understanding: viene utilizzato per capire meglio i dati che abbiamo, quindi gruppi di documenti

associati, gruppi di geni e proteine che hanno funzioni simili or stock di fluttuazioni di prezzo simili. Es:

raggruppare i documenti per contenuto simile (creando un cluster) e indicizzarli

- Summarization: semplificazione, riduce la taglia di un grande dataset di modo che un singolo

consumatore mi possa rappresentare una piccola parte del set. Es: 1000 precipitazioni in Australia divisi

in 10 gruppi, così da snellire la struttura.

DIFFERENTI TIPI DI CLUSTERING

Un’intera raccolta di clusters viene comunemente definita come clustering, distinguiamo i seguenti tipi:

gerarchico (annidato) vs partizionale (non annidato); esclusivo vs sovrapposto vs fuzzy; completo vs

parziale.

- Gerarchico vs Partizionale: un clustering partizionale è semplicemente una divisione dell’insieme di

oggetti in sottoinsiemi (clusters) non sovrapposti, in modo che ogni oggetto si trovi esattamente in un

sottoinsieme. Se permettiamo a clusters di avere dei sottoclusters otteniamo un clustering gerarchico,

che è un insieme di clusters annidati, organizzati come un albero. Ogni nodo (cluster) in un albero

(eccetto il nodo foglia) è l’unione dei suoi figli (sottoclusters), e la radice dell’albero è il cluster che

contiene tutti gli oggetti. Spesso, ma non sempre, le foglie dell’albero sono cluster singleton, di singoli

oggetti. Infine, si noti che un clustering gerarchico può essere visto come una sequenza di clustering

partizionali e un clustering partizionale può essere ottenuto prendendo qualsiasi membro di quella

sequenza; cioè tagliando l'albero gerarchico a un livello particolare. Un’altra maniera per rappresentarli

è il dendogram, metodo con cui si parte da X oggetti che corrispondono a X cluster. Il passo successivo è

iniziare ad aggregare sempre più per formare cluster più grandi 1

- Esclusivo vs Sovrapposto vs Fuzzy: Nei clustering esclusivi ogni punto viene assegnato ad un singolo

cluster. Tuttavia, ci sono molte situazioni in cui un punto potrebbe ragionevolmente essere collocato in

più di un cluster, e queste situazioni sono affrontate meglio dal clustering non-esclusivo. Un clustering

sovrapposto o non-esclusivo viene utilizzato per riflettere il fatto che un oggetto può essere associato a

più di un gruppo (classe). Ad esempio, una persona in un'università può essere sia uno studente iscritto

che un dipendente dell'università. Un clustering non-esclusivo viene spesso utilizzato anche quando, ad

esempio, un oggetto è "tra" due o più cluster e può essere ragionevolmente assegnato a uno di questi

cluster (quando altrimenti dovremmo fare un’assegnazione più o meno arbitraria). In un clustering fuzzi

ogni oggetto appartiene ad ogni cluster con un peso di appartenenza compreso tra 0 (assolutamente

non appartenente) e 1 (appartiene assolutamente). In altre parole, i clusters sono trattati come insiemi

fuzzy. In questo clustering spesso si impone un vincolo aggiuntivo, che la somma dei pesi per ogni

oggetto deve essere uguale ad 1. Allo stesso modo, le tecniche probabilistiche di clustering calcolano la

probabilità con cui ogni punto appartiene a ciascun cluster, e queste probabilità devono anche

sommarsi a 1. Poiché i pesi o le probabilità di appartenenza per qualsiasi somma di oggetto sono 1, un

clustering fuzzy o probabilistico non affronta situazioni reali di multiclassi, ad esempio il caso di un

dipendente studente, in cui un oggetto appartiene a più classi. Al contrario, questi approcci sono più

appropriati per evitare l'arbitrarietà di assegnare un oggetto a un solo cluster quando può essere vicino

a più. In pratica, un clustering fuzzy o probabilistico viene spesso convertito in un clustering esclusivo

assegnando ogni oggetto al cluster in cui il suo peso o probabilità di appartenenza è più alto.

- Completo vs Parziale: Un clustering completo assegna ogni oggetto a un cluster, mentre un clustering

parziale no. La motivazione per un clustering parziale è che alcuni oggetti in un set di dati potrebbero

non appartenere a gruppi ben definiti. Molte volte gli oggetti nel set di dati possono rappresentare

rumore, valori anomali o essere poco utili. Ad esempio, alcune storie di giornali possono condividere un

tema comune, come il riscaldamento globale, mentre altre storie sono più generiche o uniche nel loro

genere. Pertanto, per trovare gli argomenti importanti nelle storie del mese scorso, potremmo voler

cercare solo cluster di documenti strettamente correlati da un tema comune. In altri casi, si desidera un

clustering completo degli oggetti.

- Omogeneo vs eterogeneo: se i clusters sono dello stesso tipo o di tipo diverso.

DIFFERENTI TIPI DI CLUSTERS

Il clustering mira a trovare gruppi utili di oggetti (cluster), dove l'utilità è definita dagli obiettivi

dell'analisi dei dati.

- Well-Separated: Un cluster è un insieme di oggetti in cui ogni oggetto è più vicino (o più simile) a ogni

altro oggetto dello stesso cluster rispetto a qualsiasi oggetto non nel cluster. A volte viene utilizzata una

soglia per specificare che tutti gli oggetti in un cluster devono essere sufficientemente vicini (o simili)

l'uno all'altro. Questa definizione idealistica di cluster è soddisfatta solo quando i dati contengono

cluster naturali abbastanza distanti l'uno dall'altro. Gli ammassi ben separati non hanno bisogno di

essere globulari, ma possono avere qualsiasi forma.

- Prototype-Based: Un cluster è un insieme di oggetti in cui ogni oggetto è più vicino (più simile) al

prototipo che definisce il cluster che al prototipo di qualsiasi altro cluster. Per i dati con attributi

continui, il prototipo di un cluster è spesso un centroide, cioè la media di tutti i punti del cluster. Quando

un centroide non è significativo, ad esempio quando i dati hanno attributi categorici, il prototipo è

spesso un medoide, cioè il punto più rappresentativo di un cluster. Per molti tipi di dati, il prototipo può

essere considerato il punto più centrale e, in tali casi, comunemente ci riferiamo ai cluster basati su

prototipi come cluster center based. Non sorprende che tali ammassi tendano ad essere globulari.

- Graph-Based: Se i dati sono rappresentati come un grafo, dove i nodi sono oggetti e i collegamenti

rappresentano connessioni tra oggetti, allora un cluster può essere definito come un componente

connesso; cioè un gruppo di oggetti connessi tra loro, ma che non hanno alcuna connessione con oggetti

esterni al gruppo. Un esempio importante di cluster graph-based sono i cluster basati contiguity-based,

in cui due oggetti sono connessi solo se si trovano entro una distanza specificata l'uno dall'altro (si

connettono punti vicini tra loro). Ciò implica che ogni oggetto in un cluster basato sulla contiguità è più

2

vicino a qualche altro oggetto nel cluster che a qualsiasi punto di un cluster diverso. Questa definizione

di cluster è utile quando i cluster sono irregolari o intrecciati, ma può avere problemi quando è presente

rumore poiché, un piccolo ponte di punti può unire due cluster distinti, per transitività. Nella realtà al di

fuori dei clusters ci sono molti punti. Il bordo tra “cluster” e “non-cluster” non è così netto come

abbiamo assunto finora, quindi se usassimo la definizione descritta precedentemente, la contiguity

based, troveremo un singolo grande cluster.

- Density-Based: Un ammasso è una regione densa di oggetti circondata da una regione a bassa densità.

Una definizione basata sulla densità di un cluster viene spesso utilizzata quando i cluster sono irregolari

o intrecciati e quando sono presenti rumore e valori anomali. Con questa tecnica rimuoviamo i punti che

sono isolati, ma è necessario definire una soglia di densità.

- Objective Functin: vi sono casi in cui si trovano i cluster che massimizzano o minimizzano la funzione

obiettivo. Ci sono molti possibili modi per dividere i punti nei cluster e per misurare la bontà di ogni set

di cluster potenziale trovati usando la funzione obiettivo data (NP Hard). È possibile inoltre avere

obiettivi locali o globali: il clustering gerarchico tipicamente da obiettivi locali, mentre i partitional

algorithms li hanno globali.

- Shared-Property (Conceptual Clusters): Più in generale, possiamo definire un cluster come un insieme

di oggetti che condividono alcune proprietà. Questa definizione comprende tutte le definizioni

precedenti di un cluster; ad esempio, gli oggetti in un cluster basato sul centro condividono la proprietà

che sono tutti più vicini allo stesso centroide o medoide. Tuttavia, l'approccio della proprietà condivisa

include anche nuovi tipi di cluster

Caratteristiche dei dati di input:

Le misure di prossimità o densità per i dati sono centrali per il raggruppamento, ma ciò dipende molto

dai dati che si hanno. Le caratteristiche dei dati che influenzano la prossimità o la densità sono

molteplici:

- Dimensionalità: ci può portare a problemi di ”sparsness”

- Diversi tipi di attributi

- Correlazioni interne speciali: possono influenzare il risultato

- Distribuzione dei dati: può influenzare la distribuzione

- Rumore e outliers interferiscono con le operazioni degli algoritmi di clustering.

Algoritmi di clustering (Sommario):

- K-Means: Si tratta di una tecnica di clustering partizionale prototype-based che tenta di trovare un

numero specificato dall'utente di cluster (K), rappresentati dai loro centroidi.

- DBSCAN: Si tratta di un algoritmo di clustering density-based che produce un clustering partizionale, in

cui il numero di cluster viene determinato automaticamente dall'algoritmo. I punti nelle regioni a bassa

densità sono classificati come rumore e omessi; pertanto, DBSCAN non produce un clustering completo.

- Clustering gerarchico agglomerativo: Questo approccio di clustering si riferisce a una raccolta di

tecniche di clustering strettamente correlate che producono un clustering gerarchico iniziando con ogni

punto come cluster singleton e quindi unendo ripetutamente i due cluster più vicini fino a quando non

rimane un singolo cluster onnicomprensivo. Alcune di queste tecniche hanno un'interpretazione

naturale in termini di clustering basato su grafi, mentre altre hanno un'interpretazione in termini di

approccio basato su prototipi. KMEANS

Le tecniche di clustering basate su prototipi creano un partizionamento a un livello degli oggetti. Ci sono

un certo numero di tali tecniche, ma due delle più importanti sono K-means e K-medoid. K-means

definisce un prototipo in termini di centroidi, che di solito è la media di un gruppo di punti, ed è

tipicamente applicato agli oggetti in uno spazio n-dimensionale continuo. K-medoid definisce un

prototipo in termini di medoide, che è il punto più rappresentativo per un gruppo di punti, e può essere

applicato a una vasta gamma di dati poiché richiede solo una misura di prossimità per una coppia di

3

oggetti. Mentre un centroide non corrisponde quasi mai a un punto dati effettivo, un medoid, per

definizione, deve essere un punto dati effettivo.

AlgoritmoBase del K-Means

La tecnica di clustering K-means è semplice, e iniziamo con una descrizione dell'algoritmo di base. Per

prima cosa scegliamo K centroidi iniziali, dove K è un parametro specificato dagli utenti, vale a dire il

numero di cluster desiderati. Ogni punto viene quindi assegnato al centroide più vicino, e ogni raccolta

di punti assegnati a un centroide è un cluster. Il centroide di ogni cluster viene quindi aggiornato in base

ai punti assegnati al cluster. Ripetiamo i passaggi di assegnazione e aggiornamento fino a quando nessun

punto cambia cluster, o in modo equivalente, fino a quando i centroidi rimangono gli stessi.

L’algoritmo del K-Means è formalmente descritto così:

1. Per prima cosa scelgo K centroidi iniziali (ad esempio casualmente) e assumo che siano il centro dei

clusters (tipicamente il centroide è la media dei punti del cluster).

3. Durante il ciclo, i punti vengono assegnati al centroide più vicino.

Per farlo, abbiamo bisogno di una misura di prossimità che quantifichi la nozione di “più vicino” per i

dati considerati. La distanza euclidea (la L2) è usata spesso per i dati nello spazio euclideo, mentre la

cosine similarity è più appropriata per i documenti. Tuttavia, possono esserci diversi tipi di misure di

prossimità appropriate per un determinato tipo di dato. Ad esempio, la distanza di Manhattan (L1) può

essere utilizzata per i dati euclidei, mentre la misura Jaccard è spesso utilizzata per i documenti. Di

solito, le misure di somiglianza utilizzate per i mezzi K sono relativamente semplici poiché l'algoritmo

calcola ripetutamente la somiglianza di ogni punto con ogni centroide. In alcuni casi. Tuttavia. come

quando i dati si trova nello spazio euclideo a bassa dimensione, è possibile evitare di calcolare molte

delle somiglianze, accelerando così significativamente l'algoritmo K-means. Il bisecting K-Means è un

altro approccio che accellera il tradizionale K-Means andando a ridurre il numero di similarità da

calcolare.

4. Dopo aver assegnato i punti ai clusters si ricalcolano i centroidi per ogni cluster, poiché il centroide

può variare, a seconda della misura di prossimità e dell’obiettivo del clustering. Una volta creato il

cluster e sapendo che il centroide non è il vero punto medio del cluster, verrà rifatta la media al suo

interno e verrà “eletto” un nuovo centroide. Il loop si ripeterà ancora, cioè la media verrà aggiornata

nuovamente finchè non ci saranno più variazioni e il centroide sarà il più rappresentativo possibile, così

da minimizzare l’SSE. L’obiettivo del clustering è tipicamente espresso da una funzione obiettivo che

dipende dalla distanza tra i punti di ogni punto dal centroide più vicino.

5. Spesso, siccome la convergenza avviene nei primi passaggi, la condizione al passo 5 viene sostituita da

una condizione più debole, ad esempio “ripetere il ciclo fino a quando solo l’1% dei punti cambia

clusters”.

Complessità del KMeans

I requisiti in spazio per il K-Means sono modesti, in quanto vengono memorizzati solo i dati (punti) e i

centroidi. In particolare, il costo di archiviazione è O((m + K)*n), dove m è il numero di punti ed n il

numero di attributi. Anche il costo in tempo è modesto, fondamentalmente lineare rispetto al numero

di punti. In particolare, il tempo richiesto è O(I * K * m * m), dove I è il numero di iterazioni richieste per

la convergenza. “I” è solitamente piccolo e può essere delimitato in modo sicuro, poiché la maggior

parte dei cambiamenti si verifica in genere nelle prime iterazioni. Pertanto, il K-Means è lineare in “m”, il

numero di punti ed è efficiente oltre che semplice, a condizione che K (il numero di clusters) sia

significativamente minore di m.

- DomandaOrale: il K-means può non terminare? No, ad un certo punto arriverà ad una conclusione. Si

4

può vedere anche matematicamente per la SSE. Questo non esclude il fatto che ci possa mettere degli

anni a raggiungere la convergenza perfetta. Quindi converge sempre, ma alle volte trova soluzioni

subottimali.

- DomandaOrale: è possibile accellerarlo? Sì, possiamo definire il numero di iterazioni. Più se ne ha, più

ci si avvicinerà alla situazione ideale. Interrompendo prima, accetto il fatto di avere una soluzione non

ottima. Ovviamente, ciò dipende anche dalla precisione con cu