Lezione 8 PDF - Analisi di Raggruppamento

Cosa è l'analisi di raggruppamento? 2  Cosa è la analisi di raggruppamento? Un gruppo (cluster) è una collezione di istanze tali che: – le istanze dello stesso cluster sono simili tra loro alta somiglianza intra-classe – le istanze di cl...

Cosa è l'analisi di raggruppamento? 2  Cosa è la analisi di raggruppamento? Un gruppo (cluster) è una collezione di istanze tali che: – le istanze dello stesso cluster sono simili tra loro alta somiglianza intra-classe – le istanze di cluster diversi sono dissimili bassa somiglianza inter-classe Analisi di raggruppamento (cluster analysis) – il processo di raggruppamento delle istanze in cluster. – si tratta di apprendimento non supervisionato le istanze di addestramento non hanno una classe nota a priori – la qualità di una analisi di raggruppamento dipenderà dal parametro scelto per misurare la somiglianza inter e intra-classe dall'algoritmo utilizzato per l'implementazione dell'analisi. 3  Applicazioni dell'analisi di raggruppamento Varie possibilità di utilizzo: – come analisi stand-alone, – come processo preliminare ad altre analisi di dati ad esempio, assegnare una etichetta ad ognuno, e poi utilizzare un algoritmo di classificazione. – come componente integrato di algoritmi per altri tipi di analisi: ad esempio le regole associative quantitative “basate sulla distanza” (che non abbiamo visto, ma che si basano su algortimi di raggruppamento) – nella fase di pre-elaborazione dati eliminazione degli outlier riduzione della numerosità 4  Esempi di analisi di raggruppamento Marketing. Aiuta gli esperti di marketing a individuare gruppi distinti tra i propri clienti, sulla base delle abitudini di acquisto (la cosiddetta analisi di segmentazione) Assicurazioni. Identifica gruppi di assicurati con notevoli richieste di rimborso. Studi sui terremoti. Gli epicentri dei terremoti dovrebbero essere agglomerati lungo le faglie continentali. Motori di ricerca. I risultati di un motore di ricerca possono essere sottoposti ad analisi di raggruppamento in modo da mettere in un unico gruppo le risposte tra loro simili – quindi presentare meno alternative all'utente 5 Distanza tra istanze 6  Strutture Dati Gli algoritmi di raggruppamento usano di solito rappresentare i dati in uno di questi due modi:   – Matrice dati x 11  x 1f  x 1p      xij = attributo i della istanza j x 1p    x ip Tipica visione relazionale      modello usato fin'ora x n1  x nf  x np   – Matrice delle distanze 0 d(i,j)=distanza tra l'istanza i e d 2,1 0 l'istanza j d 3,1 d 3,2 0 ⋮ ⋮ ⋮ ⋮ ⋮ d(j,i)=d(i,j) per cui si rappresenta d  n ,1 d  n , 2   0 solo metà matrice. 7  Distanze e tipi di dati d(i,j) misura la “dissimilarità” o “distanza” tra le istanze i e j. La definizione di d cambia molto a seconda del tipo di dato degli attributi – Intervallo – Nominali (e in particolare binari) – Ordinali... e ovviamente si possono avere situazioni in cui attributi diversi hanno tipo diverso! 8  Dati di tipo intervallo e normalizzazione Il primo passo per definire una misura di distanza su dati di tipo intervallo, è normalizzare i dati. Quasi sempre, si vuole che i vari attributi pesino in maniera uguale. – Esempio : una serie di istanze che rappresentano città Attributi: temperatura media (gradi centigradi) e popolazione (numero di abitanti) Il range di valori della popolazione è molto più ampio, ma si vuole che questo attributi non conti proporzionalmente di più Ci sono vari modi per normalizzare i dati. 9  Normalizzazione (1) Zero-score normalization – Per ogni attributo f, calcolo la media mf delle xif 1 m f =  x 1f  x 2f ⋯ x nf  n – Calcolo lo scarto assoluto medio 1 s f = ∣x 1f −m f ∣∣x 2f −m f ∣⋯∣x nf −m f ∣ n – Ottengo il valore zif normalizzato come x if −m f z if = sf In alternativa, – sf = squarto quadratico medio più sensibile ad outliers 10  Normalizzazione (2) Mix-man normalization x if −min i x if vif = max f x if −min f x if – ancora più sensibile ad outliers Si vuole sempre normalizzare? – non sempre.. –...e anche quando si vuole normalizzare, può essere desiderabile dare a un attributo peso maggiore che a un altro. 11  Distanza su dati di tipo intervallo Distanza di Manhattan d m i , j =∣x i1− x j1∣∣x i2− x j2∣⋯∣x ip− x jp∣ Distanza euclidea d e i , j =  x i1− x j1   x i2 − x j2  ⋯ x ip− x jp  2 2 2 Comunque si definisca una distanze, è bene che abbia alcune proprietà generali: – d(i,j) ≥ 0 – d(i,i) = 0 – d(i,j) = d(j,i) (simmetria) – d(i,j) ≤ d(i,k) + d(k,j) (disuguaglianza triangolare) 12  Distanza su dati di tipo binario (1) Per calcolare la distanza tra l'istanza i e j, sia data la seguente tabella di contingenza – In riga h, colonna k sta il numero di attributi per cui l'istanza i ha valore h e l'istanza j ha valore k Object j 1 0 Object i 1 a b 0 c d 13  Distanza su dati di tipo binario (2) Attributi simmetrici – quando valori positivi e negativi contano allo stesso modo Attributi asimmetrici – quando valori positivi sono più importanti di valori negativi – ad esempio il risultato di un test su una malattia Simple matching distance per attributi simmetrici bc d i , j= abcd Distanza di Jaccard per attributi asimmetrici bc d i , j= abc 14  Distanza su dati di tipo binario (3) Esempio Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4 Jack M Y N P N N N Mary F Y N P N P N Jim M Y P N N N N Gender è un attributo simmetrico, gli altri sono asimmetrici. Supponiamo di calcolare la distanza solo sulla base degli attributi asimmetrici – Se Y e P equivalgono a 1 e N equivale a 0, abbiamo 01 d  jack , mary= =0.33 201 11 d  jack , jim= =0.67 111 12 d  jim , mary= =0.75 112 15  Distanza su dati di tipo nominale Una semplice estensione del caso binario – l'attributo può assumere più di due valori. Metodo 1: matching semplice – m: numero di attributi che corrispondono – p: numero totale di attributi p−m – distanza: d i , j= p Metodo 2 : trasformazione in attributi binari – Si trasforma una variabile nominale con N valori possibili in una serie di N variabili binarie asimmetriche. – La variabili binaria numero i è a 1 se la variabile nominale corrispondente assume il valore i, altrimenti è a 0. 16  Distanza su dati di tipo ordinale Una variabile nominale in cui è presente un ordine tra i valori Può essere trattata come un variabile di tipo intervallo – Si rimpiazza xif con la sua posizione posizione rif nella relazione di ordinamento. I possibili valori di rif vanno da 1 a Mf, il numero di possibili valori di xif. – Si normalizza rif con il metodo min-max ottenendo r if −1 z if = M f −1 – Si calcola la distanza con i metodi visti per gli attributi di tipo intervallo. 17  Distanza su valori di tipo misto In generale una istanza può contenere valori di vario tipo. La dissimilarità tra due istanze è allora ottenuta combinando i metodi visti prima – Non esiste un metodo che vada sempre bene per effettuare la combinazione – In generale, non appena si ha più di un attributo ci sono varie possibili scelte, riguardanti il peso che ogni attributo può avere nel calcolo complessivo della dissimilarità – Il tutto è fondamentalmente un processo soggettivo. 18 Classificazione degli algoritmi di raggruppamento 19  Principali approcci al clustering (1) Algoritmi di partizionamento: dati un insieme di n istanze e un numero k, divide le istanze in k partizioni. – Usa tecniche di rilocazione iterativa per spostare le istanze da una partizione all'altra per migliorare la qualità dei cluster. Algoritmi gerarchici: crea una decomposizione gerarchica dell'insieme di tutte le istanza. – Simile agli alberi zoologici – Si dividono in agglomerativi (se partono da cluster piccoli che fondono tra di loro) o scissori (se partono da un unico grosso cluster che dividono in sotto-cluster). Algoritmi basati sulla densità: piuttosto che utilizzare la distanza tra oggetti, usano il concetto di densità. – Partono da un cluster minimale lo espandono purché la densità (numero di istanze) nelle vicinanze ecceda una specifica soglia. 20  Principali approcci al clustering (2) Algoritmi basati su griglie: prima di iniziare, discretizzano i valori di input in un numero finito di celle che costituiscono una struttura a griglia. Le operazioni successive operano solo su questa griglia. – molto veloci Algoritmi basati su modelli: ipotizzano l'esistenza di un modello per ognuno dei cluster e trovano la miglior disposizione dei cluster che soddisfi il modello. Algoritmi per dati a molte dimensioni. Algoritmi di raggruppamento guidati da vincoli. – vincoli spaziali – raggruppamento semi-supervisionato Molti algoritmi “reali” integrano più di uno schema base. 21 Metodi basati sulle partizioni 22  Metodi basati sulle partizioni Date n istanze e un numero k, partiziona le istanze in k insiemi. – Obiettivo: massimizzare la qualità del raggruppamento Qualità definita di solito in base alle distanze inter- e intra-cluster. Soluzione ottimale: può essere ottenuta enumerando tutte le possibili partizioni.. non è praticabile. Soluzione euristica: basata sulla ricerca di minimi locali. – Usa tecniche di rilocazione iterativa per spostare le istanze da una partizione all'altra allo scopo di migliorare la qualità dei cluster. – Di solito, un punto viene scelto come “centro di gravità” di un cluster, e le varie misure di similarità vengono riferite a questo. – Due sono i metodi più famosi k-means (MacQueen 67) k-medoids (Kaufman & Rousseeuw’87) 23  Metodo k-means Il metodo k-means adotta come centro di gravità di un cluster il suo punto medio. Si tenta di minimizzare l'errore quadratico: k Err =∑ ∑ d e  p , mi  2 i=1 p∈Ci dove mi è il punto medio del cluster Ci. In effetti l'errore non viene mai calcolato esplicitamente, ma l'algoritmo procede come segue: – Scegli k oggetti come centri dei vari cluster come avviene la scelta? varie alternative sono state proposte – Ripeti Assegna ogni oggetto al cluster il cui centro è più vicino Ricalcola i nuovi centri dei cluster – Finché non c'è nessun cambiamento 24  Metodo k-means : esempio 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 25  Pregi e difetti del metodo k-means Pregi – Relativamente efficiente: O(tnk) dove t è il numero di iterazioni. Di solito t e k sono molto minori di n, per cui la complessità si può considerare O(n) – Spesso termina in un ottimo locale. L'ottimo globale si può rincorrere con tecniche standard come annealing simulato o algoritmi genetici. Difetti – Applicabile solo se è possibile definire il centro. Non adatto per dati di tipo categoriale. – Necessità di specificare k in anticipo. – Molto sensibile a rumore e ad outliers – Non adatto per cluster con forme non convesse. 26  Esempio di ottimo locale in k-means I cerchi blu sono le istanze da raggruppare, i cerchi rossi i punti iniziali dei due cluster. – le istanze sono ai 4 vertici di un rettangolo, con un lato corso e uno lungo – i centri iniziali sono i punti medi dei due lati lunghi – la suddivisione ottimale sarebbero costituite da un gruppo con i punti a sinistra e uno con i punti a destra – la soluzione iniziale è un ottimo locale, quindi l'algoritmo termina con un gruppo con i punti in basso, uno con i punti in alto. cluster 1 cluster 2 27  Metodo k-medoids (1) Usa come centro di gravità di un cluster l'istanza “più centrale” del cluster stesso. – riduce l'effetto degli outliers – funziona anche con dati categoriali Dato k, l'algoritmo consta dei seguenti passi – Scegli k oggetti come medoidi iniziali – Ripeti Assegna ogni oggetto al cluster il cui medoide è più vicino Considera di sostituire ognuno dei medoidi con un non-medoide. Effettua la sostituzione se questa migliora la qualità del cluster, altrimenti lascia invariato. – Finché non c'è nessun cambiamento 28  Metodo k-medoids (2) Come qualità del cluster si adotta spesso l'errore assoluto k – Err =∑ ∑ d  p , mi  i=1 p∈C i – Ci cluster i-esimo – mi medoide rappresentativo per Ci – d è una opportuna distanza Se l'istanza i è un medoide che viene sostituito col medoide h, l'errore cambia. La variazione dell'errore è n T ih =∑ C jih j=1 dove n è il numero di istanze è Cjih la componente dell'errore relativo alla istanza j 29  Metodo k-medoids (3) 1° caso: j passa dal medoide i ad h 2° caso: j era e rimane assegnato 10 ad un altro medoide 9 10 8 t 9 j 7 8 t 6 j 7 6 5 i h 5 4 3 4 h 2 3 2 i 1 1 0 0 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Cjih = d(j, h) - d(j, i) Cjih = 0 3° caso: j passa dal medoide i a t≠h 4° caso: j passa dal medoide t≠i ad h 10 10 9 9 8 h 8 j 7 7 6 i 6 5 i 5 4 t 4 h j 3 3 2 2 t 1 1 0 0 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Cjih = d(j, t) - d(j, i) Cjih = d(j, h) - d(j, t) 30 Riferimenti bibliografici 67  Bibliografia Jaiwei Han, Micheline Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann – capitolo 8 Ian H. Witten, Eibe Frank. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations. Morgan Kaufmann. – sezione 6.6 68