Eficiencia de los lenguajes basados en reglas4ª parte

Árboles de decisión

Árboles de decisión

Los árboles de decisión proporcionan un paradigma útil para resolver ciertos tipos de problemas de clasificación, pues deducen soluciones al reducir el conjunto de posibles soluciones a una serie de decisiones o preguntas que acortan su espacio de búsqueda.

Árboles de decisión

Los problemas que son adecuados para su solución mediante árboles de decisión se tipifican con la característica de que proporcionan la respuesta a un problema a partir de un conjunto predeterminado de respuestas posibles.

Árboles de decisión

Puesto que debe determinarse el conjunto de respuestas, los árboles de decisión no funcionan bien para resolver problemas de programación, planeación o síntesis y, en general, problemas que deben producir soluciones además de seleccionar entre ellas.

Árboles de decisión

Recuerde que un árbol de decisión se compone de nodos y ramas, los nodos representan ubicaciones en el árbol y las ramas conectan nodos padre con nodos hijo.

Los nodos sin hijos se llaman hojas. En un árbol, cada nodo sólo tiene un

padre, con excepción del nodo raíz, que no tiene ninguno.

Árboles de decisión

Los nodos hojas de un árbol de decisión representan todas las soluciones posibles que se derivan del árbol, a esos nodos se les conoce como “nodos respuestas”, y a los demás como “nodos decisión”.

Cada nodo de decisión representa un cuestionamiento o decisión que, al preguntarse o decidirse, determina la rama apropiada que debe seguirse en el árbol de decisión.

Árboles de decisión

En los árboles de decisión simples esta pregunta podría tener respuestas de si o no.

En general un nodo de decisión puede usar cualquier criterio para seleccionar la rama a seguir, suponiendo que el proceso de selección siempre produce una sola rama.

Los nodos de decisión sofisticados podrían permitir incluso razonamiento hacia atrás o probabilístico.

Ejemplo

Consideremos las siguientes heurísticas en la selección del vino apropiado para servir con un alimento:

SI el plato principal es carne roja

ENTONCES servir con vino tinto

SI el plato principal es ave y es pavo

ENTONCES servir vino tinto

SI el plato principal es ave y no es pavo

ENTONCES servir vino blanco

SI el plato principal es pescado

ENTONCES servir vino blanco

Árbol de decisión binario

Pseudocódigo

procedure Resolver_arbol_binario

Establecer la ubicación del nodo raíz en el árbol

while la ubicación actual es un nodo de decisión do

If la respuesta a la pregunta actual es si

Establecer el nodo actual en la rama su

else

Establecer el nodo actual en la rama no

end if

end do

Devolver la respuesta al nodo actual

End procedure

Árboles de decisión con varias ramas

Árboles decisión múltiple En ocasiones se deben tomar

decisiones que tienen mas de dos alternativas.

En la siguiente figura se muestra un árbol de decisión modificado que permite ramas múltiples realizadas mediante una modificación simple del algoritmo Resolver_arbol_binario:

figura

Pseudocódigo

Procedure Resolver_arbol

Establecer la ubicación actual del nodo raíz.

while la ubicación actual es un nodo de decisión doPreguntar en el nodo actual hasta que se proporcione una respuesta válida para el conjunto de opciones de este nodo.

Establecer el nodo actual en el nodo hijo de la rama asociada con la opción seleccionada

end do

Devolver respuesta al nodo actual

End procedure

Árboles de decisión que aprenden

Árboles que aprenden

En ocasiones es útil agregar conocimiento nuevo a un árbol de decisión a medida que se aprende, como en el conocido ejemplo de identificar animales.

Una vez que el árbol de decisión alcanza una respuesta, pregunta si la respuesta es correcta y, si es así, entonces no hace nada más; pero si la respuesta es incorrecta, se modifica para ajustarse a la respuesta correcta.

Árboles que aprenden

El nodo de respuesta se reemplaza con un nodo de decisión que contiene una pregunta que diferenciará entre la respuesta anterior que estaba en el nodo y la respuesta que no se dedujo correctamente.

A continuación veremos un ejemplo con un árbol de decisión que clasificará un animal conforme a sus características.

Ejemplo de deducción ¿El animal es de sangre caliente? (si o no)

si ¿El animal ronronea? (si o no)

no Deduzco que es un perro ¿Estoy en lo correcto? (si o no)

no ¿Cuál es el animal?

Pajaro

Árboles que aprenden

¿Qué pregunta distinguirá entre un pájaro y un perro cuando se responda si? ¿El animal vuela?

Ahora ya puedo deducir que es un pájaro

¿Intentar otra vez? (si o no)no

Figura

Árboles que aprenden

La sesión puede continuar sin cesar, con el árbol de decisión aprendiendo cada vez más información.

En la siguiente figura se muestra la representación del árbol de decisión después de la sesión anterior, aunque una desventaja de este tipo de aprendizaje es que el árbol de decisión quizá no termine muy estructurado jerárquicamente o no sea muy eficiente en el descubrimiento del animal apropiado.

Figura –árbol que ya aprendió

Árboles que aprenden

Un árbol de decisión eficiente debe tener casi el mismo número de ramas del nodo raíz a los de respuesta para todas las rutas.