Riassunto esame Data mining, Prof. Marinai Simone, libro consigliato Mining of massive datasets, J.D Ullman

25/09/2019 Intro DM, K-means

Capacità di analizzare dati << capacità di immagazzinare dati.

Data mining = trasformare i dati in informazione.

KDD (= Knowledge Discovery in Databases): analisi di grandi quantità di dati (in database) finalizzata all’estrazione di conoscenze.

→ → → → → Flow: dati pre-processing data mining post-processing informazioni decisioni.

Fattori importanti

• Big data: grandi quantità di dati.
• Secondary data-analysis: analisi condotte su dati magari non specificatamente destinati a quelle specifiche analisi.
• Data-driven discovery: non ipotesi, ma deduzioni a partire dai dati.

Problemi classici del Data Mining

Metodi descrittivi:

• Clustering: trovare dei supergruppi di elementi simili tra loro all’interno del gruppo di dati.
• Regole associative: regolarità all’interno di transazioni anonime.
• Ricerca di pattern sequenziali: regolarità all’interno di transazioni non anonime in un periodo di tempo ben preciso.

Metodi predittivi:

• Classificazione: dato un insieme di dati, avendo un insieme di attributi tra cui una classe specifica, trovare un modello che permetta di assegnare la classe ad un nuovo dato di classe ignota con facilità.
• Regressione: prevedere il valore di un dato ignoto dato il valore di altri dati noti, assumendo o ipotizzando una dipendenza lineare/non lineare.

K-means

K-means: dato un dataset, restituisce una partizione del dataset in k gruppi di elementi simili tra loro (= con distanza minima dal loro centroide).

c centroide dell’i-esimo cluster i.

Allora c viene calcolato con media distanza dei punti m del cluster i i.

Un algoritmo di clustering spesso precede un altro algoritmo di classificazione, che permette poi di effettuare decisioni.

Concetto di transazione

Un insieme I di oggetti ⊂ Transazione t, insieme di oggetti o tale che = { , , ..., } Insieme di transazioni 1 2.

σ(X) = numero di transazioni contenenti X → ⋂.

Regola associativa: X Y, X Y = insieme vuoto → σ(X →⋃.

Supporto: s(X Y) = Y) / N numero di transazioni che contengono sia X che Y, diviso le transazioni totali → σ(X σ(X) →⋃.

Confidenza: c(X Y) = Y) / numero di transazioni che contengono sia X che Y, diviso quelle che contengono solo le X.

Problema: determinare tutte le regole con supporto e confidenza superiori ad una certa soglia.

Dato che il supporto dipende solo dall’unione dei due itemset X e Y, qualunque loro combinazione mi genera lo stesso supporto.

Dato che il numero di regole è esponenziale con il numero di item, si usa il buonsenso e un algoritmo chiamato Apriori: se un itemset è molto frequente, lo sono anche tutti i suoi sottoinsiemi.

Analogamente, se un itemset è poco frequente, allora lo sono anche tutti i suoi sovrainsiemi.

Ricerca di pattern sequenziali

Ricerca di pattern sequenziali…

Sequenza: S = <i i i > è una lista ordinata di elementi, i quali sono a loro volta 1 2 n …, collezioni di uno o più eventi i = <e , e , e > (informazione ordinata j 1 2 j temporalmente) mentre n è definito come lunghezza della sequenza.

Il supporto di una sottosequenza s è la frazione di sequenze che la contengono.

02/10/2019 Distanza(), similarità()

Data = collezione di oggetti (record, instance) e i loro attributi (field, variable).

Diversi set di operazioni su diversi tipi di dati: distinzione (= o !=), ordine (> o <), addizione (+ o -), moltiplicazione (* o /).

Distinzione tra attributo discreto o continuo.

Attributi binari asimmetrici: attributi binari (0/1) dove solo quelli posti a 1 contano.

Es.: → Test di 100 domande con 4 possibili risposte. A partire da una tabella 100xnumero di studenti con 4 possibili soluzioni per cella, ho una tabella (100x4)xnumero di studenti in cui metto 1 se lo studente i-esimo ha risposto alla domanda j-esima con la risposta A-D corrispondente.

Eseguo questa trasformazione perché l’analisi associativa funziona con variabili di tipo binario e non variabili di altro tipo (come nel nostro caso, valori A-D).

Qualità dei dati

Qualità dei dati: alcune problematiche:

• Rumore (= modifica dei valori originali non voluta dovuta a errori di misura o trasmissione).
• Outliers (= valori anomali, oggetti del dataset non errati ma con un comportamento sostanzialmente diverso dal resto del dataset).
• Dati mancanti (= informazione non raccolta o non applicabile. Posso o ignorarli, o stimarli o eliminarli).
• Dati duplicati (= quando uniamo due dataset eterogenei).

Fasi del pre-processing

Fasi del pre-processing:

• Aggregazione: combinazione di due o più attributi in un unico campo con lo scopo di ridurre la dimensione del problema. Dati aggregati tendono ad avere meno variabilità in quanto hanno tipicamente meno precisione/dettagli.
• Campionamento: usato sia per un’analisi iniziale che finale, spesso utile perché la dimensione del campione è molto inferiore a quella del dataset totale. Il campione deve essere significativo. Es.: campionamento con/senza reinserimento, casuale, stratificato.
• Riduzione della dimensione: gli algoritmi di data mining di solito lavorano → meglio se il numero di attributi non è troppo alto riducendola tramite tecniche di algebra lineare per combinare più attributi assieme ottengo un modello più consistente.
• Selezione di attributi: rimozione di feature non importanti o ridondanti per → diminuire la dimensione del problema necessita conoscenza del caso studio.
• Creazione di attributi: aggiunta di feature importanti che non erano presenti in precedenza.
• Discretizzazione: trasformazione da continuo a discreto di un attributo che altrimenti sarebbe complicato da analizzare.
• Trasformazione di attributi: applicazione, ad esempio, di una funzione a tutti gli elementi di una colonna.

Normalizzazioni possibili (alcune): min-max normalization, z-score normalization.

Misura di similarità e dissimilarità

Misura di similarità e dissimilarità:

• Similarità: misura numerica di quanto due oggetti sono simili, range [0,1].
• Dissimilarità: misura numerica di quanto due oggetti sono diversi, range [0, vario]. La distanza è un esempio molto noto di dissimilarità.

2(, ) = ∑ ( − ) Distanza euclidea: =1 1( ) | | →(, ) = ∑ − Distanza di Minkowski: Casi particolari: r=1, r=2, r=∞ =1.

Nel caso in cui r=1 si ha che la distanza è la somma delle differenze delle componenti: δx δy. In 2D, D = - r=∞.

Nel caso in cui si ha che la distanza coincide con la massima distanza tra le | | − componenti dei punti: =1.

Delle dissimilarità non metriche sono ad esempio: la differenza tra insiemi e la differenza di tempo.

Proprietà della distanza

Proprietà della distanza:

• (, ) ≥ 0, vale 0 solo se a = b.
• (, ) = (, ).
• Triangolarità.

Proprietà della similarità

Proprietà della similarità:

• Similarità(x, y) = 1 se e solo se x = y.
• Similarità(x, y) = similarità(y, x) per ogni x e y.

Similarità tra vettori binari

Similarità tra vettori binari:

È possibile una situazione in cui x e y hanno solo attributi binari: → M = numero di attributi dove x è 0/1 e y è 0/1 bitwise xy + ℎ 00 11 = = Simple Matching Coefficient: + + +00 01 10 11 ℎ →11 11 = = Jaccard Coefficient: usata spesso + +00 01 10 11 nell’ambito di oggetti acquistati (1) e non acquistati (0).

· →(, ) = · Cosine Similarity: dove è il prodotto vettoriale tra x e y ||||∗|||| e ||x|| è la lunghezza dei vettori x e y. È usata nel confronto tra documenti.

(,)(, ) = Coefficiente di correlazione lineare di Pearson: in()*()− 1 ≤ (, ) ≤ 1 (, ) = 0 particolare si ha che: . Se allora (, ) = 0 e si dice che x e y non sono correlate. Si ha quindi che x e y sono = * + legate, si dice, da una correlazione lineare del tipo.

09/10/2019 Corr, cluster e K-means

2∑ (( )−( )) =1 (, ) = 1 − 6 * Correlazione di Spearman: 2 ( −1) dove r(x ) e r(y ) sono dei rank che assegnamo ad ogni elemento delle due sequenze xk k e y con un ordine crescente.

Es.: = (29, 21, 30, 23, 20) Voti in CS = = (25, 20, 29, 18, 19) Voti in Math = = () − ().

CS r(CS) Math r(Math) 29 2 25 2 0 21 4 20 3 1 30 1 29 1 0 23 3 18 5 2 20 5 19 4 1.

2∑ (( )−( )) 2 2 2 2 2 0 +1 +0 +2 +1 6=1 (, ) = 1 − 6 * =1−6* =1−6* = 0. 6252 5(25−1) 96 ( −1) → x e y sono correlate per un fattore 0.625.

A volte gli attributi che stiamo considerando utilizzano scale diverse, o sono proprio completamente diversi. Per avere una corretta comparazione tra gli attributi, dobbiamo:

• Per ogni attributo k-esimo, computare una similarità S nel range [0,1] k.
• Utilizzare dei pesi (valori compresi tra 0 e 1) per stabilire quali attributi sono più importanti.

Clustering

Clustering: trovare dei gruppi di elementi tali che gli elementi all’interno di un gruppo → siano simili che la loro distanza interna sia minima e che la distanza tra elementi di gruppi diversi sia massima.

Applicazioni della cluster analysis:

• Comprensione.
• Rappresentazione.
• Classificazione supervisionata.
• Partizione.
• Risultati di una query.
• Partizione di grafi.

Un “clustering” è un set di cluster.

Due tipologie principali:

• Partizionale: divisione del dataset iniziale in gruppi che formano una partizione dell’insieme di partenza (senso insiemistico).
• Gerarchico: i cluster possono essere anche annidati, rappresentabile da un albero o altra struttura gerarchica.

Ulteriori distinzioni:

• Cl. esclusivi vs non esclusivi: un elemento può o meno appartenere ad un solo cluster.
• Cl. parziale vs completo: si considera tutto il dataset o un suo sottoinsieme.
• Cl. eterogeneo vs omogeneo: differenti forme e dimensioni.
• Cl. fuzzy vs non-fuzzy: ci dice con che probabilità un elemento appartiene ad un cluster.

Tipologie di cluster

Tipologie di cluster:

• Cluster ben separati: cluster in cui gli elementi di un cluster C sono tutti più 1 vicini agli elementi di C piuttosto che agli elementi di altri cluster. 1.
• Cluster basato sul centro: cluster in cui gli elementi di un cluster C sono tutti 1 più vicini al centro del cluster C piuttosto che al centro di altri cluster. 1.
• Cluster basati sulla contiguità: cluster in cui un set di elementi di un cluster C 1 che sono più vicini ai punti del cluster C piuttosto che ad altri elementi di un 1 altro cluster.
• Cluster basati sulla densità: cluster in cui gli elementi sono tutti in regioni ad alta densità. Usati quando sono presenti molto outliers.
• Cluster definiti da funzioni obiettivo: cluster che vengono formati cercando di minimizzare o massimizzare una certa funzione, ad esempio considerando tutti i modi in cui è possibile clusterizzare il dataset e scegliendo quello più efficace secondo i criteri scelti.

K-means pseudo code

K-Means:

Algoritmo di clustering partizionale (restituisce partizioni del dataset), in cui i cluster sono definiti dai loro centroidi. La strategia seguita è assegnare ogni punto al cluster con il centroide più vicino. Richiede come input il numero di cluster desiderati.

K-Means pseudo code:

• Selezionare K punti come centroidi iniziali.
• Repeat.
• Formare K cluster assegnando i punti al cluster col centroide più vicino.
• Ricomputare i centroidi considerando i nuovi punti aggiunti.
• Until tutti i centroidi non cambiano più.

I centroidi sono scelti randomicamente, la vicinanza è definita come distanza Euclidea o altre similarità, il centroide è tipicamente la media dei punti nel suo cluster, tipicamente converge, la maggior parte della convergenza avviene nelle prime iterazioni e quindi si definisce la condizione di “until” come “until relativamente pochi punti cambiano/until i centroidi cambiano poco”.

( * * * ) La complessità è: dove:

• N = numero di punti.
• K = numero di cluster.
• I = numero di iterazioni.
• D = numero di attributi.

Essendo un algoritmo di partizione, il numero di modi in cui è possibile partizionare N (, ) = elementi in K gruppi è dato dal Numero di Stirling di seconda specie: !

Steps dell’algoritmo

Steps dell’algoritmo: …, …, Abbiamo i punti (p , p ) e i centroidi (c , c ). 1 k 1 n.

Assegno i punti ai cluster relativi ai centroidi iniziali e ricomputo i cluster eseguendo la media delle coordinate dei punti per determinare le nuove coordinate dei centroidi.

Ripetere fino a quando i centroidi non cambiano a causa del fatto che c’è stato alcun cambiamento nell’appartenenza dei punti ai diversi cluster.

2 = = ∑ ∑ ( , ) Introduciamo il concetto di =1 ∈ dove c è il punto rappresentativo del cluster i-esimo e x è il punto considerato. i.

Definito K costante, un modo di ridurre il SSE è quello di aumentare il numero di iterazioni dell’algoritmo, in quanto le distanze progressivamente diventano più piccole e quindi il valore di SSE cala.

Se usiamo la distanza Euclidea ad esempio, calcoliamo il centroide come media dei punti appartenenti al suo cluster perché questa scelta rende minimo l’SSE: 21 = ∑ = ∑ ∑ ( , ) ∈ =1 ∈ δ Questo è dimostrabile attraverso la derivata di SSE: e la sua minimizzazione. δ

Se invece usassimo la distanza Manhattan, calcoliamo il centroide come mediana dei punti appartenenti al suo cluster, perché questa scelta rende minimo il SAE. | | = ∑ ∑ ( , ) = ∑ ∑ − =1 ∈ =1 ∈1 che rappresenta la Somma degli Errori Assoluti.

NB.: nel caso in cui due attributi non siano di tipo numerico e si debba calcolare la distanza Euclidea, allora usare questa notazione: ( , ) = 0 = 1 2 1 2 ( , ) = 1 ≠ 1 2 1 2.

Nel caso in cui per esempio si abbia:

P1 0.7 0.3 White P2 0.4 0.2 Red P3 0.7 0.1 Green.

2 2( , ) = ( − ) + ( − ) + ( , )1 2 1 2 1 2 1 2 ( , ) = 0 = ( , ) = 1 ≠ dove ( )2 2 2 = ∑ ∑ ( , ) = ∑ ∑ ( − ) + ( − ) + ( , ) = 1 2 1 2 1 2=1 ∈ =1 ∈ ( )2 2 →= ∑ ∑ ( − ) + ( − ) + ∑ ∑ ( , ) la prima parte si minimizza 1 2 1 2 1 2=1 ∈ =1 ∈ effettuando la media come spiegato sopra, la seconda si minimizza quando ho più → similarità tra colori assegno ad un cluster il colore prevalente dei suoi elementi.

11/10/2019 Centroidi, c. gerarchico

Quanto la scelta dei centroidi iniziali può influenzare il risultato finale?

La possibilità di scegliere un centroide da ogni cluster è molto bassa, data dalla formula: ! != = = = ! ()

Qual’è la soluzione possibile?

• Utilizzare un clustering gerarchico sui cluster per determinare i centroidi iniziali.
• Multiple esecuzioni dell’algoritmo.
• Selezionare più di K centroidi iniziali e poi selezionare quelli altamente significativi a partire da quelli.

Per elaborare i cambiamenti di posizione dei centroidi ad ogni step, essi vanno nominati con indici incrementali per ricalcolare le distribuzioni dei punti nei cluster.

Dopodiché va determinato se i punti assegnati in precedenza vengono spostati di cluster o meno.

Pre-processing possibile:

• Normalizzare i dati.
• Eliminare gli outliers.

Post-processing possibile.