ARBORI DE DECIZIE

Un arbore de decizie este o structură sub forma unui arbore care conţine două tipuri de noduri:

- noduri terminale sau frunze

- noduri decizionale

Fiecare nod decizional reprezintă de fapt un test pentru o anumită proprietate (caracteristică,

atribut), fiecare arc, care pleacă dintr-un astfel de nod, fiind o valoare a proprietăţii respective. în

schimb, fiecare frunză reprezintă o clasă.

Arborii de clasificare sunt utilizaţi în prognoza apartenenţei unor obiecte la diferite clase tinând

cont de una sau mai multe variabile ce caracterizează obiectele respective. De asemenea, sunt cea

mai populară metodă de clasificare şi predicţie.

Flexibilitatea acestei tehnici o face deosebit de atractivă, mai ales datorită faptului că prezintă şi

avantajul unei vizualizări sugestive (arborele ce sintetizează clasificarea obţinută).

Figura 3- 1: Exemplu de arbore de decizie

(Sursa: Tutorial SPSS)

Arborii de decizie se împart în 3 categorii:

Arbori de clasificare, termen folosit atunci când rezultatul predicţiei este clasa de apartenenţă

a datelor

Arbori de regresie, atunci când rezultatul prognozat poate fi considerat un număr real (preţul

petrolului, preţul unei acţiuni, valoarea unei case etc.)

CART (C&RT), adică Classification And Regression Tree (Breiman, 1984), atunci când

suntem în ambele situaţii de mai sus.

Construcţia unui arbore de decizie

În principiu, se pot construi mai mulţi arbori de decizie având dat un set de atribute, dar unii

dintre ei au o precizie mai mare de clasificare decât alţii. Astfel, există o serie de algoritmi care

pot fi folosiţi pentru obţinerea de arbori cu o acurateţe cât mai mare. Cei mai cunoscuţi algoritmi

sunt: algoritmul Hunt, CART( Classification and Regression Tree), ID3, C4.5, CHAID, SLIQ,

SPRINT, QUEST, FACT, THAID.

Algoritmul Hunt stă la baza celorlalţi algoritmi de creare a arborilor de decizie. Vom considera

Dt mulţimea elementelor care se găsesc în nodul t, iar C={C1, C2,..., Ck} este mulţimea etichetelor

claselor corespunzătoare nodului t, astfel vom avea 2 situaţii :

dacă Dt conţine elemente ce aparţin aceleiaşi clase C t, atunci t este o frunză etichetată

Ct

dacă Dt conţine elemente ce aparţin la mai mult de o clasă, atunci se alege un atribut

test pentru a împărţi mulţimea Dt în submulţimi (noduri).

Procedeul se aplică recursiv fiecărui nod.

O problemă fundamentală în construcţia unui arbore o constituie modul în care sunt selectate

atributele pentru fiecare nod din arbore. Se urmăreşte realizarea celei mai adecvate divizări a

unui subset de date din cadrul unui nod, astfel încât să se obţină un grad cât mai mare de puritate

a nodurilor-fii. Astfel, alegerea atributelor în vederea realizării celei mai adecvate clasificări se

bazează pe gradul de puritate a nodurilor-fii. Pentru a determina gradul de impuritate se folosesc

următoarele modalităţi de calcul a impurităţii:

1. Entropia: arată cât de “dezordonat” este un set de date:

Entropia (S )=−∑i=1

c

p i /S log2 p i /S

unde S – setul de obiecte

pi/S – ponderea elementelor i din setul S

c – numărul de clase

Dacă entropia este 0 atunci toate obiectele lui S aparţin aceleiaşi clase. Dacă entropia este 1

există un număr egal de elemente în fiecare clasă, iar dacă aceasta este între 0 şi 1 numărul de

obiecte diferă de la o clasă la alta.

2. Indexul Gini (Gini index): utilizat cu predilecţie în CART şi SPRINT, se bazează pe

selectarea acelui atribut de partiţionare care minimizează impuritatea divizării:

I G(S )=1−∑j=1

c

pi / S2

Partiţionarea optimă a nodului i este aceea care asigură cea mai mică valoare a indexului GINI de

partiţionare.

3. Câştigul de informaţie (information gain): utilizat cu predilecţie în ID3, C4.5 şi C5.0,) şi se

calculează ca diferenţă între gradul de impuritate al nodului-părinte şi gradul de impuritate

ale nodurilor-fii. Cu cât este mai mare diferenţa cu atât mai bun este atributul de clasificare

ales.

Gain( S )=Entropia (S )−∑j=1

k N ( v j )N

Entropia (v j )

unde

Entropia (S) – entropia nodului părinte S

N – numărul de obiecte din nodul părinte

k – numărul stări ale atributului ales pentru clasificare

N(vj) – numărul de obiecte ce aparţin nodului-fiu vj

Entropia(vj) – entropia nodului-fiu vj

4. Măsura de clasificare greşită (misclassification measure): utilizată câteodată la măsurarea

impurităţii nodului:

Miclassificationerror (S )=1−maxi

pi /S

Figura 3- 2: Comparaţie între modalităţile de calcul a impurităţii pentru o clasificare binară

(Sursa: Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining, Pearson Education, 2006, pag. 159)

p indica proporţia obiectelor care aparţin uneia din cele 2 clase. Se observă că toate cele trei

modalităţi de calcul ating valoarea maximă atunci când distribuţia clasei este uniformă (p = 0.5),

iar valoarea minimă se atinge atunci când toate înregistrările aparţin aceleiaşi clase (când p = 0

sau p = 1).

Alegerea criteriului de oprire După stabilirea criteriului de partiţionare a nodurilor, se pune problema alegerii criteriului de

oprire a acestui proces.

Procesul de partiţionare se derulează până când toate nodurile terminale (frunzele) sunt “pure”

din punct de vedere al elementelor constitutive, atâta timp cât nu există o condiţie de stopare a

creşterii arborelui.

Reguli de “stop”:

a) Minimul n, se referă la condiţia de stop care specifică un număr minim de obiecte care să

fie conţinute în nodurile terminale. În aceste condiţii, divizarea unui nod ia sfârşit atunci

când fie nodul este pur, fie nu conţine mai mult decât numărul specificat de obiecte.

b) Proporţia de obiecte, se referă la condiţia de stop care impune ca divizarea unui nod să ia

sfârşit atunci când fie nodul este pur, fie nu conţine mai multe obiecte decât o proporţie

(procentaj) minimă din mărimea uneia sau mai multor clase.

Odată construit arborele de clasificare şi decizie, pe baza setului de obiecte de antrenament,

acesta va reflecta caracteristicile acestei mulţimi.

Deoarece un arbore se construieşte pentru a putea fi aplicat la diverse alte seturi de date, este

necesară evitarea acestei “potriviri” prea accentuate (overfitting) cu mulţimea pe care s-a făcut

antrenamentul. În acest caz se utilizează metoda de fasonare(pruning) a arborelui.

Fasonarea prealabilă (pre-pruning) înseamnă că se opreşte practic “creşterea” arborelui în

timpul procesului de inducţie, prin decizia de a se sista divizarea nodului, astfel încât acesta va

deveni o frunză etichetată cu numele clasei cu cele mai multe elemente. Principalele condiţii de

stopare sunt fie atunci când nodul e “pur”, fie când toate valorile atributelor sunt egale.

Fasonarea ulterioară (post-pruning) are loc după terminarea “creşterii” arborelui, fiind un

proces de jos în sus, bazat pe măsurarea erorii de clasificare a arborelui. Astfel, un nod va fi

fasonat prin renunţarea la ramurile sale, el devenind o frunză etichetată în aceeaşi manieră ca

mai sus, dacă eroarea de clasificare se diminuează prin această operaţie.

Avantajele şi dezavantajele folosirii arborilor decizionali

Avantaje:- sunt uşor de înţeles şi interpretat, forma lor grafică reprezentând un atu puternic în acest

sens;

- necesită un volum mic de pregătire a datelor în raport cu alte tehnici;

- permit utilizarea atât a datelor nominale, categoriale, ct si a celor numerice fără nicio

restricţie;

- reprezintă modele de tip „cutie albă” (white-box), în care logica deciziei poate fi

urmărită uşor, regulile de clasificare fiind „la vedere”. Spre deosebire de arborii de

decizie, alte tehnici utilizate şi în clasificare, ca de exemplu reţelele neuronale

artificiale, acţionează ca nişte „cutii negre” (black-box), nefurnizând direct utilizatorului

regulile de clasificare;

- fac posibilă utilizarea unor tehnici statistice clasice pentru validarea modelului;

- sunt robuste, rapide şi lucrează bine cu seturi mari de date

Dezavantaje:- nu sunt recomandate pentru sarcinile de apreciere unde scopul este să prezică valoarea

unui atribut continuu

- nu sunt recomandaţi în clasificări cu multe clase şi număr relativ mic de unitati

- nu tratează bine regiunile nerectangulare; majoritatea algoritmilor ce folosesc arbori de

decizie examinează doar un singur câmp la un moment dat, acest lucru ar putea duce la

o clasificare care s-ar putea să nu corespundă cu distribuirea existentă a înregistrărilor în

spaţiul de decizie

- nu poate pune in evidenta corelaţiile dintre variabile