Alternativní metody rozhodovacích stromů

David Filip

dejv.eutwitter.com/dejv

davidfilip@gmail.com

Osnova

• Rozhodovací stromy Historie, algoritmy, limity

• Alternativní techniky rozhodovacích stromů Bagging, boosting, random forest, genetické stromy

• Proudy dat• Swarm trees

Rozhodovací stromy

Rozhodovací strom

• Nejsnáze pochopitelná technika ML• Funguje prakticky na všech typech dat:

kategorické, numerické, chybějící, ...• Velmi snadno vizualizovatelné• Snadný převod na if-then pravidla

Historie

• Vznik koncem 70. let

• Ross Quinlan:1986 – ID31993 – C4.5

• 1995 - Random Forest

Obecný algoritmus

– Zvol jeden atribut jako kořen dílčího stromu– Rozděl data v tomto uzlu na podmnožiny podle

hodnot a přidej uzel pro každou podmnožinu– Opakuj dokud je co rozdělovat

Výběr atributu záleží na zvoleném algoritmu, často se používá entropie/informační zisk.

Limity rozhodovacích stromů

• Učení optimálního rozhodovacího stromu je NP-úplný problém => je třeba využít heuristických algoritmů k nalezení lokálního optima pro každý uzel.

• Generování vede k přeučení (overfitting). Je třeba provádět prořezávání.

• Existují koncepty, které jsou složité pro učení rozhodovacích stromů (např. XOR), vznikají složité stromy.

Benchmark

http://videolectures.net/mlas06_cohen_tc/

Dataset: Reuters-21578 newswire stories9603 train, 3299 test documents, 80-100 words each, 93 classes

Alternativní metody

Leo Breiman

• 1928 – 2005 • University of California, Berkeley• Výzkum rozhodovacíh a regresních stromů• Bagging + Random Forest

Bagging

Bootstrap aggregating• Z trénovacích dat vytvoříme N stejně velkých

podmnožin pomocí náhodného výběru s opakováním (= jedna trénovací položka může být vložena vícekrát).

• Na těchto podmnožinách necháme naučit N rozhodovacích stromů.

• Při klasifikaci hlasují o výsledku.

Boosting

• Iterativně vytváříme nové modely• Každý nový model se zaměřuje na příklady,

které se nepodařilo správně klasifikovat• Výsledkem iterace vzniká pouze jeden strom

Známý algoritmus AdaBoost (Shapire, 1999)

Random Forest

• Kombinace baggingu a náhodného výběru parametrů

• Stromy se neprořezávají• Zvládá datové soubory s velkým množstvím

parametrů a učení je velmi rychlé• Nevýhoda: overfitting, nepříliš velká

úspěšnost pro data s šumem

Genetické Stromy

• Náhodně vytvoříme množinu minimálních stromů

• Podle výsledku testu vybíráme nejlepší stromy, které rozrůstáme, mutujeme a křížíme

• Opakujeme dokud nezískáme uspokojivý klasifikátor

Jakub Gajarský, 2009: Efektívne algoritmy pre učenie rozhodovacích stromov

Proudy dat

Typický Přístup k Datům v ML

• Máme množinu učících příkladů uloženou v paměti či v jiném uložišti.

• Jednotlivé algoritmy mají přístup k těmto datům opakovaně.

Příklad: C4.5 opakovaně načítá data a hledá, který parametr nejlépe rozdělí množinu.

Proudy dat

• Proud dat je sekvence jednotlivých příkladů, kde každý příklad může být čten pouze jednou či po nějaký (krátký) časový úsek

• Motivace: potřebujeme jednotlivé případy zpracovávat rychle

• Příklady: bankovní či telefonické transakce, sensorové sítě, síťové logy

Swarm Trees

Very Fast Decission Tree

• Algoritmus na učení rozhodovacích stromů z proudů dat

• Využívá Hoeffdingovo ohraničení: určuje kolik příkladů je potřeba výběr nejlepšího atributu

• Horší účinnost než jiné metody: potřeba použít na velkých datasetech → množství dat vždy překoná kvalitu algoritmu (Norvig)

Distribuované učení

• Učení: vytvořím N VFDT klasifikátorů a ty pak spustím na jednotlivých podstreamech

• Klasifikace: "obešlu" všechny klasifikátory a ty hlasují o výsledné třídě

Swarm Inteligence

• Inspirováno přírodními koloniemi (např. mravenci, včely) či obecně genetickými algoritmy

• V množině VFDT stromů se snažím vytvářet co nejvíce nehomogení společnost: odstraňuji podobné stromy, čímž podporuju pokrývání celého stavového prostoru