Eficiencia de los lenguajes basados en reglas 4a parte
25
Eficiencia de los lenguajes basados en reglas 4ª parte
description
Uso de los árboles de decisión en los sistemas basados en reglas.
Transcript of Eficiencia de los lenguajes basados en reglas 4a parte
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.
