Aprendizaje Inductivo: Árboles de Decisión
Entre los diversos tipos de aprendizaje que podemos diferenciar, destaca el aprendizaje inductivo, que se basa en el descubrimiento de patrones a partir de ejemplos. Desde el punto de vista de la clasificación, la tarea general consiste en lo siguiente:
Supongamos que disponemos de N ejemplos observados en el mundo real, \(\{e_1,\dots, e_N\}\), que vienen definidos a partir de un conjunto de atributos (propiedades), \(e_i=(p_{i1},\dots,p_{im})\), y para cada uno de ellos tenemos una clasificación observada, \(c_i\). La tarea del aprendizaje inductivo consiste en inducir de los datos anteriores un mecanismo que nos permita inferir las clasificaciones de cada uno de los ejemplos a partir únicamente de las propiedades. Si esto es posible, podríamos usar este mecanismo para deducir la clasificación de nuevos ejemplos habiendo observado únicamente sus propiedades.
Es evidente que obtener un mecanismo como este sería muy útil debido a que podríamos predecir comportamientos futuros a partir de los comportamientos observados en el pasado. Por ejemplo, a partir de los síntomas que tenemos observados en enfermos anteriores, y sabiendo ya si han desarrollado o no cierta enfermedad, podríamos extraer patrones que nos permitieran predecir si un paciente nuevo, aquejado de ciertos síntomas, desarrollará o no la misma enfermedad, lo que nos permitiría adelantarnos a su tratamiento. Otro ejemplo que es muy usado en la actualidad se encuentra en el mundo de los créditos bancarios, a partir de los comportamientos de los clientes antiguos con respecto a la morosidad o no de sus pagos del crédito concedido, podemos inferir qué nuevos clientes pueden ser los más convenientes para la concesión de un crédito, es decir, cuáles de ellos tienen más probabilidad de hacer frente al pago del mismo y cuáles más probabilidad de dejarlo sin pagar.
Aunque los resultados que se obtienen dependen de la calidad de los ejemplos introducidos (que sea una cantidad suficiente, que representen fielmente el comportamiento de la población no observada, que no muestren contradicciones internas, etc.), sin lugar a dudas este mecanismo de descubrimiento de patrones se ha convertido en los últimos años en una de las fuentes más fiables de predicciones y su uso se ha extendido velozmente.
Entre todos los posibles mecanismos para obtener estas predicciones de manera fiable, una de las que más destaca es la creación de árboles de decisión, que proporcionan un conjunto de reglas que se van aplicando sobre los ejemplos nuevos para decidir qué clasificación es la más adecuada a sus atributos/propiedades.
Un árbol de decisión está formado por un conjunto de nodos de decisión (interiores) y de nodos-respuesta (hojas):
- Un nodo de decisión está asociado a uno de los atributos y tiene 2 o más ramas que salen de él, cada una de ellas representando los posibles valores que puede tomar el atributo asociado. De alguna forma, un nodo de decisión es como una pregunta que se le hace al ejemplo analizado, y dependiendo de la respuesta que de, el flujo tomará una de las ramas salientes.
- Un nodo-respuesta está asociado a la clasificación que se quiere proporcionar, y devuelve la decisión del árbol con respecto al ejemplo de entrada.
El ejemplo anterior (el más clásico de los que se pueden encontrar) muestra la tabla de ejemplos que hemos observado a lo largo del tiempo respecto a las condiciones meteorológicas y la idoneidad de jugar al golf o no (esencialmente, es un conjunto de anotaciones de algunas condiciones meteorológicas que se han dado en días anteriores, y la opinión de individuos que determinaron si el día fue adecuado o no para jugar).
El árbol de la derecha muestra un posible mecanismo coherente con los datos para poder tomar decisiones para esta tarea de clasificación. Observa que el árbol está formado únicamente por los nodos azul oscuro (nodos de decisión) y los de color amarillo (nodos-respuesta), mientras que los rectángulos azules claro son simplemente las etiquetas de las ramas de salida de cada nodo de decisión, indicando cuál es la opción que verifica el ejemplo que estamos intentando clasificar.
Es evidente que no siempre podremos conseguir un árbol de decisión que sea capaz de predecir los ejemplos con una fiabilidad del 100%, pero cuanto mejor sea la batería de ejemplos de los que disponemos (por ejemplo, que no haya contradicciones entre clasificaciones), mejor se comportará el árbol que podemos construir a partir de ellos.
El algoritmo ID3
Evidentemente, la construcción del árbol de decisión no es única, y si aplicamos una estrategia u otra a la hora de decidir en qué orden se hacen las preguntas sobre los atributos podemos encontrar árboles muy dispares. De entre todos los posibles árboles, estamos interesados en encontrar aquellos que cumplan las mejores características como máquinas de predicción, e intentaremos dar un mecanismo automático de construcción del árbol a partir de los ejemplos.
En el año 1979, J. Ross Quinlan presenta un método para construir árboles de decisión que presentan muy buenas características, como son un buen balanceado y un tamaño pequeño (el menor número de preguntas posibles para poder encontrar la respuesta en todos los casos, si es posible). Para ello, hace uso de la Teoría de la Información desarrollada por C. Shannon en 1948. Aunque el mérito se le asocia a Quinlan, la verdad es que de forma paralela aparecieron varios métodos de construcción que eran prácticamente equivalentes. El algoritmo de construcción que presenta se llama ID3, y hasta el momento ha sido el más utilizado y en el que se han basado la mayoría de las mejoras posteriores introducidas por el mismo Quinlan y por otros autores.
El ID3 construye un árbol de decisión de arriba a abajo, de forma directa, sin hacer uso de backtracking, y basándose únicamente en los ejemplos iniciales proporcionados. Para ello, usa el concepto de Ganancia de Información para seleccionar el atributo más útil en cada paso. En cierta forma, sigue un método voraz para decidir la pregunta que mayor ganancia da en cada paso, es decir, aquella que permite separar mejor los ejemplos respecto a la clasificación final.
Para poder aplicar el algoritmo hemos de comenzar sabiendo cómo se mide la ganancia de información, y para ello hay que introducir el concepto de Entropía de Shannon, que de alguna forma mide el grado de incertidumbre de una muestra.
Antes de entrar en esos detalles, vamos a ver los elementos principales en los que se basa el método ID3:
- Las entradas del algoritmo ID3 son un conjunto de ejemplos descritos mediante una serie de pares atributo-valor. Podemos pensar en ellos como una tabla en la que cada fila representa un ejemplo completo, y cada columna tiene el valor almacenado de cada uno de sus posibles atributos. Uno de esos atributos, generalmente el último de la tabla, debe almacenar la clasificación (clase) que corresponde con el ejemplo, y que es el objetivo de predicción. En el campo de la Ciencia de Datos a este tipo de tablas se le llama DataFrames:
- La salida del algoritmo ID3 será un árbol de decisión que separe los ejemplos de acuerdo a las clases a las que pertenecen.
En definitiva, el algoritmo responde a un esquema clásico de clasificación en el que se imponen dos requisitos para las clases:
- Clases predefinidas: Se parte de un problema de aprendizaje supervisado en el que el atributo que hace las veces de clase está perfectamente identificado de antemano y se conoce para todos los ejemplos iniciales.
- Clases discretas: Se exige que haya un conjunto discreto y finito de clases que sirven para clasificar claramente todos los ejemplos presentados. Aunque hay variantes que permiten trabajar con clases con valores continuos, como veremos al final de esta entrada.
Además, se supone que el número de ejemplos presentados tiene que ser muy superior al de posibles clases, ya que el proceso de aprendizaje que vamos a ver se basa en un análisis estadísitico que puede arrojar errores en caso contrario. Un problema real puede requerir cientos o miles de ejemplos de entrenamiento.
Entropía de Shannon
Supongamos que miramos cómo de homogéneos son los ejemplos de los que queremos aprender respecto a la clasificación:
- Una muestra completamente homogénea (es decir, en la que todos se clasifican igual) tiene incertidumbre mínima, ya que no hay dudas de cuál es la clasificación de cualquiera de sus elementos (si elegimos al azar cualquier de ellos, sabremos qué resultado tendremos). En este caso, fijaremos la incertidumbre (entropía) a \(0\).
- Una muestra igualmente distribuida, es decir, que tiene el mismo número de ejemplos de cada posible clasificación, muestra una incertidumbre máxima, en el sentido de que es la peor situación para poder saber a priori cuál sería la clasificación de cualquiera de sus ejemplos elegido al azar. Así pues, en este caso fijaremos la incertidumbre (entropía) a \(1\).
Con estos requisitos, y algunas propiedades más que hemos de añadir para que se comporte bien, buscamos dar una definición matemática de la entropía que sirva para medir la incertidumbre de un sistema. Tras un análisis minucioso de las propiedades que debía cumplir una tal función de entropía, Shannon llegó a la conclusión de que la mejor función matemática que mide este grado de incertidumbre es la siguiente:
\(E(S)=\sum_{c\in C}-p_c \log_2(p_c)\)
donde \(S\) es el conjunto de muestras (el sistema analizado), \(C=\{c_1,\dots,c_n\}\) es el conjunto de diferentes clasificaciones que usamos, y cada \(p_c\) es la proporción de ejemplos que hay de la clasificación \(c\) en la muestra.
En el caso particular de una clasificación binaria (que podríamos denotar como ejemplos positivos / negativos), la fórmula anterior queda como:
\(E(S)=-P \log_2(P) - N \log_2(N)\)
donde \(P\) y \(N\) son, respectivamente, la proporción de ejemplos positivos y negativos. La figura adjunta muestra la variación de la función entropia en función de una de las dos opciones.
(Recordemos que \(log_2(a)=\log_{10}(a) / \log_{10}(2)\), y que debido a que no está definido el \(\log_x(0)\), tomaremos siempre que \(0 \log_2(0) = 0\) en la suma anterior.)
Por ejemplo, en el ejemplo presentado en la tabla anterior (la del juego de golf), la entropía que tiene el sistema respecto a la clasificación de si se juega al golf o no es la siguiente:
Aplicación de la Entropía a ID3
Una vez definida matemáticamente la incertidumbre, o entropía, tenemos más fácil entender qué es la información. Decimos que tenemos información acerca de un sistema cuando estamos más alejados de la incertidumbre, cuando podemos predecir con mayor fiabilidad el estado del sistema. En este sentido, la ganancia de información consiste en un decremento de la entropía/incertidumbre del sistema.
En general, cuando dividimos la muestra de datos (el dataframe) respecto a los valores de cualquiera de los atributos conseguimos que la entropía del sistema disminuya en cada uno de los sub-dataframes que aparecen, ya que hemos fijado información adicional en cada muestra (hay menos incertidumbre respecto a uno de sus atributos). Así pues, dividir las muestras según los valores de sus atributos parece ser una buena forma de conseguir reducir la incertidumbre y aumentar nuestro conocimiento del sistema.
¿Qué atributo crea las ramas más homogéneas y, por tanto, proporciona una ganancia de información mayor? Respondiendo a esta pregunta obtendríamos cuál sería la mejor pregunta posible en un determinado momento, para ello podemos usar la entropía asociada a cada atributo (respecto del atributo Objetivo que ofrece la clasificación), donde la entropía asociada a un atributo $X$ se podría calcular como:
\[E(T,X)=\sum_{c\in X}p(c)E(T,D_c)\]
Y la ganancia de información que aportaría dividir respecto a los valores de ese atributo vendría dada por:
\[Gain(T,X)=E(T,D)-E(T,X)\]
Así pues, el mecanismo que nos permite seleccionar respecto qué atributo puede ser más conveninente hacer la división vendrá dado por:
SELECCION_ATRIBUTO(D,T) [D: Dataset; T: Atributo Objetivo; Att: Atributos de D]
S = E(T,D) (Entropía de D respecto a T)
Para cada X ∈ Att:
Para cada c ∈ X: D_c={e ∈ D: X(e)=c}
Calcular E(T,X) = ∑_{c ∈ X} p(c) E(T,D_c) (Entropía de X respecto a T)
Calcular Gain(T,X) = E(T,D) - E(T,X)
Devolver A=maxarg{X ∈ Att: Gain(T,X)}
El algoritmo ID3 consiste en ejecutar recursivamente este procedimiento sobre los diversos Datasets que se van generando hasta llegar al caso de entropía nula (o se verifique la condición de parada que se considere adecuada, por ejemplo, que el tamaño del conjunto de muestras en ese momento no supere un tamaño mínimo). En el siguiente pseudocódigo, el caso $D$ expandible representa el caso en el que el dataset requiere más exploración:
ID3(D,T)
Si D expandible: (nodo decisión)
X = SELECCION_ATRIBUTO(D,T)
Crear Nodo_X
Para cada c ∈ X:
Arbol_c = ID3(D_c,T)
Conectar Nodo_X --c--> Arbol_c
si no:
Nodo_x = argmax {t ∈ T: |D_t|} (nodo respuesta)
Devolver Nodo_X
Una rama con entropía \(0\) se convierte en una hoja (nodo-respuesta), ya que representa una muestra completamente homogénea, en la que todos los ejemplos tienen la misma clasificación. Si no es así, la rama debe seguir subdividiéndose con el fin de clasificar mejor sus nodos.
Ejemplo 1:
Las siguientes figuras muestran el proceso que hay que seguir para dar un paso completo en el ejemplo anterior. Recordemos que inicialmente, antes de realizar ninguna división por atributos, la entropía del sistema es:
Calculemos la ganancia que obtendríamos si hicieramos una división usando el primer atributo (Outlook):
Y se repite con cada uno de los atributos que tienen los ejemplos:
Y nos quedamos con el atributo que proporciona mayor ganancia (en este caso, Outlook), con lo que tenemos construido el primer paso del árbol de decisión, identificando el primer nodo de decisión:
 |
 |
A continuación nos situamos en cada uno de los subconjuntos de ejemplos que define cada valor del atributo seleccionado y repetimos el proceso, construyendo poco a poco el árbol completo de decisión. Un nodo que tenga entropía nula se convierte en un nodo respuesta, ya que representa una muestra homogénea en el que la clasificación final es la misma para todos los ejemplos que contiene:
 |
 |
Uno de los aspectos más interesantes que ofrecen los árboles de decisión como máquinas de predicción es que permiten explicar porqué un determinado ejemplo se clasifica de una cierta forma, y podemos extraer un procedimiento que se implementa fácilmente en cualquier sistema haciendo uso de reglas condicionales. Por ejemplo, el árbol anterior tiene una traducción en el siguiente conjunto de reglas:
Ejemplo 2:
Tras haber visto el esquema de ejecución con el ejemplo anterior, vamos a presentar un ejemplo completo de construcción de un árbol de decisión aplicando el algoritmo.
El dataset, $D_0$, sobre el que trabajaremos es el siguiente:
| Nº Paciente | Presión Arterial | Urea en Sangre | Gota | Hipotiroidismo | Administrar Tratamiento |
|---|---|---|---|---|---|
| 1 | Alta | Alta | true | false | false |
| 2 | Alta | Alta | true | true | false |
| 3 | Normal | Alta | true | false | true |
| 4 | Baja | Normal | true | false | true |
| 5 | Baja | Baja | false | false | true |
| 6 | Baja | Baja | false | true | false |
| 7 | Normal | Baja | false | true | true |
| 8 | Alta | Normal | true | false | false |
| 9 | Alta | Baja | false | false | true |
| 10 | Baja | Normal | false | false | true |
| 11 | Alta | Normal | false | true | true |
| 12 | Normal | Normal | true | true | true |
| 13 | Normal | Alta | false | false | true |
| 14 | Baja | Normal | true | true | false |
donde AT=Administrar Tratamiento es el atributo objetivo (un problema de clasificación binario). Hemos añadido una columna inicial con el número de fila (número de paciente) para facilitar el seguimiento de qué pacientes se trasladan a qué datasets tras cada nodo de decisión, pero no intervendrá (obviamente) en el proceso de decisión.
Elección del primer atributo de máxima ganancia:
La entropía del dataset original (respecto al atributo objetivo) es:
$$E(D_0,AT)= -\frac{5}{14} log_2(\frac{5}{14}) - \frac{9}{14} log_2(\frac{9}{14})=0.940$$
y las cuatro ganancias de información que se obtendrían con los atributos del dataframe $D_0$ son:
-
Presión Arterial ( P ): $GI(P,D_0)=0940-\frac{5}{14} 0.971 - \frac{4}{14} 0 - \frac{5}{14} 0.971 = 0.246$
- Alta $[2+,3-]$: $E=0.971$
- Normal $[4+,0-]$: $E=0$
- Baja $[3+,2-]$: $E=0.971$
-
Gota ( G ): $GI(G,D_0)=0.940-\frac{7}{14} 0.985 -\frac{7}{14} 0.592 = 0.151$
- Sí $[3+,4-]$: $E=0.985$
- No $[6+,1-]$: $E=0.592$
-
Urea en Sangre ( U ): $GI(G,D_0)=0.940-\frac{4}{14} 1-\frac{6}{14} 0.918-\frac{4}{14} 0.811=0.029$
- Alta $[2+,2-]$: $E=1$
- Normal $[4+,2-]$: $E=0.918$
- Baja $[3+,1-]$: $E=0.811$
-
Hipotiroidismo ( H ): $GI(H,D_0)= 0.940 -\frac{6}{14} 1-\frac{8}{14} 0.811=0.048$
- Sí $[3+,3-]$: $E=1$
- No $[6+,2-]$: $E=0.811$
La máxima ganancia se obtiene con Presión Arterial, que se convierte en el primer nodo de decisión, con tres ramas de salida (una para cada valor del atributo: Alta, Normal y Baja). Para cada una de estas tres ramas hemos de construir un árbol de decisión con el resto de atributos siguiendo el mismo proceso que se ha seguido con el dataset original, pero considerando solo aquellas muestras que verifican el valor correspondiente para el atributo PA.
Nota: La rama correspondiente al valor PA=Normal desemboca en un nodo de respuesta, ya que el dataset correspondiente tiene entropía nula (para todas sus muestras la decisión es la misma, true).
Elección del segundo atributo de máxima ganancia:
Para el dataset $D_1=D_{PA=Alta}$ la entropía respecto del atributo objetivo es:
$$E(D_1,AT)= -\frac{2}{5} log_2(\frac{2}{5}) - \frac{3}{5} log_2(\frac{3}{5})=0.971$$
y las tres ganancias de información que se obtendrían con los atributos que queda en el dataframe $D_1$ son:
-
Gota ( G ): $GI(G,D_1)=0.971-\frac{3}{5} 0 -\frac{2}{5} 0 = 0.971$
- Sí $[0+,3-]$: $E=0$
- No $[2+,0-]$: $E=0$
-
Urea en Sangre ( U ): $GI(G,D_1)=0.971-\frac{2}{5} 0-\frac{2}{5} 1-\frac{1}{5} 0=0.571$
- Alta $[0+,2-]$: $E=0$
- Normal $[1+,1-]$: $E=1$
- Baja $[1+,0-]$: $E=0$
-
Hipotiroidismo ( H ): $GI(H,D_1)= 0.971 -\frac{2}{5} 1-\frac{3}{5} 0.918=0.020$
- Sí $[1+,1-]$: $E=1$
- No $[1+,2-]$: $E=0.918$
La máxima ganancia se obtiene con Gota, que proporciona el siguiente nodo de decisión del que salen dos ramas (para cada uno de sus valores: Sí, No), de las que cuelgan dos nodos de respuesta, ya que los datasets asociados tienen entropía nula.
Elección del tercer atributo de máxima ganancia:
Para el dataset $D_2=D_{PA=Baja}$ la entropía respecto del atributo objetivo es:
$$E(D_2,AT)= -\frac{3}{5} log_2(\frac{3}{5}) - \frac{2}{5} log_2(\frac{2}{5})=0.971$$
y las tres ganancias de información que se obtendrían con los atributos que quedan en el dataframe $D_2$ son:
-
Gota ( G ): $GI(G,D_2)=0.971-\frac{2}{5} 1 -\frac{3}{5} 0.918 = 0.020$
- Sí $[1+,1-]$: $E=1$
- No $[2+,1-]$: $E=0.918$
-
Urea en Sangre ( U ): $GI(G,D_2)=0.971-\frac{3}{5} 0.918-\frac{2}{5} 1-\frac{2}{5} 1=0.020$
- Alta $[0+,0-]$: No considerable.
- Normal $[2+,1-]$: $E=0.918$
- Baja $[1+,1-]$: $E=1$
-
Hipotiroidismo ( H ): $GI(H,D_2)= 0.971 -\frac{2}{5} 0-\frac{3}{5} 0=0.971$
- Sí $[0+,2-]$: $E=0$
- No $[3+,0-]$: $E=0$
La máxima ganancia se obtiene con Hipotiroidismo, que proporciona el siguiente nodo de decisión del que salen dos ramas (para cada uno de sus valores: Sí, No), de las que cuelgan dos nodos de respuesta, ya que los datasets asociados tienen entropía nula.
En este momento el árbol tiene ya todas sus ramas, por lo que el procedimiento ha terminado y se ha generado el siguiente árbol de decisión:
Extensiones de ID3
Como hemos visto, la heurística del ID3 es realmente el de una búsqueda (el camino de preguntas que mejor dividen el conjunto de datos inicial) y antepone los árboles que tengan atributos con mayor información más cerca de la raíz, y árboles más cortos, siguiendo la hipótesis de la navaja de Occam (preferir siempre las hipótesis más sencillas que describan los datos). También, por la heurística que emplea, favorece atributos con muchos valores.
Ya desde el principio Quinlan se dio cuenta de que el algoritmo ID3 era una primera aproximación que no cubría todos los casos que podíamos encontrar. Entre otros, destaca los siguientes problemas:
- Está bien definido para aquellos atributos que tienen un rango finito de valores (los que se llaman "atributos categóricos"), pero no se puede usar para otros casos, por ejemplo, cuando un atributo es numérico y puede tomar una cantidad infinita de posibles valores.
- Además, no siempre da el mejor árbol posible, ya que se basa en un método voraz que optimiza cada paso por separado, pero quizás hay otras opciones en el orden de preguntas que, aunque inicialmente no sean las más óptimas localmente y no aporten la mayor ganancia inmediata, sí pueden ofrecer un resultado global más óptimo en un recorrido a más larga distancia (muy parecido a lo que ocurre en todos los problemas de búsqueda).
- Por último, no se comporta bien con ejemplos para los que se desconoce el valor de alguno de sus atributos.
Para resolver estos problemas, el propio Quinlan propone el algoritmo C4.5 como una extensión del ID3, y poco después el C5.0 como versión más optimizada y completa (aunque también, con licencia comercial). Veremos a continuación cómo se pueden resolver los problemas anteriores de una forma relativamente sencilla (y aunque quizás no sean las opciones más óptimas, sí que podremos implementarlas muy sencillamente).
Respecto a la falta de información en algunos atributos de algunos ejemplos, la solución más directa es hacer uso en cada paso de aquellos ejemplos en los que sí hay información respecto al atributo que se está estudiando, de manera que tanto para el cálculo de la entropía como de las probabilidades asociadas se tengan en cuenta los que tienen ese atributo conocido. Es una ligera modificación del ID3 que se podría haber incluído directamente.
Respecto a encontrar variantes no voraces que den soluciones más óptimas globalmente, es un problema sin solución eficiente. Se sabe que este problema, el de la optimalidad global en los árboles de decisión, es un problema NP-completo, es decir, que está dentro de un importante conjunto para los que no se conoce solución eficiente (en el mejor de los casos, solo exponencial) y para los que es muy probable que dicha solución no exista. Así que podremos aplicar algunas heurísticas para mejorar un poco el ID3 (es lo que hacen C4.5 y C5.0), pero sabiendo que no conseguiremos una solución óptima en todos los casos.
Es mucho más interesante el tratamiento del problema de los atributos con infinitos valores. En el caso general, el problema consiste en ver qué pregunta se puede hacer respecto de estos atributos para dividir el conjunto de ejemplos de la forma más homogénea posible. Evidentemente, si disponemos de infinitos valores, se pueden hacer infinitas preguntas, por lo que el método de buscar entre todas ellas la mejor para la ganancia es inviable. Pero disponemos de otras soluciones, dependiendo de qué estructura tenga ese atributo:
Si el atributo es de tipo general (depende de varias dimensiones, o no es un conjunto ordenado), podemos aplicar métodos de clusterización (por ejemplo, algo parecido al algoritmo de las K-medias) para poder saber en qué bolsas se puede dividir de forma eficiente, y entonces utlilizar como preguntas la pertenencia a una bolsa o no. Con este método podemos fijar el número de bolsas a priori, o hacerlo de forma dinámica, por lo que realmente estamos proyectando el atributo con infinitos valores en un nuevo atributo categórico. Aunque este método también se puede utilizar cuando el atributo toma valores en un conjunto numérico ordenado, como por ejemplo los números naturales o reales, en estos casos existe otra solución que a veces puede funcionar mejor.- La solución que se puede dar para el caso númerico habitual es mucho más sencilla. Si tenemos los \(N\) ejemplos, y estos toman los valores \(\{v_1,\dots,v_N\}\) en el atributo continuo que estamos estudiando, podemos trabajar con las \(N\) preguntas posibles de la forma "\(x\leq v_i\)". Considerando únicamente estas \(N\) preguntas se suelen conseguir resultados suficientemente buenos, y hay métodos para que el cálculo de la ganancia de información se pueda hacer sencilla y reutilizando los casos ya calculados. En estos casos, una solución habitual pasa por ordenar los ejemplos en función de este atributo, y analizar dónde se producen los cambios de clasificación.
C4.5(D,T)
Para cada X ∈ Att, numérico:
Para cada v ∈ X:
Añadir atributo "≤ v"
Modificar D rellenando el nuevo atributo (booleano)
D = Eliminar X de D
Devolver ID3(D,T)
Hay otra consideración que puede ser interesante, y es el tratamiento de árboles que, debido a ruido en los datos, generan algún error en la clasificación incluso para los datos de entrenamiento. Uno de los tratamientos más habituales para reducir el error, o incluso para reducir el árbol sin afectar al error, es el que se conoce como Poda, y se realiza tras la construcción del árbol completo (hay métodos para realizar podas a medida que se va construyendo el árbol de decisión).
El método de poda del árbol consiste en generar el árbol tal y como hemos visto y, a continuación, analizar recursivamente, y desde las hojas, qué preguntas (nodos interiores) se pueden eliminar sin que se incremente el error de clasificación con el conjunto de test. Es decir, supongamos que se tiene un error calculado con todo el árbol de \(e_a\), y supongamos que se elimina un nodo interior cuyos sucesores son todos nodos hoja. Calculamos el error que se comete con este nuevo árbol sobre el conjunto de test. Si este error es menor que \(e_a\), entonces compensa eliminar el nodo y todos sus sucesores (hojas). Se continua recursivamente realizando este análisis hasta que no se puede eliminar ningún nodo interior adicional sin incrementar el error.
Esta poda también se podría realizar sobre el conjunto de reglas obtenidas a partir del árbol, ya que su uso es equivalente a trabajar con el árbol completo.
Como conclusión, desde el punto de vista de la búsqueda, ID3 busca hipótesis en un espacio de búsqueda completo. En cada momento, mantiene una hipótesis única, suponiendo que el clasificador se puede representar como una disyunción de conjunciones. Esto le hace perder oportunidades, como, por ejemplo, cómo seleccionar el siguiente ejemplo, pero le hace ser más eficiente. Al utilizar un procedimiento voraz, por ascenso de la colina, no realiza retrocesos por lo que puede caer en mínimos locales. Sin embargo, si no hay ruido en los datos y se tienen todos los atributos relevantes, se llega al mínimo global. Por otro lado, la heurística se basa en cálculos estadísticos sobre el conjunto de entrenamiento, lo que lo hace robusto al ruido: si un ejemplo es incorrecto, la estadística suavizará el efecto de ese ejemplo en el cálculo global.
Por todas estas características, ID3 ha sido una de las técnicas más utilizadas en las aplicaciones de análisis de datos y de aprendizaje automático aplicado a tareas tan diversas como predicción de enfermedades, control de robots, o caracterización de clientes en bancos o entidades de seguros, y hoy en día sigue teniendo relevancia al ser usado como unidad simple para la construcción de métodos combinados de aprendizaje, como son los Random Forest.