Różnica w implementacji podziałów binarnych w drzewach decyzyjnych

12

Jestem ciekawy praktycznej implementacji podziału binarnego w drzewie decyzyjnym - ponieważ dotyczy on poziomów predyktora jakościowego .Xj

W szczególności często będę używał pewnego rodzaju schematu próbkowania (np. Tworzenie worków, nadpróbkowanie itp.) Podczas budowania modelu predykcyjnego przy użyciu drzewa decyzyjnego - w celu poprawy jego dokładności i stabilności predykcyjnej. Podczas tych procedur próbkowania możliwe jest przedstawienie zmiennej kategorialnej algorytmowi dopasowania drzewa z mniej niż pełnym zestawem poziomów.

Powiedzmy, że zmienna X przyjmuje poziomy {A,B,C,D,E}. W próbce mogą występować tylko poziomy {A,B,C,D}. Następnie, gdy powstałe drzewo jest używane do przewidywania, może być obecny pełny zestaw.

Kontynuując ten przykład, powiedz, że drzewo dzieli się na X i wysyła {A,B}w lewo i {C,D}w prawo. Oczekiwałbym, że logika podziału binarnego powie, kiedy w obliczu nowych danych: „Jeśli X ma wartość A lub B, wyślij w lewo, w przeciwnym razie wyślij tę skrzynkę w prawo”. W niektórych implementacjach wydaje się, że „jeśli X ma wartość A lub B, wyślij w lewo, jeśli X ma wartość C lub D, wyślij w prawo”. Gdy ten przypadek przyjmuje wartość E, algorytm ulega awarii.

Jaki jest „właściwy” sposób obsługi podziału binarnego? Wydaje się, że znacznie bardziej niezawodny sposób jest wdrażany często, ale nie zawsze (patrz Rpart poniżej).

Oto kilka przykładów:

Rpart zawiedzie, pozostałe są w porządku.

#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
źródło

Odpowiedzi:

9

W rzeczywistości istnieją dwa rodzaje czynników - uporządkowane (jak małe <małe <średnie <duże <duże) i nieuporządkowane (ogórek, marchew, koper włoski, bakłażan).
Pierwsza klasa jest taka sama jak ciągła - sprawdzanie wszystkich osi jest łatwiejsze, nie ma też problemu z rozszerzaniem listy poziomów.
Dla drugiej klasy musisz wykonać zestaw elementów, które będą kierowane w jednej gałęzi, pozostawiając resztę w drugiej - w tym przypadku możesz:

  1. wyrzucić błąd
  2. Załóżmy, że niewidoczna klasa idzie do twojej ulubionej gałęzi
  3. potraktuj to jako NA i wybierz gałąź w sposób mniej przypadkowy.

Teraz bezpośrednie traktowanie czynników nieuporządkowanych jest trudne, ponieważ wiele algorytmów „oszukiwa” i twierdzi, że czynniki nieuporządkowane są uporządkowane, więc nawet nie dotykają tego problemu *. Reszta zwykle używa maski int, tj. Optymalizuje liczbę całkowitą od do i traktuje -ty bit jako wybór gałęzi dla poziomu czynnika . (Czy zastanawiałeś się kiedyś, dlaczego często występuje ograniczenie do 32 poziomów?) W tym ustawieniu całkiem naturalne jest, że niewidoczne poziomy przechodzą cicho do gałęzi „0”. Nie wydaje się to jednak zbyt „słuszne”, ponieważ dlaczego tak naprawdę powinniśmy to robić? A co z liczbą poziomów wymaganych do entropii dźwigni w wyborze atrybutów?12#categories11ii

Powiedziałbym, że najbardziej sensownym pomysłem jest skłonienie użytkownika do zdefiniowania pełnego zestawu czynników (na przykład R robi to organicznie, zachowując poziomy poprzez operacje podzbiorów) i skorzystania z opcji 1. dla poziomów niezadeklarowanych i opcji 2. dla poziomów zadeklarowanych . Opcja 3. może mieć sens, jeśli masz już infrastrukturę do obsługi NA.

*) Istnieje również strategia poboczna, która polega na nietrywialnym przekodowaniu poziomów na liczby, na przykład kodowaniu Breimana - jednak generuje to jeszcze więcej problemów.


źródło
1
Czy mówisz, że ctree lub drzewo w moim przykładzie traktuje ten nieuporządkowany czynnik jako czynnik uporządkowany i w ten sposób wysyła go do gałęzi „0”?
B_Miner,
@mbq czy możesz wyjaśnić, dlaczego łączna liczba sposobów podziału wynosi 2 ^ (# kategorii + 1) - 2. Nie bardzo rozumiem, dlaczego część „-2”.
honeybadger
Hmm, wygląda na to, że spieprzyłem ten wzór; są jak 2 ^ n-bitowe słowa, ale nie liczymy zarówno słowa a i ~ a, więc 2 ^ (n-1), i nie lubimy podziałów, które w ogóle się nie rozlały, więc 2 ^ (n-1) -1 (innymi słowy, liczymy od 1). n = 1 jest wówczas przypadkiem szczególnym.