17 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni Gruppo 2Gruppo 2
Mining the stock market: Mining the stock market: which measure is best?which measure is best?
M.GavrilovM.GavrilovD.AnguelovD.Anguelov
P.IndykP.IndykR.MotwaniR.Motwani
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Dati utilizzatiDati utilizzati
500 titoli dell’indice S&P 500 titoli dell’indice S&P
Anno 1998Anno 1998
Serie di 252 numeri Serie di 252 numeri
Prezzo di aperturaPrezzo di apertura
Classificazione S&P in 62 cluster
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Cosa vedremo…Cosa vedremo…
……clustering dello S&Pclustering dello S&P Data pre-processingData pre-processing
Algoritmo di clusteringAlgoritmo di clustering
Misure di similaritàMisure di similarità
Analisi dei risultati ottenutiAnalisi dei risultati ottenuti
Confronto con lo studio di Jin, Lu, Shi “Similarity Confronto con lo studio di Jin, Lu, Shi “Similarity
measure based on partial information of time seriesmeasure based on partial information of time series””
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
FASE 1: data pre-processingFASE 1: data pre-processing
1.1. Rappresentazione della serieRappresentazione della serie
Raw dataRaw data
First derivativeFirst derivative
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
FASE 1: data pre-processingFASE 1: data pre-processing
2.2. NormalizzazioneNormalizzazione
NoneNone
Z-scoreZ-score
PiecewisePiecewise
v’ = v – μ
σ
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
FASE 1: data pre-processingFASE 1: data pre-processing
3.3. Riduzione delle dimensioniRiduzione delle dimensioni
PCA ( = principal component analysis)PCA ( = principal component analysis)
AggregationAggregation
Fourier transformFourier transform
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
I. Principal Component AnalysisI. Principal Component Analysis
Crea un Crea un nuovo insiemenuovo insieme di attributi di attributi
Dato il vettore XDato il vettore X ii in d dimensioni, trova le d basi in d dimensioni, trova le d basi
ortonormali e ne seleziona M, con M<d, definite ortonormali e ne seleziona M, con M<d, definite principal componentprincipal component ed ordinate in maniera ed ordinate in maniera decrescente secondo la varianzadecrescente secondo la varianza
I dati iniziali diventano una combinazione lineare dei principal component
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
I. PCAI. PCA
Y2
X2
X1
Y1
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
II. AggregationII. Aggregation
Sostituisce i valori di un periodo di giorni Sostituisce i valori di un periodo di giorni BB con la loro con la loro mediamedia
Il periodo Il periodo BB può avere ampiezza diversa può avere ampiezza diversa
(5, 10, 20 giorni)(5, 10, 20 giorni)
La dimensione dei La dimensione dei dati diminuisce di dati diminuisce di un fattore un fattore 1/B1/B
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
III. Trasformata di FourierIII. Trasformata di Fourier
Data una serie temporale s, i coefficienti di Fourier Data una serie temporale s, i coefficienti di Fourier sono numeri complessi definiti come:sono numeri complessi definiti come:
Selezionando pochi coefficienti di Fourier si ottiene Selezionando pochi coefficienti di Fourier si ottiene una buona approssimazione della serie inizialeuna buona approssimazione della serie iniziale
La maggior parte dell’energia è concentrata alle basse La maggior parte dell’energia è concentrata alle basse frequenzefrequenze
Sf = 1/√D ∑t st exp(-j2πft/D) f = 0,……,D-1
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
FASE 2: algoritmo di clusteringFASE 2: algoritmo di clustering
Algoritmo gerarchico agglomerativo (HAC)Algoritmo gerarchico agglomerativo (HAC)
unione binaria di clusterunione binaria di cluster
unione di 2 cluster con la minima distanza unione di 2 cluster con la minima distanza
interclusterintercluster
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
FASE 3: misure di similaritàFASE 3: misure di similarità
Confronto tra classificazione S&P di riferimento (C) e Confronto tra classificazione S&P di riferimento (C) e clustering effettuato con i metodi precedenti (C’)clustering effettuato con i metodi precedenti (C’)
Similarità tra i 2 gruppi di cluster:Similarità tra i 2 gruppi di cluster:
Similarità tra 2 singoli cluster:Similarità tra 2 singoli cluster:
Sim(C,C’) = (∑i maxjSim(Ci ,C’j)) / k
2 |Ci ∩ C’j| |Ci| + |C’j|
Sim(Ci ,C’j) =
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Risultati ottenutiRisultati ottenuti
FD NORM Sim(S&P,HAC) Sim(HAC,S&P)DIM
N
N
N
N
N
N
Y
Y
Y
Y
N
N
Y
Y
Y
Y
all
5
all
10
all
50
all
100
0.183
0.197
0.222
0.211
0.154
0.172
0.290
0.310
0.210
0.210
0.213
0.212
0.198
0.207
0.298
0.310
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Risultati ottenutiRisultati ottenutiFD NORM AggWin Sim(S&P,HAC) Sim(HAC,S&P)
NNNN
NNNN
YYYY
YYYY
NNNN
YYYY
NNNN
YYYY
none51020
none51020
none51020
none51020
0.1830.1920.1930.192
0.2280.2170.2210.215
0.1520.1900.1950.178
0.2880.2250.2300.211
0.2100.2170.2150.213
0.2170.2120.2160.220
0.1970.2110.2170.208
0.2940.2170.2310.211
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Risultati ottenutiRisultati ottenutiFD NORM Freq Sim(S&P,HAC) Sim(HAC,S&P)
NNNN
NNNN
YYYY
YYYY
NNNN
YYYY
NNNN
YYYY
5102050
5102050
5102050
5102050
0.1910.2030.1920.193
0.2150.2100.2210.225
0.2020.1890.1910.190
0.1980.2350.2470.232
0.1970.2040.1960.202
0.2170.2080.2290.224
0.2150.2090.2170.212
0.2090.2360.2400.234
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Risultati ottenutiRisultati ottenuti
101530456075
0.3220.3070.2700.2660.2460.255
0.3380.3460.3300.3460.3160.310
0.3260.3140.2730.2810.2410.257
0.3340.3390.3290.3330.3100.297
FD Sim(S&P,HAC) Sim(HAC,S&P)Win
NNNNNN
101530456075
YYYYYY
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Precision-recall curvesPrecision-recall curves
RELEVANT
NON RELEVANT
RETRIEVED
NOT RETRIEVED
RELEVANT & NOTRETRIEVED
NON RELEVANT & NOTRETRIEVED
NON RELEVANT &RETRIEVED
RELEVANT & RETRIEVED
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Precision-recall curvesPrecision-recall curves
PRECISION = RECALL =+ +
RELEVANT & NOTRETRIEVED
NON RELEVANT & NOTRETRIEVED
NON RELEVANT &RETRIEVED
RELEVANT & RETRIEVED
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Osservazioni generaliOsservazioni generali
Normalizzare i dati in input migliora la qualità dei Normalizzare i dati in input migliora la qualità dei risultatirisultati
FD NORM Sim(S&P,HAC) Sim(HAC,S&P)DIM
Y
Y
N
N
Y
Y
Y
Y
all
50
all
100
0.154
0.172
0.290
0.310
0.198
0.207
0.298
0.310
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Osservazioni generaliOsservazioni generali
Si ottengono migliori risultati con la piecewise Si ottengono migliori risultati con la piecewise normalizationnormalization
10 0.322
0.338
0.326
0.334
FD Sim(S&P,HAC) Sim(HAC,S&P)Win
N
10 Y
FD NORM Sim(S&P,HAC) Sim(HAC,S&P)DIM
N Y
Y Y
all
all
0.222
0.290
0.213
0.298
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Osservazioni generaliOsservazioni generali Utilizzando le first derivative normalizzate della serie Utilizzando le first derivative normalizzate della serie
temporale si ottengono risultati miglioritemporale si ottengono risultati migliori
101530456075
0.3220.3070.2700.2660.2460.2550.3380.3460.3300.3460.3160.310
0.3260.3140.2730.2810.2410.2570.3340.3390.3290.3330.3100.297
FD Sim(S&P,HAC) Sim(HAC,S&P)Win
NNNNNN
101530456075
YYYYYY
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Osservazioni generaliOsservazioni generali Calcolare le first derivative senza normalizzare Calcolare le first derivative senza normalizzare
peggiora le performancepeggiora le performanceFD NORM Sim(S&P,HAC) Sim(HAC,S&P)DIM
N
N
N
N
N
N
Y
Y
Y
Y
N
N
Y
Y
Y
Y
all
5
all
10
all
50
all
100
0.183
0.197
0.222
0.211
0.154
0.172
0.290
0.310
0.210
0.210
0.213
0.212
0.198
0.207
0.298
0.310
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Osservazioni generaliOsservazioni generali
I dati grezzi possono essere ridotti I dati grezzi possono essere ridotti notevolmente senza perdere il loro notevolmente senza perdere il loro contenuto, ma non è possibile ottenere contenuto, ma non è possibile ottenere buoni cluster da essibuoni cluster da essi
Con le tecniche per ottenere buoni cluster Con le tecniche per ottenere buoni cluster non posso ridurre le dimensioni senza non posso ridurre le dimensioni senza perdere le informazioniperdere le informazioni
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
E’ POSSIBILE RIDURRE LE
DIMENSIONI DEI DATI E FARE
BUONI CLUSTER SU DI ESSI?
17 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni Gruppo 2Gruppo 2
Similarity measure based on Similarity measure based on partial information of time partial information of time
series series
X.JinX.JinY.luY.lu
C.ShiC.Shi
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Osservazioni generaliOsservazioni generali
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
Osservazioni generaliOsservazioni generali
Gruppo 2Gruppo 217 marzo 200617 marzo 2006Sistemi informativi per le Sistemi informativi per le
decisionidecisioni
MA LA % DI DATI CONSIDERATI HA
UN IMPATTO DECISIVO SULLA
QUALITA’ DEL CLUSTERING!