Inteligenţa Artificială studiază entităţile inteligente

Învăţarea prin arbori de decizie:

Învăţarea prin arbori de decizie este unul dintre cei mai simpli şi totuşi una dintre cele mai de succes metode de învăţare. Este o bună introducere pentru aria învăţării inductive şi este uşor de implementat.

Arborii de decizie primesc la intrare o situaţie, descrisă printr-un set de proprietăţi, şi au ca ieşire o decizie de forma ”Da / Nu”. De aceea arborii de decizie reprezintă funcţii booleene. Fiecare nod intern din arbore corespunde unui test al valorii unei proprietăţi ţi fiecare ramură a nodului este etichetată cu o valoare posibilă a testului. Fiecare nod frunză din arbore specifică o valoare booleană ce va fi returnată dacă se va merge pe un drum în arbore ce conduce la acel nod.

Ca un exemplu, să considerăm următoarea problemă: să se aştepte sau nu pentru o masă în restaurant. Predicatul scop este VomAştepta iar definiţia acestui predicat este exprimată printr-un arbore de decizie. Pentru a putea defini această problemă de învăţare mai întâi trebuie să vedem care dintre proprietăţi sau atribute sunt valabile pentru a putea descrie exemplele din domeniu. Să presupunem că avem următoare listă de atribute:

1. 
   Alternativă: dacă este un restaurant acceptabil în apropiere.
   
2. 
   Vineri / Sâmbătă: dacă este vineri sau sâmbătă.
   
3. 
   Bar: dacă restaurantul are bar unde se poate aştepta.
   
4. 
   Apetitul: dacă clienţilor le este foame.
   
5. 
   Clienţi: câte persoane sunt în restaurant (valorile sunt: Nimeni, Câţiva, Plin).
   
6. 
   Preţ: preţurile din restaurant. (valorile sunt: $, $$, $$$)
   
7. 
   Ploaie: dacă plouă afară.
   
8. 
   Rezervare: dacă s-a făcut rezervare sau nu.
   
9. 
   Tipul: tipul restaurantului (valorile sunt Francez, Chinezesc, Italian)
   
10. 
    PerioadaDeAşteptare: perioada de aşteptare pentru o masă. (valorile sun: 0-10 minute, 10-30 minute, 30-60 minute, mai mult de o oră)
    

Arborele de decizie pentru această problemă este în Figura........ Arborele poate fi exprimat ca o conjuncţie de implicaţii individuale care corespund drumurilor prin arbore până la nodurile frunză care au valori “Da”. De exemplu, drumul pentru un restaurant plin de clienţi, cu un timp de aşteptare de 10-30 de minute, când agentului nu îi este foame, este exprimat prin următoarea propoziţie logică:

 Clienţi(r, Plin)  PerioadaDeAşteptare(r, 0-10)  Apetit(r, N)  VomAştepta(r)



Fig.$$$$$$$ Un arbore de decizie pentru a decide

dacă se aşteaptă sau nu pentru o masă
Arborii de decizie sunt buni pentru anumite tipuri de funcţii şi nepotriviţi pentru alte tipuri de funcţii. Nu există nici o reprezentare eficientă pentru toate tipurile de funcţii. Dacă considerăm un set de funcţii booleene cu n atribute sunt tot atâtea tabele de adevăr pentru aceste funcţii. Un tabel de adevăr are 2ⁿ coloane deoarece fiecare intrare este descrisă de n atribute. Dacă ne trebuie 2ⁿ pentru a defini o funcţie, aceasta înseamnă că sunt ₂2ⁿ funcţii diferite cu n atribute. De exemplu, dacă avem numai şase atribute booleene, sunt aproximativ 2  10¹⁹ funcţii diferite. Va fi nevoie de nişte algoritmi ingenioşi pentru a găsi ipoteze bune într-un spaţiu atât de mare.

Ideea de bază pentru algoritmul Învăţarea prin arbori de decizie este ca prima oară să fie testat cel mai important atribut. Prin cel mai important atribut se înţelege acel atribut care realizează cea mai semnificativă diferenţă în clasificarea exemplelor. În acest mod, se speră găsirea unei clasificări corecte cu un număr mic de teste, aceasta însemnând că drumurile în arbore vor fi scurte şi întregul arbore va fi mic.

Definiţie: Se numeşte clasificare a unui exemplu valoarea predicatului scop. Dacă predicatul scop este adevărat pentru un exemplu, acesta se numeşte exemplu pozitiv, altfel se numeşte exemplu negativ. În figura ¤¤¤¤ sunt descrise cinci exemple pentru problema restaurantului. Exemplele pozitive sunt cele pentru care valoarea predicatului VomAştepta este adevărat (X₁, X₃, X₄ ) iar cele negative sunt cele pentru care această valoare este fals (X₂, X₅, X₆ ). Setul complet de exemple se numeşte setul de instruire.

Fig.¤¤¤¤¤ Exemple pentru problema restaurantului

Avem cele cinci exemple de instruire pe care le-am clasificat în exemple pozitive şi exemple negative. Apoi trebuie să decidem care este atributul cel mai semnificativ. Figura ####.a) arată că atributul Clienţi este un atribut important, deoarece dacă valoarea lui este câţiva sau nimeni atunci ne rămâne un set pentru care putem da un răspuns; pentru atributul plin mai avem nevoie de câteva teste. În figura ###.b) se observă că atributul Tip este un atribut irelevant, deoarece nu reduce domeniul căutărilor. Se cercetează astfel toate atributele şi se alege ca rădăcină a arborelui acel atribut care este cel mai important. Am ales atributul Clienţi.

După ce a fost ales primul atribut fiecare ieşire este la rândul ei un arbore de decizie, dar cu mai puţine exemple şi mai puţine atribute. Sunt patru cazuri:

1. 
   Dacă mai sunt exemple negative şi pozitive trebuie ales cel mai bun atribut pentru
   

a le împărţi. Se alege Apetit.

2. 
   Dacă toate exemplele rămase sunt fie pozitive, fie negative, am terminat: se poate
   

răspunde prin da sau nu. Exemple de felul acesta sunt cazurile nimeni şi câţiva.

3. 
   Dacă nu au mai rămas exemple în setul de instruire, înseamnă că nu a mai fost
   

observat nici un exemplu , şi se va returna o valoare implicită calculată din

majoritatea clasificărilor nodurilor părinţi.

4. 
   Dacă nu au mai rămas atribute, dar nu se poate lua o decizie atunci înseamnă că
   

avem exemple cu aceeaşi descriere dar clasificări diferite. Acest lucru se întâmplă

când unele date sunt incorecte sau când atributele nu oferă destule informaţii

pentru a putea descrie complet situaţia.
S-ar putea trage concluzia că algoritmul de învăţare nu se comportă conform aşteptărilor în învăţarea funcţiei corecte. Această concluzie este greşită deoarece algoritmul de învăţare ia în considerare exemplele, nu cunoaşte funcţia corectă.

Algoritmul de învăţare în arbori de decizie este descris figura următoare:

function Învăţare_Arb(exemple, atribute, implicit) returns un arbore de decizie

intrări: exemple //setul de exemple

atribute //setul de atribute

implicit //valoarea implicită pentru predicatul scop

if nu mai există exemple then return implicit

else if toate exemplele au aceeaşi clasificare then return clasificarea

else if nu mai există atribute then return Majoritatea_Valorilor(exemple)

else

cel_mai_bun := Alege_Atribut(atribute, exemple)

arbore := un nou arbore de decizie cu rădăcina cel_mai_bun

for each valoare v_i din cel_mai_bun do

exemple_i := elementele din exemple cu cel_mai_bun = v_i

subarbore := Învăţare_Arb(exemple_i, atribute – cel_mai_bun,

Majoritatea_Valorilor(exemple))

adaugă o nouă ramură la arbore cu eticheta v_i şi subarborele subarbore

end

return arbore

Fig. cccc Algoritmul de învăţare în arbori de decizie

5.