Librería en R para la generación heurística de árboles de decisión

! 2! ! 3! ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA GRADO EN INGENIERÍA DEL SOFTWARE LIBRERÍA EN R PARA LA GENERACIÓN HEURÍSTICA DE ÁRBOLES DE DECISIÓN R-BASED LIBRARY FOR HEURISTIC GENERATION OF DECISION TREES Realizado por Marcos Vergara Gómez Tutorizado por Eduardo Guzmán de los Riscos Departamento Lenguajes y Ciencias de la Computación UNIVERSIDAD DE MÁLAGA MÁLAGA, Septiembre 2016 Fecha defensa: El Secretario del Tribunal ! ! ! ! 4! ! 5! AGRADECIMIENTOS En primer lugar, quiero darle las gracias más sinceras a mi director de Trabajo de Fin de Grado, Eduardo, por haberme dado la oportunidad para realizar este trabajo y poder aprender de él, pero sobre todo agradecer toda su ayuda y el magnífico trato recibido. Gracias a todos mis amigos, compañeros y a todas aquellas personas que en algún momento me hayan apoyado y hayan estado dispuestas a ayudarme. Gracias a mi tía Juana y a mis abuelos, María y José, que en paz descanse, por todo el apoyo diario desde pequeño y por haber dado una gran parte de su vida por hacerme mejor persona. Gracias a mi hermano Eloy, por estar apoyándome en los buenos y malos momentos. Gracias a mi padre, por aquellos días en que me obligabas a machacar y machacar la lección de pequeño, parece que por fin empieza a verse la recompensa. Gracias a mi madre, por intentar ayudarme siempre en todo y haberme enseñado que trabajando, luchando y confiando en uno mismo, todo se acaba consiguiendo. ! 6! ! 7! Resumen: Se ha implementado una API en R para la generación de árboles de decisión. Se ha trabajado con un fichero de datos, con una serie de síntomas que han provocado una enfermedad, que ha sido depurado posteriormente. Hemos implementado una función en la que, a partir del fichero de datos y un conjunto de síntomas ordenados a nuestra elección, se crea el árbol de decisión que en cada elección escogerá el síntoma indicado anteriormente. El siguiente paso ha sido crear dos funciones de predicción que nos sirvan para comparar los resultados reales con los resultados obtenidos por el árbol de decisión. Tras construir el árbol y las funciones de predicción, crearemos una función que unificará ambas tareas. Este método será la validación cruzada que nos permitirá obtener mejores resultados. Finalmente, se ha realizado una comparación de los resultados obtenidos con nuestro método y los resultados extraídos por los algoritmos existentes hasta la actualidad. La implementación de todas las funciones se ha llevado a cabo con el programa estadístico R, mientras que para la comparación de resultados se ha utilizado la herramienta de minería de datos Weka. Palabras clave: Árbol de decisión, R, Weka, Clasificación, Predicción, Validación Cruzada Abstract: An API has been implemented in R to generate decision trees. It has worked with a data file, with a series of symptoms that have caused a disease, which has been refined later. We have implemented a function in which from the data file and a set of ordered symptoms of our choice, a decision tree that in every choice will pick the symptom previously mentioned is created. The next step was to create two prediction functions, which help us to compare actual results with results obtained by the decision tree. After building the tree and prediction functions, we will create a function that will unify both tasks. This method will be the cross-validation that will enable us to obtain better results. Finally, it has been made a comparison between the results obtained with our method and the results extracted from existing algorithms until now. The implementation of all functions has been carried out with the statistical program R, while for the comparison of results has been used the data mining tool Weka. Keywords: Decision Tree, R, Weka, Classification, Prediction, Cross-validation ! 8! ! ! 9! Índice' 1.!INTRODUCCIÓN,11! 1.1.!CONTEXTO,11! 1.2.!OBJETIVOS,12! 1.3.!ESTRUCTURA,DE,LA,MEMORIA,12! 1.4.!TECNOLOGÍAS,UTILIZADAS,12! 1.4.1.!R! 12! 1.4.2.!WEKA!14! 1.5.!METODOLOGÍA,15! 1.6.!FASES,DEL,PROYECTO,15! 2.!DEFINICIÓN,Y,PREPROCESAMIENTO,DE,LOS,DATOS,17! 2.1,DEFINICIÓN,DE,LOS,DATOS,A,UTILIZAR,17! 2.2,PREPROCESAMIENTO,DE,LOS,DATOS,18! 3.ESTADO,DEL,ARTE,21! 3.1,INTRODUCCIÓN,21! 3.2,CONCEPTO,DE,ÁRBOL,DE,DECISIÓN,21! 3.3,ALGORITMOS,EXISTENTES,SOBRE,ÁRBOLES,DE,DECISIÓN,Y,MÉTODOS,BAYESIANOS,24! 3.3.1!ID3!25! 3.3.2!C4.5!27! 3.3.3!NAÏVE!BAYES!29! 3.4,LIBRERÍAS,EN,R,SOBRE,ÁRBOLES,DE,DECISIÓN,33! 4.,ALGORITMO,DE,CREACIÓN,DEL,ÁRBOL,DE,DECISIÓN,39! 4.1,INTRODUCCIÓN,Y,MOTIVACIÓN,39! 4.2,UTILIZACIÓN,DE,LA,LIBRERÍA,DATA.TREE,39! 4.3,ALGORITMO,PARA,CREAR,EL,ÁRBOL,DE,DECISIÓN,39! 4.4,EJEMPLO,42! 5.,VALIDACIÓN,DE,RESULTADOS,OBTENIDOS,CON,EL,ÁRBOL,DE,DECISIÓN,51! 5.1,FUNCIÓN,DE,PREDICCIÓN,DEL,MÁXIMO,VALOR,51! 5.2,FUNCIÓN,DE,PREDICCIÓN,DE,TODAS,LAS,OPCIONES,53! 5.3,INTRODUCCIÓN,AL,CONCEPTO,DE,VALIDACIÓN,CRUZADA,55! 5.4,VALIDACIÓN,CRUZADA,PARA,FUNCIÓN,DE,PREDICCIÓN,DEL,MÁXIMO,VALOR,58! 5.5,VALIDACIÓN,CRUZADA,PARA,FUNCIÓN,DE,PREDICCIÓN,DE,TODAS,LAS,OPCIONES,66! 6.,COMPARACIÓN,DE,RESULTADOS,69! 6.1,INTRODUCCIÓN,69! 6.2,VARIABLES,NECESARIAS,PARA,LA,COMPARACIÓN,DE,RESULTADOS,69! 6.3,COMPARACIÓN,DE,MÉTODOS,EXISTENTES,76! 7.,CONCLUSIONES,Y,LÍNEAS,FUTURAS,79! 7.1,CONCLUSIONES,79! 7.2,LÍNEAS,FUTURAS,79! ! 16! ! 17! 2. DEFINICIÓN'Y'PREPROCESAMIENTO'DE'LOS'DATOS'' ! 2.1)DEFINICIÓN)DE)LOS)DATOS)A)UTILIZAR) ! Durante todo el trabajo a realizar, vamos a trabajar con un fichero de datos de tipo .xls que estará compuesto por 1000 filas y 12 columnas. Las 1000 filas estarán referidas a las diferentes observaciones de los individuos de los diversos síntomas que puedan o no tener. Mientras que las 12 columnas nos indicarán los síntomas que podrán tener los individuos. Los datos estarán referidos a casos de meningitis, ocurridos en Bahía (Brasil), durante los últimos 10 años, proporcionados por DATASUS. La meningitis es una enfermedad infecciosa con alta tasa de mortalidad, especialmente en los países menos desarrollados. DATASUS, el departamento de Informática del sistema de salud pública brasileño (SUS), almacena y pone a disposición de profesionales, investigadores y de administradores de salud pública una enorme cantidad de datos sobre la salud, que es con frecuencia infrautilizado. Un estudio retrospectivo de estos datos para trazar un modelo de comportamiento de la enfermedad en una particular región y la simulación de posibles escenarios podían ser bastante útiles en la toma de decisiones para reducir la incidencia y la mortalidad de esta enfermedad. Estos síntomas que pueden tener los individuos son: 1. CLI_CEFALE: Cefalea 2. CLI_FEBRE: Fiebre 3. CLI_VOMITO: Vómito 4. CLI_CONVUL: Convulsiones 5. CLI_RIGIDE: Rigidez 6. CLI_KERNIG: Kernig 7. CLI_ABAULA: Abultamiento 8. CLI_COMA: Coma 9. CLI_PETEQU: Petequias Asimismo, el fichero contiene la siguiente información adicional § CLASSI_FIN: Clasificación final § CON_DIAGES: Diagnóstico ! 18! § EVOLUCAO: Evolución Los primeros 9 síntomas pueden tomar los valores -1 (valor inválido), 1 (tiene el síntoma), 2 (no tiene el síntoma), 9 (valor inválido), donde como veremos posteriormente fusionaremos los valores -1 y 9 en el valor 0, para reducir la complejidad. La variable “CLASSI_FIN” indica si el paciente tiene o no meningitis; “CON_DIAGES”, indica el tipo de meningitis, toma los valores -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Si presenta el valor -1 indica que el dato no está. Los valores 1, 2, 3 indican que el individuo presenta meningitis meningocócica. El valor 4 significa que el individuo tiene meningitis tuberculosa. El valor 6 significa que no está especificado. El resto de valores indica que el individuo presenta otros tipos de meningitis. La variable “EVOLUCAO” nos indica la evolución del individuo y toma los valores -1 (vacío), 1 (curado), 2 (muerto por meningitis), 3 (muerto por otras causas), 9 (no se sabe). En la figura 3, veremos una vista previa del fichero de datos. ! Figura 3: Vista previa del fichero de datos 2.2)PREPROCESAMIENTO)DE)LOS)DATOS) ! 19! Una vez que se tienen los datos que vamos a utilizar, realizaremos un par de cambios para menor complejidad y poder acercarnos a los resultados que deseamos obtener. En primer lugar, eliminaremos la variable “EVOLUCAO”, puesto que el objetivo es, en la medida de lo posible, diagnosticar si un paciente tiene meningitis y el tipo de meningitis. En segundo lugar, para los primeros 9 síntomas, en los individuos que tengan el valor -1 o 9, lo convertiremos en 0. Con esta medida, estas 9 variables tendrán un valor posible menos y nos ayudará posteriormente a reducir el tamaño del árbol de decisión.(Decir lo que significaban -1 y 9). Finalmente, la última medida que vamos a tomar, es convertir todos los valores de la tabla, de Número a Factor, debido a que nos ayudará en la construcción del árbol de decisión. El principal motivo de esta medida es que si dejamos la tabla con valores de tipo Número, las divisiones se realizarán con números reales, por ejemplo, CLI_CEFALE > 1.94, y no es lo que queremos conseguir en la construcción del árbol. ! 20! ! ' ! 21! 3.ESTADO'DEL'ARTE' 3.1)INTRODUCCIÓN) El objetivo de este capítulo es presentar aquellas tecnologías y trabajos relacionados con el presente proyecto. La finalidad es facilitar al lector la comprensión de los siguientes capítulos y esclarecer todos los conceptos de forma que pueda valorar adecuadamente las contribuciones del proyecto. Concretamente, vamos a hablar sobre los árboles de decisión y comentar los diferentes algoritmos que han sido creados hasta la fecha. Finalmente, hablaremos sobre algunas de las librerías sobre árboles de decisión creadas hasta la actualidad. 3.2)CONCEPTO)DE)ÁRBOL)DE)DECISIÓN) Los árboles de decisión se pueden aplicar prácticamente a todo. Los sistemas de aprendizaje basados en árboles de decisión son posiblemente el método más fácil de utilizar y de entender. Un árbol de decisión es un conjunto de condiciones organizadas en una estructura jerárquica, de tal manera que la decisión final a tomar se puede determinar siguiendo las condiciones que se cumplen desde la raíz del árbol hasta alguna de sus hojas. Los árboles de decisión se utilizan desde hace siglos, y son especialmente apropiados para expresar procedimientos médicos (como utilizaremos durante este trabajo), legales, comerciales, estratégicos, matemáticos, lógicos, etc. En la figura 4, vemos dos ejemplos simples de árboles de decisión: ! 22! ! Figura 4: Ejemplos de árboles de decisión Una de las ventajas más importantes de los árboles de decisión es que, en su forma más general, las opciones posibles a partir de una determinada condición son excluyentes. Esto permite analizar una situación y, siguiendo el árbol de decisión apropiadamente, llegar a una sola acción a decisión a tomar. Estos algoritmos se llaman algoritmos de partición o algoritmos de “divide y vencerás”. Otra característica importante de los primeros algoritmos de aprendizaje de árboles de decisión es que una vez que elijamos la partición, dicha partición no se podrá cambiar, aunque más tarde se pueda llegar a pensar que ha sido una mala elección. Por lo tanto, uno de los aspectos más importantes en los sistemas de aprendizaje de árboles de decisión es el llamado criterio de partición, ya que una mala elección de la partición(sobre todo, en las partes superiores del árbol) generará un peor árbol. En la figura 5, vemos en pseudolenguaje el algoritmo básico de los árboles de decisión: ! 23! ! Figura 5: Algoritmo de árbol de decisión en pseudolenguaje Lo que hace el algoritmo es simplemente, ir construyendo el árbol (desde el árbol que sólo contiene la raíz) añadiendo particiones y los hijos resultantes de cada partición. Lógicamente, en cada partición, los ejemplos se van dividiendo entre los hijos. Finalmente, se llega a la situación en la que todos los ejemplos que caen en los nodos inferiores son de la misma clase y esa rama ya no sigue creciendo. La única condición que hay que exigir es que las particiones al menos separen ejemplos en distintos hijos. Como acabamos de explicar, los dos puntos más importantes para que el algoritmo funcione bien son los siguientes: - Particiones a considerar: un conjunto de condiciones exhaustivas y excluyentes. Cuantas más particiones permitamos más expresivos podrán ser los árboles de decisión generados y, probablemente, más precisos. No obstante, cuantas más particiones elijamos, la complejidad del algoritmo será mayor. Por tanto, debemos encontrar un buen compromiso entre expresividad y eficiencia. Debido a esto, la mayoría de algoritmos de aprendizaje de árboles de decisión sólo permiten un juego muy limitado de particiones. Por ejemplo, el C4.5 contiene un solo tipo de partición para los atributos nominales y un solo tipo de partición para los atributos numéricos. - Criterio de selección de particiones: incluso con sólo los dos tipos de particiones sencillas vistas, el número de particiones posibles en cada caso puede dispararse(si existen n atributos y m valores posibles para cada atributo, el número de ! 24! particiones posibles es de n·m). Los algoritmos clásicos de aprendizaje de decisión son voraces, en el sentido de que una vez elegida la partición se continúa hacia abajo la construcción del árbol y no vuelven a plantearse las particiones ya construidas. Por tanto, se debe buscar un criterio que permita realizar una buena elección de la partición que parece más prometedora y que esto se haga sin demasiado esfuerzo computacional. Esto es lo que diferencia fundamentalmente los distintos algoritmos de árboles de decisión hasta la actualidad, como ID3, C4.5, etc. 3.3)ALGORITMOS)EXISTENTES)SOBRE)ÁRBOLES)DE)DECISIÓN)Y)MÉTODOS) BAYESIANOS) Antes de comenzar a explicar los distintos algoritmos sobre árboles de decisión, conviene recordar una serie de conceptos estadísticos que nos serán de utilidad. Dos variables son independientes si se cumple que: 𝑃 𝑥, 𝑦 = 𝑃(𝑥)𝑃(𝑦) Probabilidad condicionada: Sea (W, a, P) un espacio probabilístico y A un suceso de a de probabilidad no nula, P(A) > 0. Si B es un suceso cualquiera de a, se llama probabilidad de B condicionada a A, al número P(B | A) definido por: 𝑃 𝐵 𝐴 = 𝑃(𝐴 ∩ 𝐵) 𝑃(𝐴) que mide la ocurrencia del suceso B si se sabe que ha ocurrido el suceso A. El Teorema de Bayes nos dice: Sea (W, a, P) un espacio probabilístico, y sea Ai, para i=1,2,…,n, una partición de W formada por una colección finita de sucesos de probabilidad no nula. Sea B un suceso tal que P(B) ¹ 0. Entonces: 𝑃 𝐴+𝐵 = 𝑃(𝐴+)𝑃 𝐵 𝐴+ 𝑃(𝐴,)𝑃 𝐵 𝐴, - ,./ La entropía se calcula con la siguiente fórmula: 𝐻 𝑥 = − 𝑃 𝑋 = 𝑥,·𝑙𝑜𝑔7𝑃 𝑋 = 𝑥, - ,.8 ! 25! 3.3.1'ID3' ID3 es un algoritmo de aprendizaje que pretende modelar los datos mediante un árbol de decisión. Fue creado por J.R.Quinlan en 1986. Se encuentra englobado dentro del llamado aprendizaje inductivo y supervisado. En este árbol, los nodos intermedios son atributos de los ejemplos de la tabla de datos, las ramas representan valores de dichos atributos y los nodos finales son los valores de la clase, que en nuestro caso nos da el diagnóstico, como ya vimos al hablar de los árboles de decisión binarios. Tanto éste como el algoritmo que hablaremos a continuación, el C4.5, pertenecen a la familia de métodos de inducción TDIDT(Top Down Induction Trees). Ambos generan árboles y reglas de decisión a partir de datos preclasificados. Para construir los árboles usamos el método de divide y vencerás. El ID3 construye árboles de decisión a partir de un conjunto de ejemplos. Estos ejemplos o tuplas están constituidos por un conjunto de atributos y un clasificador. Los dominios de los atributos y de las clases deben ser discretos, algo que se cumple en nuestro conjunto de datos. Para elegir qué atributos y en qué orden aparecen en el árbol se utiliza una función de evaluación: minimización de la entropía. También es posible escribirlo en forma de reglas IF-THEN. La principal aplicación de este algoritmo es para los problemas de decisión. Su empleo se centra en los problemas de clasificación (diagnóstico de enfermedades dados unos síntomas, problemas de malfuncionamiento de equipos, concesión de préstamos, clasificación de un ser en una especie animal dadas unas características del mismo, etc.). La función de salida presentará valores discretos. Los datos de aprendizaje pueden contener errores, valores nulos en algún atributo para algún ejemplo. Nos saldrá un mejor árbol cuando los atributos tengan un dominio de valores reducido. Una vez aprendido el árbol, lo podremos emplear para clasificar nuevos casos. Las principales ventajas son que tiene buenos resultados en un amplio rango de aplicaciones y que presenta una precisión del resultado alta. Las desventajas más importantes son el hecho de que los atributos sean discretos y que a veces los árboles son demasiado frondosos, lo cual nos hace difícil su interpretación. Esta última desventaja, como veremos adelante, la tendremos en nuestro problema. La selección de los atributos se realizará mediante el principio de ganancia de la información. La ganancia de información es una propiedad estadística que nos sirve para medir cómo clasifica un atributo a los ejemplos. Se elige como nodo del árbol aquel que tenga una mayor ganancia de información. Posteriormente, expando sus ramas y sigo igual, pero considerando la nueva partición formada por el subconjunto de ejemplos que tienen ese valor para el atributo elegido. ! 32! ciclos dirigidos. La otra parte es cuantitativa, donde una serie de probabilidades condicionadas determinan una única distribución de probabilidad conjunta. En el grafo dirigido acíclico, se tiene que un nodo puede tener varios padres. Para representar la red bayesiana Naive, que será la representación gráfica de Naive Bayes, se tendrá un árbol de profundidad 1, donde el nodo raíz, será la probabilidad a priori (clase) y los nodos hijos serán las probabilidades a posteriori (la clase dado un atributo). Un ejemplo de red bayesiana Naive será de la forma que vemos en la figura 8: ! Figura 8: Red Bayesiana Naive y un ejemplo de red bayesiana, sin ser Naive, tiene la que vemos en la figura 9: ! 33! ! Figura 9: Red Bayesiana Las redes bayesianas están implementadas en Weka mediante el método BayesNet, que las utilizaremos posteriormente para realizar la comparación entre métodos. 3.4)LIBRERÍAS)EN)R)SOBRE)ÁRBOLES)DE)DECISIÓN)) En este apartado, vamos a hablar acerca de las distintas librerías que existen sobre árboles de decisión. En primer lugar, vamos a comentar la librería data.tree. Esta librería nos sirve para crear estructuras de árbol de datos jerárquicos y recorrer el árbol en varios ! 34! niveles. Esta librería es útil para árboles de decisión, aprendizaje automático, finanzas y otras muchas más aplicaciones. Entre sus funciones más destacadas tenemos Sort, Prune, Aggregate, Cumulate y print, que nos servirán para ordenar, podar o imprimir el árbol, entre otras. También presenta varias funciones de construcción y conversión. Esta librería se diferencia de las que vamos a comentar posteriormente en que no presenta un método para construir un árbol de decisión con un algoritmo ya construido, sino que es útil para crearlo desde cero. Este es uno de los motivos que decidirán a usar esta librería en el siguiente apartado. El paquete RPart fue descrito por Brieman, Friedman, Olshen y Stone, y se utiliza para árboles de clasificación y regresión(CART). Posiblemente, se trata del método más utilizado en R para árboles de decisión. Para ajustar árboles CART utilizaremos la siguiente expresión: rpart(y ~ x1 + x2 + … + xp, datos) donde y es la variable respuesta y x1, x2, …, xp son las variables predictoras. Si y es discreta la función ajusta un árbol de clasificación y si es continua un árbol de regresión. Como funciones dentro de esta librería vamos a destacar: predict, para realizar la predicción de un objeto de tipo RPart; print, imprime un objeto RPart; plotcp, da una representación visual de la cross-validation en un objeto RPart. Veamos un ejemplo con nuestro conjunto de datos. Pondríamos las siguientes instrucciones como se ve en la figura 10: ModeloArbol<-rpart(datos$CON_DIAGES ~ .,data=datos,parms=list(split="information")) > ModeloArbol Figura 10: Entrada para crear un árbol de decisión con RPart y nos devolvería el siguiente árbol como vemos en la figura 11. Cada línea representará un nodo y presenta varias datos como el número de nodo (node), el atributo que realiza la división (split), el número de elementos con estos valores (n), el número de errores cometidos (loss), la respuesta predicha en dicho nodo (yval), un vector con las probabilidades de cada valor de decisión (yprob). Si al final de una de las líneas tenemos un *, esto nos indicará que el nodo es terminal. n= 1000 node), split, n, loss, yval, (yprob) * denotes terminal node ! 35! 1) root 1000 680 -1 (0.32 0.027 0.058 0.011 0.007 0.11 0.21 0.19 0.02 0.004 0.036) 2) CLASSI_FIN=-1,2,8 332 13 -1 (0.96 0.003 0.006 0.003 0 0.003 0.018 0 0.003 0 0.003) * 3) CLASSI_FIN=1 668 461 6 (0.0015 0.039 0.084 0.015 0.01 0.17 0.31 0.29 0.028 0.006 0.052) 6) CLI_PETEQU=1 57 36 1 (0 0.37 0.18 0.12 0 0.053 0.18 0.053 0.018 0 0.035) * 7) CLI_PETEQU=0,2 611 414 6 (0.0016 0.0082 0.075 0.0049 0.011 0.18 0.32 0.31 0.029 0.0065 0.054) 14) CLI_COMA=0,1 100 73 6 (0.01 0.04 0.19 0.01 0.03 0.22 0.27 0.09 0.02 0.01 0.11) * 15) CLI_COMA=2 511 332 7 (0 0.002 0.053 0.0039 0.0078 0.17 0.33 0.35 0.031 0.0059 0.043) 30) CLI_RIGIDE=1 294 179 6 (0 0.0034 0.071 0.0068 0.014 0.18 0.39 0.27 0.027 0.0034 0.041) * 31) CLI_RIGIDE=0,2 217 116 7 (0 0 0.028 0 0 0.16 0.25 0.47 0.037 0.0092 0.046) 62) CLI_CEFALE=0 9 1 6 (0 0 0.11 0 0 0 0.89 0 0 0 0) * 63) CLI_CEFALE=1,2 208 107 7 (0 0 0.024 0 0 0.17 0.23 0.49 0.038 0.0096 0.048) * Figura 11: Salida de árbol de decisión con RPart También existe el paquete party que nos ofrece árboles de regresión no paramétricos para variables nominales, ordinales, numéricas, censuradas y respuestas multivariantes. Estos serán árboles basados en inferencia condicional, que será lo que diferencia este paquete del resto. En este paquete, podemos crear el árbol de clasificación o regresión, mediante la siguiente fórmula: ctree (formula= y ~ x1 + x2 + … + xp, datos) El tipo de árbol creado dependerá del tipo de la variable de salida(nominal, ordinal, numérico, etc.). El crecimiento del árbol estará basado con reglas estadísticas de parada, y podando cuando sea necesario. El paquete tree es otro paquete para la clasificación y regresión de árboles. La sentencia para crear el árbol sigue la misma estructura que en los paquetes anteriores: tree (y ~ x1 + x2 + … + xp, datos) ! 36! donde y es la variable respuesta y x1, x2, …, xp son las variables predictoras. Este paquete tiene una serie de funciones, entre las que destacamos las que se dedican a la predicción, como Predict, o las que nos muestran el árbol, como Plot o Print. A continuación, vamos a ver un ejemplo de esta librería con los datos que vamos a usar durante todo el trabajo. En la figura 12, vemos la entrada para crear un árbol con la librería tree: ModeloTree <- tree(datos$CON_DIAGES ~ ., datos) > ModeloTree Figura 12: Entrada para crear un árbol de decisión con la librería tree y nos devolverá lo que vemos en la figura 13. Cada línea representará un nodo y presenta varias datos como el número de nodo (node), el atributo que realiza la división (split), el número de elementos con estos valores (n), la desviación (deviance), la respuesta predicha en dicho nodo (yval), un vector con las probabilidades de cada valor de decisión (yprob). Si al final de una de las líneas tenemos un *, esto nos indicará que el nodo es terminal. node), split, n, deviance, yval, (yprob) * denotes terminal node 1) root 1000 3647.00 -1 ( 0.320000 0.027000 0.058000 0.011000 0.007000 0.113000 0.213000 0.191000 0.020000 0.004000 0.036000 ) 2) CLASSI_FIN: -1,2,8 332 152.10 -1 ( 0.960843 0.003012 0.006024 0.003012 0.000000 0.003012 0.018072 0.000000 0.003012 0.000000 0.003012 ) 4) CLASSI_FIN: -1,8 46 97.19 -1 ( 0.717391 0.021739 0.043478 0.021739 0.000000 0.021739 0.130435 0.000000 0.021739 0.000000 0.021739 ) * 5) CLASSI_FIN: 2 286 0.00 -1 ( 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 ) * 3) CLASSI_FIN: 1 668 2353.00 6 ( 0.001497 0.038922 0.083832 0.014970 0.010479 0.167665 0.309880 0.285928 0.028443 0.005988 0.052395 ) 6) CLI_PETEQU: 0,2 611 2018.00 6 ( 0.001637 0.008183 0.075286 0.004910 0.011457 0.178396 0.322422 0.307692 0.029460 0.006547 0.054010 ) ! 37! 12) CLI_COMA: 0,1 100 382.40 6 ( 0.010000 0.040000 0.190000 0.010000 0.030000 0.220000 0.270000 0.090000 0.020000 0.010000 0.110000 ) * 13) CLI_COMA: 2 511 1570.00 7 ( 0.000000 0.001957 0.052838 0.003914 0.007828 0.170254 0.332681 0.350294 0.031311 0.005871 0.043053 ) * 7) CLI_PETEQU: 1 57 197.70 1 ( 0.000000 0.368421 0.175439 0.122807 0.000000 0.052632 0.175439 0.052632 0.017544 0.000000 0.035088 ) * Figura 13: Salida de un árbol de decisión con la librería tree ! 38! ! ' ! 39! 4.'ALGORITMO'DE'CREACIÓN'DEL'ÁRBOL'DE'DECISIÓN' )))))4.1)INTRODUCCIÓN)Y)MOTIVACIÓN) En este apartado, vamos a hablar de uno de los principales objetivos de este trabajo de fin de grado, que va a ser la construcción de un algoritmo para crear un árbol de decisión, con ciertas características que vamos a comentar a continuación. )))))4.2)UTILIZACIÓN)DE)LA)LIBRERÍA)DATA.TREE) Después de buscar sobre la utilización acerca de las librerías existentes sobre árboles de decisión como RPart, Tree, Party, Partykit, MVPart, Data.Tree, hemos decidido que para crear un árbol desde cero como pretendemos realizar, vamos a usar la librería data.tree. Para poder utilizar esta librería, tenemos que instalarla en R y cargarla usando lo siguiente como veremos en la figura 14: install.packages("data.tree") library(data.tree) Figura 14: Instalación y carga del paquete data.tree )))))4.3)ALGORITMO)PARA)CREAR)EL)ÁRBOL)DE)DECISIÓN) Dado un conjunto de datos, que tendremos en una tabla descrita como explicamos en el apartado 2 del trabajo, y un conjunto de variables que nos permitirán decidir en cada momento que decisión tomar, será posible construir el árbol. Respecto a las variables, tendremos n variables, de las cuales n-1 serán explicativas y una será explicada. Esta variable explicada siempre la situaremos en última posición del conjunto, debido a que nos indicará la decisión a tomar. Para crear el árbol, partiremos del conjunto de datos y si tenemos en la primera variable del conjunto Variables, por ejemplo, CLI_CEFALE, que presenta valores 0,1,2, entonces dividiremos el conjunto en 3 diferentes, los que tienen CLI_CEFALE=0, CLI_CEFALE=1 y CLI_CEFALE=2, y en el árbol crearemos un nodo con cada opción. Una vez aquí, estudiaremos cada uno de los 3 conjuntos por ! 40! separado y seguiremos así recursivamente hasta llegar a la última variable del conjunto Variables. Tenemos que destacar que a diferencia de otros algoritmos de creación de árboles de decisión, en nuestro algoritmo no existe ningún criterio de parada y es por esto por lo que nos sale un árbol tan grande. Esta función tendrá atributos de entrada, que serán las siguientes: variables, que son las variables de creación para el árbol de decisión, data, que se refiere al conjunto de datos, donde tendremos a todos los pacientes con sus síntomas, y node, que será la raíz del árbol de decisión. Cuando queramos imprimir el árbol, utilizaremos la función Print de la librería data.tree. En la figura 15, veremos la instrucción para mostrar un árbol: print(tree, "feature", "obsCount", "porcentaje") Figura 15: Función para imprimir un árbol que nos mostrará la estructura del árbol con su raíz, sus nodos y sus hijos. A la derecha, nos indicará el nombre de la variable del nodo a la que se refiera, el número de observaciones y el porcentaje de las observaciones de ese tipo con respecto al total de observaciones del nodo padre. En la figura 16, veremos el código para crear el árbol: #Creamos el arbol de decision #En variables, introduciremos las variables para crear el arbol, la última #que pongamos sera la que nos diga el diagnostico arbolDecMarcos <- function(variables, data, node) { long <- length(variables) node$obsCount <- nrow(data) node$feature <- variables[1] #Estudiamos primero el caso en que el numero de variables de los datos #sea mayor que 0 if(length(names(data))>0) { #Dividimos en subconjuntos que tengan por ejemplo CLI_CEFALE=1 childObs <- split(data[,!(names(data) %in% variables[1])], data[,variables[1]], drop=TRUE) for(i in 1:length(childObs)) { ! 41! #Construimos un hijo que tenga el nombre del valor de la #caracteristica child <- node$AddChild(names(childObs)[i]) #Llama al algoritmo recursivamente en el hijo y el subconjunto varNueva <- variables[-1] if(length(varNueva)!=0) { datosNew <- childObs[[i]] child$porcentaje <- (nrow(childObs[[i]])*100)/nrow(data) arbolDecMarcos(varNueva, datosNew, child) } else { child$obsCount <- nrow(childObs[[i]]) child$porcentaje <- (nrow(childObs[[i]])*100)/nrow(data) } } } #Estudiamos primero el caso en que el número de variables de los datos #sea 0. Diferenciamos porque el tipo de datos aqui no sera una tabla, #sino un vector else { node$obsCount <- length(data) node$porcentaje <-((length(data))*100) /(node$parent$obsCount) childObs <- sort(unique(data)) for(i in 1:length(childObs)) { child <-node$AddChild(childObs[i]) cont <- 0 for(j in 1:length(data)) { if (childObs[i]== data[j]) { cont <- cont +1 } } ! 48! 77 ¦ ¦ ¦ °--6 1 25.000000 78 ¦ ¦ °--2 CLI_CONVUL 18 26.086957 79 ¦ ¦ ¦--1 CLI_RIGIDE 8 44.444444 80 ¦ ¦ ¦ ¦--0 CON_DIAGES 1 12.500000 81 ¦ ¦ ¦ ¦ °--1 1 100.000000 82 ¦ ¦ ¦ ¦--1 CON_DIAGES 2 25.000000 83 ¦ ¦ ¦ ¦ ¦--5 1 50.000000 84 ¦ ¦ ¦ ¦ °--6 1 50.000000 85 ¦ ¦ ¦ °--2 CON_DIAGES 5 62.500000 86 ¦ ¦ ¦ ¦---1 3 60.000000 87 ¦ ¦ ¦ °--6 2 40.000000 88 ¦ ¦ °--2 CLI_RIGIDE 10 55.555556 89 ¦ ¦ ¦--0 CON_DIAGES 1 10.000000 90 ¦ ¦ ¦ °---1 1 100.000000 91 ¦ ¦ ¦--1 CON_DIAGES 4 40.000000 92 ¦ ¦ ¦ ¦---1 2 50.000000 93 ¦ ¦ ¦ °--5 2 50.000000 94 ¦ ¦ °--2 CON_DIAGES 5 50.000000 95 ¦ ¦ ¦---1 2 40.000000 96 ¦ ¦ ¦--1 1 20.000000 97 ¦ ¦ ¦--2 1 20.000000 98 ¦ ¦ °--8 1 20.000000 99 ¦ °--2 CLI_VOMITO 7 6.194690 100 ¦ °--... 2 nodes w/ 17 sub NA NA 101 °--... 2 nodes w/ 310 sub NA NA Figura 20: Árbol de decisión con 6 variables Cabe reseñar que para representar gráficamente el árbol, podríamos haber utilizado la función plot, también de la librería data.tree. Pero después de probarlo, desechamos esta opción, ya que debido al gran tamaño del árbol, la representación gráfica es aún peor y es imposible ver nada, ni siquiera si hacemos zoom en la imagen del árbol. ! 49! ! Figura 21: Representación gráfica del árbol con 6 variables! ! 50! ! ' ! 51! 5.'VALIDACIÓN'DE'RESULTADOS'OBTENIDOS'CON'EL'ÁRBOL'DE' DECISIÓN' 5.1)FUNCIÓN)DE)PREDICCIÓN)DEL)MÁXIMO)VALOR) La predicción en un árbol de decisión consistirá en comprobar si el valor real de un diagnóstico de un paciente coincide con el valor predicho por el árbol de decisión. Por tanto, para realizar la validación de los obtenidos con el árbol de decisión construiremos una función de predicción. La función de predicción consistirá en ir recorriendo los distintos niveles del árbol para finalmente llegar al valor predicho o al diagnóstico predicho por el árbol. Una vez aquí, comprobaremos si coincide el valor predicho por el árbol y el valor real que tendremos en el conjunto de datos. La función de predicción, que llamaremos PredictMaxVal, tendrá 2 atributos de entrada. Estos serán tree, que es el árbol de decisión que hemos construido anteriormente, y features, que serán las características de un individuo en cuestión. Esta función nos devolverá el valor predicho por el árbol y en el caso de que el árbol nos prediga más de un valor, devolveremos el valor que presente más observaciones. En la figura 22, vemos el código de esta función de predicción: #Funcion de prediccion, poniendo como parametros, el arbol y las #caracteristicas de decision PredictMaxVal <- function(tree, features) { #Estudiamos el caso en que el nodo sea raiz if (tree$children[[1]]$isLeaf) { num<- tree$count max<- 1 #Elegimos el nodo que más observaciones tenga for(j in 1:num) { if(tree$children[[max]]$obsCount < tree$children[[j]]$obsCount) { max <- j } } ! 52! #Devolvemos el nombre del nodo que mas observaciones tenga return (tree$children[[max]]$name) } caract<-names(tree$children)[1] for(i in 1:tree$count){ if(features[[tree$feature]]==names(tree$children)[i]) caract<- names(tree$children)[i] } child <- tree$children[[caract]] return (PredictMaxVal(child, features)) } Figura 22: Código de la función de predicción del máximo valor Veamos un ejemplo de uso para el primer árbol construido en el apartado anterior. Se introduce por pantalla lo que vemos en la figura 23: features <- c(CLI_CEFALE='1', CLI_FEBRE='1', CLI_VOMITO='1', CLI_CONVUL='2', + CLI_RIGIDE='1', CLI_KERNIG='2', CLI_ABAULA='2', CLI_COMA='2', + CLI_PETEQU='2', CLASSI_FIN='1' ) > PredictMaxVal(tree,features) Figura 23: Entrada de un ejemplo de la función de predicción del máximo valor y nos devolverá lo que vemos en la figura 24: [1] "6" Figura 24: Salida de un ejemplo de la función de predicción del máximo valor Esta función de predicción tiene el gran inconveniente de que cuando el árbol nos dé más de un valor para diagnóstico, como hemos puesto la condición de que nos devuelva el valor con mayor número de observaciones, el resto de valores bien predichos realmente no los devolverá como bien predichos.! ! 53! 5.2)FUNCIÓN)DE)PREDICCIÓN)DE)TODAS)LAS)OPCIONES) La principal motivación de este apartado es corregir un inconveniente que tiene la anterior función de predicción. Este inconveniente es debido a que hay un gran número de casos en que árbol predice bien, pero la función de predicción nos dirá lo contrario. Esto ocurrirá cuando para un conjunto de datos de un paciente, el árbol nos devuelva más de un valor. Para cuando el árbol nos devuelva varios valores, la anterior función de predicción nos devolvía el valor con mayor número de observaciones, pero el resto no es contemplado. Debido a esto, pensamos en la idea de crear una nueva función de predicción de la misma forma que la anterior, pero en vez de devolver el valor con mayor número de observaciones, que nos dé como salida con conjunto con todos los valores predichos. A esta función de predicción, la llamaremos PredictAllOptions, ya que contemplará todas las opciones que nos dé el árbol de decisión. Esta función tendrá dos parámetros de entrada como son: tree, que es el árbol de decisión ya obtenido anteriormente, y features, que son las características de un paciente en cuestión. Esta función funcionará igual que la anterior con la diferencia de que iremos construyendo un conjunto con todos los valores predichos por el árbol. Este conjunto será la salida de la función. A continuación, vemos en la figura 25 el código de esta nueva función de predicción: #Funcion de prediccion(cogiendo todas las posibles opciones), poniendo como #parametros, el arbol y las caracteristicas de decision PredictAllOptions <- function(tree, features) { if (tree$children[[1]]$isLeaf) { num<- tree$count conj <- c() #Creamos un conjunto con las observaciones que haya en el arbol para la #tupla dada for(j in 1:num) { conj <- c(conj, tree$children[[j]]$name) } #Devolvemos el vector con los nombres de los nodos ! 54! return (conj) } #Tomamos como arbol, el hijo, por ejemplo el que sea CLI_CEFALE=1 y hacemos #recursividad caract<-names(tree$children)[1] for(i in 1:tree$count){ if(features[[tree$feature]]==names(tree$children)[i]) caract<- names(tree$children)[i] } child <- tree$children[[caract]] return (PredictAllOptions(child, features)) } Figura 25: Código de la función de predicción de todas las opciones Veamos a continuación un ejemplo de uso de la función para el árbol construido en el apartado anterior. Se introduce por pantalla como se ve en la figura 26: features <- c(CLI_CEFALE='1', CLI_FEBRE='1', CLI_VOMITO='1', CLI_CONVUL='2', + CLI_RIGIDE='1', CLI_KERNIG='2', CLI_ABAULA='2', CLI_COMA='2', + CLI_PETEQU='2', CLASSI_FIN='1' ) > PredictAllOptions(tree,features) Figura 26: Entrada de un ejemplo de la función de predicción de todas las opciones y nos devolverá lo siguiente como vemos en la figura 27: [1] "1" "2" "4" "5" "6" "7" "8" "10" Figura 27: Salida de un ejemplo de la función de predicción de todas las opciones Esta función de predicción a simple vista no presenta ningún inconveniente, pero una vez que pasemos a la validación cruzada, comprobaremos que no es posible obtener una matriz de confusión. Esto se debe a que como obtenemos un vector con ! 55! los valores que predice el árbol, el cual es posible que tenga más de un valor. Como es posible que el vector tenga más de un valor predicho, no tiene sentido construir una matriz de confusión, lo cual nos dificultaría la comparación con otros métodos. Únicamente, como veremos en los próximos apartados, podremos sacar el porcentaje de acierto y de fallo. 5.3)INTRODUCCIÓN)AL)CONCEPTO)DE)VALIDACIÓN)CRUZADA) La validación cruzada o cross-validation se trata de una técnica utilizada para evaluar los resultados de un análisis estadístico y garantizar que son independientes de la partición entre datos de entrenamiento y prueba. Esta técnica consiste en repetir y calcular la media aritmética obtenida de las medidas de evaluación sobre diferentes particiones. Se utiliza en entornos donde el objetivo principal es la predicción y se quiere estimar como de preciso es un modelo que se llevará a cabo en la práctica. Es una técnica muy utilizada en proyectos relacionados con la inteligencia artificial para validar modelos generados. A continuación, vemos en la figura 28 un ejemplo de cross-validation con k=4: ! 56! ! Figura 28: Proceso de cross-validation para k=4 La validación cruzada tiene su origen en el método de retención. El método de retención consiste en dividir en dos conjuntos complementarios los datos de la muestra, realizar el análisis de un subconjunto(llamado datos de entrenamiento), y validar el análisis en el otro subconjunto(llamado datos de prueba). De esta forma, la función de aproximación sólo se ajusta con el conjunto de datos de entrenamiento y a partir de aquí calcula los valores de salida para el conjunto de datos de prueba. Este método realiza únicamente una iteración, con lo cual es muy rápido respecto a la computación. Pero tiene el inconveniente de que no es demasiado preciso debido a la variación de los resultados obtenidos para diferentes datos de entrenamiento. Aquí en la figura 29, vemos una representación gráfica de este método. ! 57! Figura 29: Método de retención Como consecuencia de los inconvenientes del método de retención surge la validación cruzada o cross-validation. Existen varios tipos de validaciones cruzadas como la validación cruzada de K iteraciones, la validación cruzada aleatoria o la validación cruzada dejando uno fuera, pero nos vamos a centrar en la validación cruzada de K iteraciones o K-fold crossvalidation, que será la que vamos a utilizar. Esta técnica consiste en dividir los datos en varios conjuntos de datos y luego elegir uno de ellos para “testear” y el resto para entrenar el árbol de decisión. Esto se hace de forma repetida hasta “testear” con cada conjunto de datos, guardando el resultado de cada iteración en una tabla para luego analizar la eficiencia de la predicción. Este método es bastante preciso ya que evaluamos a partir de K combinaciones de datos de entrenamiento y de prueba, aunque presenta la desventaja de ser computacionalmente lento. En la práctica, la elección del número de iteraciones depende de la medida del conjunto de datos, aunque la más usada habitualmente es la 10-fold cross-validation (k=10). En la figura 30, vemos un ejemplo de validación cruzada con k=4. ! 64! [28] 5 6 2 -1 7 7 7 6 2 6 7 7 7 -1 7 6 6 6 7 6 7 6 - 1 -1 -1 1 7 [55] 6 7 -1 -1 7 1 1 -1 6 -1 -1 -1 6 -1 -1 -1 7 6 -1 1 7 -1 7 7 3 7 5 [82] 7 1 7 7 6 7 2 3 -1 7 7 -1 7 -1 -1 -1 7 7 9 1 6 7 7 -1 7 5 6 [109] 6 1 6 -1 5 2 -1 -1 5 -1 6 7 7 5 6 6 -1 -1 -1 2 6 7 - 1 6 6 -1 7 [136] 6 7 4 5 6 5 7 7 7 7 5 7 7 7 5 5 6 5 7 7 7 7 6 7 6 7 5 [163] 7 7 5 7 7 6 7 6 6 7 5 6 7 8 7 5 7 6 6 7 5 5 7 7 7 7 6 [190] 7 7 6 7 5 7 7 7 7 6 7 7 6 5 -1 6 6 7 5 6 5 -1 - 1 6 -1 -1 6 [217] 6 6 7 6 6 6 6 7 -1 7 6 -1 6 2 7 7 6 6 2 6 7 -1 6 6 6 6 6 [244] -1 6 6 -1 5 -1 -1 4 6 5 6 6 -1 6 6 -1 7 7 6 7 8 6 - 1 5 8 -1 5 [271] 6 6 6 6 6 7 6 6 6 5 6 -1 6 7 6 -1 6 -1 6 1 6 7 - 1 6 5 5 6 [298] 7 6 -1 6 5 -1 1 6 5 6 -1 -1 6 7 6 7 -1 6 -1 6 6 -1 - 1 1 6 6 2 [325] 6 6 7 5 6 1 1 6 2 7 7 6 5 2 7 6 6 6 -1 6 6 5 8 6 6 -1 -1 [352] 6 3 6 -1 5 -1 -1 -1 2 -1 6 -1 6 6 1 7 8 6 7 7 6 -1 - 1 1 -1 -1 -1 [379] -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 10 5 5 1 10 5 1 -1 7 -1 5 -1 6 5 6 [406] 6 6 7 6 7 6 5 -1 6 -1 5 7 6 7 6 6 7 -1 -1 6 7 -1 7 6 -1 6 6 [433] 6 7 6 -1 7 5 5 4 1 7 2 7 -1 7 10 5 6 6 6 7 6 6 6 7 -1 6 6 [460] -1 -1 7 1 5 6 6 7 -1 2 6 -1 6 6 -1 6 7 7 6 7 6 6 6 6 6 6 5 [487] 5 -1 5 6 5 7 -1 5 -1 -1 -1 1 6 7 7 7 6 -1 -1 6 5 6 2 10 7 6 6 [514] 6 4 -1 6 7 6 6 6 6 6 6 2 7 7 7 7 2 -1 6 10 6 -1 - 1 7 -1 6 7 ! 65! [541] 5 6 7 -1 -1 3 -1 6 -1 5 7 -1 7 6 6 -1 -1 1 -1 -1 6 -1 7 -1 6 7 6 [568] 7 3 6 6 6 6 6 6 2 6 -1 6 7 6 6 7 -1 6 1 7 -1 6 6 -1 6 5 6 [595] 7 6 -1 6 6 4 7 -1 -1 6 -1 7 -1 6 -1 -1 6 6 -1 7 7 -1 2 7 6 7 6 [622] -1 2 6 -1 7 7 5 7 7 -1 6 -1 -1 10 -1 -1 -1 2 6 -1 6 6 7 7 -1 -1 -1 [649] -1 -1 6 7 6 -1 -1 -1 -1 2 1 2 -1 7 -1 6 6 7 -1 6 2 6 - 1 -1 7 -1 7 [676] 5 7 10 -1 -1 6 -1 4 -1 -1 -1 7 4 -1 7 -1 -1 -1 6 2 6 6 7 6 -1 -1 6 [703] -1 6 7 6 10 7 2 7 6 7 -1 7 7 2 3 -1 6 -1 3 6 -1 6 6 -1 6 5 -1 [730] 7 2 -1 -1 -1 7 6 6 6 6 -1 -1 7 5 10 6 5 7 -1 6 2 -1 6 7 6 -1 -1 [757] 7 -1 5 7 -1 7 7 6 -1 7 -1 3 3 -1 1 7 6 6 6 7 7 6 7 -1 6 7 -1 [784] 7 6 6 -1 -1 7 7 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 7 4 -1 5 -1 6 6 5 -1 -1 [811] 6 -1 -1 6 -1 -1 6 -1 -1 6 6 7 6 -1 6 6 10 7 1 6 6 5 2 1 6 6 6 [838] 7 -1 1 10 2 -1 -1 6 6 7 6 7 6 6 6 6 -1 6 6 -1 2 6 6 -1 -1 -1 5 [865] -1 6 7 -1 5 6 -1 -1 -1 6 2 7 10 -1 -1 2 5 2 6 -1 -1 6 - 1 6 6 2 -1 [892] 6 -1 -1 6 -1 2 2 -1 5 6 6 7 6 -1 7 6 6 5 -1 6 5 6 6 6 7 5 7 [919] -1 -1 6 -1 7 7 6 6 7 -1 6 7 -1 6 -1 -1 -1 6 6 -1 6 -1 - 1 2 7 -1 -1 [946] -1 7 6 -1 6 6 7 -1 -1 -1 -1 6 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 - 1 -1 -1 -1 2 [973] -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 6 -1 6 1 -1 -1 -1 -1 7 -1 6 -1 -1 -1 1 [1000] -1 Figura 33: Salida de un ejemplo de la función de cross-validation del máximo valor! ! 66! 5.5)VALIDACIÓN)CRUZADA)PARA)FUNCIÓN)DE)PREDICCIÓN)DE)TODAS)LAS) OPCIONES) La siguiente función realizamos el proceso de validación cruzada para la segunda función de predicción construida. Obtendremos un árbol de decisión para cada iteración y con estos árboles realizaremos la predicción. Una vez realizada la predicción, sacaremos el porcentaje de acierto y de fallo del método, y la matriz de confusión que emplearemos para comparar con los otros algoritmos ya existentes. En este caso, la función de predicción que utilizaremos será PredictAllOptions. A esta función que llamaremos CrossValAllOptions, le pasaremos 3 atributos de entrada. Estos serán: kfolds, que será el número de iteraciones que realizaremos en la cross-validation; datos, que será el conjunto de datos de ejemplos, que para nuestro caso serán los pacientes; variables, que serán las variables utilizadas para la construcción del árbol en cada nivel. Como salida, vamos a obtener varios resultados como el vector de acierto, con los porcentajes de acierto del árbol en cada iteración, el porcentaje total de acierto y el porcentaje de fallo. El código de esta función lo tenemos representado en la figura 34. CrossValAllOptions <- function(kfolds, datos, variables) { len <- length(variables) tamMuestra <- nrow(datos)/kfolds probs <- c() for(i in 1:kfolds) { conj <- ((tamMuestra*(i-1))+1):(tamMuestra*(i)) #Tomamos un conjunto de entrenamiento train <- datos[-conj, ] #Creamos el arbol tree <- Node$new("enfermedad") arbolDecMarcos(variables, train, tree) contador <- 0 for (j in conj) { #Obtenemos un vector de los datos predichos val <- PredictAllOptions(tree,datos[j,]) ! 67! #Vemos si el valor del conjunto de datos está en el vector de los datos predichos if(datos[j, variables[len]] %in% val) { contador <- contador +1 } } probs <- c(probs, contador) } #Devolvemos un vector de probabilidades vect<- probs/tamMuestra print(vect) print("Porcentaje de acierto: ") print(sum(vect)*10) print("Porcentaje de fallo: ") print(100- (sum(vect)*10)) } Figura 34: Función de cross-validation para la función de predicción de todas las opciones Ahora, vamos a ver un ejemplo de uso de esta función. En este caso, introduciremos por pantalla lo que tenemos en la figura 35. variables <- c("CLI_CEFALE", "CLI_FEBRE", "CLI_VOMITO", "CLI_CONVUL", + "CLI_RIGIDE", "CLI_KERNIG", "CLI_ABAULA", "CLI_COMA", + "CLI_PETEQU", "CLASSI_FIN", "CON_DIAGES") > kfolds <- 10 > CrossValAllOptions(kfolds, datos, variables) Figura 35: Entrada de un ejemplo de la función de cross-validation de todas las opciones y obtendremos como salida lo que vemos en la figura 36. [1] 0.70 0.77 0.67 0.68 0.54 0.72 0.61 0.63 0.50 0.75 [1] "Porcentaje de acierto: " ! 68! [1] 65.7 [1] "Porcentaje de fallo: " [1] 34.3 Figura 36: Salida de un ejemplo de la función de cross-validation de todas las opciones Con esta función, como vemos no es posible obtener la matriz de confusión, con lo que no será posible poder realizar comparaciones con los resultados de otros algoritmos sobre árboles de decisión. ! ' ! 69! 6.'COMPARACIÓN'DE'RESULTADOS' 6.1)INTRODUCCIÓN)) El objetivo de este apartado será realizar una comparación de los resultados obtenidos con nuestro árbol de decisión relacionados con la predicción, con los resultados que se obtienen con otros métodos que ya existen. Para obtener los resultados que compararemos, realizaremos una función en R que nos devolverá ciertos resultados. Mientras que con los otros métodos ya existentes, utilizaremos la herramienta Weka, debido a que la forma en que nos devuelve los resultados es más comprensible para el usuario y para poder comparar mejor resultados. 6.2)VARIABLES)NECESARIAS)PARA)LA)COMPARACIÓN)DE)RESULTADOS) Para la comparación de resultados hemos seleccionado varias variables, para las cuales realizaremos una función que la calcule. Definiremos estas variables orientándolas a nuestro problema. Antes de definir estas variables, vamos a considerar un problema de predicción binario, ya que tomaremos un síntoma de un individuo y veremos si ese síntoma se da realmente o no. Estos resultados lo clasificaremos como positivos(P) o negativos(N). Ahora vamos a considerar 4 casos resultantes de las combinaciones entre los valores reales y predichos, que como hemos comentado, se han clasificado como P o N: • Si el valor real es P y el valor predicho es P, tendremos un verdadero positivo. • Si el valor real es P y el valor predicho es N, tendremos un falso negativo. • Si el valor real es N y el valor predicho es P, tendremos un falso positivo. • Si el valor real es N y el valor predicho es N, tendremos un verdadero negativo. Estos cuatro valores lo podemos expresar en una matriz de confusión 2x2 como vemos en la figura 37: ! 70! ! Figura 37: Matriz de confusión 2x2 Estos 4 valores serán utilizados en el cálculo de las variables que veremos a continuación. La sensibilidad es la probabilidad de clasificar correctamente a un individuo con un síntoma, es decir, la probabilidad de que para un sujeto con un síntoma se obtenga en la prueba un resultado positivo. La sensibilidad se trata, por tanto, de la capacidad del test para detectar la enfermedad. También es conocida como fracción de verdaderos positivos. Utilizaremos la fórmula siguiente: 𝑆𝑒𝑛𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑 =7 𝑉𝑃 𝑉𝑃 +𝐹𝑁 La especificidad es la probabilidad de clasificar correctamente a un individuo que no tenga un determinado síntoma, es decir, la probabilidad de que para un sujeto sin un síntoma se obtenga un resultado negativo. También es posible definirla como la capacidad de detectar a los pacientes sanos. Es posible llamarla también fracción de verdaderos negativos. Para calcular la especificidad, haremos uso de la siguiente fórmula: 𝐸𝑠𝑝𝑒𝑐𝑖𝑓𝑖𝑐𝑖𝑑𝑎𝑑 =7 𝑉𝑁 𝑉𝑁 + 𝐹𝑃 La razón de falsos positivos vendrá dada por: 𝑅𝑎𝑧ó𝑛7𝑑𝑒7𝐹𝑎𝑙𝑠𝑜𝑠7𝑃𝑜𝑠𝑖𝑡𝑖𝑣𝑜𝑠 =7 𝐹𝑃 𝑉𝑁 +𝐹𝑃 La exactitud (accuracy) nos indicará el porcentaje de individuos que está bien clasificado. 𝐸𝑥𝑎𝑐𝑡𝑖𝑡𝑢𝑑 =7 𝑉𝑃 +𝑉𝑁 𝑇𝑜𝑡𝑎𝑙7𝑑𝑒7𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑜𝑠 La precisión o valor predictivo positivo nos indicará la probabilidad de tener el síntoma si el resultado de la prueba es positivo. 𝑃𝑟𝑒𝑐𝑖𝑠𝑖ó𝑛 =7 𝑉𝑃 𝑉𝑃 +𝐹𝑃 ! 71! En R, hemos creado una función que nos calcula estos valores, que será la que vemos en la figura 38: DerivadosMatConfusion <- function(mat) { sens <- c() razonFP <- c() accuracy <- c() especificidad <- c() precision <- c() for(i in 1:nrow(mat)) { vp <- VerdaderosPositivos(mat,i) fn <- FalsosNegativos(mat,i) vn <- VerdaderosNegativos(mat,i) fp <- FalsosPositivos(mat,i) sensi <- vp/(vp+fn) preci <- vp/(vp+fp) sens <- c(sens, sensi) razonFP <- c(razonFP, fp/(fp+vn)) accuracy <- c(accuracy, (vp+vn)/(vp+vn+fp+fn)) especificidad <- c(especificidad, 1- (fp/(fp+vn))) precision <- c(precision, preci) ##rMeasure <- c(rMeasure, (2*sensi*preci)/(sensi+preci)) } print("Sensibilidad") print(sens) print("Razon de falsos positivos") print(razonFP) print("Accuracy") print(accuracy) print("Especificidad") print(especificidad) print("Precision") ! 72! print(precision) ##print("R-Measure") ##print(rMeasure) } Figura 38: Función que calcula valores para comparar con otros métodos A esta función le pasaremos una matriz de confusión, y nos devolverá los valores de las variables comentados anteriormente. Para nuestro caso, la matriz de confusión será la obtenida mediante la validación cruzada. Finalmente, vamos a hablar sobre la curva ROC. Una curva ROC (Receiver Operating Characteristic, o Característica Operativa del Receptor) es una representación gráfica de la sensibilidad frente a la especificidad para un sistema clasificador binario según se varía el umbral de discriminación. Ha tenido un gran desarrollo en los últimos año en el proceso diagnóstico. Es muy útil para test con datos cuantitativos. Tradicionalmente, cuando se tenía un test cuantitativo, se elegía el mejor punto de corte, que combinaba la mejor sensibilidad y especificidad del test (mayor rendimiento). Con esto, teníamos una pérdida de información, cuando transformábamos una variable continua en una dicotómica. Ahora con las curvas ROC, podemos graficar los diferentes puntos de corte de las características operativas del test, es decir, la sensibilidad y la especificidad. El gráfico será una relación entre los verdaderos positivos (VP) y los falsos positivos (FP). En el eje Y, tendremos la sensibilidad, mientras que en el X, tendremos el valor de 1-especificidad. Esta curva nos va a ser muy útil porque nos da una idea del rendimiento del test. Veamos en la figura 39, un ejemplo de un gráfico de la curva ROC: ! 73! ! Figura 39: Gráfico de la curva ROC Un dato que será muy útil, que será el que nos servirá para la comparación, va a ser el área bajo la curva. A mayor valor, mejor es el test. Veamos algunos valores: • Máximo 1 -> Test perfecto • Mayor de 0.9 -> Excelente test • 0.8 a 0.9 -> Buen test • 0.7 a 0.8 -> Regular test • 0.5 a 0.7 -> Mal test • 0.5 -> No relación • Menor de 0.5 -> Relación inversa ! 80! resumen, la idea sería construir una función de predicción que unificara la idea de ambas funciones de predicción. También estaría interesante incorporar alguna función más a la API, sobre todo orientada a la fase de preprocesamiento de los datos. ' ' ! 81! Bibliografía' 1. Documentación y descarga de RProject. Disponible en:!http://www.rproject.org 2. ZUUR, A.; IENO, E.N.; MEESTERS, E. (2009). A Beginner's Guide to R. Springer. 3. Documentación y descarga de Weka. Disponible en: http://www.cs.waikato.ac.nz/~ml/weka/ 4. ALER, R. (2010). Tutorial sobre Weka. Curso Herramientas de la inteligencia artificial. [Consultado en Septiembre 2016]. Disponible en: http://ocw.uc3m.es/ingenieria-informatica/herramientas-de-la-inteligenciaartificial/contenidos/transparencias/TutorialWeka.pdf/view 5. SANTANA, J.S; MATEOS, E. (2014). El arte de programar en R: un lenguaje para la estadística. Instituto Mexicano de Tecnología del Agua. 6. MITCHELL, T. (1997). Machine Learning. McGraw-Hill. 7. MURPHY, K.P.; Machine learning : a probabilistic perspective. Cambridge, 1970 8. RIPLEY, B. (2015). Documentación del paquete "rpart". [Consultado en Septiembre 2016]. Disponible en: https://cran.rproject.org/web/packages/rpart/index.html 9. RIPLEY, B. (2016). Documentación del paquete "tree". [Consultado en Septiembre 2016]. Disponible en: https://cran.rproject.org/web/packages/tree/index.html ,!