arbori de decizie c7

24
1 Modele decizionale grafice -arbori de decizie- Semnificatie diferita: Invatarea automata si evaluarea datelor (data mining): arborele de decizie este o model de clasificare in care functia de invatare este reprezentata de un arbore; se utilizeaza pentru clasificarea unor obiecte descrise de atribute. Se mai numeste arbore de clasificare – descrie date. Analiza Deciziilor: arborele de decizie reprezinta un model grafic al deciziilor (in conditii de incertitudine) si a consecintelor posibile ale acestora, inclusiv al starilor posibile ale mediului; se utilizeaza pentru a identifica startegia optima in raport cu un criteriu dat. Se mai numeste si diagrama de decizie. vom retine denumirea arbore de clasificare pentru primul si diagrama de decizie pentru al doilea

Upload: patricia-ghita

Post on 31-Dec-2015

332 views

Category:

Documents


9 download

DESCRIPTION

Arbori de decizie

TRANSCRIPT

Page 1: Arbori de Decizie c7

1

Modele decizionale grafice-arbori de decizie-

• Semnificatie diferita:

• Invatarea automata si evaluarea datelor (data mining): arborele de decizie este o model de clasificare in care functia de invatare este reprezentata de un arbore; se utilizeaza pentru clasificarea unor obiecte descrise de atribute. Se mai numeste arbore de clasificare – descrie date.

• Analiza Deciziilor: arborele de decizie reprezinta un model grafic al deciziilor (in conditii de incertitudine) si a consecintelor posibile ale acestora, inclusiv al starilor posibile ale mediului; se utilizeaza pentru a identifica startegia optima in raport cu un criteriu dat. Se mai numeste si diagrama de decizie.

• vom retine denumirea arbore de clasificare pentru primul si diagrama de decizie pentru al doilea

Page 2: Arbori de Decizie c7

2

Arbori de clasificare• Reprezinta una din metodele cele mai utilizate in clasificare si

predictie• In raport cu retelele neuronale poate fi usor interpretat ca o

reprezentare grafica a unor reguli – mult mai accesibil utilizatorului

• Definitie, concepte, elemente componente • Constructia arborelui – invatare supervizata

– procedura generala de constructie– selectarea atributelor– algoritmul ID3

• Utilizarea arborelui de decizie

Page 3: Arbori de Decizie c7

3

Definitii, elemente componente

Fie S=(S1,…Sn) setul exemplelor de antrenare, Si o instanta caracterizata de (x,y): x setul atributelor si y – clasa (categorie)

Observatie: y atribut discret.

Definitie: clasificarea reprezinta taskul de invatare a unei functii “f” care mapeaza fiecare set x unei clase predefinite y

• O tehnica de invatare reprezinta o metoda de construtie a modelului de clasificare dintr-un set de date de invatare

• Tehnici de invatare: clasificatorul Bayes, arbori de clasificare, retele neurale, etc.

Page 4: Arbori de Decizie c7

4

Definitii, elemente componente

• Metoda generala de rezolvare a problemei clasificarii:

• Procedura de tip inductiv – Inferenta inductiva: o proprietate adevarata pentru o submultime

de obiecte dintr-o clasa este adevarata pentru toate obiectele din acea clasa P(a ),P(a ),...,P(a )

( x)P(x)1 2 n

Page 5: Arbori de Decizie c7

5

Definitii, elemente componente

• Performanta clasificatorului:• precizia:

• eroarea (rata erorii)

– erori de antrenare – pentru setul exemplelor de antrenare – eroare aparenta

– erori de generalizare – pentru setul exemplelor de testare – eroare de test: reprezinta eroarea asteptata a modelului in raport cu instantele ce urmeaza a fi clasificate

Page 6: Arbori de Decizie c7

6

Arborele de clasificare• Defintie: arborele de decizie este

o metoda de clasificare in care functia target este reprezentata de un arbore constind din noduri si arce directionate

• Elemente componente:• noduri decizionale - atribute

– noduri radacina– noduri decizionale interne

• noduri frunza - clasa• arce – valori ale atributelor• Analogie cu diagnosticarea:

achizitia secventiala a informatiei – nodurile intermediare,

nodul frunza: ipoteza cea mai probabila corespunzatoare valorilor observate ale caracteristicilor

Page 7: Arbori de Decizie c7

7

Constructia arborelui de clasificareProcedura generala propusa de Hunt

• Procedura de invatare de tip inductiv : daca o ipoteza aproximeaza bine atributul target peste un set suficient de exemple, va aproxima bine atributul target si peste alte exemple necunoscute: de ex., o ipoteza este H=( rosu, fam, C2)

• Procedura primeste la intrare un set de inregistrari (exemple)- S=(x1,x2,..,xn,ci) si inlocuieste nodurile frunza cu noduri test, partitionind setul exemplelor in subseturi din ce in ce mai omogene

• Fie Sr=(x1,x2,..,xn,ci) setul de exemple asociat nodului r, atunci:– daca toate exemplele asociate nodului r apartin aceleiasi

clase, atunci nodul r ramine nod frunza etichetat cu clasa respectiva

– daca setul apartine mai multor clase alege atributul care urmeaza a fi testat in nodul respectiv si partitioneaza exemplele dupa valorile sale; un nod copil este creat pentru fiecare valoare a atributului si atribuie nodului partitia corespunzatoare valorii respective

– algoritmul continua pina ce fiecare combinatie a valorilor atributului este prezenta in setul de invatare si fiecare combinatie are o clasa unica

• conditii suplimentare: – daca multimea Sr=Ø, nodul este declarat nod frunza etichetat

cu clasa nodului parinte cu cele mai multe instante– daca Sr are valorile atributelor identice si clasele diferite, nodul

este declarat nod frunza si I se taribuie clasa cu cele mai multe exemple

Tip org

Page 8: Arbori de Decizie c7

8

Constructia arborelui de clasificare

Probleme:• selectarea atributului care partitioneaza cit mai omogen setul de

date• oprirea procedurii de crestere in adincime a arborelui:

– cresterea in adincime a arborelui pina ce toate exemplele de antrenare au fost clasificate

– oprirea inainte a cresterii• atribute numerice: transformarea variabilei continue in variabila

discreta• valoare lipsa a unui atribut in setul de date

– se atribuie exemplului valoarea cu cele mai multe realizari in cadrul exemplelor asociate nodului

– se atribuie valoarea cu cele mai multe realizari in cadrul clasei careia ii apartine exemplul

– se atribuie probabilitati pe baza frecventelor valorilor atributului si exemplele cu valori lipsa se distribuie valorilor atributului proportional cu probabilitatea fiecaruia

Page 9: Arbori de Decizie c7

9

Constructia arborelui de clasificareSelectarea atributelor – masura impuritatii

• masurile utilizate in alegerea atributului ( a celei mai bune partitionarii) se definesc in termenii distributiei de probabilitate a claselor, in setul de exemple, inaintea si dupa partitionarea in functie de atribut; in termenii arborelui: se bazeaza pe gradul impuritatii nodurilor copil

• de exemplu:– distributia de probabilitate a

claselor inaintea partitionarii dupa atributul culoare: (0.54 0.45)

– dupa partitionare:– (0.66 0.34) (0.4 0.6) gradul

impuritatii a scazut• un nod cu ditributia (1 0) are

impuritate 0, un nod cu distributia (0.5 0.5) are impuritate maxima

• inaintea partitionarii

• dupa partitionare

Page 10: Arbori de Decizie c7

10

Constructia arborelui de clasificareSelectarea atributelor – masura impuritatii

• Masurile impuritatii: – entropia– indicele Gini– eroarea de clasificare

• Presupunem setul exemplelor S partitionat in N subseturi (clase) disjuncte S1,..,Sn astfel incit:

=S pentru fiecare i≠j

probabilitatea ca o instanta sa apartina clasei j este:

• pe baza probabilitatii estimate se definesc cele trei masuri ale impuritatii

Page 11: Arbori de Decizie c7

11

Constructia arborelui de clasificareSelectarea atributelor – entropia

• Entropia- masura utilizata in teoria informatiei pentru a caracteriza impuritatea (sau puritatea) unui set de exemple

• Presupunem cazul binar: setul de exemple, S, contine doua tipuri de date- doua clase

• Definitie: entropia setului S raportata la clasificarea binara este data de relatia:

• Unde

• Prin conventie

• Generalizind pentru n clase entropia setului S este:

• Exemplu: consideram multimea S, formata din 11 instante, din care 6 calsei C1 si 5 clasei C2. Entropia setului S relativ la aceasta clasificare este:

• Se poate spune ca entropia masoara incertitudinea cu privire la apartenenta unui exemplu la o clasa

Page 12: Arbori de Decizie c7

12

Constructia arborelui de clasificareSelectarea atributelor – entropia

• Entropia setului de exemple:

Fie atributul A cu dom(A)=(a1,..,am) si partitiile corespunzatoare ale setului de exemple: S=(Sa1,..,Sam)

• Entropia medie a setului de exemple dupa partitionarea functie de valorile atributului este:

unde

Sai = setul de exemple corespunzatoare valorii ai

naij= numarul de exemple corespunzatoare valorii ai si clasei j

nai= numarul total de exemple corespunzatoare valorii ai

• Exemplu:

Page 13: Arbori de Decizie c7

13

Constructia arborelui de clasificareSelectarea atributelor –indicele Gini

• Indicele Gini al setului de exemple S este dat de relatia

• Daca partitonam setul de exemple dupa valorile atributului A, indicile gini al setului de exemple devine:

• pentru cazul binar:– daca p1=p2 - exemplele uniform distribuite in

cele doua clase, indicile gini are valoarea maxima: Gini(S)=0.5

– daca exemplele apartin aceleiasi clase: Gini(S)=0

– altfel valoarea indicelui cuprinsa intre 0 si 0.5

• Acelasi exemplu:

Page 14: Arbori de Decizie c7

14

Selectarea atributelor –eroarea de clasificare

• Presupunem cazul binar: clasele C1, C2, cu probabilitatile p1, (1-p1).

• probabilitatea clasificarii gresite este p1, daca instanta apartine clasei C2 si (1-p1) daca instanta apartine clasei C1.

• Eroarea de clasificare:

sau

• generalizind

• presupunem atributul A, eroarea de clasificare este data de:

• unde

• Observatie. Raportul reprezinta

probabilitatea conditionata a ipoteei conform careia exemplul apartine clasei j atunci cind a fost observata valoarea ai a atributului A:

• rezulta:

Page 15: Arbori de Decizie c7

15

Constructia arborelui de clasificareSelectarea atributelor – criteriul de optim

• Functia cistigPresupunem Sr setul de exemple asociat nodului r, atributul A, dupa valorile caruia se face partitia;Notam Imp(.) masura impuritatii – poate fi oricare din masurile definite mai sus, atunci functia cistig este data de relatia:

in termenii arborelui de decizie, functia cistig masoara diferenta dintre impuritatea nodului parinte, inainte de ramificare si impuritatea nodurilor copil, dupa ramificare.

• Criteriul de optim pentru alegerea atributului care urmeaza sa fie testat in nodul parinte si dupa ale carui valori va fi ramicat este

• deoarece imp(Sr) este aceiasi pentru toate atributele se poate scrie:

Page 16: Arbori de Decizie c7

16

Constructia arborelui de clasificareAlgoritmul de selectare a unui atribut

• pas 1. Partitioneaza multimea exemplelor dupa fiecare atribut in parte

• pas 2. Calculeaza cistigul pentru fiecare atribut in parte si alege atributul care maximizeaza functia cistig

• exemplu: presupunem baza de date din tabel

• pas 1. • p• p

• pas 1

• observatie• pas 2

Page 17: Arbori de Decizie c7

17

Constructia arborelui de clasificareCriterii de oprire a procedurii

• oprirea inaintea clasificarii tuturor exemplelor de invatare: fenomenul underfitting (sub-antrenare)

• oprirea cind toate exemplele au fost clasificate – overfitting (supra-invatare)

• cauzele overfitting-ului: prezenta zgomotelor, lipsa unor exemple reprezentative pentru functia target, numar mic de exemple de invatare

• efecte: rata erorii de invatare mica→specializare excesiva→capacitate de predictie mica

• proceduri de evitare: postpruning - prin inlocuirea subarborilor care prezinta zgomote sau exceptii cu:– un nod frunza a carei clasa este determinata de clasa celor mai

multe exemple asociate nodului respectiv– cu cel mai utilizat subarbore

Page 18: Arbori de Decizie c7

18

Constructia arborelui de clasificareCriterii de oprire a procedurii

• REantr=0.18

REtest=0.50

• REantr=0.27

REtest=0.25

Page 19: Arbori de Decizie c7

19

Constructia arborelui de decizie-algoritmul ID3-

Function ID3 (A, C, S)begin

daca S=vida atunci intoarce un singur nod cu eticheta failurealtfel daca toate elementele lui S in aceiasi clasa atunci intoarce un sigur nod frunza etichetat cu aceea clasa altfel daca A=vida atunci intoarce nod frunza etichetat cu disjunctia tuturor claselor din S

altfel begin selecteaza atributul a cu cel mai mare Gain(a) si intoarce arbore cu

nod radacina etichetat a si ramuri etichetate cu valorile ai ale lui a sterge a din multimea atributelor A pentru fiecare valoare ai atributului a begin creeaza partitia (Si) corespunzatoare valorii ai a atributului a

intoarce arbore apelind ID3(A,C,Si) end

endend

Input: (A: multimea atributelor; C: multimea claselor; S: multimea exemplelor de invatare)

Page 20: Arbori de Decizie c7

20

Constructia arborelui de decizie-algoritmul ID3-

• Strategia utilizata este de tip top-down fara intoarcere (greedy search).• Masura impuritatii este entropia

• Algoritmul:• Dindu-se setul de exemple S, si clasele (deciziile), c, corespunzatoare, atunci:

• 1. Alege nodul radacina atributul A cu cel mai mare cistig informational relativ la S

• 2. Pentru fiecare valoare v pe care A o poate lua, construieste o ramura din acel nod

• 3. Pentru fiecare ramura din A corespunzatoare valorii v, calculeaza Sv.

- daca Sv contine exemple numai dintr-o categorie c, atunci pune c nod frunza (clasa).

– altfel, exclude atributul A din setul atributelor si pune un nod nou in arborele de decizie, unde noul atribut care va fi testat este cel cu cel mai mare cistig informational raportat la Sv (observatie: nu la S). Cu acest nou nod procedura se reia de la pasul 2 cu S inlocuit cu Sv.

Procedura opereaza recursiv pina cind:

• fiecare atribut a fost deja inclus de-a lungul caii de la radacina la acel nod - A= vida

sau • exemplele de invatare asociate nodului au toate aceiasi clasa atribuita (toate exemplele au fost perfect clasificate)

Page 21: Arbori de Decizie c7

21

Constructia arborelui de decizie-algoritmul ID3-

• 1. alegerea nodului radacina: A2

• 2. pentru fiecare valoare a atributului se construieste un nod

• 3. determina multimea exemplelor Sv asociate nodului:

– pentru valoarea “joasa” si “medie” multimea exemplelor apartine aceleiasi clase: nod frunza

– pentru valoarea “mare” sterge din lista atributelor A2 si reia procedura pentru setul exemplelor ramase SA2=M=(1-C1, 2-C2, 4-C1, 8-C2)

• alege atributul (din atributele ramase) cu cea mai mica entropie

• Enmed(SA2=M, A3)=0• Enmed(SA2=M, A1)=0.5

• se alege atributul A3 (se reia procedura)

• Stop - toate exemplele clasificate

A2

j m M

Page 22: Arbori de Decizie c7

22

Utilizarea arborelui de decizie• extragerea de reguli

– postpruning: eliminarea valorilor atributelor care nu influenteaza decizia (concluzia);

• clasificarea unor instante necunoscute

de exemplu, instanta:

Page 23: Arbori de Decizie c7

23

Utilizarea arborelui de decizie

• Procedura de eliminare a valorilor care nu influenteaza concluzia

• pas 1. Tabelul de contingenta:

• pas 2. Alegerea criteriului pentru determinarea dependentei concluziei de valoarea atributului din premisa se face pe baza frecventei estimate maxime:

EF=max(eij), unde eij=

criteriul ( ) se alege astfel: – pentru EF>10 → Chi-patrat

– pentru → corectia pentru continuitate a lui Yates

– pentru EF< 5 → testul exact al lui Ficher

• pas 3. Se alege din tabelul distributiei functiei valoarea functie de gradul de libertate g l=(r-1)(c-

1) si a unui factor de importanta dorit si se compara cu valoarea calculata la punctul 2, daca:

• atunci concluzia este dependenta

• atunci concluzia este independenta

• presupunem regula :

• pas 1. Se construieste tabelul:

se calculeaza frecventele estimate

• pas 2. Intrucit EF=max(eij)=10 se alege corectia lui Yates:

• pentru gl=1 rezulta intrucit concluzia nu este dependenta de valoarea atributului.

Page 24: Arbori de Decizie c7

24

Concluzii

• Anumite clase nu testeaza toate proprietatile unui anumit obiect

• Pentru aceeasi multime de exemple, exista mai multi arbori de decizie care le clasifica corect

• Algoritmul ID3 – alege cel mai simplu arbore de decizie care acopera

toate exemplele din multimea initiala– este robust la erori in date (lipsa valorii unui atribut,

erori instanta-clasa)