Árboles de decisión

Equipo 13 StessCalc (Ex-InteliQWOP)

Diego García M. 1162205
Joaquín León M. 1162101
Enrique Peña A. 1162110

Instituto Tecnológico de Estudios Superiores Monterrey
Aprendizaje Automático

Actividad de programación 3 – Árboles de decisión

a. Breve descripción del medio ambiente.
El medio se basa en el análisis de una base de datos que se llenó con información real proporcionada por estudiantes. La información contenida en la base de datos nos dice el nivel de estrés que maneja una persona dependiendo de varios síntomas. La base de datos tiene como columna a cada síntoma, y se llena con una de cuatro opciones (nada, pocas veces, ocasionalmente, frecuentemente). Y al final todos estos valores convergen al resultado final del nivel de estrés de la persona que puede ser: Nada, Poco, Regular y Alto.

b. Descripción detallada de la actividad o acción que va a aprender tu agente.
El sistema aprende a decidir el nivel de estrés que maneja una persona con base a todos los ejemplos que tiene en su base de datos y nos dá un resultado sin tener que preguntar por todos los síntomas.

c. Descripción detallada de los patrones obtenidos del medio ambiente para el entrenamiento. Explicar la razón por la que se escogieron cada uno de los atributos del patrón.
Los patrones se obtuvieron por medio de una encuesta realizada por internet. Los atributos de los patrones están basados en un estudio previamente realizado por la alumna de la carrera de Psicología Organizacional, Adriana Sánchez Ávalos.

d. Solución planteada al problema utilizando árboles de decisión (pueden utilizar ID3, C4.5, etc.). Describe con detalle cada elemento del planteamiento:

I. Algoritmo de aprendizaje mediante árboles de decisión, ¿cuál algoritmo utilizaron y por qué?
Utilizamos el algoritmo de aprendizaje ID3 ya que fue el que conocíamos y vimos en clase. Utilizamos una implementación previa del algoritmo creada por Christopher Roach.

II. Patrones de aprendizaje:

i. ¿Cuántos patrones se utilizaron para el entrenamiento y por qué?
Se utilizaron 150+ ejemplos para el aprendizaje del sistema. Es el número de encuestas contestadas después de restarle el porcentaje considerado para la validación.

ii. ¿Cuántos patrones se utilizaron para la validación y por qué?
Decidimos utilizar el 15% de las encuestas para validación

iii. Ejemplos de patrones con todo y el atributo de clasificación (clasificación correcta e incorrecta).

Ejemplos:

A P P P M M A P M P P P M P M P P M Regular P N N N N N P P P N N N P N P N N N Poco

Donde:

A = Alto

M = Medio

B = Bajo

N = Nada

III. ¿Funciona en tiempo real o fuera de línea su programa? ¿Por qué?
El programa funciona fuera de línea, se realizó una única copia de la base de datos y se transfirió al programa. Se hizo de esta forma para poder tener un acceso más rápido a los datos dentro de la base y así agilizando el aprendizaje, además de que, dado que la base de datos en tiempo real proviene de google docs, no tenemos manera de accesarla en tiempo real, nada más se puede importar a un archivo de excel pero manualmente.

IV. ¿Sobreclasifica los patrones (overfitting)? ¿Por qué?
Se sobreclasifica un poco ya que nuestro número de atributos es bastante grande (19) y el número de ejemplos que obtuvimos no es completamente suficiente para generar un árbol muy general, es decir, se “aprende” un poco las respuestas obtenidas en la encuesta. Sin embargo, sigue pudiendo clasificar nuevos ejemplos de prueba de una manera bastante aceptable.

V. ¿Cómo mejorarías el desempeño de tu programa?
Utilizando un mayor número de patrones de ejemplo para que termine de aprender correctamente el sistema y genere un árbol adecuado y lo suficientemente general.

e. Conclusiones después de la programación.
Nos costó un poco de trabajo terminar de entender el funcionamiento de ID3 con árboles más grandes ya que los ejemplos vistos en clase eran muy pequeños (solo 2 niveles) Lo cual nos llevó mucho más tiempo para poder adaptar la implementación de ID3 a nuestra base de datos.

Árbol generado:

Referencias:

· Roach, C. (2006). Building Decision Trees in Python. Obtenido el 14 de abril del 2011 de: http://onlamp.com/pub/a/python/2006/02/09/ai_decision_trees.html?page=1

Arboles de decision

Medio Ambiente

Planet Wars, juego basado en Galcon. El juego tiene un mapa que contiene varios planetas, cada uno con un escuadrón de naves. Los planetas pueden pertenecer a uno de tres propietarios diferentes: al jugador 1, al enemigo o neutral. El juego tiene un cierto número máximo de vueltas y el juego puede terminar antes si uno de los jugadores pierde todas sus naves. Si ambos jugadores tiene el mismo número de naves cuando el juego termina, es un empate.

Actividad que el Agente Aprenderá: Maximizar su eficiencia de juego por medio de la creación de una estrategia de juego.

Algoritmo Arboles de decision

Experiencia de Aprendizaje: En el medio ambiente y el algoritmo dado (en este arboles de decisión), el agente aprenderá a generar una decisión, a partir de atributos que le daremos. Se puede dividir en 3 el número de acercamientos a este aprendizaje, pues puede aprender por acciones, estrategias o estados. Por estados sería que estuviera atacando, defendiendo o expandiendo; por estrategia seria que por una serie de tornos tomara una secuencia de acciones en base a su análisis del medio ambiente. Y por acciones, es literalmente decirle que ataque efectuar cada turno, es decir decirle que dado por ejemplo 10 planetas míos, y 15 planetas enemigos, conviene seguir expandiendo. Dado que lo mejor es que cada turno evalúe su medio, decidimos que este sería este mejor método.

Ejemplos del Estados

PGCD	PGCND	PGLD	…	PEGCD	PEGCND	…	FGC	FGL	Decision
mucho	poco	poco		mucho	poco		nulo	poco	MPGCD

Conclusiones

Después de trabajar en la implementación de árboles de decisión en Planet Wars, pudimos llegar a la conclusión de que la implementación en este medio no es viable debido a la naturaleza del mismo; ya que al ser en parte muy dinámico y en parte variable en tamaño, por esto se refiere al número de planetas totales en cada partida, un árbol puede resultar inservible de un juego a otro.

NOTA IMPORTANTE: por las razones expuestas en la conclusión, no se tiene un video del programa corriendo, una disculpa atenta por esto.

Actividad 3 - Árboles de decisión

Spam o no Spam

Breve descripción del medio ambiente

Descripción detallada de la actividad o acción que va a aprender tu agente.

El programa tiene como finalidad el poder clasificar si un correo es considerado spam o no. Nótese que la definición de spam fue propuesta por nosotros, así que lo que el agente aprenderá tiene base en nuestra definición. Spam es cualquier intención de querer tratar de venderte algo y/o correos que no tengan un valor importante o que te puedan hacer daño

Descripción detallada de los patrones obtenidos del medio ambiente para el entrenamiento.

Los patrones los obtuvimos inicialmente de analizar cada uno de los casos según nuestro criterio de spam. Si hubiéramos obtenido los patrones mediante una encuesta podríamos haber sufrido de mucho overfitting por el ruido que se le mete al programa. Esto porque cada quien tiene una opinión diferente de lo que se considera spam. Se podía dar el caso de que se pudiera llegar a un porcentaje de relación entre las opiniones, pero los casos específicos hubieran hecho que algoritmo memorizara en lugar de aprender. Este tipo de aplicaciones están enfocadas a ser de uso personal y no de forma grupal.

Solución planteada al problema utilizando árboles de decisión (pueden utilizar ID3, C4.5, etc.).

Describe con detalle cada elemento del planteamiento:

i. Algoritmo de aprendizaje mediante árboles de decisión, ¿cuál algoritmo utilizaron y por qué?

Usamos el algoritmo de ID3 debido a que nuestro ambiente no es continuo. Y por tanto no se necesitan las mejoras del C4.5

ii. Patrones de aprendizaje:

1. ¿Cuántos patrones se utilizaron para el entrenamiento y por qué?

Usamos 300 patrones porque consideramos que eran suficientes como para que pudiera aprender sin necesidad de que tenga todas las opciones a la mano. El algoritmo no menciona cual es un número adecuado de patrones para aprender pero consideramos que al ser aprox el 40% de la población de posibilidades era suficiente para que pudiera generalizar.

2. ¿Cuántos patrones se utilizaron para la validación y por qué?

Para la validación usamos aproximadamente 20 patrones porque es un número ni muy grande ni muy pequeño para las pruebas.

3. Ejemplos de patrones con todo y el atributo de clasificación (clasificación                      correcta e incorrecta).

Ejemplo No Spam:

·       (SpamWords=Bajo,ImportantWords=Alta,self=No,cadena=No,%=No,Level=alto,Links=Si,Trustiness=Alta)

·         (SpamWords=Medio,,ImportantWords=Medio,self=Si,cadena=Si,%=No,Level=Medio,Links=Si,Trustiness=Alta)

Ejemplo Spam:

·         (SpamWords=Bajo,ImportantWords=Alta,self=No,cadena=So,%=Si,Level=bajo,Links=Si,Trustiness=Medio)

·         (SpamWords=Medio,ImportantWords=Baja,self=No,cadena=Si,%=No,Level=medio,Links=Si,Trustiness=Baja)

iii. ¿Funciona en tiempo real o fuera de línea su programa? ¿Por qué?

El entrenamiento es fuera de línea y el funcionamiento ya es en tiempo real. Pues el valor que tiene un filtro anti-spam es precisamente que funcione cada ocasión que te llegue un correo

iv. ¿Sobre clasifica los patrones (overfitting)? ¿Por qué?

Inicialmente si tenía overfitting puesto que algunos de los patrones se repetían y algunos estaban siendo mal clasificados. Solucionamos el problema clasificando los patrones de una mejor forma, con más consistencia.

v. ¿Cómo mejorarías el desempeño de tu programa?

Inicialmente haciendo que este funcione en tiempo real, es decir que realmente fuera parte de algún cliente de correo y que pueda regenerar el árbol con cada correo que le llegara. De la misma forma en que la App de importantes de google funciona, le vas poniendo que consideras importante y ve que agregar o no a su descripción de importancia. A lo mejor se podrían sacar palabras de las listas de spam e importancia y agregar dependiendo de la retroalimentación del usuario. Lo que sí es importante considerar es que considerar algo spam o no depende mucho de lo que el usuario finalmente considere poco importante.

  

Conclusiones después de la programación.

Esta actividad resultó interesante ya que el tema se nos hizo importante desde un punto de vista práctico. Tuvimos la oportunidad de desarrollar parte del código en python y aprender a usar una biblioteca de gráficos para python que nunca habíamos usado. Lo mejor fue lograr que el árbol si generalizara.

Árboles de decisión

EQUIPO 7:

Martha Hernández
Alfonso Martínez
José Angel Daza

Nuestro ambiente se centra alrededor de los lenguajes de programación, cada uno con sus propias reglas de sintaxis, semántica y símbolos. Basados en estas propiedades se pretende programar a un agente que distinga entre siete lenguajes diferentes.

Nuestro agente aprenderá a determinar el lenguaje de programación en el que está escrito cierto código. Para fines prácticos se decidió usar 100 líneas como el tamaño estándar de un programa y se eligieron python, c, java, brainfuck , clojure, erlang y php como las diferentes categorías de clasificación.

La clasificación de los patrones está basada en el número de ciertos símbolos representativos presentes en el código dado. Basados en nuestra experiencia personal, decidimos contar el número de repeticiones de los siguientes símbolos y palabras

(), *, +, [], |, $, class, private, abstract, #, include, :, -, /, extends

Para entrenar a nuestro árbol de decisión bajamos código de diferentes repositorios de código abierto. Enseguida hicimos un sencillo programa que cuenta el número de repeticiones de los símbolos en los archivos, así generamos los patrones para entrenar al agente.

Para que el agente pudiera diferenciar los diferentes lenguajes utilizamos el algoritmo C4.5, ya que genera árboles de decisión a partir de valores continuos. Particularmente utilizamos la implementación de Orange, que es muy fácil de usar. En el siguiente video se puede apreciar la facilidad con la que el programa genera el árbol de decisión.

Nuestro árbol de decisión quedó finalmente así:

Al hacer esta actividad nos dimos cuenta de que diseñar un patrón de aprendizaje no es una tarea sencilla. El algoritmo ya está programado, y hay paquetería que lo hace muy bien, pero el verdadero reto consiste en saber cuándo el algoritmo funcionará, y darle las condiciones para que lo haga. En nuestro caso afortunadamente funcionó a la primera, pero seguramente si no hubiéramos tenido la asesoría del profesor desde el inicio pudimos haber sufrido bastante en este aspecto.

Por otra parte, recopilar datos también es una de las partes más pesadas del algoritmo, y aunque afortunadamente por nuestro ambiente pudimos obtener rápidamente varios ejemplos de la red, no en todos los casos es tan sencillo hacerlo.