CART (Classification and Regression Trees)

Wprowadzenie

CART (Classification and Regression Trees) to algorytm drzew decyzyjnych wykorzystywany w uczeniu maszynowym zarówno do zadań klasyfikacji, jak i regresji. Jest to jeden z najbardziej fundamentalnych i szeroko stosowanych algorytmów drzewiastych, ceniony za swoją prostotę, interpretowalność i zdolność do przetwarzania danych o różnorodnych typach. Algorytm CART dzieli przestrzeń cech na serię binarnych podziałów, tworząc strukturę drzewa, gdzie każdy węzeł wewnętrzny reprezentuje test na atrybucie, a każdy liść reprezentuje przewidywaną klasę lub wartość. Dzięki swojej nieliniowej i nieparametrycznej naturze, jest w stanie modelować złożone relacje w danych bez konieczności zakładania konkretnej dystrybucji danych.

Jak działają algorytm CART?

Algorytm CART działa na zasadzie rekurencyjnego dzielenia zbioru danych. Na każdym kroku, w węźle drzewa, algorytm szuka binarnego podziału (np. „czy cecha X > wartość Y?”) dla jednej z cech, który najlepiej rozdziela dane pod względem zmiennej docelowej. Dla zadań klasyfikacji kryterium podziału jest zazwyczaj indeks Giniego (mierzący „nieczystość” węzła – im niższy indeks, tym bardziej jednorodny węzeł pod względem klas). Dla zadań regresji używa się redukcji wariancji (im większa redukcja wariancji po podziale, tym lepiej). Proces podziału kontynuowany jest rekurencyjnie, tworząc nowe węzły i poddrzewa, aż do spełnienia pewnych kryteriów zatrzymania. Mogą to być: osiągnięcie maksymalnej głębokości drzewa, minimalna liczba próbek w węźle, osiągnięcie minimalnego spadku nieczystości po podziale lub gdy wszystkie próbki w węźle należą do tej samej klasy (lub mają zbliżoną wartość w przypadku regresji). Po zbudowaniu drzewa, często stosuje się proces przycinania (pruning). Ma to na celu redukcję złożoności drzewa i zapobieganie nadmiernemu dopasowaniu (overfitting). Przycinanie może być wykonywane w trakcie budowy drzewa (pre-pruning) poprzez restrykcyjne kryteria zatrzymania, lub po jego pełnym zbudowaniu (post-pruning), usuwając gałęzie, które nie wnoszą znaczącej wartości predykcyjnej na danych walidacyjnych. Przewidywania są dokonywane poprzez sprowadzenie obserwacji w dół drzewa do węzła liściastego, a następnie przypisanie jej klasy większościowej (klasyfikacja) lub średniej wartości (regresja) próbek w tym liściu.

Główne zalety i charakterystyka

Główne zalety algorytmu CART to jego **wysoka interpretowalność i przejrzystość**. Struktura drzewa decyzyjnego jest łatwa do wizualizacji i zrozumienia, co pozwala na łatwe śledzenie procesu decyzyjnego i identyfikację najważniejszych cech wpływających na wynik. CART jest również **odporny na różnorodne typy danych** – może przetwarzać cechy numeryczne i kategoryczne bez konieczności skomplikowanego wstępnego przetwarzania. Jako model nieliniowy i nieparametryczny, potrafi uchwycić złożone interakcje między cechami, których modele liniowe by nie dostrzegły. Jest również **stosunkowo odporny na wartości odstające** w danych wejściowych, a jego implementacja jest relatywnie prosta.

Zastosowania w praktyce

• Diagnoza medyczna i prognozowanie ryzyka chorób (np. przewidywanie zawału serca na podstawie danych pacjenta)
• Analiza zachowań klientów i prognozowanie rezygnacji (churn prediction) w sektorach telekomunikacji czy bankowości
• Ocena ryzyka kredytowego i wykrywanie oszustw finansowych
• Klasyfikacja obrazów i rozpoznawanie wzorców (np. identyfikacja typów roślin na zdjęciach)
• Systemy rekomendacyjne, pomagające personalizować oferty produktów lub usług

Porównanie z innymi strukturami danych

W porównaniu do innych algorytmów drzew decyzyjnych, takich jak ID3 czy C4.5, algorytm CART wyróżnia się przede wszystkim **obsługą zadań regresji** oraz tym, że zawsze tworzy **binarne podziały**. ID3 działa wyłącznie w klasyfikacji i preferuje cechy kategoryczne, a C4.5 jest jego rozszerzeniem, które również generuje podziały wielokrotne i radzi sobie z brakującymi danymi. Drzewa CART są zazwyczaj prostsze w strukturze niż drzewa C4.5, co może przekładać się na lepszą interpretowalność, choć czasem kosztem pewnej precyzji. Względem bardziej złożonych modeli, takich jak maszyny wektorów nośnych (SVM) czy sieci neuronowe, drzewa CART oferują **nieporównywalnie lepszą interpretowalność**, co jest kluczowe w domenach wymagających wyjaśnienia decyzji (np. medycyna, finanse). Jednak pojedyncze drzewa CART są często **mniej dokładne** niż te bardziej zaawansowane metody, szczególnie w przypadku bardzo złożonych relacji w danych. Ich moc jest często ujawniana w algorytmach zespołowych (ensemble methods), takich jak Random Forest czy Gradient Boosting, gdzie wiele drzew CART jest łączonych w celu zwiększenia stabilności i precyzji.

Najlepsze praktyki (2026)

• Regulacja hiperparametrów, takich jak `max_depth` (maksymalna głębokość), `min_samples_leaf` (minimalna liczba próbek w liściu) czy `min_samples_split` (minimalna liczba próbek wymagana do podziału węzła), aby zapobiec nadmiernemu dopasowaniu i znaleźć optymalną złożoność drzewa.
• Wykorzystanie w algorytmach zespołowych (ensemble methods) jak Random Forest, Gradient Boosting Machine (GBM) czy XGBoost, co znacznie poprawia ich stabilność i zdolność predykcyjną, redukując problem wysokiej wariancji pojedynczych drzew.
• Przetwarzanie wstępne danych, w tym odpowiednie kodowanie cech kategorycznych (np. one-hot encoding, label encoding) oraz radzenie sobie z brakującymi wartościami, mimo że CART jest na to mniej wrażliwy niż inne algorytmy.
• Stosowanie walidacji krzyżowej (cross-validation) do oceny wydajności modelu i doboru hiperparametrów, co pozwala na obiektywną ocenę zdolności uogólniania modelu na niewidziane dane.
• Analiza ważności cech (feature importance) – drzewa CART naturalnie dostarczają informacji o tym, które cechy mają największy wpływ na podziały, co jest cenne w eksploracji danych.

Typowe błędy i pułapki

• **Nadmierne dopasowanie (overfitting)**: Drzewa CART, szczególnie te głębokie, mogą łatwo nadmiernie dopasować się do danych treningowych, ucząc się szumu i specyficznych wzorców, które nie uogólniają się dobrze na nowe dane. Należy zawsze stosować przycinanie lub ograniczać głębokość drzewa.
• **Niestabilność**: Małe zmiany w danych treningowych mogą prowadzić do zupełnie innej struktury drzewa, co sprawia, że pojedyncze drzewa są wrażliwe na zmiany w zbiorze danych. Tę wadę adresują algorytmy zespołowe.
• **Problem optymalizowanego lokalnie podziału**: Algorytm CART wybiera najlepszy podział na każdym kroku lokalnie (zachłannie), co nie zawsze prowadzi do globalnie optymalnego drzewa. Decyzje podjęte na wczesnych etapach są trudne do skorygowania w dalszej budowie drzewa.
• **Brak zdolności do ekstrapolacji w regresji**: Drzewa regresyjne przewidują wartości będące średnią z próbek w węźle liściastym. Nie są w stanie przewidzieć wartości spoza zakresu obserwowanych wartości treningowych dla danej cechy.
• **Brak równowagi klas**: W przypadku niezbalansowanych zbiorów danych, drzewo może być tendencyjne w stronę klasy większościowej, ignorując mniejszościowe klasy. Wymaga to odpowiedniego ważenia klas lub strategii undersamplingu/oversamplingu danych.