Drzewa Decyzyjne i Niezachłanny Impurez: Jak CART Wytnie Dane

Podział danych jednym pionowo ułożonym cięciem po razu

Drzewo decyzyjne CART (Classification And Regression Trees, Breiman et al. 1984) klasyfikuje punkty zadając sekwencję pytań typu "czy cecha x jest mniejsza niż pewien próg t?" Każde pytanie stanowi pojedyncze, pionowo ułożone cięcie danych, a drzewo wynikowe to po prostu wcięte, nierozerwalne sekwencje tych cięć, wizualizowane jako prostokąty dzielące przestrzeń wejściową. Na naprawdę nieliniowej granicy, jak np. XOR, żaden pojedynczy cieć nie oddziela klas, ale dwa cięcia w kolejności, po jednym osi, izolują cztery kwadranty idealnie, co dokładnie można obserwować poziom po poziomie w animacji automatycznego wzrostu.

Wybór najlepszego podziału z użyciem współczynnika Giniego

Na każdym węźle algorytm CART testuje wszystkie cechy i wszystkie kandydatowe wartości progowe, wybierając ten podział, który najmocniej redukuje współczynnik Giniego:

Współczynnik Giniego mierzy stopień mieszania się klas w węźle: Gini(węzeł) = 1 - Σ p_k^2 p_k część przypadków w węźle należących do klasy k Gini = 0 węzeł jest czysty, wszystkie jedna klasa Gini = 0.5 węzeł jest maksymalnie zmieszany (dwuklasowy, 50/50) zysk_podziału = Gini(rodzic) - ( n_lewe/n * Gini(lewy) + n_prawe/n * Gini(prawy)) Algorytm wybiórczo wybiera podział z największym zyskiem podziału na każdym węźle, rekurencyjnie działając na lewym i prawym potomstwie. Jest to lokalnie-optymalne, żądane podejście: każdy podział jest najlepszy dostępny w danym momencie, bez uwzględniania potencjalnych korzyści płynących z podziałów, które mogłyby się opłacić na dwóch poziomach głębszych, co powoduje, że drzewa decyzyjne mogą być trenowane w czasie zbliżonym do O(n*d*log n) (n próbek, d cech), ale nie gwarantują znalezienia drzewa o najmniejszym rozmiarze, które najlepiej pasuje do danych.

Gini(node) = 1 − Σ p_k²

p_k   fraction of samples in the node belonging to class k

Gini = 0        node is pure, all one class
Gini = 0.5      node is maximally mixed (2-class, 50/50)

split_gain = Gini(parent) − ( n_left/n · Gini(left) + n_right/n · Gini(right) )

Dlaczego głębokie drzewa zapamiętują zamiast uczyć się

Pozostawione bez kontroli, algorytm CART kontynuuje dzielenie aż do momentu, w którym każdy liść jest czysty lub zawiera jeden przykład. Oznacza to, że może wyrysować dowolnie skomplikowaną granicę wokół pojedynczych szumów — klasyczne przeuczenie (overfitting). Na zbiorach danych Moons lub Blobs w tej symulacji można to obserwować bezpośrednio: na wczesnych etapach uchwycone jest rzeczywiste ułożenie klastrów, ale po głębokości 6–8 drzewo zaczyna rysować cienkie palce wokół pojedynczych punktów odstających, granice, które nie będą generalizować się na nowe dane. Zwykle stosuje się ograniczenie maksymalnej głębokości, wymóg minimalnej liczby próbek na liście lub wzrost pełnego drzewa a następnie przycinanie gałęzi, które nie poprawiają wydajności walidacji.

Gini Impurity w porównaniu z Zyskiem Informacji

W CART (Classification and Regression Trees) i kryterium Gini oraz alternatywne kryterium entropii/zysku informacji (używane przez ID3 i C4.5) prawie zawsze wybierają bardzo podobne podziały w praktyce; oba są funkcjami wypukłymi proporcji klas, które wynoszą zero dla czystego węzła i maksymalną wartość przy podziale na dwie równe części. Gini jest marginalnie tańszy do obliczenia (brak logarytmu) i jest domyślny w implementacji scikit-learn, co jest jedną z przyczyn jego popularności, choć drzewa otrzymane z niego rzadko różnią się znacząco.

Od jednego drzewa do lasu

Poszczególne drzewa są o wysokiej wariancji: ponowne wytrenowanie ich na nieznacznie innym zbiorze próbek oraz zmiana wczesnych podziałów, od których zależy każdy kolejny podział, może nastąpić całkowicie. Random Foresty i drzewa boosted budują na dokładnie tym mechanizmie, który tutaj przedstawiono – wiele drzew CART, każde wytrenowanych na bootstrapowej próbce i losowym podzbiorze cech (lasy) lub każde korygujących resztkowe błędy poprzedniego drzewa (boosting), a następnie średnio lub sumują ich prognozy, aby wyeliminować tendencję do przeuczenia pojedynczego drzewa na rzecz znacznie lepszej generalizacji, kosztem utraty łatwej interpretowalności pojedynczego drzewa.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Decision Tree Live i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.