Download Práctica 9

Práctica 9
Árboles de decisión
En esta práctica vamos a ver un sistema de aprendizaje basado en árboles de decisión
capaz de generar un conjunto de reglas. Este sistema es el más utilizado y conocido.
1 C4.5
C4.5 es el nombre del sistema de aprendizaje que vamos a utilizar. Lo puedes obtener
en:
http://www.aic.uniovi.es/ssii/P9/winc4.5.zip
Al descomprimirlo verás varios ejecutables y un directorio con conjuntos de
entrenamiento.
Veamos un ejemplo de utilización. Para ello vamos a utilizar el conjunto golf. En
fichero golf.names está la descripción de los atributos:
Play, Don't Play.
outlook: sunny, overcast, rain.
temperature: continuous.
humidity: continuous.
windy: true, false.
Tiene dos clases: jugar o no jugar. Y tiene cuatro atributos: dos simbólicos y dos
numéricos. Los simbólicos indican los símbolos que pueden tomar.
En el fichero golf.data están los ejemplos:
sunny, 85, 85, false, Don't Play
sunny, 80, 90, true, Don't Play
overcast, 83, 78, false, Play
rain, 70, 96, false, Play
rain, 68, 80, false, Play
rain, 65, 70, true, Don't Play
overcast, 64, 65, true, Play
sunny, 72, 95, false, Don't Play
sunny, 69, 70, false, Play
rain, 75, 80, false, Play
sunny, 75, 70, true, Play
overcast, 72, 90, true, Play
overcast, 81, 75, false, Play
rain, 71, 80, true, Don't Play
Son 14 ejemplos. Cada ejemplo tiene un valor para cada atributo y su clase o categoría.
Desde una ventana de MS-DOS vamos a ejecutar el algoritmo:
$ c4.5 –f Data\golf
Obtenemos la siguiente salida:
C4.5 [release 8] decision tree generator Fri May 06 10:50:15 2005
---------------------------------------Options:
File stem <Data\golf>
Read 14 cases (4 attributes) from Data\golf.data
Decision Tree:
outlook = overcast: Play (4.0)
outlook = sunny:
|
humidity <= 75 : Play (2.0)
|
humidity > 75 : Don't Play (3.0)
outlook = rain:
|
windy = true: Don't Play (2.0)
|
windy = false: Play (3.0)
Tree saved
Evaluation on training data (14 items):
Before Pruning
---------------Size
Errors
8
0( 0.0%)
After Pruning
--------------------------Size
Errors
Estimate
8
0( 0.0%)
(38.5%)
<<
Como vemos, se genera un árbol de decisión más fácilmente comprensible mediante la
representación gráfica de la figura 1. Entre paréntesis aparece el número de ejemplos de
entrenamiento que va a cada hoja del árbol. Si nos encontrásemos con que una hoja
tiene (4.0/2.0) querría decir que de los cuatro ejemplos que clasifica esa hoja, falla
dos.
Figura 1.- Representación gráfica del árbol de decisión
En la salida del algoritmo se ve también el resultado del árbol antes y después de podar.
Size es el número de nodos del árbol, Errors el número de errores en el conjunto de
entrenamiento y Estimate el porcentaje de error que estima que tendría sobre un
conjunto de test.
Si tenemos un conjunto de test, podemos utilizar el parámetro –u, que hace que el
algoritmo, una vez haya aprendido, evalúe su árbol sobre el conjunto de test
mostrándonos los resultados y la matriz de confusión.
La ejecución de c4.5 genera dos ficheros:
• golf.unpruned. El árbol sin podar.
• golf.tree. El árbol podado, que es necesario para ejecutar c4.5rules y
consult.
Podríamos, ahora, ejecutar consult. Este programa nos permite evaluar nuevos
ejemplos.
$ consult –f Data\golf
C4.5 [release 8] decision tree interpreter
------------------------------------------
Fri May 06 12:54:13 2005
outlook: sunny
humidity: 34
Decision:
Play
CF = 1.00
[ 0.50 - 1.00 ]
Retry, new case or quit [r,n,q]: q
Podemos obtener reglas a partir del árbol. Esto se logra con el algoritmo c4.5rules:
$ c4.5rules –f Data\golf
C4.5 [release 8] rule generator
-------------------------------
Fri May 06 12:58:18 2005
Options:
File stem <Data\golf>
Read 14 cases (4 attributes) from Data\golf
-----------------Processing tree 0
Final rules from tree 0:
Rule 2:
outlook = overcast
-> class Play [70.7%]
Rule 4:
outlook = rain
windy = false
-> class Play
[63.0%]
Rule 1:
outlook = sunny
humidity > 75
-> class Don't Play
[63.0%]
Rule 3:
outlook = rain
windy = true
-> class Don't Play
[50.0%]
Default class: Play
Evaluation on training data (14 items):
Rule Size Error Used Wrong
---- ---- ----- ---- ----2
1 29.3%
4
0 (0.0%)
4
2 37.0%
3
0 (0.0%)
1
2 37.0%
3
0 (0.0%)
3
2 50.0%
2
0 (0.0%)
Tested 14, errors 0 (0.0%)
(a) (b)
---- ---9
5
Advantage
--------0 (0|0)
0 (0|0)
3 (3|0)
2 (2|0)
Play
Play
Don't Play
Don't Play
<<
<-classified as
(a): class Play
(b): class Don't Play
Vemos que aparecen varias reglas y al final una clase por defecto. Los ejemplos que no
cumplan las condiciones de ninguna regla serán clasificados con el valor que tiene la
clase por defecto. Entre corchetes se indica el acierto esperado de cada regla.
Aparece, luego, una tabla con los siguientes valores:
• Rules: número de regla que le asignó c4.5rules
• Size: número de antecedentes de la regla
• Error: el error esperado de la regla
• Used: número de veces que fue utilizada
• Wrong: número de veces que ha fallado
• Advantage: ventaja entre aciertos y fallos de la regla. Por ejemplo, si tenemos
2(3|1) quiere decir que esta regla se ha utilizado 4 veces: tres veces
correctamente y una vez de manera incorrecta. Por tanto la ventaja es dos.
Finalmente vemos la matriz de confusión.
La ejecución de c4.5rules genera un fichero:
• golf.rules. Este fichero almacena las reglas y es necesario para ejecutar el
programa consultr.
Podemos, por tanto, utilizar consultr para evaluar un ejemplo con las reglas:
$ consult –f Data\golf
C4.5 [release 8] production rule interpreter
2005
--------------------------------------------
Fri May 06 13:21:11
outlook: sunny
Decision:
Play (default class)
Retry, new case or quit [r,n,q]: q
Se puede encontrar más información en el siguiente enlace:
http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.html
1.1 Trabajo
Aplicar este algoritmo sobre los conjuntos de datos que aparecen en el directorio Data.
2 Como utilizarlo en Spider
El Spider no es el único entorno de experimentación de Aprendizaje Automático,
existen otros, como por ejemplo el Weka (http://www.cs.waikato.ac.nz/ml/weka/),
donde los algoritmos están implementados en Java. La última versión del Spider
permite la ejecución de los algoritmos implementados para el Weka. Para ello,
necesitamos colocar el fichero weka.jar en el directorio
C:\Archivos de programa\MATLAB\R2007a\java\jar
de nuestro sistema. En los ordenadores de la escuela, no es necesario hacer esto, ya que
ha sido instalado con anterioridad. En vuestras casas, sin embargo, deberéis hacerlo. El
fichero weka.jar podéis obtenerlo descargando el weka o copiándolo de los
ordenadores de la escuela.
Si todo está correctamente instalado, al ejecutar el comando use_spider del
spider debería aparecer en algún momento el siguiente texto: WEKA support
enabled!
¿Por qué estamos tan interesados en instalar el Weka? Porque tienen una
implementación del C4.5 llamada j48 (¿?) y la nueva versión de Spider nos permite
utilizarla como un algoritmo más. Veamos un problema en el que tenemos 200 ejemplos
en un espacio bidimensional uniformemente distribuidos en el intervalo [0,1]:
>> x=rand(200,2);
>> y=ones(200,1);
Serán de clase positiva todos los ejemplos excepto aquellos cuyas coordenadas cumplan
que ambas son menores que 0.5 o la primera mayor que 0.75 y la segunda mayor que
0.9.
>>
>>
>>
>>
>>
indexneg=find(x(:,1)<0.5 & x(:,2)<0.5);
y(indexneg)=-1;
indexneg=find(x(:,1)>0.75 & x(:,2)>0.9);
y(indexneg)=-1;
d=data(x,y);
Ahora ya podemos crear un sistema j48 y experimentar con el utilizando las técnicas
de evaluación vistas en la práctica anterior.
>> a=j48;
>> [r s]=train(cv(a),d);
>> get_mean(r)
Podemos también ver el árbol que genera cuando hacemos un entrenamiento simple:
>> [r s]=train(a,d) % vemos el árbol
training j48....
data -> j48
data dimensions:
X = 200x1 Y = 200x1
J48 pruned tree
-----------------inp
|
|
inp
|
|
|
|
2 <= 0.485229
inp 1 <= 0.495177: out 1 (55.0)
inp 1 > 0.495177: out 2 (39.0)
2 > 0.485229
inp 2 <= 0.900852: out 2 (89.0)
inp 2 > 0.900852
|
inp 1 <= 0.741258: out 2 (12.0)
|
inp 1 > 0.741258: out 1 (5.0)
Number of Leaves
:
Size of the tree :
5
9
Incluso podemos ver gráficamente las reglas si trabajamos con problemas de dos
dimensiones:
>> plot(s,d)
Fíjate que se le pasa como parámetro s, que es el sistema entrenado.
Figura 2.- Reglas generadas por el j48
2.1 Trabajo
En la práctica anterior nos conectamos al Web:
http://www.ics.uci.edu/~mlearn/MLRepository.html
y experimentamos con diferentes conjuntos de datos. Utiliza el j48 para aprender sobre
esos conjuntos. ¿Qué sistema te ofrece mejores resultados? ¿El knn? ¿El j48?