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