Gini berkurang dan Gini ketidakmurnian simpul anak

Saya sedang mengerjakan ukuran kepentingan fitur Gini untuk hutan acak. Oleh karena itu, saya perlu menghitung penurunan Gini dalam ketidakmurnian simpul. Inilah cara saya melakukannya, yang mengarah pada konflik dengan definisi tersebut, menunjukkan bahwa saya pasti salah di suatu tempat ... :)

Untuk pohon biner, dan mengingat probabilitas anak-anak kiri dan kanan, saya dapat menghitung ketidakmurnian Gini dari sebuah simpul : $n$

i (n) = 1 - p_{l}^{2} - p_{r}^{2}

$i(n) = 1 - p_l^2 - p_r^2$

Dan penurunan Gini:

Δ i (n) = i (n) - p_{l} i (n_{l}) - p_{r} i (n_{r})

$\Delta i(n) = i(n) - p_li(n_l) - p_ri(n_r)$

Jadi, untuk contoh ini dengan 110 pengamatan pada sebuah simpul:

- node (110)
   - left (100)
      - left_left (60)
      - left_right (40)
   - right (10)
      - right_left (5)
      - right_right (5)

Saya akan menghitung penurunan Gini untuk simpul seperti ini:

\begin{aligned} i (l e f t) & = 1 - (60 / 100)^{²} - (40 / 100)^{²} & = 0.48 \\ i (r i g h t) & = 1 - (5 / 10)^{²} - (5 / 10)^{²} & = 0.50 \\ i (n o d e) & = 1 - (100 / 110)^{²} - (10 / 110)^{²} & = 0.16 \end{aligned}

$\begin{align} i({\rm left}) &= 1 - (60/100)^² - (40/100)^²& &= 0.48 \\ i({\rm right}) &= 1 - (5/10)^² - (5/10)^²& &= 0.50 \\ i({\rm node}) &= 1 - (100/110)^² - (10/110)^²& &= 0.16 \end{align}$

Tetapi mengikuti definisi Breiman (atau jawaban ini di CV: Bagaimana mengukur / memberi peringkat "variabel penting" ketika menggunakan CART , tetapi saya tidak memiliki akses ke buku yang dirujuk), kriteria kenajisan dari keturunan harus lebih kecil dari induknya. simpul:

Pentingnya gini
Setiap kali pemisahan simpul dilakukan pada variabel m kriteria pengotor gini untuk dua simpul turunan lebih kecil dari simpul induk. Menambahkan gini berkurang untuk setiap variabel individu atas semua pohon di hutan memberikan variabel cepat penting yang sering sangat konsisten dengan ukuran kepentingan permutasi.

Karena jika tidak, itu mengarah ke penurunan Gini negatif ...

Δ i (n o d e) = i (n o d e) - (100 / 110) * i (l e f t) - (10 / 110) * i (r i g h t) = - 0.32

$\Delta i({\rm node}) = i({\rm node}) - (100/110)*i({\rm left}) - (10/110)*i({\rm right}) = -0.32$

Jadi, jika seseorang dapat mengetahui di mana saya salah, saya akan sangat berterima kasih karena sepertinya saya kehilangan sesuatu yang jelas di sini ...

feature-selection random-forest cart Remi Mélisson
sumber

Anda sama sekali tidak menggunakan variabel kelas target sama sekali. Gini pengotor seperti semua fungsi pengotor lainnya, mengukur pengotor dari output setelah split. Apa yang Anda lakukan adalah mengukur sesuatu hanya dengan menggunakan ukuran sampel.

Saya mencoba untuk mendapatkan formula untuk kasus Anda.

Misalkan untuk kesederhanaan Anda telah memiliki classifier biner. Ditunjukkan dengan sebagai atribut uji, dengan atribut kelas yang memiliki nilai . $A$ $C$ $c_+, c_-$

Indeks gini awal sebelum pemisahan diberikan oleh mana adalah proporsi titik data yang memiliki nilai untuk variabel kelas.

saya (SEBUAH) = 1 - P ({SEBUAH}_{+})^{2} - P ({SEBUAH}_{-})^{2}

$I(A) = 1 - P(A_+)^2 - P(A_-)^2$

P (A_{+})

$P(A_+)$

c_{+}

$c_+$

Sekarang, pengotor untuk simpul kiri adalah mana

saya (SEBUAH l) = 1 - P (SEBUAH l_{+})^{2} - P (SEBUAH l_{-})^{2}

$I(Al) = 1 - P(Al_+)^2-P(Al_-)^2$

saya (SEBUAH r) = 1 - P (SEBUAH r_{+})^{2} - P (SEBUAH r_{-})^{2}

$I(Ar) = 1 - P(Ar_+)^2-P(Ar_-)^2$

P (A l_{+})

$P(Al_+)$ adalah proporsi titik data dari subset kiri

yang memiliki nilai

dalam variabel kelas, dll.

A

$A$

c_{+}

$c_+$

Sekarang formula final untuk GiniGain adalah

mana adalah proporsi dari instance untuk subset kiri, atau

G i n i G a i n (A) = I (A) - p_{l e f t} I (A l) - p_{r i g h t} I (A r)

$GiniGain(A) = I(A) - p_{left}I(Al) - p_{right}I(Ar)$

p_{l e f t}

$p_{left}$

(berapa banyak contoh yang di bagian kiri dibagi dengan jumlah total kasus dari

\frac{# | A l |}{# | A l | + # | A r |}

$\frac{\#|Al|}{\#|Al|+\#|Ar|}$

A

$A$

Saya merasa notasi saya dapat ditingkatkan, saya akan menonton nanti ketika saya akan memiliki lebih banyak waktu.

Kesimpulan

Hanya menggunakan jumlah titik data saja tidak cukup, pengotor berarti seberapa baik satu fitur (fitur uji) dapat mereproduksi distribusi fitur lain (fitur kelas). Distribusi fitur tes menghasilkan angka yang Anda gunakan (cara ke kiri, cara ke kanan), tetapi distribusi fitur kelas tidak digunakan dalam rumus Anda.

Kemudian edit - cari alasannya berkurang

Sekarang saya perhatikan bahwa saya melewatkan bagian yang membuktikan mengapa selalu indeks gini pada simpul anak kurang dari pada simpul orangtua. Saya tidak memiliki proove lengkap atau yang diverifikasi, tetapi saya pikir itu adalah bukti yang valid. Untuk hal campur tangan lain yang terkait dengan topik Anda dapat memeriksa Catatan Teknis: Beberapa Properti Kriteria Membelah - Leo Breiman . Sekarang akan mengikuti bukti saya.

$(a,b)$ $a$ $b$ $(a,b)$

Untuk menemukan pemecahan terbaik, kami mengurutkan instance berdasarkan dengan fitur tes dan kami mencoba semua pemecahan biner yang mungkin. Diurutkan berdasarkan fitur yang diberikan sebenarnya adalah permutasi dari instance, di mana kelas dimulai dengan instance dari kelas pertama atau dari kelas kedua. Tanpa menghilangkan sifat umum, kita akan mengira bahwa itu dimulai dengan turunan dari kelas pertama (jika ini bukan masalahnya, kita memiliki bukti cermin dengan perhitungan yang sama).

$(1,0)$ $(a-1,b)$ $h(left) = 1 - (1/1)^2 - (0/1)^2 = 0$ . Jadi di sisi kiri kita memiliki nilai indeks gini yang lebih kecil. Bagaimana dengan simpul yang benar?

h (p a r e n t) = 1 - (\frac{a}{a + b})^{2} - (\frac{b}{a + b})^{2}

$h(parent) = 1 - (\frac{a}{a+b})^2 - (\frac{b}{a+b})^2$

h (r i g h t) = 1 - (\frac{a - 1}{(a - 1) + b})^{2} - (\frac{b}{(a - 1) + b})^{2}

$h(right) = 1 - (\frac{a-1}{(a-1)+b})^2 - (\frac{b}{(a-1)+b})^2$

Considering that $a$ is greater or equal than $0$ (since otherwise how could we separate an instance of the first class in the left node?) and after simplification it's simple to see that the gini index for the right node has a smaller value than for the parent node.

Now the final stage of the proof is to node that while considering all the possible split points dictated by the data we have, we keep the one which has the smallest aggregated gini index, which means that the optimum we choose is less or equal than the trivial one which I prooved that is smaller. Which concludes that in the end the gini index will decrease.

As a final conclusion we have to note even if various splits can give values bigger that parent node, the one that we choose will be the smallest among them and also smaller that the parent gini index value.

Hope it helps.

rapaio
sumber

Terima kasih banyak, Anda membuka kunci otak saya ... Bahkan, karena saya sedang berurusan dengan pohon regresi, menggunakan variabel kelas target tampak kurang jelas daripada untuk tugas klasifikasi murni. Tapi sekarang benar-benar masuk akal.

Remi Mélisson

Saya memperbarui jawaban untuk memuat bagian yang hilang.

rapaio

Gini berkurang dan Gini ketidakmurnian simpul anak

Jawaban: