7.3 Selección de las particiones

En esta sección responderemos a la primera pregunta que nos planteamos en la sección 7.2:

¿De qué forma se hacen las particiones y se selecciona la mejor de entre las posibles en cada momento?

Antes, recordemos que una partición divide a un conjunto de prototipos en conjuntos disjuntos. En CART las particiones son binarias, resultado de evaluar una condición que tiene dos únicas respuestas: sí o no.

El objetivo de una partición es incrementar la homogeneidad (en términos de clase) de los subconjuntos resultantes, o lo que es lo mismo, que éstos sean más puros que el conjunto originario. Cada partición tiene asociada una medida de pureza, que se utiliza para:

1.

Para la selección de la mejor partición.

2.

Como criterio de parada, aunque no resulta muy recomendable, como veremos más adelante (sección 7.5).

Para responder adecuadamente a la pregunta que nos ocupa debemos resolver previamente dos cuestiones:

1.

¿Cómo se formulan las preguntas?

2.

¿Qué partición es la mejor?

7.3.1 Formulación de la regla de partición

En esta sección estudiaremos cómo se formulan las preguntas (en CART) que dan lugar a las particiones. En primer lugar fijaremos el marco teórico de trabajo. Sea Q el conjunto de preguntas binarias de la forma:

 

$$\in \subset$$ (48)

El conjunto Q genera un conjunto de particiones, s, en cada nodo, t y cada nodo t se particiona en t_L (izquierdo) y t_R (derecho) de manera que:

• Los casos de t que verifican la condición ¿ X  $\in$  A? se asignan a t_L,
  t_L  =  t  $$\cap$$  A

• Los casos de t que no la verifican se asignan a t_R.
  t_R  =  t  $$\cap$$  $$\overline{A}$$

En CART se define el llamado conjunto estándar de preguntas de la siguiente forma:

1.

Cada partición depende de un único atributo.

2.

Si X_i es un atributo categórico, que toma valores en en { c₁, c₂,..., c_L}, Q incluye las preguntas:

 

$$\in$$ (49)

donde C es un conjunto de entre los subconjuntos de { c₁, c₂,..., c_L}.

Por ejemplo, si X₂ toma valores en {Rojo, Verde, Azul}, las preguntas válidas son del tipo ¿ X₂ $\in$ {Rojo}?, ¿ X₂ $\in$ {Verde}?, etc.

3.

Si X_i es un atributo continuo, Q incluye preguntas del tipo:

 

$$\leq$$ (50)

donde v es un valor real, teóricamente cualquiera. En CART, no obstante, v es el punto medio de dos valores consecutivos de X_i. Esta heurística simplifica enormemente los cálculos haciendo que los problemas sean tratables.

Por ejemplo, si X₁ es un atributo contínuo (real) cuyos valores son: 0.1, 0.5 y 1.0 las preguntas válidas que se evalúan son las siguientes:

¿ X₁ $\leq$ (0.1 + 0.5)/2?, ¿ X₁ $\leq$ (0.5 + 1.0)/2?

Como se puede deducir, el conjunto de preguntas que pueden formularse (y que evaluará CART), aunque puede ser muy amplio, está perfectamente definido y es sistemático.

   
7.3.2 Criterios de partición

Una vez que conocemos cómo se formulan las preguntas (cada una da lugar a una partición) se trata ahora de concretar cómo calcular la mejor partición entre todas las posibles.

Hemos venido utilizando el adjetivo puro asociándolo a un conjunto de prototipos (un nodo) sin formalizar el significado de pureza. No obstante, el lector no habrá tenido dificultad al interpretar su significado. Cada partición tiene asociada una medida de pureza y se tratará de incrementar la homogeneidad de los subconjuntos resultantes de la partición, esto es, que sean más puros que el conjunto originario. En esta sección formalizaremos estos conceptos.

Función de impureza y medida de impureza

En primer lugar definiremos lo que se entiende por función de impureza. Una función de impureza es una función $\phi$ definida sobre J-uplas de la forma (c₁, c₂,..., c_J) tales que: a) c_j $\geq$ 0 para j = 1, 2,..., J y b) $\sum_{j}^{}$c_j = 1, con las siguientes propiedades:

i)

$\phi$ tiene un único máximo en (${\frac{1}{J}}$,${\frac{1}{J}}$,...,${\frac{1}{J}}$).

ii)

$\phi$ alcanza su mínimo en

(1, 0, 0,..., 0),(0, 1, 0,..., 0),...,(0, 0, 0,..., 1)

y el valor del mínimo es 0.

iii)

$\phi$ es una función simétrica de c₁, c₂,..., c_J

Relacionada con la función de impureza está la medida de impureza de un nodo. Dada una función de impureza $\phi$, definimos la medida de impureza de cualquier nodo t, y se escribe i(t),como:

 

$$\phi$$ (51)

donde p(j| t) es la probabilidad de que un caso del nodo t (un prototipo asociado al nodo t) sea de clase j. Estas probabilidades pueden calcularse empíricamente como la proporción de casos de clase j en el nodo t:

 

$${\frac{N_j(t)}{N(t)}}$$ (52)

La notación N_j(t) y N(t) ya es conocida por el lector (ver  este ejemplo).

Dicho de otra forma, la medida de impureza de un nodo es el resultado de evaluar la función de impureza sobre ese nodo tomando las proporciones relativas de cada clase como los c_j. Observar que, por un lado,

a)

p(j| t) $\geq$ 0

b)

$\sum_{j}^{}$p(j| t) =  $\sum_{j}^{}$${\frac{N_j(t)}{N(t)}}$  =  ${\frac{1}{N(t)}}$$\sum_{j}^{}$N_j(t)  =  1

lo que garantiza que los componentes de la J-upla, calculados en términos de proporción relativa son válidos para evaluar la función de impureza. Por otro lado,

i)

La máxima impureza (resp. mínima pureza) se obtiene cuando todas las clases están igualmente representadas en t (recordar la situación inical del árbol de este ejemplo).

ii)

La mínima impureza (resp. máxima pureza) se obtiene cuando en t sólo hay casos de una sola clase (máxima homogeneidad).

iii)

Cualquier permutación de los c_j produce el mismo resultado en el valor de impureza. Por ejemplo, para dos nodos t_j $\neq$ t_k,
i(t_j) = $\phi$(0.7, 0.2, 0.1) = $\phi$(0.2, 0.1, 0.7) = i(t_k)

Bondad de una partición

La bondad de una partición s en un nodo t debe estar relacionada con la impureza del nodo sobre el que se realiza la partición, t, y con la impureza de los nodos resultantes de la partición, t_L y t_R.

Supongamos una partición candidata, s, que divide t en t_L y t_R (ver figura 87) de forma que una proporción p_L de los casos de t van a t_L y una proporción p_R van a t_R.

  

Figura 87: La partición s divide t en t_L y t_R

La bondad de la partición s en un nodo t, $\Phi$(s, t), se define como el decrecimiento en impureza conseguido con ella:

 

$$\Phi \Delta$$ (53)

Así, como conocemos cómo calcular i(t), podemos calcular $\Phi$(s, t) para cada partición s y seleccionar la mejor paritición como la que proporciona la mayor bondad $\Phi$(s, t).

Para establecer el efecto que produce la selección de la mejor partición en cada nodo sobre el árbol final necesitamos una medida de la impureza global del árbol.

Impureza de un árbol

Supongamos construido un árbol binario T, obtenido mediante una serie de particiones. Sea $\tilde{T}$ el conjunto de nodos terminales del árbol T.

Sea I(t) = i(t)p(t), donde p(t) es la probabilidad de que un caso cualquiera esté en el nodo t. La impureza del árbol T, I(T), se define como:

 

$$\sum_{t\in \tilde{T}}^{} \sum_{t\in \tilde{T}}^{}$$ (54)

En definitiva, la impureza de un árbol se calcula únicamente en base al conjunto de nodos terminales.

Una conclusión fundamental a la que llegan Breiman y otros en [B.1], cuya demostración obviamos por su difucultad es la siguiente:

La selección continuada de las particiones que maximizan $\Delta$i(s, t) es equivalente a seleccionar las particiones que minimizan la impureza global I(T)

lo que significa que la estrategia de selección de la mejor partición en cada nodo conduce a la solución óptima considerando el árbol final.

Criterios de medida de impureza

Para finalizar, presentaremos algunas de las funciones más importantes para la medida de la impureza de un nodo. Entre los criterios más utilizados se encuentran la medida de entropía y el índice de Gini.

• Medida de entropía.

  Mide la entropía en un nodo t de acuerdo a la formulación clásica de la entropía:

   

  $$\sum_{j=1}^{J}$$ (55)

  Se asume que 0 log 0  =   0

   

• Indice de Gini.

  
  
  Mide la diversidad de clases en un nodo.

   

  $$\sum_{\stackrel{i,j=1}{i \neq j}}^{J} \sum_{j=1}^{J}$$ (56)

Puede definirse otros criterios de impureza (ver [B.1]), aunque es importante destacar que Breiman y otros concluyen en [B.1], tras numerosos experimentos, que la elección del criterio de partición más adecuado depende del problema, aunque el clasificador generado no parece muy sensible a esta elección, como demuestra la experiencia.

 

Ejemplo  

En este ejemplo ilustramos el uso del índice de diversidad de Gini. Para ello utilizaremos dos nodos muy diferentes, t₁ y t₂ (ver figura 88). A priori, parece que el nodo t₂ es más homogéneo o puro, o lo que es lo mismo, presenta menos diversidad.

  

Figura 88: Dos nodos para calcular i(t)

La expresión para calcular el índice de diversidad de Gini dada en la ecuación 56 puede simplificarse como indicamos en la ecuación 57:

 

$$\underbrace{\sum_{\stackrel{i,j = 1} {i \neq j}}^{3}{p(i\vert t_1)\space p(j\vert t_1)}}\, \underbrace{1\space -\space \sum_{j = 1}^{3}{p(j\vert t_1)}^2}\,$$ (57) (1)                                                  (2)

Según la ecuación 56 (o lo que es igual, según el caso (1) de 57),

i(t₁) = p(1| t₁)p(2| t₁) + p(1| t₁)p(3| t₁) + p(2| t₁)p(1| t₁) + + p(2| t₁)p(3| t₁) + p(3| t₁)p(1| t₁) + p(3| t₁)p(2| t₁) =

= 2p(1| t₁)p(2| t₁) + 2p(2| t₁)p(3| t₁) + 2p(3| t₁)p(1| t₁) =

$$\left(\vphantom{\frac{5}{40}\frac{10}{40}}\right. {\textstyle\frac{5}{40}} {\textstyle\frac{10}{40}} \left.\vphantom{\frac{5}{40}\frac{10}{40}}\right) \left(\vphantom{\frac{10}{40}\frac{25}{40}}\right. {\textstyle\frac{10}{40}} {\textstyle\frac{25}{40}} \left.\vphantom{\frac{10}{40}\frac{25}{40}}\right) \left(\vphantom{\frac{25}{40}\frac{5}{40}}\right. {\textstyle\frac{25}{40}} {\textstyle\frac{5}{40}} \left.\vphantom{\frac{25}{40}\frac{5}{40}}\right)$$ =

y según el caso (2) de 57,

i(t₁) = 1  -  (p(1| t₁)² + p(2| t₁)² + p(3| t₁)²) =
= 1 - $$\left(\vphantom{ {\left(\frac{5}{40}\right)}^2 + {\left(\frac{10}{40}\right)}^2 + {\left(\frac{25}{40}\right)}^2 }\right.$$$$\left(\vphantom{\frac{5}{40}}\right.$$$${\textstyle\frac{5}{40}}$$ $$\left.\vphantom{\frac{5}{40}}\right)^{2{_}}_{}$$ + $$\left(\vphantom{\frac{10}{40}}\right.$$$${\textstyle\frac{10}{40}}$$ $$\left.\vphantom{\frac{10}{40}}\right)^{2{_}}_{}$$ + $$\left(\vphantom{\frac{25}{40}}\right.$$$${\textstyle\frac{25}{40}}$$ $$\left.\vphantom{\frac{25}{40}}\right)^{2{_}}_{}$$$$\left.\vphantom{ {\left(\frac{5}{40}\right)}^2 + {\left(\frac{10}{40}\right)}^2 + {\left(\frac{25}{40}\right)}^2 }\right)$$ =

$$= 1 - \frac{25 + 100 + 625}{1600}\ =\ 1 - 0.4687\ =\ \mbox{\bf0.5313}$$

La impureza del nodo t₂ será:

i(t₂) = 2p(1| t₂)p(2| t₂) + 2p(2| t₂)p(3| t₂) + 2p(3| t₂)p(1| t₂) =

$$= 2 \left(\frac{2}{40}\frac{3}{40}\right) + 2 \left(\frac{3}... ...2 \left(\frac{35}{40}\frac{2}{40}\right)\ =\ \mbox{\bf0.2263}$$

lo que demuestra, numéricamente, que el nodo t₂ es menos impuro (más homogéneo) que el nodo t₁.