Algoritmus C4.5 - C4.5 algorithm - Wikipedia

C4.5 je algoritmus používaný ke generování a rozhodovací strom vyvinutý uživatelem Ross Quinlan.^[1] C4.5 je rozšířením Quinlanova dříve Algoritmus ID3. K klasifikaci lze použít rozhodovací stromy generované C4.5 az tohoto důvodu se C4.5 často označuje jako a statistický klasifikátor. V roce 2011 autoři Weka software pro strojové učení popsal algoritmus C4.5 jako „program s rozhodovacím stromem, který je pravděpodobně dosud nejpoužívanějším praktickým tahounem strojového učení“.^[2]

To se stalo docela populární po umístění # 1 v Top 10 algoritmů v dolování dat přední článek publikoval Springer LNCS v roce 2008.^[3]

Algoritmus

C4.5 vytváří rozhodovací stromy ze sady tréninkových dat stejným způsobem jako ID3 pomocí konceptu informační entropie. Data školení jsou sada ${ displaystyle S = {s_ {1}, s_ {2}, ...}}$ již klasifikovaných vzorků. Každý vzorek ${ displaystyle s_ {i}}$ sestává z p-rozměrného vektoru ${ displaystyle (x_ {1, i}, x_ {2, i}, ..., x_ {p, i})}$ , Kde ${ displaystyle x_ {j}}$ představují hodnoty atributu nebo funkce vzorku, stejně jako třída, ve které ${ displaystyle s_ {i}}$ padá.

V každém uzlu stromu si C4.5 vybere atribut dat, který nejefektivněji rozdělí jeho sadu vzorků na podmnožiny obohacené v jedné nebo druhé třídě. Kritériem rozdělení je normalizace zisk informací (rozdíl v entropie ). Pro rozhodnutí je vybrán atribut s nejvyšším normalizovaným ziskem informací. Algoritmus C4.5 pak opakuje na rozdělené podlisty.

Tento algoritmus má několik základní případy.

Všechny vzorky v seznamu patří do stejné třídy. Když k tomu dojde, jednoduše vytvoří uzel listu pro rozhodovací strom, který říká, že si má vybrat tuto třídu.
Žádná z funkcí neposkytuje žádné informace. V tomto případě C4.5 vytvoří rozhodovací uzel výše ve stromu pomocí očekávané hodnoty třídy.
Byla zjištěna instance dříve neviditelné třídy. C4.5 opět vytváří rozhodovací uzel výše ve stromu pomocí očekávané hodnoty.

Pseudo kód

v pseudo kód, obecný algoritmus pro vytváření rozhodovacích stromů je:^[4]

Zkontrolujte výše uvedené základní případy.
Pro každý atribut A, najděte normalizovaný poměr zisku informací od rozdělení A.
Nechat a_best být atributem s nejvyšším normalizovaným ziskem informací.
Vytvořte rozhodnutí uzel který se rozdělí a_best.
Rekurze na podlisty získané rozdělením na a_besta přidejte tyto uzly jako podřízené uzel.

Implementace

J48 je otevřený zdroj Jáva implementace algoritmu C4.5 v Weka dolování dat nástroj.

Vylepšení z algoritmu ID.3

C4.5 provedl řadu vylepšení ID3. Některé z nich jsou:

Zpracování spojitých i diskrétních atributů - Aby bylo možné zpracovat spojité atributy, vytvoří C4.5 prahovou hodnotu a poté rozdělí seznam na ty, jejichž hodnota atributu je nad prahovou hodnotou, a na ty, které jsou menší nebo rovny této hodnotě.^[5]
Zpracování tréninkových dat s chybějícími hodnotami atributů - C4.5 umožňuje, aby byly hodnoty atributů označeny jako? za zmizení. Chybějící hodnoty atributů se při výpočtech zisku a entropie jednoduše nepoužívají.
Zpracování atributů s různými náklady.
Prořezávání stromů po vytvoření - C4.5 se po vytvoření vrátí zpět do stromu a pokusí se odstranit větve, které nepomáhají, jejich nahrazením listovými uzly.

Vylepšení v algoritmu C5.0 / See5

Quinlan pokračoval v tvorbě C5.0 a See5 (C5.0 pro Unix / Linux, See5 pro Windows), které komerčně uvádí na trh. C5.0 nabízí řadu vylepšení na C4.5. Některé z nich jsou:^[6]^[7]

Rychlost - C5.0 je výrazně rychlejší než C4.5 (několik řádů)
Využití paměti - C5.0 je paměťově efektivnější než C4.5
Menší rozhodovací stromy - C5.0 získá podobné výsledky jako C4.5 s podstatně menšími rozhodovacími stromy.
Podpora pro posílení - Posílení vylepšuje stromy a poskytuje jim větší přesnost.
Vážení - C5.0 umožňuje vážit různé případy a typy nesprávné klasifikace.
Winnowing - možnost C5.0 automaticky vědí atributy k odstranění těch, které mohou být neužitečné.

Zdroj pro linuxovou verzi C5.0 s jedním vláknem je k dispozici pod GPL.

Viz také

Reference

^ Quinlan, J. R. C4.5: Programy pro strojové učení. Morgan Kaufmann Publishers, 1993.
^ Ian H. Witten; Eibe Frank; Mark A. Hall (2011). „Data Mining: Praktické nástroje a techniky strojového učení, 3. vydání“. Morgan Kaufmann, San Francisco. p. 191.
^ Umd.edu - top 10 algoritmů v dolování dat
^ S.B. Kotsiantis, "Supervised Machine Learning: A Review of Classification Techniques", Informatica 31(2007) 249-268, 2007
^ J. R. Quinlan. Vylepšené použití spojitých atributů v c4.5. Journal of Artificial Intelligence Research, 4: 77-90, 1996.
^ Je See5 / C5.0 lepší než C4.5?
^ M. Kuhn a K. Johnson, Aplikované prediktivní modelování, Springer 2013

externí odkazy

Původní implementace na domovské stránce Rossa Quinlana: http://www.rulequest.com/Personal/
Viz 5 a C5.0

[1] Quinlan, J. R. C4.5: Programy pro strojové učení. Morgan Kaufmann Publishers, 1993.

[2] Ian H. Witten; Eibe Frank; Mark A. Hall (2011). „Data Mining: Praktické nástroje a techniky strojového učení, 3. vydání“. Morgan Kaufmann, San Francisco. p. 191.

[3] Umd.edu - top 10 algoritmů v dolování dat

[4] S.B. Kotsiantis, "Supervised Machine Learning: A Review of Classification Techniques", Informatica 31(2007) 249-268, 2007

[5] J. R. Quinlan. Vylepšené použití spojitých atributů v c4.5. Journal of Artificial Intelligence Research, 4: 77-90, 1996.

[6] Je See5 / C5.0 lepší než C4.5?

[7] M. Kuhn a K. Johnson, Aplikované prediktivní modelování, Springer 2013

[1]

[2]

[3]

[4]

[5]

[6]

[7]