Post on 15-Jan-2016
description
Invatare automata
Universitatea Politehnica BucurestiAnul universitar 2010-2011
Adina Magda Floreahttp://turing.cs.pub.ro/inva_11 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 prin grupare (clsuterizare)
2
1. 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
3
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
4
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
5
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)
6
ID3 – Exemplul 1
7
No. Atribute Clasa
Vreme Temperatura Umiditate Vant
1 soare cald mare fals N
2 soare cald mare adev N
3 nori cald mare fals P
4 ploaie placut mare fals P
5 ploaie racoare normal fals P
6 ploaie racoare normal adev N
7 nori racoare normal adev P
8 soare placut mare fals N
9 soare racoare normal fals P
10 ploaie placut normal fals P
11 soare placut normal adev P
12 nori placut mare adev P
13 nori cald normal fals P
14 ploaie placut mare adev N
ID3 – Exemplul 1
8
Vreme
Umiditate Vant
N P N P
ploaiesoare
adevmare normal fals
P
noriCsoare = {1N,2N,8N,9P,11P}
Cploaie = {4P,5P,6N,10P,14N}
Cnori = {3P,7P,12P,13P}
ID3 – Exemplul 2 (mai multe clase)
9
No. Risk (Classification) Credit History Debt Collateral IncomeIncome
1 High Bad High None $0 to $15k2 High Unknown High None $15 to $35k3 Moderate Unknown Low None $15 to $35k4 High Unknown Low None $0k to $15k5 Low Unknown Low None Over $35k6 Low Unknown Low Adequate Over $35k7 High Bad Low None $0 to $15k8 Moderate Bad Low Adequate Over $35k9 Low Good Low None Over $35k10 Low Good High Adequate Over $35k11 High Good High None $0 to $15k12 Moderate Good High None $15 to $35k13 Low Good High None Over $35k14 High Bad High None $15 to $35k
ID3 – Exemplu mai multe clase
10
Income?
High risk Credit history?
Low risk Moderate riskDebt?
Credit history?
Low riskHigh risk Moderate risk
Moderate riskHigh risk
$0K-$15K
$15K-$35K
$Over 35K
Unknown Bad Good
High Low
UnknownBad
Good
ID3 – Arbore minim
11
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?
12
C cu pP si nNSe 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
13
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:
I M p mii
n( ) ( )
1
14
log2(p(mi))
Selectia testului (atributului)
15
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
np
n
np
n
np
p
np
pADI np
22, loglog)(
Selectia testului (atributului)
16
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
)()( ,1
nipi
v
i
ii ADInp
npAE
Selectia testului (atributului)
17
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
Calcul G(A) pt Ex 1
18
14 exemple, 9P, 5N I(ADp,n) = ???? = 0.940 bits
vreme soare - 2P, 3N I(ADp1,n1) = 0.971 nori - 4P, 0N I(ADp2,n2) = ? ploaie - 3P, 2N I(ADp3,n3) = ?
E(vreme) = ??? = 0.694 bits G(vreme) = 0.940-0.694= 0.246 bits G(temperatura) = 0.029 bits G(umiditate) = 0.151 G(vant) = 0.048 bits
14
5log
14
5
14
9log
14
922
)(14
5)(
14
4)(
14
53,32,21,1 npnpnp ADIADIADI
0
0.971
Csoare = {1N,2N,8N,9P,11P}
Cploaie = {4P,5P,6N,10P,14N}
Cnori = {3P,7P,12P,13P}
Generalizare la mai multe clase Continutul de informatie
Cantitatea de informatie necesara pentru a termina constructia arborelui
Castigul informational
G(A) = I(Arb) – E(A)
)(log*)()( 2
1
CiClpCClpArbIv
ii
19
v
ii
i CIC
CAE
1
)(||
||)(
Algoritm ID3
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 –> atribute1
6. m = cea mai frecventa clasa (set-invatare) 7. pentru fiecare valoare V a lui A repeta
- fie partitieV multimea exemplelor dinset-invatare, cu valorea V pentru A
- creaza nodV = ind-arbore (partitieV, atribute1, m)- creaza legatura nod A – nodV etichetata cu V
sfarsit
20
caz 1 – ex inv lipsa
caz 2 – atr inadecvate
Bine = recunoaste
Acuratetea predictiva a ID3 Acuratetea predictiva = cat de bine clasifica un
AD obiecte necunoscute
Experimente 1.4 mil pozitii joc tabla sah descrise de 49 atribute
715 obiecte (65% si 35%) AD cu 150 noduri SI – fereastra cu 20% din cele 715 obiecte AD care
clasifica corect 84% din restul obiectelor 1987 obiecte AD cu 48 noduri
SI – fereastra cu 20% din obiecte AD clasifica corect 98% din restul obiectelor
21
Complexitate
In fiecare nod cu exceptia frunzelor trebuie aflat G (castig informational) pt fiecare atribut A
G depinde de valorile pi si ni pentru fiecare valoare Ai a lui A fiecare obiect din C trebuie investigat (clasa, valoare A)
O(|C| * |A|) , |A| - nr atribute Pentru fiecare iteratie, complexitatea ID3 O(|C| * |A| * |AD|) , unde |AD| - numar de noduri
interne AD
22
Cazuri speciale
Caz 1. Nu exista obiecte o C pentru care A=Aj
ID3 eticheteaza frunzele cu "null" sau "Failure" – deci nu clasifica in aceste noduri
Solutie Generalizeaza si se atribuie frunzei clasa cu cea
mai mare frecventa de aparitie in C (cea mai frecventa)
23
Cazuri speciale: Zgomot
Caz 2. Informatia din SI este afectata de zgomot Zgomot
valori de atribute ale obiectelor din C afectate de zgomot
clasificare incorecta ale obiectelor din C Erorile din C (zgomotele) pot duce la 2
probleme: atribute inadecvate (a) AD cu complexitate mai mare decat este
necesar (b)
24
Cazuri speciale: Zgomot
Modificari necesare ID3 pt a trata zgomotul (a) Trebuie sa poata lucra cu atribute inadecvate (b) trebuie sa decida daca testarea unor atribute
suplimentare va creste sau nu acuratetea predictiva a AD
Cum se realizeaza (b) Este un atribut relevant? Fie A cu valori aleatoare Alegerea lui A pt a creste arborele va aduce un castig
informational mare (cu exceptia cazului in care procentul de obiecte P din fiecare Ci este exact aceasi cu procentul de obiecte P din C) – numai aparent
25
Cazuri speciale: Zgomot clase
Solutia 1 G(A) > prag absolut sau relativ suficient de mare pt a elimina atribute nerelevante
elimina si atribute relevante pt cazul fara zgomot
Solutia 2 Testul pt independenta stohastica
Ci cu pi P si ni N
Daca valoarea Ai a lui A este irelevanta pt clasa unui obiect din C, valoarea estimata pi
' a lui pi este:
26
2
np
nppp ii
i
'
Cazuri speciale: Zgomot clase
Daca pi' si ni' nu sunt foarte mici atunci se poate utiliza o expresie ce aproximeaza testul pentru a determina increderea in relevanta lui A
Se elimina atributele pentru care increderea in relevanta nu este foarte mare.
27
'
2'
1'
2' )()(
i
iv
i i
i
n
nn
p
pp
2
Cazuri speciale: Zgomot atribute
Cum se realizeaza (a) Trebuie produsa o eticheta pt Ci dar obiectele nu
sunt in aceeasi clasa
Solutia 1 Se utilizeaza notiunea de apartenenta la o clasa
cu o anumita probabilitate, de ex. pi/(pi+ni)
Solutia 2 Eticheteaza cu clasa cea mai numeroasa: P daca
pi>ni, N daca pi<ni, oricare (P sau N) daca pi=ni
28
Cazuri speciale: Extinderi C4.5
Caz 3. Valori necunoscute de atribute3.1 Valori de atribute lipsa in SISolutia 1 Atribuie valoarea cu cea mai mare frecventa
Solutia 2 Foloseste probabilitati pt a determia distributia de
probabilitate a valorilor lui A in C in functie de apartenenta la o clasa
si alege valoarea cu cea mai mare probabilitate29
)(
)()|(
Pclasaprob
PclasaAAprobPclasaAAprob i
i
Cazuri speciale: atribute lipsa SI
Solutia 3
Construieste un AD pt a invata valorile atributelor lipsa C'C, C' cu valori pt A In C' clasa este privita ca un atribut cu valori P sau N Valorile lui A – clasele de invatat Obtine AD' utilizat apoi pentru a clasifica obiectele din
C-C' determin valoarea atributului A Solutia 3 > Solutia 2 > Solutia 1
30
Cazuri speciale: atribute lipsa SI
Solutia 4 Adauga o noua valoare "nec" Rezultate anormale A={A1, A2} C A1 p1=2 n1=2 A2 p2=2 n2=2 E(A)=1 A' identic cu A cu exceptia unui obiect care are val 'nec' pt
A1 A' = {A1', A2', A3'="nec"} p1' = 1 p2'=2 p3'=1 n1'=2 n2'=2 n3'=0 E(A') = 0.84 Se selecteaza A'
31
Cazuri speciale: atribute lipsa SI
Solutia 5 La evaluarea castigului informational, obiectelor
cu valori necunoscute li se atribuie valori distribuite peste valorile lui A proportional cu frecventa relativa a acestor valori in C
G(A) este calculat ca si cum valoarea lui pi ar fi data de: pi+pi * Ri
ni+ni * Ri
Valorile necunoscute nu pot decat sa scada castigul informational
32
jjj
iii np
npR
)(
Cazuri speciale: atribute lipsa in clasificare
Caz 3. Valori necunoscute de atribute
3.2 Valori de atribute lipsa in clasificare
Valoarea lui A este necunoscuta in obiect Se exploreaza toate alternativele A1,…, Av si se transmite pe
fiecare ramura un jeton AiRi
daca sunt mai multe jetoane pe o frunza, se insumeaza Rezultatul clasificarii este clasa cu cea mai mare valoare
33
jjj
iii np
npR
)(
Cazuri speciale: Extinderi C4.5
Caz 4. Atribute cu multe valori A1 .. An - f multe valori simbolice sau valori numerice /
continue, sau chiar valori aleatoare Castig mare arbore cu 1 nivel
Solutia 1 (valori numerice) Partitionez in intervale (Ai+Ai+1)/2, fiecare interval o
valoare
Solutia 2 (valori numerice)
Pt fiecare Ai, i=1,m imparte obiectele in (-, Ai] si
(Ai, + ) partitie Pi
Pentru fiecare Pi calculeaza castigul informational si selecteaza partitia cu castig informational maxim
34
Cazuri speciale: A cu multe valori
Solutia 3 (valori simbolice) Utilizeaza Informatia de separare = cantitatea de
informatie necesara pentru a determina valoarea unui atribut A intr-un set de invatare C
Fie PA,C distributia de probabilitate a valorilor lui A
Informatia de separare masoara continutul informational al raspunsului la intrebarea "Care este valoarea atributului A?"
35
np
np
np
npAISep ii
v
i
ii
21
log)(
)||
||,...,
||
||( 1
C
A
C
AP v
AC
Cazuri speciale: A cu multe valori
Dar GR poate sa nu fie intotdeauna definita (ISep=0) sau sa tinda sa favorizeze ISep mici
Selecteaza dintre atributele cu G(A) mare (peste medie) acelea cu GR(A) cel mai bun
G(vreme) = 0.246 bits G(temperatura) = 0.029 bits G(umiditate) = 0.151 bits G(vant) = 0.048 bits ISep(vreme) = 1.578, ISep(umiditate) = 1 bit GR(vreme) = 0.246/1.578=0.156 GR(umiditate) = 0.151/1.0 = 0.151
36
)(
)()(
AISep
AGAGR sa fie cat mai mare
Cazuri speciale: A cu multe valori
Utilizeaza diverse metode de invatare pentru a forma clase din aceste valori sau a grupa aceste valori in grupuri (clustere), clase care sa devina valori discrete (sau sa produca mai putine valori) pentru atribut
Retele neurale
37
2. Invatarea conceptelor din exemple prin clusterizare
Generalizare si specializare
Exemple de invatare1. (galben piram lucios mare +)
2. (bleu sfera lucios mic +)
3. (galben piram mat mic +)
4. (verde sfera mat mare +)
5. (galben cub lucios mare +)
6. (bleu cub lucios mic -)
7. (bleu piram lucios mare -)
38
Invatarea conceptelor prin clusterizare
nume concept: NUMEparte pozitiva
cluster: descriere: (galben piram lucios mare) ex: 1
parte negativaex:
nume concept: NUMEparte pozitiva
cluster: descriere: ( _ _ lucios _) ex: 1, 2
parte negativaex:
39
1. (galben piram lucios mare +)
2. (bleu sfera lucios mic +)
3. (galben piram mat mic +)
4. (verde sfera mat mare +)
5. (galben cub lucios mare +)
6. (bleu cub lucios mic -)
7. (bleu piram lucios mare -)
Invatarea conceptelor clusterizare
nume concept: NUME
parte pozitiva
cluster: descriere: ( _ _ _ _)
ex: 1, 2, 3, 4, 5
parte negativa
ex: 6, 7
40
suprageneralizare
1. (galben piram lucios mare +)
2. (bleu sfera lucios mic +)
3. (galben piram mat mic +)
4. (verde sfera mat mare +)
5. (galben cub lucios mare +)
6. (bleu cub lucios mic -)
7. (bleu piram lucios mare -)
Invatarea conceptelor clusterizare
nume concept: NUME
parte pozitiva
cluster: descriere: (galben piram lucios mare)
ex: 1
cluster: descriere: ( bleu sfera lucios mic)
ex: 2
parte negativa
ex: 6, 7
41
1. (galben piram lucios mare +)
2. (bleu sfera lucios mic +)
3. (galben piram mat mic +)
4. (verde sfera mat mare +)
5. (galben cub lucios mare +)
6. (bleu cub lucios mic -)
7. (bleu piram lucios mare -)
Invatarea conceptelor clusterizare
nume concept: NUME
parte pozitiva
cluster: descriere: ( galben piram _ _)
ex: 1, 3
cluster: descriere: ( _ sfera _ _)
ex: 2, 4
parte negativa
ex: 6, 7
42
1. (galben piram lucios mare +)
2. (bleu sfera lucios mic +)
3. (galben piram mat mic +)
4. (verde sfera mat mare +)
5. (galben cub lucios mare +)
6. (bleu cub lucios mic -)
7. (bleu piram lucios mare -)
Invatarea conceptelor clusterizare
nume concept: NUME
parte pozitiva
cluster: descriere: ( galben _ _ _)
ex: 1, 3, 5
cluster: descriere: ( _ sfera _ _)
ex: 2, 4
parte negativa
ex: 6, 7
43
1. (galben piram lucios mare +)
2. (bleu sfera lucios mic +)
3. (galben piram mat mic +)
4. (verde sfera mat mare +)
5. (galben cub lucios mare +)
6. (bleu cub lucios mic -)
7. (bleu piram lucios mare -)
A daca galben sau sfera
Invatare prin clusterizare
1. Fie S setul de exemple
2. Creaza PP si PN
3. Adauga toate ex- din S la PN (*vezi coment) si elimina ex- din S
4. Creaza un cluster in PP si adauga primul ex+
5. S = S – ex+
6. pentru fiecare ex+ din S ei repeta
6.1 pentru fiecare cluster Ci repeta
- Creaza descriere ei + Ci
- daca descriere nu acopera nici un ex-
atunci adauga ei la Ci
6.2 daca ei nu a fost adaugat la nici un cluster
atunci creaza un nou cluster cu ei
sfarsit
44