Matematyka za drzewami klasyfikacji i regresji

Czy ktoś może wyjaśnić matematykę związaną z klasyfikacją w CART? Chcę zrozumieć, jak przebiegają dwa główne etapy. Na przykład przeszkoliłem klasyfikator CART na zestawie danych i użyłem testowego zestawu danych, aby oznaczyć jego predykcyjne działanie, ale:

1. Jak wybiera się początkowy korzeń drzewa?

2. Dlaczego i jak powstaje każda gałąź?

Mój zestaw danych, składający się z 400 tysięcy rekordów z 15 kolumnami i 23 klasami, osiąga 100% dokładność z macierzy zamieszania, używam 10-krotnej walidacji krzyżowej w zbiorze danych. Byłbym naprawdę wdzięczny, gdyby ktoś mógł wyjaśnić etapy klasyfikacji CART?

Drzewa CART i drzewa decyzyjne, takie jak algorytmy, działają poprzez rekurencyjne partycjonowanie zestawu szkoleniowego w celu uzyskania podzestawów, które są możliwie najczystsze dla danej klasy docelowej. Każdy węzeł drzewa jest powiązany z określonym zestawem rekordów który jest dzielony przez określony test elementu. Na przykład podział na ciągły atrybut A może być indukowany przez test A ≤ x . Zestaw rekordów T jest następnie dzielony na dwa podzbiory, które prowadzą do lewej gałęzi drzewa i prawej.$T$$A$$A \le x$$T$

$T_l = \{ t \in T: t(A) \le x \}$

i

$T_r = \{ t \in T: t(A) > x \}$

Podobnie funkcja jakościowa może być użyta do wywołania podziałów zgodnie z jej wartościami. Na przykład, jeśli B = { b 1 , ... , b k } każdej gałęzi i mogą być wywołane przez test B = b I .$B$$B = \{b_1, \dots, b_k\}$$i$$B = b_i$

Krok podziału algorytmu rekurencyjnego w celu wywołania drzewa decyzyjnego uwzględnia wszystkie możliwe podziały dla każdej cechy i próbuje znaleźć najlepszy według wybranej miary jakości: kryterium podziału. Jeśli Twój zestaw danych został wywołany na następującym schemacie

$$A_1, \dots, A_m, C$$

$A_j$$C$$(E_1, E_2, \dots, E_k)$$E$$I(\cdot)$

$$\Delta = I(E) - \sum_{i=1}^{k}\frac{|E_i|}{|E|}I(E_i)$$

$E$$p_j$$E$$c_j$

$$p_j = \frac{|\{t \in E:t[C] = c_j\}|}{|E|}$$ $$\mathit{Gini}(E) = 1 - \sum_{j=1}^{Q}p_j^2$$ $Q$

Prowadzi to do zanieczyszczenia 0, gdy wszystkie rekordy należą do tej samej klasy.

$T$$(1/2, 1/2)$$T$

$T_l$$(1,0)$$T_r$$(0,1)$$T_l$$T_r$$|T_l|/|T| = |T_r|/|T| = 1/2$$\Delta$

$$\Delta = 1 - 1/2^2 - 1/2^2 - 0 - 0 = 1/2$$

$\Delta$

$$\Delta = 1 - 1/2^2 - 1/2^2 - 1/2 \bigg( 1 - (3/4)^2 - (1/4)^2 \bigg) - 1/2 \bigg( 1 - (1/4)^2 - (3/4)^2 \bigg) = 1/2 - 1/2(3/8) - 1/2(3/8) = 1/8$$

Pierwszy podział zostanie wybrany jako najlepszy, a następnie algorytm będzie działał rekurencyjnie.

Łatwo jest sklasyfikować nową instancję za pomocą drzewa decyzyjnego, w rzeczywistości wystarczy podążać ścieżką od węzła głównego do liścia. Rekord jest klasyfikowany według większościowej klasy liścia, który osiąga.

Powiedzmy, że chcemy sklasyfikować kwadrat na tej figurze

$A,B,C$$C$$A$$B$

Możliwe drzewo decyzji może być następujące:

Oczywiste jest, że kwadrat rekordu zostanie sklasyfikowany według drzewa decyzyjnego jako okrąg, biorąc pod uwagę, że rekord spada na liść oznaczony kółkami.

W tym przykładzie zabawki dokładność zestawu treningowego wynosi 100%, ponieważ żaden rekord nie jest źle sklasyfikowany przez drzewo. Na graficznej reprezentacji zestawu treningowego powyżej możemy zobaczyć granice (szare linie przerywane), których drzewo używa do klasyfikowania nowych instancji.

Jest mnóstwo literatury na temat drzew decyzyjnych, chciałem tylko napisać szkicowe wprowadzenie. Inną znaną implementacją jest C4.5.

Nie jestem ekspertem od CART, ale możesz wypróbować książkę „Elementy statystycznego uczenia się”, która jest dostępna bezpłatnie online (patrz rozdział 9 dotyczący CART). Myślę, że książka została napisana przez jednego z twórców algorytmu CART (Friedman).