1. No category

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 <xi,f(xi)>
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