Extras din curs
Inductia automata a arborilor de
clasificare (de decizie)
Arbore de clasificare - componente
- Noduri neterminale (atribute), arce (valori
ale atributelor) si noduri terminale (etichete
ale claselor).
- Atributele pot fi binare, multivaloare sau
continue.
- Numarul claselor este, de obicei redus.
Exemplu
Durere
temp tuse
Atribute si etichete de clase binare
atribute
Valori de atribute
Etichete de clase
Arbori de clasificare si expresii booleene
h=(~f3^f2) ½ f3^f1^~f2
Nu exista nici o legatura intre complexitatea
expresiei si cea a arborelui!
(~F^~H)v(~F^H^J)v(F^~G^K)v(F^G)
Arbore complex si expresie simpla
(F^G)v(H^J)
Arbore de clasificare real
Alt arbore de clasificare real
Inductia automata a arborilor – instante
de instruire
- Se utilizeaza instante de instruire.
- O instanta de instruire este constituita din
valori ale atributelor impreuna cu eticheta
de clasa.
Aspecte practice ale inductiei automate
- Cerinta de inteligibilitate a arborelui
- Cerinta de rapiditate a invatarii
- Cu cat setul de instante de instruire este
mai mare cu atat dimensiunea arborelui
creste.
- La seturi diferite de instante se obtin arbori
diferiti.
Spatiul de cautare
- Toate secventele posibile a tuturor testelor posibile
- Spatiul de cautare este foarte mare De exemplu, pentru N
atribute binare:
- N arbori cu 1 test
- N*(N-1) arbori cu 2 teste
- N*(N-1)*(N-1) arbori cu 3 teste
- H N4 arbori cu 4 teste
- Dimensiunea spatiului de cautare creste exponential cu
numarul atributelor
- Nu se poate realiza o cautare exhaustiva
- Se folosesc algoritmi de inductie care nu realizeaza
cautare exhaustiva
Algoritmi de inductie automata a
arborilor de clasificare
- Primul algoritm de inductie automata a arborilor
de clasificare - definit in 1984, simultan de catre
Breiman, Friedman, Olsen, Stone (statistica) si
Quinlan (IA, machine learning).
- Reprezinta un algoritm de inductie top-down a
arborilor de clasificare.
- Este cunoscut sub numele ID3, ID4, ID5, …,
ulterior C4.5, C5.0 [Quinlan] respectiv CART:
Classification and Regression Trees [Breiman].
Inductie-arbore(Instante)
If toate instantele au aceeasi eticheta de
clasa, y
then Include-nod-terminal(y)
else
Atribut = Cel-mai-bun-atribut(Instante)
Include-nod-neterminal(atribut,
Inductie-arbore(SelectFalse(Instante,
atribut),
Inductie-arbore(SelectTrue(Instante,
atribut)))
endif
Preview document
Conținut arhivă zip
- Invatarea Supervizata in Calculul Simbolic.pdf