Arbori De Decizie In Asistarea Diagnosticarii Medicale Teza (1) [632024]

UNIVERSITATEA BABEȘ -BOLYAI CLUJ -NAPOCA

FACULTATEA DE MATEMATICǍ ȘI INFORMATICǍ

SPECIALIZAREA INFORMATICĂ

LUCRARE DE LICEN ȚǍ

ARBORI DE DECIZIE ÎN ASISTAREA
DIAGNOSTICĂRII MEDICALE

Conducător științific ,
Prof. univ. dr. Czibula Gabriela

Absolvent: [anonimizat]

2017

2
CUPRINS

INTRODUCERE ………………………….. ………………………….. ………………………….. ………………………. 4
CAPITOLUL I ………………………….. ………………………….. ………………………….. ………………………….. 6
Învățare automată ………………………….. ………………………….. ………………………….. ………………………. 6
1.1 Ce este învățarea automată? ………………………….. ………………………….. ………………………….. .. 6
1.2 Domenii de aplicare ale învățării automate ………………………….. ………………………….. ……….. 7
1.3 Specificarea unui sistem care învață ………………………….. ………………………….. ………………… 9
1.3.1 Alegerea experienței pentru învățare ………………………….. ………………………….. ………….. 9
1.3.2 Alegerea funcției obiectiv ………………………….. ………………………….. ……………………….. 10
1.3.3 Alegerea reprezentării pentru funcția obiectiv ………………………….. ……………………….. 10
1.3.4 Alegerea unui algoritm de aproximare ………………………….. ………………………….. ……… 11
1.3.5 Componentele centrale ale unui sistem care învață ………………………….. …………………. 12
1.4 Tipuri de învățare automată ………………………….. ………………………….. ………………………….. . 14
1.4.1 Învățare supervizată ………………………….. ………………………….. ………………………….. …… 14
1.4.2 Învățare nesupervizată ………………………….. ………………………….. ………………………….. .. 15
1.4.3 Învățare prin întărire ………………………….. ………………………….. ………………………….. ….. 16
1.5 Învățare inductivă ………………………….. ………………………….. ………………………….. ……………. 16
CAPITOLUL II ………………………….. ………………………….. ………………………….. ……………………….. 17
Arbori de decizi e ………………………….. ………………………….. ………………………….. ……………………… 17
2.1 Prezentare generală ………………………….. ………………………….. ………………………….. …………. 17
2.2 Probleme potrivite pentru a fi abordate cu arbori de decizie ………………………….. ………….. 19
2.3 Tipuri de arbori de decizie ………………………….. ………………………….. ………………………….. .. 20
2.4 Algoritmul ID3 ………………………….. ………………………….. ………………………….. ……………….. 21
2.5 Preferința inductivă a arborilor de decizie (Inductive Bias) ………………………….. ……………. 26
2.6 Limitări ale algoritmului ID3 ………………………….. ………………………….. ………………………… 27
2.6.1 Evitarea supraantrenării datelor ( overfitting ) ………………………….. …………………………. 27
2.6.2 Includerea atributelor cu valori continue ………………………….. ………………………….. …… 29
2.6.3 Măsuri alternative pentru selectarea atributelor ………………………….. ……………………… 29
2.6.4 Manipularea atributelor cu valori lipsă ………………………….. ………………………….. ……… 30

3
2.6.5 Manipularea atributelor cu costuri diferite ………………………….. ………………………….. … 30
2.7 Avantajele și dezavantajele arborilor de decizie ………………………….. ………………………….. . 31
CAPITOLUL III ………………………….. ………………………….. ………………………….. ……………………… 33
Utilizarea arborilor de decizie în medicină ………………………….. ………………………….. ………………. 33
CAPITOLUL IV ………………………….. ………………………….. ………………………….. ……………………… 40
Aplicația practică. DT4Park – Decision Tree for assisting the diagnosis of Parkinson ……………. 40
4.1 Dezvoltarea aplicației ………………………….. ………………………….. ………………………….. ………. 40
4.1.1 Definirea și specificarea problemei ………………………….. ………………………….. ………….. 40
4.1.2 Analiză și proiectare ………………………….. ………………………….. ………………………….. ….. 43
4.1.3 Implementare ………………………….. ………………………….. ………………………….. ……………. 45
4.1.4 Manual de utilizare ………………………….. ………………………….. ………………………….. ……. 50
4.2 Rezultate experimentale ………………………….. ………………………….. ………………………….. …… 53
4.3 Extinderi posibile ………………………….. ………………………….. ………………………….. ……………. 57
CONCLUZII ………………………….. ………………………….. ………………………….. ………………………….. . 58
BIBLIOGRAFIE ………………………….. ………………………….. ………………………….. ……………………… 59

4
INTRODUCERE

Dacă ar fi să privim în jurul nostru, am observa că rezultatul a ceea ce facem, a ceea ce
suntem este con secința deciziilor pe care le luăm . De aceea, l uarea deciziilor corecte devine
factorul cheie în atingerea obiectivelor noastre pe toate planurile, atât personal, câ t și profesional.
De regulă, luarea deciziilor se bazează pe experiențele din trecut și pe raționamentul personal.
Deși cazurile rezolvate din experiențele trecute ar trebui să ducă la decizii corecte și sigure, nu
este așa , deoarece cazurile noi apărute sunt mult mai complicate și mai complexe. Astfel apare
nevoia unor sisteme capabile să asiste oamenii în luarea deciziilor , deoarece cantitatea imensă de
informație nu poate fi procesat ă de către aceștia . Aceste sisteme ar putea veni în ajutorul nostru ,
presupunând fap tul că ele ar fi capabile să procese cantitatea imensă de informație, oferind
decizia cea mai b ună.
Deciziile cele mai greu de luat, sunt deciziil e neprogramate . Ele sunt luate în situații
inedite și în condiții nestabil ite. Deciziile neprogramate nu au proceduri prestabilite de rezolvare,
deoarece nu au ma i fost întâlnite sau pentru că sunt foarte dificile și complexe. Condițiile de
incertitudine , de risc crescut, unde stresul accentuează și amplifică caracter ul incert și riscant al
deciziilor fac ca acestea să devină vulnerabile .
Prin urmare, d eciziile sunt esențiale pentru obținerea obiectivelor noastre , având un rol
important în multe domenii, în special în medicină , unde decizia trebuie luată într -un mod cât
mai efi cient , ea având un rol decisiv . Partea importantă a proces ului medical sunt aceste sisteme
care au rolul de a asigura asistență în procesul de diagnosticare medicală . Astfel, sistemele de
suport decizional devin o ramură importantă în medicină.
În medicină , arborii de decizie sunt utilizați d e mai bine de 20 de ani și au ca scop luarea
celei mai bune decizii sau a unei decizii adecvate într-o situație limită . Medicina este un domeniu
în care luarea deciziilor reprezintă o problemă majoră . Așa cum spunea Șir. William Osler
“Medicina est e știința incertitudinii și arta probabilității ”.
Arborii de decizie sunt indicați pentru astfel de probleme deoarece sunt modele relativ
simple , dar cu o performa nță mare, cel mai mare avantaj al lor fiind faptul că , rațion amentul
acestor modele poate fi urmărit spre deosebire de cele mai multe modele de învățare.
Posibilitatea urmăririi raționamentului este fo arte importantă deoarece medicina este un domeniu
crucial . Astfel specialiștii pot trage concluzia dacă soluția ofer ită de sistem este corectă sau nu.
Scopul lucrării de față este de a studia performanț ele sistemelor bazate pe arbori de decizie
în procesul asistării automate a diagnosticării medicale și în special în diagnosticarea bolii
Parkinson .
Lucrarea este struct urată în patru capitole.

5
În Capitolul I sunt prezentate noțiuni despre învățarea automată și subtipuri le de învățare
ale acesteia : învățarea supervizată, învățarea nesupervizată și învățarea prin întărire. Acest
capitol descrie specificarea și componentele centrale ale unui sistem care învață.
În Capitolul II este realizată prezentarea generală a arborilor de decizie, clasificarea lor,
probleme potrivite pentru a fi abordate cu arbori de decizie , avantaje și limitări ale acestora și
descrierea a lgoritmul ID3.
Capitolul III prezintă abordări din literatură în asistarea diagnosticării medicale folosind
arbori de decizie sau sisteme hibride care combină arborii de decizie cu alte tehnici de învățare.
Capitolul IV prezintă descrierea aplicației pract ice. Începem cu motivația alegerii temei ,
după care sunt prezentați pașii realizaț i în dezvoltarea aplicației. Sunt prezentate rezultatele
experimentale obținute care sunt comparabile cu cele raportate în literatură , în majoritatea
situații lor fiind chiar mai bune decât cele raportate.

6
CAPITOLUL I
Învățare automată

1.1 Ce este învățarea automată?

Odată cu apariția primelor calculatoare s-a pus problema dacă acestea ar fi capabile să
învețe. Astfel, n e putem imagina calculatoare care învață din dat ele medicale ce tratamente ar fi
eficiente pe ntru noile boli , case învățân d din experiență s ă optimiz eze costurile energiei, bazate
pe activitățile locuitorilor acestora.
Una dintre caracteri sticile esențiale ale inteligenț ei um ane este capacitatea de a învăța.
Până în prezent, nu s-a ajuns la această capacitate și anume calculatoarele să în vețe la fel de bine
ca oamenii, însă au fost dezvoltați algoritmi care învăța să rezolve cu succes anumite sarcini.
Mulțumită p uterii inovative , învățarea automată joacă un rol din ce în ce mai important în
informatică [18].
În [18], Mitchel l, definea î nvățarea automată ca fiind : “Despre un sistem informatic se
spune că învață din experiența E în raport cu o sarciniă T și o măsură de performață P, în cazul
în care performanțele sale măsurate folosind P în ceea ce privește rezolvarea sarcinii T sunt
îmbunătățite pe baza experienței E.”
Învățarea automată (machine learning, ML) reprezintă unul dintre subdomeniile de bază
ale inteligenței artificiale. Aceasta are rolul de a dezvolta algoritmi și metode care vor fi utilizate
de sistemele informatic e pentru a învăța date, reguli sau algoritmi. Unul dintre avantajele
învățării automate este considerat a fi identificarea și implementarea unei modalități cât mai
eficiente de a reprezenta informații , cu scopul de a îmbunătăți procesele de căutare, modificare
sau reorganizare a acesteia. Reprezentarea datelor este influențată de modul de rezolvare al
problemei și de caracteristicile in formațiilor cu care se lucrează [7].
Tehnicile de învățare sunt metode orientate pe date ( data-driven ) care îmbină noțiuni de
bază din informatică cu noțiuni din statistică, probabilități și tehnici de optimizare. Ideea de bază
a învățării automate este generalizarea din experie nțe. Generalizarea este capacitatea unui sistem
care învață să rezolve corect cazuri noi pe baza experiențelor sale. Experiența reprezintă
informațiile disponibile din trecut , care de regulă sunt date în format electonic . Calitatea și
cantitatea acestor da te sunt caracteristici semnificative în obținerea performanțelor sistemul ui

7
care învață. Performanțele algoritmilor dezvoltați fiind dependente de datele utilizate, face ca
învățarea automată să fie strâns legătă de statistică și analiza datelor [2], [19].
Herbert Simon afirma că: „ învăț area este procesul prin care un sistem își îmbunătățește
performanțele ”.

1.2 Domenii de aplicare ale învățării automate

Probleme le întâlnite în diferite domenii de activitate au fost rezolvate cu ajutorul
algoritmilor de î nvățare, astfel aceștia dovedindu -și eficiența. Putem enumera câteva aplicații:
 Recunoașterea vorbirii – toate sistemele de recunoaștere a vorbir ii care au avut
succes utilizează învățare a automată într-o anumită manieră . Sistemul SPHINX , de
exemplu, învață strategii speaker -specific pentru a recunoaște sunete primitive și
cuvinte din semnalele vocale. Metode de învățare precum rețelele neuronale se pot
adapta la particualrit ățile fiecărui vorbitor, la cara cteristicile microfonului, la
zgomotul din fu ndal, etc. Astfel de tehnici de învățare au aplicabilitate în multe
situații în care este nevoie de interpretarea semnalelor.
 Conducerea unei autovehicul în mod autonom – metode de învățare automată au fost
folosite pentru a antrena autovehicule controlate de c alaculator care să fie capabile să
se descurce în trafic, conducând pe o varietate de tipuri de drum . Sistemul ALVINN
a folosit strategiile învățate pentru a conduce fără asistență umană cu 70 de mile pe
oră, pe o dista nță de 90 de mile , pe autostradă printre alte mașini. Tehnici similare au
posibile aplicații în multe probleme de control bazate pe senzori.
 Clasificarea structurilor astronomice noi – algoritm ii de învățare au fost folosiți
pentru multe baze de date din diverse domenii pentru a extrage informații despre
modul î n care datele sunt organizate. NASA , de exemplu, a folosit algoritmi de
învățare a arborilor de decizie pentru a clasifica obiecte cereșt i din Palomar
Observatory Sky Survey. Acum , acest sistem este folosit pentru a clasifica toate
obiectele din Sky Survey care constă în 3 terra bytes de date sub formă de imagini
[18].
 Clasificarea textelor sau a documentelor – de exemplu detectarea mesajelor de tipul
spam.
 Jocuri.
 Detecția fraudelor.
 Diagnosticare medicală .
 Procesarea limbajului natural.

8
 Recunoașterea imaginilor, recunoaștere facială.
 Recunoaștere optică a caracterelor .
 Sisteme de recomandare [19].
Această listă ar putea continua, iar algoritmii de învățare sunt utilizați în noile aplicații în
fiecare zi. În plus, astfel de aplicații corespund unei game largi de probleme de învățare.
Principalele clase de probleme de învățare sunt:
 Probleme de clasif icare (classification ): asociază o categorie fiecărui element
(instață). De exemplu, clasificarea documentelor poate asocia instanțelor categorii
cum ar fi politica , afacerea , sportul sau vremea , în timp ce clasificarea imaginilor
poate atribui instanțelor categorii cum ar fi peisaj , portret sau animal . Numărul de
categorii (clase) în astfel de sarcini este adesea relativ mic, dar poate fi mare în
anumite sarcini dificile și chiar nelimitat ca în OCR (Optical character
recognition) , clasificarea textului, sau recunoașterea vorbirii.
 Probleme de r egresie (regression) : prezic o valoare reală pentru fiecare element
(instanță) . Exemple de regresie includ estimarea valorilor stocurilor sau a variațiilor
variabilelor economice. În această problemă, pedeapsa pentr u o predicție incorectă
depinde de diferența dintre valorile adevărate și cele prezise, în contrast cu
problema de clasificare, unde de obicei , nu există nici o noțiune de apropiere între
clase .
 Probleme de ranking: sortează elementele după un anumit criteriu. Un bun
exemplu ar fi căutare a pe w eb, care întoarcere paginile web relevante pentru o
interogare de căutare. Multe alte probleme similare de clasificare apar în contextul
extragerii de informații sau a procesării limbajului natural .
 Probleme de grupare (Clustering) : împarte instanțele în regiuni omogene.
Clustering -ul este adesea utilizat pentru a analiza seturi de date foarte mari. De
exemplu, în contextul rețelei sociale, algoritmii de grupare încearcă să identi fice
"comunitățile" în cadrul unor mari grupuri de oameni.
 Probleme legate de reducerea dimensionalității (Dimensionality reduction or
manifold learning) : transform ă o reprezentare inițială de elemente într -o
reprezentare mai mică , simplificată , păstrând î n același timp unele proprietăți ale
reprezentării inițiale. Un exemplu comun este procesarea imaginilor digitale [19].

9
1.3 Specificarea unui sistem care învață

Pentru a ilustra unele dintre problemele de bază ale proiectării și abo rdări ale învățării
automate, luăm în considerare proiectarea unui program pentru a învăța să joace dame . Măsura
de performanță în acest caz o reprezintă procentul de jocuri câștigate î mpotriva unui oponent
oarecare [18].

1.3.1 Alegerea experienței pentru învățare

Prima alegere în dezvoltarea sistemelor care învață este alegerea experienței pe baza
căreia sistemul va învăța. Tipul de experiență poate avea un impact semnificativ asupra
sistemului, ducând fie la succesul , fie la eșecul sistemului. Legat de ale gerile făcute, f eedback -ul
primit poate fi direct sau indirect , acesta fiind de o importanță deosebită . Spre exemplu, în
problema jocului de dame , sistemul poate învăța direct din exem plele de antrenament care
constau în poziția fiecă rei dame pe tablă și fiecare mutare corectă a acesteia. În mod alternativ,
pot exista doar informații indirecte disponibile constând din secvențe de mutări și rezultatul final
al jocului jucat. În ultimul caz specificat, informațiile legate de corectitudinea mutărilor specifice
de la î nceputul jocului trebuie deduse indirect din fapt ul că jocul a fost în cele din urmă câștigat
sau pierdut. Sistemul se confruntă cu o problemă suplimentară numită credit assignment și
anume problema determinării rolului fiecarei mutări în cadrul rezultatului final. Jocul poate fi
pierdut chiar dac ă la început mutările sunt optime, dacă acestea sunt urmate mai târziu de mutari
greșite . Prin urmare, învățare a direct ă din exemplele de antrenament care furnizează un feedback
direct este mai ușoară decât învățarea din feedback -ul indirect.
Al doilea aspect important al experienței de antrenament este gradul în care sistemul
controlează succesiunea exemplelor de antrenament. De exemplu, s istemul ar putea să se bazeze
pe ,,profesor” (antrenor) și să selecteze po ziții informative pe tabla de șah și să furnizeze mutări
corecte pentru fiecare. Alternativ, sistemul poate propune singur pozițiile pe tabla de șah și cere
,,profesorului ” să mute c orect. Sau o altă alternativă este când sistemul joacă contra lui și are
control deplin asupra pozițiilor pe tabla de șah.
Un al treilea aspect important al experienței de antrenament este cât de reprezentativ este
setul de date de antrename nt. De regulă, învățarea este mai fiabilă atunci când datele de
antrenament urmează o distribuție similară celei di n exemplele viitoare de testare [18].

10
1.3.2 Alegerea funcției obiectiv

Următoarea alegere în specificarea sistemelor care învață este alegerea funcției obiectiv. În
ceea ce privește jocul de dame, sistemul trebuie doar să învețe cum să aleagă cea mai bună
mutare dintre toate cele posibile . Această sarcină de învățare este rep rezentativă pentru o mare
categorie de sarcini pentru care mutările posibile definesc un spațiu mare de căutare, dar pentru
care nu este cunoscută cea mai bună strategie de căutare , adică cea mai bună mutare . Având în
vedere acest cadru în care trebuie să învățăm să alegem între mutările posibile , alegerea cea mai
evidentă pentru tipul de informație care trebuie învățată , este un program, sau o funcție, care
alege cea mai bună mutare pentru orice poziție de pe tabla de șah.
În cazul jocului de dame , funcți a obiectiv poate fi o funcție de evaluare c are asignează un
scor pentru fiecare stare dată a tablei de șah. Fie V această funcție , iar prin V:B->R se înțelege că
funcția V mapează fiecare stare corectă a tablei de șah la o valoare numerică. Intenționăm ca
această funcție obiectiv V să atribuie scoruri mai mari pentru stări mai bune. Acest lucru poate fi
realizat prin generarea stării succesive produsă de fiecare mutare, iar apoi folosind V pentru a
alege cea mai bună stare succesor și, prin urmare cea mai bună mutare.
Astfel , definim, v aloarea țintă V(b) pentru o stare arbitrară a tablei de șah b în B, după cum
urmează:
Dacă b reprezintă o stare finală câstigătoare atunci V(b) = 100
Dacă b reprezintă o stare finală necâștigătoare atunci V(b) = -100
Dacă b reprezintă o stare finală nedecisă (remiză) atunci V(b) = 0
Dacă b nu reprezintă o stare finală atunci V(b) = V(b’ ) unde b’ reprezintă cea mai bună
stare finală la care se poate ajunge plecând din starea b și jucâ nd în modul optimal până
la finalizarea jocului.
Datorită faptului că această funcție V nu poate fi calculată ușor, spunem că funcția V este o
definiție neoperațională . Scopul în acest caz este de a descoperi o descriere operațională a lui V.
Astfel, problema de învățare în acest caz se reduce la găsirea unei definiți i operațional e a funcției
obiectiv V. Este posibil să fie foarte dificil, astfel, de cele mai multe ori se așteaptă ca sistemul să
gasească o aproximantă a funcției obiectiv pe care o vom nota cu V’ [18].
1.3.3 Alegerea reprezentării pentru funcția obiectiv

Următorul pas dup ă ce am specificat funcția obiectiv V, este să alegem o reprezentare
pentru aceasta. În cazul problemei studiate, aceasta s -ar putea reprezenta printr -un tabel mare
care să conțină toate stările posi bile sau printr -o rețea neuronală sau prin funcții de mapare. De

11
regulă stabilirea reprezentării funcției obiectiv implică anumite compromisuri. Ar fi de preferat o
reprezent re cât mai aproximativ ă a funcției obiectiv.
Se alege o reprezentare simplă: pentr u orice stare dată, funcția V’ va fi calculată ca o
combinație liniară din următoarele caracteristici :
 xl reprezintă numărul de piese negre de pe tabla de șah ;
 x2 reprezintă numărul de piese albe de pe tabl a de șah ;
 x3 reprezintă numărul de regi de culoare neagră de pe tabla de șah ;
 x4 reprezintă numărul de reg i de culoare albă de pe tabla de șah ;
 x5 reprezintă numărul de piese negre amenințate de piesele albe (adică, care pot fi
capturate) ;
 x6 reprezintă numărul de piese albe amenințate de piesele negre .
Astfel funcția V’ ar putea avea forma :
V’(b) = w0 + w 1×1 + w 2×2 + w 3×3 + w 4×4 + w 5×5 + w 6×6 ,
unde w0, …, w6 reprezintă ponderi ( weights ) care trebuie învățate de către algoritm [18].

1.3.4 Alegerea unui algoritm de aproximare

Penru a învăța aproximanta funcției obiectiv V’ avem nevoie de un set de date de
antrenament , fiecare d escriind o stare specifică b și valoarea de antrename nt Vtrain (b) pentru b.
Cu alte c uvinte, setul de antrenament constă din perechi (b, V train(b)), unde b reprezintă o stare a
tablei de șah , iar Vtrain(b) valoarea corespunzătoare stări i. Dat fiind faptul că î n problema studiată,
datele de antrenament (experiența) sunt de fapt lista mutărilor și rezultatul jocului , este nevoie ca
aceste perechi (b, V train(b)) să fie determinate, această metodă purtând numele de Estimare a
valorilor de antrename nt. În acest caz, se folos ește ecuația:

Vtrain(b) V’(Successor(b))

Următoarea operație ar fi Ajustarea ponderilor. Ponderile trebuie alese în așa fel încât
acestea “să se potrivească cât mai bine” cu setul de datele de antrenament. Prin expresia “să se
potrivească cât mai bine” înțelegem găsirea valorilor pentru ponderi astfel încât eroarea E să fie
minimă , unde

[18]

12
1.3.5 Componentele centrale ale unui sistem care învață

Proiectarea finală a sistemului nostru privind jocul de dame , poate fi descris în mod natural
de patru module distincte de program care reprezintă componentele centrale ale multor sisteme
de înv ățare. Aceste patru module, sunt prezentate în Figura 1 din [18].

Figura 1 Proiectarea finală a jocului de dame [18]

 Sistemul de performan ță (Performa nce System ) este modulul care trebuie să rezolve
problema dată, în acest caz jocul de dame , folosind funcția obiectiv învățată . Ca date de
intrare, primește o instanță nouă , iar ca date de ieșire va avea evaluarea
corespunzătoare instanței analizate . În cazul nostru, strategia utilizată de sistem pentru
a selecta următoarea mutare la fiecare pas este dete rminată de funcția de evaluare
învățată. Prin urmare, ne așteptăm ca performanțele sale să se îmbunătățească , deoarece
această funcție de evaluare devine din ce în ce mai exactă .
 Criticul ( Critic ) este modulul care primește ca date de intrare istoricul mut ărilor jocului
și produce ca date de ieșire un set de date de antrenament a funcției obiectiv. În cazul
nostru, Critic corespunde regulii de antrenament dată de ecuția:
Vtrain(b) V’(Successor(b)) .

13
 Generalizatorul ( Generalizer ) primește ca date de intrare setul de date de
antrenament și produce ca date de ieșire o ipoteză care estimează funcția obiectiv.
Acesta generalizează datele de antrenament alegând din spațiul ipotez elor posibile,
ipoteza care se potrivesțe cel mai bine cu datele și care să ai bă capacit ate de
generalizare.
 Generatorul de experimente ( Experiment generator ) primește ca date de intrare
ipoteza curentă și are ca date de ieșire o nouă problemă care trebuie explorată de
sistem. Rolul lui este să aleagă o nouă problemă pr actică care să crească rata de
învățare a întreg sistemului. În exemplul nostru, Experiment generator urmează o
strategie foarte simplă, propune întotdeaun a aceeași configurație a table i de șah
pentru a începe un nou joc.
Multe sisteme de învățare automată pot fi car acterizate de aceste patru module generice.
Se sintetizeaza succesiunea de alegeri de proiectare făcute pentru jocul de dame în Figura
2 [18].

Figura 2 Rezumatul alegerilor în proiectarea jocului de dame [18]

14
1.4 Tipuri de învățare automată

Metodele învățării automate sunt diverse, variind după modul de reprezentare a seturilor de
date folosite pentru antrenament sau strategii de învățare. În cadrul învățării automate se pot
distinge trei mari tipuri de învățare : învățare supervizată, învățar e nesupervizată și învățare prin
întărire .

1.4.1 Învățare supervizată

Învățarea supervizată face parte din subcategoria învățarii inductive . Aceasta pornește de
la un set de instanțe ale problemei și realizează o funcție de evaluare, care să permită clasificarea,
rezolvarea unor noi instanțe.
Algoritmului de rezolvare are la bază cazurile care au fost deja rezolvate , acestea fiind
folosite ca instanțe pentru „antren area” acestuia . Algoritmul de învățare supervizată analizează
setul d e date de antrenament și duce la crearea unei funcții deduse, care în cazul obținerii unui
rezultat discret este numită clasificator, sau numită funcție de regresie, în cazul unu i rezultat
continuu . Funcția dedusă are rolul de a intui valorile corect e în c e privește datele de ieșire pentru
orice set de date folosit ca date de intrare .
În învățarea supervizată, setul de date de antrenament constă dintr -un set de n perechi
ordonate (x1, y1), (x 2, y2),…,(x n, yn), unde fiecare xi este o anumită caracteristică sau set de
caracteristici a unei instanțe și yi este eticheta pentru acel punct de date , adică valoarea obținută
în urma evaluării instanței (de cele mai multe ori această valoare reprezintă clasificarea
instanței) .
De exemplu, un xi poate fi un vector d e 5 caracteristici pentru un pacient aflat în spital cum
ar fi înălțimea, greutatea, temperatura, nivelul de zahăr din sânge și tensiunea arterială . Yi-ul
corespunzător ar putea fi o clasificare a pacientului ca fiind " sănăto s" sau " nesănătos ".
Datele de testare în învățarea supervizată reprezintă un alt set de m măsurători fără
etichete: (xn + 1, x n + 2, …, x n + m) . Așa cum am descris mai sus, obiectivul este de a face
sugestii despre etichetele setului de test (cum ar fi " sănătos " sau " nesănătos") prin trasarea unor
deducții din setul de antrenament [15].
Modelul , în cazul învățării supervizate, are rolul de a defini structura în strânsă legătură cu
setul de observații utilizat ca date de intrare și setul utilizat ca date de ieșire. Așadar, datele de
intrare se presupun a fi la începutul lanțului cauza l, însă, modelul poate conține legături
intermediare între datele de intrare și cele de ieșire.
În Figura 3 se poate observa întreg procesul învățării supervizate.

15

Figura 3 Procesul învățării supervizate [24]

1.4.2 Învățare nesupervizată

În cadrul învățării nesupervizate se elimină necesitatea unor instanțe de antrenament,
implicit și probleme cauzate de a cestea. În schimb , presupune existența unor instanțe
neclasificate , un set de reguli eur istice pentru dezvoltarea de noi instanțe și evaluarea unor
concepte deduse .
Algoritmul de învățare nesupervizată contruiește concepte pentru a clasifica instanțele, le
evaluează și le dezvoltă pe cele pe care le consideră „interesante” de regulile eurist ice. De regulă,
conceptele „interesante” sunt acelea care acoperă o part e din instanțe, dar nu pe toate [16].
Prin această metodă de învățare se pot obține , plecând de la date cunoscute , concepte cu
totul noi. În cercetarea științifică, s -au obținut rezultate remarcarbile cu încercarea de a aplica
acest tip de învățare.
Învățarea se poate face ierarhic î n cazul învățării nesupervizate, pornind de la setul de
observații și ajungând la nivele tot mai abstracte ale reprezentării. Fiecare ierarhie adițională
învață doar câte un pas, ducând astfel la creșterea timpului de învățare aproximativ liniar cu

16
numărul nivelelor din cadrul modelului ierarhic. Făcând o comparație cu învățărea supervizată,
folosind învățarea nesupervizată se poate ajunge la învățarea unor modele mult mai mari și
complexe [12].
Un tip de învățare nesupervizată este considerat clusteri ng-ul. Acest tip de abordare
presupune existența unei mulțimi de obiecte negrupate și a unor căi de a găsi și mă sura
similarități între aceste obiecte. Scopul algoritm ului de identificare a unor clase de obiecte este
de a grupa obiectele într -o ierarhie de clase după criterii , cum ar fi maximizarea similarității
obiectelor din aceeași clasă. Ierarhia de clase este reprezentată de regulă ca un arbore, fi ii unui
nod reprezentând categorii distincte , dar incluse în categoria părinte [8].

1.4.3 Învățare prin întărire

Acest tip de învățare este reprezentat de învățarea pe baza recompense lor. Modalitatea
implementată este de a „răsplăti” sau „ pedepsi” sistemul în funcție de cât de mult se apropie de
rezultatul corect. Fiecare acțiune are un impact asupra mediului și mediul oferă feedback care
ghidează algoritmul de învățare. Sistemul favorizează acțiunile pe care le -a mai încercat în trecut
și au fost bine recompensate, dar to todata încearcă să găsească acțiuni mai bune care îl conduc la
recompense mai mari , astfel fiind evident compromisu l între explorare și exploatare [23].

1.5 Învățare inductivă

În general, metodele inductive pot fi caracterizate ca fiind metode de căutare într-un spațiu
de ipoteze. În învățarea inductivă, sistemului care învață i se dă un spațiu de ipoteze H din care
trebuie să selectez e o ipoteză de ieșire și un set de date de antrenament D ={(Xl, f (x ~)). .,. (X, f
(x,))} , unde f (x i) este valoarea țintă pentru instanța xi. Ieșirea dorită a sistemului este o ipoteză h
din H, care este consecventă cu aceste date de antrenament [18].

17
CAPITOLUL II
Arbori de decizie

2.1 Prezentare generală

Arborii de decizii sunt una dintre metodele cele mai utilizate și practice pentru învățarea
inductivă. Sunt o metodă de aproximare a funcțiilor cu valoare discretă , fiind robuști la date
zgomotoase și capabil i să învețe expresii disjun ctive. De asemenea, arborii de decizie pot fi
reprezentați ca seturi de reguli „if-then” pentru a îmbunătăți lizibilitatea umană.
Aceste metode de învățare sunt aplicate cu succes în diagnosticarea medicală și în multe
alte domenii : inginerie, economie, m anagement, industrie farmaceutică, controlul calității,
biologia moleculară, analiză compoziției amino -acizilor, dar cel mai des sunt utilizați în
domeniul medical. Industria farmaceutică folosește arborii de decizie pentru a planifica studiile
clinice în condiții de siguranță. Experții financiari îi folosesc pentru acordarea de credite,
încercând astfel eliminarea fraudei în ceea ce privește cardurile de credit [10].
Arborii de decizie sunt utilizați mult pentru predicție. Modelul furnizat de aceștia este de
multe ori superior altor modele obținute cu alte tehnici.
Un arbore de decizie este un clasificator , fiind structura t sub formă unui arbore care are o
singură rădăcina, această însemnând că nu are alte noduri superioare. În schimb toate celelalte
noduri au un singur nod superior, numit nod părinte. În cazul în care un nod are descendenți
acesta se numește nod intern, sau nod de test, iar restul nodurilor se num esc frunze . Arborele de
decizie conține trei tipuri de noduri:
 noduri decizionale (de test sau interne) – posibilitățile decidentului (ex. d iversele
examinări sau tratamente la care este supus pacientul)
 noduri ale hazardului – evenimente aleatoare în afar a controlului decidentului (rezultatul
examinărilor, efectul terapiilor)
 noduri terminale (fru nze)- situațiile finale cărora li se asociază o utilitate (apreciată
aprioric de către un pacient generic) sau o etichetă
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 atributului
respectiv .

18
Nodurile frunză sunt asociate cu valorile corespunzătoare c lasifică rilor posibile ale datelor
de intrare. Aceste valori poartă numele de clasă. Fiecare f runză este asociată cu o clasă .

Figura 4 Arbore de decizie pentru problema PlayTennis [18]

În Figura 4 este ilustrat un arbore de decizie care clasifică diminețile de Sâmbătă favorabile
sau nefavorabile pentru a juca tenis, în funcție de condițiile meteo.
De exemplu, instanța (Vreme = Insorită , Temperatura =Ridicată , Umiditate = Mare , Vânt
= Puternic ) este clasificată ca fiind una negativă, adică este o diminea ță nefavorabilă pentru a
juca tenis.
Clasificarea unei instanț e se face plecând de la rădăcină unde se testează atributul
specificat în acel nod după care se merge jos în arbore pe arcul corespunzător valorii atributului
testat. Acest proces se re petă pentru subarborele care are rădăcina în nodul la care s -a ajun s prin
această deplasare până când nodul la care se ajunge este un nod frunză. Valoarea acest ei frunze
furnizează clasa din care face parte instanța.
De obicei, arborii de d ecizie reprezin tă o disjuncție de conjuncții de constrângeri c u privire
la valorile atributelor instanțelor. Fiecare drum de la rădăcina arborelui la un nod frunză
corespunde unei combinații de teste asupra atribut elor, iar arborele însuși este disjuncția tuturor
acestor conjuncții. De exemplu, arborele de decizie prezentat în Figura 4 corespunde expresiei
(Vreme = Însorită ^ Umiditate = Normal ă)
˅ (Vreme = Innorată )
˅ (Vreme = Ploioasă ^ Vânt = Slab) [18]

19
În practică se preferă arborii de decizie mai puțin complecși pentru că sunt mai ușor de
înțeles. La fel cum spunea și Breiman (1984) complexitatea arborilor are un efect semnificativ
asupra acurațeții problemei. Criteriul de oprire și metoda folosită pentru partiționarea setului de
date are control asupra complexității problemei . În majoritatea cazuri lor, complexitatea este
măsurată în funcție de una din tre caracteristici le: numărul total de noduri, numărul total de
frunze, adâncimea arborelui, numărul de atribute folosite [17].

2.2 Probleme potrivite pentru a fi abordate cu arbori de decizie

Arborii de decizie sunt potriviți pentru probleme care au urmă toarele caracteristici :
 Instanț ele sunt reprezentate de perechi de forma atribut -valoare. Instanțele sunt descrise
de un set fix de atribute și valorile acestora . Situația cea mai simplă este cea î n care
atributele au puține valori disjuncte . Extensiile algoritmului de bază descris în secțiunea
2.4, permit discretizarea valorilor atributelor, în cazul în care aceste valori sunt continue.
 Datele de ieș ire ale fun cției obiectiv sunt valori discrete . Arborele de decizie din Figura 4
atribuie o clasificare booleană (de exemplu, da sau nu) fiecărui exemplu. În aces caz
clasificatorul este binar, deoarece funcția obiect iv are do ar două ieșiri. Metodele arborilor
de decizie pot fi extinse ușor pentru a învăța funcții care au mai mult de două valori de
ieșire
 După cum am precizat mai sus, în mod normal, arborii de decizie reprezintă expresii
disjunctive , astfel pot fi necesare descrieri disjunctive .
 Setul de date de antrenament poate conț ine eror i. Arborii de decizie sunt robuști la erori
chiar dacă erorile provin din clasificare a incorectă a datelor de antrenament sau din valori
greșite ale acestora .
 Datele de antrenament pot conține instanțe care au atribute ale că ror valori sunt lipsă
(missing values ). Metodele arborilor de decizie pot fi utilizate chiar și atunci când
anumite date de antrenament au valori necunoscute.
Sunt multiple probleme pr actice cu aceste proprietaț i. Astfel, a rbori i de decizie pot fi
aplicați î n problem e cum ar fi clasificarea pacienților în funcț ie de boală , clasificarea
echipamentelor în funcție de cauza defecț iunii, clasificarea solicitanț ilor de credite . Aceste tipuri
de probleme sunt numite probleme de clasificare [18].

20
2.3 Tipuri de arbori de decizie

Există o varietate de tipuri de arbori de decizie î n funcție de domeniul problemei și de
rezultatele care se doresc așteptate:
 arbori de clasificare;
 arbori de regres ie;
 arbori măriți (tree boost);
 păduri de arbori de decizie;
 arbori de clasificare si regresie.
Arborii de clasificare reprezintă modelele de arbori în care rezultatul prezis poate lua
valori discrete , utilizând un proces binar de împărțire a categoriilor și subcategoriilor pentru a
evidenția diferite atribute legate de un rezultat și folosesc tipuri de date cu scopul de a obține
rezultatul cel mai așteptat. Aceștia sunt folosiți, cu precădere , în domeniul probab ilității și
statisticii.
Arborii de regresie sunt arborii în care rezultatul prezis poate lua valori continue (de
obicei numere reale) , fiind utilizați atunci când avem o diversitate de categorii de informații și au
rol de a determina rezultat ul scontat . Datele sunt divizate în secțiuni, iar apoi sunt subdivizate în
diferite grupuri, în timpul procesului de construcție a arborelui . Arborii de regresie sunt utilizați
în special, în cazul calculelor imobiliare.
Arborii măriți ( tree boost ) sunt întrebuințați pentru îmbună tățirea preciziei procesului
decizional, folosind inițial o singură variabilă care se calculează și structurează astfel încât
numărul erorilor să fie minim, astfel ducând la informații precise datorită eliminării , în mare
parte a erorilor. Acești arbori sunt folosiți în mod special în contabilitate și matematică.
Pădurile de arbori de decizie presupun utilizarea mai multor arbori pen tru a îmbunătății
rata clasifică rii corecte.
Arborii de clasificare și regresie sunt definiți de t ermenul CAR T (Classification and
regression tree ), terme n introdus pentru prima dată de către Braimen în 1984 [3], făcând referi re
atât la ar borii de clasificare , cât și la cei de regresie . Acești arbori au devenit una dintre cele mai
folosite metode pentru construcția modelelor statice din seturi de date simp le. Li se atribuie
denumirea de arbori puternici , pentru că pot lucra chiar cu date incomplete și cu caracteristici de
diferite tipuri, atât în ce ea ce privește datele de intrare , cât și cele presupuse, arborele produs
conținând reguli ușor de înțeles de ființa uman ă.

21
2.4 Algoritmul ID3

Majoritatea algoritimilor dezvoltați pentru învatare a prin arbori de decizie sunt variații
ale unui algoritm de bază care folosește metoda top -down, căutare de tip greedy în spațiul tuturor
arborilor de decizie posibili. Acest tip de abordare este exemplificat prin algoritmul ID3 (1986)
și succesorul acestuia C4.5 (1993) .
Algoritmul de bază, ID3, învăța arborii de decizie prin construcția top -down a a cestora,
pornind de la întrebarea: “ care atribut ar trebui testat la radăcina arborelui? ”. Pentru a răspunde
la această întrebare fiecare instanță din setul de date este evaluată folosind un test statistic pentru
a se putea detemina cât de bine clasifică d atele de antrenament . Atributul cel mai bun este
selectat pentru a fi testat în nodul rădăcină. Se creează câte un descendent al nodului rădăcină
pentru fiecare valoare posibilă a acestui atributului, iar datele de antrenament sunt sortate în
funcție de nodul descendent corespunzător . Întregul proces se repetă folosind datele de
antrenament asociate fiecărui nod descendent pentru a se putea alege cel mai bun atribut de test
în punctul respectiv al arborelui . Acesta formează o căutare de tip greedy pentru un arbore de
decizie acceptat, în care algoritmul nu mai revine niciodată asupra alegerilor anterioare .
Ideea centrală a algoritmului ID3 este aceea de a selecta care atribut să se testeze î n
fiecare nod al arborelui. Ne-am dori să alegem atributul care este cel mai folositor î n clasificarea
datelor , însă problema este în funcție de ce anume comparăm atributele, care este măsura
cantitativă a valorilor acestora? Vom defini o proprietate st atistică , denumită câștig
informațional (information gain ). Acesta are rolul de a măsura cât de bine reușeste un atribut să
divizeze datele de antrenament conform clasificării rezultatului acestora. Algoritmul ID3
folosește acest câștig informațional pentru a selecta atributul ele care să fie testate la fiecare pas
în procesul de creștere al arborelui .
În teoria informației pentru a putea defini cât mai precis câștigul informațional se folosește
ca și măsură termenul de entropie . Entropia caracterizează impuritatea sau puritatea unei colecții
arbitrare de date. Con siderăm colecția de date S, care conține atât valori pozitive , cât și negative
ale unor rezultate conceptuale, entropia colecției S relativ la clasificarea booleană este:

unde p+ este proporția exemplelor pozitive din S, iar p- este proporția exemplelor care au valori
negative.

22
Pentru a ilustra acest lucru : se presupune că S este o colecție care are 14 exemple ale unor
concepte booleane, dintre care 9 sunt pozitive, iar 5 negative ( notăm pe scurt: [9+,5 -]). Atunci,
entropia lui S relativ la clasificarea booleană este:
Entropy([9+,5 -]) = -(9/14)log2(9/14) – (5/14)log2(5/14) = 0.940
De observat este faptul că entropia este 0 dacă toate datele colecției S aparțin aceleiași
clase. De exemplu, dacă toate valorilor datelor sunt poziti ve, adică p+ =1, atunci p- va fi 0,
atunci :
Entropy(S) = -1*log2(1) – 0*log2(0)=0 (0log0 se consideră a fi 0 în toate calculele
entropiei)
Entropia este 1 dacă colecția conține un număr egal de exemple cu valori po zitive și
negative. Î n cazul în care colecția conține un număr inegal de exemple cu valori positive și
negative, entropia este între 0 și 1. Graficul de mai jos [18] evidențiază forma funcției entropiei
când p+ variază între 0 și 1 .

În exemplul de mai sus am ilustrat cazul special în care clasificarea rezultatului este
booleană. La modul general, dacă rezultatul ia mai multe valori, atunci valoarea entropiei pentru
colecția S este:

unde pi este proporția de exemple din S aparținând clasei i, iar n e numărul de valori pe care îl
poate lua rezultatul .
Entropia , folosită ca o măsură a impurității într -o colecție de exemple de ant renament,
defini nește măsura în ce ea ce privește eficiența unui atribut în clasificarea date de antrenament.
Măsura folosit ă, denumită câștig informațional este de fapt, reducerea așteptată în calcularea

23
entropiei, cauzată de partiționarea exemplelor relativ la un atribut. Mai exact, câștig ul
informațional , Gain(S, A) al unui atribut A relativ la o colecție de exemple S este d efinit astfel:

unde Values(A) este setul tututor valorilor posibile pentru atributul A, iar Sv este un subset al lui S
pentru care atributul A are valoarea v (Sv = {s Є S | A(s) = v } ) [18].
În continuarea vom discuta asupra exemplelor prezentate de Mitchell în cartea sa [18].
Spunem că S este o colecție de exemple de antrenament privind zilele descrise de diferite
atribute, inclusiv Vânt, care poate avea valorile Slab sau Puternic. De asemene a, presupune m că
S este o colecție care are 14 exemple, dintre care 9 sunt pozitive și 5 negative [9+, 5 -]. Dintre
cele 14 exemple, presupunem că 6 dintre cele pozitive si 2 dintre cele negative au valoarea Slab,
iar celelalte au valoarea Puternic. Câștigu l informațional datorită sortării celor 14 exemple în
funcție de atributul Vânt se poate calcula în felul următor:

Values(Vânt) = Slab, Puternic
S = [9+, 5 -]
Sslab ← [6+, 2 -]
Sputernic ← [3+, 3 -]

Gain(S, Vânt) = Entropy(S) – (8/14)Entropy(S slab) -(6/14)Entropy(S puternic )
= 0.940 – (8/14)0.811 – (6/14)1.00
= 0.048

Câștigul informațional este măsura folosită de algoritmul ID3 pentru a putea selecta cel
mai bun atribut la fiecare pas în construcția arborelui [18].
În con tinuare, vom ilustra funcț ionarea ID3. Datele de antrenament sunt prezentate în
Tabelul 1 de mai jos . Aici atribut ul țintă Joacă Tenis , poate l ua valori le da sau nu, fiind prezis pe
baza altor atribute ale dimineții în cauză.

24

Zi Vreme Temperatură Umiditate Vânt Joacă Tenis
1 Însorită Ridicată Mare Slab NU
2 Însorită Ridicată Mare Puternic NU
3 Înnorată Ridicată Mare Slab DA
4 Ploioasă Medie Mare Slab DA
5 Ploioasă Scăzută Normal Slab DA
6 Ploioasă Scăzută Normal Puternic NU
7 Înnorată Scăzută Normal Puternic DA
8 Însorită Medie Mare Slab DA
9 Însorită Scăzută Normal Slab DA
10 Ploioasă Medie Normal Slab DA
11 Însorită Medie Normal Puternic DA
12 Înnorată Medie Mare Puternic DA
13 Înnorată Ridicată Normal Slab DA
14 Ploioasă Medie Mare Puternic NU

Tabelul 1 Datele de antrenament pentru problema Joacă Tenis [18]

Algoritmul ID3 determină câștigul informațional pentru fiecare atribut (Vreme,
Temperatură, Umiditate, Vânt) , iar apoi selectează atributul cu cel mai mare câștig
informațional. Câștigul informațional se calculează la fel ca și în exemplul de mai sus, astfel vom
avea următoarele valori:
Gain(S, Vreme ) = 0.246
Gain(S, Umiditate) = 0.151
Gain(S, Vânt) = 0.048
Gain(S, Temperat ură) = 0.029

Se observă că atributul cu cel mai mare caștig informațional este Vreme și va fi ales ca și
rădăcină a arborelui de decizie. Acest a va avea trei descendenți câte unul pentru fiecare valoare
posibil ă ale atributului Vreme și anume Însorit ă, Înnorat ă și Ploioasă .

25

?
?
DA Observăm c ă fiecare exemplu în care Vreme = Înnorat ă este un exemplu pozitiv al
atributului Joacă Tenis. Prin urmare, acest nod al arborelui devine un nod cu clasificarea Joacă
Tenis = DA. În schimb , descendenții valorilor Vreme = Înso rită și Vreme = Ploioasă au valorile
entropiei diferite de zero, iar arborele de decizie va fi construit în continuare pe aceste ramuri.

[9+, 5 -]

Însorit ă Înnorat ă Ploioasă

{1, 2, 8, 9, 11} {3, 7, 12, 13} {4, 5, 6, 10, 14}
[2+, 3 -] [4+, 0 -] [3+, 2 -]

Procesul de selecție a unui nou atribut și partiționarea exemplelor de antrenament este
repetat pentru fiecare nod descendent, ne terminal, folosind doar exemple de antrenament
asociate acestui nod. Atributele care au fost incluse înainte în arbore sunt excluse, astfel încât
fiecare atribut poate apărea o singură dată de -a lungul unui drum de la rădăcină la no dul
decizional. Acest proces continuă pentru fiecare nod frunză până când se ajunge la una dintre
condițiile:
 fiecare atribut a fost deja inclus într-un drum al arborelui;
 exemplelor de antrenament asociate acestui nod frunză au toate aceeași valo are a
atributului rezultatului, entropia acestora fiind zero.
Astfel , după aplicarea algoritmului ID3 , arborele de decizie final este ilustrat în Figura 4,
care a fost menționată în secțiunea 2.1 [18].
În urma analizei algoritmul ui ID3 putem observa anumite avantaje și limitări ale acestuia ,
analiză făcută după spațiul de căutare și strategia folosită în procesul de căutare:
 În cazul algoritmului ID3 se poate observa că spatiul ipotezelor este un spațiu complet de
funcții finite, cu valori discrete, relativ la atributele disponibile din acesta. Datorită
faptului că orice funcție finită cu valori discrete poate fi reprezentată cu ajutorul arbori lor
de decizie, ID3 evită riscu l major ca spațiul de ipoteze să nu conțină funcția rezultat .
 Acest algoritm păstrează o singură ipoteză curentă în timpul căutării în spațiul de ipoteze
al arborilor, din acest motiv , algoritmul pierde informații care sunt evidențiate de datele
de antrenament disponibile . De exemplu, nu are capacitatea să determin e la un moment
Vreme

26
dat câți arbori de decizie alternativi sunt consistenți cu datele de antrenament disponibile,
sau să ia hotărâri pent ru a ajunge la o ipoteză optimă.
 ID3 nu face căutări în datele căutate anterior . Dacă un atribut a fost deja selectat pentru
test într -un anumit punct al arborelui, el nu mai e ste luat în considerare în drumul sp re
nodul de decizie. Astfel , fiind expus la riscurile căutării fără backtraking , se ajunge la o
soluție optimă locală, care , însă nu este optimul global.
 La fiecare pas, ID3 utilizează toate datele de antrenament în procesul de căutare pentru
luarea decizii lor statistice în privința modul d e rafinare al ipotezei curente, a cest lucru
contrastează cu metodele care iau decizii incrementale, bazându -se pe exemplele de
antrenament individuale. A vantaj ul folosirii valorilor statistice ale tuturor exemplelor, la
fel ca și în cazul utilizării câștigului informațional , este că rezultatul căutării este mai
puțin sensibil la erori în exemplele individuale de antrenam ent. ID3 poate fi ușor extins
pentru a lucra cu date de antrenament care conțin zgomot , prin mo dificarea criteriului de
oprire ca să accepte ipoteze care nu se potrivesc perfect datelor de antrenament [18].

2.5 Preferinț a inductiv ă a arborilor de decizie (Inductive Bias )

Preferința inductivă (Inductive bias ) este setul de ipoteze care, împreună cu datele de
antrenament justifică deductiv clas ificările atribuite de către sistemul care învață viitoarele
instanțe .
ID3 caută u n spațiu complet al ipotezelor, adică unul capabil să exprime orice funcție finită
cu valori discrete . Caută incomplet prin aceast s pațiu, de la ipoteze simple la ipoteze complexe,
până când întâlnește condiția de terminare , până când găsește o ip oteză în conformitate cu datele .
Preferința inductivă a acestuia este doar o consecință a ordonării ipoteze lor de strategia de
căutare .
Preferința inductivă a unui model de învățare supervizată reprezintă preferința acestuia
pentru o anumită ipoteză , în general, i poteze scute , în cazul nostru, fiind arbore le de decizie .
Există numeroși arbori de decizie care pot fi construiți pentru un set de date de
antrenament . A descrie preferința inductivă a algoritmului ID3 constă în a descrie modul în care
alege arborele de d ecizie dintre toț i arborii de decizie posibili.
Așadar , algoritmul ID3 preferă arborii mai mici ș i arborii care au atributele cu un câștig
informa țional mare , cât mai aproape d e nodul rădăcină [18].

27
2.6 Limitări ale algoritmului ID3

2.6.1 Evitarea supraantrenării datelor ( overfitting )

Problem a supra antrenarii datelor (overfitting) este una din tre cele mai mari probleme ale
arborilor de decizie , dar și a celorlalte metode de învățare supervizată.
Algoritmul ID3 dezvoltă fiecare ramură până când reușește să clasifice perfect datele de
antrenament. Acest lucru poate cauza probleme când datele conțin zgomot (pot scădea foarte
mult acuratețea) sau când numărul de date de antrenament este prea mic pentru a putea produce
un mod el reprezentativ a funcției obiectiv . În ambele cazuri , acest algoritmul de bază produc e
arbori care supra antrenează datele de antrenamet . Putem spune despre o ipoteză că
supra antre nează datele de antrenament dacă pentru o alta ipoteză se obține o acurateț e mai mica
pentru datele de antrenament dar se obține o acuratețe mai mare pentru întregul set de date [20].
Există cateva abordări care evită supraantren area în învățarea prin arbo ri de decizie. Se pot
distinge două clase în care acestea au fost grupate:
 abordarea care oprește din timp creșterea arborelui, înainte ca acesta să ajungă în
punctul în care clasifică perfect datele de antrenament;
 abordare care permite supra antrenarea datelor și apoi arborele este trunchiat (post –
prune) ;
Deși prima abordare pare mai directă, a doua abordare (post -prune) s-a dovedit a fi mai de
succes în practică. Acest lucru se datorează dificultății întâlnite în prima abordare când se
estimează oprirea creșterii arborelui.
Indiferent de abordarea folosită se pune întrebare a: ce criteriu ar trebui folosit pentru a
determina corect dimensiunea arborelui?
Prima abord are este cea mai comună și presupune împărțirea datelor în două seturi : unul de
antrenament și unul de validare . Setul de antrenament este folosit pentru construirea ar borelui iar
setul de validare este f olosit pentru evaluarea acurateții și evaluarea impactului aplicării
trunchierii . Motivația acestei abordări este aceea că, indiferent dacă datele de antrenament conț in
unele er ori, aceste a ducâ nd la rezultate eronate , este puț in probabil ca datele de validare să
conțină aceleași tipuri de erori. O euristică spune că se tul de antrenament să conțină două treimi
din numă rul total de date disponi bile, iar setul de validare să conț ină o treime din numă rul total
de date [18].
Există două moduri prin care putem trunchia arborii de decizie:
 Trunchiere a prin reducerea erorii (Reduced error pruning) este abordarea prin
care considerăm fiecare nod din arbore ca fiind candidat la trunchiere. Trunchierea

28
unui nod de decizie constă în eliminarea subarborelui care are ca rădăcină acest
nod, făcându -l nod frunză și atribuindu -i ca valoare cea mai comună claificare
asociată cu acel nod . Elimina rea nodurilor se face doar dacă prin această eliminare
se obține o acuratețe mai mare. De fiecare dată se trunchiaz ă nodul care duce la cea
mai mare creștere a acurateții . Se continuă reducerea nodurilor doar până în
momentul în care aceasta devin e dăunătoare, adică scade acuratețea pe setul de
validare [18].
 Trunchierea regulilor (Rule post -pruning) este abordarea care are succes în practică
în găsirea ipotezelor cu acuratețe mare , fiind utilizată de algoritmul C4.5 , extindere
a algoritmului ID3. Această tehnică implică următorii pași :
o Se construiește arborele de decizie din setul de antrenament,
dezvoltându -l până când datele de antrenament se potrivesc cât mai
bine posibil și permit e să se producă supraantrenarea.
o Se transformă arborele învățat într -un set echival ent de reguli,
creând o regulă p entru fiecare drum de la nodul rădăcină la un nod
frunză .
o Se generalizează fiecare regulă prin eliminarea precondițiilor care au
ca rezultat îmbunătățirea acurateții estimate .
o Se sortează regulile generalizate după acuratețea estimată și în
mome ntul clasificării unei instanțe se consideră regulile în ordinea
acestei sortă ri [18].
În Figura 5 [18] se evidențiază influența supraantrenării în cazul unei aplicații care
lucrează cu arbori de decizie .

Figura 5 Supraantrenarea în învățarea prin arbori de decizie

29
2.6.2 Includerea atributelor cu valori continue

Definiția inițială a algoritmului ID3 limita atributele să facă parte dintr -un set de valori
discrete . Arborii de decizie , în general , ar trebui să fie capabil i să manipuleze atributele cu
valoar e continuă . Un atribut cu valoare continuă este de obicei gestionat prin împărțirea
intervalului său în subintervale , adică este conceput un test care cuantifică intervalul continuu.
În primul rând,valoarea intuită a rezultatului arborelui de învăț are trebuie să fie discretă. În
al doilea rând atributele testate în nodurile de decizie ale arborelui trebuie să aibă de asemenea
valori discrete. Cea de -a doua restricție poate fi eliminată cu ușurință, în așa fel încât atributele
de decizie cu valori co ntinue pot fi integrate în arborele de decizie.
Există metode pr in care aceste valori continue pot fi transformate în valori discrete.
Particulariz ând această metodă , pentru un atribut A cu valori continue se alege o valoare T și
instanțele vor fi împărțit e în două categorii: instanțe pentru care atributul A are valoare mai mică
sau egală decâ t T și instanțe pentru care valoarea atributului A este mai mare decât T. T se
numește punct de tăietură . O altă metodă p entru discretizarea datelor este formarea unei condiț ii
care compară direct două sau mai multe atribute, d e exemplu d acă A < B unde A și B sunt doua
atribute. Datorită numărul mare de astfel de expresii posibile care fac ca spațiul să devin ă prea
mare pentru căutare , în literatură este preferată metod a alegerii punctului de tăietură [6].

2.6.3 Măsuri alternative pentru selectarea atributelor

Atributele cu mai multe valori sunt preferate de către câștigul informațional. Putem
considera ca exemplu atributul Data care are un număr foarte mare de valori posibile. Dacă am
introduce acest atribut în exemplul prezentat mai sus, Joacă Tenis , el va avea cel mai mare caștig
informațional dintre toate atributele. Astfel , este posibil ca acest atribut să fie selectat ca și nod
rădăcină , ducând la un arbore destu l de vast, arbore care clasifică foarte bine datele de
antrenament. Acest arbore de decizie ar da rezultate foarte rele în cazul exemplelor ulterioare,
deoarece nu este un predictor folositor , deși clasifică perfect datele de antrenament.
Problema atribut ului Data este c ă are foarte multe valori posiblie și va împărți datele de
antrenament în foarte multe submulțimi mici având astfel un câștig informațional foarte mare și
va clasifica rapid și perfect datele de antrenament , însă va fi un predictor foarte p rost pentru
instanțe noi.
Folosirea măsurii numite Gain Ratio care penalizează atributele cu numar foarte mare de
valori posibile este o soluție la această problemă.

30

unde S1, S2,…,Sc sunt submulțimile obținute prin partiționarea lui S dupa cele c posibile valori
ale atributului A.
Măsura Gain Ratio se calculează ca fiind raportul dintre Câștigul Informațional și Split
Information .

Observăm că termenul Splitlnformation defavorizează selectarea atributelor care au multe
valori posibibile [18].

2.6.4 Manipularea atributelor cu valori lips ă

În anumite situații , unele date de antrenament p ot avea atribute a căror valo ri lipsesc ,
exemplificativ ar fi domeniul medical , însă putem s ă aproxim ăm valoarea lips ă pe baza datelor
pentru care atributul are valori cunoscute.
Considerăm situația în care trebuie să se calculeze Gain(S, A) pentru nodul n al arborelui
de decizie pentru a se verifica dacă atributul A este cel mai bun atribut pentru testul din acest
nod. Presupunem că <x, c(x)> este unul dintre exemplele de antrenament din S, iar valoarea A(x)
este necunoscută.
O metodă pentru a rezolva problema valorilor lipsă ale unui atribut este să i se atribuie
acestuia valoarea cea mai comună întâlnită printre exemplele de antrenament în n odul n.
Alternativ, îi putem atribui valoarea cel mai des întâlnită printre exemplele care în nodul n au
clasificarea c(x) [18].

2.6.5 Manipulare a atributelor cu costuri diferite

Atributele instanțelor pot avea asociate anumite costuri (valori) în anumit e procese de
învățare . Acest lucra l -am putea exemplifica în cazul încercării de a clasifica diferite boli , putem
descrie pacienții cu ajutorul atributelor , cum ar fi Temperatura , Rezultatul biopsiei, Puls, Analize
de sânge, etc. Aceste atribute variază semnificativ atât în ceea ce prive ște costurile , precum și
costurile bănești, dar și cele privind con fortul pacientului . În aceste cazuri, preferabil ă ar fi

31
utilizarea arborilor de decizie care folosesc atribute cu costuri scăzute , dacă este posibil, utilizând
atribute cu costuri ridicate doar atunci când este nevoie de clasificări fiabile.
Algoritmul ID3 poate fi modificat astfel încât să aibă posibilitatea de a lucra cu atribute
care au anumite costuri prin introducerea unui termen privind costul în metod e de selecție a
atributelor. De exemplu, s -ar putea divide câștigul ( Gain ) în funcție de costul atributelor, astfel
încât cele cu cost scăzut să fie preferate [18].

2.7 Avantajele și dezavantajele arborilor de decizie

Arbor ii de decizie sunt utilizați în foarte multe domenii pentru avantajele lor, dar au și
anumite inconveniente.
Aceștia sunt superiori altor metode de învățare datorită avantajelor pe care le au și anume :
 sunt ușor de înțeles și interpretat , raționamentul lor fiind ușor de urm ărit;
 permit utilizarea seturilor de date care conține atât atribute numerice cât și
nominale;
 pot să lucreze cu seturi de date care conține erori;
 pot manipula seturi de date care conți n atribute ale căror valori lipsesc ;
 sunt rapizi și robuști și pot luc ra cu seturi de date mari ;
 arborii de decizie nu au nici un fel de ipoteze legate de spațiul de distribuție și
structura clasificatorului , astfel fiind considerați metode neparametrice ;
 sunt una dintre cele mai utilizate metode pentru luarea în considerare a multor
rezultate în ceea ce privește o decizie și au rolul de a ajuta utilizatorul în
compararea consecințelor deciziilor posibile, astfel ajutând la luarea celei mai bune
decizii .
După cum am spus, arborii de decizie prezintă și anumite dezavantaje cum ar fi:
 complexitatea, aceștia f iind ușor de înțeles atunci când se utilizează seturi de date
mici, în schimb, când se utilizează seturi de date mari, aceștia cuprind zeci de
noduri decizionale , fiind complicați și au valori limitate ; astfel acuratețea
rezultatelor așteptate scade pe măsură ce numărul de decizii de lua t crește ;
 un alt dezavantaj al utilizării arborilor de decizie este că rezultatele deciziilor, ale
deciziilor ulterioare și ale beneficiilor se pot b aza, în primul rând , pe așteptări;
atunci când se iau decizii reale, deciziile care rezultă pot fi diferite de cele pe care
le-am planificat;
 majoritatea algoritmi lor (ID3, C4.5 ) necesită ca valorile target -ului să fie valori
discrete;

32
 costurile ridicate;
 instabilitate a, arborele de decizie modificându -se când perturbăm setul de date , iar
acest lucru nu este de dorit deoarece dorim ca algoritmul nostru de clasificare să fie
destul de robust la zgomot și să fie capabil să ge neralizeze bine instanțele noi .

33
CAPITOLUL III
Utilizarea arborilor de decizie în medicină

Dacă ar fi să vorbim despre ce are omul mai prețios , am spune că sănătate a este cel mai
important aspect . Dacă suntem sănătoși și nu ne deranjează nimic, nu o prețuim deoarece nu știm
cum este să fii bolnav . Dar, cum ne îmbolnăvim, punem imediat la îndoială scopurile și planurile
noastre, dar și toate dorințele și posibilitățile. Trebuie să privim sănătatea și din perspectiva
confortului mental și emoțional , nu doar di n perspectiva confortului fizic. Sănătatea fizică putem
să o menținem printr -o alimentaț ie corectă și prin sport, iar pe c ea emoțională, prin evitarea
stresului , care este mai greu de controlat . Sunt o mulțime de metode prin care îți poți menține
sănătatea , alegerea metodei adecvate ducând la s ucces . Decizia de a avea un mod de viață
sănătos este, de fapt , o opțiune personală. Cu toate acestea, în zilele noastre, sănătatea este
neglijată .
Thomas Goetz prezintă ideea după care se ghidează aplicația sa astfel : “Sănătatea noastră
nu se consumă toată dintr -o dată, este o consecință a ani de alegeri, unele mai mici, altele mai
mari, care se combină ducând la ceea ce numim sănătatea pe care o avem. Uneori facem alegeri
înțelepte și ne bucurăm de o sănătate bună, a lteori alegem greșit și prin urmare suferim
consecințele. Arborele de decizie este de fapt o figura de stil, un dispozitiv care poate face aceste
decizii mai explicite și mai evidente, ceva ce alegem propriu -zis, este un mod de a externaliza
deciziile pe c are altfel le luăm fără a ne gândi prea mult la ele. Cercetările arată că atunci când
ne angajăm de fapt într -o decizie (atunci când o gândim, chiar și doar pentru câteva momente)
avem tendința să luăm o decizie mai bună, definită atât ca una care ne este mai confortabilă în
retrospectivă și ca una care duce la un rezultat mai bun. Conlucrând cu sănătatea noastră în
mod conștient și explicit printr -o serie de decizii, putem deveni mai “inteligenți” și ne putem
bucură de sănătatea noastră.” [9].
Luarea deciziilor corecte devine factorul cheie în atingerea obiectivelor noastre pe toate
planurile, atât personal, cât și profesional. De regulă, luarea deciziilor se bazează pe experiențele
din trecut și pe raționamentul personal. Deși cazurile rezolvate din experiențele trecute ar trebui
să ducă la decizii corecte și sigure, nu este așa, deoarece cazurile noi apărute sunt mult mai
complicate și mai complexe. Astfel apare nevoia unor sisteme capabile să asiste oamenii în
luarea deciziilor , deoarece cantit atea imensă de informație nu poate fi procesată de aceștia.
Aceste sisteme ar putea veni în ajutorul nostru, presupunând faptul că ele ar fi capabile să
procese cantitatea imensă de informație, oferind decizia cea mai bună.

34
Deciziile cele mai greu de luat , sunt deciziile neprogramate. Ele sunt luate în situații
inedite și în condiții nestabilite. Deciziile neprogramate nu au proceduri prestabilite de rezolvare,
deoarece nu au ma i fost întâlnite sau pentru că sunt foarte dificile și complexe. Condițiile de
incertitudine , de risc crescut, unde stresul accentuează și amplifică caracter ul incert și riscant al
deciziilor fac ca acestea să devină vulnerabile .
Prin urmare, deciziile sunt esențiale pentru obținerea obiectivelor noastre, având un rol
important în m ulte domenii, în special în medicină, unde decizia trebuie luată într -un mod cât
mai eficient, ea având un rol decisiv . Partea importantă a proces ului medical sunt aceste s isteme
care au rolul de a asigura asistență în procesul de diagnosticare medicală. A stfel, sistemele de
suport decizional devin o ramura importantă în medicină.
Privită ca un ansamblu, sănătatea pare un lucru enigmatic, însă dacă o privim ca fiind
formată din mai multe părți, această duce la o serie de decizii, fiecare dintre ele cu riscu l,
beneficiile și compromisurile ei. Cu alte cuvinte, putem organiza sănătatea noastră într -un arbore
de decizie, acesta fiind un mod de a transformă datele pe care le avem despre sănătatea noastră,
de structurare a opțiunilor într -un sistem d e alegeri și rezultate mai bune [10].
În medicină, arborii de decizie sunt utilizați d e mai bine de 20 de ani și au ca scop luarea
celei mai bune decizii sau a unei decizii adecvate într-o situație limită . Medicina este un domeniu
în care luarea deciziilor reprezintă o problema majoră . Așa cum spunea Șir. William Osler
“Medicina est e știința incertitudinii și arta probabilității ”.
Arborii de decizie sunt indicați pentru astfel de probleme deoarece sunt modele relativ
simple , dar cu o performată mare, cel mai mare avantaj al lor fiind faptul că , raționamentul
acestor modele poate fi urmărit spre deosebire de cele mai multe modele de învățare.
Posibilitatea urmăririi raționamentului este foarte importantă deoarece medicina este un domeniu
crucial. Astfel specialiștii pot trage concluzia dacă soluția oferită de sistem este corectă sau nu.
Thomas Goetz, în cartea sa “The Decision Tree: Taking Control of Your Health în the New
Era of Personalized Medicine ” [11], ne încurajează să ne construim propriul arbore de decizie, în
ceea ce privește sănătatea noastră. Acesta ar putea începe cu vizualizarea efectelor ADN -ului
asupra noastră. Putem ține evidența stării noastre de sănătate fie prin servicii de genomică
personală cum ar fi testele de screening, fie prin auto -monotoriza re care se poate realiza prin
aplicațiile de pe smartphone -uri și Iphone -uri.
Articolul “ Decision tree classifiers for automated medical diagnosis “ [1] prezintă un
instrument de susținere a deciziei pentru detectarea cancerului la sâ n pe baza a trei tipuri de
arbori de decizie: arbori de decizie unici (single decision tree – SDT) , arbori măriți (boosted
decision tree – BDT) și păduri de arbori de decizie (decision tree forest – DTF) . Luarea deciziilor
se face în două etape: formarea clasificatorilor cu cara cteristici din setul de date Wisconsin
privind cancerul la sâ n și apoi testarea. Performanța structurii propuse este evaluată în funcție de

35
sensibilitate, specificitate, acuratețe. Rezultatele au arătat că acuratețea totală a SDT și BDT în
faza de învățare a atins 97,07%, respectiv 98,83. BDT a arătat cea mai bună performanță în ceea
ce privește se nsibilitatea, iar SDT a fost cel mai bun d oar în ceea ce privește viteza [1].
În articolele mai generale, Cremilleux (1977) și Robert [21] prezintă cadrul general pentru
utilizarea arborilor de decizie în medicină . Kokol (1998) și alții în lucrarea lor prezintă o anumită
limitare a arborilor de decizie în domeniul medical.
Zorman et al. [21] au evaluat diferite strategii de inducție în ce privește arborii de decizie
utilizând probleme din lumea reală și anume fracturile ortopedice. Au testat abordări clasice, una
hibridă (arbori de decizie și rețele neuronale) și una evolutivă. Ei au testat diverse metode pentru
construcția unor arbori de decizie invarianți cu scopul de a ajunge la cea mai bună strategie de
inducție. Rezultatele au demonstrat că abordările testate au avut lipsuri în ceea ce privește
acuratețea, sensibilitatea sau dimensiunea arborelui de decizie. Comparația arată că cel mai bun
compromis în con strucția arborilor de decizie utilizând probleme din lumea reală este abordarea
evolutivă.
Tsien et al. [21] au remarcat faptul că arborii de decizie pot prezenta ajutor în
diagnosticarea precisă și din timp a infarctului miocardic. Au fost produse numeroa se sisteme
care să ofere asistenț ă experților în această problemă . Din păcate, acestea nu au ajuns să fie
folosite. Tehnicile de învățare care cuprind arbor ii de clasificare și regresiile logistice (LR) au
potențialul de a genera modele simple, dar precise care să poată fi utilizate în asistența experților.
Au fost produse atât un arbore fără clasificare (FT Tree) , cât și un model LR (FT LR) pentr u a se
prezice probabilitatea ca un pacient cu durere în piept are infarct miocardic. Acest fapt se
constată nu mai pe datele disponibile la momentul prezentării pacientului la secția de urgențe.
Datele de antrenament utilizate au fost luate dintr -un set de date colectate în Edinburg, Scoția.
Fiecare model a fost mai apoi testat pe un set de date separat din Edinbur g și de asemenea, pe un
set de date dintr -un spital din Sheffield, Anglia. Spre deosebire de lucrările anterioare din acest
domeniu, acest studiu indică faptul că arborii de clasificare, care au anumite avantaje față de
modelele LR, pot lucra la fel de bin e ca și modelele LR în ce privește diagnosticarea pacienților
cu infarct miocardic.
Bonner (2001) [21] a examinat aplicarea arborilor de decizie în luarea deciziilor cu privire
la îngrijirea sănătății men tale în Marea Britanie . Există puține dovezi care au fost publicate în
ceea ce privește folosirea acestora în procesul clinic de decizie cu scopul sta bilirii sănătății
mentale. Dubla diagnosticare, complexitatea acesteia (schizofrenie și abuzul de substanță în acest
caz) și diferitele puncte de vedere ale d iferitor profesioniști împiedică adesea procesul de luare a
deciziilor. Această lucrare a evidențiat cum abordarea a fost folosită cu succes ca și o abordar e
colaborativă multiprofesională în luarea deciziilor în cadrul comunității britanice de î ngrijire a
sănătății mentale.

36
Babic (2000 ) et al. [21] au demonstrat avantajele arborilor de decizie fuzzy referitoare la
luarea deciziilor în cazul alăptării. Barierele fuzzy înlocuiesc barierele clare între valori, fiind
mult mai generale și ușor de folosit.
Jones (2001) [21] pune în evidență aplicabilitatea arborilor de decizie privind constatarea
semnelor unor posibile reacții adverse în cazul unor medicamente. Apariția bazelor mari de date
în ce privește datele referitoare la adversitățile și necesitatea identi ficării semnelor unor noi
efecte, efectele adverse necunoscute ale noilor medicamente comercializate de către autoritățile
de reglementare și de sponsorii farmaceutici au coincis cu dezvo ltarea mai multor metode de data
mining pentru indentificarea unor no i asociații între toate tipurile de baze de date. El a ajuns la
concluzia că utilizarea data mining -ului bazându -se pe metodele arborilor de decizie are rezultate
promițătoare în ce privește identificarea unor semnale noi, necunoscute ale efectelor adverse , mai
ales în cazul populațiilor definite. În 1997, autoritățile în c eea privește sănătatea statului Sao
Paulo, Brazilia au realizat o campanie de vaccinare împotriva pojarului bazându -se pe un model
decizional care utiliza logică fuzzy . Astfel strategia aleasă pentru vaccinarea în masă, a schimbat
cursul natural al epidemiei în acest stat. Realizatorii proiectului au creat un arbore de decizie pe
care mai apoi l -au comparat cu modelul logicii fuzzy. Contrastul dintre cele două metode
abordate a fost evidențiat prin utilizarea în esență a aceluiași set de ipoteze. Modelele identifică
aceeași strategie ca fiind cea mai bună, dar prezintă diferențe în clasificarea strategiilor rămase.
Dantchev (1996 ) [21] a dovedit că tehnicile de luare a decizii lor bazate pe calculator și
anume, că arborii de decizie sunt încă în stadiul experimental și este în continuare dificil să fie
aplicați în practicile clinice în domeniului psihiatriei. Totuși, aceștia par a fi de mare interes nu
doar în dobândirea cunoști nțelor de comunicare, predare și formare precum și în cerce tare.
Arborii de decizie permit vizualizarea rezultatele studiilor epidemiologice și de cercetare clinică
dintr -o perspectiva de ansamblu, pentru a evidenția zonele gri ale științei și pentru a sta bili noi
priorități în cercetare.
În recenzia lui, Gambhir (1999 ) [21], s-a concentrat pe metodologia implicată în
revizuirea în mod corespunzător a literaturii medicale în scopul efectuării unei meta -analize, iar
mai apoi pe metodele care îndeplinesc o a naliză decizională form ală utilizând arbori de decizie.
El abordează problemele apărute în cazul relatării unei meta -analize detaliate ținând cont de
anumite neclarități printre care și publicarea preferințelor (bias), verificarea acestora și spectrul
pacientului. A șadar, fiind detaliată importanța colectării de măsuri convenț ionale privitoare la
performanța testului ( de exemplu sensibilitate a și specificitate a) și de modificări în
managementul pacientului pentru a se efectua modelul cost -eficienț ă al unui algoritm de
gestiune. Datorită frecvenței folosirii tehnicilor abordate în recenzie, cercetătorii în medicină
nucleară ar trebui să fie mai bine pregătiți pentru a concura pentru puținele resursele disponibile

37
în mediul actual de îngrijire a sănătății. În plus, medicii fiind mai bine pregătiți ii vor putea ajuta
pe pacienți folosind studii le cu rol dovedit în îmbunătăț irea managementului pacientului [21].
În Articolul “ Different Decision Tree Induction Strategies for a Medical Decision
Problem ” [4] este p rezentat un caz medical particular și anume durerile abdominale acute. Se
prezintă două abordări ale arborilor de decizie privind această problema. Prima abordare nu
utilizează cunoștințe de specialitate și generează clasificator numai pe baza setului de învățare. A
doua , utilizează cunoștințe de specialitate pentru a specifica structura arborelui decizional și setul
de învățare pentru determinarea modului de luare a deciziilor în fiecare nod pe baza teoriei
decizionale Bayes. Toți clasificatorii sunt eval uați pe baza experimentelor pe calculator.
Clasificatorii generați de aceste abordări s -au aplicat algoritmilor pentru rezolvarea problemei
medicale (recunoașterea durerii abdominale acute) și pot fi utilizate pentru a asista medicii în
diagnosticare, aduc ând o îmbunătățire semnificativă a cal ității îngrijirilor medicale [4].
Articolul “ Prediction of prostate cancer using decision tree algorithm ” [13] Zorman et al.
utilizează arborii de decizie în predicția cancerului de prostată folosind informațiile oferi te de
PSA (Serum Prostate Specific Antigen) . Date le au fost evaluate prin analiza arborilor de decizie
și cea a regresiei logistice. Cu ajutorul arborelui de decizie realizat, se definesc două subgrupe de
pacienți care au o posibilitate foarte scăzută de a avea cancer, în funcție de nivelul de PSA și de
DRE (Digital Rectal Examination) . Arborii de decizie s -au dovedit ma i eficienți comparativ cu
metoda tradițională baz ată doar pe raportul PSA/PSA [13].
În zilele noastre, cancerul la sân este o cauză frecv entă a decesului în rândul femeilor.
Depistarea la timp și aplicarea tratamentului medicamentos poate salva vieți. Astfel, articolul
“Identification of Breast Cancer Using Ensemble of Support Vector Machine and Decision Tree
with Reduced Feature Subset ” [14] încurajează utilizarea unui sistem eficient de identificare a
cancerului la sân. În ultimii ani, arborii de decizie și mașinile cu suport vectorial ( SVM ) au
demonstrat capacitatea lor de a diagnostica eficient cancerul la sân.
În viitor, un sistem inte grat de suport decisional ( DSS) va fi dezvoltat pentru identificarea
multor boli care ne pun viața în pericol. Acest studiu, pune în evidență un model de ansamblu
(ensemble model ), care reprezintă combinarea a doua sau mai multe tehnici pentru a elimina
neajunsurile modelelor individuale în scopul obținerii unei acurateți cât mai mare.

38

Figura 6 Modelul de ansamblu pentru diag nosticarea cancerului la sân [14]

Combinarea SVM cu algoritmul C5.0 a lui Ross Quinlann pentru diagnosticarea
cancerului la sân reprezinta modelul de ansamblu prezentat în acest articol. La acestea a fost
adăugată și o tehnică de selecție a atributelor pe baza rangului ( rank feature selection ) pentru a
determina atributele relevante pentru obținerea rezultatelor și înlăturarea atributelor nerelevante
în sco pul obținerii unei acurateți cât mai mare. Această tehnică de eliminare a atributelor
nesemnificative împreună cu combinarea celor doua metode a fost aplicată pe un set de date de
pe pagina UCI Machine Learning Repository care conține informații despre cancerul la sân.
Inițial setul de date conținea 33 de atribute, iar după eliminarea atributelor nesemnificative s -a
obținut un subset cu doar 5 atribute. Pe acest set de date nou s -a obținut o acuratețe de 92.59%, o
senzitivitate de 100% și o specificitate de 60% [14].
Obiectivul articolului “Diagnosis of Breast Cancer using Decision Tree Models and
SVM ” [5] evaluează performanțele noilor algoritimi descoperiți pentru modelarea arborilor de
decizie și le compară cu perfomanța mașinilor cu suport vectorial ( SVM ), mai exact radial basis
function kernel support vector machine (RBFSVM ), în cazul diagnosticării c ancerului la sân. S –
au folosit patru tipuri de arbori de decizie: Chi-squared Automatic Interaction Detection
(CHAID), arbori de clasificare și regresie ( C&R ), Quick Unbiased Efficient Statistical Tree
(QUEST) și noul model C5.0. al lui Ross Quinlan. Ace ști algoritmi au fost aplicați pe setul de
date Wisconsin Breast Cancer.

39
Performațele obținute în urma aplicării celor cinci clasificatori au fost următo arele :

Figura 7 Performanțele clasificatorilor pentru setul de date Wisconsin Breast Cance r [5]

Putem observa că utilizând mașinile cu suport vectorial ( SVM ) a rezultat cea mai mare
acuratețe pentru datele de antrenament 99.976% , dar cea mai mare acuratețe 96.635% pentru
datele de test s -a obținut prin aplicarea lui C5.0. La fel și în cazul senzitivității , cea mai mare
senzitivitate pentru datele de antrenament 100% s-a obținut folosind SVM , iar cea mai mare
senzitivitate pentru datele de test 99.074% s-a obținut utilizând CHAID . Când vine vorba de cea
mai mare specificitate , pentru datele de antrenament 99.074% a rezultat în urma aplicării SVM ,
iar pentru datele de test 94.845% s-a obținut folosind C5.0 și SVM [5].
Există totusi anumite rețineri, limitări în ceea ce privește folosirea arborilor de decizie în
medicină. În articolul “ The Limi tations of Decision Trees and Automatic Learning în Real World
Medical Decision Making ” [26] Zorman et al. evidențiază faptul că abordarea arborilo r de
decizie sunt una dintre cele mai des utilizate metode în luarea deciziilor și în învățarea automată.
Învățarea automată a arborilor de decizie și utilizarea lor, de obicei, prezintă rezultate foarte bune
în diferite medii "teoretice". Însă, în viață reală este adesea imposibil să găsim numărul dorit de
obiecte reprezentative de antrenament din diferite motiv e. Câteva motive reprezentative sunt:
lipsa posibilităților de a măsură valorile atributelor, costurile ridicate, complexitatea unor astfel
de măsurători precum și lipsa tuturor atributelor în același timp. Datori tă acestor motive, se
propune ca arborii de decizie să nu fie folosiți pentru sarcina lor principala și anume, luarea
deciziilor, ci pentru a evidenția cele mai importante atribute. În acest domeniu delicat, medicina,
nu ne permitem să luăm decizii inexacte sau eronate, iar “sfaturile” oferite de a rborii de d ecizie
pot fi de mare ajutor [26].

40
CAPITOLUL IV
Aplicația practică . DT4Park – Decision Tree for assisting the
diagnosis of Parkinson

În acest capitol vom prezenta o scurtă descriere a aplicației practice DT4Park . Scopul
acesteia este de a studia performanț ele sistemelor bazate pe arbori de decizie în procesul asistării
automate a diagnosticării medicale și în special în diagnosticarea bolii Parkinson .

4.1 Dezvoltarea apli cației
4.1.1 Definirea și specificarea problemei

Ritmul de viață actual este unul agi tat, obositor și stresant. Statisticile arată că surmenajul,
ar putea fi ș i el un factor care poate declanș a boa la Parkinson pe lângă mulți alț i factori cum sunt
trauma tismele, traumele psihice. Dar î n afara etiologiei degener ative, boala Parkinson poate
apărea din diferite motive: î n urma u nei encefalite, a unei intoxicaț ii cu gaze toxice, din cauza
etiolismului cr onic. Principala cauză este î ncă necunoscută și ar putea fi mai mult decâ t un agent
cauzator.
Boala Parkinson este o boală degenerativă ce apare în urma distrugerii lente și progresive
a neuronilor , afectând aproximativ zece milioane de persoane din întreaga lume . Pacienții care
suferă de această boala prezintă gesturi rigide, sacadate și incontrolabile, tremor și instabilitate
posturală.
Această afecțiune neurologică are o frecvență crescută în ultima perioadă de timp. În ciuda
eforturilor științifice ș i medica le depuse până în prezent , nu s -a găs it încă un tratament pentru
vindecarea pacienț ilor bolnavi de Parkinson, dar noile scheme de t ratament le îmbunătăț esc
semnificativ calitatea vieț ii.
Diagnosticarea în faze incipiente a bolii este foarte importantă pentru a putea găsi un
tratamen t corespunzător, care ar putea îmbunătăț i calitatea vieț ii celor diagnosticați cu această
boală.
În fiecare c lipă a vieții noastre trebuie să luă m anumite decizii. Fiecare act al nostru este
rezultatul unei decizii luate. Dintre decizii, unele su nt mai importante altele mai puți n
importante, unele decizii având chiar un rol decisiv în viaț a noas tră, astfel trebuie să fim atenț i ce
decizii luăm.

41
Deciziile sunt de o importanță semnificativă în medicină, mai ales în procesul de
diagnosticare. În medicină , diagnosticarea joacă un rol foarte important , iar deciziile greșite pot
avea co nsecințe fatale, iar pentru a î nlatura acest fen omen, deciziile luate trebuie să ia în
considerare foarte multe lucruri, fiind important să nu se omită nimic din ce ar putea influenț a
rezultatul, deoarece orice amănunt contează. Ar fi utilă existenț a unor sisteme care s ă ajute
medicii în luarea deciziilor, deoarece ș i medicii sunt oameni ș i pot greș i. Aceste sis teme trebuie
să fie exacte , iar raționamentul lor să poată fi vizual izat de către medici pentru a își da seama
dacă decizia este corectă . Arborii de de cizie sunt compatibili cu cerinț ele pentru construirea unor
astfel de sisteme de asistare deoarece datele despre bolnavi pot fi reprezentate cu ușurintă sub
forma unor perechi de valori de forma <atribut,valoare>, rezultatele obț inute folosind acest tip de
învățare au o precizie mare, iar raționamentul lor poate fi urmă rit.
Scopul aplicației este de a studia performanțele sistemelor bazate pe arbori de decizie în
ceea ce privește diagnosticarea medicală , în special diagnosticarea bolii Parkinson . De asemenea,
se pot diagnostica noi pacienți după ce la înc eput, aplicația a fost antrenată folosind un set de
date din literatura de specialitate , disponibil la [22].
Baza de date pe care am folosit -o, Parkinson Disease , este formată din fișiere de test și
fișiere de antrenament, care conțin informații despre boala Parkinson . Setul de date este format
din 1040 de instanțe , fiecare dintre ele având câte 28 de atribute și două posibilități de
clasificare : 0 (nu are Parkinson ) și 1 (are Parkinson) . Aceste două pos ibilități de clasificare 0 și 1 ,
le-am înlocuit cu x și y, deoarece am creat o constrâ ngere pe setul de date și anume ca atributul
de target (cel pe baza căruia se realizează clasificarea) să fie nominal .
Setul de date este balansat, deoarece d atele de antrenament aparțin la 20 de persoane
sănătoase (10 femei, 10 bărbați) și 20 de persoane cu Parkinson (6 femei, 14 bărbați) care au
apelat la Departamentul de Neurologie al Facultății de Medicină din Cerrahpasa, Universitatea
din Istanbul . Sunt lu ate mai multe tipuri de înregistrări sonore (26 eșantioane de voce, inclusiv
vocale susținute, numere, cuvinte și propoziții scurte) din toate subiectele. Din fiecare probă de
voce sunt extrase un grup de 26 de caracteristici liniare de timp bazate pe frec vență. Eșantioanele
de voce din fișierul de date de antrenament sunt date în ordinea:
 1: sustained vowel (aaa¦…. );
 2: sustained vowel (ooo¦…);
 3: sustained vowel (uuu¦…);
 4-13: numbers from 1 to 10;
 14-17: short sentences;
 18-26: words.

42
UPDRS ( Unified Parkinson’s Disease Rating Scale ) scorul fiecărui pacient care este
determinat de medicul expert este de asemenea disponibil în acest set de date. Acest lucru, face
posibilă utilizarea acestui set de date ș i pentru regresie.
După colectarea datelor de antrenament, s -a colectat un set de date independent de testare
de la persoane care au boala Parkinson prin același proces de examinare, în aceleași condiții . În
timpul colectării ace stui set de date, 28 pacienți sunt rugați să spună numai vocalele susținute "a"
și "o" de trei ori, ceea ce înseamnă un total de 168 de înregistrări. Aceleași 26 de caracteristici
sunt extrase din eșantioane le de voce din acest set de date. Pentru validarea rezultatelor obținute
în setul de antrenament, poate fi utilizat ca set de testare independent acest set de date.
Cele 28 de atributele ale instanțelor sunt:
 Jitter (local);
 Jitter (local, absolute);
 Jitter (rap);
 Jitter (ppq5);
 Jitter (ddp);
 Shimmer (local);
 Shimmer (local, dB);
 Shimmer (apq3);
 Shimmer (apq5);
 Shimmer (apq11);
 Shimmer (dda);
 AC (Autocorrelation) ;
 NTH (Noise -to-Harmonic) ;
 HTN (Harmonic -to-Noise) ;
 Median pitch;
 Mean pitch;
 Standard deviation;
 Minimum pitch;
 Maximum pitch;
 Number of pulses;
 Number of periods;
 Mean peri od;
 Standard deviation of period;
 Fraction of locally unvoiced frames;
 Number of voice breaks;

43
 Degree of voice breaks;
 UPDRS (Unified Parkinson’s Disease Rating Scale) ;
 class information .

Am eliminat câteva atribute nesemnificate, iar d atele prelucrate sunt citite dintr -un fișier
csv (comma separated value) care are următoarea formă :

1.488,0.000090213,0.9,0.794,2.699,8.334,0.779,4.517,4.609,6.802,13.551,0.905905,0.12,1
1.13,166.53,164.78,10.42,142.23,187.58,160,159,0,0,y
0.728,0.0000376 98,0.353,0.376,1.059,5.864,0.642,2.058,3.18,7.194,6.175,0.951285,0.07,1
7.4,195.25,193.29,14.77,159.52,234.51,170,169,2.25,0,y
1.22,0.000074041,0.732,0.67,2.196,8.719,0.875,4.347,5.166,7.548,13.04,0.911508,0.11,12
.21,158.69,164.77,12.98,146.45,211.44,1431,1 427,10.66,0.18,y
2.502,0.000122824,1.156,1.634,3.469,13.513,1.273,5.263,8.771,16.779,15.789,0.901302,0
.12,11.38,202,203.47,10.85,182.71,220.23,94,92,0,0,y

4.1.2 Analiză și proiectare

Pentru realizarea aplicației am folosit algoritmul ID3, pe care l -am îmbunătățit prin
trunchierea arborelui (pruning) pentru a evita supra antrenarea și prin discret izarea atributelor,
metode pe care algorimult ID3 clasic nu le are. Aceste îmbunătățiri le -am folosit pentru a aduce
o performanță cât mai mare a sistemului.
Aplicația este generică, poate fi utilizat orice set de date . Datele prelucrate sunt citite dintr –
un fișier text în care pe prima linie se află numele atributelor, iar pe următoarele linii sunt
instanțele atributelor. Ultimul atribut reprezintă atributul de target sau eticheta (label) , pe baza
căruia se va face clasificarea . Acesta din urmă, trebuie să fie nominal (string) . Numele
atributelor sunt separate prin virgulă. De asemenea, instanțele sunt separate prin virgulă și sun t
formate fie din valori discrete, fie din valori continue. Valorile cont inue, vor fi discretizate pe
baza caștigului informațional (information gain) .

44

Figura 8 Diagra ma cazurilor de utiliz are

Figura 9 Diagrama de clase pentru Model e (Models ) și Utilitare (Utils )

45
4.1.3 Implementare

Proiectul este o aplicație windows forms dezvoltată în limbajul de programare C#. De
asemenea, am folosit framework -ul Accord.N et pentru trunchierea arborelui (Chi Square
Pruning) și anume pentru calcularea lui chi-pătrat .
În cele ce urmează vom prezenta p rincipalele clase ale aplicației.
În clasa DtAttribute se verifică dacă atributul este nominal sau numeric , dacă este nominal
se obț in valorile nominale distincte pe care le poate lua atributul și se introduc în lista
distinctItems . Se obț ine lista tuturor itemurilor (instanțelor) care au aceeași valoare pe câ mpul
corespunzator atributului res pectiv , iar apoi se creeză un bin (interval nou) , care va contine toț i
itemii cu valoarea respectivă. Dacă este numeric, trebuie s ă se împartă pe baza unei separă ri
statistice și anume pe baza câștigului i nformațional, realizându -se astfel și discretizarea
atributelor.

public class DtAttribute
{
public void SplitIntoBins()
{
if (Items.Count >= 1 && Items[0].Item2 is string)
{
SplitIntoBinsNominal();
return;
}
var bin = new DtBin
{
Items = Items
};
SplitIntoBins(bin);
}

private void SplitIntoBinsNominal()
{
//se obtin valorile nominale distincte pe care le poate lua
//atributul si se introduc in lista distinctItems
distinctItems=Items.GroupBy(x=>x.Item2).Select(x => x.Key).ToList();
//astfel, pentru fiecare valoare distincta obtinuta
foreach (var distinctItem in distinctItems)
{
//se obtine denumirea valorii nominale
var item = (string)distinctItem;
//se obtine lista tuturor itemurilor ca re au aceasta
//valoare pe campul corespunzator atributului resectiv
binItems=Items.Where(x=> x.Item2.Equals(item)).ToList();
//se creeza un bin (interval ) nou care va contine toti
//itemii cu valoarea respectiva
Bins.Add(new DtBin{
Items = new List<Tuple<int, object, string>>(binItems),
Label = item,
IsNominal = true
});
}
}
private void SplitIntoBins(DtBin bin)
{
var bin1 = new DtBin();
var bin2 = new DtBin
{

46
Items = new List<Tuple<int, object,string>>(bin.Items)
};
var binList = new List<DtBin> {bin1, bin2};
var maxIg = ComputeInformationGain(binList);
var maxI = -1;
int i = 0;
while (bin2.Items.Count > 0)
{
bin1.Items.Add(bin2.Items[0]);
bin2.Items.RemoveAt(0);
var ig = C omputeInformationGain(binList);
if (ig > maxIg)
{
maxIg = ig;
maxI = i;
}
i++;
}
if (maxI == -1)
{
Bins.Add(bin1);
return;
}
for (i = bin1.Items.Count – 1; i > maxI; i –)
{
bin2.Items.Insert(0, bin1.Items[i]);
bin1.Items.RemoveAt(i);
}
if(StoppingCriteriasApply(maxIg,bin,bin1, bin2))
{
Bins.Add(bin);
return;
}
if (bin1.Items.Count <= 1)
{
Bins.Add(bin);
return;
}
else
{
SplitIntoBins(bin1);
}
if (bin2.Items.Count <= 1)
{
Bins.Add(bin);
return;
}
else
{
SplitIntoBins(bin2);
}
}
}

În clasa DecisionTree se creează în mod recursiv arborele de decizie pe baza setului de
date. În primul rând, se creează un nod care va fi pă rintele de pe nivelul curent. Condițiile de
oprire ale recursivității sunt:
 dacă în setul de date nu mai există decât un sin gur atribut, atunci nodul e frunză și
va avea ca etichetă cea mai frecventă valoare a targetului itemilor din setul de date ;
 dacă se ajunge ca targetul tuturor itemilor din setul de date curent să aibă aceea și
valoare, atunci este din nou frunză și va primi ca etichetă valoarea respectivă ;

47
 dacă nu mai există instanțe se creează o frunză cu cea mai frecventă valoare a
etichetei din setul de date și o pun em copil la nodul curent .
Până când una dintre aceste con diții este adevarată, funcția BuildDt va fi apelată recursiv
deoarece setul de date aparț ine unui descendent ( copil ) al nodului curent care poate la râ ndul lui
să aibă copii ș i atunci o să adaug ăm la copiii nodului curent rezultatul apelului recursiv pent ru
setul de date nou creat .
Nodul curent va fi un nod părinte pentru alte noduri din arborele de decizie și se va alege
dintre atribute acela care aduce cel mai mare caștig informațional . Atributul ales se setează ca
atribut al nodului curent care nu e frunză , se creează un nou set de date . Pentru fiecare set de
date nou creat , se creează un nou set de atribute care nu îl va mai coține pe atributul folosit deja
ca nod curent. Pentru fiecare item din item -urile din bin, pentru fiecare dintre atributele rămase
în setul de date , se gaseș te atributul din noul set de date pentru a putea fi introduse itemurile
corespunzătoare în el. Se salvează o copie a itemului în atributul găsit din noul set de date. În
continuare, se calculează numă rul de valori distincte pentru valorile targetului din noul set de
date creat. E importan t să fie calcula t acum pentru că ajută la stabilirea ulterioară a statutului de
frunză a nodului curent din arbore. După ce am facut toate seturile de date din interval (bin -uri)
trebuie să sortam din nou v alorile pe atributele numerice și să recalculă m bin -uri pe setul de date
nou creat .

public class DecisionTree
{
public void Build(Dataset dataset)
{
Root = BuildDt(dataset);
}
private DtNode BuildDt(Dataset dataset)
{
//se va obtine in mod recursiv arborele de decizie pe baza
//setului de date
//in primul rand, se creeaza un nod care va fi parintele de
//pe nivelul curent
var parent = new DtNode();
// se verifica daca in dataset nu mai exista decat un
//atribut si atunci sigur nodul e frunza
if (dataset.Attributes.Count == 1)
{
parent.IsLeaf = true;
//in acest caz eticheta va fi data ca eticheta cea mai
//frecventa a tergetului itemilor din dataset
parent.Label = GetMostFrequentLabel(dataset);
}
//daca se ajunge ca targetul tuturor itemilor din setul de
//date curent sa aiba aceeasi valoare
else if (dataset.TargetAttributeValuesCount == 1)
{
//iarasi e frunza si are eticheta valoarea respectiva
parent.IsLeaf = true;
parent.Label = dataset.Attributes[0].Items[0].Item3;
}
else
{
//daca nu atunci , nodul curent va fi un nod parinte

48
//pentru alte noduri din arborele de decizie
var maxI = 0;
var i = 0;
var maxIg = -1.0;
//se va alege dintre atribute acela care aduce cel mai
//mare castig informational
foreach (var dtAttribute in dataset.Attributes)
{
//se calculeaza castigul informational
var ig = dtAttribute.ComputeInformationGain();
//se pastreaza atributul cu castigul informational
//cel mai mare
if (ig > maxIg)
{
maxIg = ig;
maxI = i;
}
i++;
}
dataset.Attributes[maxI].Entropy);
//se seteaza ca at ribut al nodului curent care nu este frunza
parent.Attribute = dataset.Attributes[maxI];
//pentru fiecare bin al atributului ales
List<Dataset> newDSs = new List<Dataset>();
foreach (var dtBin in parent.Attribute.Bins)
{
Console.WriteLine(dtBin.Label);
//se creeaza un nou dataset
var newDs = new Dataset
{
TargetAttribute = dataset.TargetAttribute,
Attributes = new List<DtAttribute>()
};
//pentru fiecare dataset nou creat se creeaza un
//nou set de atribute care nu il va mai contine pe
//atributul folosit acum
foreach(var upperDtAttribute in dataset.Attributes)
{
//sarim peste atributul folosit la pasul curent
if(upperDtAttribute.Label.Equals(parent.Attribute.Label))
continue;
newDs.Attributes.Add(new DtAttribute
{
Label = upperDtAttribute.Label
});
}
//pentru fiecare item din itemurile din bin
foreach (var tuple in dtBin.Items)
{
//pentru fiecare atribut ramas in dataset
foreach (var dtAttribute in dataset.Attributes)
{
//se gaseste atributul din noul set de date
// pentru a putea fi introduse itemurile
//corespunzatoare in el
foundAttribute= newDs.Attributes.FirstOrDefault(a =>
a.Label.Equals(dtAttribute.Label));
if (foundAttribute == null)
continue;
//se salveaza o copie a item -ului in atributul
//foundAtribute din noul dataset
Tuple<int, object, string> tuple1 = tuple;
foundAttribute.Items.Add(dtA ttribute.Items.
FirstOrDefault(t=> t.Item1 == tuple1.Item1));
}
}
var targetAttributeValues = new Dictionary<string,
List<Tuple<int, object, string>>> ();
foreach (var attr in newDs.Attributes)
{
foreach (var item in attr.Items)

49
{
var targetAttr = item.Item3;
if(!targetAttributeValues.ContainsKey(targetAttr))
targetAttributeValues.Add(targetAttr, new
List<Tuple<int, object, string>>());
else
{
targetAttributeValues[targetAttr].Add(item);
}
}
newDs.TargetAttribute Values = targetAttributeValues;
//se calculeaza numarul de valori distincte pentru
//valorile tar getului din noul set de date creat e
//important sa fie calculat acum pentru ca ajuta la
//stabilirea ulterioara a statutului de frunza a
//nodului curent din arbore
newDs.TargetAttributeValuesCount =
GetTargetAttributesValuesCount(newDs);
//dupa ce am fac ut toate dataseturi din binuri
//trebuie sa sortam din nou valorile pe atributele
//numerice si sa recalculam binuri pe setul de date
//nou creat
foreach (var dtAttribute in newDs.Attributes)
{
dtAttribute.SortItems();
dtAttribute.SplitIntoBins();
}
//daca nu mai am atribute sau nu mai am instante
//(itemi) in noul dataset creat
//fac o frunza cu cea mai frecventa valoare a
//etichetei din setul de d ate si o pun copil la
//nodul curent
newDSs.Add(newDs);
}
if (!passedChi2(dataset, newDSs))
{
foreach (var newDs in newDSs)
{
if (newDs.Attributes.Count == 0 ||
newDs.Attributes[0].Items.Count == 0)
{
parent.Childs.Add(new DtNode
{
Label = GetMostFrequentLabel(newDs),
IsLeaf = true
});
}
else
{
//daca nu, atunci trebuie sa fac apelul recursiv
//pentru ca setul de date apartine unui copil al
//nodului curent care poate la randul lui sa aiba
//copii si atu nci o sa adaug la copii nodului curent
//rezultatul apelului recursiv pentru setul de date noucreat
parent.Childs.Add(BuildDt(newDs));
}
}
}
else
{
parent.IsLeaf = true;
//in acest caz eticheta va fi data ca eticheta cea mai
//frecventa a targetului itemilor din dataset
parent.Label = GetMostFrequentLabel(dataset);
}
}
//de accea, tot timpul functia recursiva BuildDt va returna
//nodul creat la inceput fie ca e frunza incerc sa vad, f ie
//ca e nod parinte pentru alte ramuri din arbore
return parent;
}

50
public string EvaluateInstance(Dictionary< string,
object> instance)
{
var currentNode = Root;
while (!currentNode.IsLeaf)
{
var rule = currentNode.Attribute.Label;
var ruleValue = instance[rule];
var i = 0;
foreach (var dtBin in currentNode.Attribute.Bins)
{
if (RuleApplies(ruleValue, dtBin) ||
i == currentNode.Attribute.Bins.Count – 1)
{
currentNode = currentNode.Childs[i];
break;
}
i++;
}
}
return currentNode.Label;
}

4.1.4 Manual de utilizare

Când pornește ap licația, se deschide o fereastră pentru antrenarea setului de date , în care se
poate construi arborel e de decizie, se pot vizualiza performanțele obținute de algoritmul
implementat sau clasificarea instanțelor . Aceste funcționalități se pot vede a în Figura 10 . Pentru
a ilustra faptul că aplicația este generică, se poate rula pe mai multe seturi de date. Astfel când se
deschide această fereastră, se alege fișierul care conținele setul de date. După alegerea fișierului,
lista atributelor va fi popu lată cu numele atributelor și tipul acestora: Numeric sau Nominal. Din
combobox -ul de mai jos, unde este afișată lista atributelor Nominale, se poate alege atributul de
target. După selectarea atributului de target, se poate vizualiza arborele de decizie p e care
aplicația îl construiește, apasând butonul Show Decision Tree , lucru ilustrat în Figura 11. Avem
posibilitatea de a trunchia arborele prin marcarea checkbox -ului Prune decision tree . Pentru a
calcula măsurătorile specifice, cum sunt acuratețea, sensibilitatea, specificitatea și precizia, se
folosește metoda leave-one-out (utilizând butonul Leave -One-Out) sau k-fold-cross validation .
Pentru k-fold-cross validation se alege numărul de fold-uri, k, apoi se apasă butonul k-Fold
Validation . După ce am obținut valorile măsurătorilor, pentru a putea urmări evoluția acestora, le
putem reprezenta într -un grafic.

51

Figura 10 Construirea arborelui de decizie

52

Figura 11 Vizualizarea arborelui de decizie

Dacă se dorește clasificarea unei noi instanțe se apasă butonul Classify new instance din
Figura 10 . În acel moment se va deschide o fereastră prezentată î n Figura 12 în care se vor putea
introduce manual valori pentru fiecare atribut după care se va putea vizualiz a clasificarea dată .
Măsura prin care este calculată import anța asociată fiecărui atribut este câștigul informațional . Se
va afișa clasificator ul (arborele de decizie construit de către algoritm ).

53

Figura 12 Clasificarea unei instanțe noi

4.2 Rezultate experimentale

Pentru a testa performanța sistemului am folos it metoda leave-one-out și k-fold-cross –
validation .
Datele din baza de date Parkinson Disease [22] corespund a două categorii de pacienți ,
pacienți care suferă de boala Parkinson și pacienț i care nu suferă de boala Parkinson. Astfel
clasificatorul construit pentru acest set de date este un clasificator binar. Principalele metode de a
calcula performanțe le sistemelor care învață în cazul clasific atorilor binari sunt: Acuratețe a
(Accuracy ), Sensibilitatea (Sensitivity) , aceasta se găsește în literatură și sub denumirea de
Recall , Specificitatea (Specificity) și Precizia (Precision).
Vom prezenta formulele de calcul folosite pentru acest e măsurători specifice. Pentru
început vom explica notațiile folosite. TP (TruePositive) reprezintă numărul de instanțe pozitive
care au fost clasificate ca și pozitive. FP (FalseP ozitive ) este numărul de instanțe negative ca re
au fost clasificate ca și pozitive. TN (TrueNegative ) semnifică numărul de instanțe negative care

54
au fost clasificate ca și negative , iar prin FN ( FalseNegative ) se înțelege numărul de instanțe
pozitive care au fost clasificate ca și negative.
Acuratețe a (Accuracy) [22] calculează procentul de instanțe clasificate corect și se
calculează cu formula:

Sensibilitatea (Specificity/Recall) [22] este probabilitatea ca un test să indice "boala"
printre pacienț ii cu boală . Măsoară procentul de instanțe pozitive care sunt clasificate ca fiind
pozitive și are formula de calcul :

Specificitatea (Specificity ) [22] este fracțiunea celor care nu sunt boalnavi și care vor avea
un rezultat negativ al testului . Aceasta măsoară pr ocentul de instanțe negative care au fost
clasificate ca și negative. S e obține în felul următor:

Precizia (Precision ) [25] măsoară procentul de i nstanțe clasificate pozitiv din instantele
care sunt pozitive se determină după formula:

În Parkinson Speech Dataset with Multiple Types of Sound Recordings Data Set [22] este
prezentat un interes sporit pentru telediagnoza și telemoni torizarea bolii Parkinson prin utilizarea
eșantioanelor de voce. Astfel , cum am menționat mai sus, s-au colectat o mare var ietate de
mostre de voce, inclusiv vocale susținute, cuvinte și propoziții scurte dintr -un set de exerciții de
vorbire , de la persoane care suferă de boala Parkinson. Privind boala Parkinson, s -a descoperit că
vocalele susținute oferă mai multe informații discriminative decât cuvintele și propozițiile scurte .
Algoritm ii de clasificare care au fost folosiți în [22] sunt: cei mai apropiați k vecini (k-
nearest neighbor (k -NN)) și mașinile cu suport vectorial (Support Vector Machines – SVM).
Se poate observ a că în urma comparațiilor cu abordări le din literatu ră [22] raportate în
Tabelul 2, rezultatele noastre , în majoritatea cazurilor sunt mai bune . Rezultatele noastre pot fi
vizualizate în Tabelul 3.

55
Pentru început, vom explica notațiile folosite în literatur a: LOSO reprezintă leave -one-
subject -out și s-LOO este summarized -leave -one-out.

k Cross
Validation Accuracy
(%) Sensitivity
(%) Specificity
(%)
1 LOSO 53.57 49.62 57.12
s-LOO (1 -4) 42.50 30.00 55.00
s-LOO (2 -5) 52.50 45.00 60.00
s-LOO (3 -6) 50.00 55.00 45.00
s-LOO (all) 55.00 55.00 55.00
3 LOSO 54.04 53.27 54.81
s-LOO (1 -4) 55.00 45.00 65.00
s-LOO (2 -5) 60.00 55.00 65.00
s-LOO (3 -6) 42.50 55.00 30.00
s-LOO (all) 55.00 55.00 55.00
5 LOSO 54.42 53.65 55.19
s-LOO (1 -4) 55.00 45.00 65.00
s-LOO (2 -5) 57.50 65.00 50.00
s-LOO (3 -6) 50.00 70.00 30.00
s-LOO (all) 55.00 70.00 40.00
7 LOSO 53.94 54.04 53.85
s-LOO (1 -4) 65.00 55.00 75.00
s-LOO (2 -5) 62.50 60.00 65.00
s-LOO (3 -6) 42.50 65.00 20.00
s-LOO (all) 57.50 65.00 50.00
Central tendency metrics : 1: mean, 2: median, 3: trimmed mean (25% removed)
Dispersion metrics: 4: standard deviation, 5: mean absolute deviation, 6: interquatile range

Tabelul 2 Performanțe obținute în literatura pentru setul de date Parkinson Speech
Dataset With Multiple Types of Sound Recordings [22]

56

Am observa t o creștere mare a performanței dacă se efectuază operațiunea de trunchiere. Astfel, vom prezenta doar rezultate
relevante și pentru a sublinia marele avantaj adus de trunchiere vom pr ezenta rezultatele obținute cu ș i fără trunchiere.

Test
performanță Măsură Trun –
chiere Leave –
one-out K=1 K=2 K=3 K=4 K=5 K=6 K=7 K=8 K=9 K=10 Medie
Acuratețe IG NU 0.552 0.552 0.533 0.556 0.560 0.559 0.561 0.523 0.534 0.559 0.565 0.560
Acuratețe IG DA 0.620 0.620 0.608 0.643 0.625 0.625 0.627 0.604 0.618 0.627 0.627 0.622
Sensibilitate IG NU 0.478 0.478 0.461 0.501 0.462 0.464 0.461 0.451 0.467 0.488 0.481 0.471
Sensibilitate IG DA 0.576 0.576 0.478 0.516 0.486 0.489 0.478 0.461 0.480 0.502 0.494 0.487
Specificitate IG NU 0.526 0.526 0.580 0.560 0.559 0.552 0.572 0.532 0.524 0.526 0.550 0.548
Specificitate IG DA 0.755 0.755 0.738 0.770 0.763 0.761 0.774 0.745 0.755 0.749 0.759 0.75
Precizie IG NU 0.550 0.550 0.559 0.552 0.550 0.552 0.549 0.558 0.555 0.550 0.549 0.552
Precizie IG DA 0.665 0.665 0.645 0.691 0.671 0.670 0.677 0.642 0.659 0.664 0.668 0.665

Tabelul 3 Performan țele obținute

57 4.3 Extinderi posibile

Arborele de decizie obține performanțe comparabile cu cele din literatura, însă aceste
performanțe pot fi îmbunătățit e prin adă ugarea de noi funcționalități.
În eventualitatea existeței valorilor lipsă în setul de date, acestea pot fi înlocuite prin
construirea unui a lgoritm de aproximare pe baza celorlalte valori ale atributului respectiv .
O altă metodă de reducere a zgomotului și de completare a valorilor lipsă ar putea fi
transformarea atributelor clasice în atribute fuzzy, folosind funcții fuzzy care să caracterize ze
domeniul datelor de intrare. Performanța ar mai putea fi î mbunătățită prin folosirea unor
algoritmi de discretizare mai performanți sau a unor metode de trunchiere a arborelui mai
eficiente.
Se va avea în vedere utilizarea unor măsuri alte rnative pentru calcului importanței
atributelor în procesul de construire al arborelui de decizie (de exemplu, indexul Ginni) .

58 CONCLUZII

Această lucrare are ca obiectiv studierea performanțele sistemelor bazate pe arbori de
decizie în procesul asistării automate a diagnosticării medicale și în special în diagnosticarea
bolii Parkinson. În urma combinării mai multor tehnici, rezultatele experimentale obținute sunt
comparabile cu rezultate raportate în literatură, unele fiind chiar mai bune decât cele rapor tate.
În medicină, arborii de decizie sunt utilizați d e mai bine de 20 de ani și au ca scop luarea
celei mai bune decizii sau a unei decizii adecvate într-o situație limită, deoarece deciziile greșite
pot avea co nsecințe fatale. Medicina este un domeniu în care luarea deciziilor reprezintă o
problemă majoră. Deciziile luate trebuie să ia în considerare foarte multe lucruri, fiind important
să nu se omită nimic din ce ar putea influenț a rezultatul, deoarece orice amănu nt contează. Astfel
apare nevoia utilizării unor sisteme bazate pe arbori de decizie capabile să asiste specialiștii în
luarea deciziilor.
Metodele învățării automate bazate pe arbori de decizie au devenit instrumente de bază în
implementarea sistemelor complexe de inteligență artificială. Există numeroase centre de
cercetare și conferințe anuale având ca principal domeniu dezvoltarea și evaluarea
metodologiilor de învățare automată. Tendința generală de a crea sisteme informatice tot mai
independente și adaptabile face studiul învățării automate unul dintre cele mai atractive domenii
de cercetare în inteligența artificială.
În concluzie, se poate spune că inteligența artificială, învățarea automată și în special
arborii de decizie rămân în continuare un domeniu de cercetare ca re prezintă un real interes
pentru cercetătorii din ziua de azi. În contextul în care cantitatea de date acumulate devine din ce
în ce mai mare, iar nevoia de informație și cunoștințe necesare unui suport decizional de bună
calitate și util , în timp crește , cercetările din domeniul abordat pot să ducă la îmbunătățiri
semnificative în acest sens.

59
BIBLIOGRAFIE

[1] Azar Ahmad Taher, El-Metwally Shereen M. : “Decision tree classifiers for automated
medical diagnosis ”

[2] Bishop Christopher M. : “Pattern Recognition and Machine Learning ”,Springer, 2006

[3] Breiman Leo, Friedman J., Olshen R. A ., Stone C.: “Classification and regression trees ”,
Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, 1984

[4] Burduk Robert, Wozniak Michal : “Different Decision Tree Induction Strategies for a
Medical Decision Problem ”, Department of Systems and Computer Networks, Faculty of
Electronics, Wroclaw University of Technology Wybrzeze Wyspianskiego 27, 50 -370 Wroclaw,
Poland

[5] Elsayad Alaa. M., Elsalamony H. A.: “Diagnosis of Breast Cancer using Decision Tree
Models and SVM ”, International Journal of Computer Applications, Vol. 83, No 5, 2013

[6] Fayyad Usama M., Irani Keki B.: “On the Handling in Decision Tree of Continuous -Valued
Attributes Generation ”, Machine Learning, Vol. 8, 1992 , p. 87 -102

[7] Fieldsend Jonathan E.: “ Multi -Objective Supervised Learning ” – University of Exeter, Exeter,
Devon, EX4 4QF, UK

[8] Gan G., Ma C., Wu J.: “Data Clustering: Theory, Algorithms and Applications ”.
Philadelphia : SIAM, 2007

[9] Goetz Thomas : “About Thomas Goetz ”, The decision tree – Navigating the future of
healthcare, 2010, http://thedecisiontree.com/blog/thomas -goetz/

[10] Goetz Thomas : “The Decision Tree: How Smarter Choices Lead to Better Health ”, 2010,
http://www.wired.com/magazine/2010/01/ff_decisiontree/all/1

60
[11] Goetzhomas : “The Decision Tree: Taking Control of Your Health in the New Era of
Personalized Medicine ”, Rodale, 2010

[12] Grossberg Stephen, Abraham Ajith, Jain Lakhmi C., Palade Vasile : “The International
Journal of Hybrid Intelligent Systems (IJHIS) ”, IOS Press, The Netherlands , 2004,
http://www.softcomputing.net/ijhis/

[13] GÜLKESEN Kemal Hakan, KÖKSAL İsmail Türker, ÖZDEM Sebahat, SAKA
Osman“Prediction of prostate cancer using decision tree algorithm ”, 5th Turkish Medical
Informatics Congress, Turk J Med Sci, 2010, pag. 681 -686

[14] Hota H.S.: “ Identification of Breast Cancer Using Ensemble of Support Vector Machine
and Decision Tree with Reduced Feature Subset ”, International Journal of Innovative
Technology and Exploring Engineering, Vol. 3, Issue 9, 2014

[15] Learned -Miller Erik G.: “Supervised Learning and Bayesian Classification ”, Department of
Com puter Science University of Massachusetts, 2011

[16] MacKay, David J. C.: “Information Theory, Inference and Learning Algorithms ”.
Cambridge : Cambridge University Press, 2003

[17] Maimon Oded, Rokach Lior: “ Data Mining and Knowledge Discovery Handbook ”, Second
Edition, Springer Science+Business Media, p. 149 -174

[18] Mitchell om M.: “ Machine Learning ”, McGraw -Hill Science/Engineering/Math, 1997

[19] Mohri Mehryar , Rostamizadeh Afshin , Talwalkar Ameet: “Foundations of Machine
Learning , The MIT Press, 2012

[20] Nilsson Nils J.: “Introduction to Machine Learning ”, Robotics Laboratory, Department of
Computer Science, Stanford University, 1997

[21] Podgorelec Vili, Kokol Peter, Stiglic Bruno, Rozman Ivan – “Decision trees: an overview
and their use in medicine ”,University of Maribor, Slovenia, 2002

61
[22] Sakar Erdogdu, Isenkul M. Er dem, Sakar C.Okan, Sertbas A., Gurgen F., Delil S., Apaydin
H., Kursun O.: “ Collection and Analysis of a Parkinson Speech Dataset with Multiple Types of
Sound Recordings ”, IEEE Journal of Biomedical and Health Informatics, vol. 17(4), pp. 828 –
834, 2013

[23] Sutton R.S and Barto, A.G. : “Reinforcement Learning: An Introduction, Cambridge, MA:
MIT Press, 1998

[24] Taiwo Oladipupo Ayodele: “Types of Machine Learning Algorithms ”, New Advances in
Machine Learning, 2010

[25] Taylor John Robert : “An Introduction to Error Analysis: The Study of Uncertainties in
Physical Measurements ”, University Science Books, 1999

[26] Zorman M , Stiglic M M , Kokol P, Malcić I : “The limitations of decision trees and
automatic learning in real world medical decision making ” Journal of medical systems, 1997