Combinación de Clasificadores: Construcción de Características e Incremento de la Diversidad


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "Combinación de Clasificadores: Construcción de Características e Incremento de la Diversidad"

Transcripción

1 Universidad de Burgos Tesis Doctoral Combinación de Clasificadores: Construcción de Características e Incremento de la Diversidad Jesús Maudes 4-Octubre-2010 Directores: Dr. Juan José Rodríguez Diez Dr. César García Osorio

2

3 i Agradecimientos A mis directores de tesis, por su paciencia y dedicación, y sobretodo por su amistad. Sin ellos, sin sus conocimientos, sin sus ánimos y su comprensión, hubiera sido poco probable que hubiera conseguido acabar esta tesis. A los compañeros del Área de Lenguajes y Sistemas Informáticos, por todos los cafés compartidos y por no cargarme de trabajo de gestión en estos últimos años, lo cual me ha facilitado en gran medida las cosas. También quiero agradecerles su disposición para compartir sus PCs en los inicios de esta tesis, cuando aún no disponíamos de máquinas específicas de cálculo. Dentro de los compañeros del área también quiero dar un agradecimiento especial a Carlos Pardo, por sus conocimientos enciclopédicos de Linux que sirvieron para facilitarme las validaciones experimentales. También quisiera animar, en general, a mis compañeros no doctores: si lo he hecho yo, qué no podríais hacer cualquiera de vosotros. A Nicolás García Pedrajas por su amabilidad al permitirme usar el cluster de su equipo de investigación en la Universidad de Córdoba para completar los resultados experimentales. Sin esta ayuda algunos experimentos hubieran tardado mucho más. A Colin Fyfe, por sus comentarios ( en castellano!). Vaya también mi agradecimiento para todas aquellas personas e instituciones que de manera gratuita y, muchas veces, desinteresada han puesto a disposición del público recursos que han sido utilizados en la elaboración de la tesis. En concreto sobretodo a los desarrolladores de WEKA, pero también a los de TeXnicCenter, MiKTeX, Yap, OpenOffice, Linux, GNUPlot, FoxIt y GhostView; así como a los donantes de datos y mantenedores de los repositorios UCI y Statlib. A mis vecinos, por no ser en absoluto disturbing. A los que les he robado horas: padres, hermanos, amigos, hijo, esposa y perro, que lleva más de un año en arresto domiciliario. Finalmente, a Maria José por convivir con mi yo más inaguantable.

4 ii

5 Índice general 1. Introducción Objetivos Organización de la tesis Aportaciones de esta tesis Conceptos Previos y Estado del Arte Clasificadores base utilizados en esta tesis Máquinas de Vectores Soporte, SVM Árboles de Decisión Multiclasificadores Bagging Random Forests Random Subspaces Boosting Cascading Stacking Grading Otros métodos multiclasificadores Técnicas de validación experimental Tests estadísticos utilizados Ordenación de los métodos por su acierto Gráficas para visualización de la diversidad Cascadas para Datos Nominales Introducción Multiclasificadores de dos niveles Árboles de decisión binarios vs. VDM Equivalencias entre multiclasificadores de dos niveles Validación experimental Conclusiones Disturbing Neighbors Introducción Algoritmo iii

6 iv ÍNDICE GENERAL El efecto del algoritmo en SVM El efecto del algoritmo en árboles de decisión Resultados de DN con SVM Análisis de la diversidad en multiclasificadores con DN- SVM Resultados de DN con árboles Análisis de la diversidad en multiclasificadores con DNárboles Estudio de lesiones Conclusiones Random Feature Weights Introducción Algoritmo Distribución de los pesos aleatorios Resultados experimentales Robustez Árboles RFW como clasificadores base Diagramas Kappa-Error Influencia del parámetro Conclusiones Conclusiones y Trabajos Futuros 169 A. Tablas con las Tasas de Acierto 175 A.1. Tasas de acierto para DN con SVM A.2. Tasas de acierto para DN con árboles A.3. Tasas de acierto del análisis de lesiones para DN A.4. Tasas de acierto para RFW

7 Índice de tablas 3.1. Ejemplo de conversión de datos nominales a binarios conducente a regiones que no son linealmente separables Ejemplos de equivalencias de multiclasificadores de dos niveles con VDM Conjuntos de datos utilizados en la validación experimental del Capítulo Estudio de 57 métodos para datos nominales ordenados por su ranking promedio (I) Estudio de 57 métodos para datos nominales ordenados por su ranking promedio (II) Acierto de los 12 métodos para datos nominales considerados (I) Acierto de los 12 métodos para datos nominales considerados (II) Ranking de los 12 métodos por la diferencia entre victorias y derrotas significativas Ranking promedio de los 12 métodos considerados Vista de algunas instancias del conjunto iris aumentadas al añadir nuevas dimensiones mediante DN Coeficientes de los hiperplanos resultantes de computar los SVM y los DN-SVM (m = 10) para el conjunto iris Lista de los conjuntos de datos utilizados en los experimentos para DN Ranking promedio de la validación experimental de DN con clasificadores base SVM Comparación de las posiciones de los multiclasificadores con DN- SVM vs. SVM en el ranking promedio Ranking de diferencias entre victorias y derrotas significativas de la validación experimental de DN con clasificadores base SVM Comparación de las posiciones de los multiclasificadores con DN- SVM vs. SVM en el ranking de diferencias entre victorias y derrotas significativas Comparación de los métodos basados en SVM con y sin DN Comparativa de los multiclasificadores que usan DN contra 1-NN Comparativa de los métodos que usan DN con el clasificador k-nn. 97 v

8 vi ÍNDICE DE TABLAS Ranking promedio de la validación experimental de DN con clasificadores base árboles Posiciones de los multiclasificadores con DN-árboles vs. árboles puros en el ranking promedio Ranking de diferencias entre victorias y derrotas significativas de la validación experimental de DN con clasificadores base árboles Posiciones de los multiclasificadores con DN-árboles vs. árboles puros en el Ranking de diferencias entre victorias y derrotas significativas Comparación de los métodos basados en árboles con y sin DN Comparativa de los multiclasificadores de árboles que usan DN contra 1-NN Comparativa de los multiclasificadores de árboles que usan DN contra k-nn Rankings para las distintas variantes de (DN-)Bagging Rankings para las distintas variantes de (DN-)Random Forest Rankings para las distintas variantes de DN-Ensemble Rankings para las distintas variantes de (DN-)Random Subspaces 50% Rankings para las distintas variantes de (DN-)Random Subspaces 75% Rankings para las distintas variantes de (DN-)AdaBoost(W) Rankings para las distintas variantes de (DN-)AdaBoost(S) Rankings para las distintas variantes de (DN-)MultiBoost(W) Rankings para las distintas variantes de (DN-)MultiBoost(S) Rankings promedios de todas las DN-variantes Posiciones relativas en la familia de cada DN-variante usando el ranking promedio de la Tabla Rankings de los beneficios computados en la Tabla Comparación de RFW con otros métodos, utilizando clasificadores base podados y el Sign test Comparación de RFW con otros métodos, utilizando clasificadores base no podados y el Sign test Comparación de RFW con otros métodos, utilizando clasificadores base podados y el Resampled t-test Comparación de RFW con otros métodos, utilizando clasificadores base no podados y el Resampled t-test Ranking promedio de todos los métodos considerados en la validación de RFW Ranking por la diferencia entre victorias y derrotas significativas utilizando todos los métodos considerados en la validación de RFW Comparación de RFW con otros métodos, utilizando clasificadores base podados, con un error artificial del 10%, y el Sign test

9 ÍNDICE DE TABLAS vii 5.8. Comparación de RFW con otros métodos, utilizando clasificadores base no podados, con un error artificial del 10%, y el Sign test Comparación de RFW con otros métodos, utilizando clasificadores base podados, con un error artificial del 20%, y el Sign test Comparación de RFW con otros métodos, utilizando clasificadores base no podados, con un error artificial del 20%, y el Sign test Comparación de RFW con otros métodos, utilizando clasificadores base podados, con un error artificial del 10%, y el Resampled t-test Comparación de RFW con otros métodos, utilizando clasificadores base no podados, con un error artificial del 10%, y el resampled t-test Comparación de RFW con otros métodos, utilizando clasificadores base podados, con un error artificial del 20%, y el Resampled t-test Comparación de RFW con otros métodos, utilizando clasificadores base no podados, con un error artificial del 20%, y el Resampled t-test Ranking promedio de todos los métodos considerados al analizar RFW con un error artificial del 10% Ranking por la diferencia entre victorias y derrotas significativas de todos los métodos considerados al analizar RFW con un error artificial del 10% Ranking promedio de todos los métodos considerados al analizar RFW con un error artificial del 20% Ranking por la diferencia entre victorias y derrotas significativas de todos los métodos considerados al analizar RFW con un error artificial del 20% Comparación mediante el sign test de las versiones con/sin RFW de los multiclasificadiores de referencia considerados Comparación mediante el t-test de las versiones con/sin RFW de los multiclasificadiores de referencia considerados Ranking promedio de los métodos considerados tomando como clasificadores base árboles puros o árboles RFW Ranking por la diferencia entre victorias (V) y derrotas (D) significativas de los métodos considerados tomando como clasificadores base árboles puros o árboles RFW A.1. Experimentos con DN para multiclasificadores con SVM. Tasas de acierto para DN-Ensemble, 1-NN y k-nn A.2. Experimentos con DN para multiclasificadores con SVM. Tasas de acierto para las configuraciones de SVM y Bagging

10 viii ÍNDICE DE TABLAS A.3. Experimentos con DN para multiclasificadores con SVM. Tasas de acierto para las configuraciones de Random Subspaces A.4. Experimentos con DN para multiclasificadores con SVM. Tasas de acierto para las configuraciones de AdaBoost A.5. Experimentos con DN para multiclasificadores con SVM. Tasas de acierto para las configuraciones de MultiBoost A.6. Experimentos con DN para multiclasificadores con árboles de decisión. Tasas de acierto para DN-Ensemble, 1-NN y k-nn A.7. Experimentos con DN para multiclasificadores con árboles de decisión. Tasas de acierto para las configuraciones de Bagging y Random Forest A.8. Experimentos con DN para multiclasificadores con árboles de decisión. Tasas de acierto para las configuraciones de AdaBoost. 185 A.9. Experimentos con DN para multiclasificadores con árboles de decisión. Tasas de acierto para las configuraciones de MultiBoost. 186 A.10.Experimentos con DN para multiclasificadores con árboles de decisión. Tasas de acierto para las configuraciones de Random Subspaces A.11.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de Bagging A.12.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de Random Forest A.13.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de DN-Ensemble A.14.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de Random Subespaces(50%) A.15.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de Random Subespaces(75%) A.16.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de AdaBoost(W) A.17.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de AdaBoost(S) A.18.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de MultiBoost(W) A.19.Experimentos del análisis de lesiones para DN. Tasas de acierto para las configuraciones de MultiBoost(S) A.20.Experimentos para RFW. Tasas de acierto para RFW con árboles podados y p = A.21.Experimentos para RFW. Tasas de acierto para Bagging y Random Subspaces 50% y 75% contra RFW p = (para árboles podados en ambos casos) A.22.Experimentos para RFW. Tasas de acierto para las dos versiones de AdaBoost y MultiBoost contra RFW p = (para árboles podados en ambos casos) A.23.Experimentos para RFW. Tasas de acierto para RFW con árboles no podados y p =

11 ÍNDICE DE TABLAS ix A.24.Experimentos para RFW. Tasas de acierto para Bagging, Random Forests y Random Subspaces 50% y 75% contra RFW p = (para árboles sin podar en ambos casos) A.25.Experimentos para RFW. Tasas de acierto para las dos versiones de AdaBoost y MultiBoost contra RFW p = (para árboles sin podar en ambos casos) A.26.Experimentos para RFW. Tasas de acierto para RFW con árboles podados y p = 1...4, para el caso de un error artificial del 10% en el conjunto de datos A.27.Experimentos para RFW. Tasas de acierto para Bagging y las dos versiones de Random Subspaces contra RFW p = 1...4, para árboles podados y conjuntos de entrenamiento con error artificial del 10% en ambos casos A.28.Experimentos para RFW. Tasas de acierto para las dos versiones de AdaBoost y MultiBoost contra RFW p = 1...4, para árboles podados y conjuntos de entrenamiento con error artificial del 10% en ambos casos A.29.Experimentos para RFW. Tasas de acierto para RFW con árboles no podados y p = 1...4, para el caso de un error artificial del 10% en el conjunto de datos A.30.Experimentos para RFW. Tasas de acierto para Bagging, Random Forests y Random Subspaces 50% y 75% contra RFW p = para árboles sin podar y conjuntos de entrenamiento con error artificial del 10% en ambos casos A.31.Experimentos para RFW. Tasas de acierto para las dos versiones de AdaBoost y MultiBoost contra RFW p = 1...4, para árboles sin podar y conjuntos de entrenamiento con error artificial del 10% en ambos casos A.32.Experimentos para RFW. Tasas de acierto para RFW con árboles podados y p = 1...4, para el caso de un error artificial del 20% en el conjunto de datos A.33.Experimentos para RFW. Tasas de acierto para Bagging y las dos versiones de Random Subspaces contra RFW p = 1...4, para árboles podados y conjuntos de entrenamiento con error artificial del 20% en ambos casos A.34.Experimentos para RFW. Tasas de acierto para las dos versiones de AdaBoost y MultiBoost contra RFW p = 1...4, para árboles podados y conjuntos de entrenamiento con error artificial del 20% en ambos casos A.35.Experimentos para RFW. Tasas de acierto para RFW con árboles no podados y p = 1...4, para el caso de un error artificial del 20% en el conjunto de datos A.36.Experimentos para RFW. Tasas de acierto para Bagging, Random Forests y Random Subspaces 50% y 75% contra RFW p = para árboles sin podar y conjuntos de entrenamiento con error artificial del 20% en ambos casos

12 x ÍNDICE DE TABLAS A.37.Experimentos para RFW. Tasas de acierto para las dos versiones de AdaBoost y MultiBoost contra RFW p = 1...4, para árboles sin podar y conjuntos de entrenamiento con error artificial del 20% en ambos casos A.38.Experimentos para RFW. Tasas de acierto para RFW-Bagging y RFW-Random Subspaces 50% y 75% contra sus versiones sin RFW, tanto para árboles podados (P) como sin podar (U) ) A.39.Experimentos para RFW. Tasas de acierto para RFW-AdaBoost y RFW-MultiBoost contra sus versiones sin RFW, tanto para las versiones con repesado (W) como para las de remuestro (S), y tanto para árboles podados (P) como sin podar (U)

13 Índice de figuras 2.1. El algoritmo de entrenamiento de AdaBoost según [119] El algoritmo de entrenamiento de AdaBoost.M1 según [41] El algoritmo de entrenamiento de MultiBoosting según [116] Funcionamiento de Cascading Funcionamiento de Stacking (I) Funcionamiento de Stacking (II) Funcionamiento de Grading (I) Funcionamiento de Grading (II) Ejemplos de diagramas Kappa-Error para el conjunto de datos letter Ejemplo de diagrama de Movimiento Kappa-Error Ejemplo de diagrama de Movimiento Relativo de Kappa-Error Notación utilizada para los multiclasificadores de dos niveles Entrenamiento de un clasificador base usando DN. Función Principal Función 1-Nearest Neighbor utilizada en DN Regiones de Voronoi para el conjunto de datos conus-torus Un árbol C4.5 y otro DN-C4.5 para el conjunto de datos iris Bagging vs. DN-Bagging Error vs. Kappa para Bagging y Subspaces(75%) en el conjunto de datos letter. Vista separada Error vs. Kappa para Bagging y Subspaces(75%) en el conjunto de datos letter. Vista conjunta Diagramas de movimiento κ-error para DN con SVM en los 62 conjuntos de datos Diagrama de Movimiento κ-error para Bagging de SVM Diagrama de Movimiento κ-error para Subspaces (75%) de SVM Diagrama de Movimiento κ-error para AdaBoost(S) de SVM Diagrama de Movimiento κ-error para MultiBoost(S) de SVM Diagrama de Movimiento Relativo de κ-error para Bagging de SVM xi

14 xii ÍNDICE DE FIGURAS Diagrama de Movimiento Relativo de κ-error para Subspaces (75%) de SVM Diagrama de Movimiento Relativo de κ-error para AdaBoost(S) de SVM Diagrama de Movimiento Relativo de κ-error para MultiBoost(S) de SVM Error vs. Kappa para Boosting y Bagging en el conjunto de datos krk Diagramas de movimiento κ-error para DN con árboles en los 62 conjuntos de datos Diagrama de Movimiento Relativo de κ-error para Bagging de árboles Diagrama de Movimiento Relativo de κ-error para Random Forests Diagrama de Movimiento Relativo de κ-error para Random Subspaces (50%) de árboles Diagrama de Movimiento Relativo de κ-error para AdaBoost(S) de árboles Diagrama de Movimiento Relativo de κ-error para MultiBoost(S) de árboles Algoritmo de construcón de un árbol RFW Distribución de los pesos en RFW Diagramas κ-error correspondientes al estudio de los RFWs para el conjunto segment Diagramas κ-error correspondientes al estudio de los RFWs para el conjunto sick Diagramas κ-error correspondientes al estudio de los RFWs para el conjunto splice Diagramas de movimiento κ-error correspondientes para los RFWs Diagramas de movimiento relativo κ-error para los RFWs Influencia del parámetro p en el error Influencia del parámetro p en los diagramas kappa-error Diagrama de porcentajes para diferentes valores del parámetro p. 166

15 Capítulo 1 Introducción Esta tesis presenta varios algoritmos de Pattern Recognition o Reconocimiento de Patrones [46]. Esta disciplina hace tiempo que salió de los laboratorios y las publicaciones científicas para impregnar nuestro día a día. Sistemas que reconocen la escritura [70], la voz [56], las imágenes [120], que descifran los genes [73], diagnostican enfermedades [6], interpretan las señales de tráfico [86], o rechazan el correo basura [105]. Todos ellos, son unos pocos ejemplos de estos sistemas con los que de manera casi imperceptible nos hemos acostumbrado poco a poco a convivir. En reconocimiento de patrones un algoritmo aprende o analiza de forma automatizada un conjunto de datos existentes sobre una población de individuos o instancias. Este proceso de aprendizaje se conoce como entrenamiento. Cada uno de los individuos del conjunto de datos se caracteriza mediante un conjunto de valores o atributos. El Aprendizaje Supervisado es un tipo especial de reconocimiento de patrones. En el aprendizaje supervisado cada instancia del conjunto de datos se puede representar como un par (x,y), donde y es un atributo especial en tanto el algoritmo ha de aprender a predecirlo a partir de los valores del vector x, que son el resto de atributos de la instancia. El adjetivo supervisado se aplica debido a que en el proceso de entrenamiento se conocen y utilizan los valores de y de cada una de las instancias para realizar ese aprendizaje. También existe el aprendizaje no supervisado, en el que los posibles valores de y no son conocidos a priori, y el algoritmo trata de descubrir agrupaciones de instancias entre las que poder establecer una relación, por ejemplo, asociarles una etiqueta. Dentro del aprendizaje supervisado puede ocurrir que los valores de y sean un conjunto finito de etiquetas, o bien un conjunto de valores continuos. En el primer caso el aprendizaje resolvería un problema denominado de clasificación, mientras que en el segundo el problema sería de regresión. Esta tesis está centrada en los problemas de clasificación dentro del aprendizaje supervisado. Un clasificador es un modelo que sirve para clasificar las entradas x de un conjunto de datos. Para obtener un clasificador, previamente un algoritmo procesa un conjunto 1

16 2 CAPÍTULO 1. INTRODUCCIÓN de pares (x, y), el cual se denomina conjunto de entrenamiento. El algoritmo, analiza este conjunto de datos mediante un proceso que se conoce como entrenamiento, fruto del cual se obtiene un modelo predictivo (i.e., el clasificador) que es capaz de asignar a futuros valores del vector x, los valores y que probablemente le corresponderían. El mérito del algoritmo estará en obtener modelos que yerren lo menos posible en estas asignaciones. Una forma relativamente reciente de abordar el problema de la clasificación, es la utilización de Multiclasificadores o Ensembles [66, 102, 88]. Un multiclasificador es una agrupación de clasificadores, que se conocen como clasificadores base que combinan sus predicciones siguiendo un determinado esquema, con el fin de obtener una predicción más fiable que la que normalmente serían capaces de obtener en solitario. El tipo de algoritmos que se presentan en esta tesis o son multiclasificadores, o bien son modificaciones aplicables a multiclasificadores existentes que son capaces de mejorarlos en determinadas situaciones. El común denominador a dos de ellos es la construcción de características. La construcción de características es el proceso mediante el cual se descubre información no presente sobre las relaciones de los atributos, aumentando el espacio de características al deducir o crear otras nuevas [51]. La construcción de características no presentes en el conjunto de datos es distinta a: 1. La extracción de características, que persigue encontrar un conjunto mínimo de nuevas características a través de alguna transformación y según un criterio de optimización. 2. La selección de características, que tiene por objeto eliminar aquellas que resulten redundantes. 3. La combinación de características que sirve para obtener grupos de las mismas que faciliten la tarea de clasificación. Las nuevas características que construyen dos de los algoritmos que se presentan en esta tesis, en unos casos servirán para adaptar determinados tipos de problemas a determinados tipos de clasificadores, y en otros casos han servido para mejorar el comportamiento del multiclasificador, alterando el funcionamiento de sus clasificadores base. La diversidad es una cualidad que idealmente debieran presentar los clasificadores base de un multiclasificador, en virtud de la cual las predicciones de los mismos tienden a ser distintas. Construir un multiclasificador exitoso requiere que sus clasificadores base acierten casi siempre en sus predicciones, pero que cuando yerren cada uno lo haga en distintas instancias; de lo contrario la ventaja de tener varios clasificadores colaborando, frente a uno solo, no existiría. Dos de los métodos presentados en esta tesis servirán para aumentar la diversidad en sus clasificadores base, consiguiendo generalmente mejorar el rendimiento de los multiclasificadores a los que pertenecen.

17 1.1. OBJETIVOS Objetivos Los métodos que se incluyen en esta memoria pueden agruparse en dos: 1. Por un lado, se presenta un método orientado a mejorar el acierto de métodos de clasificación numéricos frente a datos nominales. 2. Por otro lado, se presentan dos métodos orientados a incrementar la diversidad en multiclasificadores cuyos clasificadores miembros o clasificadores base sean del mismo tipo. El primero de los métodos está enfocado a un tipo de problemas específico: aquellos en los que predominan los datos nominales o categóricos. Este tipo de datos son aquellos que toman sus valores de entre un conjunto de etiquetas finitas (e.g., la clase es un ejemplo de atributo categórico). Hay clasificadores capaces de trabajar con este tipo de datos directamente, mientras que otros sólo admiten entradas numéricas, por ejemplo, los clasificadores lineales, en los que un hiperplano separa las instancias de una clase de las de otras. Una de las aportaciones de esta tesis es un algoritmo para la construcción de nuevas características numéricas a partir de las características nominales de partida. El resultado será un multiclasificador en tanto que las nuevas características a construir, provienen de la salida de otro clasificador capaz de trabajar con datos nominales directamente (i.e., Cascading utilizando árboles de decisión como clasificadores base). Los resultados experimentales obtenidos indican una mejora frente a otras técnicas conocidas para resolver el mismo problema. En cuanto al segundo grupo de métodos que se presentan, están orientados a mejorar el acierto en multiclasificadores que utilizan un único tipo de clasificador base replicado durante un número dado de iteraciones. La idea fundamental de estas mejoras es la introducción de algún tipo de perturbación aleatoria en el entrenamiento de los clasificadores base, de manera que dicha perturbación acabe por generar clasificadores base más diversos. Los métodos correspondientes a este segundo grupo que se presentan en la tesis son: 1. Uno llamado Disturbing Neighbors, que es genérico en cuanto puede valer tanto para múltiples tipos de clasificadores base como para múltiples tipos de multiclasificador, y que está basado en construcción de características. El método obtendrá esas características adicionales a partir de la pertenencia a ciertas regiones de Voronoi definidas a partir de una selección aleatoria de un conjunto reducido de instancias de entrenamiento. 2. Otro llamado Random Feature Weights, que es más específico en cuanto está orientado a bosques, esto es: a multiclasificadores cuyos clasificadores base son todos de tipo árbol. Sin embargo, aunque es un esquema que restringe el tipo de clasificador base, su aplicación no está restringida a ningún tipo de bosque en concreto. En este caso, lo que se trastoca es el

18 4 CAPÍTULO 1. INTRODUCCIÓN normal funcionamiento del proceso de entrenamiento de los árboles mediante la introducción de un elemento aleatorio en el criterio de bifurcación de las ramas de cada árbol. La mejora de la diversidad de ambas técnicas ha sido probada experimentalmente, así como la mejora de las tasas de acierto de los multiclasificadores así generados Organización de la tesis El capítulo 2 introduce los conceptos que son comunes al resto de capítulos de la tesis. En concreto, se centra en explicar brevemente los clasificadores base y multiclasificadores de referencia utilizados. También analiza la técnicas de validación experimental utilizadas, junto con los diagramas que han servido para explicar los resultados obtenidos en términos de aumento de la diversidad. Estos diagramas son unos de los productos más relevantes que ha dado lugar el desarrollo de esta tesis. El capítulo 3 presenta una configuración concreta de Cascada que permite mejorar la utilización de datos nominales por clasificadores que sólo admiten entradas de tipo numérico. El capítulo 4 es el más extenso de la tesis. Presenta el método de Disturbing Neighbors que es capaz de aumentar la diversidad en clasificadores base, lo que generalmente mejora los resultados del multiclasificador al que pertenecen. Este método se ha probado utilizando árboles de decisión y máquinas de vectores soporte como clasificadores base. La elección de estos dos tipos de clasificadores responde a que entre si presentan grandes diferencias en un elemento que es clave para los miembros de un multiclasificador, como es el caso de su estabilidad frente a pequeños cambios en el conjunto de entrenamiento. El éxito del método es analizado desde la perspectiva del aumento de la diversidad en los clasificadores base, para lo que se aportan diagramas obtenidos experimentalmente, basados en la estadística Kappa-Error. Además, el capítulo presenta un análisis de lesiones que muestra qué elementos del algoritmo de Disturbing Neighbors son fundamentales y cuáles no son influyentes. El capítulo 5 presenta el método Random Feature Weights que sirve para aumentar la diversidad en multiclasificadores con clasificadores base que sean árboles de decisión. En este capítulo se incluyen resultados experimentales para este método con y sin ruido, dado el buen comportamiento que tiene en ambos escenarios. Para comprobar el aumento de la diversidad en los Random Feature Weights también se aportan los correspondientes diagramas basados en la estadística Kappa-Error. Finalmente, el capítulo 6 presenta cuáles son las conclusiones que se extraen de la tesis, y cuáles son las posibles líneas de investigación futuras. Además, al final del volumen, se aporta un apéndice conteniendo las tasas de error correspondientes a las validaciones experimentales. Debido a que las validaciones experimentales incluyen un gran número de conjuntos de datos y

19 1.3. APORTACIONES DE ESTA TESIS 5 métodos, se ha preferido ubicarlas de esta manera, ya que si se hubieran incluido en el interior de sus correspondientes capítulos, debido a su tamaño, posiblemente no hubieran facilitado la lectura de los mismos. En los capítulos ya se incluyen las tablas y gráficos necesarios que permiten sintetizar toda esta información de una manera más concisa y eficiente, mientras que el apéndice permite comprobar de qué conjuntos de datos y métodos provienen esos resúmenes Aportaciones de esta tesis Como resumen de todo lo comentado anteriormente en este capítulo, a continuación se numeran las principales aportaciones de esta tesis: Dos diagramas para facilitar la comparación visual de métodos de clasificación (subsección 2.3.3, página 55): - Diagramas de Movimiento Kappa-Error. - Diagramas de Movimiento Relativo Kappa-Error. Un nuevo clasificador para conjuntos de datos nominales, Cascadas para Datos Nominales (Capítulo 3, página 61). Dos nuevas familias de algoritmos de construcción de multiclasificadores: - Disturbing Neighbors (Capítulo 4, página 81). - Random Feature Weights (Capítulo 5, página 129). Los resultados de esta tesis han tenido sus reflejos en las siguientes publicaciones: Capítulos de Libros: [78], [80]. Actas de Congresos: [76], [77], [79], [81].

20 6 CAPÍTULO 1. INTRODUCCIÓN

21 Capítulo 2 Conceptos Previos y Estado del Arte 2.1. Clasificadores base utilizados en esta tesis En Reconocimiento de Patrones un clasificador no es más que una función que dado un vector de atributos x le asigna a éste una etiqueta y perteneciente al conjunto de clases del problema. Los multiclasificadores o ensembles son clasificadores que se construyen a partir de otros más simples, llamados Clasificadores Base. El entrenamiento de los clasificadores base puede seguir pautas distintas de un multiclasificador a otro, y la predicción final de un multiclasificador seguirá un esquema de combinación de las predicciones de los clasificadores base que también será propio de cada multiclasificador. Los clasificadores base que se han utilizado en esta tesis son dos: 1. Máquinas de vectores soporte 1 (SVM) [115, 16, 108, 54, 24]. Una SVM es un clasificador lineal en un espacio que podría ser distinto al espacio original donde están definidos los vectores x, y por tanto un hiperplano que clasifica las instancias por la pertenencia a cada una de las regiones de ese espacio que son limitadas por dicho hiperplano. La SVM se obtiene siguiendo unos determinados criterios de optimización, y aunque en principio parece requerir que el problema de clasificación presente regiones linealmente separables, es capaz de tratar problemas no separables linealmente a partir de la modificación de ciertos parámetros y/o de la elección del espacio donde se defina el hiperplano. 2. Árboles de decisión [103, 13, 63, 54]. Los árboles de decisión son una colección de nodos conectados entre sí, cada uno con un ascendiente -excepto el nodo raíz que no tiene ascendientes - y cero o más descendientes. Los 1 En lo sucesivo se utilizará indistintamente la/s SVM (la/s máquinas de vectores soporte) y el/los SVM (el/los clasificadores tipo SVM). 7

22 8 CAPÍTULO 2. CONCEPTOS PREVIOS Y ESTADO DEL ARTE nodos sin descendientes se conocen como hojas y tienen asociada una clase. Los nodos que no son hojas contienen una condición con la que evaluar la instancia que se esté clasificando. El proceso de clasificación consiste en ir recorriendo los nodos desde la raíz hasta una hoja. El recorrido viene dado por cómo responda la instancia a cada una de las decisiones que el árbol planteará en cada nodo, de forma que cada posible respuesta de la instancia se traducirá en por que nodo o rama continuará la instancia el proceso de clasificación. Los dos clasificadores base elegidos son muy distintos en muchos aspectos, entre otros cabe destacar: 1. Por un lado una SVM al ser un hiperplano es un clasificador orientado a trabajar con datos numéricos, mientras que los árboles de decisión pueden trabajar directamente con datos nominales, pues en sus nodos intermedios pueden albergar comparaciones del tipo este atributo es igual a tal etiqueta. 2. Las SVM dividen el espacio del problema en dos, por tanto son clasificadores binarios; si bien existen técnicas basadas en generar múltiples SVM para tratar el caso multiclase. Los árboles de decisión, sin embargo, pueden trabajar directamente con problemas multiclase. 3. Las SVM, en su planteamiento más simple, se benefician de que el problema sea linealmente separable, mientras que a los árboles de decisión no les influye esta propiedad del problema. Finalmente, los árboles de decisión son capaces de aprender todos los ejemplos del conjunto de entrenamiento, incluso aquellos que sean banales o espurios y tengan poco que ver con la hipótesis predictiva que el clasificador pretende modelar. Se dice que los árboles de decisión podrían sufrir en ese caso un problema de sobreentrenamiento. Existen técnicas en la construcción de árboles que palían con éxito este efecto. A diferencia de los árboles, las SVM no suelen tener este problema. Se dice que un clasificador generaliza, cuando sus predicciones no acusan el efecto del sobreentrenamiento Máquinas de Vectores Soporte, SVM Una forma de abordar el problema de la clasificación es utilizar un modelo lineal. Sea x una instancia de un conjunto de datos X R n cuyas clases toman los valores y { 1,+1}. Entonces, un modelo lineal viene definido por la siguiente ecuación del hiperplano en R n f(x) = n w i x i + b = w x + b (2.1) i=1 Donde w i son los coeficientes de ese hiperplano y b el término independiente. El sumatorio indica el producto escalar entre el vector normal al hiperplano y

23 2.1. CLASIFICADORES BASE UTILIZADOS EN ESTA TESIS 9 cada instancia x. El signo de f(x) para un x determinado, indicará si la instancia queda a un lado u otro de dicho hiperplano, clasificándola como 1 o +1. En principio, los modelos lineales asumen que el conjunto de datos es linealmente separable. Es decir, es posible encontrar al menos un hiperplano que separe a todas las instancias de una clase de las instancias de la otra. La utilización de modelos lineales no es reciente (e.g., el discriminante lineal de Fisher, 1936 [37] o el perceptrón de Rosenblatt, 1956 [104]). Las máquinas de vectores soporte (SVM) [115] pueden considerarse que pertenecen a esta familia. La peculiaridad de las SVM sobre sus predecesoras es que maximizan el margen y ello las permite obtener muy buenos resultados, porque son capaces de generalizar muy bien. Se adjunta a continuación, a modo de resumen, una serie de explicaciones acerca de esta propiedad de maximización del margen. Dichas explicaciones están extraídas de [16, 108]. Maximización del Margen Sea un conjunto de datos X linealmente separable por un hiperplano, y sean d + y d la distancias que separan a dicho hiperplano de las instancias más cercanas correspondiente a cada clase. La maximización del margen significa que el hiperplano es tal que maximiza la suma de esas dos distancias. Esto ocurre cuando d + = d, es decir cuando el hiperplano equidista de esos puntos. Escalando los coeficientes w del hiperplano, se puede hacer que para x i X e y i { 1,+1} se verifique: x i w + b +1 para y i = +1 x i w + b 1 para y i = 1 (2.2) Cada una de estas dos restricciones indican que todas las instancias están separadas del hiperplano por una cierta magnitud, que en este caso se ha considerado unitaria (podría haberse elegido cualquier otra constante). Al combinar ambas restricciones en una sola expresión queda: y i ( x i w + b) 1 0, i (2.3) De donde d + = d = 1/ w, por lo que el margen es 2/ w, que se maximiza minimizando w 2 sujeto a la restricción (2.3). Supuesto que X tiene l instancias, el problema se puede plantear tomando multiplicadores de Lagrange α i 0,i = 1,...,l. L P 1 2 w 2 l α i (y i ( x i w + b) 1) (2.4) i=1 Que es la forma Primaria 2 del problema. Ahora el problema se traduce en minimizar L P respecto a las variables w y b, maximizándolo respecto las variables α i. Igualando las derivadas parciales de w y b en (2.4) a cero se llega a: 2 En lo que sigue la terminología en castellano de este apartado se tomará de [54].

24 10 CAPÍTULO 2. CONCEPTOS PREVIOS Y ESTADO DEL ARTE w = 0 = l α i y i x i (2.5) i=1 l α i y i (2.6) i=1 Sustituyendo (2.5) y (2.6) en (2.4), se obtiene la forma Dual del problema: L D l α i 1 2 i=1 l α i α j y i y j x i x j (2.7) i,j=1 Como se verá más adelante, la forma dual tiene otras ventajas, pues permite hallar el hiperplano en espacios diferentes al original. Si se denotasen como H + y H a los dos hiperplanos que: (i) son paralelos al hiperplano de la SVM y, (ii) contienen los puntos que distan d + (d ) del hiperplano de la SVM; se tendría que los puntos que verifican la igualdad en (2.3) son los que pertenecen a H + y H, que son los que están más cercanos a la zona limítrofe entre las dos regiones del problema, y que se conocen como Vectores Soporte, mientras los que verifican la desigualdad estricta en (2.3) son los que quedan del lado del plano más alejado de esa zona limítrofe. Los Vectores Soporte son los que dan nombre al método. Como se verá más adelante las instancias que no son vectores soporte no influyen en el cálculo de la SVM. En el caso de que las regiones correspondientes a las clases no fuesen linealmente separables, se introducen en la formulación del problema unas variables positivas ξ i,i = 1...l, llamadas variables de holgura, de manera que las restricciones en (2.2) quedan en la forma: x i w + b +1 ξ i para y i = +1 x i w + b 1 + ξ i para y i = 1 ξ i 0 i (2.8) De donde se deduce que cuando una instancia x i esta mal clasificada por el hiperplano, le ha de corresponder un ξ i mayor que uno, de donde, a su vez se deduce que i ξ i es una cota superior del número de errores de entrenamiento. Al incorporar el coste de estos errores de entrenamiento, la función objetivo a minimizar pasa de ser w 2 /2 a ser w 2 /2+C i ξ i, donde C es un parámetro de coste a elegir para cada conjunto de datos, de forma que cuanto mayor sea C más se penalizarán los errores. La forma primal del Lagrangiano queda ahora como: L P 1 2 w 2 + C i l l ξ i α i {y i ( x i w + b) 1 + ξ i } µ i ξ i (2.9) i=1 i=1

25 2.1. CLASIFICADORES BASE UTILIZADOS EN ESTA TESIS 11 Donde los µ i son los multiplicadores de Lagrange asociados a la restricción de que todos los ξ i sean mayores o iguales que cero. Al igualar las derivadas parciales de w, b y ξ i a cero se llega a: w = 0 = l α i y i x i (2.10) i=1 l α i y i (2.11) i=1 0 = C α i µ i (2.12) Sustituyendo (2.10), (2.11) y (2.12) en (2.9) queda la forma dual para el caso no linealmente separable: L D l α i 1 2 i=1 l α i α j y i y j x i x j (2.13) i,j=1 que parece la misma que para el caso separable (2.7). La diferencia es que la restricción (2.12) unida a que las µ i son mayores o iguales que cero, da lugar a que en el caso no separable habrá de verificarse 0 α i C. Es decir, ahora las α i están acotadas también superiormente. En [108] puede encontrarse una explicación intuitiva de esta cota superior. Esa explicación se basa en que la forma primal del Lagrangiano para el caso no separable (2.4) ha de minimizarse respecto a w y b, pero a la vez ha de maximizarse respecto a los α i, es decir se trata de hallar un punto de silla. Cuando una instancia esté mal clasificada la restricción y i ( x i w +b) 1 0, i, no se verifica haciendo que el término (y i ( x i w + b) 1) sea negativo. Como α i 0 y el sumatorio tiene signo menos, haciendo los multiplicadores α i todo lo grandes que se desee, el Lagrangiano va aumentando respecto a esa variable. Por tanto, en esas instancias la maximización del Lagrangiano respecto a los α i lleva a que los α i tiendan a infinito. Al añadir el coste C lo que se hace es limitar el crecimiento de los α i para esos casos. Esta misma línea de razonamiento sirve para ver como los α i toman el valor cero en el caso de que la instancia a clasificar verifique la desigualdad estricta y i ( x i w + b) 1 > 0 (i.e., esté bien clasificada pero no sea un vector soporte), pues y i ( x i w +b) 1 contribuye con signo positivo al sumatorio que a su vez tiene signo menos, luego α i = 0 anula ese término, maximizando el Lagrangiano. La forma dual (2.13), tiene la ventaja de que el Lagrangiano queda expresado únicamente en términos del producto escalar de las instancias del conjunto de datos. Esto permite generalizar el método utilizando funciones de decisión que no sean hiperplanos en el espacio del conjunto de datos, pero si que lo sean en otros espacios quizás de dimensión superior. Una función núcleo es una función K, tal que para dos instancias cualquiera del conjunto de datos x i e x j

26 12 CAPÍTULO 2. CONCEPTOS PREVIOS Y ESTADO DEL ARTE K(x i,x j ) = φ(x i ).φ(x j ) φ(x) : R n F (2.14) Es decir, φ(x) es una transformación que permite llevar a las instancias del espacio original a otro espacio F, con otra dimensión (incluso de dimensión infinita). La función K permite calcular el producto escalar x i x j sin necesidad de utilizar la transformación φ. Problemas que no son linealmente separables en el espacio original del conjunto de datos pueden serlo, o estar más cerca de serlo en F. En esta tesis no se han utilizado nunca una SVM con ninguna función núcleo que trasladara el problema a otro espacio (i.e., el hiperplano siempre ha estado definido en el espacio original del problema), o dicho de otra forma, la función núcleo utilizada ha sido la lineal. Esto ha sido debido a que: 1. En los métodos propuestos, las SVM se han utilizado como clasificadores base de algún multiclasificador, y la opción lineal es la más rápida computacionalmente, lo cual es muy interesante cuando cada multiclasificador tiene que calcular por ejemplo 50 SVM, como ha ocurrido en bastantes de los experimentos. 2. El interés de los experimentos no ha sido tanto el de encontrar la mejor SVM para cada problema, sino tener una idea comparativa de los métodos multiclasificadores que usan SVM. Para ello, una opción razonable y a la vez manejable en cuanto a número de casos posibles a experimentar, es que todos usaran el mismo tipo de SVM. 3. El resto de funciones núcleo necesitan de más parámetros además del ya mencionado parámetro de coste. La sensibilidad a estos parámetros por parte de la SVM puede ser grande, y no existe una razón objetiva para dar unos valores concretos; habría que hallar los valores óptimos de los parámetros para cada caso. Optimizar los parámetros en multiclaficadores de 50 SVM, con validaciones experimentales sobre un gran número de conjuntos de datos, tiene un elevado coste computacional y por ello se ha renunciado a hacerlo. Por ello, parece razonable usar un tipo de SVM lo menos sensible posible a la optimización de parámetros. Existen funciones núcleo para SVM que permiten trabajar con strings o secuencias de símbolos directamente (i.e., String Kernels [53]). Dos aplicaciones fundamentales de este tipo de funciones núcleo son la categorización de textos [24] y la de secuencias en bioinformática (e.g., proteínas formadas por aminoácidos) [24, 71]. En el primer caso la función núcleo puede depender de qué palabras tienen en común los dos textos, en el segundo de alguna función de similitud entre las secuencias. En el caso de la categorización de textos es posible conocer de antemano el léxico o conjunto de secuencias posibles, y la clasificación suele ser multietiqueta (i.e., a una instancia se le asignan varias clases simultáneamente).

27 2.1. CLASIFICADORES BASE UTILIZADOS EN ESTA TESIS 13 En el caso de la clasificación de proteínas, el léxico se asume que consiste en todas las combinaciones posibles de símbolos de una longitud máxima dada. Además, en este caso, la coincidencia de las secuencias no tiene porqué ser exacta, pues puede haber símbolos intercalados (e.g. en una proteína podría haber bases intercaladas en la cadena de aminoácidos). Los SVM con String Kernel no necesitan convertir los datos a numéricos, sino que procesan directamente las cadenas. Para ello, las funciones núcleo asociadas se definen internamente en base a expresiones que ponderan la importancia de las secuencias según su peso, y que de alguna forma hacen un recuento del número de secuencias en común entre las dos instancias x i y x j que sirven de parámetros en la ecuación (2.14), de forma que si las instancias son parecidas, su la función núcleo devolverá un valor elevado. Estos problemas específicos para los que se utilizan String Kernels no son los que se abordan en esta tesis, que expone métodos que utilizan SVM que trabajan con conjuntos de datos con atributos numéricos y/o nominales (ver capítulo 4), y métodos que utilizan SVM con datos únicamente nominales (ver capítulo 3). En el caso de los atributos nominales, cada atributo toma un valor de entre varias etiquetas posibles, las cuales no pueden ser entendidas como secuencias de símbolos. Por ello, se asume que las SVM que se van a utilizar, al ser clasificadores que trabajan con entradas numéricas, necesitan que las entradas categóricas o nominales sean transformadas en números. Para ello, en esta tesis, mientras no se indique lo contrario, las SVM utilizadas realizan la transformación nominal a binario (NBF). Esto es, cada atributo nominal que pudiese tomar m valores se sustituye por m atributos binarios, de forma que cuando un atributo categórico original tome el valor nominal i-ésimo, el atributo binario i-ésimo tomará el valor uno, y el resto tomará valores cero. Las SVM, por otro lado, son clasificadores binarios. Es decir, en principio no son capaces de trabajar directamente con conjuntos de datos con más de dos clases. En esta tesis, se asume que las SVM utilizadas usan la aproximación uno contra uno [60], para resolver dicho problema. Es decir, se crea una SVM por cada combinación de dos clases, entrenado únicamente con instancias de dichas dos clases. En un problema de c clases esto da lugar a c(c 1)/2 SVM. Al predecir se toma la clase que más veces es predicha por todas estas SVM. Asimismo, también se asumirá en adelante, que los atributos que sirven de entrada a una SVM están normalizados a partir de los valores del conjunto de entrenamiento, para evitar que unos predominen artificialmente sobre otros. Finalmente, conviene comentar que las SVM son clasificadores sensibles a cambios de pesos en las instancias y ello permite que sean utilizadas dentro de multiclasificadores que puedan aprovechar esta característica (p.e Boosting, como se verá más adelante). Para ello, hay que ponderar el coste del error de clasificación según la importancia de cada instancia. Esto se logra redefiniendo el problema de minimizar w 2 /2+C i ξ i como minimizar w 2 /2+C i ξ ip i, donde p i es el peso de la instancia x i dentro del conjunto de datos. La forma dual que se obtiene es la misma, pero la restricción 0 α i C, queda ahora de la forma 0 α i Cp i.

Sitemap