Invatare automata Universitatea Politehnica Bucuresti Anul universitar 2008-2009
Adina Magda Florea
http://turing.cs.pub.ro/inva_09 si curs.cs.pub.ro
Invatare automata Universitatea Politehnica Bucuresti Anul universitar 2008-2009
Adina Magda Florea
http://turing.cs.pub.ro/inva_09 si curs.cs.pub.ro
Curs nr. 2
* Inductia arborilor de decizie
Invatarea prin arbori de decizie
Metoda ID3
Construirea arborelui minim
Cazuri speciale
Extinderea C4.5
Invatarea inductiva prin AD
* Vede invatarea ca achizitia cunostintelor structurate
Reprezentarea cunostintelor = arbori de decizie (AD)
Problema de invatare = clasificare
Invatare supervizata
Aplicatii posibile
Strategie = invatare batch (ne-incrementala)
AD se construieste pornind de la radacina spre frunze = Top Down Induction of Decision Tree
Exemple
Mediu – istorie a observatiilor
Profesor – expert in domeniu
ID3 (Quinlan)
* Univers de obiecte U descrise in termenii unei colectii de atribute {A}
Fiecare atribut masoara o caracteristica importanta a unui obiect oU
Domeniul de valori atribute DA= discret, simbolic (ulterior extins)
Fiecare obiect apartine unui clase dintr-o multime de clase mutual exclusive {Cl}
Se da setul de invatare (SI)
Problema = obtinerea unor reguli de clasificare / construirea unui AD care clasifica corect nu numai oSI dar si oU
ID3 (Quinlan)
* Structura iterativa – fereastra din SI
S-au gasit AD corecti in cateva iteratii pt 30 000 obiecte cu 50 atribute
Empiric s-a aratat ca iterativ se obtin arbori mai buni decat daca s-ar construi din tot SI
Utilizare AD
Reguli de decizie
ID3 (Quinlan)
* Metoda de constructie
C = multmea de obiecte / ex inv. din SI
A – atribut test cu valori / iesiri A1, .. An
[C1, ..Cn], cu Ci ={oC | A = Ai}
"divide-and-conquer"
Impartirea/expandarea AD se opreste cand toate Ci apartin unei aceleiasi clase
Se termina intotdeauna (in cazul cel mai nefavorabil, cate un obiect in fiecare clasa)
ID3 – Exemplul 1
* N adev mare placut ploaie 14 P fals normal cald nori 13 P adev mare placut nori 12 P adev normal placut soare 11 P fals normal placut ploaie 10 P fals normal racoare soare 9 N fals mare placut soare 8 P adev normal racoare nori 7 N adev normal racoare ploaie 6 P fals normal racoare ploaie 5 P fals mare placut ploaie 4 P fals mare cald nori 3 N adev mare cald soare 2 N fals mare cald soare 1 Vant Umiditate Temperatura Vreme Clasa Atribute No.
ID3 – Exemplul 1
* Vreme Umiditate Vant N P N P ploaie soare adev mare normal fals P nori Csoare = {1N,2N,8N,9P,11P} Cploaie = {4P,5P,6N,10P,14N} Cploaie = {3P,7P,12P,13P}
ID3 – Exemplul 2 (mai multe clase)
* No. Risk (Classification) Credit History Debt Collateral Income 1 High Bad High None $0 to $15k 2 High Unknown High None $15 to $35k 3 Moderate Unknown Low None $15 to $35k 4 High Unknown Low None $0k to $15k 5 Low Unknown Low None Over $35k 6 Low Unknown Low Adequate Over $35k 7 High Bad Low None $0 to $15k 8 Moderate Bad Low Adequate Over $35k 9 Low Good Low None Over $35k 10 Low Good High Adequate Over $35k 11 High Good High None $0 to $15k 12 Moderate Good High None $15 to $35k 13 Low Good High None Over $35k 14 High Bad High None $15 to $35k
ID3 – Exemplu mai multe clase
*
ID3 – Arbore minim
* Din acelasi SI se pot contrui diferiti AD (vezi exemplu curs 1)
Cum se poate obtine cel mai mic arbore (lama lui Occam) ?
= Cum selectez atributul din radacina unui arbore?
ID3 – Cum selectez A?
* C cu pP si nN
Se presupune ca:
(1) Orice AD corect va clasifica obiectele proportional cu reprezentarea lor in C
Un obiect arbitrar oC va fi clasificat:
P cu probabilitatea p/(p+n)
N cu probabilitatea n/(p+n)
(2) Cand un AD este utilizat pentru a clasifica obiecte, acesta intoarce o clasa
AD poate fi vazut ca o sursa a unui mesaj 'P' sau 'N' avand informatia necesara pentru a genera acest mesaj
Teoria informatiei ofera criteriul
* Teoria informatiei furnizeaza fundamentul matematic pentru masurarea continutului de informatie dintr-un mesaj
Un mesaj este privit ca o instanta dintr-un univers al tuturor mesajelor posibile
Transmiterea mesajului este echivalenta cu selectia unui anumit mesaj din acest univers
Teoria informatiei ofera criteriul
* Pentru un univers de mesaje
M = {m1, m2, ..., mn }
si o probabilitate p(mi) de aparitie a fiecarui mesaj, continutul informational I(M) al mesajelor din M se defineste astfel:
Selectia testului (atributului)
* C cu pP si nN
Continutul de informatie I(ADp,n) este
Selecteaza A in radacina; A {A1,…,Av}
Fie Ci cu piP si niN, i=1,v
Continutul de informatie pentru Ci este
I(ADpi,ni), i=1,v
Selectia testului (atributului)
* Dupa selectarea lui A in radacina, cantitatea de informatie necesara pentru a termina constructia arborelui este suma ponderata a continutului de informatie din toti subarborii
unde ponderea ramurii i este fractiunea de obiecte din C care apartin lui Ci ;
v este numarul de valori ale lui A
Selectia testului (atributului)
* Castigul informational al unui atribut A obtinut prin selectia acestuia ca radacina a arborelui de decizie este:
G(A) = I(ADp,n) – E(A)
Se selecteaza A cu castig informational maxim
Recursiv pentru a forma AD corespunzatori C1 … Cm
* Continutul de informatie
Cantitatea de informatie necesara pentru a termina constructia arborelui
Castigul informational
G(A) = I(Arb) – E(A)
Algoritm ID3
* caz 1 – ex inv lipsa caz 2 – atr inadecvate Bine = recunoaste functie ind-arbore (set-invatare, atribute, default) 1. daca set-invatare = vid atunci intoarce frunza etichetata cu default sau "Failure" 2. daca toate exemplele din set-invatare sunt in aceeasi clasa atunci intoarce o frunza etichetata cu acea clasa 3. daca atribute este vida atunci intoarce o frunza etichetata cu disjunctia tuturor claselor din set-invatare
4. selecteaza un atribut A, creaza nod pt A si eticheteaza nodul cu A 5. sterge A din atribute –> atribute’ 6. m = cea mai frecventa clasa (set-invatare) 7. pentru fiecare valoare V a lui A repeta - fie partitieV multimea exemplelor din set-invatare, cu valorea V pentru A - creaza nodV = ind-arbore (partitieV, atribute’, m) - creaza legatura nod A – nodV etichetata cu V sfarsit
Comments