Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

 
CATEGORII DOCUMENTE

AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Arbori de decizie - Inteligenta artificiala

algoritmi

+ Font mai mare | - Font mai mic


DOCUMENTE SIMILARE

Trimite pe Messenger
Sistem informational – Sistem informatic
Arbori de decizie - Inteligenta artificiala
Algoritmi semnatura digitala
Stiva - Utilitatea stivelor - Accesarea elementului de la varf
Proiect ASDN - Algoritmul de minimizare Karnaugh
Tipuri de limbaje de programare
Tehnici de programare structurata: Recursivitatea, Backtracking
Constructia si simularea executiei unui program (in limbaj de asamblare)

TERMENI importanti pentru acest document

:

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:

1.      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([9,5]) = 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:

1.      Cate atribute avem?

2.      Care este informatia detinuta de “structura din date”

3.      Pe ce atribut se va face prima scindare

1.      Calculati informatia si

2.      castigul informational

4.      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.

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1013
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Distribuie URL

Adauga cod HTML in site

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2014. All rights reserved