CART: Pilihan prediktor terbaik untuk pemisahan ketika keuntungan dalam penurunan pengotor adalah sama?

Pertanyaan saya berkaitan dengan pohon Klasifikasi . Pertimbangkan contoh berikut dari kumpulan data Iris:

Saya ingin secara manual memilih prediktor terbaik untuk pemisahan pertama. Menurut algoritma CART, fitur terbaik untuk membuat pemisahan adalah fitur yang memaksimalkan penurunan pengotor partisi, juga disebut Gini gain:

$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})$

Di mana adalah fitur yang diberikan, adalah simpul yang perpecahan itu harus dibuat, dan dan adalah dua node anak yang dibuat oleh membelah . adalah jumlah elemen dalam sebuah node.$X$$N$$N_{1}$$N_{2}$$N$$\lvert . \rvert$

Dan , di mana adalah jumlah kategori dalam simpul$Gini(N)=1-\sum_{k=1}^{K}p_{k}^2$$K$

Sekarang, karena membuat pemisahan berdasarkan lebar kelopak (sumbu # 1) dan panjang kelopak (sumbu # 2) menghasilkan partisi yang sama (semua bunga Setosa dipisahkan dari non-Setosa), skor GinGain akan persis sama untuk setiap prediktor. Jadi bagaimana algoritma CART memutuskan mana yang terbaik?

Secara intuitif, orang dapat melihat bahwa pemisahan pada panjang kelopak (2) dikaitkan dengan "margin" terbesar, maka panjang kelopak harus dipilih (sebenarnya apa yang terjadi ketika menerapkan rpartdalam R), tetapi tidak ada dalam mengukur margin, sehingga keputusan harus didasarkan pada sesuatu yang lain.$GiniGain$

Utas terkait tetapi tanpa jawaban untuk pertanyaan saya.

Utas terkait tanpa jawaban apa pun.

Saya mengaku sebagai juru bahasa c-code biasa-biasa saja dan kode lama ini tidak ramah pengguna. Yang mengatakan saya pergi melalui kode sumber dan membuat pengamatan ini yang membuat saya cukup yakin untuk mengatakan: "rpart benar-benar mengambil kolom variabel pertama dan terbaik". Karena kolom 1 dan 2 menghasilkan pemisahan yang lebih rendah, petal.length akan menjadi variabel-split pertama karena kolom ini sebelum petal.width dalam data.frame / matrix. Terakhir, saya menunjukkan ini dengan membalikkan urutan kolom sehingga petal.with akan menjadi variabel-split pertama.

Di dalam file sumber c "bsplit.c" dalam kode sumber untuk rpart saya kutip dari baris 38:

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

... dengan demikian iterasi di dalam for loop mulai dari i = 1 hingga rp.nvar, fungsi loss akan dipanggil untuk memindai semua pembagian dengan satu variabel, di dalam gini.c untuk baris "non-kategorikal split" baris 230, split terbaik yang ditemukan adalah diperbarui jika perpecahan baru lebih baik. (Ini juga bisa menjadi fungsi kerugian yang ditentukan pengguna)

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

dan baris terakhir 323, peningkatan untuk pemisahan terbaik oleh variabel dihitung ...

*improve = total_ss - best

... kembali di bsplit.c peningkatan diperiksa jika lebih besar dari apa yang terlihat sebelumnya, dan hanya diperbarui jika lebih besar.

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

Kesan saya pada ini adalah bahwa yang pertama dan terbaik (dari ikatan mungkin akan dipilih), karena hanya jika break point baru memiliki skor yang lebih baik maka akan disimpan. Ini menyangkut titik istirahat terbaik pertama yang ditemukan dan variabel terbaik pertama yang ditemukan. Break point tampaknya tidak akan dipindai, hanya kiri ke kanan di gini.c sehingga break point mengikat pertama yang ditemukan mungkin sulit untuk diprediksi. Tapi variabel dipindai sangat mudah ditebak dari kolom pertama ke kolom terakhir.

Perilaku ini berbeda dari implementasi randomForest di mana di classTree.c solusi berikut digunakan:

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

sangat terakhir saya mengkonfirmasi perilaku ini dengan membalik kolom iris, sehingga petal.width dipilih terlebih dahulu

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

... dan balik lagi

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