Data Mining 1 - Appunti

DM1 – Part2 – Clustering

L'analisi dei clusters

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 o stock di fluttuazioni di prezzo simili. Esempio: 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. Esempio: 1000 precipitazioni in Australia divise 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 ai 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.

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 fuzzy 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ù 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 Function

Vi sono casi in cui si trovano i cluster che massimizzano o minimizzano la funziona 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 oggetti. Mentre un centroide non corrisponde quasi mai a un punto dati effettivo, un medoid, per definizione, deve essere un punto dati effettivo.

Algoritmo Base 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).
2. 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 trovano 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 accelera il tradizionale K-Means andando a ridurre il numero di similarità da calcolare.
3. 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.
4. 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, perché 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.

Domanda Orale

Il K-means può non terminare? No, ad un certo punto arriverà ad una conclusione. Si 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.

È 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 cui... [Testo incompleto]