SEMINARIOS DE DOCTORADO 2005-2006
Doctorado en Ingeniería
Informática y de
Telecomunicación
Escuela Politécnica Superior, Universidad Autónoma de
Madrid
16 de diciembre de 2005, 12:00
Salón de Grados, Escuela Politécnica Superior,
Universidad Autónoma de Madrid
Clasificación mediante conjuntos
Gonzalo Martínez Muñoz
Escuela
Politécnica Superior - UAM
Resumen
En esta conferencias se describen cuatro nuevos métodos de
generación de conjuntos de clasificadores y varias
heurísticas para la mejora por ordenación y poda de
conjuntos generados con bagging:
- Se presentan tres nuevos métodos de construcción de
clasificadores que se caracterizan por usar sin modificaciones todos
los datos de entrenamiento para construir cada uno de los
clasificadores del conjunto. El algoritmo base, presentado en
[gelfand91iterative], construye un árbol de decisión de
forma iterativa a partir de un conjunto de datos que se divide en dos
subconjuntos. En cada iteración, uno de los dos subconjuntos se
utiliza para hacer crecer el árbol a partir del árbol de
decisión obtenido en la iteración anterior. Una vez que
se ha hecho crecer el árbol hasta su tamaño máximo
éste se poda usando el otro subconjunto de datos. Los papeles de
los subconjuntos se intercambian en cada iteración. Este proceso
converge a un árbol final que es estable con respecto a la
secuencia de pasos de crecimiento y poda. Para generar una variedad de
clasificadores en el conjunto se crean tantas divisiones aleatorias de
los ejemplos en dos subconjuntos como árboles se quieran
construir. Este método da buenos resultados de
clasificación en varias bases de datos estándar con un
coste computacional menor que los conjuntos basados en CART.
- Se presenta un conjunto de clasificadores cuyos miembros son
construidos a partir de alteraciones de las etiquetas de clase de un
porcentaje de ejemplos elegidos aleatoriamente de entre los que
componen el conjunto de entrenamiento. Este método obtiene una
gran mejora del error de clasificación cuando se utiliza una
alta probabilidad de modificación de etiquetas de clase y se
generan conjuntos con un número elevado de clasificadores.
Asimismo se muestra cómo los clasificadores generados siguiendo
este procedimiento cometen errores en el conjunto de entrenamiento
estadísticamente no correlacionados. La dependencia del error de
entrenamiento de los conjuntos generados con el tamaño del
conjunto es independiente del problema de clasificación
analizado. En concreto, se muestra cómo para problemas de
clasificación binarios, esta dependencia se puede analizar en
términos de un proceso de Bernoulli. Asimismo, se muestran los
resultados de experimentos realizados en 15 bases de datos
estándar que demuestran las mejoras que se pueden obtener con
este procedimiento.
- El orden en que los clasificadores se agregan en un conjunto de
clasificadores puede ser una herramienta útil para la
selección de subconjuntos de clasificadores más
eficientes que el conjunto original completo. En general, el error de
generalización de un conjunto de clasificadores ordenados
aleatoriamente disminuye al incrementarse el número de
clasificadores hasta alcanzar un valor constante. Si se modifica
adecuadamente el orden de los clasificadores dentro del conjunto, el
error de generalización puede alcanzar un mínimo cuyo
valor esté por debajo del error asintótico del conjunto
completo. En este capítulo se presentan varias
heurísticas que utilizan las correlaciones entre clasificadores
generados mediante bagging para identificar un orden apropiado que
permita identificar un subconjunto de clasificadores con buenas
capacidades de generalización. Una vez ordenado el conjunto
éste se poda para seleccionar los K primeros clasificadores de
acuerdo con un porcentaje de poda prefijado o mediante otras reglas de
poda. De esta manera se pueden construir conjuntos de clasificadores de
menor tamaño y con menor error de clasificación en
conjuntos de test que el conjunto original completo.
Gonzalo Martínez
Muñoz
Gonzalo Martínez-Muñoz obtuvo el título de
licenciado en Ciencias Físicas en 1995 y el Diploma de Estudios
Avanzados en 2001 por la Universidad Autónoma de Madrid (UAM).
Actualmente está trabajando en la finalización de su
tesis sobre conjuntos de clasificadores dentro del departamento de
Ingeniería Informática de la Escuela Politécnica
Superior (UAM). Además, trabaja como profesor ayudante en este
mismo departamento donde imparte la parte práctica de las
asignaturas de “Programación Orientada a Objetos” y
“Análisis de Algoritmos”. De 1996 a 2002, trabajó para
Geosys SL, una PYME especializada en sistemas de información
geográficos y teledetección, como analista y programador
en el marco de proyectos de I+D. Sus principales campos de
investigación incluyen: aprendizaje automático,
reconocimiento de patrones, árboles de decisión,
conjuntos de clasificadores y algoritmos genéticos.