A continuación se presenta el algoritmo del método ID3 para la construcción de árboles de decisión en función de un conjunto de datos previamente clasificados.
Función ID3
(R: conjunto de atributos no clasificados,
C: atributo clasificador,
S: conjunto de entrenamiento) devuelve un árbol de decisión;
Comienzo
Si S está vacío,
devolver un único nodo con valor falla;
Si todos los registros de S tienen el mismo valor para el atributo clasificador,
devolver un único nodo con dicho valor;
Si R está vacío, entonces
devolver un único nodo con el valor más frecuente del atributo clasificador en
los registros de S (Nota: habrá errores, es decir, registros que no estarán bien
clasificados en este caso);
Si R no está vacío, entonces
D atributo con mayor Ganancia(D,S) entre los atributos de R;
Sean {dj | j =1,2, .., m} los valores del atributo D;
Sean {Sj | j =1,2, .., m} los subconjuntos de S correspondientes a los valores de
dj respectivamente;
devolver un árbol con la raíz nombrada como D y con los arcos nombrados d1, d2,
.., dm que van respectivamente a los árboles
ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm);
Fin.
- Algoritmo ID3
La poda de los árboles de decisión se realiza con el objetivo de que éstos sean más comprensibles. Lo cual implica que tengan menos niveles y/o sean menos frondosos. La poda aplicada en el ID3 se realiza una vez que el árbol ha sido generado y es un mecanismo bastante simple: si de un nodo nacen muchas ramas, las cuales terminan todas en la misma clase, entonces se reemplaza dicho nodo por una hoja con la clase común. En caso contrario, se analizan todos los nodos hijos.
- Poda de los árboles de decisión
Para pasar a reglas de decisión, el ID3 recorre el árbol desde la raíz hasta las hojas y genera una regla por cada camino recorrido. El antecedente de cada regla estará compuesto por la conjunción de las pruebas de valor de cada nodo visitado, y la clase será la correspondiente a la hoja. El recorrido del árbol se basa en el recorrido de preorden (de raíz a hojas, de izquierda a derecha). Como se trabaja con árboles n-arios, este recorrido es único.
- Pasaje a reglas de decisión
Es necesario que todos los casos presentados al ID3 estén descriptos por los mismos atributos. Esto limita la aplicación del algoritmo, ya que no siempre se cuenta con toda la información necesaria. Imaginemos una base de datos histórica en la que se fueron agregando atributos a medida que se lo consideró necesario, para los primeros casos de la misma no se conocerán los valores de los nuevos atributos. El ID3 puede trabajar con atributos desconocidos, los considera como si fuesen un nuevo valor, por ello, se llega a la convención de que los valores desconocidos, deben expresarse con un "?" en los datos. El "?" constituye un nuevo valor posible para el atributo en cuestión.
- Atributos desconocidos
- Limitaciones del ID3
El ID3 puede aplicarse a cualquier conjunto de datos, siempre y cuando los atributos sean discretos. Este sistema no cuenta con la facilidad de trabajar con atributos continuos ya que analiza la entropía sobre cada uno de los valores de un atributo, por lo tanto, tomaría cada valor de un atributo continuo individualmente en el cálculo de la entropía, lo cual no es útil en muchos de los dominios. Cuando se trabaja con atributos continuos generalmente se piensa en rangos de valores y no en valores particulares.
Según Blurock, (1996).Existen varias maneras de solucionar este problema del ID3, como la agrupación de o la discretización de los mismos. El C4.5 resolvió el problema de los atributos continuos mediante la discretización.
En esta sección se presenta un árbol y un conjunto de reglas de decisión obtenidos utilizando el ID3, para ejemplificar su aplicación. Se requieren analizar parte de cuales hogares son pobres o no basándonos en la escolaridad, el hacinamiento, la vivienda, los servicios básicos y la dependencia económica. Los datos que se utilizarán en este ejemplo, se presentan en la siguiente tabla:
Escolaridad
Hacinamiento
Vivienda
- Servicios
Dependencia
Condición
No Asisten
Hay
Adecuada
Con serv
Alta depend
Pobre
No Asisten
No hay
Adecuada
Sin serv
Alta depend
Pobre
Asisten
No hay
Inadecuada
Sin serv
Sin depend
Pobre
No Asisten
No hay
Adecuada
Sin serv
Sin depend
Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
No hay
Inadecuada
Sin serv
Sin depend
Pobre
No Asisten
No hay
Adecuada
Con serv
Alta depend
Pobre
No Asisten
Hay
Adecuada
Con serv
Sin depend
Pobre
No Asisten
Hay
Adecuada
Con serv
Sin depend
Pobre
No Asisten
Hay
Inadecuada
Con serv
Alta depend
Pobre
No Asisten
Hay
Adecuada
Con serv
Sin depend
Pobre
Asisten
Hay
Adecuada
Con serv
Alta depend
Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
Hay
Adecuada
Con serv
Alta depend
Pobre
Asisten
No hay
Inadecuada
Sin serv
Sin depend
Pobre
En el caso de este ejemplo, los árboles y las reglas obtenidas utilizando la ganancia y la proporción de ganancia son iguales.
Construcción del árbol de decisión
A partir de todos los datos disponibles, el ID3 analiza todas las divisiones posibles según los distintos atributos y calcula la ganancia y/o la proporción de ganancia. Se comienza analizando el atributo Escolaridad.
El atributo Escolaridad tiene la siguiente distribución de datos:
Asisten
No Asisten
Total General
No Pobre
5
0
5
Pobre
5
8
13
Total General
10
8
18
Para calcular la ganancia y, por lo tanto, también la proporción de ganancia, es necesario calcular la entropía del conjunto. Entonces,
Se calcula ahora la entropía que tendrían los conjuntos resultante de la división de datos según este atributo.
=
Ahora se calcula la ganancia resultante de dividir al subconjunto según el atributo Escolaridad, se tiene:
Para calcular la proporción de ganancia se debe conocer primero la información de la división que se calcula como:
I_división(S) = –
= 
= 0.9910 bits.Finalmente, calculamos la proporción de ganancia.
Proporción de ganancia (S) =
= 0.2995 bitsDe la misma manera en que se calculó la ganancia y proporción de ganancia para el caso anterior, se calcula para el atributo Hacinamiento los valores son los siguientes:
Ganancia = 0.2449 bits Proporción de ganancia = 0.2540 bits
Para el caso del atributo Vivienda se obtienen los siguientes valores:
Ganancia = 0.1210 bits Proporción de ganancia = 0.1584 bits
Para el atributo Servicios los valores son los siguientes:
Ganancia = 0.1581 bits Proporción de ganancia = 0.1855 bits
finalmente para el atributo Dependencia los valores son los siguientes:
Ganancia = 0.1991 bits Proporción de ganancia = 0.2168 bits
Una vez que se han calculado las ganancias y proporciones de ganancia para todos los atributos disponibles, se debe elegir el atributo según el cual se dividirá a este conjunto de datos. Tanto en el caso de la ganancia como en el de la proporción de ganancia, el mejor atributo para la división es aquel que la maximiza. En este ejemplo, la división según el atributo Escolaridad es el que mayor ganancia y proporción de ganancia ofrece. Esto significa que el nodo raíz del árbol será un nodo que evalúa el atributo Escolaridad.
La figura No 3 esquematiza la construcción de un árbol de decisión utilizando el ID3 para el conjunto de datos en cuestión. La figura No 4 presenta el árbol de decisión obtenido.
Transformación a reglas de decisión
Para pasar un árbol de decisión a reglas de decisión, el ID3 lo recorre en preorden y cada vez que llega a una hoja, escribe la regla que tiene como consecuente el valor de la misma, y como antecedente, la conjunción de las pruebas de valor especificados en todos los nodos recorridos desde la raíz para llegar a dicha hoja. Al analizar el pasaje del árbol de la figura No 4 a reglas de decisión, el recorrido del árbol comienza por la raíz "Escolaridad" continúa por los nodos "Vivienda" y "Hacinamiento" hasta llegar a la hoja "No Pobre". La regla generada para este recorrido será:
Al seguir el recorrido preorden, se llega a continuación a la hoja "Pobre", obteniendo en este caso la siguiente regla:
recorriendo en este sentido el árbol, el resto de las reglas obtenidas se muestran a continuación:
Figura 3
Esquema de la construcción de un árbol de decisión utilizando el ID3
Figura 4
Árbol de decisión obtenido con el ID3
El C4.5 se basa en el ID3, por lo tanto, la estructura principal de ambos métodos es la misma. El C4.5 construye un árbol de decisión mediante el algoritmo "divide y reinarás" y evalúa la información en cada caso utilizando los criterios de entropía y ganancia o proporción de ganancia, según sea el caso. A continuación, se explicarán las características particulares de este método que lo diferencian de su antecesor.
- C4.5
El algoritmo del método C4.5 para la construcción de árboles de decisión a grandes rasgos es muy similar al del ID3. Varía en la manera en que realiza las pruebas sobre los atributos, tal como se detalla en las secciones siguientes.
Función C4.5
(R: conjunto de atributos no clasificadores,
C: atributo clasificador,
S: conjunto de entrenamiento) devuelve un árbol de decisión;
Comienzo
Si S está vacío,
devolver un único nodo con Valor Falla;
Si todos los registros de S tienen el mismo valor para el atributo clasificador,
devolver un único nodo con dicho valor;
Si R está vacío, entonces
devolver un único nodo con el valor más frecuente del atributo clasificador en
los registros de S (Nota: habrá errores, es decir, registros que no estarán bien
clasificados en este caso);
Si R no está vacío, entonces
D atributo con mayor Proporción de Ganancia(D,S) entre los atributos de R;
Sean {d j | j =1,2, .., m} los valores del atributo D;
Sean {Sj | j =1,2, .., m} los subconjuntos de S correspondientes a los valores de
dj respectivamente;
devolver un árbol con la raíz nombrada como D y con los arcos nombradosd1,d2,.., dm que van respectivamente a los árboles
C4.5(R-{D}, C, S1), C4.5(R-{D}, C, S2), .., C4.5(R-{D}, C, Sm);
Fin.
- Algoritmo C4.5
- Características particulares del C4.5
- Resolución de un ejemplo utilizando el ID3
Según Quinlan, (1993). En cada nodo, el sistema debe decidir cuál prueba escoge para dividir los datos. Los tres tipos de pruebas posibles propuestas por el C4.5 son:
- La prueba "estándar" para los atributos discretos, con un resultado y una rama para cada valor posible del atributo.
- Una prueba más compleja, basada en un atributo discreto, en donde los valores posibles son asignados a un número variable de grupos con un resultado posible para cada grupo, en lugar de para cada valor.
- Si un atributo A tiene valores numéricos continuos, se realiza una prueba binaria con resultados A ≤Z y A > Z, para lo cual debe determinarse el valor límite Z.
Todas estas pruebas se evalúan de la misma manera, mirando el resultado de la proporción de ganancia, o alternativamente, el de la ganancia, resultante de la división que producen. Ha sido útil agregar una restricción adicional: para cualquier división, al menos dos de los subconjuntos Ti deben contener un número razonable de casos. Esta restricción, que evita las subdivisiones casi triviales es tenida en cuenta solamente cuando el conjunto T es pequeño.
Según Quinlan, (1993). Las pruebas para valores continuos trabajan con un valor límite arbitrario. El método utilizado para ello por el C4.5 es muy simple. Primero, los casos de entrenamiento T se ordenan según los valores del atributo A continuo que está siendo considerado. Existe un número finito de estos valores.
Sean {v1, v2,. . ., vm} los valores que toma el atributo A. Cualquier valor límite entre vi y vi +1 tendrá el mismo efecto al dividir los casos entre aquellos cuyo valor para A pertenece al subconjunto {v1, v2,. . .,vi} y aquellos cuyo valor pertenece a {vi+1, vi+2,. . ., vm}. Entonces, existen sólo m – 1 divisiones posibles de el valor de A y todas son examinadas. Al estar ordenados, las sucesivas pruebas para todos los valores, pueden realizarse en una única pasada.
Típicamente se elige el punto medio del intervalo como valor límite representativo, entonces el iésimo valor límite sería:
C4.5 se diferencia de otros algoritmos en que elige el mayor valor de A en todo el conjunto de casos de entrenamiento que no excede el punto medio presentado, en lugar del punto medio en sí mismo, como valor límite; de esta manera se asegura que todos los valores límites que aparezcan en el árbol y/o las reglas ocurran al menos una vez en los datos.
El método utilizado para la binarización de atributos tiene una gran desventaja. Mientras que todas las operaciones de construcción de un árbol de decisión crecen linealmente con el número de casos de entrenamiento, el ordenamiento de d valores continuos crece proporcionalmente a d x log(d). Entonces, el tiempo requerido para construir un árbol a partir de un gran conjunto de datos de entrenamiento, puede estar dominado por el ordenamiento de datos con valores continuos.
- Pruebas sobre atributos continuos
- Atributos desconocidos
C4.5 asume que todos los resultados de pruebas desconocidos se distribuyen probabilísticamente según la frecuencia relativa de los valores conocidos. Un caso (posiblemente fraccional) con un valor desconocido se divide en fragmentos cuyos pesos son proporcionales a dichas frecuencias relativas, dando por resultado que un caso puede seguir múltiples caminos en el árbol. Esto se aplica tanto cuando los casos de entrenamiento se dividen durante la construcción del árbol, como cuando el árbol se utiliza para clasificar casos.
La modificación del criterio de ganancia es bastante directa. La ganancia de una prueba mide la información sobre la pertenencia a una clase que puede esperarse como resultado de partir un conjunto de datos de entrenamiento, calculada al restar la información que se espera que sea necesaria para identificar la clase de un objeto después de la partición a la misma cantidad antes de la partición. Es evidente que una prueba no puede proveer información de pertenencia a una clase si no se conoce el valor de un atributo.
Sea T el conjunto de datos de entrenamiento y X una prueba basada en un atributo A, supongamos que el valor de A se conoce únicamente en una fracción F de casos en T. Sean I(T) e IX(T) calculadas según la ecuación
, excepto que sólo se tienen en cuenta los casos para los cuales el valor de A es conocido. La definición de ganancia puede corregirse a:
o, en otras palabras, la ganancia aparente de mirar a los casos con valores conocidos, multiplicada por la fracción de dichos casos en el conjunto de entrenamiento. El cálculo de la proporción de ganancia se calcula con la siguiente ecuación
. La definición de información de la división puede modificarse de manera similar, considerando los casos con valores desconocidos como un grupo más, entonces, si una prueba tienen n resultados, su información de la división se calcula como la prueba dividido n+1 subconjuntos.- Evaluación de las pruebas
-
Una prueba puede seleccionar del conjunto de pruebas posibles, como antes, pero utilizando las versiones modificadas de ganancia e información de la división. Si la prueba X con resultados O1, O2, …, On es escogida y tiene algunos valores desconocidos para algunos de los datos de entrenamiento, el concepto de particionamiento debe ser generalizado, según un criterio probabilístico.
Cuando un caso T con un resultado conocido Oi es asignado al subconjunto Ti, esto significa que la probabilidad de que el caso pertenezca a Ti es 1 y de que pertenezca a todos los otros subconjuntos es 0. Cuando el resultado es desconocido, sólo se puede realizar una afirmación estadística más débil.
Entonces, se asocia con cada caso del subconjunto Ti un peso representando la probabilidad de que el caso pertenezca a cada subconjunto. Si el resultado para el caso es conocido, entonces el peso es 1; si el caso tiene un resultado desconocido, entonces el peso es simplemente la probabilidad del resultado Oi en este punto. Cada subconjunto Ti es una colección de casos fraccionales posibles, tal que |Ti| debe ser reinterpretada como la suma de los pesos fraccionales de los casos pertenecientes al subconjunto. Los casos de entrenamiento en T pueden tener pesos no unitarios, ya que T puede ser el resultado de una partición previa. Entonces, en general, un caso de T con peso p cuyo resultado no se conoce, es asignado a cada subconjunto Ti con peso: P x probabilidad_de_resultado Oi
- Partición del conjunto de entrenamiento
Se toma un enfoque similar cuando el árbol de decisión es utilizado para clasificar un caso. Si en un nodo de decisión el atributo relevante no se conoce, de manera tal que el resultado de la prueba no puede determinarse, el sistema explora todos los resultados posibles y combina aritméticamente las clasificaciones resultantes. Como para cada atributo pueden existir múltiples caminos desde la raíz del árbol hasta las hojas, una "clasificación" es una distribución de clases más que una única clase. Cuando la distribución de clases total para un caso nuevo ha sido establecida de esta manera, la clase con la probabilidad más alta, es asignada como "la" clase predicha.
La información de la división aún se determina a partir del conjunto de entrenamiento completo y es mayor, ya que existe una categoría extra para los valores desconocidos. Cada hoja en el árbol de decisión resultante tiene asociados dos valores: (N/E). N es la suma de los casos fraccionales que llegan a la hoja; y E es el número de casos cubiertos por la hoja, que no pertenecen a la clase de la misma.
- Clasificación de un nuevo caso
- Poda de los Árboles de Decisión
Según Mitchell, (2000). El método recursivo de particionamiento para construir los árboles de decisión descrito anteriormente, subdividirá el conjunto de entrenamiento hasta que la partición contenga casos de una única clase, o hasta que la prueba no ofrezca mejora alguna. Esto da como resultado, generalmente, un árbol muy complejo que sobre ajusta los datos al inferir una estructura mayor que la requerida por los casos de entrenamiento . Además, el árbol inicial generalmente es extremadamente complejo y tiene una proporción de errores superior a la de un árbol más simple. Mientras que el aumento en complejidad se comprende a simple vista, la mayor proporción de errores puede ser más difícil de visualizar.
Para entender este problema, supongamos que tenemos un conjunto de datos dos clases, donde una proporción p ≥ 0.5 de los casos pertenecen a la clase mayoritaria. Si un clasificador asigna todos los casos con valores indeterminados a la clase mayoritaria, la proporción esperada de error es claramente 1 – p. Si, en cambio, el clasificador asigna un caso a la clase mayoritaria con probabilidad p y a la otra clase con probabilidad 1 – p, su proporción esperada de error es la suma de:
- la probabilidad de que un caso perteneciente a la clase mayoritaria sea asignado a la otra clase, p x (1– p)
- la probabilidad de que un caso perteneciente a la otra clase sea asignado a la clase mayoritaria, (1 – p) x p
que da como resultado 2 x p (1 – p). Como p es al menos 0.5, esto es generalmente superior a 1 – p, entonces el segundo clasificador tendrá una mayor proporción de errores. Un árbol de decisión complejo tiene una gran similitud con este segundo tipo de clasificador. Los casos no se relacionan a una clase, entonces, el árbol manda cada caso al azar a alguna de las hojas.
Un árbol de decisión no se simplifica borrando todo el árbol a favor de una rama, sino que se eliminan las partes del árbol que no contribuyen a la exactitud de la clasificación para los nuevos casos, produciendo un árbol menos complejo, y por lo tanto, más comprensible.
Generalmente, la simplificación de los árboles de decisión se realiza descartando uno o más subárboles y reemplazándolos por hojas. Al igual que en la construcción de árboles, las clases asociadas con cada hoja se encuentran al examinar los casos de entrenamiento cubiertos por la hoja y eligiendo el caso más frecuente. Además de este método, el C4.5 permite reemplazar un subárbol por alguna de sus ramas.
Al suponer que fuera posible predecir la proporción de errores de un árbol y sus subárboles. Esto inmediatamente llevaría al siguiente método de poda: "Comenzar por las hojas y examinar cada subárbol. Si un reemplazo del subárbol por una hoja o por su rama más frecuentemente utilizada, lleva a una proporción de errores predicha menor, entonces podar el árbol de acuerdo a ello, recordando que las proporciones de errores predichas para todos los subárboles que lo contienen se verán afectadas". Como la proporción de errores predicha para un árbol disminuye si disminuyen las proporciones de errores predichas en cada una de sus ramas, este proceso generaría un árbol con una proporción de errores predicha mínima.
¿Cómo se puede predecir la proporción de errores?. Calcular la proporción de errores a partir de los datos de entrenamiento para los cuales el árbol fue construido, no es un estimador útil, ya que en lo que respecta al conjunto de entrenamiento, la poda siempre aumenta la proporción de errores.
El C4.5 utiliza únicamente el conjunto de entrenamiento a partir del cual se construyó el árbol. La estimación de la proporción de errores pura se ajusta para reflejar su propia tendencia. El método utilizado por el C4.5 se describe a continuación:
Cuando una hoja cubre N casos de entrenamiento, E de ellos en forma errónea, el estimador de la proporción de errores de resubstitución para dicha hoja es N/E. como E "eventos" en N pruebas. Si el conjunto de N casos de entrenamiento se tomase como una muestra (lo cual, por supuesto, no es cierto), se pregunta qué nos dice este resultado acerca de la probabilidad de un evento (error) en la totalidad de la población de casos cubiertos por la hoja. La probabilidad de error no puede determinarse de forma exacta, pero cuenta con límites de confianza. Para un límite de confianza CF, el límite superior de esta probabilidad puede encontrarse a partir de los límites de confianza para la distribución binomial; el límite superior se expresa como UCF(E,N). Como en la distribución binomial los límites superior e inferior son simétricos, la probabilidad de que el promedio real de errores exceda UCF(E,N),es CF/2. El C4.5 simplemente iguala el estimador de error predicho de la hoja con su límite superior, bajo el argumento de que el árbol fue construido para minimizar la
proporción de error observada. Aunque los fundamentos de esta heurística son cuestionables y violan algunos principios estadísticos, las estimaciones producidas presentan frecuentemente resultados aceptables.
Para simplificar el cálculo, las proporciones de error para las hojas y subárboles se computan asumiendo que fueron utilizados para clasificar un conjunto de nuevos casos del mismo tamaño del conjunto de entrenamiento. Entonces, una hoja que cubre N casos de entrenamiento con un estimador de error predicho de UCF(E,N) generaría N x UCF(E,N) errores predichos. Análogamente, la cantidad de errores predichos asociados con un subárbol es la suma de los errores predichos para cada una de sus ramas.
Estimación de la Proporción de Errores para los Árboles de Decisión
Una vez podados, las hojas de los árboles de decisión generados por el C4.5 tendrán dos números asociados: N y E. N es la cantidad de casos de entrenamiento cubiertos por la hoja, y E es la cantidad de errores predichos si un conjunto de N nuevos casos fuera clasificados por el árbol. La suma de los errores predichos en las hojas, dividido entre el número de casos de entrenamiento, es un estimador inmediato del error de un árbol podado sobre nuevos casos.
- Poda en Base a Errores
Se requieren analizar parte de cuales hogares son pobres o no basándonos en la escolaridad, el hacinamiento, la vivienda, los servicios básicos y la dependencia económica. Los datos que se utilizan en el sistema se presentan en la siguiente tabla:
Escolaridad
Hacinamiento
Vivienda
- Servicios
Dependencia
Condicion
?
Hay
Adecuada
Con serv
Alta depend
Pobre
No Asisten
No hay
Adecuada
Sin serv
Alta depend
Pobre
Asisten
No hay
Inadecuada
Sin serv
Sin depend
Pobre
No Asisten
No hay
Adecuada
Sin serv
Sin depend
Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
No hay
Inadecuada
Sin serv
Sin depend
Pobre
No Asisten
No hay
Adecuada
Con serv
Alta depend
Pobre
No Asisten
Hay
Adecuada
Con serv
Sin depend
Pobre
No Asisten
Hay
Adecuada
Con serv
Sin depend
Pobre
No Asisten
Hay
Inadecuada
Con serv
Alta depend
Pobre
No Asisten
Hay
Adecuada
Con serv
Sin depend
Pobre
Asisten
Hay
Adecuada
Con serv
Alta depend
Pobre
Asisten
No hay
Adecuada
Con serv
Sin depend
No Pobre
Asisten
Hay
Adecuada
Con serv
Alta depend
Pobre
Asisten
No hay
Inadecuada
Sin serv
Sin depend
Pobre
Este es el mismo conjunto de datos que fue utilizado para construir un árbol utilizando el ID3 con la diferencia que el valor del atributo "Escolaridad para el primer caso es desconocido.
Construcción del árbol de decisión
En este caso, la distribución de datos para el atributo "Escolaridad" es la siguiente :
Desconocido
Asisten
No Asisten
Total General
No Pobre
0
5
0
5
Pobre
1
5
7
13
Total General
1
10
7
18
Primero se calcula la entropía del conjunto, no se debe tener en cuenta los atributos desconocidos. Entonces se trabaja sobre un total de 17 casos.
Se calcula ahora la entropía que tendrían los conjuntos resultante de la división de datos según este atributo.
=
Ahora se calcula la ganancia resultante de dividir al subconjunto según el atributo Escolaridad, tendremos:
Al calcular la información de la división, se debe tener en cuenta una categoría extra para el valor desconocido para el atributo. La información de la división que se calcula como:
I_división(S)= –
= 
= 1.2326 bits.
Finalmente, se calcula proporción de ganancia.
Proporción de ganancia (S) =
= 1.3015bitsDe la misma manera en que se calculó la ganancia y proporción de ganancia para el caso anterior, se calcula para el atributo Hacinamiento los valores son los siguientes:
Ganancia = 0.2449 bits Proporción de ganancia = 0.2540 bits
Para el caso del atributo Vivienda se obtienen los siguientes valores:
Ganancia = 0.1210 bits Proporción de ganancia = 0.1584 bits
Para el atributo Servicios los valores son los siguientes:
Ganancia = 0.1581 bits Proporción de ganancia = 0.1855 bits
finalmente para el atributo Dependencia los valores son los siguientes:
Ganancia = 0.1991 bits Proporción de ganancia = 0.2168 bits
Al igual que el ID3, conviene dividir el conjunto según el atributo "Escolaridad" tanto si se trabaja con la ganancia o con la proporción de ganancia. Al dividir los 18 casos para continuar con la construcción del árbol, los 17 casos para los que el valor de "Escolaridad" es conocido, no presentan problemas y se reparten según el valor de "Escolaridad".mientras que el caso en que no se conoce el valor de "escolaridad, se reparte entre los conjuntos que tienen "Asisten"y "No Asisten" con los pesos 10/17 y 7/17 respectivamente.
Por ejemplo la división de los datos para el atributo "Asisten" del atributo "Escolaridad, los datos que se tienen en cuenta en este caso son:
La distribución de datos para el atributo "Hacinamiento" es:
Desconocido
Hay
No Hay
No pobre
0
0
5
Pobre
0
0.5
3
Totales
0
0.5
8
Con estos datos se obtienen los siguientes valores:
Ganancia = 0.0791 Proporción de ganancia = 0.2451
Para el caso del atributo "Vivienda" se obtienen los siguientes valores:
Ganancia = 0.6930 Proporción de ganancia = 0.7398
Para el atributo "Servicios" los valores son los siguientes:
Ganancia = 0.6930 Proporción de ganancia = 0.7398
Finalmente para el atributo "Dependencia" los valores son los siguientes:
Ganancia = 0.0791 Proporción de ganancia = 0.2451
En este caso se observa que la división de los datos no ofrece ninguna mejora, por lo tanto, se colapsa el árbol a la hoja "Pobre", que es la que mayor peso tiene. La cantidad de casos cubiertos por la hoja, es decir, el N asociado a la misma es 8 y el E asociado a la hoja es 0.. a continuación se muestra el árbol obtenido.
El C4.5 analiza los errores predichos en cada uno de los subárboles y ramas del árbol generado para analizar si es conveniente simplificarlo. En este caso, el error total predicho para el árbol estará dado por:
=
.El error predicho para el árbol simplificado es menor que el error predicho para el árbol generado. Entonces, el C4.5 poda el árbol a la siguiente hoja:
Generalización de reglas
Al rescribir el árbol completamente en forma de un conjunto de reglas, una por cada hoja del árbol, no se obtendrá una estructura más simple que el árbol en sí. Sin embargo, los antecedentes de las reglas pueden contener condiciones irrelevantes, con lo cual la regla puede ser generalizada eliminando dichas condiciones.
Para decidir cuándo una condición debe eliminarse, se utiliza el siguiente método. Sea R una regla de la forma:
Si A entonces clase C
y sea una regla más general R–
Si A– entonces clase C,
donde A– se obtiene borrando la condición X de las condiciones de A. La evidencia para la importancia de X debe encontrarse en los casos de entrenamiento utilizados para la construcción del árbol de decisión.
Cada caso que satisface el antecedente más corto A– pertenece o no a la clase C, y satisface o no la condición X. Los números de casos en cada uno de estos cuatro grupos pueden organizarse en una tabla de contingencias de 2 x 2:
Satisface la condición X
No satisface la condición X
Clase C Otras clases
Y1
E1
Y2
E2
¿Qué significan los valores de la tabla?:
Y1+E1: casos que satisfacen A– y también X, por lo tanto, también están cubiertos por la regla original R, E1 de ellos erróneamente ya que pertenecen a clases distintas a C.
Y2+E2: casos que satisfacen A– pero no X que serán cubiertos por la regla generalizada R– pero no por la regla original. E2 de estos casos serán clasificados erróneamente.
Y1+Y2 + E1+E2: número total de casos cubiertos por R–
Según Quinlan, (1987), de acuerdo a varios experimentos desarrollados para medir la importancia de la tabla de contingencia al decidir si una condición X debe ser eliminada o no, se encontró que se obtienen mejores resultados utilizando una estimación pesimista de la precisión de las reglas R y R- sobre nuevos casos. No es muy probable que una hoja que cubre N casos con E errores tenga una proporción de
error tan baja como E/N al clasificar nuevos casos. En lugar de utilizar el estimador E/N al estimar la proporción real de errores de una hoja como el límite superior UCF(E,N) del intervalo de confianza para algún nivel de confianza CF. Si se reemplazan estos valores por los de las reglas R y R- se obtendrán los siguientes estimadores pesimistas:
UCF(E1,Y1 + E1 ) para la regla R
UCF(E1 + E2, Y1 + Y2 + E1 + E2) para la regla R-
Si UCF(E1 + E2, Y1 + Y2 + E1 + E2) <= UCF(E1,Y1 + E1 ) entonces tiene sentido eliminar la condición X.
Durante el proceso de generalización será necesario eliminar más de una condición. En lugar de analizar todos los subconjuntos posibles de condiciones que podrían eliminarse, el sistema de C4.5 realiza una eliminación directa golosa de todas las reglas que pueden eliminarse por el método descrito, se elimina aquella que produce la menor proporción pesimista de error en la regla generalizada. Como en todos las búsquedas golosas el hecho de buscar el mínimo en cada paso no nos asegura llegar al mínimo global.
- Conjuntos de Reglas
- Construcción de un árbol de decisión utilizando el C4.5
El proceso de generalización de las reglas se repite para todos los caminos del árbol. Con lo cual, las reglas derivadas de algunos caminos pueden tener una proporción de error inaceptable o pueden solaparse con otras derivadas de distintos caminos. Por lo tanto, se puede afirmar que el proceso de generalización produce menos reglas que el número de hojas del árbol, y además las reglas dejan de ser mutuamente excluyentes y exhaustivas. Un caso puede satisfacer los antecedentes de más de una regla o, si se descartan reglas por tener una alta proporción de errores, de ninguna regla. En este último caso debe existir una condición por defecto que indique cómo proseguir. Para resolver estos conflictos el C4.5 plantea una solución simple: ordenar las reglas y la primera regla que cubre el caso se toma como la regla operativa. Es necesario, entonces, establecer prioridades para el ordenamiento de las reglas y decidir la clasificación por defecto a utilizar.
Para establecer las prioridades se siguió un método propuesto por Michie, (1986) que determina que todas las reglas de una misma clase deben aparecer juntas y estos subconjuntos de clases son los que están ordenados en lugar de las reglas en sí. Este agrupamiento hace que las reglas sean más entendibles y tiene la ventaja que el ordenamiento de las reglas en particular no es importante.
Al suponer que del conjunto de reglas se elige un subconjunto S de reglas que cubren la clase C. La performance de este subconjunto puede medirse mediante el número de casos de entrenamiento cubiertos por S que no pertenecen a la clase C (falsos positivos) y el número de casos de entrenamiento de la clase C que no son cubiertos por ninguna regla de S (falsos negativos). Según Rissanen, (1983), el valor del subconjunto S se mide utilizando el Principio de Longitud de Descripción Mínima este principio puede expresarse de la siguiente manera: Un emisor y un receptor cuentan con copias idénticas de un conjunto de casos de entrenamiento, pero los casos del emisor también especifican la clase de cada caso, mientras que los casos del receptor no tienen información de las clases. El emisor debe comunicar esta información faltante al receptor mediante la transmisión de una teoría de clasificación junto con las excepciones a la misma. El emisor puede elegir la complejidad de la teoría que envía (una teoría relativamente simple con muchas excepciones, o una teoría muy compleja con pocas excepciones). Este principio afirma que la mejor teoría derivable de los datos de entrenamiento minimizará la cantidad de bits necesarios para codificar el mensaje completo consistente de la teoría y sus excepciones.
La información a transmitir es la identidad en los casos de entrenamiento que pertenecen a la clase C, utilizando un esquema de codificación para la teoría (subconjunto S de reglas) y sus excepciones. El esquema utilizado por el C4.5 es aproximado ya que en lugar de utilizar un método de codificación en particular, trata de encontrar un límite inferior al número de bits. Se puede resumir de la siguiente
manera:
- Para codificar una regla, se debe especificar cada antecedente. El consecuente no necesita ser codificado, porque todas las reglas del subconjunto pertenecen a la misma clase C. Existe una pequeña complicación: las condiciones deben enviarse en algún orden, pero el orden no importa porque las condiciones pertenecen a una conjunción. Si existen x condiciones en el antecedente, existen x! ordenamientos posibles que podrían enviarse, todos equivalentes del punto de vista de la especificación de la regla. Por lo tanto, la cantidad de bits requerida para enviar cualquier ordenamiento en particular debe ser reducida en un "crédito" de log2(x!).
- La codificación de un conjunto de reglas requiere la suma de los bits para codificar cada regla, menos un crédito similar para el ordenamiento de las reglas (ya que todos los ordenamientos de reglas para una misma clase son equivalentes)
- Las excepciones se codifican indicando cuáles de los casos cubiertos por las reglas S son falsos positivos y cuáles falsos negativos. Si las reglas cubren r de los n casos de entrenamiento, con fp falsos positivos y fn falsos negativos, la cantidad de bits necesarios para codificar la excepción es:
El primer término indica los bits necesarios para indicar los falsos positivos entre los casos cubiertos por las reglas y el segundo término indica los falsos negativos entre los casos no cubiertos por las reglas. El valor de un subconjunto S en particular se mide con la suma de las longitudes de codificación para las reglas y excepciones, a menor suma, mejor teoría.
En la práctica, los métodos de codificación tienden a sobrestimar la cantidad de bits requeridos para codificar una teoría relativa al conjunto de excepciones. Esto se explica por el hecho de que los conjuntos de atributos generalmente son redundantes, por lo que diferentes teorías pueden ser funcionalmente idénticas. Como la función de una teoría para una clase es identificar un subconjunto de casos de entrenamiento, diferentes reglas que identifiquen al mismo conjunto son intercambiables, aún cuando hayan sido codificadas de manera distinta. Para compensar este efecto, el sistema utiliza la suma ponderada:
Bits de excepción + W X bits de teoría
donde W < 1.
El valor apropiado de W dependerá de la probabilidad de que dos teorías representen los mismos casos, lo cual dependerá del grado de redundancia en los datos. C4.5 utiliza el valor 0.5 por defecto para W, pero puede ajustarse a un valor menor si se encuentra un gran grado de redundancia en los datos. Sin embargo, no se ha encontrado que el resultado del algoritmo dependa en gran medida del valor de W.
Entonces, para enviar las reglas debe encontrarse un subconjunto S de reglas para la clase C que minimice esta codificación total. Esto es similar a la generalización de reglas descripta anteriormente, pero en este caso la eliminación golosa no parece ser efectiva. En cambio, el sistema analiza todos los subconjuntos posibles de reglas para una clase, si no son demasiados, y utiliza recocido simulado en caso contrario. En este último caso, el sistema repetidamente elige una regla al azar y considera incluirla en el subconjunto S (si aún no pertenece al mismo), o eliminarla de S (si ya pertenece). Esta acción producirá un cambio B en el total de bits necesario para codificar el subconjunto y las excepciones y, si el caso es beneficioso, entonces se lo acepta inmediatamente. Si la acción incrementa la longitud total de la codificación tal que B es positivo, el cambio se acepta con una probabilidad de e-B/K donde K es una especia de temperatura sintética. Al reducir gradualmente el valor de K al ir explorando los cambios, el sistema tiende a converger a un conjunto de reglas con una codificación cerca del mínimo.
Orden de las clases y elección de la clase por defecto
Una vez que ya se ha encontrado un subconjunto de reglas para representar cada clase, queda determinar el ordenamiento para las clases y seleccionar un valor por defecto. Al decidir el ordenamiento de las clases es importante tener en cuenta los falsos positivos ya que ocasionarán clasificaciones incorrectas. Entonces, a la hora de decidir sobre el ordenamiento, se elige primero a la clase que tiene menos falsos positivos. Luego, los falsos positivos de los casos de entrenamiento que aún no han sido seleccionados se recomputan y se vuelve a elegir la clase con menos falsos positivos, y así sucesivamente.
Como la clase por defecto será utilizada cuando un caso no sea cubierto por ninguna de las reglas, éstas reglas deberían tenerse en cuenta para determinar cuál será la clase por defecto. El C4.5 elige como clase por defecto aquella clase que cubre la mayoría de los casos de entrenamiento no cubiertos por ninguna regla, resolviendo empates a favor de la clase con la mayor frecuencia absoluta.
Una vez que se ha determinado el ordenamiento y la clase por defecto, el conjunto de reglas se examina por última vez. Si existe alguna regla cuya eliminación reduzca el número de errores de clasificación, se elimina y se recomputan los errores.
El conjunto vuelve a chequearse. Este paso fue diseñado para evaluar el conjunto de reglas en la forma en que será utilizado.
Generalización de un árbol de decisión a reglas de decisión utilizando el C4.5
Para generar las reglas de decisión, el C4.5 parte del árbol sin simplificar y construye una regla de decisión para cada hoja del mismo. En este caso, las reglas generadas a partir del árbol sin simplificar serán:
A continuación, el C4.5 generaliza cada una de estas reglas, eliminando aquellas condiciones que generan un estimador de error pesimístico mayor. Se calcula este estimador para cada una de las reglas presentadas y para las reglas resultantes de eliminar cada una de sus condiciones.
Las reglas resultantes de eliminar cualquiera de las dos condiciones del antecedente, tienen un estimador pesimístico de error superior al de la regla actual, con lo cual no es conveniente eliminar ninguna de las dos condiciones. Se mantiene, entonces, la regla tal como fue generada, agregándole la precisión de la misma.
Archivo de Reglas de decisión y evaluación de resultados del C4.5
El formato del archivo de reglas de decisión y evaluación de los resultados es el siguiente:
Donde:
- Regla es el número de regla
- Tamaño es la cantidad de pruebas de valor en el antecedente de la regla
- Error es el estimador calculado como el complemento de la proporción de éxito asociada a cada regla
- Usada indica la cantidad de veces que se utilizó la regla durante la evaluación
- Errores: indica la cantidad de errores cometidos durante la evaluación, y la proporción de error calculada como dicha cantidad sobre la cantidad de veces en que se utilizó la regla.
- La ventaja tiene el siguiente formato a(b|c), donde b es la cantidad de casos que serían clasificados erróneamente si dicha regla se omitiese, c es la cantidad de casos que serían clasificados correctamente si dicha regla se omitiese por las reglas siguientes, a es el beneficio neto de omitir la regla, calculado como b-c.
| Página siguiente |