Árboles de regresión y clasificación

Traballo Fin de Grao Árboles de regresión y clasificación José Ángel Vicente Porres Julio, 2022 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Árboles de regresión y clasificación José Ángel Vicente Porres Julio, 2022 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Coñecemento: Estatística e Investigación Operativa Título: Árbores de regresión e clasificación Breve descrición do contido As árbores de decisión son unha metodoloxía de aprendizaxe estatística supervisada que se emprega tanto en problemas de clasificación (cando a variable resposta é cualitativa) coma en problemas de regresión (cando a variable resposta é cuantitativa). As árbores constrúense de forma recursiva partindo o espazo das covariables e axustando un modelo de predición en cada paso. Entre os algoritmos máis destacados para a construción de árbores de decisión está o algoritmo CART (Classification and Regression Trees) O obxectivo deste traballo é que o alumno ou a alumna faga unha revisión destes métodos desde o pun- to de vista teórico e estude a súa implementación e aplicación a datos reais Recomendacións Outras observacións iii Índice Resumen viii Introducción xi 1. Reglas de clasificación y predicción 1 1.1. Reglasdeclasificación ................................ 1 1.2. Ratios de clasificación incorrecta . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Estimador de la probabilidad de clases . . . . . . . . . . . . . . . . . . . . . . . 3 1.4. Reglasdepredicción ................................. 4 2. Modelos en forma de árbol 7 2.1. ÁrbolesdeClasificación ............................... 9 2.1.1. Árboles de probabilidad de clases . . . . . . . . . . . . . . . . . . . . . . 11 2.2. ÁrbolesdePredicción................................. 12 2.3. Ejemplos ........................................ 12 3. Construcción de un árbol 15 3.1. FuncióndeImpureza ................................. 15 3.2. CriteriodeGini .................................... 18 3.3. CriteriodeTwoing .................................. 19 3.4. Criterio en un árbol de predicción . . . . . . . . . . . . . . . . . . . . . . . . . . 20 v vi ÍNDICE 3.5. Conjuntos de preguntas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.6. Conjunto estándar de preguntas . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4. Podado y tamaño adecuado 25 4.1. Reglasdefrenado.................................... 26 4.2. Podado ......................................... 27 4.3. Podado coste-complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4. Estimación del mejor árbol podado . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.5. Ejemplo podado coste complejidad . . . . . . . . . . . . . . . . . . . . . . . . . 29 5. Métodos alternativos 33 5.1. BoostrapyBagging .................................. 33 5.1.1. Aplicación a árboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.1.2. Por qué Bagging funciona . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.1.3. Resultados experimentales . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2. Boosting ........................................ 36 5.2.1. AdaBoost.................................... 36 5.2.2. Comparación con Bagging . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3. Ejemplos......................................... 38 5.3.1. Árbol de clasificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3.2. BaggingyBoosting .............................. 39 5.3.3. RandomForest ................................ 40 Bibliografía 43 xiv INTRODUCCIÓN Capítulo 1 Reglas de clasificación y predicción 1.1. Reglas de clasificación Supongamos que nos encontramos en un hospital y nos encargan la creación de un modelo capaz de identificar qué pacientes tienen un mayor riesgo de padecer una enfermedad coronaria. Se tiene que los procedimientos que permiten detectar este tipo de enfermedades de manera fiable suelen ser bastante complejos, necesitando en muchos casos la realización de un TAC de gran parte del torso. La obtención y procesado de este tipo de imágenes suele ser lenta, complicada y costosa, por lo que determinar de manera eficiente que pacientes necesitan este tipo de pruebas con mayor urgencia, puede ser un paso fundamental en su tratamiento. En este tipo de procedimientos, se etiqueta cada uno de los pacientes. Para este ejemplo, diremos que con un 0, si se cree que está fuera de peligro, o 1si es un caso de riesgo. Este será un problema de clasificación binario, ya que solo hay dos clases entre las que discernir. Si se quiere un modelo más completo, se puede intentar realizar una clasificación más precisa, no solo estudiando si un paciente está sano o no, sino estimando el grado de peligro en el que se encuentra. Formalmente, se llamará conjunto de clases C={1,2,3, . . . , J}a las distintas categorías que se consideran en el modelo. Es necesario disponer de información sobre la que realizar dicha clasificación. Por ejemplo, es sabido que la probabilidad de padecer una enfermedad coronaria aumenta enormemente en personas mayores, por lo que conocer la edad del paciente puede ser crucial en la realización un estudio satisfactorio. Otros datos que se podrían utilizar serían antecedentes familiares, peso, colesterol en sangre, síntomas, etc. Toda esta información sobre un paciente se guarda en un vector de medidas x. Este se estudiará como una variable aleatoria que toma valores siguiendo una distribución del espacio muestral Ω. 1 2 1. Reglas de clasificación y predicción Será necesario tener acceso a una base de datos para poder realizar el modelo. Esta podría ser el historial del hospital, ya que contiene información sobre los antiguos pacientes. En este caso, se debe saber el nivel de riesgo real, y los datos suficientes como para construir su vector de medidas. Todo esto se recoge en el conjunto de aprendizaje L= (xi, Yi)i=1...N , compuesto por Nparejas xi∈Ω,Yi∈ C. En el fondo, el proceso de construcción de un modelo se basa en un estudio sobre L, por lo que es necesario asegurarse de que representa una buena muestra del medio. Definición 1.1. Una regla de clasificación o clasificador d, es una aplicación que a cada punto del espacio muestral Ω, le asigna una de las clases de C. Regresando al ejemplo del hospital, a partir del conjunto de aprendizaje L, se construirá un clasificador d. Este usará el vector de medidas x de un paciente para predecir si está sano, o que enfermedad puede tener. Esto permitiría detectar de manera sencilla aquellos individuos con un mayor riesgo de sufrir la enfermedad estudiada, y por tanto, facilitar su diagnosis. 1.2. Ratios de clasificación incorrecta Una vez definido lo que es un clasificador d, surge un nuevo problema que será necesario abordar, ya que su resolución será fundamental para la construcción de modelos precisos. ¿Cómo se sabe si des eficiente? De manera intuitiva, un clasificador es mejor qué otro si es capaz de cometer menos errores al asignar etiquetas a nuevos sujetos. Con el fin de dar un valor numérico a la calidad de un modelo de este tipo, se definen los ratios de clasificación incorrecta. En una primera aproximación a este problema, se puede definir el riesgo como la probabilidad de que el clasificador cometa un error, R∗(d) = P[d(x)=Y]. Donde x ∈Ωrepresenta el vector de medidas de un sujeto, e Yla clase a la que dicho sujeto pertenece en realidad. Hay que tener en cuenta que la construcción de un clasificador dse lleva a cabo a partir de la experiencia pasada, en forma de conjunto de aprendizaje L. Debido a esta razón, en la gran mayoría de casos será imposible calcular este riesgo, ya que no se dispone de la distribución real del medio. Se proponen por tanto estimadores de esta probabilidad, con el fin de encontrar una medida de la calidad de un clasificador a partir de la información contenida en L Definición 1.2. Sea dun clasificador, se define el ratio de clasificación incorrecta, R(d), como la proporción de observaciones del conjunto de aprendizaje Lque dno es capaz de clasificar correctamente. Así, a partir del conjunto de aprendizaje L= (xi, Yi)i=1...N , y considerando Ila función indicador tal que I(a) = 1 si la condición a se cumple, y 0en otro caso. Se calculará por tanto 1.3. Estimador de la probabilidad de clases 3 el ratio de clasificación incorrecta de un modelo como R(d) = N X i=1 I(d(xi)=Yi)/N Para la construcción de clasificadores, el último ratio es realmente bueno, ya que permite calcular rápidamente la calidad del modelo a medida que este se va construyendo. Sin embargo, se está usando la misma información para construir y para testear el clasificador. Esto suele llevar a modelos demasiado complejos, que pierden información sobre las relaciones que existen entre x eYdebido a problemas de sobreajuste. Con el fin de evitar estos problemas, se suelen aplicar diversos métodos capaces de obtener estimaciones más precisas del error cometido. Sin entrar en detalles, en este trabajo se empleará validación cruzada, que trabaja sobre diversas particiones del conjunto de aprendizaje para comprobar cuánta información se pierde por sobreajuste. Con el fin de obtener una estimación realista del error cometido, se suele aislar una parte del conjunto de aprendizaje. Construyendo aleatoriamente la partición de Lformada por Le, conjunto de entrenamiento, y Lv, de validación. De la misma forma, se definirán los ratios de clasificación incorrecta ReyRv, definidos de forma similar a R, pero restringido a los conjuntos de entrenamiento y de validación respectivamente. En los apartados del trabajo que se centren en la construcción del modelo, y por ende, validar pase a un segundo plano, se usará únicamente la notación LyRpara el desarrollo de la teoría. 1.3. Estimador de la probabilidad de clases Hasta ahora, en el problema del hospital, a cada paciente se le clasificaba como sano o enfermo, como mucho dándole un grado de peligrosidad. Una aproximación más realista, sería construir un modelo que como respuesta diese una probabilidad de que el paciente padezca dicha enfermedad, o no. De esta forma, el médico puede cotejar los resultados y tener más información a la hora de plantear un tratamiento. Para este tipo de modelos, al vector de medidas x se le deberá asignar un valor para cada una de las clases del estudio C={1,2,3, . . . , J}. De tal forma que la respuesta se de como un vector  d( x)=(d(1/x), d(2/x), . . . , d(J/x)), donde d(j/x)es una estimación p(j/x), la probabilidad de que x pertenezca a la clase j. Por esta razón se debe cumplir que d(j/x)∈[0,1] yPj∈C d(j/x)=1 Definición 1.3. Un estimador de probabilidad de clases es una aplicación d, que a cada clase del conjunto C, y a cada vector x del espacio muestral Ω, les asigna un valor real d(j/x)∈[0,1], 4 1. Reglas de clasificación y predicción tal que Pj∈C d(j/x) = 1 Se define la precisión del modelo como R∗(d) = E[Pj(p(j/x)−d(j/x))2/x ∈Ω], la esperanza entre las probabilidad real y las estimadas al cuadrado. Al igual que en la distribución de clases, como se desconoce la distribución real del medio, no es posible obtener un cálculo de dicha precisión. A partir del conjunto de aprendizaje L= (xi, Yi)i=1, se propone como estimador de la precisión R(d) = N X i=1 X j∈C (I(i=j)−d(j/xi))2.(1.1) Esta estimación se obtiene de suponer que la probabilidad p(Yi/xi)es igual a 1. De la misma forma p(j/xi)=0para el resto de clases posibles. 1.4. Reglas de predicción En el ejemplo del hospital, a cada paciente se le clasifica en uno de los niveles de C, estos son los clasificadores. También se puede dar el caso en el que en vez de a una clase, el modelo deba realizar una estimación sobre una magnitud continua. A este tipo de modelos se les llama predictores, ya que se encargan de predecir el valor de una variable. Definición 1.4. Una regla de predicción o predictor d, es una aplicación que a cada punto del espacio muestral Ωle asigna un valor de R. A lo largo de este trabajo se denotará con dtanto a los clasificadores como a los predictores. El objetivo final es construir una metodología general para ambos tipos de modelos, por lo que diferenciarlos ahora podría llevar a confusiones más adelante. Al igual que en el caso anterior, se dispone de un conjunto de aprendizaje L, del que se espera obtener la información suficiente como para realizar predicciones precisas. Sin embargo, en este tipo de modelos no tiene sentido hablar de reglas de clasificación incorrecta, ya que será raro el caso en el que un resultado sea exacto. Por esta razón se suele preferir el uso de un estimador de la esperanza del error cuadrático R∗(d) = E[(d(x)−Y)2]con el fin de medir la calidad del modelo. Definición 1.5. Sea dun predictor, se define el error de mínimos cuadrados R(d)como la media del error al cuadrado cometido de las diversas observaciones sobre el conjunto de aprendizaje L. 1.4. Reglas de predicción 5 R(d) = N X i=1 (d(xi)−Yi)2/N En este tipo de modelos también se puede separar el conjunto de aprendizaje entre entrenamiento y validación con el fin de obtener estimaciones del error más precisas. Se tiene que el uso de Rpara definir tanto el ratio de clasificación incorrecta como el error por mínimos cuadrados. Este abuso de notación permite la formulación de metodología para la construcción de árboles de decisión independientemente de su tipo. 6 1. Reglas de clasificación y predicción Capítulo 2 Modelos en forma de árbol La idea que está detrás de usar árboles binarios para la construcción de modelos está en la recursividad que los caracteriza. Cada uno de los nodos del árbol puede estar asociado a otros dos, sus hijos, que a su vez pueden estar unidos a dos más. En el caso concreto de árboles de decisión, se asocia cada uno de los nodos a una región del espacio muestral Ω. De tal forma que la raíz representa el total, y cada separación es una división del espacio en dos. Este proceso de separar y repartir se puede continuar de manera repetida, aumentando en cada paso el tamaño del árbol. Más adelante se explicará con detalle la forma en la que se decide la división óptima del espacio. Como introducción, se busca aquella separación que minimice Ra partir de la información del conjunto de aprendizaje. La idea es conseguir agrupar en el mismo nodo aquellas zonas del espacio con cualidades similares, para clasificarlas de la misma forma. A B D E F G C (a) Ejemplo simple de árbol binario (b) Relación con Ω Figura 2.1: Ejemplo de separación del espacio de medidas a partir de un árbol En la Figura 2.1 se puede observar un pequeño ejemplo de cómo se emplea un árbol para 7 8 2. Modelos en forma de árbol dividir el espacio muestral en distintas partes. En este caso, Ωestá representado por el rectángulo de la derecha, por notación se considerará que es un espacio bidimensional continuo y x = (x1, x2). De esta forma, se tiene que A=Ω, el cual se divide entre ByC,Bse separa entre EyD, y por último E, entre FyG. En este caso, todas las separaciones se centran en solo una de las variables, lo que permite que su descripción sea bastante sencilla. Por ejemplo, B={x ∈A/x1< c}. Se puede utilizar esta misma estructura para describir cada uno de los subespacios en este ejemplo. Otras posibles formas de dividir el espacio sería mediante el uso de hiperplanos, {x ∈Ω/atx < c}, o bolas {x ∈Ω/∥a −x∥< c}. A la hora de implementar el modelo, estas dos últimas descripciones son computacionalmente más costosas, por lo que solo se utilizan en el caso de que haya un conocimiento a priori que favorezca su aplicación. Por lo general, las separaciones se suelen describir en forma de preguntas s. En el caso del ejemplo anterior, se definiría sA(x) = ¿x < c?, con lo que quedaría B={x ∈A/sA(x) = sí}, y C={x ∈A/sA(x) = no}. Esta forma de expresar las divisiones del espacio muestral como un objeto en si mismo, es útil a la hora de construir modelos. Por como se han construido estos árboles, el conjunto de los subespacios asociados a los nodos terminales son un recubrimiento disjunto del espacio muestral. De esta forma, en el ejemplo anterior, Ωestá formado por C,D,GyF. Para completar el modelo d, a cada uno de los nodos terminales se le asigna un valor, en el caso de ser un clasificador, una de las clases de C, y para un predictor, un número real. Una vez hecho todo esto, el funcionamiento del modelo es bastante sencillo. Los nuevos elementos a estudiar se disponen en la raíz. A estos se les realiza la pregunta sdel nodo, y según como respondan, bajan a uno de los hijos. Este proceso se repite a lo largo del árbol, hasta que llega a uno de los nodos terminales. En este punto, se concluye que x se encuentra en dicho subespacio terminal, por lo que al sujeto se le asigna el mismo valor que al nodo. Siguiendo con el ejemplo anterior, en la Figura 2.2 se construye un modelo de clasificación y uno de predicción a partir de la división del espacio ya vista. A la izquierda, se considera un clasificador de dos clases C={1,2}. Los subespacios G,Cse asignan a la clase 1, y los otros dos, F,D, a la clase 2. De la misma forma, se podría definir un recubrimiento de Ωa partir de las clases, A1=G∪CyA2=F∪D. Por otro lado, a la derecha se muestra un predictor, en el que a cada uno de los subespacios terminales se les asigna un valor real distinto. En estos últimos ejemplos se puede ver que la principal diferencia entre un árbol de clasificación y uno de predicción reside en el último paso, la asignación de un valor a un nodo terminal. Antes de empezar a hablar de la manera en la que se divide el espacio a partir este tipo de estruc- 2.1. Árboles de Clasificación 9 (a) Clasificador (b) Predictor Figura 2.2: Ejemplo de construcción de modelos a partir de un árbol turas, es conveniente aclarar las diferencias técnicas entre clasificadores y predictores. De esta forma se espera poder construir toda clase de modelos dejando de lado a que tipo pertenecen. 2.1. Árboles de Clasificación En la construcción de un modelo se llega hasta At, subespacio de Ωasociado a cierto nodo terminal t, de tal forma que todo vector de medidas x ∈At, se clasifica como j∈ C ={1,2,3. . . J}. Se busca la forma óptima de realizar dicha asignación a partir de la información de Lt, conjunto de aprendizaje restringido a esta región. Sea un nuevo elemento dispuesto para ser clasificado por d, se define π(j)la probabilidad de que pertenezca a la clase jsin ningún conocimiento a mayores del sujeto. De esta forma se define {π(j)}j∈C el conjunto de probabilidades a priori. Estas representan una distribución ideal del conjunto muestral, por lo que no se suele tener información precisa sobre ellas. A la hora de construir modelos, es trabajo del analista estimar dichas probabilidades por {ˆπ(j)}j∈C. Generalmente se suele recurrir al conjunto de aprendizaje para asignarle un valor a dicha magnitud, tomando ˆπ(j)como la proporción de elementos de Lque pertenecen a la clase j. La razón por la que se introduce estas probabilidades a priori π, es para paliar los casos en los que Lno sea representativo del medio que se va a estudiar. Por ejemplo, en el hospital, tiene sentido realizar el entrenamiento con muchos informes de pacientes con síntomas raros. De esta forma, el modelo se blinda ante estos síntomas a costa de que los comunes tengan una menor representación. Para trabajar con el conjunto de aprendizaje L, se tendrá que está compuesto por Nelemen- 16 3. Construcción de un árbol distintas definiciones en función del tipo de árbol que se intenta construir, llamándose ratio de clasificación incorrecta en el caso de ser un clasificador, o error de mínimos cuadrados en un predictor, véanse Definiciones 1.2, 1.5. A pesar de ser dos definiciones distintas, ambas están construidas de tal forma que la siguiente igualdad se cumple. Sea suna separación del nodo ten tiytd, la disminución del riesgo del árbol viene dado por ∆R(t, s) = ˆp(t)·[r(t)−ˆpi·r(ti)−ˆpd·r(td)], donde ˆp(t)estima la probabilidad de que un elemento de Lcaiga en t. Por otro lado, ˆpi= ˆp(ti)/ˆp(t), y ˆpd= ˆp(td)/ˆp(t). En el caso de que las ˆπ(j)no sean homogéneas, este cálculo se puede complicar, pero generalmente serán el porcentaje de los elementos de Ltque bajan por cada rama. Por construcción, se cumple que ˆpi+ ˆpd= 1. Sin embargo, en ciertos casos, la optimización de este ratio puede no ser un buen criterio para construir un árbol. En la Figura 3.1 se presenta un ejemplo tomado de [5], en el que se tienen dos posibles separaciones de un nodo con elementos en las clases 1,2. Figura 3.1: Dos separaciones de un nodo de 800 elementos. Al calcular el ratio de clasificación incorrecta de ambos árboles, se obtiene un valor R(T) = 0,25. Según este criterio, ambas separaciones son igual de buenas. Sin embargo, uno de los nodos del segundo árbol está compuesto únicamente por elementos de la primera clase y no será necesario dividirlo en partes más pequeñas. Teniendo esto en cuenta, la segunda partición es más beneficiosa a la hora de construir un árbol de clasificación. Este tipo de sucesos se hacen más comunes a medida que se construyen modelos más complejos. Por esta razón, se propone como criterio de separación la reducción de una función i(t). Esta debe ser capaz de medir la “impureza” de un árbol, tomando valores elevados cuanto más homogénea sea la distribución de clases. Definición 3.1. Se dice que una función ϕsimétrica no negativa es de impureza, si cumple las condiciones: 3.1. Función de Impureza 17 Definida sobre vectores J-dimensionales p = (p1, p2. . . pJ)tal que pj∈[0,1] yPjpj= 1. El punto homogéneo (1 J,1 J. . . 1 J)representa el único punto máximo de ϕ. ϕ(p1, p2. . . pJ)=0si pj= 1 para algún j. La primera de las condiciones está impuesta para que la función de impureza este definida sobre todo vector de probabilidades p(t) = (ˆp(1/t),ˆp(2/t). . . ˆp(J/t)), siendo ˆp(j/t)una estimación de la probabilidad de que un elemento que llegue al nodo t, pertenezca a la clase j Definición 3.2. Sea ϕuna función de impureza, se define la impureza de un nodo tal valor obtenido de aplicar ϕal vector de probabilidades p(t) i(t) = ϕ(ˆp(1/t),ˆp(2/t). . . ˆp(J/t)). Se observa que si todos los elementos de Ltpertenecen a una única clase j, la impureza será i(t)=0. Esto se debe a que bajo estas condiciones ˆp(j/t)=1. Al igual que con la función de riesgo, se puede definir la impureza de un árbol I(T)como la suma de las impureza de cada uno de sus nodos terminales. I(T) = X t∈ˆ T I(t) = X t∈ˆ T ˆp(t)·i(t) De la misma forma, sea suna separación del nodo t, se tiene que la disminución de la impureza debido a sviene dada por: ∆I(s, t) = ˆp(t)·∆i(s, t) = ˆp(t)·[i(t)−ˆpi·i(ti)−ˆpd·i(td)]. Más adelante, en 4.1 se demostrará que ∆R(s, t)≥0para todo tys. Esta es una propiedad importante, ya que asegura la existencia de una separación que mejore la calidad del árbol. Por esta razón, es interesante comprobar si también se cumple ∆I(s, t)≥0para toda pareja (s, t). Proposición 3.3. Sea i(t) = ϕ(ˆp(1/t),ˆp(2/t). . . ˆp(J/t)) la impureza de t, y suna separación del nodo entre los hijos tiytd. Si ϕes convexa sobre su dominio, se tendrá: ∆i(s, t) = i(t)−ˆpi·i(ti)−ˆpd·i(td)≥0(3.1) Alcanzando la igualdad en el caso de que ˆp(j/t) = ˆp(j/ti) = ˆp(j/td)para todas las clases j. Demostración. Por la definición usual de función convexa, se cumple que pi·i(ti) + ˆpd·i(td) = ˆpi·ϕ(ˆp(1/ti), . . . ˆp(J/ti)) + ˆpd·ϕ(ˆp(1/td), . . . ˆp(J/td)) ≤ ≤ϕ(ˆpi·ˆp(1/ti) + ˆpd·ˆp(1/td), . . . ˆpi·ˆp(J/ti) + ˆpd·ˆp(J/td)). 18 3. Construcción de un árbol En este caso, como ˆpi+ ˆpd= 1, se alcanzará la igualdad si la estimación del vector de probabilidad es igual para los tres nodos, p(t) = p(ti) = p(td). Se recuerda que ˆp(j, ti) = ˆp(ti)·ˆp(j/ti), es la estimación de la probabilidad combinada de que un elemento llegue a tiy pertenezca a la clase j. Esto unido a que ˆpi= ˆp(ti)/ˆp(t)por construcción, se llega a que: ˆpi·ˆp(j/ti) + ˆpd·ˆp(j/td) = ˆp(ti)·ˆp(j/ti) + ˆp(td)·ˆp(j/td) ˆp(t)=ˆp(j, ti) + ˆp(j, td) ˆp(t)= ˆp(j/t) Uniendo ambos resultados, se llega finalmente a la desigualdad ˆpi·i(ti) + ˆpd·i(td)≤ϕ(ˆp(1/t), . . . ˆp(J/t)) = i(t), con lo que se concluye la demostración. 3.2. Criterio de Gini Una vez definido el criterio para separar los nodos de un árbol a partir de la impureza, surge el problema de encontrar una función ϕcapaz de medirla. Por la Proposición 3.3, es conveniente que sea convexa. Tampoco puede beneficiar demasiado a los nodos “puros”, pues se podrían acabar perdiendo los beneficios que tiene estructurar el modelo en forma de árbol. Al final, es trabajo del analista definir dicha función de tal forma que se ajuste bien al problema. Como primera aproximación, la función de impureza más simple viene dada por: ϕ(p) = 1 −m´ax j=1...J pj= m´ın j=1...J pj. Esta aproximación al problema no es muy popular ya que no beneficia lo suficiente a los nodos “puros”. En los orígenes del método, probando cómo distintas funciones se comportaban ante los experimento, se hizo especialmente popular usar como medida de la impureza: ϕ(p) = − J X j=1 pj·ln pj. Similar a este, se empezó a utilizar el método de Gini. Este criterio se deduce de una aproximación de la probabilidad de clasificar incorrectamente un elemento que llegue al nodo t. Se estima que ˆp(j/t)es la probabilidad de que un elemento cualquiera de tsea clasificado por j. Estimando por ˆp(i/t)la probabilidad de que en realidad pertenezca a la clase iy sumando sobre todas las combinaciones i=j, se deduce el índice de diversidad de Gini: ϕ(p) = X i=j pi·pj= 1 − J X j=1 p2 j(3.2) 3.3. Criterio de Twoing 19 Se tiene que el índice de diversidad de Gini está compuesto por un polinomio cuadrático no negativo. Por esta razón cumple la condición de convexidad, y por la Proposición 3.3, ∆i(s, t)≥0 para toda separación s. Se puede observar que en la construcción del criterio de Gini, se estima la probabilidad de clasificar incorrectamente un elemento que llegue a t. Sin embargo, todos los errores se consideran iguales, C(i/j) = δij. Con el fin de tener en cuenta esta construcción, se puede ampliar la definición del índice de diversidad de Gini a : i(t) = X i=j C(i/j)ˆp(i/t)ˆp(j/t). La aplicación de esta fórmula puede llegar a resultados satisfactorios en la construcción de árboles. Sin embargo, bajo esta definición general es imposible asegurar la convexidad del problema. Determinar si la aplicación de este método es beneficioso o no, recae una vez más en el analista. En el caso de los estimadores de probabilidad de clasificación, se observa que el índice de diversidad de Gini 3.2, es similar a la estimación del error en cada nodo 2.1. Por esta razón, el uso del criterio de Gini es ideal para la construcción de este tipo de árboles. 3.3. Criterio de Twoing Se plantea una segunda aproximación al problema de dividir el espacio con la ayuda de un conjunto de entrenamiento. En este caso, la clasificación se reduce a únicamente dos categorías, C1={j1, j2...,jn≤J}, subconjunto de C={1,2,3, . . . , J}, y su complementario C2=C − C1. De esta forma, dada una función de impureza ϕ(p1, p2), y una separación sdel nodo t, se define de manera usual ∆i(s, t, C1), disminución de la impureza restringido al conjunto C1. El criterio de Twoing propone para cada uno de los C1subconjuntos de C, buscar aquella separación s∗(C1)que maximice el incremento de impureza. Una vez completado, escoger aquella de las superclases con la que se obtenga un mayor ∆i(s∗(C1), t, C1). El mayor inconveniente que surge de aplicar este criterio es el coste computacional, que crece exponencialmente con la complejidad del problema. Se tiene que para un conjunto de Jclases, existen 2J−1posibles superclases, y que en cada paso de la construcción del árbol, hay que encontrar la división óptima s∗(C1)para todos los C1. Este problema se simplifica enormemente si como función de impureza se aplica Gini en bidimensional ϕ(p1, p2) = p1·p2. Se puede demostrar que en este caso, el aumento de la impureza 20 3. Construcción de un árbol asociado viene dado por ∆i(s, t) = ˆpiˆpd 4   J X j=1 |p(j/ti)−p(j/td)|  2 .(3.3) Siendo C∗ 1(s) = {j/p(j/ti)≥p(j/td)}la superclase que caracteriza esta separación. Poder calcular la impureza antes de separar las clases, hace posible aplicar este criterio con la misma eficiencia que Gini. El principal inconveniente de aplicar este criterio para la construcción de un modelo, es que al juntar varias clases en una categoría conjunta, no tiene sentido medir la impureza total de un árbol. Por esta razón, la única forma de saber si el método funciona correctamente, es una vez completado el árbol. A nivel computacional, si se tiene en cuenta la ecuación 3.3, no hay diferencia entre un criterio u otro. En pruebas realizadas mediante la construcción de árboles por ambos métodos y con la misma base de datos, se ha podido comprobar que en los primeros pasos se comportan prácticamente igual, llegando en muchos casos al mismo resultado final. Aunque es posible construir ejemplos en los que un método es mejor que otro, se suele usar el criterio de Gini, ya que agrupa nodos terminales puros con mayor frecuencia. A diferencia del criterio de Twoing, que tiende más a mantener todos los nodos con el mismo número de elementos, lo que puede llevar a que en algunos casos la eficacia del método sea un poco peor. 3.4. Criterio en un árbol de predicción Sea Tun árbol de predicción en el que el valor asociado a un nodo ν(t)viene dado por la media muestral ¯µ=P(x,Y )∈LtY/Nt, se tiene que el riesgo de uno de sus nodos se estima por r(t) = P(x,Y )∈Lt(Y−¯µ(t))2/Nt. De esta forma, al realizar una separación por s, se observará una disminución del ratio: ∆r(t, s) = r(t)−ˆpi·r(ti)−ˆpd·r(td),(3.4) donde ˆpiyˆpdrepresentan la proporción del conjunto de entrenamiento restringido Ltque caen en cada parte de la división. Calcular esta magnitud para cada una de las parejas (t, s)es un proceso computacionalmente complejo, ya que requiere de elevar una gran cantidad de números al cuadrado. Por esta razón, es importante encontrar un criterio que permita optimizar esta ∆reficientemente. Se considera por tanto que ˆpi=Nti/Ntes un estimador de Pi=P[x ∈Ωti/x ∈Ωt], probabilidad del espacio muestral asociado al nodo tirestringido a Ωt. Recordando que r(t)es 3.5. Conjuntos de preguntas 21 un estimador de la varianza del nodo σ(t) = E[(Y−µ(t))2/x ∈Ωt], se llega a la conclusión que ∆restima δr. δr(t, s) = σ(t)−Pi·σ(ti)−Pd·σ(td).(3.5) Por construcción, µ(t) = Pi·µ(ti) + Pd·µ(td). De la misma forma se cumple la igualdad E[(Y−µ(t))2/x ∈Ωt] = Pi·E[(Y−µ(ti))2/x ∈Ωti] + Pd·E[(Y−µ(td))2/x ∈Ωtd] E(Y−µ(t))2−(Y−µ(tu))2/x ∈Ωt= =Ehµ(t)2−µ(ti)2−2Y(µ(ti)−µ(t)) /x ∈Ωti= =µ(t)2−µ(ti)2−2µ(ti) (µ(ti)−µ(t)= = (µ(t)−µ(ti))2 (3.6) Juntando todo lo anterior, se puede llegar a la conclusión: δr(t, s) = Pi(µ(ti)−µ(t))2+Pd(µ(td)−µ(t))2 =Piµ2(ti) + Pdµ2(td)−µ2t2 =PiPd(µ(ti)−µ(td))2. (3.7) Regresando al mundo de los estimadores, se obtiene el resultado final ∆r(t, s) = pi·pd(ν(ti)− ν(td))2. De donde se concluye que para estimar la disminución del error cuadrático medio al realizar una separación s, es suficiente con estudiar las medias muéstrales en sus nodos hijos. Este resultado se suele utilizar como criterio para construir árboles de predicción. 3.5. Conjuntos de preguntas A lo largo de este capítulo se ha estado visitando los distintos tipos de árboles de clasificación y qué problemas pueden surgir a la hora de construir un modelo de este tipo. A la conclusión a la que se llega en cada apartado, es que para cada nodo ty separación s, se puede construir una función ∆i(t, s)que cuantifica el incremento de la pureza del árbol al realizar dicha división. Bajo los criterios establecidos, se plantea el problema de optimización de encontrar la separación que maximice el incremento de pureza. Por lo general, comprobar todas las separaciones posibles resulta computacionalmente prohibitivo, por lo que se suele acotar a conjuntos concretos de preguntas Q, y se busca el m´axs∈Q∆i(t, s) Con el fin de construir conjuntos de preguntas, en [6] se presentan las siguientes como las particiones más comúnmente usadas. El vector de medidas se describe con la notación x = (x1,...xM) 22 3. Construcción de un árbol En el caso de que xmsea una variable categórica con Bel conjunto de categorías, se tendrá que las preguntas posibles son de la forma s=¿xm∈B∗?, donde B∗⊂B x ∈B x ∈B∗x ∈¯ B∗ Para el caso de variables continuas, la partición más sencilla es mediante la aplicación de hiperrectángulos. Para un xmy un valor real cse define la pregunta s=¿xm< c? Se puede complicar un poco más los cortes lineales mediante la aplicación de hiperplanos, se toma un vector de pesos a = (a1,...an), un valor real cy se define la pregunta s=¿at·x < c? Por último, también se suelen construir lo que se denominará como árboles esféricos, en los que las divisiones del espacio vectorial se determinan entre dentro y fuera de una bola. Se toma un centro z y un radio cy se define s=¿∥x −z ∥< c? Todo esto se puede complicar mediante la aplicación de recursos más complejos o mediante la combinación de preguntas. Por ejemplo si x1es una variable categórica y x2una continua, s=¿x1∈B∗&x2< c? sería una pregunta válida. 3.6. Conjunto estándar de preguntas A la hora de construir un árbol, la inclusión de demasiados tipos de preguntas puede llevar a la construcción de un conjunto Qdemasiado grande, lo que resultaría en un coste computacional demasiado elevado para una mejora de ∆i(t, s)mínima. Por esta razón, generalmente se emplea el conjunto de preguntas estándar, el cual ofrece un gran número de preguntas, una manera sencilla de obtenerlas, y en la práctica, un tiempo de fabricación del árbol aceptable. Sea L= (xi, Yi)i=1...N el conjunto de entrenamiento en el que xi= (xi 1, xi 2, . . . , xi M)representa el vector de medidas de un modelo, el conjunto de preguntas estándar estará compuesto por la unión Q=SM m=1 Qm. Las preguntas de cada conjunto Qmúnicamente hacen referencia a la variable xm, y el primer paso en la separación de un nodo, será la construcción de cada uno de 3.6. Conjunto estándar de preguntas 23 estos subconjuntos. En el caso de que xmsea una variable continua, Qmestará compuesto por preguntas de la forma ¿xm< c?. Para facilitar la explicación, se considera que el conjunto de mediciones de xm está ordenado, {x1 m≤x2 m≤ · · · ≤ xN m}. Se define así ci m= (xi+1 m−xi m)/2sucesión de puntos medios, y se construye el conjunto de preguntas Qm={¿xm< ci m?/i = 1 . . . N −1}. Hay que tener en cuenta que todos los cortes cen el intervalo (xi m, xi+1 m)representan la misma pregunta ¿xm< c?, ya que llevan a cabo la misma separación del conjunto de entrenamiento. Se decide tomar el punto medio ya tiende a separar el espacio muestral en partes equiprobables. En el caso de que xmrepresente una variable categórica sobre el conjunto B={b1,...bn}, Qmestará compuesto por todos los posibles divisiones de B,Qm={¿xm∈B∗?/B∗⊂B}. Esto representa 2|B|−1−2preguntas posibles, ya que ∅yBno ofrecen información al modelo y por simetría B∗lleva a cabo la misma separación que su complementario ¯ B∗. 24 3. Construcción de un árbol Capítulo 4 Podado y tamaño adecuado La principal cuestión en la construcción de este tipo de modelos, es asegurarse que el árbol final sea una buena representación del medio real al que se va a enfrentar. Por desgracia, a la hora de construirlo, solo se dispone de una cantidad de información limitada por el conjunto de aprendizaje, lo que dificulta juzgar si el modelo realiza predicciones buenas o no. Con este fin, se suele dividir el conjunto de aprendizaje en dos partes, uno de entrenamiento Le, usado para la construcción, y uno de validación, Lv, al margen del anterior, dedicado a juzgar si el modelo realiza predicciones correctas. Se ha definido el ratio R(T)como un estimador del error cometido por un modelo, para este apartado se distinguirá entre ReyRv, en función si se han utilizados los datos del conjunto de entrenamiento o de validación. Es importante que el árbol final sea del tamaño adecuado, demasiado pequeño, y no extraerán todas las relaciones contenidas en el conjunto de aprendizaje, demasiado grande, y se llegarán a errores de sobredimensión, en los que se pierde parte de la información. En 4.1 se grafican datos de un estudio de [5]. A partir de una serie de experimentos consistentes en construir clasificadores para diversas bases de datos, se presenta la evolución de los errores medios en función del número de nodos terminales del árbol. Se puede observar el efecto de sobredispersión en Rv, a partir de los 10 nodos terminales, el error aumenta de nuevo. Por otro lado, Resiempre decrece, da igual el número de nodos o qué división se realice. Este resultado que se demuestra en 4.1. Proposición 4.1. Sea suna separación del nodo tentre tiytd, se tiene que ∆re(t, s)>0 Demostración. En el caso de que el modelo creado sea de predicción, en 3.7 se deduce que ∆re(t, s) = pi·pd(νe(ti)−νe(td))2, claramente superior a 0. 25 32 4. Podado y tamaño adecuado Capítulo 5 Métodos alternativos 5.1. Boostrap y Bagging El método Boostrap, introducido por Efron B. en [8], permite la reducción de la varianza en el cálculo de un estimador a partir de una base de datos L={x1,...xN}. Por ejemplo, se podría tener s(x), un estimador de cierto parámetro θ, como la media muestral ¯x=1 NPxies un estimador de la esperanza de la variable respuesta. El algoritmo consiste en la construcción de un conjunto de Boostrap L(B)={L1, . . . LM} en el que cada uno de sus elementos es un subconjunto diferente de L. Generalmente, cada una de las muestras de Boostrap se construye mediante la toma con reemplazo de puntos de L. De esta forma, todos son del mismo tamaño, pero tienen algunos elementos repetidos. La fuerza del método se basa en estas pequeñas diferencias, ya que cada árbol desarrollará distintas sutilezas, que suman en el modelo final. A partir de aquí, para cada uno de los Lmse aplica spara conseguir Mestimadores distintos de cierto θ. Se define por último el estimador de Boostrap ˆ θ(B), la media aritmética del calculado a partir de cada uno de las muestras del conjunto de Boostrap. Se puede demostrar que este método permite la construcción de estimadores con una menor varianza real. Para más detalles en este tema remitir al libro de Efron and Tibshirani(1994) [9], en concreto el capítulo 6 en el que demuestran las ventajas de este método. 5.1.1. Aplicación a árboles Después de su creación, y debido al éxito que tenía el método Boostrap para reducir la varianza en estimadores muestrales, se intentó aplicar la misma técnica a distintos problemas 33 34 5. Métodos alternativos con el fin de obtener resultados, en Breiman(1996) [2] se plante su aplicación a los modelos en forma de árbol. A esta técnica se le acabó llamando Bagging (Boostrap Agregating). El primer paso es el mismo que en el método general, a partir del conjunto de entrenamien- to, se construye un conjunto de Boostrap L(B). Este estará formado por distintos conjuntos elaborados a partir de los elementos de L. Una vez que se tiene un árbol construido a partir de cada una de las muestras del conjunto de Boostrap, se unen en el modelo de Bagging dB(x). En el caso de que el modelo a desarrollar sea un predictor, se aplica la media muestral dB(x) = Pdm(x)/M, y para un clasificador, se tiende a usar un método por votación. A partir del vector de medidas x, se estima la probabilidad de que pertenezca a la clase j,ˆpj(x), como el porcentaje de los árboles que predicen dm(x) = j. De esta forma, el clasificador de Bagging, toma como dB(x)aquella clase con una mayor ˆpj(x). Estos mismos resultados se pueden emplear para construir modelos de estimación de la probabilidad a partir de los ˆp(x) La segunda parte en la construcción de un árbol, consiste en el podado. Al final de este proceso, a la hora de tomar un modelo final, apartado 4.4, se precisa de un conjunto de testeo, un muestreo con una distribución similar al conjunto de entrenamiento, pero independiente de este. Esto es sencillo de conseguir en Bagging, cualquier subconjunto de Lobtenido bajo los mismos criterios que las muestras de Boostrap, cumplen condiciones similares a las deseadas. De esta forma es posible conseguir los test necesarios sin usar el conjunto de validación. 5.1.2. Por qué Bagging funciona A pesar de que en un principio los métodos Boostrap no fueron creados para la construcción de estimadores, se puede comprobar de manera sencilla que los modelos diseñados por este método, tienden a ser mejores que los árboles construidos directamente con todo el conjunto de aprendizaje. Se define el predictor agregado dA(x) = EL[d(x, L)], siendo ELla esperanza medida sobre la variable aleatoria L. Esta toma la forma de diversos subconjuntos de aprendizaje siguiendo una distribución P. Dado un elemento conocido (x, y), se tiene que la esperanza media del error cuadrático cometido viene dada por: EL[(y−d(x, L))2] = y2−2yEL[d(x, L)] + EL[d(x, L)2](5.1) Considerando que por definición dA(x) = EL[d(x, L)] y aplicando la propiedad E[Z2]≥E2[Z] 5.1. Boostrap y Bagging 35 para toda distribución Z, se cumple la desigualdad: EL[(y−d(x, L))2]≥y2−2ydA(x) + d2 A(x)=(y−dA(x))2(5.2) De donde se deduce que el predictor agregado tiende a comportarse mejor que los diversos predictores construidos. En el plano muestral, se tiene que dBes un estimador de dA, donde el conjunto de Bagging {L(B)}es una muestra de la distribución P Este método funciona especialmente bien sobre bases de datos inestables, una gran dispersión en el conjunto de aprendizaje, hace que los modelos reducidos d(x, L)den resultados muy diversos. En estas situaciones, la desigualdad 5.2 se hace especialmente marcada, y los modelos obtenidos por Bagging sobresalen con respecto al resto. Por otra parte, en el caso de bases estables, los diversos predictores d(x, L)son similares los unos a los otros, por lo que dBno ofrecerá ninguna información extra, a pesar de ser un método computacionalmente costoso. 5.1.3. Resultados experimentales La principal razón por la que se emplea Bagging en la construcción de árboles, es porque en bases de datos reales se puede observar una disminución significativa del error cometido. Con el fin de presentar resultados reales, se mencionan conclusiones del artículo Breiman(1996) [2], en el que se estudia la mejor forma de construir estimadores de Bagging a partir de diversas bases de datos. Para la construcción de clasificadores, se observa que 10 muestras de Boostrap tienden a ser suficientes para conseguir mejoras del 30 % en la disminución del error por clasificación incorrecta. Por lo general, el uso de conjuntos de Bagging más grandes no suelen ofrecer mejoras significativas de los modelos. En el caso de predictores, por lo general se tiende a necesitar un mayor número de muestras para conseguir mejoras considerables. Sin embargo, se consiguen mejores resultados que en los clasificadores. Bajo los casos estudiados, usando conjuntos de Boosting de 25 elementos, se consiguen mejoras de en torno al 40 % del error cometido. Un fenómeno que ha sido observado al aplicar estos métodos, es que si a los árboles no se les aplica el podado, los resultados finales no empeoran. La explicación que se le suele dar a esto, es que no podar proboca errores en áreas locales del espacio muestral. Al generar un gran número de modelos, estos fallos puntuales tienden a suavizarse al combinar todos los árboles. 36 5. Métodos alternativos 5.2. Boosting En [12], Schapire R. E. plantea un nuevo método para la construcción de estimadores precisos. Boosting permite reducir el error cometido de cualquier clasificador, solo es necesario que sea un poco mejor que si la elección de clase fuese aleatoria. Se llamarán modelos "debiles.aaquellos que no sean mucho mejores que la clasificación aleatoria. Boosting se basa en la generación continua de modelos "débiles", para finalmente recombinarlos en un clasificado compuesto. En este último paso se le da más importancia a aquellos modelos parciales que se ajustan mejor al conjunto de aprendizaje. Cada una de las parejas (xi, Yi), tienen asociado un peso wi, que se aplica a la función de error a la hora de construir el árbol. De esta forma, los puntos con un mayo w, tienen mayor importancia en el modelo. En cada paso, estos varían, haciendo que cada uno de los árboles dm sean distintos entre sí. 5.2.1. AdaBoost Entre las distintas propuestas de Boosting, la que ha tenido más popularidad ha sido el algoritmo AdaBoost, aquí se hablará de los trabajos de Freund Y. y Schapire R. E., en concreto de [10], ya que presenta las bases necesarias como para poder aplicar el algoritmo a problemas reales. Algoritmo AdaBoost.M1 Entrada: conjunto de aprendizaje de tamaño M,L= (xi, Yi), con Y∈ C ={1,...J} Inicializar los pesos wi= 1/M For t∈ {1,...T}: Construir modelo dta partir de los pesos wi Calcular error, ϵt=Pdt(xi)=Yiwi Asignar βt=ϵt/(1 −ϵt) Actualizar pesos, si dt(xi=Yi),wi=βtwi Normalizar los pesos a 1 Modelo final, d(x) = arg m´axj∈C Pt/dt(x)=jlog 1 βt Este planteamiento del problema sirve únicamente para creación de clasificadores. En el caso de que se quiera usar en predictores, se puede modificar cambiando la definición del error aϵt=P(xi,Yi)wi(dt(xi)−Yi)2. Sin embargo, esto puede introducir nuevos inconvenientes, y requiere un estudio del problema más profundo. De momento el trabajo se centrará en árboles de clasificación. 5.2. Boosting 37 En cada paso del algoritmo se construye un modelo dtdistinto, este no tiene por qué ser un árbol, incluso hay estudios de como afecta Boosting a los distintos métodos de aprendizaje, véase [10]. Centrándonos en la creación de árboles de decisión, es necesaria la introducción de los wien el proceso de construcción. La idea detrás de estos pesos, es hacer que los modelos se centren en clasificar correctamente aquellos puntos con un mayor w. En el caso de árboles, este proceso es un poco más complicado, ya que la construcción de estos modelos no está preparada para introducir pesos en el conjunto de aprendizaje. La solución propuesta es similar a las muestras Boostrap, coger con reemplazo elementos de L, para construir un conjunto de entrenamiento de dt. Se aprovecha que los w’s tienen forma de distribución para hacer que la probabilidad de tomar cada punto sea wi. De esta forma se consigue que los árboles tiendan a clasificar correctamente los puntos de mayor peso. Notar que para el primer modelo, los pesos son uniformes, de tal forma que el árbol que se genera, es el mismo que si no se estuviese aplicando Boosting. La eficacia del algoritmo se basa en cómo se actualizan los pesos. Los nuevos modelos deben ser capaces de clasificar correctamente aquellos puntos que los antiguos fallaron. De esta forma se introduce el factor βt∈[0,1), que reduce el peso de las clasificaciones acertadas. Antes de avanzar al siguiente paso, se renormalizan los w′spara que mantengan la forma de distribución. Una vez repetido este proceso un número Tde veces, se construye el modelo final. Dado un vector de medidas x, se observa en que clase lo clasifican cada uno de los dt, y se le asigna aquella clase jque maximice Pt/dt(x)=jlog 1 bt. En cada paso se calcula un βt, este debe tender a cero si el error del modelo es bajo, y preferiblemente menor que uno. Experimentalmente se ha comprobado que βt=ϵt/(1 −ϵt) tiende a construir modelos precisos. Es capaz de mantener el equilibrio entre sus dos funciones, modificar los pesos wiy cuantificar la influencia de dten el modelo final. A pesar de que se ha comprobado que este método funciona especialmente bien con modelos "débiles", tiene problemas graves si el error cometido es mayor que ϵt>1/2. Esta condición es complicada de cumplir si el número de clases disponibles es elevado. El algoritmo AdaBoost.M2 intenta corregir esto. Para ello aumenta la dimensión del problema, haciendo que cada pareja punto/clase (i, j)tenga un peso distinto, y que los modelos parciales hagan hipótesis dt(i, j)∈[0,1]. Si se quiere llevar a árboles, será necesario el uso de estimadores de la probabilidad de clasificación. El algoritmo es algo más complicado, pero hay pruebas experimentales de que si el número de clases es elevado, esta versión da resultados mucho mejores que la M1. 38 5. Métodos alternativos 5.2.2. Comparación con Bagging Por lo general, en experimentos se ha comprobado que Boosting tiende a generar modelos más precisos que Bagging. Esto se debe a que la formación de los conjuntos de aprendizaje parciales es menos arbitraria, contiene más información. Esta diferencia se reduce a medida los árboles generados son más complejos. En [3], Breiman L. hace sus propios experimentos comparando Bagging con Boosting. Llega a la conclusión de que el proceso de votación con pesos del AdaBoost hace que los modelos finales tiendan a ser mas precisos que los obtenidos por Boosting. 5.3. Ejemplos Por último, se presentan una serie de modelos construidos sobre un mismo conjunto de aprendizaje con el fin de estudiar cómo se comportan. Como base de datos se usará una vez más "Wine Data Set"de [7], que trata de clasificar el cultivo al que pertenece una serie de vinos a partir de un análisis químico. Se ha podido comprobar que esta base de datos se clasifica realmente bien, en ejemplos anteriores se han conseguido precisiones elevadas a partir de modelos muy básicos. Con el fin de mostrar la potencia de los métodos más complejos, se excluyen del estudio aquellas variables que discriminan bien entre cultivos, en concreto la cantidad de alcohol, flavanoides, proteínas OD280.OD315, prolinas y la intensidad del color del vino. Con el fin de realizar un estudio más profundo de los modelos, se separa la base de datos entre un conjunto de entrenamiento y uno de validación. El primero se construye cogiendo al azar el 80 % de los elementos totales. 5.3.1. Árbol de clasificación Con el fin de mostrar un modelo de referencia, se construye un árbol clásico a partir de los mismos datos que se usarán para el resto de modelos. Para este paso se utiliza el paquete caret [11], ya que ofrece una recopilación de los distintos métodos de entrenamiento. En concreto, se utiliza la creación de árboles del rpart reforzado por una implementación de la validación cruzada. El modelo presentado en 5.1 tiene un error de validación Rv= 0,269. Además de este, se intentaron construir varios árboles a partir de la misma información, sin conseguir una mejora 5.3. Ejemplos 39 Figura 5.1: Árbol de clasificación considerable en el error cometido. No parece sencillo construir un modelo simple satisfactorio a partir de la base de datos con la que se está trabajando, lo que exige la aplicación de métodos más complejos. 5.3.2. Bagging y Boosting Se tiene que los modelos construidos por Bagging y Boosting son bastante similares, por lo que se estudian a la vez con el fin de compararlos entre sí. Ambos métodos se basan en la formación sucesiva de muestras de Boostrap a partir del conjunto de entrenamiento, esta elección tiene una componente aleatoria, lo que dificulta un estudio preciso de la metodología. A falta de un estudio preciso de como se comportan ambos métodos en función del número de replicas Boostrap creadas y el método utilizado para construir cada uno de los árboles individuales, se opta por crear una serie de modelos de ambos tipos bajo las mismas condiciones y comparar el error de validación medio. Para la creación de modelos se usa el paquete "adabag"de R [1], ya que ofrece implementaciones de ambos algoritmos empleando el mismo método de construcción de árboles. En todos los casos se construirán clasificadores a partir de 20 muestras diferentes. En Boosting se aplica el algoritmo AdaBoost.M1 tal cual introducido en este Capítulo, con los coeficientes de Freund βt=ϵt/(1−ϵt). En 5.2 y 5.3 se muestran los cuatro primeros árboles construidos a partir de una de las iteraciones de cada uno de los métodos aquí estudiados. Observando a simple ojo los árboles construidos por ambas metodologías, no es posible apreciar ninguna diferencia fundamental las dos series. Todos han sido construidos bajo las mismas 40 5. Métodos alternativos Figura 5.2: Sucesión de árboles obtenida aplicando Bagging condiciones, variando ligeramente el conjunto de aprendizaje. La diferencia fundamental entre Bagging y Boosting, es que el segundo utiliza información del árbol anterior en la construcción del siguiente. En estos experimentos, se puede observar que los modelos Boosting tienden a tener un menor ratio de validación. Haciendo media sobre 10, se mide Rv= 0,0847 para los construidos por AdaBoost y Rv= 0,172 para los Bagging. A pesar de ser claramente inferiores, los modelos construidos por Bagging son claramente superiores al árbol de clasificación estándar. La única desventaja de estos métodos es el tiempo, cada proceso consta de la fabricación de 20 modelos simples, lo que retrasa enormemente su creación. 5.3.3. Random Forest En [4], Breiman propone un nuevo método para la generación de modelos a partir de árboles de decisión. Random Forest es una versión de su anterior Bagging que ofrece resultados tan precisos como los Boosting con un coste computacional incluso menor. En este método, para la construcción de cada árbol parcial, no solo se escoge de manera aleatoria el conjunto de entrenamiento, sino que también se limitan la cantidad de separaciones posibles. Este proceso sigue una actualización de costes similar al algoritmo AdaBoost. Para el experimento, se usará la implementación presente en el método rf"del paquete [11] de R. Tras hacer una serie de experimentos aplicando Random Forest con 20 pasos, se ha conseguido 5.3. Ejemplos 41 Figura 5.3: Sucesión de árboles obtenida aplicando AdaBoost M.1 una media Rv= 0,00723. Los modelos obtenidos de esta forma son realmente precisos, y sin entrar en un estudio preciso de los árboles parciales o el tiempo de ejecución, si que tiende a parecer que en este método consigue mejores resultados de manera más eficiente que los AdaBoost del apartado anterior.