ID3 un C5.0

2. Teorētiskais pamatojums.
ID 3
Grafs ar vairākām virsotnēm ir induktīvais lēmuma koks. Virsotnes savā starpā ir saistītas ar lokiem. Katra no virsotnēm attēlo kādu ne-mērķa atribūtu un katrs loks iespējamo šī atribūta vērtību. Mērķa virsotnes atspoguļo atribūta gaidīto vērtību vai klasi.
Sākuma virsotne lēmumu kokā tiek dēvēta par saknes virsotni. Lai klasificētu nezināmu objektu, tā atribūta vērtības ir jāpārbauda ar lēmuma koka palīdzību, kā rezultātā rodas ceļš, kas ved no saknes virsotnes uz koka lapu, kas satur klases paredzējumu. Priekšrocība lēmumu kokiem ir tā, ka tos ir samērā viegli pārveidot klasifikācijas likumos.
Lēmumu koku sastādīšanas algoritms ID3 ģenerē lēmumu koku no dotas apmācošās datu kopas, kur ieejas dati ir eksemplāri, attēloti kā diskrētu vērtības atribūti un to saraksts.
Lēmumu koka izveidošanas algoritms ir rekursīvs un tā soļi ir šādi:
1) Izveido virsotni (N);
2) Atgriezt N kā koka lapu, ja eksemplāri ir visi no vienas klases C. Koka lapas nosaukums ir klase C;
3) Ja atribūtu saraksts ir tukšs, tad atgriezt N kā koka lapu, kuras nosaukums ir visizplatītākā klase apmācošā kopā;
4) Atlasīt atribūtu no atribūtu saraksta ar visaugstāko informācijas labumu, kas tiek dēvēts par pārbaudes atribūts;
5) Nosauc virsotni N kā pārbaudes atribūtu;
6) Katrai zināmajai vērtībai ai no pārbaudes atribūtiem
7) Pievieno zaru virsotnei N nosacījumam pārbaudes atribūts = ai;
8) Apzīmē si kā apmācošo datu kopas kopu katram, kuram atribūts = ai;
9) Ja kopa si ir tukša, tad pievieno lapu, nosauktu visvairāk sastopamākās klases vārdā iekš apmācošo datu kopas datiem. Pretējā gadījumā pievienot virsotni atgrieztu funkcijai
Atribūts ar visaugstāko informācijas labumu tiek izvēlēt kā pārbaudes atribūts tekošai virsotnei. Šis atribūts minimizē informācijas vajadzību, lai klasificētu eksemplārus rezultējošos nodalījumos un atspoguļo nejaušību šajos gadījumos. Šāda informācijas teorijas pieeja minimizē gaidāmo pūļa apjomu, lai klasificētu objektu un garantētu vienkārša koka atrašanu.
Gaidāmā informācijas vajadzība tiek aprēķināta ar formulas (1) palīdzību.

…