Ing. Massimo Guarascio

OutlineBreve ricapitolazionePresentazione tool

RialtoWeka

Formato datiData Exploration (Rialto e Weka)Data preparation e cleaning (Rialto e Weka)

Ricapitoliamo…Il mondo reale consiste di Concetti

Automobili, Vigili, Norme, … Nel nostro caso, ciò che deve essere appreso

Ad ogni concetto è associabile un insieme di proprietà (features)Colore, Cilindrata, Proprietario, …

Su ogni proprietà è possibile stabilire delle misurazioniColore = rosso, Cilindrata = 50cc, Proprietario = luigi, …

Il Processo di KDD

Selection and Selection and PreprocessingPreprocessing

Data Mining

Interpretation and Evaluation

Data Consolidation

Knowledge

p(x)=0.02

Warehouse

Data Sources

Patterns & Models

Prepared Data

ConsolidatedData

La Nostra ModellazioneLa realtà di interesse è descritta da un insieme di istanze,

raccolte in una tabellaLe tuple (istanze) della tabella sono i concetti che vogliamo

studiareEsempi di concetti

Le colonne (attributi) della tabella rappresentano le caratteristiche degli oggetti che vogliamo studiare

Una variabile è un contenitore per una misurazione di una caratteristica particolare di un oggettoA volte utilizzata anche per indicare un attributo

Cos’è un esempio? Istanza: esempio di concetto

La cosa da classificare, clusterizzare, associare Un esempio individuale e indipendente di concetto target Caratterizzato da un insieme predeterminato di attributi

Input ad uno schema di learning: un insieme di istanze (dataset) Rappresentato da una singola relazione/tabella

Rappresentazione piuttosto povera Non si possono esprimere relazioni tra oggetti

La più tipica nel data mining

Istanze, attributi, misurazioni

Tid Refund Marital Status

Taxable Income Cheat

1 Yes Single 125K No

2 No Married 100K No

3 No Single 70K No

4 Yes Married 120K No

5 No Divorced 95K Yes

6 No Married 60K No

7 Yes Divorced 220K No

8 No Single 85K Yes

9 No Married 75K No

10 No Single 90K Yes 10

Attributi

Istanze

Caricare i dati in RialtoLive Demo

Weka

ExplorerNella sezione in alto sono visibili le operazioni disponibili

Preprocessing

Distribuzioni in funzionedella classe selezionata

Apertura Dataset

Attributi del dataset

Tipo di Filtro da applicare

Tipi di attributiVariabili Discrete (simboliche)

NominaliCategoricheOrdinaliBinarie

Variabili ContinueInterval-Based (valori interi)Ratio-Scaled (valori reali)

Misure su Scale NominaliMisurazioni qualitativeVariabili Nominali

Un’etichetta da associare per l’identificazione L’attributo Nome può assumere valori: giuseppe, antonio, luigi, … Il codice fiscale di ogni persona è unico

Variabili CategorichePer riferirsi a gruppi di coseLa misura può essere condiviso da più oggetti

Colore: rosso, giallo, bluAnche un numero può essere una variabile categorica!

Il Codice di avviamento postale è condiviso da tutte le persone appartenenti alla stessa città

Non è associata una nozione di ordineNon c’è un criterio per stabilire una differenza (quantitativa) tra gli

elementi

Misure su scale numericheEsprimono misure quantitativeMisurazioni Basate su intervalli

I valori provengono da un range continuoE.g.: Temperatura, Non c’è (apparente) correlazione tra i valori

Misurazioni Ratio-ScaledLe misure esprimono proprietà

La quantità di denaro in una macchina per il caffè è un multiplo dell’unità minima che si può inserire

Una misurazione fisica che dipende dal tempo t (in secondi): e-t

Variabili BinarieSimmetriche (dicotomiche)

Sesso: Maschio/FemminaAsimmetriche

Responso: SI/NO, Vero/Valso, 1/0

Le proprietà dei datiIl tipo di un attributo dipende da quali proprietà possiede:

distinguibilità: = Ordine: < > Additività: + - Moltiplicabilità: * /

Attributi nominali: distinguibilità

Attributi ordinali: distinguibilità, ordine

intervalli: distinguibilità, ordine, additività

Ratio: tutte le proprietà

Tipi di dati in RialtoDiscreti

NominalString

NumericiDoubleInteger

Collections Events: discrete values Contexts: numeric properties

Perché c’è bisogno di specificare i tipi?D: Perché gli algoritmi di learning devono sapere il tipo

degli attributi?R: per poter effettuare i confronti appropriati, e

apprendere i concetti significativiOutlook > “sunny” non ha senso, mentre Temperature > “cool” oppure Humidity > 70 ha senso

Weka DatasetRappresentazione:

Su file: formato ARFFIn Weka: Instances

Il formato arff ha due distinte sezioniIntestazione (Metadati)

@relation (nome della relazione) @attribute (lista degli attributi)

Corpo @data (le istanze)

ARFF: tipi di dati

Numeric, Real @attribute <name> numeric @attribute <name> real

Nominal Specification, lista di valori: @attribute <name> {<nominal-name1>, <nominal-name2>,…}

String: @attribute <name> string

Date: @attribute <name> date [<date-format>]

Relational @attribute <name> relational

<further attribute definitions>

@end <name>

Esempio di file ARFF

WekaSono disponibili quattro modalità

Simple CLI Linea di comando

Explorer Versione grafica di base

Experimenter Parte sperimentale con collegamento a JDBC

KnowledgeFlow Versione drag and drop

Note sul formato sparso

I valori di default (ad esempio 0) non sono rappresentatiNon ci sono cambiamenti a livello di headerC’è una diversa specificazione per il corpo del file

Standard

Sparse

Esistono altri tipi di dati?Si

TestoGrafiDati spazio-temporali

In genere, molti di questi possono essere riportati nel formato descritto in precedenzaNon è vero (o conveniente) in generale

Document DataOgni documento diventa un vettore di termini,

Un termine è un attributo (componente) del vettoreIl valore di ogni componente è la frequenza del termine nel

documento

Document 1

season

timeout

lost

win

game

score

ball

play

coach

team

Document 2

Document 3

3 0 5 0 2 6 0 2 0 2

0

0

7 0 2 1 0 0 3 0 0

1 0 0 1 2 2 0 3 0

Dati transazionaliCoinvolge insiemi

Si può trasformare nel formato tabellare

TID Items

1 Bread, Coke, Milk

2 Beer, Bread

3 Beer, Coke, Diaper, Milk

4 Beer, Bread, Diaper, Milk

5 Coke, Diaper, Milk

GrafiGrafo dei links HTML

5

2

1

2

5

<a href="papers/papers.html#bbbb">Data Mining </a><li><a href="papers/papers.html#aaaa">Graph Partitioning </a><li><a href="papers/papers.html#aaaa">Parallel Solution of Sparse Linear System of Equations </a><li><a href="papers/papers.html#ffff">N-Body Computation and Dense Linear System Solvers

Data ExplorationÉ possibile esplorare i dati sia in maniera visuale (usando

tabelle e grafi) o numericamente (usando statistiche riassuntive)

Si inizierà utilizzando dapprima un’analisi visuale

Data ExplorationEstrarre informazioni dal datasetEsaminare le relazioni tra gli attributiIdentificare interessanti dataset di osservazioneIpotizzare possibili relazioni tra gli attributi la variabile

target se possibile

VisualizzazioneÉ uno strumento estremamente potente

si possono analizzare datasets di grosse dimensionisi possono determinare tendenze e statistiche generalisi possono determinare outliers/patterns inusuali

EsempioSia dato il seguente insieme di valori contenuto nel file

exam_scores.csv :

192 160 183 136 162 165181 188 150 163 192 164184 189 183 181 188 191190 184 171 177 125 192149 188 154 151 159 141171 153 169 168 168 157160 190 166 150

IstogrammiUn grafico che mostra la distribuzione dei valori per gli

attributi dividendo i possibili valori in bins e che mostra il numero di oggetti che rientrano in ogni bin

E’ possibile sostituire la frequenza assoluta con la frequenza relativa. Ciò permette di confrontare diversi gruppi di diverse dimensioni.

La corrispondente tabella è spesso chiamata distribuzione di frequenza.

EsempioCostruire un istogramma per i risultati degli esami

usando bin di dimensione 10 nell’intervallo 120 , 200.

EsempioCostruire un istogramma per i risultati degli esami

usando bin di dimensione 10 nell’intervallo 120 , 200.

Soluzione:Exam Score Histogram

Exam Scores

Fre

qu

en

cy

120 140 160 180 200

02

46

81

01

2

Istogrammi in RialtoCambiare prospettiva:

Data Perspective

Istogrammi in Weka

Diagrammi di ParetoDiagammi a barre distanziateUn assortimento di eventi presenta pochi picchi e molti elementi comuni

6

22

13

2

5

Rosso Verde Bianco Nero Grigio

AerogrammiRappresentazioni a tortafrequenza della distribuzioni

Verde

Bianco

Nero

Grigio

Rosso

WebVisualizzano correlazioni tra

valori simbolici

Diagrammi polari

Rappresentano fenomeni cicliciE.g., concentrazione delle

vendite nell’arco settimanale

0%

5%

10%

15%

20%

25%

Lunedi'

Martedi'

Mercoledi'

Giovedi'

Venerdi'

Sabato

Coordinate parallele

Per rappresentare relazioni con dati ad alta dimensionalità Un asse per ogni attributo I valori sugli assi

Un oggetto è rappresentato come una linea

Sepal Length

5.1

sepal length

sepal width

petal length

petal width

5.1 3.5 1.4 0.2

Sepal Length

5.1

Sepal Width

3.5

sepal length

sepal width

petal length

petal width

5.1 3.5 1.4 0.2

Sepal Length

5.1

Sepal Width

Petal length

Petal Width

3.5

sepal length

sepal width

petal length

petal width

5.1 3.5 1.4 0.2

1.4 0.2

5.1

3.5

1.40.2

Visualizzare coppie di datiSi prenda ora in considerazione il dataset

exams_and_names.csv, il quale contiene i risultati di 2 due esami distinti per uno studente

Uno studente è identificato da un IDSi vuole ora valutare una possibile correlazione fra i due

attribuitiCome fare?

Scatter plotVisualizza la dispersione

100 120 140 160 180 200

10

01

20

14

01

60

18

02

00

Exam Scores

Exam 1

Exa

m 2

Data ExplorationÉ possibile esplorare i dati sia in maniera visuale (usando

tabelle e grafi) o numericamente (usando statistiche riassuntive)

Si passeranno in rassegna le principali misure statistiche

Sommario delle statisticheLe principali statistiche di interesse sono:

Misure di posizione Percentili Media Mediana

Misure di dispersione Range Varianza, deviazione standard Distanza interquartile

Misure di correlazione Covarianza Correlazione

Media AritmeticaPer effettuare la correzione di

errori accidentalipermette di sostituire i valori di

ogni elemento senza cambiare il totale Sostituzione di valori NULL

Monotona crescente

n

iix

nx

1

1

xxkxkn

n

ii

1

1

Mediana Il valore centrale in un insieme

ordinato di datiRobusta

poco influenzata dalla presenza di dati anomali

1 7 12 23 34 54 68

3.21x

23M

ModaMisura della frequenza dei dati

a a b b c c a d b c a e c b a a

moda = a (f = 6)Significativo per dati categoriciNon risente di picchiMolto instabile

Range, Deviazione media Intervallo di variazione

Scarti interquantili

Scarto medio assoluto

Scarto medio assoluto dalla mediana In generale, S.5 Sn

r = max-min

ppp xxr 100

n

iin xx

nS

1

1

n

iiM Mx

nS

1

1

Varianza, deviazione standardmisure di mutua variabilità tra i

dati di una serie Devianza empirica

Varianza

Coefficiente di variazione misura relativa

n

ii xx

ns

1

22 1

n

ii xxdev

1

2

x

sV

EsempioCalcolare le deviazione standard per questo insieme di valori:

2 10 22 43 18

Misure di correlazioneCovarianza

Correlazione

n

iii yyxx

nyx

1

))((1

),(

yxxy ss

yxr

),(

Y

X

Y

X

Y

X

Y

X

r = -1 r = -.6

r = +.3r = +1

Correlazione (r)

EsempioAssociare ogni grafico al corretto valore di correlazione

Scelte: r=-3.20, r=-0.98, r=0.86, r=0.95, r=1.20, r=-0.96, r=-0.40

0

20

40

60

80

100

120

140

0 5 10 15 20 25

X

Y

0

20

40

60

80

100

120

140

0 5 10 15 20 25

X

Y

0

20

40

60

80

100

120

140

0 5 10 15 20 25

X

Y

0

20

40

60

80

100

120

140

0 5 10 15 20 25

X

Y

0

20

40

60

80

100

120

140

0 5 10 15 20 25

X

Y

A) B) C)

D) E)

Esempio

Che valore di correlazione

ci aspettiamo per i campi

esami contenuti nel file

exams_and_names.csv?

100 120 140 160 180 200

10

01

20

14

01

60

18

02

00

Exam Scores

Exam 1

Exa

m 2

Mediana

Primo Quartile

Min

Max

Secondo Quartile

Rappresentano il grado di dispersione o variabilità

dei dati (w.r.t. mediana e/o media) la simmetria la presenza di valori anomali

Le distanze tra i quartili definiscono la dispersione dei dati

Box PlotsInventati J. TukeyPermettono di riassumere la distribuzione dei dati

outlier

10th percentile

25th percentile

75th percentile

50th percentile

10th percentile

EsempioUtilizzare i BoxPlot per confrontare i risultati del primo

esame con quelli del secondo nel file exams_and_names.csv

EsempioUtilizzare i BoxPlot per confrontare i risultati del primo

esame con quelli del secondo nel file exams_and_names.csv

Soluzione:

Exam 1 Exam 2

10

01

20

14

01

60

18

0

Exam Scores

Exa

m S

core

Rialto mette a disposizione diverse tipologie di grafici utili per la fase di data exploration.

In tal senso tool interessanti sono il Segment Viewer e la Confusion Matrix disponibili nella Data Perspective

Utilizzare VariabiliSparsità

Mancanza di valore associato ad una variabile Un attributo è sparso se contiene molti valori nulli

Monotonicità Crescita continua dei valori di una variabile

Intervallo [-, ] (o simili) Non ha senso considerare l’intero intervallo

Outliers Valori singoli o con frequenza estremamente bassa Possono distorcere le informazioni sui dati

Dimensionalità Il numero di valori che una variabile può assumere può essere estremamente alto

Tipicamente riguarda valori categoriciAnacronismo

Una variabile può essere contingente: abbiamo i valori in una sola porzione dei dati

L’Influenza (bias)Un fattore esterno significativo e rilevante nei dati

Comporta problemi (espliciti o impliciti) nei dati Il valore della variabile Velocità in una tabella Infrazioni è alto

Il problema è sistematicoAppare con una certa persistenza

Il misuratore della velocità è tarato male Il problema può essere trattato

Il valore è suscettibile di una distorsione, che deve essere considerata Considera solo i valori che vanno oltre una certa tolleranza

Comprensione dei dati QuantitàNumero di istanze

Regola empirica: 5,000 o piùSe sono di meno, i risultati sono meno affidabili

Numero di attributiRegola pratica: per ogni campo, 10 (o più) istanzeSe ci sono più campi, si deve utilizzare riduzione e selezione di

dimensionalitàNumero di esempi (nella classificazione)

Regola pratica: >100 per ogni concettoSe i dati sono sbilanciati, si può (deve) utilizzare il

campionamento stratificato

Problemi con i datiCampi obsoleti o ridondantiMissing values Outliers Dati non direttamente utilizzabili per l’estrazione di

modelli di miningValori inconsistenti.

EsempioQ: Quali problemi presenta il campo ZIP Code?

EsempioQ: Quali problemi presenta il campo ZIP Code?

Il soggetto 1002 presenta un valore anomalo (canadian customer)

EsempioQ: Quali problemi presenta il campo ZIP Code?

Il soggetto 1002 presenta un valore anomalo (canadian customer)

Per il soggetto 1004 il campo è stato inserito senza il prefisso “0”

Esempio 2Q: Quali altri problemi possono essere individuati nella

tabella presentata?

Esempio 2Q: Quali altri problemi possono essere individuati nella

tabella presentata?Il soggetto 1003 ha un valore mancanteIl soggetto 1003 è probabilmente un outlier: 1.000.000 è un

valore inusualeIl soggetto1002 presenta un errore: entrate negative!Il soggetto 1005 ha un valore anomalo

Probably denoting a missing value in legacy jargon

Esempio 2Q: Altri problemi?

Il soggetto 1001 ha un’età con valore “C”dovuto probabilmente ad un problema di integrazione dei dati

Il soggetto 1004 ha età pari “0” Probabilmente denota un valore mancante

Esempio 2Q: Altri problemi?

Qual è il significato di “S” nei soggetti 1003 e 1004?

Data CleaningTrattamento di valori anomaliTrattamento di outliersTrattamento di tipi impropri

Valori AnomaliValori mancanti

NULL

Valori sconosciutiPrivi di significato

Valori non validiCon valore noto ma non significativo

Valori NULLI valori mancanti possono apparire in molte forme:

<empty field> “0” “.” “999” “NA” … I valori vanno standardizzati (e.g., utilizzando il simbolo

NULL)Trattamento di valori nulli:

Ignorare i record con valori nulliTrattare il valore null come un valore separatoImputare: sostituire il valore null con altri valori

Valori nulli: esempioUn valore può essere

mancante perché non registrato o perché è inapplicabile

Per Jane non è registrato, mentre per Joe o Anna dovrebbe essere considerato Non applicabile

I valori null possono essere inferiti

Nome Età Sesso Incinta ..

Mary 25 F N

Jane 27 F -

Joe 30 M -

Anna 2 F -

Pronto soccorso Ospedale

Trattamento di valori nulliUtilizzando media/mediana/modaPredicendo i valori mancanti utilizzando la distribuzione dei valori

non nulliSegmentando i dati (tramite le distribuzioni di altre variabili) e

utilizzando misure statistiche (media/moda/mediana) di ogni segmento

Segmentando i dati e utilizzando le distribuzioni di probabilità all’interno dei segmenti

Costruendo un modello di classificazione/regressione e utilizzando il modello per calcolare i valori nulliIn dati numerici il trattamento può influenzare la

distribuzione

Rimozione di OutlierOutliers = Near-range values, against the trend of the remaining

dataDifferente significato per gli outliers

Valido: il salario di un amministratore delegatoRumore: Età = 200

DetectionRimozione

ClusteringCurve-fittingTest di ipotesi con un modello precalcolato

Metodi grafici per l’identificazione di OutlierIstogrammi

Metodi grafici per l’identificazione di OutlierScatter Plots

Metodi numerici per l’identificazione di OutlierNormalizzazioni

E.g., z-scoreOutliers: esibiscono valori pi alti di 3 (o più bassi di -3)

nel z-scorePercentili

interquartile range (IQR) Misura la variabilità

Più robusta della deviazione standard. IQR = Q3 − Q1

Un valore è un outlier se: Se è situato a1.5(IQR) o più in basso di Q1, Se è situato a1.5(IQR) o più in alto di Q3.

Un caso particolare: le dateVogliamo trasformare tutte le date in uno stesso formatoProblema molto sentito

e.g. “Sep 24, 2003” , 9/24/03, 24.09.03, etcRappresentazioni categoriche: YYYYMM / YYYYMMDD

YYYYMMDD non preserva gli intervalli: 20040201 - 20040131 /= 20040131 – 20040130Ciò può introdurre bias nei modelli

Opzioni possibiliPossiamo usare:

Unix system date: numero di secondi dal 1970Numero di giorni dal 1 gennaio 1960 (SAS)

Problemi: I valori non sono ovviiNon aiuta l’interpretazioneFacile commettere errori

Un Formato possibile giorni_dal_1_gennaio - 0.5

Date = YYYY + ----------------------------------

365 + 1_se_bisestilePreserva gli intervalliL’anno e il quadrimestre sono facili da estrapolare

Sep 24, 2003 is 2003 + (267-0.5)/365= 2003.7301 (round to 4 digits)

Può essere esteso al tempo

RialtoIl filtro Remove Useless

Conversione: da Nominali a NumericiAlcuni algoritmi possono lavorare con valori nominaliAltri metodi (reti neurali, regressione) lavorano solo con

valori numericiConseguenza: trasformazione

Strategie differenti

Da Binari a NumericiCampi binari

E.g. Sesso=M, F Convertito in Campo_0_1 con valori 0, 1

e.g. Sesso= M Sesso_0_1 = 0 Sesso = F Sesso_0_1 = 1

Da Ordinali a NumericiAttributi ordinati (ad esempio, Giudizio) possono

essere convertiti in numeri che preservano l’ordine naturaleOttimo 10.0Discreto 8Sufficiente 6Insufficente 4Scarso 2

D: Perché è importante preservare l’ordine?R: Per permettere confronti significativi: Giudizio

> 6

Caso particolare: da ordinale a booleano Un ordinale con n valori può essere codificato utilizzando n–

1 attributi booleani Esempio: l’attributo “temperature”

Temperature

Cold

Medium

Hot

Temperature > cold Temperature > medium

False False

True False

True True

Dati originali Dati trasformati

Nominali con pochi valoriAttributi numinali con pochi (regola pratica < 20) valori

e.g. Colore=Rosso, Arancio, Giallo, …, ViolaPer ogni valore v creiamo una variabile binaria C_v , che

assumerà valore 1 if Colore=v, 0 altrimenti

ID Colore …

371 rosso

433 giallo

ID C_rosso C_arancio C_giallo …371 1 0 0

433 0 0 1

CategoriciEsempi:

Codici Postali (~10.000 valori)Codici professionali (7,000 valori)

D: Come gestirli ? R: Ignoriamo gli attributi che si comportano come chiavi (=

con valori unici per ogni record)Gli altri attributi dovrebbero essere raggruppati in gruppi

“naturali” :Esempio: Codici postali regioniProfessioni – selezionare le più frequenti, raggruppare le altre

Trattare le nuove categorie come attributi nominali

DiscretizzazioneUnsupervised vs. SupervisedGlobale vs. LocaleStatica vs. DinamicaTask difficile

Difficile capire a priori qual’è la discretizzazione ottimale bisognerebbe conoscere la distribuzione reale dei dati

Discretizzazione: Vantaggi I dati originali possono avere valori continui estremamente sparsi I dati originali possono avere variabili multimodali I dati discretizzati possono essere più semplici da interpretareLe distribuzioni dei dati discretizzate possono avere una forma “Normale” I dati discretizzati possono essere ancora estremamente sparsi

Eliminazione della variabile in oggetto

Unsupervised DiscretizationNon etichetta le istanzeIl numero di classi è noto a prioriNatural binning

intervalli di identica ampiezzaEqual Frequency binning

intervalli di identica frequenzaStatistical binning

Utilizzando informazioni statistiche media e varianza Quartili

Quante classi?Troppo poche perdita di informazione sulla distribuzione troppe disperde i valori e non manifesta la foma della distribuzione Il numero ottimale C di classi è funzione del numero N di elementi

(Sturges, 1929)

L’ampiezza ottimale delle classi dipende dalla varianza e dal numero dei dati (Scott, 1979)

)(log3

101 10 NC

N

sh

5,3

Natural BinningSempliceOrdino i valori, quindi divido il range di valori in k parti della stessa

dimensione

l’elemento xj appartiene alla classe i se

xj [xmin + i, xmin + (i+1))

Puo` produrre distribuzioni molto sbilanciate

k

xx minmax

Natural binning

Ampiezza dell’intervallo prefissata

[64,67) [67,70) [70,73) [73,76) [76,79) [79,82) [82,85]

Valori della temperatura: 64 65 68 69 70 71 72 72 75 75 80 81 83 85

2 2

Count

42 2 20

Il natural binning può produrre raggruppamenti

[0 – 200,000) … ….

1

Count

Stipendi in un’azienda

[1,800,000 – 2,000,000]

Esempio =(160-100)/4 = 15classe 1: [100,115)classe 2: [115,130)classe 3: [130,145)classe 4: [145, 160]

Caratterizza il prezzo di Bud

Non caratterizza il prezzo di Becks

Bar Beer Price

A Bud 100A Becks 120C Bud 110D Bud 130D Becks 150E Becks 140E Bud 120F Bud 110G Bud 130H Bud 125H Becks 160I Bud 135

Equal Frequency BinningOrdino e Conto gli elementi, quindi definisco il numero di intervalli

calcolando

Dove N è il numero di elementi del campione

l’elemento xi appartiene alla classe j se

j f i < (j+1) f

Non sempre adatta ad evidenziare correlazioni interessanti

k

Nf

Frequency binning

Altezza identica= 4 (tranne che per l’ultimo intervallo)

[64 .. .. .. .. 69] [70 .. 72] [73 .. .. .. .. .. .. .. .. 81] [83 .. 85]

Valori di temperatura: 64 65 68 69 70 71 72 72 75 75 80 81 83 85

4

Count

4 42

VantaggiPreferita perché evita i raggruppamentiIn aggiunta:

Non separa valori frequenti ai bordi degli intervalliCrea intervalli specifici per valori speciali (e.g. 0)

Esempio f = 12/4 = 3classe 1: {100,110,110}classe 2: {120,120,125}classe 3: {130,130,135}

classe 4: {140,150,160}

Non caratterizza il prezzo di Becks

Bar Beer Price

A Bud 100A Becks 120C Bud 110D Bud 130D Becks 150E Becks 140E Bud 120F Bud 110G Bud 130H Bud 125H Becks 160I Bud 135

Supervised DiscretizationLa discretizzazione ha un obiettivo quantificabileIl numero di intervalli non è noto a prioriEsempio: voglio che in ogni intervallo ci siano almeno tre

valori identici per un altro attributo

64 65 68 69 70 71 72 72 75 75 80 81 83 85Yes No Yes Yes Yes No No Yes Yes Yes No Yes Yes No

64 85

Supervised Discretization: ChiMergeBottom-up Inizialmente, ogni valore è un intervallo a se’ Intervalli adiacenti sono iterativamente uniti se sono similiLa similitudine è misurata sulla base dell’attributo target, contando quanto i

due intervalli sono “diversi”

ChiMerge: criterio di similitudineBasato sul test del Chi quadrok numero di valori differenti dell’attributo targetAij numero di casi della j-esima classe nell’i-esimo intervalloRi numero di casi nell’i-esimo intervallo ( )

Cj numero di casi nella j-esima classe ( )

Eij frequenza attesa di Aij (Ri* Cj /N)

k

j ijA1

2

1i ijA

Reminder: test del Chi QuadroObiettivo: data una tabella di

contingenza, verificare se righe e colonne sono indipendentiPer un dato elemento in classe

i,j la sua probabilità è pij

Se righe e colonne sono indipendenti, allora pij = uivj

Test dell’indipendenzaSe l’indipendenza vale, allora

La statisticaHa una distribuzione del Chi

quadro con (r-1)(c-1) gradi di libertà

1)Pr( )1)(1(,22

0 cr

ConseguenzeDato un valore per (tipicamente, 0.05)

Se la statistica associata ha un

valore maggiore a Il test viene rigettato e le colonne non sono indipendenti

)1)(1(,2

cr

EsempioValori attuali Valori attesi

Test del Chi Quadro per la discretizzazione

Si individua quanto “distinti” sono due intervalli

k-1 gradi di liberta`La significativita` del test è data da un

threshold Probabilita` che l’intervallo in

questione e la classe siano indipendenti

1 2 … K Total1 A11 A12 … A1k R1

2 A21 A22 … A2k R2

Total C1 C2 … Ck N

2

1 1

22 )(

i

k

j ij

ijij

E

EA

EsempioDiscretizzazione w.r.t. Beer threshold 50% confidenzaVogliamo ottenere una discretizzazione

del prezzo che permetta di mantenere omogeneita` w.r.t. Beer

Bar Beer Price

A Bud 100A Becks 120C Bud 110D Bud 130D Becks 150E Becks 140E Bud 120F Bud 110G Bud 130H Bud 125H Becks 160I Bud 135

Scegliamo gli elementi adiacenti con Chi-Value minimo

Bud Becks100 1 0110 2 0120 1 1125 1 0130 2 0135 1 0140 0 1150 0 1160 0 1

Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 0.75125 1 0 0130 2 0 0135 1 0 2140 0 1 0

150-160 0 2 1.38629

Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 0.75125 1 0 0130 2 0 0135 1 0 2140 0 1 0150 0 1 0160 0 1 1.38629

Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 0.75125 1 0 0130 2 0 0135 1 0 2140 0 1 0

150-160 0 2 1.38629 Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 0.75125 1 0 0130 2 0 0135 1 0 4

140-150-160 0 3 1.38629

Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 0.75125 1 0 0130 2 0 0135 1 0 4

140-150-160 0 3 1.38629

Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 0.75125 1 0 0

130-135 3 0 6140-150-160 0 3 1.38629

Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 0.75125 1 0 0

130-135 3 0 6140-150-160 0 3 1.38629

Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 2.4

125-130-135 4 0 7140-150-160 0 3 1.38629

Bud Becks Chi Value100 1 0 0110 2 0 1.33333120 1 1 2.4

125-130-135 4 0 7140-150-160 0 3 1.38629

Bud Becks Chi Value100-110 3 0 1.875

120 1 1 2.4125-130-135 4 0 7140-150-160 0 3 1.38629

Tutti i valori sonooltre il 50% di confidenza(1.38)

Considerazioni finaliNatural binning è il metodo più semplice (e va bene nella

maggioranza dei casi)Fallisce miseramente con distribuzioni sbilanciate)

Frequency binning può dare risultati miglioriMa non può essere utilizzato con tutte le tecniche

La discretizzazione supervisionata è particolarmente importante per l’analisi delle dipendenzeAlcuni algoritmi (Naïve Bayes) richiedono la

discretizzazione