Soluții pentru înlăturarea specializării

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

curs IA ASE