Data Reduction & Transformation

(1)

Data Reduction & Transformation

Daniele Contarino

University of Catania

Department of Mathematics and Computer Science (DMI)

Second Part

(2)

Executive summary

 Introduzione

 Regressione lineare

 Modelli log-lineari

 Sampling

 Decomposizione SVD e CUR

 Data Transformation and Discretization

(3)

Data Preprocessing include:

 Data Cleaning

 Data Integration

Data Reduction

Data Transformation

Introduction

(4)

Perché ridurre i dati?

 Volume di dati molto ampi (storage)

 Tempi impraticabili per analisi complesse

 Risultati dei dati compressi  Risultati dati originali

Data Reduction

(5)

Cosa ridurre?

 # di dimensioni (attributi o variabili)

Wavelet, PCA, Attribute subset selection,

Decomposizione SVD, Decomposizione CUR, …

 # di record (osservazioni)

Regression and log-linear model, Nonparametrics

Data Reduction

(6)

Executive summary

 Introduzione

 Regressione lineare

 Modelli log-lineari

 Sampling

(7)

Dati

tabellari Funzione lineare

Linear Regression

(8)

 Una funzione lineare occupa (molto!) meno spazio rispetto a una tabella di dati

 Con regressione lineare intendiamo modellare i dati in maniera tale da adattarsi a una linea retta

 I dati vengono approssimati

Linear Regression

(9)

response or endogenous

variable

Linear Regression

𝒚 = 𝒘𝒙 + 𝒃

predictor or

exogenous variable

regression coefficients

(10)

Come trovare i coefficienti di regressione?

Linear Regression

Metodo dei minimi quadrati

(11)

Funzione lineare tipica:

I migliori coefficienti di regressione vengono trovati imponendo la relazione

𝐴

^𝑡

𝐴𝑥 = 𝐴

^𝑡

𝑏

Method of least squares

𝑨𝒙 = 𝒃

(12)

Esempio

Method of least squares

x y

-5 -6

-4 -5

0 7

4 0

5 3

−6 = −5𝑤

₀

+ 𝑤

₁

−5 = −4𝑤

₀

+ 𝑤

₁

7 = 0𝑤

₀

+ 𝑤

₁

0 = 4𝑤

₀

+ 𝑤

₁

3 = 5𝑤

₀

+ 𝑤

₁

𝒘 ⇒ 𝒘_𝟎 𝒃 ⇒ 𝒘_𝟏

(13)

Method of least squares

𝑨^𝒕𝑨 ⇒ −𝟓 −𝟒 𝟎 𝟒 𝟓

𝟏 𝟏 𝟏 𝟏 𝟏

−𝟓

−𝟒 𝟎 𝟒

𝟏 𝟏 𝟏 𝟓 𝟏𝟏

= 𝟖𝟐 𝟎 𝟎 𝟓

𝑨^𝒕𝒃 ⇒ −𝟓 −𝟒 𝟎 𝟒 𝟓

𝟏 𝟏 𝟏 𝟏 𝟏

−𝟔

−𝟓 𝟕 𝟎𝟑

= 𝟔𝟓−𝟏

𝟖𝟐 𝟎

𝟎 𝟓 ∗ 𝒘_𝟎

𝒘_𝟏 = 𝟔𝟓

−𝟏

𝟖𝟐 𝒘_𝟎 = 𝟔𝟓 𝟓 𝒘_𝟏 = −𝟏

(14)

Method of least squares

𝟖𝟐 𝒘_𝟎 = 𝟔𝟓

𝟓 𝒘_𝟏 = −𝟏 ⇒ 𝒘_𝟎 = 𝟔𝟓

𝟖𝟓 ≅ 𝟎. 𝟕𝟗 𝒘_𝟏 = −𝟏

𝒚 = 𝟎. 𝟕𝟗𝒙 − 𝟏

(15)

Multiple linear regression

𝒚 = 𝒘

_𝟎

𝒙

_𝟎

+ 𝒘

_𝟏

𝒙

_𝟏

+ ⋯ + 𝒃

(16)

Executive summary

 Introduzione

 Regressione lineare

 Modelli log-lineari

 Sampling

(17)

I modelli Log-Lineari solitamente sono usati in presenza di variabili categoriche.

Essi approssimano la distribuzione di probabilità multidimensionali discrete

Log-Linear Models

𝒚 = 𝒆𝒙𝒑 𝒃 + 𝒘

_𝒊

𝒙

_𝒊

(18)

Indichiamo un modello Log-Lineare come saturo quando esso contiene tutti i possibili effetti.

Un modello saturo riproduce sempre tutte le osservazioni raccolte.

Log-Linear Models

(19)

Doppia riduzione:

 Riduzione del # di record

consideriamo solo la possibilità di trovare una

osservazione in un sottoinsieme di attributi discreti

 Riduzione del # di attributi

Si considera un modello parsimonioso tale da non variare in maniera significativa rispetto al modello saturo

Log-Linear Models

(20)

 Le applicazioni posso essere usate insieme, ma solo per casi limitati

 Regressione è computazionalmente pesante per dati ad alte dimensioni ( > 10) a contrario dei modelli log-lineari

 Esempi di applicazioni: SAS^©, SPSS^© e S-Plus

Log-Linear Models vs. Regression

(21)

Executive summary

 Introduzione

 Modelli log-lineari

 Sampling

(22)

Il campionamento riduce il dataset in campione più piccolo di dati casuali.

Sampling

(23)

 Simple random sample without replacement

 Simple random sample with replacement

 Clustering sample

 Stratified sample

Sampling

(24)

 Sia :

 D il dataset originario, con N = |D|

 S il campione da creare, con s= |S| e s < N

 S è costituito da tuple estratte da D

 Ogni tupla ha una probabilità _𝑁¹ di essere estratta

SRSWOR

(25)

 Simile al SRSWOR

 Le tuple vengono registrate e reinserite in D

 Quindi esiste una probabilità che la stessa tupla possa essere di nuovo estratta

SRSWR

(26)

Se il nostro dataset è formato da M cluster

disgiunti, è possibile applicare un SRS(WOR) sui cluster, con M > s.

Il processo può essere inoltre ripetuto applicando sempre un SRS(WOR) sui singoli cluster

Cluster Sample

(27)

Se il dataset D è composto da gruppi disgiunti

(strati) basati su una determinata feature, si può adottare il campionamento stratificato.

Diversamente dal Cluster, si applica SRS su ogni strato,

Stratified Sample

(28)

Sampling Summary

(29)

Executive summary

 Introduzione

 Sampling

 Decomposizione SVD e CUR

(30)

Un altro metodo per ridurre i dati è quello di eliminare gli attributi meno importanti.

Per effettuare questa scelta usiamo delle analisi basate sulla

decomposizione di matrici.

Attribute reduction

(31)

La fattorizzazione SVD (Singular Value

Decomposition) permette di analizzare una

matrice di dati tramite i valori delle matrici che la compongono; tramite quest’ultime è possibile

ridurre la dimensione dei dati

Decomposizione SVD

(32)

La matrice originaria M dei dati viene fattorizzata, in modo tale risulti il prodotto di tre particolari

matrici.

𝑀 = 𝑈Σ𝑉^𝑇

Decomposizione SVD

(33)

 U è la matrice m ^⨉ n con colonne ortonormali

ogni il prodotto in ogni colonna per le altre è uguale a 0 e 𝑈^𝑇𝑈 = 𝐼

 ∑ è la matrice diagonale n ⨉ n

Gli elementi di ^∑ sono chiamati valori singolari di 𝑀

 V è la matrice m ^⨉ n con colonne ortonormali

Decomposizione SVD

(34)

Decomposizione SVD

Romanzi Fantascienza

(35)

Decomposizione SVD

(36)

Decomposizione SVD

Possiamo eliminare la corrispondente riga e colonna rispettivamente in U e V rispetto alla posizione in cui troviamo il minimo valore di ∑

∑ Min value

(37)

Decomposizione SVD

(38)

Decomposizione SVD

(39)

Come calcolare 𝑈, 𝛴 e 𝑉?

Decomposizione SVD

𝑈 è la matrice di autovettori di 𝑀𝑀^𝑇 𝑉 è la matrice di autovettori di 𝑀^𝑇𝑀

𝛴 è la matrice diagonale composta dalla radice quadrata degli autovalori di 𝑀^𝑇𝑀 o di 𝑀𝑀^𝑇

(40)

La fattorizzazione SVD ha come pecca la

creazione della matrice ∑ (che è una matrice sparsa) e la complessità di calcolo delle altre matrici.

La Decomposizione CUR cerca di migliorare questi punti.

Decomposizione CUR

(41)

Il nome CUR è dato dai nomi delle matrici di cui è formato. Sia M la nostra matrice di dati originaria

𝑀 = 𝐶𝑈𝑅

Decomposizione CUR

Matrice m x r con le colonne scelte

casualmente tra quelle di M

Matrice r x n con le righe scelte

casualmente tra quelle di M

Matrice r x r

costruito usando le matrici C e R

(42)

Data Reduction & Transformation – Second Part DMI – University of Catania

Calcolo della matrice U

1. Sia una matrice W formata dall’intersezione delle matrici C e R

2. Si applica SVD su 𝑊 = 𝑋Σ𝑌^𝑇 3. Si calcola 𝛴⁺

4. 𝑈 = 𝑌(Σ⁺)²𝑋^𝑇

Decomposizione CUR

Σ⁺ 𝑖 𝑖 =

0 𝑖𝑓 Σ 𝑖 𝑖 = 0 1

Σ 𝑖 𝑖 𝑖𝑓 Σ 𝑖 𝑖 ≠ 0

(43)

Gli elementi scelti per C e R dovrebbero essere quelli più importanti.

Ma come misurare l’importanza di una riga o di una colonna?

Decomposizione CUR

(44)

Consideriamo il quadrato della norma di Frobenius

Decomposizione CUR

𝒇 = 𝒎_𝒊𝒋^𝟐

𝒊,𝒋

𝒑_𝒊 = 𝒎_𝒊𝒋^𝟐

𝒋 𝒇

𝒒_𝒋 = 𝒎_𝒊𝒋^𝟐

𝒊 𝒇

Colonne Righe

(45)

Executive summary

 Introduzione

 Sampling

 Decomposizione SVD e CUR

 Data Transformation and Discretization

(46)

Obiettivi della trasformazione e discretizzazione dei dati:

 Aumentare l’efficienza del data mining

 Eliminare il rumore

 Create attributi più comprensibili

 Raggruppare i dati in maniera

Data Transformation & Discretization

(47)

 Smoothing

 Costruzione di attributi

 Aggregazione

 Normalizzazione

 Discretizzazione

 Generazione di gerarchie per dati nominali

Data Transformation Stategies

(48)

Meglio usare metri o pollici?

Normalization

Oppure i piedi??

(49)

La scelta di una unità di misura determina

 Del tipo di variabile (binario, intero, float o double)

 Il grado di precisione richiesto

 Il grado di comprensibilità (dip. dalla cultura)

Normalization

(50)

La normalizzazione o standardizzazione (che

hanno significati differenti in statistica) permette di slegarci dall’unità di misura e di rapportare i valori tra 0 e 1.

Normalizzation

(51)

 Min-Max normalization

 Z-score normalization

 Normalization by decimal scaling

Normalizzation methods

(52)

Min-Max Normalization

𝒗^′ = 𝒗 − 𝒎𝒊𝒏

𝒎𝒂𝒙 − 𝒎𝒊𝒏 𝒏𝒆𝒘_𝒎𝒂𝒙 − 𝒏𝒆𝒘_𝒎𝒊𝒏 + 𝒏𝒆𝒘_𝒎𝒊𝒏

1 0

(53)

Min-Max Normalization

𝒗

^′

= 𝒗 − 𝒎𝒊𝒏

𝒎𝒂𝒙 − 𝒎𝒊𝒏

(54)

Z-score Normalization

𝒗′ = 𝒗 − 𝑨 𝝈

Media

Deviazione standard

(55)

Normalization by decimal scaling

𝒗′ = 𝒗 𝟏𝟎 ^𝒋

# di posizioni decimali

(56)

La discretizzazione ha diverse caratteristiche

 Supervised / Unsupervised

 Top-Down (splitting) / Bottom-Up (merging)

Data Discretization

(57)

Il Binning è una tecnica basata sullo spliting in N intervalli specificati (bins)

 Tecnica Top-Down

 Supervised

 Divisione dei bin per larghezza o per frequenza

 Possibilità di ricorsione

Discretization by binning

(58)

 Simile al binning

 Unsupervised (nessuna informazione sulle classi)

 Ogni colonna racchiude un range disgiunto di valori (buckets o bins)

Discretization by Histogram Analysis

(59)

Definizione MANUALE di strutture gerarchiche di attributi nominali (aree geografiche, colori, etc.) è un lavoro lungo e noioso

Si può automatizzare il processo traendo informazioni dallo schema del DB

Concept Hierarchy Generation

(60)

Ordinamento parziale definito dall’utente

Concept Hierarchy Generation

Un ordinamento di attributi (parziale o totale) può essere definito già nella struttura dati.

Es. nel nostro DB è sono presenti gli attributi indirizzo, città, provincia, nazione. All’interno

dello scherma del DB è definita la relazione indirizzo < città < provincia < nazione

(61)

Data Reduction & Transformation – Second Part DMI – University of Catania

Gruppi di dati gerarchici

Concept Hierarchy Generation

L’idea è quella di raggruppare i livelli più bassi, creando dei gruppi gerarchici con grap minimo, e poi ripetere il procedimento sui gruppi superiori usando i gruppi

intermedi.

{Giorgio, Paola, Alfio}  1 A {1A, 1B, 2A}  ITIS

{ITIS, L.Sc., L.Cl, ITG}  IIS Archimede

(62)

Nessuna informazione di ordinamento

Concept Hierarchy Generation

Fornito un DB, senza nessuna informazioni proveniente da terze parti circa l’ordinamento degli attributi, quale possiamo ritenere più significativo?

Consideriamo un DB geografico:

Comuni: # di valori distinti ≃ 8100 Strade: # di valori distinti ≃ 1M

(63)

Nessuna informazione di ordinamento

Concept Hierarchy Generation

Consideriamo quindi come concetto di alto livello

l’attributo che presenta il minor numero di valori distinti.

(64)

Connessioni semantiche

Concept Hierarchy Generation

Un utente poco accurato può inserire in un DB dei dati incompleti; il DB però può ‘suggerire’ dai dati

semanticamente collegati dai dati precedentemente

inseriti dallo stesso utente.

Questo necessità della definizione di uno schema semantico all’interno della struttura.

(65)

1. J. Han M. Kamber J. Pei , Data Mining - Concepts and Techniques, Hogan Kaufmann, Third Ed., 2012

2. A. Rajaraman J. Leskovec J. Ullman, Mining of Massive Dataset, Stanford Univesity, 2013

References

(66)