Estudio de Bootstrapping en algoritmos de clasificación

i Proyecto Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Estudio de Bootstrapping en Algoritmos de Clasificación Autor: Gonzalo Franco Ceballos Tutor: Teodoro Álamo Cantarero Dep. Ingeniería de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2015 ii ii iii iii Estudio de Bootstrapping en Algoritmos de Clasificación Estudio de Bootstrapping en Algoritmos de Clasificación Autor: Gonzalo Franco Ceballos Tutor: Teodoro Álamo Cantarero Catedrático de Universidad Dep. Ingeniería de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2015 iv iv Proyecto Fin de Grado: Estudio de Bootstrapping en Algoritmos de Clasificación Autor: Gonzalo Franco Ceballos Tutor: Teodoro Álamo Cantarero El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2015 El Secretario del Tribunal v v Estudio de Bootstrapping en Algoritmos de Clasificación A mis padres vi AGRADECIMIENTOS Agradezco a mi profesor y tutor Teodoro Álamo por toda su ayuda e increíble disposición a lo largo del desarrollo de todo el proyecto, y más aún por brindarme la posibilidad de colaborar con él estos últimos tres años. Ha sido una experiencia muy enriquecedora y motivadora que me ha ayudado a entender mejor numerosos campos de interés del área de Ingeniería de Sistemas y Automática. También agradezco a mi familia por su incondicional apoyo durante toda la carrera, especialmente a mis padres, que han estado junto a mí transmitiéndome ánimos durante todo el camino. vii RESUMEN Este documento recoge un estudio de la aplicación de técnicas basadas en bootstrapping a problemas de clasificación. La primera técnica, el bagging, pretende mejorar los resultados y la estabilidad del clasificador mediante un conjunto de expertos entrenados con elementos muestreados mediante bootstrapping. La segunda técnica tiene como objetivo realizar una predicción del ratio de acierto de un clasificador entrenado mediante bagging con una confianza determinada. Para la realización del estudio se ha probado cada una de las técnicas en tres problemas de clasificación distintos, dos de ellos multiclase, con el objetivo de comprobar si las técnicas estudiadas tienen impactos diferentes en cada uno de los problemas. El objetivo final del estudio es el desarrollo de estos algoritmos de mejora de resultados y la comprobación de que realmente se consigue una mejora sustancial de los mismos. viii ABSTRACT The following report analyzes a study of the application of several techniques based on bootstrapping to a classification problem. The first of these techniques, the bagging technique, seeks to improve the results and the stability of the classifier by means of a group of experts trained with elements sampled using bootstrapping techniques. The second technique’s goal is to make a prediction of the success rate of the classifier trained using bagging techniques with a designed confidence. To conduct the study, each of these techniques have been tested on three different classification problems, two of them being multiclass, in order to observe if their impact varies from one problem to another. The main goal of the study is the development of the algorithms and checking that there is actually a notable improvement in the results obtained. ix ÍNDICE Agradecimientos vi Resumen vii Abstract viii Índice ix Índice de Tablas xii Índice de Figuras xiii 1 Introducción 1 1.1 Objetivos 1 1.2 Organización de la memoria 2 2 Conceptos Teóricos 3 2.1 El Problema de clasificación 3 2.1.1 Ejemplo 2.1: problema de clasificación. 3 2.1.2 Ejemplo 2.2: problema de clasificación. 5 2.2 Algoritmos de clasificación 6 2.2.1 Descripción 6 2.2.2 Fases de desarrollo de un clasificador 7 2.3 Árboles de decisión 8 2.3.1 Funcionamiento 8 2.3.2 Algoritmo de Hunt 9 2.3.3 Trabajando con valores continuos 11 2.3.4 Elección de la partición 12 2.3.5 Particionado según valores continuos 14 2.3.6 Criterios de parada 14 2.4 Bootstrapping 15 2.4.1 Método de bootstrapping 15 2.4.2 Ejemplo 4.1: bootstrapping 16 2.5 Bagging 18 2.6 Bagging para la estimación del ratio de acierto 19 3 Presentación Del Problema 21 3.1 Selección de los datos 21 1 1 INTRODUCCIÓN Durante mis años de colaboración en el departamento de Ingeniería de Sistemas y Automática he tenido la oportunidad de profundizar en el tema del procesamiento de datos y de información. Gracias a esto, he investigado y trabajado en varios campos que tratan grandes cantidades de datos con distintos objetivos. Uno de ellos es el Aprendizaje Automático. El proceso mediante el cual un sistema informático puede aprender a distinguir patrones, predecir sucesos o inferir relaciones es realmente interesante. Un aspecto que me llamó inmediatamente la atención es lo sujeto que están unos buenos resultados a la buena intuición del programador. A menudo no es sencillo distinguir cuál puede ser la mejor aproximación a un problema, y está en la mano de la persona que programa el algoritmo el elegir correctamente tanto las técnicas de inferencia, clasificación, etc. como las de tratamiento de datos con el fin de aumentar el rendimiento y la precisión del programa. Es en este segundo aspecto en el que se centra este estudio. 1.1 Objetivos A continuación se describen los objetivos fijados para la realización del estudio. Se muestran en orden cronológico, tal como se han ido alcanzando a lo largo del proceso. 1- Entendimiento de un algoritmo de clasificación. No sólo el que se utiliza en este estudio, durante mi tiempo de colaboración en el departamento de Ingeniería de Sistemas y Automática, he investigado sobre varios algoritmos de clasificación, algunos de invención propia y otros ampliamente utilizados, como son los algoritmos de regresión, las máquinas de vectores de soporte, los k-vecinos más cercanos y los random forests. 2- Selección del método de tratamiento de datos. El objetivo del proyecto es la utilización de algún método que ayude a mejorar un algoritmo de clasificación. La técnica de bootstrapping aplicada al algoritmo correcto ilustra muy bien cómo se pueden mejorar los resultados con un tratamiento de los datos. 3- Selección de los datos. Se intentará utilizar sets de datos vistosos desde el punto de vista del problema de clasificación. Ya que este estudio no se centra en el problema de clasificación sino en cómo mejorarlo, he creído conveniente elegir datos con un alto índice de acierto por parte del clasificador. 4- Elección de las herramientas de programación. Se buscará tanto el lenguaje de programación más adecuado como el entorno de programación, con el fin encontrar el conjunto de herramientas que permita llevar a cabo el estudio de la forma más cómoda y eficiente posible. 5- Programación de los algoritmos. 6- Investigar el impacto que tiene la aplicación de la técnica de tratamiento de datos en los resultados, aplicando clasificador. Una vez elegidos el clasificador y el método de tratamiento de datos, analizan los resultados obtenidos, comparándolos con los que se 2 2 Introducción alcanzan sin la técnica de tratamiento de datos. 1.2 Organización de la memoria En el Capítulo 2 se hace una introducción de los conceptos aprendidos en el punto 1 de los objetivos del proyecto. Se explica lo que es un algoritmo de clasificación y cómo funciona, y se presentan dos ejemplos sencillos en los que se ilustra la utilidad de un clasificador. A continuación se explica el proceso de desarrollo de un clasificador cualquiera. Se profundiza en el clasificador que se va a utilizar en el estudio: el árbol de decisión, y se continúa explicando la técnica de mejora de resultados escogida para el estudio, el bootstrapping, así como su aplicación a un problema de clasificación. Por último se describe el segundo método que es objeto de estudio: la estimación del ratio de acierto mediante bootstrapping. En el Capítulo 3 se presentan los tres problemas de clasificación escogidos y se describen sus principales características. El Capítulo 4 recoge toda la información sobre el trabajo realizado en el estudio. Se describen las herramientas de trabajo utilizadas y se justifica su elección. Se explica cada uno de los algoritmos y se describen los elementos más destacables del código. Se enumeran y explican las funciones más importantes que se han utilizado, tanto las incluidas en el paquete de trabajo escogido como las desarrolladas especialmente para el estudio. También se detallan los bloques más importantes, que están programados en scripts. En el capítulo 5 se muestran los resultados del trabajo para cada uno de los métodos de clasificación descritos a lo largo de este documento. Aquí también se incluye el análisis de los resultados para cada uno de los casos, así como explicaciones y aclaraciones de los distintos métodos al ser aplicados a cada caso concreto. El Capítulo 6 incluye un análisis de conjunto de los resultados mostrados en el Capítulo 5, y una comparativa de los distintos métodos con el objetivo de cuantificar la mejora conseguida con las técnicas estudiadas. Por último, en el Capítulo 7 se muestra el código desarrollado. 3 2 CONCEPTOS TEÓRICOS Si bien el objeto de este proyecto no es el de profundizar en las distintas técnicas de clasificación, sí que he creído conveniente una breve explicación de los conceptos básicos. En este primer capítulo se define el problema de clasificación, a continuación se explica el concepto de algoritmo de clasificación y se justifica su necesidad, y finalmente se describe en detalle el funcionamiento de un clasificador concreto: el árbol de decisión, que será el utilizado a lo largo de este estudio. Posteriormente se presenta la técnica de mejora de resultados elegida, el bootstrapping, y se detalla su aplicación en el problema de clasificación a través de la técnica de bagging. 2.1 El Problema de clasificación El problema de clasificación es aquel que tiene como objetivo predecir o estimar a qué categoría pertenece una determinada observación. Para ello, previamente se ha llevado a cabo un número de observaciones sobre un conjunto de muestras cuya clase se conoce a priori, con el objetivo de aprender las diferencias entre ellas. Una vez finalizadas estas observaciones, y en base a ellas, se intenta identificar a qué clase pertenece la nueva muestra. Para llevar a cabo esta tarea, se desarrollan algoritmos de clasificación, también llamados clasificadores. Estos encuentran y aproximan de manera automática la relación entre las características del conjunto de muestras y su salida, o clase. 2.1.1 Ejemplo 2.1: problema de clasificación. Consideremos ahora el problema de clasificación que se ilustra en la figura 2.1.1, donde se tiene un determinado número de observaciones. Cada una de ellas pertenece a la clase 1 o a la clase 2. Posteriormente se recibe una nueva muestra y se desea saber a qué clase pertenece. Como se ha explicado anteriormente, primero se deben observar las muestras conocidas y realizar algún tipo de distinción entre ellas. En este ejemplo he optado por separar el espacio en dos subregiones, una para cada clase, mediante una ecuación cuadrática en el sentido de los mínimos cuadrados (ver figura 2.1.2). Se observa que la curva calculada no separa perfectamente las dos clases, por lo que resultaría lógico preguntarse si existe alguna otra que separe el espacio mejor. En efecto, se podría, por ejemplo, trazar una línea recta que divida perfectamente a las dos clases. No existe una única forma de clasificar, del mismo modo que no existe un único clasificador para un problema de clasificación. En la mayoría de las veces no es sencillo predecir qué tipo de algoritmo de clasificación va a funcionar mejor para un problema dado. Llegados a este punto, sólo resta observar en qué región se encuentra la nueva muestra y, así, hacer la clasificación. En el ejemplo, la nueva muestra resulta pertenecer a la clase 2. Esto no es más que una estimación o predicción, pudiendo ser la clase 1 la verdadera clase de la muestra. 4 4 Conceptos Teóricos Figura 2.1.1 - Ejemplo 1: problema de clasificación. Figura 2.1.2 - Aproximación por una curva cuadrática. 5 5 Estudio de Bootstrapping en Algoritmos de Clasificación 2.1.2 Ejemplo 2.2: problema de clasificación. Un problema de clasificación puede ser mucho más complicado que el descrito en el ejemplo 1. En la figura 1.1.3 se muestra un problema en el que las dos clases no están claramente diferenciadas: existe una región del espacio donde se encuentran solapadas. Este hecho va a conllevar un inevitable porcentaje de muestras clasificadas de manera errónea al aplicar el clasificador a un nuevo set de muestras. En este caso he optado por separar las clases mediante elipses (ver figura 2.1.4). Al estar las muestras pertenecientes a la clase 2 más concentradas que las de la clase 1, se clasificará cualquier futura muestra como clase 2 si cae dentro de la elipse que encierra todas las muestras de la clase 2, y clase 1 en el caso contrario. Los problemas descritos en los ejemplos sólo dependen de dos variables con objeto de ilustrar los conceptos de una manera gráfica. En la realidad raramente ocurre esto, teniendo en muchos casos centenares o miles de variables de las que depende el resultado del problema. Para estos casos a menudo se hacen necesarias técnicas más avanzadas de clasificación que quedan fuera del alcance de este proyecto. Figura 2.1.3 - Ejemplo 2: problema de clasificación. 6 6 Conceptos Teóricos Figura 2.1.4 - Clasificación usando elipses. 2.2 Algoritmos de clasificación A la vista de los ejemplos anteriores, resulta útil el desarrollo de algún tipo de algoritmo que, de forma automática, sea capaz de aprender a partir de un determinado número de observaciones, para luego poder predecir o estimar la clase de una nueva muestra. Esto se hace absolutamente necesario en el caso de tener problemas complejos con un elevado número de muestras y de variables de las que depende el resultado. A continuación se describe el proceso de desarrollo de un clasificador cualquiera. 2.2.1 Descripción Se parte de dos conjuntos de muestras cuyas clases son conocidas. Uno de esos conjuntos – llamado set de entrenamiento - se utilizará para entrenar al clasificador, y el otro – set de validación - se utilizará para hacer predicciones y comprobar el grado de acierto del clasificador. Formalmente, se tiene un set de entrenamiento, *𝑥𝑖,𝑦𝑖+, 𝑖 =1,…,𝑁, Donde 𝑥𝑖∈ 𝑹𝑛𝑥 denota el vector de variables de la muestra i, 𝑦𝑖∈*𝑐𝑙𝑎𝑠𝑒1,𝑐𝑙𝑎𝑠𝑒2,…+ es la salida discreta, o clase de cada muestra i. Se tiene un clasificador cualquiera, C. Y se tiene un set de validación, *𝑥𝑣𝑖,𝑦𝑣𝑖+, 𝑖 =1,…,𝑁𝑣 , 7 7 Estudio de Bootstrapping en Algoritmos de Clasificación Donde 𝑥𝑣𝑖 ∈𝑹𝑛𝑥 denota el vector de variables de la muestra i, 𝑦𝑣𝑖 ∈*𝑐𝑙𝑎𝑠𝑒1,𝑐𝑙𝑎𝑠𝑒2,…+ es la salida discreta, o clase de cada muestra i. A las variables también se les llama marcadores, atributos o características. 2.2.2 Fases de desarrollo de un clasificador El desarrollo de un clasificador se lleva a cabo en tres fases: 1- Fase de entrenamiento. 2- Fase de validación. 3- Fase de ajuste. En la fase de entrenamiento se llevan a cabo todas las operaciones necesarias para ajustar el set de entrenamiento, *𝑥𝑖,𝑦𝑖+, a un modelo. Este modelo trata de representar la relación entre 𝑥𝑖 e 𝑦𝑖, separando el espacio de 𝑹𝑛𝑥 dimensiones en subregiones, cada una de ellas asociada a una de las clases posibles, de manera que dada una nueva muestra, la clase estimada de ésta será aquella correspondiente a la región donde se encuentre. Posteriormente, en la fase de validación, se utiliza el set de validación, *𝑥𝑣𝑖,𝑦𝑣𝑖+, para comprobar cómo de bien clasifica el algoritmo. Esto se hace haciendo una predicción para cada muestra 𝑥𝑣𝑖 ∈ 𝑹𝑛𝑥, y comparando el resultado con su salida real 𝑦𝑣𝑖 ∈*𝑐𝑙𝑎𝑠𝑒1,𝑐𝑙𝑎𝑠𝑒2,…+. Si tras la validación se observa que los resultados no son adecuados se llega a la fase de ajuste, donde se procede a modificar el clasificador ya sea cambiando la técnica de clasificación, modificando el set de entrenamiento, o ajustando los parámetros de los que pueda depender el clasificador. Figura 2.2.1 – Fase de entrenamiento. Figura 2.2.2 – Fase de validación. Como se observa, el clasificador sólo aprende a partir de un subconjunto de muestras, y luego se comprueba su efectividad aplicando lo aprendido a un segundo subconjunto. Es importante que el aprendizaje y la validación se hagan con conjuntos distintos para poder garantizar la imparcialidad del clasificador. Si no fuera así, se daría el caso de clasificar muestras cuya clase ya 8 8 Conceptos Teóricos se conoce y se ha utilizado para entrenar al algoritmo, obteniéndose unos resultados mejores que los que correspondería y falseando los resultados. Visto de otro modo: un clasificador lleva a cabo una transformación 𝑹𝑛→ 𝑵, siendo n el número de parámetros de los que dependen las muestras, y 𝑵=*𝑐1,𝑐2,…,𝑐𝑐+ las posibles clases, de manera que cada nueva muestra tiene una transformación sobre N, siendo su valor el resultado del proceso de clasificación. 2.3 Árboles de decisión En este apartado se describe el funcionamiento de un Árbol de decisión, que es el clasificador que he elegido en este estudio. Este clasificador tiene una serie de ventajas que se discutirán más adelante. 2.3.1 Funcionamiento Para describir el funcionamiento de un Árbol de decisión, imaginemos el siguiente ejemplo. Se desea predecir qué modelo de coche comprará un cliente en base a su perfil. Para ello se cuenta con un registro de clientes anteriores que compraron uno de los dos modelos que se muestran en la tabla 2.3.1. La técnica a utilizar es muy sencilla: ir haciendo preguntas sobre los atributos de la nueva muestra (cliente), y así ir acotando la solución del problema hasta llegar a una solución final. Observación Hijos Salario anual Sexo Edad Modelo 1 2 20.500 H 32 Deluxe 2 0 18.000 H 23 Berlina 3 4 27.000 M 35 Berlina 4 1 19.500 M 28 Berlina 5 1 40.000 H 58 Deluxe 6 0 12.000 H 37 Berlina 7 2 25.000 H 25 Berlina 8 1 14.600 M 25 Berlina 9 1 21.000 H 29 Deluxe 10 3 17.000 H 40 Berlina Tabla 2.3.1 - Clasificación de clientes. La primera pregunta que se puede hacer es si el cliente es hombre o mujer, pues se observa que sólo los hombres compran el modelo deluxe. Así, si la respuesta es mujer, se puede dar por finalizado el problema prediciendo que su compra será la del modelo berlina. En caso de ser hombre, se procede a la siguiente pregunta: ¿es su sueldo anual mayor o menor que 20.000? pues se observa que todos los clientes que eligieron la clase deluxe tenían un sueldo superior a 20.000. Por último se podría hacer la siguiente pregunta: ¿es su edad superior a 27? Si es así, la clase asociada a ese cliente será deluxe, en caso contrario, berlina. Las preguntas que se han elegido y el orden en el que se han formulado no son únicos, siendo 9 9 Estudio de Bootstrapping en Algoritmos de Clasificación realmente difícil encontrar la combinación óptima. En este ejemplo parece bastante claro qué preguntas hacer y en qué orden para alcanzar una solución con el menor número de preguntas posible, pero en la mayoría de los casos no resulta tan evidente, dejándose que sea el propio algoritmo el que decida qué preguntas hacer y cómo organizarlas en base a unas reglas que se explican más a delante. Figura 2.3.1 - Árbol de decisión Un árbol de decisión está compuesto por nodos, representando cada uno de ellos una condición. Cada nodo contiene todas las muestras provenientes de la condición anterior. Los nodos están organizados en una jerarquía de arriba abajo, y se pueden clasificar en: 1- Nodo raíz: es el comienzo del árbol. No tiene ningún arco de entrada. 2- Nodo interno: se encuentran dentro del árbol. Tienen un arco de entrada y dos o más de salida. 3- Nodo hoja: se encuentran al final del camino. Tienen un arco de entrada y ninguno de salida. Tienen asociada una etiqueta con el resultado obtenido en caso de ser alcanzados. Los nodos internos y raíz dividen grupos de muestras con características diferentes para ir obteniendo subgrupos más puros. Este concepto de pureza se explica más adelante. El objetivo de un árbol de decisión es conseguir subdividir las muestras en grupos que sólo contengan una de las clases. Esto, a pesar de ser posible en muchos casos, no se llega a alcanzar, imponiéndose condiciones de parada adicionales que evitan el fenómeno de sobre-ajuste u overfitting. 2.3.2 Algoritmo de Hunt Como se ha explicado anteriormente, existen numerosas formas de generar un árbol de decisión. En el ejemplo anterior quedaba de manifiesto que hay formas de seleccionar y organizar las preguntas mejores que otras. Lamentablemente, a medida que crece el problema lo hace también el árbol, haciéndose imposible desde un punto de vista computacional dar con la organización óptima. 16 16 Conceptos Teóricos entre sí. La técnica de bootstrapping se suele utilizar para: 1- Dibujar histogramas. 2- Calcular desviaciones típicas y errores estándar. 3- Crear intervalos de confianza Figura 2.4.1 - Proceso de bootstrapping. 2.4.2 Ejemplo 4.1: bootstrapping Se tiene una población desconocida, a partir de la cual se extrae un conjunto de muestras como el que se muestra en la figura 2.4.2. Es importante aclarar de nuevo que esta no es la distribución de la población, sino la de un conjunto de muestras tomadas aleatoriamente de ella. 17 17 Estudio de Bootstrapping en Algoritmos de Clasificación Si se tratarse de la población no sería necesaria ninguna técnica de estimación, pues se podrían obtener directamente los valores exactos a partir de los datos. Figura 2.4.2 - Distribución del conjunto de muestras M. Se puede ver que los valores muestreados son: 𝑀 = *1,1,1,2,3,3,3,3,4,4,5,6,6,+ Supóngase que se quiere calcular la media de la población. A partir de los datos, esta tendrá un valor de la media 𝜇 =3,2308 y la desviación típica 𝜎 =1,7394. A continuación se muestrea este set de muestras 1.000 veces con reposición, obteniendo por tanto 1.000 sub-sets de muestras: 𝑋(1) =*4,3,5,3,6,4,2,3,1,3,6,4,3+ → 𝜇1=3.6154 𝑋(2) =*6,3,1,6,3,6,5,4,3,4,4,4,5+ → 𝜇2=4.1538 ⋮ 𝑋(1000) =*2,6,5,6,3,3,5,4,4,3,1,3,6+ → 𝜇1000 =3.9231 Obteniéndose un conjunto de estimadores, 𝜇 = *𝜇1,𝜇1,…,𝜇1000+= *3.62,4.15,…,3.92+ 18 18 Conceptos Teóricos Que, como se puede apreciar en la figura 2.4.3, presenta una distribución gaussiana. Esto ocurrirá siempre que el número de muestras de bootstrapping, B, sea lo suficientemente grande. Figura 2.4.3 - Distribución del conjunto de estimadores, 𝜇. La media del conjunto de estimadores resulta ser 𝜇 =3.2412, aproximadamente igual a la media del conjunto de muestras tomadas de la población, M. La desviación estándar de la media es 𝜎 =0.4747, mucho menor que la desviación estándar de los valores muestreados directamente de la población. 2.5 Bagging La técnica de bagging es una aplicación del concepto de bootstrapping en problemas de regresión y de clasificación estadística. El bagging mejora la estabilidad y la precisión del clasificador, disminuyendo también la varianza de los resultados y disminuyendo el riesgo de sobre-ajuste. Suele tener buenos resultados en métodos basados en árboles de decisión, motivo por el que se eligió dicho clasificador en primer lugar. El método de bagging muestrea con reemplazamiento n veces un conjunto de muestras, con el objetivo de entrenar a n clasificadores. Una vez terminado el proceso de muestreo y aprendizaje, se promedian todos los clasificadores - de dudosa precisión - para conseguir un clasificador mejor, media de todos ellos. Al evaluarse una nueva muestra, cada clasificador emitirá un voto, y será la clase con mayor número de votos la que finalmente se elija. Sea un set de entrenamiento T que contiene n muestras, se muestrea con reposición m veces dicho set, tomando en cada muestreo n muestras. Esto da lugar a 𝐵1,𝐵2,…,𝐵𝑚 sets de muestras 19 19 Estudio de Bootstrapping en Algoritmos de Clasificación por bootstrapping. Si n es lo suficientemente grande, se puede demostrar que el valor esperado de cantidad de muestras distintas en cada muestreo es de aproximadamente 63,2%, siendo el resto muestras repetidas debido a que el muestreo se hace con reposición. Debido a esto, es de esperar que el clasificador sea peor que el que se conseguiría si se entrenara directamente con todas las muestras disponibles, ya que se están usando menos datos en la fase de aprendizaje. Es al unir los m clasificadores cuando se consigue un resultado mejor. Al haber muestreado siempre del mismo set de datos los resultados deben ser parecidos, sin embargo, al muestrear un cierto número de veces se reduce la varianza y aumenta la estabilidad. Esto se debe a que se ha conseguido un clasificador más robusto debido a que se ha aprendido en base a unos datos con una varianza menor, como se ha visto anteriormente al explicar el método de bootstrapping. Figura 2.5.1 - Proceso de bagging. 2.6 Bagging para la estimación del ratio de acierto A la vez que se aplica la técnica de bagging a un problema de clasificación se puede hacer una estimación el ratio de acierto del clasificador, en nuestro caso el árbol de decisión. En cada iteración se muestrea aleatoriamente con reposición, por lo que una determinada cantidad de muestras caerá dentro del set de datos con los que se entrenará al clasificador, quedando las restantes sin utilizar. En este procedimiento se aprovechan estas muestras no utilizadas para 20 20 Conceptos Teóricos validar el clasificador y, así, obtener una estimación del ratio de acierto que se conseguirá al utilizar el clasificador en el set de validación, tal como se muestra en la figura 2.6.1. Figura 2.6.1 - Bagging para la estimación del ratio de acierto. Durante el estudio del clasificador se compara la predicción del ratio de acierto con el resultado final para observar la diferencia entre ambos y buscar intervalos de confianza. Es posible que la predicción sea conservadora en la mayoría de los casos, esto es, consistentemente peor que los resultados finales, consiguiéndose así acotar inferiormente el ratio de acierto. Si no es así, una segunda opción es buscar un intervalo de confianza lo suficientemente grande de la estimación. Todo esto se explica con detenimiento en los capítulos 4 y 5. 21 3 PRESENTACIÓN DEL PROBLEMA En este capítulo se presentan los problemas de clasificación elegidos, describiendo cada set de datos, mostrando sus principales características y justificando su elección. 3.1 Selección de los datos Se han seleccionado tres sets de datos. Flor de iris, Cáncer de mama, y Cáncer de colón. Como se ha mencionado en el capítulo de introducción, el problema de clasificación en si no es el objeto de estudio. Por esto se ha intentado elegir problemas que permiten una buena clasificación con objeto de presentar unos resultados más vistosos, no teniendo este factor influencia a priori en el mejor o peor impacto de ninguna técnica de mejora de resultados. Este es el caso de los dos primeros problemas. El problema Cáncer de colon se clasifica bastante mal para el caso multiclase, éste se utilizará para comprobar si realmente hay una variación notable en los resultados obtenidos para problemas fácilmente clasificables y problemas que presentan dificultades. Para la selección de los datos se han realizado pruebas con distintos clasificadores para comprobar si son problemas que de forma consistente se dejan clasificar correctamente. Es importante notar que no se ha aplicado ninguna técnica de tratamiento de datos cuyos resultados habrían podido condicionar la elección. Llegados a este punto aún se desconoce si las técnicas que se van a utilizar para mejorar los resultados – que sí se garantiza que serán buenos – van a tener un efecto positivo, negativo o nulo sobre ellos. Por último, se han escogido problemas con marcadores de valores numéricos continuos. A continuación se describen los tres sets de datos. 3.2 Flor de iris El set de datos de la flor de iris es uno de los problemas clásicos de clasificación en la literatura. Fue presentado por Ronald Fisher en 1936, y es uno de los ejemplos más utilizados en estudios de clasificación. Es un problema de clasificación multiclase en el que se tienen tres tipos de flor de iris: Iris setosa, Iris virginica e Iris versicolor, y se cuenta con varios marcadores, todos referidos a aspectos morfológicos de la flor: longitud del sépalo, grosor del sépalo, longitud del pétalo y grosor del pétalo. El set de datos cuenta con 50 muestras de cada clase. Clase Cantidad Setosa 50 Virginica 50 Versicolor 50 Total 150 Tabla 3.2.1 - Flor de iris: clases. 22 22 Presentación Del Problema A continuación se muestra un extracto de los mismos: V1 V2 V3 V4 V5 1 1 5,1 3,5 1,4 0,2 2 1 4,9 3 1,4 0,2 3 1 4,7 3,2 1,3 0,2 4 1 4,6 3,1 1,5 0,2 5 1 5 3,6 1,4 0,2 6 1 5,4 3,9 1,7 0,4 7 1 4,6 3,4 1,4 0,3 8 1 5 3,4 1,5 0,2 9 1 4,4 2,9 1,4 0,2 10 1 4,9 3,1 1,5 0,1 11 1 5,4 3,7 1,5 0,2 Tabla 3.2.2 - Flor de iris: set de datos. Donde la primera columna se refiere a la clase: 1 setosa, 2 virginica y 3 versicolor, y las columnas restantes a los cuatro marcadores. 3.3 Cáncer de mama Este segundo set de datos, desarrollado por William Wolberg, Nick Street y Olvi Mangasarian, de la Universidad de Wisconsin (EE.UU.), es también ampliamente utilizado en diversos estudios de aprendizaje automático. Se trata de un problema de dos clases en los que se distingue entre pacientes con dos tipos de cáncer de mama: benigno y maligno. El set de datos cuenta con 569 muestras cuya clase depende de 30 marcadores referidos a distintas características del núcleo de las células cancerígenas. Las clases están repartidas de la siguiente forma: Clase Cantidad Benigno 357 Maligno 212 Total 569 Tabla 3.3.1 - Cáncer de mama: clases. 3.4 Cáncer de colon El último set de datos corresponde a otro problema de clasificación multiclase. En él se distingue entre pacientes con tres condiciones distintas: cáncer de colon, pólipo y sano. Se tienen 202 muestras cuya clase depende de 52 marcadores. Las clases están repartidas de la siguiente forma: 23 23 Estudio de Bootstrapping en Algoritmos de Clasificación Clase Cantidad Colon 86 Pólipo 31 Sano 85 Total 202 Tabla 3.4.1 - Cáncer de colon: clases. 24 4 DESCRIPCIÓN DEL TRABAJO En este capítulo se explican los procedimientos llevados a cabo en la realización del estudio. En primer lugar se describen las herramientas de trabajo utilizadas, posteriormente se presentan los algoritmos desarrollados para cada una de las técnicas, así como las funciones y scripts utilizados. 4.1 Herramientas de trabajo 4.1.1 MATLAB Dada la naturaleza del estudio, un punto crucial ha sido la elección de una herramienta adecuada de programación. Se ha decidido utilizar el programa MATLAB, que es una eficaz herramienta para el desarrollo de algoritmos de corte puramente matemático y que es de amplia utilización en ingeniería. MATLAB incluye un lenguaje de programación propio basado en scripts, que permite una gran flexibilidad y rapidez a la hora de hacer pruebas, modificaciones y detectar errores. Además, MATLAB cuenta con una enorme colección de funciones, todo lo cual convierte su lenguaje de programación en una herramienta realmente potente. Al ser una herramienta orientada al trabajo con matrices, se hace especialmente sencillo el operar con estos elementos tanto por la simple e intuitiva sintaxis como por la gran cantidad de opciones presentes. Por último, todas las herramientas necesarias para el estudio están incluidas por defecto en el programa. Por todo esto he pensado que MATLAB es la herramienta idónea para el desarrollo del trabajo. En momentos puntuales se ha hecho uso del programa RStudio para la lectura de bases de datos y su adaptación a MATLAB. 4.1.2 Equipo utilizado Todo el trabajo, tanto el desarrollo de los algoritmos como la simulación, se ha desarrollado en el siguiente equipo:  Procesador: Intel Core i7-4702MQ 2.2 GHz.  Memoria: 6GB RAM.  Sistema operativo: Windows 8.1 (64bits)  Versión de MATLAB: R2013a (64bits) 25 25 Estudio de Bootstrapping en Algoritmos de Clasificación 4.2 Algoritmos En este apartado se muestran los algoritmos desarrollados para el estudio. 4.2.1 Consideraciones importantes Para el análisis de resultados y de rendimiento de los clasificadores, así como las técnicas de mejora, se ha hecho uso de validación cruzada. Se realizan N experimentos, y se divide aleatoriamente para cada uno de ellos el conjunto de muestras en dos sub-sets: entrenamiento y validación. El set de entrenamiento se usa durante la etapa de entrenamiento del clasificador, y el de validación se usa al final para comprobar su eficacia. Al dividir el conjunto de muestras en entrenamiento y validación, se mantiene la misma proporción de cada clase en ambos sets. Además, se fuerza que el 70% de las muestras caigan en el set de entrenamiento con el fin de tener un número lo suficientemente grande para el aprendizaje del algoritmo, manteniendo un tamaño aún razonable para la fase de validación. Durante la ejecución del algoritmo se hace un seguimiento del acierto sobre cada muestra en validación, de modo que no sólo se obtiene el ratio de acierto del clasificador, sino que también se identifica qué muestras presentan problemas de clasificación. Esta parte del algoritmo no se muestra en los diagramas de flujo por simplicidad. 4.2.2 Algoritmo de árbol de decisión Se presenta el algoritmo de implementación del árbol de decisión utilizado en el estudio, véase la figura 4.2.1. Se fija un número N de experimentos a realizar. Se tiene como resultado N clasificadores, cada uno ofreciendo unos resultados sobre las muestras que hay en el set de validación. 4.2.3 Algoritmo de bagging A continuación se presenta el algoritmo de bagging utilizado en este estudio, véase la figura 4.2.2. Tal cual se ha explicado el método, primero se entrena a los árboles y luego, una vez todos están construidos, se clasifican las muestras de validación. En este caso se ha optado por unir ambas etapas en una. Esto es, para cada árbol que se construye se calcula seguidamente la predicción y se almacena, e inmediatamente después se destruye el árbol. Una vez hechas todas las predicciones, se vota y se genera la predicción final para ese set de entrenamiento. De este modo se evita tener que almacenar en memoria todos los árboles hasta el final del bucle. Esto se puede hacer porque sólo interesan los resultados y no los árboles generados, ya que éstos no se van a volver a usar para predicciones futuras. 32 32 Descripción Del Trabajo 4.5 Funciones Se hace una descripción de las funciones desarrolladas para el estudio. 4.5.1 LoadAllData Esta función carga los datos del problema de clasificación en MATLAB en una matriz de dimensión nxm+1. Cada fila contiene la información de cada una de las n muestras, la primera columna contiene la clase de cada una de ellas, y el resto sus m características. Esta función recibe como parámetro una cadena de caracteres con el nombre del problema de clasificación que se quiere cargar, y devuelve la matriz con los datos del problema. 4.5.2 LoadAllData_KeepingTrack Esta función realiza la misma operación que la función LoadAllData, y además agrupa los datos por clases dentro de la matriz, con el objeto de mostrar una gráfica de dispersión más clara. También se añade una columna a la matriz de datos con el identificador para cada muestra. Esta función recibe como parámetro una cadena de caracteres con el nombre del problema de clasificación que se quiere cargar, y devuelve la matriz con los datos del problema. 4.5.3 BaggingMethod Función que implementa el método de bagging para un árbol de decisión. Recibe como parámetros el set de entrenamiento, las características de las muestras del set de validación y el número de clasificadores que se quiere construir mediante bootstrapping. Devuelve la predicción que es el resultado de los votos de todos los clasificadores. Para hacer el muestreo de bootstrapping se hace una llamada a la función BootStrapping_sample descrita más adelante, y para construir el clasificador y hacer la predicción se hace uso de las funciones classregtree y eval descritas en el apartado 4.3. 4.5.4 BaggingEstimationMethod Es la función que implementa el método de bagging junto con el de estimación del ratio de acierto. Recibe como parámetros el set de entrenamiento, las características de las muestras del set de validación y el número de clasificadores que se quiere construir mediante bootstrapping. Devuelve la predicción que es el resultado de los votos de todos los clasificadores y la estimación del ratio de acierto. Al igual que hacía la función BaggingMethod, se hace una llamada a la función BootStrapping_sample para muestrear el set de entrenamiento. Además, se hace una llamada a la función Bootstrapping_remaining para obtener los datos que no han sido muestreados. Finalmente se llevan a cabo la predicción y la estimación. 4.5.5 BootStrapping_sample Esta función lleva a cabo el proceso de muestreo mediante bootstrapping, que utiliza la técnica de muestreo con reposición tal y como se ha explicado en el capítulo 2. 33 33 Estudio de Bootstrapping en Algoritmos de Clasificación La función recibe como parámetros las matrices Y y X que contienen los identificadores, las clases y las características del set de datos que se quiere muestrear. Devuelve las matrices Xsample e Ysample, que contienen los datos muestreados. Para muestrear se hace uso de la función de MATLAB datasample. 4.5.6 BootStrapping_remaining Esta función identifica los elementos que no han sido muestreados en la fase de bootstrapping. La función recibe como parámetros el set de entrenamiento completo y los índices de los datos muestreados, y devuelve el sub-set de datos no muestreados. Figura 4.5.1 - Función BaggingMethod. 34 34 Descripción Del Trabajo Figura 4.5.2 - Función BaggingEstimationMethod. 35 5 RESULTADOS En este quinto capítulo se muestran los resultados de cada uno de los métodos utilizados en el estudio aplicados a los tres problemas. Además se hace un análisis de los mismos, dejando para el capítulo 6 el análisis comparativo y las conclusiones del estudio. He pensado que es más fácil seguir las explicaciones a medida que se ven los resultados junto con las gráficas, en lugar de simplemente mostrar los resultados sin comentarios por un lado, y su análisis sin las gráficas por otro. 5.1 Aplicación del árbol de decisión a los problemas de clasificación A continuación se muestran los resultados obtenidos tras resolver el problema de clasificación utilizando un árbol de decisión, y con el algoritmo de validación cruzada arriba descrito. Para todos los casos se han llevado a cabo 10.000 experimentos. Para cada problema se muestran dos gráficas. La primera es un histograma que muestra la distribución de la función de probabilidad del acierto. La segunda es una gráfica de dispersión donde cada punto representa a una muestra y el porcentaje de veces que se clasificó incorrectamente. Además, para los problemas de clasificación del cáncer de mama y de colon se incluyen histogramas con la información sobre falsos negativos y falsos positivos. 5.1.1 Flor de iris Se observa que la totalidad de las muestras pertenecientes a la clase Setosa se clasifican correctamente, por lo que se infiere que ésta tiene unas características muy distintas a las otras dos. En la tabla 5.1.1 se muestra el porcentaje de éxito y su desviación típica, para ser comparados posteriormente con los obtenidos mediante el algoritmo de bagging. % éxito Desviación típica 92,38 3,50 Tabla 5.1.1 - Resultados de aplicar árbol de decisión al problema Flor de Iris. 36 36 Resultados Figura 5.1.1 - Clasificación de Flor de Iris mediante árbol de decisión. Figura 5.1.2 - Flor de iris. Error por cada muestra usando árbol de decisión. 37 37 Estudio de Bootstrapping en Algoritmos de Clasificación 5.1.2 Cáncer de mama A pesar de obtenerse unos resultados aparentemente parecidos a los conseguidos para el problema de clasificación Flor de Iris, se puede observar que la aleatoriedad de qué muestra será la que se clasifique incorrectamente es mucho mayor (figura 5.1.6). En el problema anterior hay unas determinadas muestras que se clasifican incorrectamente de una manera consistente, mientras que en este problema la variabilidad de las muestras clasificadas de manera errónea es mucho mayor. % Desviación típica Éxito 89,16 2,66 Falso Positivo 6,53 2,76 Falso Negativo 9,92 4,10 Tabla 5.1.2 - Resultados de aplicar árbol de decisión al problema Cáncer de mama. Figura 5.1.3 - Clasificación de Cáncer de Mama mediante árbol de decisión. 38 38 Resultados Figura 5.1.4 - Falsos positivos de Cáncer de Mama mediante árbol de decisión. Figura 5.1.5 - Falsos negativos de Cáncer de Mama mediante árbol de decisión. 39 39 Estudio de Bootstrapping en Algoritmos de Clasificación Figura 5.1.6 - Cáncer de mama. Error por cada muestra usando árbol de decisión. 5.1.3 Cáncer de colon A la vista de los resultados se hace evidente que el algoritmo del árbol de decisión no es suficiente para este problema, se observa que hay muchas muestras que se clasifican mal en un porcentaje relativamente alto de veces. Se espera que al aplicar el método de bootstrapping se consiga reducir dichos errores. También se observa que el clasificador tiene problemas identificando las muestras de clase pólipo. Esto se debe a que hay menos muestras de esta clase y que la mayoría de ellas presentan características parecidas a la clase cáncer. La desviación típica del porcentaje de éxito es también muy elevada, lo que pone de manifiesto la inestabilidad y poca fiabilidad del árbol de decisión para este problema. % Desviación típica Éxito 51,28 6,68 Falso Positivo 26,41 9,99 Falso Negativo 23,48 8,84 Tabla 5.1.3 - Resultados de aplicar árbol de decisión al problema Cáncer de mama. 40 40 Resultados Figura 5.1.7 - Clasificación de Cáncer de Colon mediante árbol de decisión. Figura 5.1.8 - Falsos positivos de Cáncer de Colon mediante árbol de decisión. 41 41 Estudio de Bootstrapping en Algoritmos de Clasificación Figura 5.1.9 - Falsos negativos de Cáncer de Colon mediante árbol de decisión. Figura 5.1.10 - Cáncer de colon. Error por cada muestra usando árbol de decisión. 48 48 Resultados Figura 5.2.10 - Cáncer de Colon. Error por cada muestra aplicando bagging. 5.3 Estimación del ratio de acierto mediante bootstrapping A continuación se muestran los resultados obtenidos tras ejecutar el algoritmo de estimación del acierto por bootstrapping aplicado a los problemas de los apartados anteriores usando el árbol de decisión. Para los tres casos se han llevado a cabo 10.000 experimentos con 50 muestreos de bootstrapping cada uno. De este modo cada experimento cuenta con la aportación de 50 estimaciones del acierto, siendo la media de todas ellas la estimación final para cada experimento. En la primera gráfica se muestran los valores de la predicción del acierto y el acierto real para cada experimento junto con una recta a 45 grados para una fácil identificación de qué elemento tiene mayor valor: si el resultado final o la estimación. Los puntos por encima de esta recta corresponden a los experimentos en los que el acierto real mayor que la estimación, y los puntos por debajo de la recta corresponden al caso contrario. Interesa que los puntos estén por encima de esta recta, ya que esto permitiría acotar inferiormente el ratio de acierto mediante la estimación. La segunda recta 3 divide los experimentos en dos sub-conjuntos, el superior conteniendo el 90% de los experimentos y el inferior los restantes. La segunda gráfica es un histograma que muestra la distribución de la diferencia entre el acierto real y la estimación, en tanto por ciento, para los 10.000 experimentos. Esta gráfica es interesante para ver la desviación típica, la media, y calcular intervalos de confianza. El criterio elegido es que se consiga una seguridad de al menos un 90% para la estimación del ratio de acierto. Esto se explica en más detalle para cada uno de los casos más abajo. En esta segunda gráfica se muestran únicamente los 1.000 primeros experimentos para que se 3 Ambas rectas pasan por el origen. 49 49 Estudio de Bootstrapping en Algoritmos de Clasificación aprecie claramente la densidad de la nube de puntos, ya que para una mayor cantidad da la impresión de que hubiera la misma densidad de puntos entorno a la recta de 45 grados que a distancias más alejadas. 5.3.1 Flor de iris Se observa que la cantidad de predicciones pesimistas es de un 60%. O sea, en el 60% de las veces el resultado real es mejor que el predicho. Se desearía que este porcentaje fuera lo más alto posible para, así, poder acotar el ratio de acierto con una confianza grande. Este número no es lo suficientemente grande, por lo que en su lugar se buscará un intervalo de confianza del 90%, o lo que es lo mismo, el percentil 10. Esto es igual a cambiar la inclinación de la recta Y=X hasta conseguir la separación deseada tal como se muestra en la figura 5.3.1. Para el cálculo del percentil 10 se utiliza la distribución mostrada en la figura 4.3.2, resultando ser -5.34. Esto quiere decir que el 90% de los experimentos estarán por encima de la recta con una pendiente un 5,34% menor que la recta Y=X. Por ejemplo, si para un determinado experimento se obtiene una estimación del acierto del 95%, se puede garantizar con un 90% de seguridad que el 95−5,34=89,66% de las muestras que se pasen al clasificador serán clasificadas correctamente. Figura 5.3.1 - Estimación del ratio de acierto real vs estimación para problema Flor de Iris. 50 50 Resultados Figura 5.3.2 - Distribución de la desviación de la predicción del acierto para el problema Flor de Iris. 5.3.2 Cáncer de mama En este caso la cantidad de predicciones pesimistas es de un 68% (figura 5.3.3). O sea, en el 68% de las veces el resultado real es mejor que el predicho. Al igual que en el caso anterior, se desea que este porcentaje sea lo más alto posible para poder acotar el ratio de acierto con una confianza suficientemente grande. Como este número no es lo suficientemente grande se buscará un intervalo de confianza del 90%. El percentil 10 resulta ser -5.78. Se puede ver la distribución de la desviación de la estimación del acierto en la figura 5.3.4. 51 51 Estudio de Bootstrapping en Algoritmos de Clasificación Figura 5.3.3 - Estimación del ratio de acierto real vs estimación para problema Cáncer de Mama. Figura 5.24 – Distribución de la desviación de la predicción del acierto para el problema Cáncer de Mama. 52 52 Resultados 5.3.3 Cáncer de colon En este caso la estimación es más conservadora que el resultado final en más del 90% de los casos. De acuerdo al criterio adoptado no es necesario calcular el intervalo de confianza del 90%, pues la línea que divide los experimentos cae por encima de la recta X=Y, tal como se muestra en la figura 5.25. De acuerdo a los resultados obtenidos, la estimación del acierto será menor que resultado real con una seguridad del 96,88%, por lo que se puede acotar dicha predicción por abajo con una seguridad suficiente. Esto permite garantizar unos intervalos de confianza mayores que los obtenidos en los casos anteriores. No se debe confundir estos intervalos de confianza con los resultados finales obtenidos. En efecto, estos resultados son peores que los que se consiguen para los problemas Flor de Iris y Cáncer de Mama. Lo positivo de estos resultados es que no habrá penalización en la estimación del ratio de acierto para conseguir el intervalo de confianza deseado que debe ser mayor o igual al 90%. Figura 5.25 – Estimación del ratio de acierto real vs estimación para problema Cáncer de Colon. 53 53 Estudio de Bootstrapping en Algoritmos de Clasificación Figura 5.3.4 - Distribución de la desviación de la predicción del acierto para el problema Cáncer de Colon. 54 6 CONCLUSIONES Este capítulo recoge un análisis de conjunto de los resultados mostrados en el capítulo anterior. Se hace una comparación entre los resultados conseguidos sin aplicar la técnica de bagging, y los conseguidos al aplicarla. También se comparan los resultados obtenidos utilizando la técnica de estimación del ratio de acierto en los tres problemas. 6.1 Impacto del uso de bagging A continuación se hace una comparación de los resultados obtenidos únicamente con el árbol de decisión y aplicando la técnica de bagging. El bagging suele mejorar los resultados de cualquier clasificador o, en el peor de los casos, mantenerlos. Como se ha visto en el capítulo 5, se cumple esta predicción: los resultados han mejorado en mayor o menor medida cuando se ha utilizado la técnica de bagging para ayudar al clasificador. 6.1.1 Flor de iris Se consigue una ligera mejora tanto del ratio de éxito como de su desviación típica. Debido a que el problema se clasifica muy bien sin necesidad de bagging, el margen de mejora es menor. Sin bagging Con bagging % éxito 92,38 93,79 Desviación típica 3,50 3,23 Tabla 6.1.1 - Comparación de resultados para el problema Flor de Iris. 6.1.2 Cáncer de mama Al igual que ocurre con en el caso anterior, los resultados mejoran ligeramente. Se observa que a pesar de clasificarse ligeramente peor que el problema Flor de Iris, se tiene una desviación típica menor para ambos casos. Esto puede deberse a que hay dos clases para clasificar en lugar de tres. Sin bagging Con bagging % Desviación típica % Desviación típica Éxito 89,16 2,66 90,70 2,05 Falso Positivo 6,53 2,76 7,73 2,86 Falso Negativo 9,92 4,10 4,00 2,62 Tabla 6.1.2 - Comparación de resultados para el problema Cáncer de Mama. 6.1.3 Cáncer de colon Al obtenerse unos malos resultados al aplicar únicamente el árbol de decisión, era de esperar que éstos se mejoraran sustancialmente al utilizar la técnica de bagging. Efectivamente, el ratio de 55 55 Estudio de Bootstrapping en Algoritmos de Clasificación acierto aumenta un 14% y la desviación típica baja más de un punto. Sin bagging Con bagging % Desviación típica % Desviación típica Éxito 51,28 6,68 65,22 5,35 Falso Positivo 26,41 9,99 31,02 9,46 Falso Negativo 23,48 8,84 6,19 4,81 Tabla 6.1.3 - Comparación de resultados para el problema Cáncer de Colon. Tal como se esperaba, la desviación típica disminuye al aplicar el método de bagging. Al igual que pasa con el ratio de acierto, ésta se consigue reducir en mayor medida en problemas con un margen de mejora mayor. 6.1.4 Conclusión Se observa que los problemas que tienen un ratio de acierto entorno al 90% a penas mejoran sus resultados al ser clasificados mediante bagging. Sin embargo, para el problema Cáncer de Colon, que ofrece unos resultados muy pobres, se consigue una mejora sustancial de los mismos. En vista de estos resultados se deduce que el método de bagging es tanto mejor como margen de mejora hay. Sin embargo, al contarse únicamente con tres problemas de clasificación no se tiene una certeza suficiente como para generalizar esta conclusión a cualquier problema de clasificación. 6.2 Análisis de la estimación de ratio de aciertos mediante bootstrapping Tanto si se consigue acotar directamente el ratio de acierto a partir de los resultados de la estimación, como si se necesita calcular un intervalo de confianza que obligue a reducir el valor de ella, se consigue siempre acotar la estimación del acierto con una seguridad 90%. Este grado de seguridad podría haberse elegido mayor, dando lugar a un intervalo de confianza mayor y disminuyendo la pendiente de la recta. Esto hará que la penalización sobre la estimación crezca, por lo el valor de la estimación final disminuirá a su vez. Una nube de puntos concentrada permitirá elegir intervalo de confianza mayores sin necesidad de aumentar la penalización demasiado. Es en problemas con una varianza grande donde habrá una penalización mayor para aumentar el intervalo de confianza. Como se ha explicado, el método de bootstrapping disminuye la varianza, por lo que esta penalización debe estar de por sí disminuida. 56 7 CÓDIGO A continuación se muestra el código de las funciones y scripts descritos en el capítulo 4. 7.1 Script core.m % CORE PROGRAM TO TEST RESULTS clear all clc % TO BE MODIFIED Num_Iter = 1; % Number of experiments to be run on every (gam,sig2) combination Nb = 50; % Number of boorstrap samplings. problem = 'colon'; % Type of problem: {iris, breast, colon} method = 'bagging_estimation'; % Options are: {normal, bagging, bagging_estimation} % CATEGORIES if(strcmp(problem,'breast')) Malign = 1; Benign = 7; Class_A = [Malign]; % Class A will be assigned Y=1 Class_B = [Benign]; % Class B will be assigned Y=-1 Class_C = []; % Class C will be assigned Y=0; elseif(strcmp(problem,'iris')) Setosa = 1; Versicolor= 2; Virginica = 3; Class_A = [Versicolor]; % Class A will be assigned Y=1 Class_B = [Virginica]; % Class B will be assigned Y=-1 Class_C = [Setosa]; % Class C will be assigned Y=0 elseif(strcmp(problem,'colon')) Cancer = 1; Polyps = 2; Healthy= 7; Class_A = [Cancer]; % Class A will be assigned Y=1 Class_B = [Healthy]; % Class B will be assigned Y=-1 Class_C = [Polyps]; % Class C will be assigned Y=0 end All_Data = LoadAllData(problem); % Load original data to messure its size, before it is shrinked by LoadData function Error_Tracker = zeros(size(All_Data,1),1); % Keeps track of how many time a sample is redicted wrong Training_Frequency = zeros(size(All_Data,1),1); % Stores how many times a sample falls into the validation set 57 57 Estudio de Bootstrapping en Algoritmos de Clasificación All_Data = LoadAllData_KeepingTrack(problem); % Loads dataset S = zeros(Num_Iter,1); C = zeros(Num_Iter,3); for k=1:Num_Iter; disp(k); % Masks to modify ErrorTracker and Frequency arrays mask_error=zeros(length(Error_Tracker),1); mask_frequency =zeros(length(Training_Frequency),1); % Splitting data set into training and validation keeping track of the original position of each sample SplitData; Yt = Y_Training(:,2); Yv = Y_Validation(:,2); Yv_tracking = Y_Validation(:,1); % APPLYING METHOD if strcmp(method,'normal') T = classregtree(X_Training,Yt); Y_predict = eval(T,X_Validation); elseif strcmp(method,'bagging') Y_predict = BaggingMethod(X_Training,Yt,X_Validation,Nb); elseif strcmp(method,'bagging_estimation') [Y_predict, s] = BaggingEstimationMethod(X_Training,Y_Training,X_Validation,Nb); S(k) = s; end I_correct=(Y_predict==Yv); % Indices of correct predictions I_incorrect=(I_correct==0); Nval=length(Yv); % Size of the validation set Nv_A=sum(Yv==1); % Number of Class_A samples Nv_B=sum(Yv==-1); % Number of Class_B samples FalsePositive=sum((Yv==-1)&(Y_predict>=0)); % Number of false positives FalseNegative=sum((Yv==1)&(Y_predict<0)); % Number of false negatives EP_Correct_Val=100*(sum(I_correct)/Nval); % Estimated Probability of correct classification in Validation Set. EP_FP_Val=100*FalsePositive/Nv_B; % Estimated Probability of False Positive in validation set. EP_FN_Val=100*FalseNegative/Nv_A ; % Estimated Probability of False Negative in validation set. % Storing results in A C(k,1) = EP_Correct_Val; C(k,2) = EP_FP_Val; 64 64 Código I3 = ~I12; Ypred(I1)=1; Ypred(I2)=-1; Ypred(I3)=0; end 7.6 Función BaggingEstimationMethod function [ Ypred, S ]= BaggingEstimationMethod( X_Training,Y_Training,X_Validation,B ) % Will provide with an estimation of the accuracy of the prediction based on % bootstrapping method. success_r = zeros(B,1); Ypred = zeros(size(X_Validation,1),1); for i=1:B % Sampling wo/ replacement [X,Y] = BootStrapping_sample(X_Training, Y_Training); % Remaining samples that didn't fall into bootstrapping sample set [Xr,Yr] = BootStrapping_remaining(X_Training, Y_Training, Y); T = classregtree(X,Y(:,2)); % Training the tree Ypred = Ypred + eval(T,X_Validation); % Prediction for bootstrapped samples Ypred_r = eval(T,Xr); % Prediction for samples that were not bootstrapped Ir_success = (Ypred_r==Yr(:,2)); % Index of samples predicted successfully % Index successfully predicted non-bootstrapped samples success_r(i) = 100*(sum(Ir_success)/length(Ypred_r)); end % Adding up predictions, computing mean, adapting outcome to fixed values {-1 0 1} S = mean(success_r); Ypred = Ypred/B; I1 = Ypred > 1/3; I2 = Ypred <-1/3; I12 = I1+I2; I3 = ~I12; Ypred(I1) = 1; Ypred(I2) =-1; Ypred(I3) = 0; end 65 65 Estudio de Bootstrapping en Algoritmos de Clasificación 7.7 Función BootStrapping_sample function [ Xsample , Ysample ] = BootStrapping_sample( X, Y ) % Ramdomly samples training data wo/ replacement to apply bootstrapping. N = size(X,1); i = 1:N; I=datasample(i,N); Xsample = X(I,:); Ysample = Y(I,:); end 7.8 Función BootStrapping_remaining function [Xr,Yr] = BootStrapping_remaining(X_Training,Y_Training,Y) % Will compute the samples that haven't been selected in the bootstrapping sampling all = Y_Training(:,1); selected = Y(:,1); Xr=[]; Yr=[]; for i=1:length(all) if( sum(find(all(i)==selected)) == 0) Yr = [Yr ; Y_Training(i,:)]; Xr = [Xr ; X_Training(i,:)]; end end end 66 BIBLIOGRAFÍA  Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining. 2015.  Oded Maimon, Lior Rokach. Data Mining and Knowledge Discovery. 2010.  Leo Breiman. Bagging Predictors. 1994.  Alex Smola,S.V.N. Vishwanathan. Introduction to machine learning. 2008.  Ian H. Witten, Eibe Frank, Mark A. Hall. Data Mining: Practical Machine Learning Tools and Techniques, Third Edition. 2011.  Decision Tree Learning (15 Mayo 2015). Wikipedia, la enciclopedia libre. Consultado 19 Mayo 2015. http://www.riate.org/version/v1/recursos/cursolicenciasnavegable/cmo_citar_la_wikipedia.html  Bootstrap aggregating (1 Junio 2015). Wikipedia, la enciclopedia libre. Consultado 3 Junio 2015. https://en.wikipedia.org/wiki/Bootstrap_aggregating  Statistical Classification (13 Junio). Wikipedia, la enciclopedia libre. Consultado 16 Junio 2015. https://en.wikipedia.org/wiki/Statistical_classification  Set de datos de Flor de Iris: UCI Machine Learning Repository. Recuperado 19 Abril 2015. https://archive.ics.uci.edu/ml/datasets/Iris  Set de datos Cáncer de Mama: UCI Machine Learning Repositoyr. Recuperado 21 Abril 2015. https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Original)