Mining the stock market:
which measure is best?
M.Gavrilov
D.Anguelov
P.Indyk
R.Motwani
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Dati utilizzati
500 titoli dell’indice S&P
Anno 1998
Serie di 252 numeri
Prezzo di apertura
Classificazione S&P in
62 cluster
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Cosa vedremo…
…clustering dello S&P

Data pre-processing

Algoritmo di clustering

Misure di similarità

Analisi dei risultati ottenuti

Confronto con lo studio di Jin, Lu, Shi “Similarity
measure based on partial information of time series”
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
FASE 1: data pre-processing
1.
Rappresentazione della serie

Raw data

First derivative
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
FASE 1: data pre-processing
2.
Normalizzazione

None

Z-score

Piecewise
17 marzo 2006
v’ =
v–μ
σ
Sistemi informativi per le decisioni
Gruppo 2
FASE 1: data pre-processing
3.
Riduzione delle dimensioni

PCA ( = principal component analysis)

Aggregation

Fourier transform
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
I. Principal Component Analysis
Crea un nuovo insieme di attributi
Dato il vettore Xi in d dimensioni, trova le d basi
ortonormali e ne seleziona M, con M<d, definite
principal component ed ordinate in maniera
decrescente secondo la varianza
I dati iniziali diventano una
combinazione lineare dei principal
component
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
I. PCA
X2
Y2
Y1
X1
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
II. Aggregation
Sostituisce i valori di un periodo di giorni B con la loro
media
Il periodo B può avere ampiezza diversa
(5, 10, 20 giorni)
La dimensione dei
dati diminuisce di
un fattore 1/B
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
III. Trasformata di Fourier
Data una serie temporale s, i coefficienti di Fourier
sono numeri complessi definiti come:
Sf = 1/√D ∑t st exp(-j2πft/D)
f = 0,……,D-1
Selezionando pochi coefficienti di Fourier si ottiene
una buona approssimazione della serie iniziale
La maggior parte dell’energia è concentrata alle basse
frequenze
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
FASE 2: algoritmo di clustering
Algoritmo gerarchico agglomerativo (HAC)

unione binaria di cluster

unione di 2 cluster con la minima distanza
intercluster
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
FASE 3: misure di similarità
Confronto tra classificazione S&P di riferimento (C) e
clustering effettuato con i metodi precedenti (C’)

Similarità tra i 2 gruppi di cluster:
Sim(C,C’) = (∑i maxjSim(Ci ,C’j)) / k

Similarità tra 2 singoli cluster:
Sim(Ci ,C’j) =
17 marzo 2006
2 |Ci ∩ C’j|
|Ci| + |C’j|
Sistemi informativi per le decisioni
Gruppo 2
Risultati ottenuti
FD
NORM
DIM
Sim(S&P,HAC)
Sim(HAC,S&P)
N
N
all
0.183
0.210
N
N
5
0.197
0.210
N
Y
all
0.222
0.213
N
Y
10
0.211
0.212
Y
N
all
0.154
0.198
Y
N
50
0.172
0.207
Y
Y
all
0.290
0.298
Y
Y
100
0.310
0.310
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Risultati ottenuti
FD
NORM
AggWin
N
N
N
N
N
N
N
N
none
5
10
20
0.183
0.192
0.193
0.192
0.210
0.217
0.215
0.213
N
N
N
N
Y
Y
Y
Y
none
5
10
20
0.228
0.217
0.221
0.215
0.217
0.212
0.216
0.220
Y
Y
Y
Y
N
N
N
N
none
5
10
20
0.152
0.190
0.195
0.178
0.197
0.211
0.217
0.208
Y
Y
Y
Y
Y
Y
Y
Y
none
5
10
20
0.288
0.225
0.230
0.211
0.294
0.217
0.231
0.211
17 marzo 2006
Sim(S&P,HAC)
Sistemi informativi per le decisioni
Sim(HAC,S&P)
Gruppo 2
Risultati ottenuti
FD
NORM
Freq
Sim(S&P,HAC)
Sim(HAC,S&P)
N
N
N
N
N
N
N
N
5
10
20
50
0.191
0.203
0.192
0.193
0.197
0.204
0.196
0.202
N
N
N
N
Y
Y
Y
Y
5
10
20
50
0.215
0.210
0.221
0.225
0.217
0.208
0.229
0.224
Y
Y
Y
Y
N
N
N
N
5
10
20
50
0.202
0.189
0.191
0.190
0.215
0.209
0.217
0.212
Y
Y
Y
Y
Y
Y
Y
Y
5
10
20
50
0.198
0.235
0.247
0.232
0.209
0.236
0.240
0.234
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Risultati ottenuti
Win
FD
Sim(S&P,HAC)
Sim(HAC,S&P)
10
15
30
45
60
75
N
N
N
N
N
N
0.322
0.307
0.270
0.266
0.246
0.255
0.326
0.314
0.273
0.281
0.241
0.257
10
15
30
45
60
75
Y
Y
Y
Y
Y
Y
0.338
0.346
0.330
0.346
0.316
0.310
0.334
0.339
0.329
0.333
0.310
0.297
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Precision-recall curves
RETRIEVED
RELEVANT
NOT RETRIEVED
NON RELEVANT
RELEVANT & NOT
RETRIEVED
NON RELEVANT & NOT
RETRIEVED
NON RELEVANT &
RETRIEVED
RELEVANT & RETRIEVED
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Precision-recall curves
RELEVANT & NOT
RETRIEVED
NON RELEVANT & NOT
RETRIEVED
NON RELEVANT &
RETRIEVED
RELEVANT & RETRIEVED
PRECISION =
RECALL =
+
17 marzo 2006
Sistemi informativi per le decisioni
+
Gruppo 2
Osservazioni generali

Normalizzare i dati in input migliora la qualità dei
risultati
FD
NORM
DIM
Sim(S&P,HAC)
Sim(HAC,S&P)
Y
N
all
0.154
0.198
Y
N
50
0.172
0.207
Y
Y
all
0.290
0.298
Y
Y
100
0.310
0.310
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Osservazioni generali
Win

FD
Sim(S&P,HAC)
Sim(HAC,S&P)
10
N
0.322
0.326
10
Y
0.338
0.334
Si ottengono migliori risultati con la piecewise
normalization
FD
NORM
DIM
Sim(S&P,HAC)
Sim(HAC,S&P)
N
Y
all
0.222
0.213
Y
Y
all
0.290
0.298
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Osservazioni generali

Utilizzando le first derivative normalizzate della serie
temporale si ottengono risultati migliori
Win
10
15
30
45
60
75
10
15
30
45
60
75
17 marzo 2006
FD
N
N
N
N
N
N
Y
Y
Y
Y
Y
Y
Sim(S&P,HAC)
0.322
0.307
0.270
0.266
0.246
0.255
0.338
0.346
0.330
0.346
0.316
0.310
Sistemi informativi per le decisioni
Sim(HAC,S&P)
0.326
0.314
0.273
0.281
0.241
0.257
0.334
0.339
0.329
0.333
0.310
0.297
Gruppo 2
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Osservazioni generali

Calcolare le first derivative senza normalizzare
peggiora le performance
FD
NORM
DIM
Sim(S&P,HAC)
Sim(HAC,S&P)
N
N
all
0.183
0.210
N
N
5
0.197
0.210
N
Y
all
0.222
0.213
N
Y
10
0.211
0.212
Y
N
all
0.154
0.198
Y
N
50
0.172
0.207
Y
Y
all
0.290
0.298
Y
Y
100
0.310
0.310
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Osservazioni generali


I dati grezzi possono essere ridotti
notevolmente senza perdere il loro
contenuto, ma non è possibile ottenere
buoni cluster da essi
Con le tecniche per ottenere buoni cluster
non posso ridurre le dimensioni senza
perdere le informazioni
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
E’ POSSIBILE
RIDURRE LE
DIMENSIONI DEI
DATI E FARE
BUONI CLUSTER
SU DI ESSI?
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Similarity measure based on
partial information of time
series
X.Jin
Y.lu
C.Shi
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Osservazioni generali
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
Osservazioni generali
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2
MA LA % DI DATI
CONSIDERATI HA
UN IMPATTO
DECISIVO SULLA
QUALITA’ DEL
CLUSTERING!
17 marzo 2006
Sistemi informativi per le decisioni
Gruppo 2