C4.5 algoritam

C4.5 je algoritam koji generiše drvo odlučivanja i koji je razvio Ross Quinlan. C4.5 je unapređenje u odnosu na ID3 algoritam koji je takođe pronašao Quinlan. Drvo odlučivanja generisano pomoću C4.5 algoritma se koristiti za klasifikaciju zbog čega se često naziva i statistički klasifikator.

Algoritam

C4.5 pravi drvo odlučivanja iz skupa trening podataka na isti način na koji to radi i ID3 algoritam, koristeći koncept entropije. Trening podaci su skup $S={s_{1},s_{2},...}$ od već klasifikovanih uzoraka. Svaki uzorak $s_{i}$ sastoji se od p-dimenzionalnog vektora $(x_{1,i},x_{2,i},...,x_{p,i})$, gde $x_{j}$ predstavlja atribute ili funkcije uzorka, kao i klasu kojoj $s_{i}$ pripada.

U svakom čvoru drveta, C4.5 bira atribut koji najefikasnije razdvaja skup uzoraka u podskupove povećavajući kvalitet u jednoj ili drugoj klasi. Kriterijum po kojem se razdvaja je normalizovana informaciona dobit. Atributi koji imaju najveću normalizovanu informacionu dobit biraju se za donošenje odluke. C4.5 algoritam se onda rekurzivno primenjuje na manjim podlistama.

Ovaj algoritam ima nekoliko osnovnih slučajeva.

• Svi uzorci pripadaju istoj klasi. Kada se ovo dogodi, kreiramo list u drvetu odlučivanja koji nam govori da odaberemo datu klasu.
• Nijedna karakteristika ne obezbeđuje nikakvu informacionu dobit. U ovom slučaju, C4.5 kreira odluku na čvoru višeg nivoa koristeći očekivanu vrednost klase.
• Pojavljuje se instanca klase koja prethodno nije razmatrana. C4.5 opet kreira odluku na čvoru višeg nivoa koristeći očekivanu vrednost klase.

Pseudokod

Opšti algoritam za pravljenje drveta odlučivanja je:

1. Proveriti bazne slučajeve
2. Za svaki atribut a
   1. Pronaći normalizovanu informacionu dobit prilikom razdvajanja po a
3. Postaviti da a_maks bude atribut koji ima najveću normalizovanu informacionu dobit
4. Kreirati čvor koji se deli po atributu a_maks
5. Primeniti rekurziju na podliste (koje su dobijene razdvajanjem po atributu a_maks) i dodati te čvorove kao decu datog čvora

Implementacija

J48 je Java implementacija C4.5 algoritma otvorenog koda u Weka alatu za istaživanje podataka. TimeSleuth proširuje upotrebu C4.5 algoritma korišćenjem privremenih i uzročnih otkrića. TimeSleuth takođe dopušta konverziju C4.5 pravila u Prolog iskaze.

Poboljšanja u odnosu na ID3 algoritam

C4.5 je napravio niz poboljšanja u odnosu na ID3. Neka od poboljšanja su:

• Podržavanje i kontinuiranih i diskretnih atributa - Da bi podržao kontinuirane atribute, C4.5 kreira prag i onda deli liste na one čija vrednost atributa je iznad praga i na one čija je vrednost atributa manja ili jednaka pragu.
• Podržavanje trening podataka sa nedostajućim vrednostima atributa - C4.5 dozvoljava da vrednost atributa bude označena sa ? ukoliko nedostaje. Nedostajuća vrednost se jednostavno ne koristi u izračunavanjima dobiti i entropije.
• Podržavanje atributa sa različitim troškovima.
• Potkresivanje drveta nakon kreiranja - C4.5 algoritam posle kreiranja drveta odlučivanja se vraća kroz drvo i pokušava da ukloni grane koje nisu od koristi zamenjujući ih za list.

Poboljšanja u C5.0/See5 algoritmu

Quinlan je radio i na stvaranju C5.0/See5 (C5.0 za Unix/Linux, See5 za Windows) algoritma koji će biti komercijalan. Algoritam C5.0 nudi niz unapređenja u odnosu na C4.5. Neka od unapređenja su:

• Brzina - C5.0 je značajno brži od C4.5 (nekoliko redova veličine)
• Upotreba memorije - C5.0 je mnogo memorijski efikasniji od C4.5
• Manje drvo odlučivanja - C5.0 dobija slične rezultate kao i C4.5 ali sa znatno manjim drvetom odlučivanja.
• Podrška za boosting - poboljšava drveće i daje im veću tačnost.
• C5.0 ima mogućnost da automatski ukloni atribute koji mu nisu od pomoći.

Izvorni kod za Linux verziju algoritma C5.0 je dostupan pod GNU licencom.