Różne algorytmy drzewa decyzyjnego z porównaniem złożoności lub wydajności

Question

Robię badania w zakresie eksploracji danych, a dokładniej drzew decyzyjnych.

chciałbym wiedzieć, czy istnieje wiele algorytmów do budowania drzewa decyzyjne (lub tylko jeden?), A co jest lepsze, na podstawie takich kryteriów, jak

• Wyniki
• złożoność
• Błędy w podejmowaniu decyzji
• i więcej.

Answer 1

implementacje Drzewo decyzyjne różnią się głównie wzdłuż tych osi:

• kryterium łupania (czyli jak "odchylenie" obliczana jest)

• czy buduje modele regresja (zmienne ciągłe, np., wynik) Oraz klasyfikacji (zmiennych dyskretnych, na przykład, klasa etykiety)

• techniką eliminacji/redukcji przez dopasowane

• czy może obsługiwać niekompletne dane

Głównymi implementacje decyzyjny są:

• ID3 lub iteracyjne Dichotomizer był pierwszym z trzech decyzyjny implementacjach rozwiniętych Ross Quinlanem (Quinlanem, J. R. 1986. Indukcja drzewa decyzyjne. Mach. Uczyć się. 1, 1 (marzec 1986), 81-106.)

• CART lub Drzewa klasyfikacyjne i regresyjne jest często używany jako ogólny akronimem dla terminu Drzewo decyzyjne, choć podobno ma bardziej konkretne znaczenie. Podsumowując, wdrożenie CART jest bardzo podobne do C4.5; jedyną zauważalną różnicą jest to, że CART konstruuje drzewo na podstawie numerycznego kryterium podziału rekursywnie stosowanego do danych, podczas gdy C4.5 zawiera pośredni etap konstruowania zestawu reguł s..

• C4.5, następna iteracja Quinlana.Nowe funkcje (w porównaniu z ID3) to: (i) akceptuje zarówno funkcje ciągłe, jak i dyskretne; (ii) obsługuje niekompletne punkty danych; (iii) rozwiązuje problem nadmiernego dopasowania przez (sprytnie) bardzo sprytna technika określana jako "przycinanie"; i (iv) różne wagi mogą być stosowane funkcje, które zawierają dane treningowe . Spośród nich, pierwsze trzy są bardzo ważne - i chciałbym zasugerować, że dowolna implementacja DT ma wszystkie trzy. Czwarte (ważenie różnicowe) jest znacznie mniej ważne.

• C5.0, najnowsza iteracja Quinlana. Ta implementacja objęta jest patentem i prawdopodobnie w wyniku tego rzadko jest implementowana (poza komercyjnymi pakietami oprogramowania). Nigdy nie kodowałem implementacji C5.0 (nigdy nie widziałem nawet kodu źródłowego), więc nie mogę zaoferować świadomego porównania C5.0 w stosunku do C4.5. Zawsze byłem sceptycznie nastawiony do ulepszeń zgłoszonych przez jego wynalazcę (Ross Quinlan) - na przykład twierdzi, że jest "o kilka rzędów wielkości" szybszy niż C4.5. Inne roszczenia są podobnie szerokie ("znacznie więcej pamięci efektywnej") i tak dalej. Po prostu wskażę ci studies , którzy zgłaszają wynik porównania obu technik i możesz sam zdecydować.

• CHAID (automatyczny detektor interakcji chi-kwadrat) faktycznie wyprzedza oryginalną realizację ID3 przez około sześć lat (opublikowany w tezy dr Gordon Kass w 1980 roku). Wiem, że każdy trochę o tym technique.The R platforma ma pakiet o nazwie CHAID który zawiera doskonałą dokumentację

• MARS (wypusty regresji wielo-adaptacyjne) jest rzeczywiście określenie zastrzeżone przez pierwotnego wynalazcę Mars, Salford Systems . Jako wynik , klony MARS w bibliotekach niesprzedanych przez Salford są nazywane czymś innym niż MARS - np. W R, odpowiednią funkcją są polimorfie w bibliotece poly-spline. Matlab i Statistica również implementacje z Marsem funkcjonalności

Polecam koszyka lub C4.5 (choć znowu, ja nie mają bezpośredniego doświadczenia z C5.0 lub CHAID, choć jestem zaznajomiony z ich funkcji zestawy).

C4.5 jest smakiem drzewa decyzyjnego zaimplementowanym w Orange; CART jest smakiem w sklearn - oby znakomite implementacje w doskonałych bibliotekach ML.

C4.5 jest ważnym krokiem poza ID3 - zarówno pod względem zakresie (C4.5 ma znacznie szersze spektrum przypadków użycia, ponieważ może obsługiwać zmiennych ciągłych w danych treningowych) i pod względem modelu jakość.

Być może najbardziej znacząca poprawa C5.0 twierdził kontra C4.5 jest wsparcie dla wzmocniony drzew. Wsparcie zespołów dla DT - wzmocnionych drzew i losowych lasów - zostało włączone do realizacji DT w Orange; tutaj obsługa zespołu została dodana do algorytmu C4.5. Sklearn oferuje także szereg losowych metod leśnych i wspomagających.