C4.5 je algoritmus používaný k vytváření rozhodovacích stromů, který vyvinul Ross Quinlan. C4.5 je rozšířením Quinlanova staršího algoritmu ID3. Rozhodovací stromy generované algoritmem C4.5 lze použít pro klasifikaci, a proto je C4.5 často označován jako statistický klasifikátor.
V roce 2011 autoři softwaru pro strojové učení Weka popsali algoritmus C4.5 jako „přelomový program pro rozhodovací stromy, který je pravděpodobně dosud nejpoužívanějším pracovním nástrojem strojového učení v praxi“. Stal se velmi populárním poté, co se umístil na prvním místě v prestižním článku Top 10 Algorithms in Data Mining, publikovaném nakladatelstvím Springer v řadě LNCS v roce 2008.Umd.edu – Top 10 Algorithms in Data Mining
Algoritmus C4.5 vytváří rozhodovací stromy z množiny trénovacích dat stejným způsobem jako ID3, pomocí konceptu informační entropie. Trénovací data jsou množina již klasifikovaných vzorků. Každý vzorek se skládá z p-rozměrného vektoru , kde představují hodnoty atributů nebo vlastnosti vzorku a třídu, do které spadá.
V každém uzlu stromu C4.5 vybere atribut dat, který nejúčinněji rozdělí množinu vzorků na podmnožiny s bohatším zastoupením jedné nebo druhé třídy. Kritériem rozdělení je normalizovaný informační zisk (rozdíl v entropii). Atribut s nejvyšším normalizovaným informačním ziskem je vybrán pro rozhodnutí. Algoritmus C4.5 poté rekurzivně pokračuje na rozdělených podseznamech.
Tento algoritmus má několik základních případů: Všechny vzorky v seznamu patří do stejné třídy. Když k tomu dojde, jednoduše se vytvoří list rozhodovacího stromu, který říká, že má být zvolena tato třída. Žádný z atributů neposkytuje žádný informační zisk. V tomto případě C4.5 vytvoří rozhodovací uzel výše v hierarchii stromu pomocí očekávané hodnoty třídy. Je nalezen vzorek dříve neviděné třídy. Opět C4.5 vytvoří rozhodovací uzel výše pomocí očekávané hodnoty.
Pseudokód V pseudokódu je obecný algoritmus pro vytváření rozhodovacích stromů následující:
Zkontroluj výše uvedené základní případy. Pro každý atribut a najdi normalizovaný poměr informačního zisku z rozdělení podle a. Nechť abest je atribut s nejvyšším normalizovaným informačním ziskem. Vytvoř rozhodovací uzel, který se rozdělí podle abest. Rekurzivně pokračuj na podseznamech získaných rozdělením podle abest a přidej tyto uzly jako potomky uzlu.
Vylepšení oproti algoritmu ID3 C4.5 přinesl řadu vylepšení oproti ID3. Některá z nich jsou:
Zpracování spojitých i diskrétních atributů: Aby mohl zpracovávat spojité atributy, C4.5 vytvoří práh a poté rozdělí seznam na ty, jejichž hodnota atributu je nad prahem, a na ty, jejichž hodnota je menší nebo rovna prahu. Zpracování trénovacích dat s chybějícími hodnotami atributů: C4.5 umožňuje označit hodnoty atributů jako chybějící. Chybějící hodnoty atributů se nepoužívají ve výpočtech informačního zisku a entropie. Zpracování atributů s různými náklady. Prořezávání stromů po vytvoření: C4.5 po skončení strom prochází zpětně a pokouší se odstranit větve, které nepomáhají klasifikaci.
Vylepšení v algoritmu C5.0/See5 Quinlan později vytvořil algoritmy C5.0 a See5 (C5.0 pro Unix/Linux, See5 pro Windows), které komerčně nabízí. C5.0 nabízí řadu vylepšení oproti C4.5. Některá z nich jsou:Is See5/C5.0 Better Than C4.5?
Rychlost – C5.0 je výrazně rychlejší než C4.5, a to o několik řádů. Využití paměti – C5.0 je paměťově efektivnější než C4.5. Menší rozhodovací stromy – C5.0 dosahuje podobných výsledků jako C4.5 s podstatně menšími rozhodovacími stromy. Podpora boostingu – boosting vylepšuje stromy a zvyšuje jejich přesnost. Vážení – C5.0 umožňuje vážit různé případy a typy chybných klasifikací. Prosévání (winnowing) – volba v C5.0 automaticky prosévá atributy, aby odstranila ty, které mohou být neužitečné.
Zdrojový kód pro jednovláknovou linuxovou verzi C5.0 je dostupný pod licencí GNU General Public License (GPL).
Reference
Externí odkazy Původní implementace na domovské stránce Rosse Quinlana See5 a C5.0
Kategorie:Algoritmy Kategorie:Strojové učení