Invatare automata Universitatea Politehnica Bucuresti Anul universitar 2008-2009
Adina Magda Florea
http://turing.cs.pub.ro/inva_09 si curs.cs.pub.ro
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
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
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)
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 (1)
AD cu complexitate mai mare decat este necesar (2)
Cazuri speciale: Zgomot
* Modificari necesare ID3 pt a trata zgomotul
(1) Trebuie sa poata lucra cu atribute inadecvate
(2) trebuie sa decida daca testarea unor atribute suplimentare va creste sau nu acuratetea predictiva a AD
Cum se realizeaza (2)
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
Cazuri speciale: Zgomot clase
* Solutia 1
G(A) > prag absolut sau relativ
suficient de mare pt a elimina atribute nerevante 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:
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.
Cazuri speciale: Zgomot atribute
* Cum se realizeaza (1)
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
Cazuri speciale: Extinderi C4.5
* Caz 3. Valori necunoscute de atribute
3.1 Valori de atribute lipsa in SI
Solutia 1
Atribuie valoarea cu cea mai mare frecventa
Solutia 2
Foloseste probabilitati pt a determia distributia de probabilitate a valorilor lui A
si alege valoarea cu cea mai mare probabilitate
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
A – clasa de invatat cu valori P sau N
Obtine AD' utilizat apoi pentru a clasifica obiectele din C-C' determin valoarea atributului A
Solutia 3 > Solutia 2 > Solutia 1
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 un obiect care are val A1 necunoscuta
A' = {A1', A2', A3'="nec"}
p1' = 1 p2'=2 p3'=1
n1'=2 n2'=2 n3'=0 E(A') = 0.84
Se selecteaza A'
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
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
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
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?"
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.48 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
Cazuri speciale: A cu multe valori
* Utilizeaza diverse metode de invatare pentru a forma clase din aceste valori sau a grupa aceste vaori in grupuri (clustere), clase care sa devina valori discrete (sau sa produca mai putine avlori) pentru atribut
Retele neurale
Comments