Ing. Massimo Guarascio. Outline Breve ricapitolazione Presentazione tool Rialto Weka Formato dati...
-
Upload
vitalia-loi -
Category
Documents
-
view
222 -
download
3
Transcript of Ing. Massimo Guarascio. Outline Breve ricapitolazione Presentazione tool Rialto Weka Formato dati...
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