Arbori de decizie - Inteligenta artificiala

Arbori de decizie

Inteligenta artificiala

Cuprins

      Notiuni introductive

      Alcatuirea unui arbore de decizie

      Algoritmi

n      ID3

n      C45

      Exemplu

      Implementari in Weka

n      ID3

n      J48

Notiuni introductive

      Definitie: Arborii de decizie sunt una dintre modalitatile de reprezentare a "structurii din date", unde nodurile reprezinta teste facute pe atributele datelor de input iar frunzele reprezinta categoriile, modelul final

n      un arbore reprezinta "cunostintele invatate" de algoritmi.

Arbori de decizie

      Incepand de la radacina fiecare dintre noduri reprezinta un test facut pe unul dintre atributele setului de date.

      Arborele se va forma testand pe rand ficare atribut al setului de date.

      Rezultatul testului va "ramifica" arborele pana la ultimul nivel unde sunt situate frunzele.

In figura 2. este reprezentat modul de clasificare a unei instante I1 folosind un arbore de decizie:

la nivelul radacina testul se face pe atributul T1 care ia valoarea a1,

urmatorul nivel va plasa instanta pe ramificarea T1 = b2,

procesul continua pana la nivelul de frunza.

Arbori de decizie

      Exemple de noduri

Arbori de decizie

Modul de construire a arborilor de decizie

      metoda divide-andconquer: arborele va fi construit recursiv urmand pasii:

Pas1: se alege un atribut care va fi considerat "radacina"

Pas2: se imparte setul de date conform valorilor acestui atribut

Pas3: pentru fiecare din ramificare se va relua procesul de la "Pas1" cu datele care au ajuns in acest set

      Algoritmul se opreste in momentul in care o sub-ramura va contine date cu o singura valoare a atributului clasa.

      Problema de implementare pe care o ridica acest algoritm este

n      metoda prin care se alege atributul dupa care sa se faca impartirea.

n      se va calcula, prin diferite formule, o marime numita "informatie"

n      Intuitiv aceasta marime va masura "cat de curata" va fi impartirea folosind acel atribut.

      Aceasta marime, "informatia", se masoara in unitati numite "biti". In cazul arborilor de decizie marimea este de obicei fractionara si mai mica decat 1 [Wi,99].

Modul de calcul al informatiei

      Pentru calculul informatiei vom avea premizele:

clasa setului de date are valori binare (ex: 0/1, da/nu, -1/1)

1. informatia trebuie sa aiba proprietatile
1. cand numarul de "da" sau "nu" este zero informatia este zero (intuitiv: daca setul de date contine o singura valoare a atributului clasa, scindarea setului dupa oricare dintre atribute este inutila deoarece detin deja o "structura" a datelor conform clasei urmarite, deci clasificarea este deja facuta)

1. daca numarul de "da" este egal cu numarul de "nu" informatia va atinge un maxim   

1. metoda trebuie sa suporte si clase cu mai multe valori

      Pentru a indeplini toate aceste premize s-a ales pentru calculul informatiei marimea "entropie":

n      Entropie(p1, p2, .,pn) = - p1 log p1 - p2 log p2 - - pn log pn

      Daca entropia este calculata in logaritmi cu baza 2 se va masura in "biti" in acceptiunea in care sunt folositi in calculul numeric

      Informatia calculata in aceasta maniera:

n      este asociata unui nod (radacina sau intermediar) si

n      reprezinta cantitatea de informatie pe care ar trebui sa o stim ca sa putem clasifica o instnta noua

      Folosind aceasta informatie pentru fiecare din ramificari si tinand seama de numarul de instante clasificate pe fiecare din ramificari:

n      ".com" - 5 instante

n      ".edu" - 4 instante

n      ".ro" - 5 instante

      putem calcula "media de informatie" pe acest atribut astfel:

info([2,3],[4,0],[3,2]) = 5/14 * 0,971 + 4/14 * 0 + 5/14 * 0,971 = 0,693

      Intuitiv aceasta medie reprezinta cantitatea de informatie de care avem nevoie, pe care ne asteptam sa o cunoastem, pentru a clasifica o instanta noua data fiind clasificarea din figura.

      Inainte sa obtinem clasificarea din figura pentru setul de date reprezentat, avem informatia:

Info( ) = 0,94 biti

      Unde: 9 instante stim ca au valoarea atributului clasa "da"

5 instante stim ca au valoarea atributului clasa "nu" (dupa cum se vede din figura 5)

      Scazand din informatia pe care o detin despre setul de date, pe cea de care am nevoie ca sa fac clasificarea, obtin informatia castigata efectuand clasificarea din figura 5

      InformatiaCastigata(domeniu) = info([9,5]) - info (domeniu) = 0,94 - 0,694 = 0,24 biti

      Dupa ce am calculat informatia castigata

n      in urma unei clasificari folosind un anumit atribut

n      se poate decide care din atribute va fi ales pentru a efectua clasificarea setului de date, urmand pasii:

      Pas1: se calculeaza informatia castigata in urma clasificarii pentru fiecare din atribute (folosind procedeul descris mai sus)

      Pas2: se vor compara informatiile castigate clasificand fiecare din atribute

      Pas3: se va alege atributul cu cea mai mare informatie castigata in urma clasificarii

      Procedeul descris se va continua recursiv pentru formarea fiecarui nod.

      In cazul in care frunzele sunt "pure" adica vor contine o singura valoare a clasei ( cum este ramificatia ".edu" din figura 5, care contine doar valori "da" a atributului clasa) clasificarea este terminata.

      In teorie clasificarea se termina cand toate frunzele sunt "pure".

      In practica, pe date reale, nu se vor obtine intotdeauna frunze "pure" caz in care algoritmul se va opri cand datele nu mai pot fi impartite.

Exercitiu

      Deschideti fisierul ex1.arff in excel si construiti manual un arbore de decizie urmand pasii descrisi mai sus

      Indicatii:

Cate atribute avem?

Care este informatia detinuta de "structura din date"

Pe ce atribut se va face prima scindare

Calculati informatia si

castigul informational

Deschideti Weka si construiti arborele de decizie cu ajutorul algoritmului J48

OBS:

Log 0,4 = -1,3219; Log 0,6 = 0,7369;Log 0,64 = -0,64; Log 0,357 = -1,486

InfoCastigata(varsta) = 0,247

InfoCastigata(venit) = 0,029

InfoCastigata(locuinta) = 0,152

InfoCastigata(salariat) = 0,048

Implementarea arborilor de decizie

Weka: Implementarea arborilor de decizie

      Etape:

n      Deschiderea fisierului de date

n      Selectarea algoritmului dorit

n      Selectarea optiunilor dorite

n      Rularea algoritmului

n      Interpretarea rezultatelor

n      Verificarea modelului

n      Salvarea modelului

      Selectarea algoritmului dorit

n      J48: atribut numerice

n      ID3: atribute nominale

      Atributul clasa: nominal

Weka: Selectarea algoritmului dorit

Weka: Selectarea optiunilor dorite

a)      Selectarea optiunilor    e rulare a algoritmului

Weka: Optiuni

Fig: Erorilie de clasificare

Instantele reprezentate corect sunt desenate cu X

- Instantele reprezentate incorectt cu patrat

Weka: Optiuni

Estimarea costurilor:

Problemele reale implica intotdeauna costuri

Erori differite / complementare vor implica (de obicei) costuri diferite

ex: daca voi acorda un imprumut unui client insolvabil, ma va costa mult mai mult (in termeni de pierdere de afacere) decat daca nu as fi acordat acel imprumut unui client solvabil

prezicerea unei disfunctii inexistente in sistemul electric si luarea masurilor pentru tratare va fi mult mai ieftin decat neprezicerea unei disfuntii existente si tratarea consecintelor

Daca se cunosc costurile reale pentru ambele situatii se pot

Instantele reprezentate corect sunt desenate cu X

- Instantele reprezentate incorectt cu patrat

Interpretarea rezultatelor

      In cazul arborilor de decizie, interpretarea rezultatelor inseamna citirea arborelui de decizie de la nivel zero pina la nivelul frunza

      Exemplu:

n      Atributul cel mai important: latimea petalei

      Descrierea clasificarii formate:

n      Daca latimea petalei e mai mica de 0.6 atunci tipul este Iris-setosa

n      Daca latimea <= 0.6 Si latimea <= 4.9 atunci iris-versicolor

Interpretarea rezultatelor

Arborele de decizie sub forma textuala

Arborele de decizie sub forma grafica

Verificarea modelului

Numar de instnte corect / incorect clasificate din total

Salvarea modelului

Exemplu

      Selectati fisierul:

n      Obj2c.arff

n      Selectati algoritmul J48

n      Optiuni implicite

      Obs.: aplicatia completa este descrisa in seminar1_b.ppt

Exemplu: arbore de decizie generat

Bibliografie

[1] Bounsaythip, C., si Runsala, R., E., - Overview of Data Minig of Customer Behavior Modeling, Research Report, VTT Information Technology, 2001.

[2] Kirkby, R., - WEKA Explorer User Guide, The University of Waikato, 2002.

[3] Witten, I., H., si Frank, E., - Data minig: Practical machine learning tools and techniques with Java implementations, Ed. Academic Press, New Zeeland, 1999.