2, la entropía tiene valores entre 0 y 1. Mientras que si hay k clases, la entropía variará entre 0 y log2k. Se buscan árboles cuyos nodos tengan la menor entropía posible, es decir, la mayoría de sus ejemplos estarán incluidos en la misma clase. Se determina la ganancia de información que se produce al utilizar un atributo. Es decir, se mide la diferencia en el contenido de información en un nodo y el contenido de información después de dividirlo según los posibles valores de un atributo. La entropía esperada después de usar un atributo A en el árbol es: ∑∈⋅)A(Valoresvv)T(EntTT(3-2) donde Tv es el subconjunto de ejemplos de T con valor del atributo A igual a v. Por tanto, la ganancia de información esperada después de usar un atributo A será: ∑∈⋅−=)A(Valoresvv)T(EntTT)T(Ent)A,T(Ganancia (3-3) Desde el punto de vista de la entropía como medida de la heterogeneidad, la ganancia sería la reducción de la heterogeneidad en el conjunto global de datos al aplicar una división y se calcula como la diferencia entre la heterogeneidad del conjunto original T menos la heterogeneidad de cada uno de los subconjuntos creados ponderados por su representatividad en el conjunto original. Por tanto, el atributo seleccionado según este criterio será aquel que divida el conjunto de datos en subconjuntos más homogéneos. El criterio que se utiliza para seleccionar el atributo más adecuado se conoce como “índice de ganancia” y se calcula como: ∑=⋅−=)A(ValoresvvTTlogTT)A,T(GananciaIG12(3-4) El conjunto de datos se va subdividiendo según el criterio especificado hasta que todos los subconjuntos sean homogéneos, o bien, se cumpla una condición de parada establecida por el usuario. Condiciones de parada podrían ser que el subconjunto final tenga un número mínimo de elementos o que no se reduzca el error de clasificación en las divisiones siguientes. Existen numerosos ejemplos de la aplicación de los algoritmos C4.5 y C5.0 en la clasificación de imágenes. Levien et al. (1999) combinan un mapa de cambios con datos sobre el tipo y la densidad de la cobertura vegetal y datos extraídos de un MDE. Con el algoritmo C4.5 generan un mapa de cambios con una leyenda más exhaustiva que identificaba los tipos y causas de los cambios. También Friedl et al. (2002) generan mapas de usos del suelo globales clasificando imágenes MODIS combinadas con datos auxiliares mediante el algoritmo C4.5. 3.3.3.3.2.- Ruido, sobreajuste y poda La calidad de los datos de entrada es fundamental para la creación de un árbol de clasificación. Los datos reales están afectados frecuentemente de ruido y se pueden identificar distintos tipos de ruido o de errores: - Dos ejemplos con los mismos valores en los atributos y distinta clasificación. - Errores en los valores de los atributos. - Atributos irrelevantes para el proceso. Este ruido en los datos de entrenamiento afecta al algoritmo produciendo un árbol bastante complejo y que se ajusta en exceso a los datos de entrenamiento. Este sobreajuste del modelo a los datos implica que el modelo aprendido será demasiado específico, poco general y probablemente, poco preciso con datos distintos de los usados en el aprendizaje. Este comportamiento se hace más significativo cuanto mayor sea el número de datos erróneos existentes en los atributos o en las clases de los datos de aprendizaje, ya que el modelo se ajustará a los datos erróneos, perjudicando el comportamiento global del modelo. Para reducir este problema, los algoritmos de aprendizaje se modifican para que obtengan modelos más generales, y por lo tanto, menos concretos. En la terminología del aprendizaje automático este procedimiento se conoce como poda del árbol de decisión. Dentro de los métodos de poda se puede distinguir entre los que se realizan durante la construcción del árbol o los que se hacen analizando el árbol ya construido. En el primer caso se trata de cambiar la condición de parada en la construcción del árbol. En el segundo caso, se trata de eliminar nodos de abajo a arriba hasta un límite determinado. El algoritmo C.5 utiliza una combinación de ambos métodos de poda. 3.3.3.4.- Conversión de árboles de decisión en reglas Los árboles de decisión son difíciles de comprender, especialmente cuando los árboles son grandes. En la mayoría de los casos, es más sencillo la interpretación de reglas que la de los árboles completos. Por lo tanto, es conveniente convertir los árboles en reglas más aptas para su utilización en un sistema experto. En un árbol de decisión, las condiciones que debe cumplir un caso para ser clasificado por una hoja se pueden obtener recorriendo el trayecto de condiciones que sigue el caso desde la raíz hasta la hoja. Si el camino hasta cada hoja se transforma directamente en una regla, el conjunto de reglas resultante clasificaría de igual forma que como lo hace el árbol y se mantendría el carácter exhaustivo y exclusivo del árbol y el orden de aplicación de las reglas no sería relevante. Esta forma de convertir árboles en reglas no implica ninguna reducción del tamaño del árbol. Se puede eliminar alguna de las condiciones que forman las reglas, es decir, hacer las reglas más generales, sin que el árbol pierda precisión. Para ello, se comienza cuantificando el error que comete la regla completa y a continuación el error que cometería la regla eliminando una de las condiciones. Si el error de la regla con una condición eliminada fuera inferior al error obtenido con la regla completa, esa condición se eliminaría de forma permanente. Este proceso se repite hasta conseguir la simplificación de la regla sin pérdida de precisión. Las reglas así generadas ya no son mutuamente exclusivas y exhaustivas; por lo tanto, puede haber casos que satisfagan las condiciones de más de una regla, o de ninguna. Para solucionar el problema de asignar una clase a un objeto que cumple más de una regla, se plantean dos soluciones: la primera posibilidad es seleccionar la regla con un nivel de confianza mayor. La segunda alternativa es que cada una de las reglas que cumple el caso, emite un voto cuyo peso es el de su confianza. Se suman los pesos de las reglas que predicen la misma clase y la clase con más votos es la elegida como predicción. Esta segunda opción es la elegida por C5.0. La clase por defecto se asignará a aquellos casos que no cumplan ninguna regla y se elige aquella clase que contiene el mayor número de casos sin clasificar por ninguna regla. La confianza, o estimación de la precisión, de cada regla se expresa por medio del ratio Laplace, a partir del número de casos que cumplen la regla y del número de falsos positivos de la regla (casos que cumplen las condiciones de la regla pero que no pertenecen a la clase predicha por la regla): 21++−=nmnLaplaceratio (3-5) donde: n es el número de casos que cumplen una regla m es el número de falsos positivos de la regla 3.3.3.5.- Clasificación mediante árboles de decisión 3.3.3.5.1.- Clasificación con un solo árbol de decisión Una vez creado un árbol de clasificación, la clasificación de un objeto se realiza mediante la comprobación de las condiciones que cumple según el valor de sus atributos en el itinerario de condiciones establecido en el árbol, desde el inicio hasta llegar al final del mismo cuando se le asigna una clase. Cualquier objeto descrito por sus atributos será asignado a una clase final, ya que las condiciones del árbol son exhaustivas y todos los objetos cumplirán unas u otras. La precisión de la asignación realizada vendrá expresada por el ratio Laplace. 3.3.3.5.2- Métodos multiclasificadores Los métodos multiclasificadores surgieron con la intención de mejorar la precisión de las predicciones realizadas por varios métodos de clasificación. Estos métodos se basan en la definición de varias hipótesis que se combinan, normalmente por votación para obtener la hipótesis más fiable. La combinación de varios árboles de decisión será más fiable cuanto más precisos y distintos sean los árboles entre sí. El método bagging (Breiman, 1996 y Quinlan, 1996a) genera subconjuntos de entrenamiento seleccionando aleatoriamente una