Una de las ventajas de los árboles de decisión es que realizan de forma implícita un proceso de selección de las variables más significativas. Por ...

Una de las ventajas de los árboles de decisión es que realizan de forma implícita un proceso de selección de las variables más significativas. Por lo tanto, una vez construido el árbol, aquellos atributos que no intervienen en ninguna condición pueden descartarse, reduciéndose el tamaño del espacio de características descriptivas de los objetos. Las ventajas principales de los árboles de decisión son las siguientes: (Hernández Orallo et al., 2004) - Son aplicables a distintas tareas: clasificación, regresión, agrupamiento, etc. - Tratan con atributos continuos y discretos. - Son flexibles. No hacen ninguna suposición sobre la distribución de los datos, al contrario de lo que hacen algunos métodos estadísticos. Esta característica permite incorporar datos discretos a la clasificación de imágenes, independientemente de la distribución y la correlación que exista entre ellos. - Son fáciles de usar. - Son tolerantes al ruido, a atributos no significativos y a valores faltantes. - Las condiciones extraídas son inteligibles por el usuario - Existe software para su aplicación y en algunos casos es gratuito. - Permiten tratar relaciones no lineales entre características y clases. La clasificación de imágenes y la actualización de B.D. cartográficas 75 - Las muestras de aprendizaje de una misma clase no tienen que ser homogéneas entre sí como ocurre en un método estadístico. Con los árboles de decisión se pueden extraer reglas distintas para tipologías distintas dentro de una misma clase. Algunos de los software comerciales de tratamiento de imágenes más utilizados en teledetección como son ERDAS IMAGINE, ENVI o IDRISI disponen de herramientas para crear clasificadores basados en árboles de decisión. Tanto en ERDAS IMAGINE (Fig. 3-7), como en ENVI 4.2 (Fig. 3-8), la creación de los árboles se hace por medio de un interfaz gráfico donde se establecen las variables, reglas y clases que intervienen en el árbol. Ambos programas permiten utilizar como variables en las condiciones los valores de los píxeles en distintas bandas, así como índices entre imágenes u operaciones calculadas sobre modelos digitales del terreno. Estas variables pueden combinarse por medio de operadores lógicos o matemáticos para formar una regla. La clasificación de imágenes y la actualización de B.D. cartográficas 77 Entre las desventajas de los árboles de decisión cabría citar que no son tan precisos como otros métodos como son las redes neuronales. Además son “débiles”, es decir, son bastante dependientes de las muestras de ejemplos que se les suministra para el aprendizaje. Dos muestras distintas sobre la misma distribución pueden dar lugar a árboles bastante diferentes. La construcción del árbol de decisión constituye la fase de aprendizaje a partir de un conjunto de prototipos o muestras de aprendizaje. Constituye la fase más compleja y la que determina el resultado final. Es un proceso recursivo y cuyas líneas generales son: 1. El avance está basado en la partición de un nodo de acuerdo a alguna regla. Habitualmente se evalúa una condición sobre el valor de alguna variable. 2. Los prototipos que cumplen una condición se asignan a uno de los dos nodos hijo y los restantes, al otro. Cuando un nodo se divide, se convierte en un nodo intermedio. 3. La condición de parada se define para detener el proceso de partición de nodos. Si se cumple la condición de parada en un nodo, éste no se divide más y se convierte en un nodo hoja y se le asigna una clase a todos los prototipos en ese nodo. Entre los algoritmos más utilizados para la generación de árboles de decisión destacan CART, ID3, C4.5 y C5.0. 3.3.3.3.1.- Algoritmo C5.0 El algoritmo C5.0 está basado en los algoritmos ID3 y C4.5 desarrollados por Ross Quinlan (Quinlan, 1993). Este algoritmo y sus versiones anteriores son los más empleados para el aprendizaje de árboles de decisión orientados a la clasificación de imágenes (Li et al., 2000; Zhang y Liu, 2005). Está implementado en los software See5 (www.rulequest.com), Clementine (http://www.spss.com/clementine/) y en la versión C4.5 en otros software y librerías como IDRISI (http://www.clarklabs.org/) o WEKA (http://www.cs.waikato.ac.nz/ml/weka/ ). Este algoritmo requiere que cada uno de los datos de entrenamiento esté descrito por una tupla de atributos y por la clase a la que corresponde. Si se consideran los registros de una tabla como tuplas y los campos como atributos, se aprecia la adecuación de este algoritmo para tratar datos contenidos en bases de datos relacionales (Li et al., 2000). A continuación se describe este algoritmo que utiliza de forma iterativa una estrategia llamada “divide y vencerás”: Sea T el conjunto de casos de entrenamiento y las clases {C1, C2, … Ck}. Hay dos posibilidades para construir el árbol de decisión: - Todos los casos de T pertenecen a la misma clase Cj: El árbol de decisión para T es una hoja identificando la clase Cj. - T contiene casos que pertenecen a varias clases: Se divide T en subconjuntos que tienden a ser lo más homogéneos posible. Se elige una condición basada en un atributo que tiene uno o varios resultados mutuamente exclusivos {O1, O2,… On}. T se divide en subconjuntos T1, T2,…, Tn, donde Ti contiene todos los casos en T que tienen como resultado en la condición el valor Oi. El árbol de decisión para T consiste en un nodo de decisión que representa la condición, y una rama para cada posible resultado. Este proceso se aplica repetidamente a cada subconjunto de casos de entrenamiento hasta que se generan subconjuntos de datos pertenecientes a la misma clase, o hasta que no exista ninguna condición que mejore la clasificación. Las condiciones utilizadas por el algoritmo C5.0 pueden ser de dos tipos: - A =v siendo A un atributo discreto y v cada uno de sus posibles valores. Obteniéndose un subconjunto de datos para cada uno de los valores de A. - A ≤t para un atributo continuo. Obteniéndose dos resultados posibles verdadero y falso. Para encontrar el umbral t que maximiza el criterio de selección, se ordenan los casos en T según el valor de su atributo A. Cada par de valores consecutivos del atributo A, definen un posible umbral que sería la media de ambos. Se selecciona el umbral que da un mejor resultado en el criterio de selección. En el caso de dos casos cuyos valores del atributo A son consecutivos y pertenecen a la misma clase, el umbral entre ellos no puede generar una partición que maximice el criterio de selección, por lo que no sería necesario considerarlo (Quinlan, 1996b). El criterio de selección del atributo está basado en la medida de la entropía. La entropía es una medida de la heterogeneidad de un conjunto de datos. En teoría de la información, este término se utiliza para cuantificar la cantidad media de información necesaria para codificar la clasificación de un ejemplo en T. Así, por ejemplo, un conjunto cuyos datos pertenezcan todos a la misma clase, tendrá por entropía el valor nulo, mientras que el conjunto que tenga el mismo número de elementos en cada una de las clases posibles, su entropía será 1. Supongamos un conjunto T formado por p+n datos, donde P es el subconjunto de T formado por p elementos y cuya clase es “Positivo”, mientras que N es el subconjunto de T formado por n elementos cuya clase es “Negativo”. La entropía de T se calcula con la expresión (3-1). np nlog np n np plog np p)T(Ent + ⋅ + − + ⋅ + −= 22 (3-1) Si en lugar de dos clases, hubiera k clases, la expresión de la entropía sería equivalente pero con un sumando para cada clase. Cuando el número de clases es