Diferença na implementação de divisões binárias nas árvores de decisão

12

Estou curioso sobre a implementação prática de uma divisão binária em uma árvore de decisão - no que se refere aos níveis de um preditor categórico .Xj

Especificamente, frequentemente utilizarei algum tipo de esquema de amostragem (por exemplo, ensacamento, superamostragem etc.) ao construir um modelo preditivo usando uma árvore de decisão - a fim de melhorar sua precisão e estabilidade preditivas. Durante essas rotinas de amostragem, é possível que uma variável categórica seja apresentada a um algoritmo de ajuste de árvore com menos do que o conjunto de níveis completo.

Digamos que uma variável X assuma níveis {A,B,C,D,E}. Em uma amostra, talvez apenas níveis {A,B,C,D}estejam presentes. Então, quando a árvore resultante for usada para previsão, o conjunto completo poderá estar presente.

Continuando neste exemplo, digamos que uma árvore se divida em X e envie {A,B}para a esquerda e {C,D}para a direita. Eu esperaria que a lógica da divisão binária dissesse, quando confrontados com novos dados: "Se X tiver o valor A ou B, envie para a esquerda, caso contrário, envie este caso para a direita". O que parece acontecer em algumas implementações é "se X tiver o valor A ou B, envie para a esquerda, se X tiver o valor C ou D, envie para a direita". Quando esse caso assume o valor E, o algoritmo se decompõe.

Qual é a maneira "certa" de lidar com uma divisão binária? Parece que a maneira muito mais robusta é implementada com frequência, mas nem sempre (veja Rpart abaixo).

Aqui estão alguns exemplos:

Rpart falha, os outros estão bem.

#test trees and missing values

summary(solder)
table(solder$PadType)

# create train and validation
set.seed(12345)
t_rows<-sample(1:nrow(solder),size=360, replace=FALSE)
train_solder<-solder[t_rows,]
val_solder<-solder[-t_rows,]

#look at PadType
table(train_solder$PadType)
table(val_solder$PadType)
#set a bunch to missing
levels(train_solder$PadType)[train_solder$PadType %in% c('L8','L9','W4','W9')] <- 'MISSING'


#Fit several trees, may have to play with the parameters to get them to split on the variable

####RPART
mod_rpart<-rpart(Solder~PadType,data=train_solder)
predict(mod_rpart,val_solder)
#Error in model.frame.default(Terms, newdata, na.action = na.action, xlev = attr(object,  : 
#factor 'PadType' has new level(s) D6, L6, L7, L8, L9, W4

####TREE
mod_tree<-tree(Solder~PadType,data=train_solder,split="gini")
predict(mod_tree,val_solder) #works fine

####ctree
mod_ctree<-ctree(Solder~PadType,data=train_solder,control = ctree_control(mincriterion = 0.05))
predict(mod_ctree,val_solder) #works fine
B_Miner
fonte

Respostas:

9

De fato, existem dois tipos de fatores - ordenados (como Minúsculo <Pequeno <Médio <Grande <Enorme) e desordenados (Pepino, Cenoura, Erva-doce, Beringela).
A primeira classe é igual à contínua - só é mais fácil verificar todos os pivôs, também não há problema em estender a lista de níveis.
Para a segunda classe, você deve criar um conjunto de elementos que serão direcionados em uma ramificação, deixando o restante na outra - nesse caso, você pode:

  1. jogar erro
  2. suponha que a classe invisível entre no seu ramo favorito
  3. trate isso como NA e selecione o ramo de maneira menos aleatória.

12#categories-1-1EuEu

Eu diria que a idéia mais sensata é fazer o usuário definir o conjunto completo de fatores (por exemplo, R faz isso organicamente, preservando os níveis por meio de operações de subconjunto) e usar a opção 1. para níveis não declarados e a opção 2. para os declarados . A opção 3. pode fazer sentido se você já tiver alguma infraestrutura de manipulação de NA.

*) Também existe uma estratégia paralela para realizar uma recodificação não trivial de níveis em números, como por exemplo a codificação Breiman - mas isso gera ainda mais problemas.


fonte
1
Você está dizendo que ctree ou tree no meu exemplo realmente trata esse fator não ordenado como um fator ordenado e, portanto, o envia para o ramo "0"?
B_Miner
@mbq, você pode explicar por que o número total de maneiras pelas quais você pode fazer as divisões é 2 ^ (# categorias + 1) - 2. Eu não entendo bem por que a parte "-2".
kasa
Hmm, parece que eu estraguei essa fórmula; existem 2 ^ n palavras de n bits, mas não contamos as palavras a e ~ a, então 2 ^ (n-1) e não gostamos de divisões que não vazam, então 2 ^ (n-1) -1 (em outras palavras, contamos a partir de 1). n = 1 é então um caso especial.