Gruppo 2 17 marzo 2006 Sistemi informativi per le decisioni Mining the stock market: which measure...

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


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


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””


decisionidecisioni

FASE 1: data pre-processingFASE 1: data pre-processing

1.1. Rappresentazione della serieRappresentazione della serie

Raw dataRaw data

First derivativeFirst derivative


decisionidecisioni


2.2. NormalizzazioneNormalizzazione

NoneNone

Z-scoreZ-score

PiecewisePiecewise

v’ = v – μ

σ


decisionidecisioni


3.3. Riduzione delle dimensioniRiduzione delle dimensioni

PCA ( = principal component analysis)PCA ( = principal component analysis)

AggregationAggregation

Fourier transformFourier transform


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


decisionidecisioni

I. PCAI. PCA

Y2

X2

X1

Y1


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


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


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


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) =


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


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


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


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


decisionidecisioni

Precision-recall curvesPrecision-recall curves

RELEVANT

NON RELEVANT

RETRIEVED

NOT RETRIEVED

RELEVANT & NOTRETRIEVED

NON RELEVANT & NOTRETRIEVED

NON RELEVANT &RETRIEVED

RELEVANT & RETRIEVED


decisionidecisioni

Precision-recall curvesPrecision-recall curves

PRECISION = RECALL =+ +

RELEVANT & NOTRETRIEVED

NON RELEVANT & NOTRETRIEVED

NON RELEVANT &RETRIEVED

RELEVANT & RETRIEVED


decisionidecisioni

Osservazioni generaliOsservazioni generali

Normalizzare i dati in input migliora la qualità dei Normalizzare i dati in input migliora la qualità dei risultatirisultati


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


decisionidecisioni


Si ottengono migliori risultati con la piecewise Si ottengono migliori risultati con la piecewise normalizationnormalization

10 0.322

0.338

0.326

0.334


N

10 Y


N Y

Y Y

all

all

0.222

0.290

0.213

0.298


decisionidecisioni


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


NNNNNN

101530456075

YYYYYY


decisionidecisioni


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


decisionidecisioni


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


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


decisionidecisioni



decisionidecisioni

MA LA % DI DATI CONSIDERATI HA

UN IMPATTO DECISIVO SULLA

QUALITA’ DEL CLUSTERING!

Gruppo 2 17 marzo 2006 Sistemi informativi per le decisioni Mining the stock market: which measure...

Documents

Transcript of Gruppo 2 17 marzo 2006 Sistemi informativi per le decisioni Mining the stock market: which measure...