selección de atributos - inaoe - ciencias …ariel/seleccionat2016.pdf · dada una muestra de...
TRANSCRIPT
![Page 2: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/2.jpg)
Contenido
Introducción
Estrategias de selección
Técnicas filter
Técnicas wrapper
Técnicas híbridas
![Page 3: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/3.jpg)
Selección de atributos
Selección de variables (feature selection)
Preprocesamiento Clasificación Supervisada Regresión Agrupamiento
Caracterización Atributos característicos
![Page 4: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/4.jpg)
Selección de atributos
Selección de variables (feature selection)
Preprocesamiento Clasificación Supervisada Regresión Agrupamiento
Caracterización Atributos característicos
![Page 5: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/5.jpg)
Por qué hacer selección de atributos en clasificación supervisada
Mejorar los resultados de la clasificación
Reducir el costo de la clasificación Acelerar el proceso de clasificación Mejorar el entendimiento del modelo y
resultados de la clasificación
Selección de atributos
![Page 6: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/6.jpg)
El objetivo es seleccionar un subconjunto reducido de atributos útiles para la clasificación eliminando
Atributos irrelevantes
Atributos redundantes
Selección de atributos
![Page 7: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/7.jpg)
Selección de variables
Variables descartadas
Muestra reducida Muestra M x1 .. xs
O1 x1(O1) .. xs(O1) :
Om x1(Om) .. xs(Om)
Selecctor
M x1 x2 ... xn O1 x1(O1) x2(O1) ... xn(O1) :
Om x1(Om) x2(Om) ... xn(Om)
M xi ... xk O1 xi(O1) ... xk(O1) :
Om xi(Om) ... xk(Om)
![Page 8: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/8.jpg)
Estrategias de Selección
filter.- La selección se hace con un criterio independiente del clasificador.
wrapper.- La selección se hace usando información del mecanismo de clasificación.
Híbridos.- Combinan estrategias filter y wrapper
![Page 9: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/9.jpg)
Estrategias filter
Usualmente ordenan las variables por algún criterio (ranking).
La selección se hace en el orden establecido con algún criterio de corte.
Comúnmente un número de variables a
seleccionar predefinido por el usuario (parámetro).
![Page 10: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/10.jpg)
Estrategias de ordenamiento
Entropía
Ganancia de información
Índice de Gini
Rough Set Theory/Teoría de Testores
Algoritmo Relief
![Page 11: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/11.jpg)
Algoritmo RELIEF Dada una muestra de objetos descritos por n atributos
numéricos normalizados.
Inicializar en 0 el peso wi de cada variable xi Repetir m veces
Seleccionar aleatoriamente un objeto O de la muestra de entrenamiento
Buscar en vecino más cercano (ONN) de O en su misma clase
Buscar en vecino más cercano (ONE) de O fuera de su clase
Para cada atributo xi tomar:
Ordenar los atributos descendentemente de acuerdo a su peso w
mOxOxmOxOxww NEiiNNiiii /))()((/))()(( 22 −+−−=
![Page 12: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/12.jpg)
Estrategias wrapper
Evalúan subconjuntos de atributos utilizando un clasificador.
Para evitar la búsqueda exhaustiva siguen alguna estrategia de búsqueda.
Comúnmente estrategias ávidas o aleatorias
![Page 13: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/13.jpg)
Estrategias wrapper
Para n variables, el espacio de búsqueda es de tamaño 2n
![Page 14: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/14.jpg)
Estrategias wrapper
Búsqueda exhaustiva
Búsqueda secuencial Hacia atrás (backward) Hacia adelante (forward) Flotante (floating)
Búsqueda aleatoria Algoritmos genéticos Búsqueda tabú ….
![Page 15: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/15.jpg)
Búsqueda exhaustiva
El tamaño del espacio de búsqueda es 2n
Si se busca un número predefinido de variable el espacio de búsqueda es de tamaño
Para seleccionar 20 variables de 50 el espacio de búsqueda es de tamaño
155013 102104
2050
≈<<×≈
kn
![Page 16: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/16.jpg)
Sequential Forward Selection
Sea F en conjunto de todas las variables S=Ø Repetir
Hasta |S|=k / q(S)<q(S\{x}) / q(S)>t
}{
})){((maxS\
xSS
xSqxFx
∪=
∪=∈
![Page 17: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/17.jpg)
Sequential Forward Selection
![Page 18: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/18.jpg)
Sequential Bacward Selection
Sea F en conjunto de todas las variables S=F Repetir
Hasta |S|=k / q(S)<q(S∪{x}) / q(S)>t
}{\
})){\((max
xSS
xSqxSx
=
=∈
![Page 19: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/19.jpg)
Sequential Backward Selection
![Page 20: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/20.jpg)
Sequential Floating Forward Selection
S=Ø Repetir
Repetir
Hasta q(S)<q(S∪{x}) S∪{x} Hasta |S|=k / q(S)>t
}{\
})){\((max
xSS
xSqxSx
=
=∈
}{
})){((maxS\
xSS
xSqxFx
∪=
∪=∈
![Page 21: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/21.jpg)
Sequential Floating Backward Selection
S=Ø Repetir
Repetir
Hasta q(S)≤q(S\{x}) S\{x} Hasta |S|=k / q(S)>t
}{\
})){\((max
xSS
xSqxSx
=
=∈
}{
})){((maxS\
xSS
xSqxFx
∪=
∪=∈
![Page 22: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/22.jpg)
Selección usando Algoritmos Genéticos
x1 x2 ... xn
0 1 0/1 ... 0/1 1
Individuos (suponiendo n variables)
![Page 23: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/23.jpg)
Selección usando Algoritmos Genéticos
Cruza (combinación de individuos)
Punto de cruza Punto de cruza
1 0 1 1 1 0 1 1 0 1 1 0
→ 1 1 0 0 0 1 1 0 1 0 0 1
![Page 24: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/24.jpg)
Selección usando Algoritmos Genéticos
Mutación (alteración de individuos)
Elemento a mutar
Elemento mutado
1 1 0 0 0 1 → 1 0 1 0 0 1
![Page 25: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/25.jpg)
Selección usando Algoritmos Genéticos
Generar población inicial P Para i=1, ... , numGeneraciones evalúa(P) P2 = cruza(P) evalúa(P2) P3 = mutación (P∪P2) evalúa(P3) P = selecciona(P∪P2∪P3) salida = mejorElemento(P)
![Page 26: Selección de Atributos - INAOE - Ciencias …ariel/seleccionAT2016.pdf · Dada una muestra de objetos descritos por n atributos numéricos normalizados. ... El tamaño del espacio](https://reader031.vdocumento.com/reader031/viewer/2022022023/5ba95ef409d3f24c398c8d55/html5/thumbnails/26.jpg)
Evaluación de selectores de variables
Utilizando un clasificador Seleccionar un conjunto de bases de datos Utilizar algún método de validación aplicando
selección+clasificación Utilizar alguna medida de evaluación de calidad de
clasificación
Utilizar datos sintéticos en los cuales se conozca cuáles son los atributos importantes