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.ZAA ≤ xT.
T.l= { t ∈ T: t ( A ) ≤ x }
i
T.r= { t ∈ 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 .bB = { b1, … , Bk}jaB = bja
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
ZA1, … , Am, C.
ZAjotdo( E1, E2), … , Ek)mija( ⋅ )
Δ = I( E) - ∑i = 1k| mija|| mi|ja( Eja)
mipjotmidojot
pjot= | { t ∈ E: t [ C] = cjot} || mi|
G i n i (E) = 1 - ∑j = 1Qp2)jot
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 )TlTr|Tl|/|T|=|Tr|/|T|=1/2Δ
Δ=1−1/22−1/22−0−0=1/2
Δ
Δ=1−1/22−1/22−1/2(1−(3/4)2−(1/4)2)−1/2(1−(1/4)2−(3/4)2)=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,CCAB
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).
źródło