Изворни код странице C4.5 algoritam

{{Neprovereni seminarski}}

'''C4.5''' je algoritam koji generiše [[drvo odlučivanja]] i koji je razvio [[Ross Quinlan]]<ref>Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.</ref>. C4.5 je unapređenje u odnosu na [[ID3 algoritam|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 <math>S = {s_1, s_2, ...}</math> od već klasifikovanih uzoraka. Svaki uzorak <math> s_i</math> sastoji se od p-dimenzionalnog vektora <math>(x_{1,i}, x_{2,i}, ...,x_{p,i}) </math>, gde <math> x_j </math> predstavlja atribute ili funkcije uzorka, kao i klasu kojoj <math> s_i </math> 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:<ref>S.B. Kotsiantis, Supervised Machine Learning: A Review of Classification Techniques, Informatica 31(2007) 249-268, 2007</ref>
# Proveriti bazne slučajeve
# Za svaki atribut ''a''
## Pronaći normalizovanu informacionu dobit prilikom razdvajanja po ''a''
# Postaviti da ''a_maks'' bude atribut koji ima najveću normalizovanu informacionu dobit
# Kreirati čvor koji se deli po atributu ''a_maks''
# Primeniti rekurziju na podliste (koje su dobijene razdvajanjem po atributu ''a_maks'') i dodati te čvorove kao decu datog čvora

=== Implementacija ===
'''J48''' je [[Java (програмски језик)|Java]] implementacija C4.5 algoritma [[отворен код|otvorenog koda]] u [[Weka (machine learning)|Weka]] alatu za [[Analiza podataka|istaživanje podataka]]. TimeSleuth<ref>K. Karimi and H.J. Hamilton, TimeSleuth: A Tool for Discovering Causal and Temporal Rules, ICTAI, 2002</ref> 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.<ref>K. Karimi and H.J. Hamilton, Logical Decision Rules: Teaching C4.5 to Speak Prolog, IDEAL, 2000</ref>


=== 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.<ref>J. R. Quinlan. Improved use of continuous attributes in c4.5. {{cite journal|author=|date=1996 |title= |journal=Journal of Artificial Intelligence Research, |volume=4|issue=|pages=77–90|doi=}}.</ref>
* 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<ref>[http://www.rulequest.com/see5-comparison.html Is See5/C5.0 Better Than C4.5?]</ref>:

* 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 (meta-algorithm)|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.

== Референце ==
{{reflist}}

{{normativna kontrola}}

[[Категорија:Seminarski radovi/MATF januar 2014.]]
[[Категорија:Algoritmi]]