Zmniejszenie Gini i zanieczyszczenie Gini węzłów dziecięcych

Pracuję nad miarą ważności funkcji Gini dla losowego lasu. Dlatego muszę obliczyć spadek zanieczyszczenia węzła Gini. Oto sposób, w jaki to robię, co prowadzi do konfliktu z definicją, co sugeruje, że gdzieś się mylę ... :)

W przypadku drzewa binarnego i biorąc pod uwagę prawdopodobieństwa lewych i prawych dzieci, mogę obliczyć zanieczyszczenie Gini węzła $n$ :

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

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

A spadek 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)$

Na przykład dla 110 obserwacji w węźle:

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

Obliczę zmniejszenie Gini dla węzła w ten sposób:

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

Ale zgodnie z definicją Breimana (lub odpowiedzią na CV: Jak mierzyć / uszeregować „zmienne znaczenie” podczas używania KOSZYKA , ale nie mam dostępu do książki, do której się odwołuje), kryterium nieczystości potomka powinno być mniejsze niż rodzic węzeł:

Znaczenie Gini
Za każdym razem, gdy dokonuje się podziału węzła na zmiennej m, kryterium zanieczyszczenia gini dla dwóch potomnych węzłów jest mniejsze niż węzeł nadrzędny. Zsumowanie spadków gini dla każdej pojedynczej zmiennej we wszystkich drzewach w lesie daje szybkie znaczenie zmiennej, które często jest bardzo zgodne z miarą ważności permutacji.

Ponieważ inaczej prowadzi to do ujemnego spadku Gini ...

Δ 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$

Więc jeśli ktoś mógłby powiedzieć, gdzie się mylę, byłbym bardzo wdzięczny, ponieważ wygląda na to, że tęsknię za czymś oczywistym ...

feature-selection random-forest cart

— Remi Mélisson
źródło

Po prostu wcale nie użyłeś zmiennej klasy docelowej. Zanieczyszczenie Giniego, podobnie jak wszystkie inne funkcje zanieczyszczenia, mierzy zanieczyszczenie wyjść po podziale. To, co zrobiłeś, to zmierzyć coś przy użyciu tylko wielkości próbki.

Próbuję wyprowadzić formułę dla twojej sprawy.

Załóżmy, że dla uproszczenia masz binarny klasyfikator. Oznacz za pomocą atrybutu testowego, za pomocą atrybutu klasy, który ma wartości . $A$ $C$ $c_+, c_-$

Początkowy indeks gini przed podziałem jest określony przez gdzie jest proporcją punktów danych, które mają wartość dla zmiennej klasy.

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

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

P (A_{+})

$P(A_+)$

c_{+}

$c_+$

I (A l) = 1 - P (A l_{+})^{2} - P (A l_{-})^{2}

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

I (A r) = 1 - P (A r_{+})^{2} - P (A r_{-})^{2}

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

P (A l_{+})

$P(Al_+)$

A

$A$

c_{+}

$c_+$

Teraz ostateczna formuła GiniGain byłaby

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

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

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

A

$A$

Wydaje mi się, że moja notacja mogłaby zostać ulepszona, będę oglądać później, kiedy będę miał więcej czasu.

Wniosek

Używanie tylko liczby punktów danych nie wystarczy, zanieczyszczenie oznacza, jak dobrze jedna funkcja (funkcja testowa) jest w stanie odtworzyć rozkład innej cechy (funkcja klasy). Rozkład funkcji testowej generuje liczbę, której użyłeś (jak odejść, jak od prawej), ale rozkład funkcji klasy nie jest używany w twoich formułach.

Późniejsza edycja - udowodnij, dlaczego się zmniejsza

Teraz zauważyłem, że przegapiłem część, która dowodzi, dlaczego zawsze indeks gini w węźle potomnym jest mniejszy niż w węźle nadrzędnym. Nie mam pełnego dowodu ani zweryfikowanego, ale uważam, że jest to ważny dowód. Aby zapoznać się z innymi zagadnieniami związanymi z tematem, możesz sprawdzić Uwaga techniczna: Niektóre właściwości kryteriów podziału - Leo Breiman . Teraz podąży za mną.

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

Aby znaleźć najlepszy podział, sortujemy wystąpienia według funkcji testowej i próbujemy wszystkich możliwych podziałów binarnych. Posortowane według danej funkcji jest w rzeczywistości permutacją instancji, w których klasy zaczynają się od instancji pierwszej klasy lub drugiej klasy. Nie tracąc ogólności, założymy, że zaczyna się ona od instancji pierwszej klasy (jeśli tak nie jest, mamy dowód lustrzany z tymi samymi obliczeniami).

$(1,0)$ $(a-1,b)$ $h(left) = 1 - (1/1)^2 - (0/1)^2 = 0$ . Więc po lewej stronie mamy mniejszą wartość indeksu Gini. Co powiesz na właściwy węzeł?

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$

$a$ $0$

Ostatnim etapem dowodu jest ustalenie, że biorąc pod uwagę wszystkie możliwe punkty podziału podyktowane danymi, zachowujemy ten, który ma najmniejszy zagregowany indeks gini, co oznacza, że wybrane przez nas optymalne jest mniejsze lub równe trywialny, który udowodniłem, że jest mniejszy. Co prowadzi do wniosku, że ostatecznie indeks gini spadnie.

Na koniec należy zauważyć, że nawet jeśli różne podziały mogą dawać wartości większe niż węzeł nadrzędny, ten, który wybieramy, będzie najmniejszy spośród nich, a także mniejszy niż wartość indeksu nadrzędnego gini.

Mam nadzieję, że to pomoże.

— rapaio
źródło

Dziękuję bardzo, odblokowałeś mój mózg ... W rzeczywistości, ponieważ mam do czynienia z drzewami regresji, użycie zmiennej klasy docelowej wydawało się mniej oczywiste niż w przypadku czystego zadania klasyfikacji. Ale teraz ma to sens.

— Remi Mélisson

Zaktualizowałem odpowiedź, aby zawierała brakujące części.

— rapaio