Predicción basada en vecinos Series Temporales Máster en Computación Universitat Politècnica de Catalunya Dra. Alicia Troncoso Lora

1

Contenido Introducción Esquema de predicción directa Predicción basada en vecinos: KW-NN Aplicaciones: Los precios de la energía La demanda de energía Referencias

2

Introducción Técnicas de vecinos cercanos son usuales en problemas de clasificación con atributos nominales Variantes de vecinos cercanos debido a sus buenos resultados Técnicas exitosas en series temporales con patrones periódicos como series temporales económicas, financieras, demanda… 3

Introducción Es uno de los métodos de clasificación más usados por ser muy intuitivo. Consiste en asignar al punto a predecir la clase mayoritaria entre los k ejemplos más cercanos según una determinada métrica. No alcanza un modelo sino que el conjunto de datos de entrenamiento es el modelo. Por eso se le llama “lazy algorithm” o tambien “instance based learning algorithm”. Lazy algorithm significa que realmente no existe fase de entrenamiento para crear un modelo sino que hasta que no llega un dato a clasificar no se pone en marcha el algoritmo de aprendizaje.

Introducción Predecir los n siguientes valores de una serie temporal Yt

Yt+1,…,Yt+n

n es el horizonte de predicción

Encontrar función f: Rm----->Rn tal que (

t+1,…,

t+n)

= f(Yt-1,…,Yt-m) + error

m es el número de valores pasados que se usan en la predicción 5

Esquema de predicción iterada Yt-(m-1) ,…,Yt-2,Yt-1,Yt Yt-(m-2) ,…,Yt-1,Yt, Yt-(m-3) ,…,Yt,

t+1,

t+1

t+1

t+2

t+2

t+3

Desventaja: Con este esquema los errores se van acumulando sobre todo al final del horizonte de predicción 6

Esquema de predicción directa Yt-(m-1),…,Yt-2,Yt-1,Yt

t+1,…, t+n

Ventaja: Con este esquema los errores NO se van acumulando sobre todo al final del horizonte de predicción Desventaja: Con este esquema no se contemplan relaciones entre los valores en el instante de tiempo t, t+1,…, t+n

7

Vecinos Más Cercanos NN: Nearest Neighbours Idea clave: almacenar todos los ejemplos de entrenamiento 1 vecino más cercano (1-NN): Dado un ejemplo no clasificado xq, localiza el ejemplo de entrenamiento más cercano xn, y estima f(xq) como f(xn)

K-vecinos más cercanos (K-NN):

Dado xq, si la función objetivo es discreta (clases) gana la mayoritaria entre sus k vecinos más cercanos Si la función es real se toma el valor medio de sus k vecinos f(xq)=Σi=1k f(xi)/k 8

Vecinos Más Cercanos KW-NN (Vecinos Ponderados) Dar más peso a los vecinos más cercanos f^(xq) = Σi=1,k wi f(xi) / Σi=1,k wi donde wi es una función de la d(xq,xi) y d(xq,xi) es la distancia entre xq y xi (p.e. W(d) = 1/d)

Una variante es el método de Shepard que en vez de usar k vecinos los usa todos 9

1-NN: separación entre clases Entre cada dos puntos de distinta clase, la frontera viene dada por la bisectriz del segmento que los une.

1-NN: diagrama de Voronoi

Vecinos Más Cercanos Diagrama de Voronoi

12

Vecinos Más Cercanos 3-NN

13

Vecinos Más Cercanos 7-NN

14

K-NN: ¿Cómo escoger k? Lo habitual es usar validación cruzada para obtener el valor óptimo Gran influencia

15

K-NN: ¿todos los atributos valen igual? ¿Cómo evitar los atributos irrelevantes?

Ponderando el peso de cada atributo en el cálculo de la distancia dist ( x, y) =

¿cómo calcular los pesos ω?

ωi ( xi − yi ) 2 i

16

k-NN: cálculo de pesos Heurísticas de búsqueda: Algoritmos evolutivos Scatter Search Selección de atributos Ranking de atributos

17

Distancias: continuas Euclidea Manhattan Minkowsky Mahalanobis Camberra Chebichev Chi-cuadrado 18

KW-NN: ¿Todos los vecinos valen lo

mismo?

Podemos ponderar cada vecino según un peso en función de la distancia. Así si {(xi,yi)} i=1..K son los k vecinos de x debemos definir wi en función de d(xi,x) Distintas posibilidades

La estimación se realiza con votos ponderados 19

KW-NN: influencia de ponderar los

vecinos

Representación gráfica de la “clase media” de 10 vecinos con distintas funciones de peso.

20

KW-NN: influencia de ponderar los

vecinos

Representación gráfica de la “clase media” de 10 vecinos con distintas funciones de peso.

21

KW-NN: influencia de ponderar los

vecinos

Representación gráfica de la “clase media” de 10 vecinos con distintas funciones de peso.

22

Predicción basada en KW-NN Yt-(m-1),…,Yt-2,Yt-1,Yt

t+1,…, t+n

Elección del parámetro m: Longitud de la ventana ¿Cuántos datos pasados se necesitan para predecir n valores futuros? 23

Predicción basada en KW-NN Longitud de la ventana Método de los falsos vecinos FNN (“False Nearest Neighbours”) Falsos Vecinos

l1

Futuro

l2

m es tal que el número de falsos vecinos sea mínimo

Radio = l2/l1 Si Radio>Rmax Falsos Vecinos Vecinos Falsos (%)

Pasado

m óptimo

Dimensión de inyección 24

Predicción basada en KW-NN Serie temporal: Precios de la energía eléctrica Vecinos Cercanos Falsos (%) Días anteriores

1

2

3

4

5

6

7

8

9

10

11

12

13

Distancia Euclídea

79.1

56.6

31.8

23.3

20.2

10.1

7.75

2.33

3.1

1.55

0.78

0

0

Distancia Manhattan

79.1

45.7

15.5

3.88

0

0

0

0

0

0

0

0

0

Vecinos Cercanos Falsos (%) Días anteriores

14

15

16

17

18

19

20

21

22

23

24

25

Distancia Euclídea

0.78

0

0

0

0

0

0

0

0.78

0

0

0

Distancia Manhattan

0

0

0

0

0

0

0

0

0

0

0

0

5 días

12 días

Comportamiento irregular: ruido 25

Predicción basada en KW-NN E = Conjunto de training

Número de vecinos ?

min Error E

26

Predicción basada en KW-NN Cálculo del número óptimo de vecinos Distancia Euclídea

Distancia Manhattan

Número de vecinos

Error Relativo Medio (%)

Error Absoluto Medio

Error Cuadrático Medio

Número de vecinos

Error Relativo Medio (%)

Error Absoluto Medio

Error Cuadrático Medio

1

10.2

0.269

0.163

1

10.7

0.289

0.181

2

10.2

0.269

0.163

2

10.7

0.289

0.181

3

10.1

0.264

0.147

3

10

0.272

0.158

4

10

0.264

0.148

4

10

0.27

0.151

5

10.5

0.273

0.155

5

10

0.269

0.149

6

10.8

0.282

0.163

6

10.1

0.273

0.153

7

11.1

0.289

0.169

7

10.3

0.277

0.158

8

11.3

0.294

0.175

8

10.4

0.279

0.159

9

11.6

0.3

0.181

9

10.6

0.283

0.162

10

11.8

0.305

0.186

10

10.7

0.286

0.163

4 vecinos

5 vecinos

27

Predicción basada en KW-NN Pesos? Basados en distancias

αj =

d ( x , v K ( x )) − d ( x , v j ( x )) d ( x , v K ( x )) − d ( x , v1 ( x ))

K-1 pesos

1 = α 1 ≥ ... ≥ α K −1 ≥ α K = 0

28

Predicción basada en KW-NN Error mínimo? fut=

v(Yfut)

?

v(Yfut) es tal que d(Yfut, v(Yfut)) es mínima v(Yfut)? desconocido

v(Ypas)

Si d = distancia Euclídea

Error cuadrático mínimo

Si d = distancia Manhattan

Error absoluto mínimo 29

Aplicaciones KW-NN TÉCNICA DE PREDICCIÓN PRECIOS DE LA ENERGÍA

DEMANDA DE ENERGÍA

RED NEURONAL

ÁRBOL DE REGRESIÓN 30

Aplicación Precios de la energía eléctrica Características de la serie temporal Modelos obtenidos Directa: Distancia Euclídea Distancia Manhattan Iterada: Distancia Euclídea Distancia Manhattan

modelo I modelo II modelo III modelo IV

Resultados Comparación con una Red Neuronal Artificial (RNA)

31

Características de la serie Porcentaje de horas

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

40% 30% 20% 10% 0 1 2 3 4 5 6 7

Precios año 2001

1

3

5

7

9

11 13 15 17 19 21 23

Nº de horas anteriores

Porcentaje de horas

Coeficiente de Correlación

50%

50% 40% 30% 20% 10% 0 1 2 3 4 5 6 7

Precios año 2000

32

Modelos: Predicción directa Modelo I: Longitud de la ventana = 12 número de vecinos = 4 P1,1 … P1,24 … P12,1 … P12,24 P13,1 … P13,24 P2,1 … P2,24 … P13,1 … P13,24 . . . . . . . . . . . . . . . . . . . . .

DISTANCIA EUCLIDEA

P14,1 … P14,24 . . . . . . . . .

Pd-12,1 … Pd-12,24 … Pd-1,1 … Pd-1,24 Pd,1 … Pd,24? Modelo II: Longitud de la ventana = 5 número de vecinos = 5 P1,1 … P1,24 … P5,1 … P5,24

P6,1 … P6,24

P2,1 … P2,24 . . . . . . . . .

P7,1 … P7,24 . . . . . . . . .

… P6,1 … P6,24 . . . . . . . . . . . .

Pd-5,1 … Pd-5,24 … Pd-1,1 … Pd-1,24

DISTANCIA MANHATTAN

Pd,1 … Pd,24? 33

Modelos: Predicción iterada: Modelo III: Longitud de la ventana = 24 número de vecinos = 5

P1,1

Modelo IV: Longitud de la ventana = 24 número de vecinos = 7 … P1,24 P2,1

P1,2 . . .

… P2,1 . . . . . .

P2,2 . . .

Pd-1,1 … Pd-1,24

Pd,1?

Pd-1,2 … Pˆd,1 . . . . . . . . . Pd-1,24 … P ˆd,23

Pd,2? . . . Pd,24?

DISTANCIA EUCLIDEA DISTANCIA MANHATTAN

Predicciones horarias de los precios

Errores se van acumulando en las últimas horas del horizonte de predicción

34

Resultados Los días laborables comprendidos entre marzo y agosto del año 2001 se han usado para determinar la longitud óptima de la ventana deslizante y el número óptimo de vecinos Los días laborables comprendidos entre septiembre y octubre del año 2001 se han usado para validar el algoritmo de predicción basado en KW-NN Las dos terceras partes de los datos han sido elegidas como conjunto de entrenamiento correspondiendo a 6 meses (marzo, abril, mayo, junio, julio y agosto) y una tercera parte como conjunto de test correspondiendo a 2 meses (septiembre y octubre). Septiembre

Octubre

Precio real medio

3.35

3.996

Desviación Estándar

0.43

0.606

35

Resultados PREDICCIÓN DIRECTA

Modelo I

Modelo II

Septiembre

Octubre

Septiembre

Octubre

Error Relativo Medio (%)

6

9.6

8

10.5

Error Absoluto Medio (Cent/KWh)

0.25

0.38

0.33

0.407

Máximo error diario (%)

18

18.6

19.57

20.3

Máximo error horario (%)

66.02

88.08

68.9

90.43

Mínimo error diario (%)

2.07

3.97

1.69

4.458

Mínimo error horario (%)

0.03

0

0.02

0

36

Resultados PREDICCIÓN ITERADA

Modelo III

Modelo IV

Septiembre

Octubre

Septiembre

Octubre

Error Relativo Medio (%)

7.3

11

7.11

11.27

Error Absoluto Medio (Cent/KWh)

0.289

0.427

0.282

0.436

Máximo error diario (%)

15.88

21.66

15.628

21.558

Máximo error horario (%)

75.9

94.7

88.9

93.3

Mínimo error diario (%)

3

4.879

2.89

4.49

Mínimo error horario (%)

0

0

0

0

37

Resultados

Modelo I

Óptima

Modelo II

Óptima

Error Relativo Medio (%)

7.8

5.77

9.25

5.55

Error Absoluto Medio (Cent/KWh)

0.315

0.226

0.368

0.216

Error Cuadrático Medio (Cent/KWh)

0.120

0.114

0.251

0.226

2.5 %

4%

38

Comparación con ANN Arquitectura de la red: Capa de entrada: 24 neuronas Capa intermedia: 24 neuronas Capa de salida:

24 precios de un día

Función de activación: tangente hiperbólica Datos: Los días laborables comprendidos entre enero y febrero del año 2001 se han usado para ajustar la topología de la red Los días laborables comprendidos entre marzo y octubre del año 2001 se han usado para validar la red

39

Comparación con ANN PREDICCIÓN RED NEURONAL

marzo-mayo

junio-agosto

septiembreoctubre

Precio real (Cent/kWh)

2.2588

3.5482

3.673

Desviación estándar

0.7801

1.0597

0.518

Error absoluto medio (Cent/kWh)

0.3464

0.428

0.576

Máximo error horario (Cent/kWh)

2.671

2.0736

2.167

Error relativo medio (%)

15

12

14

Vecinos (modelo I)

Red neuronal

Septiembre

Octubre

Septiembre

Octubre

Error Relativo Medio (%)

6

9.6

14.75

13.75

Error Absoluto Medio (Cent/KWh)

0.25

0.38

0.6

0.56

Máximo error diario (%)

18

18.6

20.73

31.18

Máximo error horario (%)

66.02

88.08

50.21

64.92

Mínimo error diario (%)

2.07

3.97

5.33

4.28

Mínimo error horario (%)

0.03

0

0.01

0

MEJORES PREDICCIONES CON EL METODO BASADO EN LOS VECINOS

40

Aplicación Demanda de la energía eléctrica Características de la serie temporal Modelos obtenidos Directa: Distancia Euclídea

modelo I

Distancia Manhattan modelo II Resultados Comparación con M5’ 41

Características de la serie Demanda (MW)

24000 23000 22000 21000 20000 19000

Media Media + s. d. Media - s. d.

18000 17000 16000 1

3

5

7

9

11 13 15 17 19 21 23

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 -0.1 -0.2 -0.3

400 300 200 100 0 12500

16000

19500

23000

26500

Demanda año 2000 500

Número de horas

Coeficiente de Correlación

Horas

Número de horas

500

25000

1

3

5

7

9 11 13 15 17 19 21 42 23

Número de horas anteriores

400 300 200 100 0 12500

16000 19500 23000 26500

Demanda año 2001

42

Modelos: predicción directa : Modelo I: Longitud de la ventana = 15 número de vecinos = 4

D1,1 … D1,24 … D15,1 … D15,24

D16,1 … D16,24

D2,1 … D2,24 … D16,1 … D16,24 . . . . . . . . . . . . . . . . . . . . .

D17,1 … D17,24 . . . . . . . . .

DISTANCIA EUCLÍDEA

Dd-15,1 … Dd-15,24 … Dd-1,1 … Dd-1,24 Dd,1 … Dd,24? Modelo II: Longitud de la ventana = 7 número de vecinos = 7 D1,1 … D1,24 … D7,1 … D7,24

D8,1 … D8,24

D2,1 … . . . . . .

D9,1 … D9,24 . . . . . . . . .

D2,24 … D8,1 … D8,24 . . . . . . . . . . . . . . .

DISTANCIA MANHATTAN

Dd-7,1 … Dd-7,24 … Dd-1,1 … Dd-1,24 Dd,1 … Dd,24? 43

Resultados Los días laborables comprendidos entre enero del año 2000 y mayo del año 2001 se han usado para determinar la longitud óptima de la ventana deslizante y el número óptimo de vecinos Los días laborables comprendidos entre junio y noviembre del año 2001 se han usado para validar el algoritmo de predicción basado en KW-NN

Junio

Julio

Agosto

Demanda real

20453.267

21624.967

20598.948

Desviación Estándar

747.121 (3.6%)

576.181 (2.6%)

816.604 (3.9%)

Septiembre

Octubre

Noviembre

Demanda real

17281.499

20404.26

21998.205

Desviación Estándar

666.605 (9.1%)

587.017 (2.8%)

1459.911 (6.6%)

44

Resultados Modelo I

Modelo II

Verano

Otoño

Verano

Otoño

Error Relativo Medio (%)

2.99

3.73

2.36

2.24

Error Absoluto Medio (Cent/KWh)

627.53

572.1

493.42

456.31

Máximo error diario (%)

8.25

8.04

7.88

6.27

Máximo error horario (%)

13.5

18.6

14.8

17.6

Mínimo error diario (%)

0.5

0.66

0.6

0.48

Mínimo error horario (%)

0

0

0

0

MEJORES PREDICCIONES USANDO LA DISTANCIA MANHATTAN

MODELO II

Errores diarios (%)

Error semanal (%)

16 de julio-20 de julio

0.8

0.6

0.8

1.7

1.3

1.05

25 de junio-29 de junio

2.1

7.2

5.9

2.6

1.3

3.8

45

Resultados 6

Precios (t)

5 4 3 2 1 0 0

1

2

3

4

5

6

P r e c io s ( t- 1 ) 30000

Demanda (t)

27000 24000 21000 18000 15000 15000

18000

21000

24000

D e m a n d a (t-1 )

27000

30000

46

Comparación con M5’ Librería WEKA (“Waikato Environment for Knowledge Analysis”) Con selección de atributos: Algoritmo de selección: CFS (“Correlation-based Feature Selection”) Variables seleccionadas: las dos horas anteriores la quinta hora anterior Árbol con 53 regresiones Sin selección de atributos: Árbol con 151 regresiones M5'con selección

M5'sin selección

Vecinos (modelo II)

Mínimo error diario (%)

7

7

0.5

Mínimo error diario (%)

16.5

17.2

8.5

Error Relativo Medio (%)

11

11.4

2.3

47

Referencias [1] Alicia Troncoso Lora. Técnicas Avanzadas de Predicción y Optimización Aplicadas a Sistemas de Potencia. Tésis, Universidad de Sevilla, 2005 (http://www.upo.es/eps/troncoso) [2] Alicia Troncoso Lora et al. Predicción basada en Vecindad, CEDI I Congreso Español de Informática. SICO I Simposio de Inteligencia Computacional, 2005 [3] Alicia Troncoso Lora et al. Advances in Optimization and Prediction Techniques: Real-World Applications. Artificial Intelligence Communications, IOS Press Vol 19, No. 3, pp. 295-297, 2006. [4] Alicia Troncoso Lora et al. Electricity Market Price Forecasting Based on Weighted Nearest Neighbors Techniques. IEEE Transactions on Power Systems, Vol. 22, No. 3, pp. 1294-1301,2007 [5] Alicia Troncoso Lora et al. Técnicas Basadas en Vecinos Cercanos para la Predicción de los Precios de la Energía en el Mercado Eléctrico. CEDI II Congreso Español de Informática. SICO II Simposio de Inteligencia Computacional, 2007

48