CARRITO: ¿Selección del mejor predictor para dividir cuando las ganancias en la disminución de impurezas son iguales?

Mi pregunta trata sobre los árboles de clasificación . Considere el siguiente ejemplo del conjunto de datos de Iris:

Quiero seleccionar manualmente el mejor predictor para la primera división. Según el algoritmo CART, la mejor característica para hacer una división es la que maximiza la disminución de la impureza de la partición, también llamada ganancia de Gini:

$GiniGain(N,X)=Gini(N)-\frac{\lvert N_{1} \rvert }{\lvert N \rvert }Gini(N_{1})-\frac{\lvert N_{2} \rvert }{\lvert N \rvert }Gini(N_{1})$

Donde es un rasgo dado, es el nodo en el que la división se va a realizar, y y son los dos nodos hijo creados por división . es el número de elementos en un nodo.$X$$N$$N_{1}$$N_{2}$$N$$\lvert . \rvert$

Y , donde es el número de categorías en el nodo$Gini(N)=1-\sum_{k=1}^{K}p_{k}^2$$K$

Ahora, dado que hacer una división basada en el ancho del pétalo (eje n. ° 1) y la longitud del pétalo (eje n. ° 2) produce la misma partición (todas las flores de Setosa se separan de las que no son Setosa), las puntuaciones de GinGain serán exactamente las mismas para cada vaticinador. Entonces, ¿cómo decide el algoritmo CART cuál es el mejor?

Intuitivamente, se puede ver que la división en la longitud del pétalo (2) está asociada con el mayor "margen", por lo tanto, se debe elegir la longitud del pétalo (en realidad es lo que sucede cuando se implementa rparten R), pero nada en mide el margen, por lo que la decisión debe basarse en otra cosa.$GiniGain$

Hilo relacionado pero sin la respuesta a mi pregunta.

Tema relacionado sin ninguna respuesta.

Confieso ser un intérprete de código C mediocre y este viejo código no es fácil de usar. Dicho esto, revisé el código fuente e hice estas observaciones, lo que me hace bastante seguro de decir: "rpart literalmente elige la primera y mejor columna variable". Como las columnas 1 y 2 producen divisiones inferiores, petal.length será la primera variable dividida porque esta columna está antes de petal.width en data.frame / matrix. Por último, muestro esto invirtiendo el orden de las columnas de manera que petal.with será la primera variable dividida.

En el archivo fuente c "bsplit.c" en el código fuente de rpart cito de la línea 38:

 * test out the variables 1 at at time
me->primary = (pSplit) NULL;
for (i = 0; i < rp.nvar; i++) {

... iterando así en un bucle for que comienza desde i = 1 hasta rp.nvar, se llamará a una función de pérdida para escanear todas las divisiones por una variable, dentro de gini.c para la línea 230 de "división no categórica" ​​la división mejor encontrada es actualizado si una nueva división es mejor. (Esto también podría ser una función de pérdida definida por el usuario)

if (temp < best) {
        best = temp;
        where = i;
        direction = lmean < rmean ? LEFT : RIGHT;
}

y la última línea 323, se calcula la mejora para la mejor división por una variable ...

*improve = total_ss - best

... de vuelta en bsplit.c, la mejora se verifica si es más grande que lo visto anteriormente, y solo se actualiza si es más grande.

if (improve > rp.iscale)
rp.iscale = improve;        /* largest seen so far */

Mi impresión sobre esto es que se elegirá el primero y el mejor (de los posibles lazos), porque solo si el nuevo punto de quiebre tiene una mejor puntuación, se guardará. Esto concierne tanto al primer mejor punto de ruptura encontrado como a la primera mejor variable encontrada. Parece que los puntos de ruptura no se escanean simplemente de izquierda a derecha en gini.c, por lo que el primer punto de ruptura encontrado puede ser difícil de predecir. Pero las variables son muy predecibles escaneadas desde la primera columna hasta la última columna.

Este comportamiento es diferente de la implementación randomForest donde en classTree.c se usa la siguiente solución:

/* Break ties at random: */
if (crit == critmax) {
    if (unif_rand() < 1.0 / ntie) {
        *bestSplit = j;
        critmax = crit;
        *splitVar = mvar;
    }
    ntie++;
}

Por último, confirmo este comportamiento volteando las columnas de iris, de modo que se elige primero petal.width

library(rpart)
data(iris)
iris = iris[,5:1]  #flip/flop", invert order of columns columns
obj = rpart(Species~.,data=iris)
print(obj) #now petal width is first split 


1) root 150 100 setosa (0.33333333 0.33333333 0.33333333)  
  2) Petal.Width< 0.8 50   0 setosa (1.00000000 0.00000000 0.00000000) *
  3) Petal.Width>=0.8 100  50 versicolor (0.00000000 0.50000000 0.50000000)  
    6) Petal.Width< 1.75 54   5 versicolor (0.00000000 0.90740741 0.09259259) *
    7) Petal.Width>=1.75 46   1 virginica (0.00000000 0.02173913 0.97826087) *

... y voltea de nuevo

iris = iris[,5:1]  #flop/flip", revert order of columns columns
obj = rpart(Species~.,data=iris)
print(obj) #now petal length is first split 
1) root 150 100 setosa (0.33333333 0.33333333 0.33333333)  
  2) Petal.Length< 2.45 50   0 setosa (1.00000000 0.00000000 0.00000000) *
  3) Petal.Length>=2.45 100  50 versicolor (0.00000000 0.50000000 0.50000000)  
    6) Petal.Width< 1.75 54   5 versicolor (0.00000000 0.90740741 0.09259259) *
    7) Petal.Width>=1.75 46   1 virginica (0.00000000 0.02173913 0.97826087) *