Minería de datos (página 3)

Enviado por ia.inteligenciartificial[arroba]yahoo.es

Partes: 1, 2, 3, 4

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
bits

De 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.3015bits

De 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.

Partes: 1, 2, 3, 4

Página anterior

Volver al principio del trabajo

Página siguiente