Perbedaan dalam implementasi pemisahan biner di pohon keputusan

12

Saya ingin tahu tentang implementasi praktis dari pemisahan biner dalam pohon keputusan - yang berkaitan dengan tingkat prediktor kategorikal .Xj

Secara khusus, saya sering akan menggunakan semacam skema pengambilan sampel (misalnya mengantongi, oversampling dll) ketika membangun model prediksi menggunakan pohon keputusan - untuk meningkatkan akurasi dan stabilitas prediksi. Selama rutinitas pengambilan sampel ini, dimungkinkan untuk variabel kategorikal untuk disajikan ke algoritma pemasangan pohon dengan kurang dari set level lengkap.

Katakanlah variabel X mengambil level {A,B,C,D,E}. Dalam sampel, mungkin hanya level {A,B,C,D}yang ada. Kemudian, ketika pohon yang dihasilkan digunakan untuk prediksi, set lengkap mungkin ada.

Melanjutkan dari contoh ini, katakan pohon terbelah pada X dan mengirim {A,B}ke kiri dan {C,D}ke kanan. Saya akan mengharapkan logika dari pemisahan biner untuk kemudian berkata, ketika dihadapkan dengan data baru: "Jika X memiliki nilai A atau B, kirim ke kiri, jika tidak, kirim case ini ke kanan". Apa yang tampaknya terjadi dalam beberapa implementasi adalah "jika X memiliki nilai A atau B, kirim ke kiri, jika X memiliki nilai C atau D kirim ke kanan". Ketika kasus ini mengambil nilai E, algoritme rusak.

Apa cara "benar" untuk pemecahan biner untuk ditangani? Tampaknya cara yang jauh lebih kuat sering diterapkan, tetapi tidak selalu (lihat Rpart di bawah).

Berikut adalah beberapa contoh:

Rpart gagal, yang lain ok.

#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
sumber

Jawaban:

9

Sebenarnya ada dua jenis faktor - dipesan (seperti Tiny <Small <Medium <Big <Huge) dan unordered (Cucumber, Carrot, Fennel, Aubergine).
Kelas pertama sama dengan kelas kontinu - hanya ada lebih mudah untuk memeriksa semua pivot, juga tidak ada masalah dengan memperpanjang daftar level.
Untuk kelas kedua, Anda harus membuat satu set elemen yang akan diarahkan dalam satu cabang, meninggalkan sisanya ke yang lain - dalam hal ini Anda bisa:

  1. kesalahan melempar
  2. asumsikan bahwa kelas tak terlihat masuk ke cabang favorit Anda
  3. perlakukan ini sebagai NA dan pilih cabang dengan cara yang lebih-kurang acak.

12#categories11ii

Saya akan mengatakan ide yang paling masuk akal adalah membuat pengguna menentukan set lengkap faktor (misalnya R melakukan ini secara organik, menjaga level melalui operasi subset) dan menggunakan opsi 1. untuk level yang tidak dideklarasikan dan opsi 2. untuk yang dinyatakan . Opsi 3. mungkin masuk akal jika Anda sudah memiliki beberapa infrastruktur penanganan NA.

*) Ada juga strategi sampingan untuk melakukan pengkodean ulang tingkat menjadi non-sepele, seperti misalnya pengkodean Breiman - namun ini menghasilkan lebih banyak masalah.


sumber
1
Apakah Anda mengatakan bahwa pohon atau pohon dalam contoh saya benar-benar memperlakukan faktor tidak berurutan ini sebagai faktor terurut dan dengan demikian mengirimkannya ke cabang "0"?
B_Miner
@mbq bisa tolong jelaskan mengapa jumlah total cara Anda dapat melakukan split adalah 2 ^ (# kategori + 1) - 2. Saya tidak begitu mengerti mengapa bagian "-2".
kasa
Hmm, sepertinya saya telah mengacaukan formula ini; ada seperti 2 ^ n n-bit kata, tapi kami tidak menghitung kedua kata a dan ~ a, jadi 2 ^ (n-1), dan kami tidak suka split yang tidak tumpah sama sekali, jadi 2 ^ (n-1) -1 (dengan kata lain, kami menghitung dari 1). n = 1 kemudian merupakan kasus khusus.