viernes, 1 de mayo de 2009

Árboles de decisión

Un árbol de decisión es un modelo de predicción utilizado en el ámbito de la inteligencia artificial. Dada una base de datos se construyen diagramas de construcción lógicas, muy similares a los sistemas de predicción basados en reglas, que sirven para representar y categorizar una serie de condiciones que ocurren de forma sucesiva, para la resolución de un problema. Un árbol de decisión tiene unas entradas las cuales pueden ser un objeto o una situación descrita por medio de un conjunto de atributos y a partir de esto devuelve una respuesta la cual en último término es una decisión que es tomada a partir de las entradas. Los valores que pueden tomar las entradas y las salidas pueden ser valores discretos o continuos. Se utilizan más los valores discretos por simplicidad, cuando se utilizan valores discretos en las funciones de una aplicación se denomina clasificación y cuando se utilizan los continuos se denomina regresión.

Un árbol de decisión lleva a cabo una prueba a medida que este se recorre hacia las hojas para alcanzar así una decisión. El árbol de decisión suele contener nodos internos, nodos de probabilidad, nodos hojas y arcos. Un nodo interno contiene una prueba sobre algún valor de una de las propiedades. Un nodo de probabilidad indica que debe ocurrir un evento aleatorio de acuerdo a la naturaleza del problema, este tipo de nodos es redondo, los demás son cuadrados. Un nodo hoja representa el valor que devolverá el árbol de decisión y finalmente las ramas brindan los posibles caminos que se tienen de acuerdo con la decisión tomada.

Los árboles de decisión son herramientas excelentes como ayuda para realizar elecciones adecuadas entre muchas posibilidades. Su estructura permite seleccionar una y otra vez diferentes opciones para explorar las diferentes alternativas posibles de decisión. Los árboles de decisión son guías jerárquicas multi-vía donde los valores de las características son el criterio diagnostico para evaluar la calidad de la solución y determinar el uso más apropiado. La jerarquía se refiere a que la toma de una decisión o camino lleva a otra, hasta que todos los factores o características involucradas se hayan tomado en cuenta. Es multi-vía porque pueden existir más de dos opciones y es una guía porque al responder una pregunta se llega a una decisión.

El uso de árboles de decisión tuvo su origen en las ciencias sociales con los trabajos de Sonquist y Morgan el año 1964 y Morgan y Messenger el año 1979, ambos realizados en la Universidad de Michigan. El programa para la “Detección de Interacciones Automáticas”, creada el año 1971 por los investigadores Sonquist, Baker y Morgan, fue uno de los primeros métodos de ajuste de los datos basados en árboles de clasificación. En estadística, el año 1980, Kass introdujo un algoritmo recursivo de clasificación no binario, llamado “Detección de Interacciones Automáticas Chi-cuadrado”. Hacia el año 1984, los investigadores Breiman, Friedman, Olshen y Stone, introdujeron un nuevo algoritmo para la construcción de árboles y los aplicaron a problemas de regresión y clasificación. El método es conocido como “Árboles de clasificación y regresión”. Casi al mismo tiempo el proceso de inducción mediante árboles de decisión comenzó a ser usado por la comunidad de “Aprendizaje automático”.

El término árboles es por la apariencia de la gráfica asociada, que se asemeja a un árbol con las raíces en la parte superior creciendo hacia la parte inferior. La raíz es el nodo superior, en cada nodo se hace una partición hasta llegar a un nodo terminal u hoja. Cada nodo no-terminal contiene una pregunta en la cual se basa la división del nodo. Cada nodo terminal contiene, en el caso de árboles de regresión, el valor de la variable de respuesta o para árboles para clasificación, el nombre de la clase a la cual pertenece. La construcción de un árbol de decisión se basa en cuatro elementos: (1) Un conjunto de preguntas binarias. (2) El método usado para particionar los nodos. (3) La estrategia requerida para detener el crecimiento del árbol. (4) La asignación de cada nodo terminal a un valor de la variable de respuesta o a una clase. Las diferencias principales entre los algoritmos para construir árboles se hallan en la estrategia para podar los árboles, la regla para particionar los nodos y el tratamiento de los valores perdidos.

Los árboles de decisión son una manera de representar una serie de reglas que culminan en una clase o valor. Los modelos de árboles de decisión son comúnmente usados en la minería de datos para examinar los datos e inducir las reglas para realizar predicciones. Los árboles de decisión crecen a través de una división iterativa de grupos discretos, donde la meta es maximizar la “distancia” entre grupos por cada división. Una de las distinciones entre los diferentes métodos de “división” es la manera en la que miden esta distancia. Se puede pensar que cada división de los datos en nuevos grupos debe ser diferente uno de otro tanto como sea posible. Esto también se denomina “purificación” de grupos. Los árboles de decisión que se utilizan para predecir variables categóricas son llamados árboles de clasificación, y los árboles usados para predecir variables continuas son llamados árboles de regresión. Los árboles de decisión manejan datos no numéricos de manera bastante conveniente. La habilidad para aceptar datos categóricos minimiza la cantidad de transformaciones en los datos y la explosión de variables de predicción inherentes en las redes neuronales. Algunos árboles de clasificación fueron diseñados, y de hecho trabajan mejor cuando las variables de predicción también son categóricas.

En términos técnicos, un árbol de decisión es un diagrama que representa en forma secuencial condiciones y acciones; muestra qué condiciones se consideran en primer lugar, en segundo lugar y así sucesivamente. Este método permite mostrar la relación que existe entre cada condición y el grupo de acciones permisibles asociado con ella. Un árbol de decisión sirve para modelar funciones discretas, en las que el objetivo es determinar el valor combinado de un conjunto de variables, y basándose en el valor de cada una de ellas, determinar la acción a ser tomada. Los árboles de decisión son normalmente construidos a partir de la descripción de la narrativa de un problema. Ellos proporcionan una visión gráfica de la toma de decisión necesaria, especifican las variables que son evaluadas, qué acciones deben ser tomadas y el orden en el cual la toma de decisión será efectuada. Cada vez que se ejecuta un árbol de decisión, solo un camino será seguido dependiendo del valor actual de la variable evaluada. Se recomienda el uso del árbol de decisión cuando el número de acciones es pequeño y no son posibles todas las combinaciones.

Se ha demostrado que los árboles de decisión son eficaces cuando es necesario describir problemas con más de una dimensión o condición. Los árboles de decisión también son útiles para identificar los requerimientos de datos críticos que rodean al proceso de decisión, es decir, los árboles indican los conjuntos de datos que se requiere para el proceso de formulación de decisiones o la toma de acciones. El analista debe identificar y elaborar una lista de todos los datos utilizados en el proceso de decisión, aunque el árbol de decisión no muestre necesariamente todos los datos. Si los árboles de decisión se construyen después de completar el análisis de flujo de datos, entonces es posible que los datos críticos se encuentren definidos en el diccionario de datos. Si únicamente se usan árboles de decisiones, entonces el analista debe tener la certeza de identificar con precisión cada dato necesario para tomar la decisión.

De retorno a la comunidad del aprendizaje automático, la construcción de árboles de decisión es sin duda el método de aprendizaje automático más utilizado. El dominio de aplicación de los árboles de decisión no está restringido a un ámbito concreto sino que pueden ser utilizados en diversas áreas, desde aplicaciones de diagnóstico médico hasta juegos como el ajedrez o sistemas de predicción meteorológica. En estas aplicaciones, el conocimiento obtenido en el proceso de aprendizaje se representa mediante un árbol en el cual cada nodo interior contiene una pregunta sobre un atributo concreto, con un hijo por cada posible respuesta, y cada hoja del árbol se refiere a una decisión. Un árbol de decisión puede usarse para clasificar un caso comenzando desde su raíz y siguiendo el camino determinado por las respuestas a las preguntas de los nodos internos hasta encontrar un nodo hoja del árbol.

Guillermo Choque Aspiazu
www.eldiario.net
Febrero 2 de 2009

1 comentario:

Unknown dijo...

Muchas gracias por la información, excelente calidad.