PANIER: Sélection du meilleur prédicteur de fractionnement lorsque les gains de diminution d'impureté sont égaux?

Ma question concerne les arbres de classification . Prenons l'exemple suivant de l'ensemble de données Iris:

Je souhaite sélectionner manuellement le meilleur prédicteur pour la première division. Selon l'algorithme CART, la meilleure fonctionnalité pour effectuer un fractionnement est celle qui maximise la diminution de l'impureté de la partition, également appelée gain 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})$

Où est une fonctionnalité donnée, N est le noeud sur lequel la séparation doit être effectuée, et N_ {1} et N_ {2} sont les deux noeuds fils créés par fractionnement N . \ lvert. \ rvert est le nombre d'éléments dans un nœud.$X$$N$$N_{1}$$N_{2}$$N$$\lvert . \rvert$

Et $Gini(N)=1-\sum_{k=1}^{K}p_{k}^2$ , où $K$ est le nombre de catégories dans le nœud

Maintenant, puisque faire une division basée sur la largeur des pétales (axe # 1) et la longueur des pétales (axe # 2) donne la même partition (toutes les fleurs de Setosa sont séparées des non-Setosa), les scores GinGain seront exactement les mêmes pour chaque prédicteur. Alors, comment l'algorithme CART décide-t-il lequel est le meilleur?

Intuitivement, on peut voir que le fractionnement sur la longueur des pétales (2) est associé à la plus grande "marge", donc la longueur des pétales doit être choisie (c'est en fait ce qui se passe lors de la mise rparten œuvre dans R), mais rien dans mesure la marge, donc la décision doit être basé sur autre chose.$GiniGain$

Fil associé mais sans la réponse à ma question.

Fil associé sans aucune réponse.

J'avoue être un interprète de code c médiocre et cet ancien code n'est pas convivial. Cela dit, j'ai parcouru le code source et fait ces observations, ce qui me donne la certitude de dire: "rpart choisit littéralement la première et la meilleure colonne de variables". Comme les colonnes 1 et 2 produisent des divisions inférieures, petal.length sera la première variable de division car cette colonne est avant petal.width dans data.frame / matrix. Enfin, je le montre en inversant l'ordre des colonnes de telle sorte que pétale.with sera la première variable divisée.

Dans le fichier source c "bsplit.c" dans le code source de rpart, je cite la ligne 38:

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

... ainsi en itérant dans une boucle for à partir de i = 1 vers rp.nvar, une fonction de perte sera appelée pour balayer tout le split par une variable, à l'intérieur de gini.c pour la ligne 230 "split non catégorique" le meilleur split trouvé est mis à jour si une nouvelle division est meilleure. (Cela pourrait également être une fonction de perte définie par l'utilisateur)

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

et dernière ligne 323, l'amélioration du meilleur fractionnement par une variable est calculée ...

*improve = total_ss - best

... de retour dans bsplit.c, l'amélioration est vérifiée si elle est plus grande que ce qui a été vu précédemment, et mise à jour uniquement si elle est plus grande.

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

Mon impression à ce sujet est que le premier et le meilleur (des liens possibles seront choisis), car seulement si un nouveau point d'arrêt a un meilleur score, il sera enregistré. Cela concerne à la fois le premier meilleur point de rupture trouvé et la première meilleure variable trouvée. Les points d'arrêt ne semblent pas être scannés simplement de gauche à droite dans gini.c, donc le premier point d'arrêt lié peut être difficile à prévoir. Mais les variables sont très prévisibles scannées de la première colonne à la dernière colonne.

Ce comportement est différent de l' implémentation randomForest où dans classTree.c la solution suivante est utilisée:

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

enfin je confirme ce comportement en retournant les colonnes d'iris, de telle sorte que petal.width soit choisi en premier

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) *

... et retournez à nouveau

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) *