Universitatea Tehnica Cluj-Napoca

Facultatea de Automatica si Calculatoare

Sectia Calculatoare

 

 

 

 

 

 

 

Proiect Semestrial la Inteligenta Artificiala

Linear Machine Decision Trees (LMDT)

 

  

 

 

 

 

                                                                                                                                                               Student : Suciu Paul Florin Andrei

                                                                                                                                                               Grupa 3242

 

 

 

 

 

1.     Prezentare generala

 

LMDT - Linear Machine Decision Trees este o unealta ce are ca scop principal prelucrarea, obtinerea, testarea arborilor de decizie folosind un algoritm bazat pe decizii multivariate(algoritmul LMDT).  Una dintre problemele cu care se confrunta masinile este cum sa invete din exemple. Dintr-o secventa sau un set de exemple de instruire, fiecare etichetat cu numele corect al clasei sale, o masina invata prin formarea sau selectarea unei generalizari a exemplelor de instruire.Acest proces, cunoscut si sub numele de invatare supervizata, este folositor pentru clasificari din lumea reala, cum ar fi diagnosticarea unor boli sau pentru rezolvarea anumitor sarcini la care deciziile de control depind de clasificare de exemplu aplicarea regulilor. Obiectivul principal al construirii unui albore de decizie este acela de a obtine o clasificare cat mai exacta  a exemplelor din domeniu. Un obiectiv secundar este acela de a obtine o procedura de decizie care poate fi inteleasa de o persoana umana, astfel ca persoana in cauza sa poate realiza o cat mai buna clasificare a cazurilor rivalizand chiar cu  procedura de decizie. Mai mult decat atat in domeniile in care costurile unei clasificari este mare, un arbore de decizie inteligibil ii ofera unei persoane posibilitatea de a verifica daca procedura de decizie este corecta. Programul foloseste un set de date de intrare de instruire,  pe care se aplica arborele de decizie.

Algoritmul LMDT costruieste un arbore de decizie multiclass si multivariat folosind un acces de tip top-down. Pentru fiecare nod de decizie din arbore, LMDT antreneaza o masina liniara, bazata pe un subset de date de intrare, care mai apoi servesc ca test multivariat pentru nodul de decizie. O masina liniara este un discriminant liniar multiclass, care la randul lui clasifica o instanta. Numele clasei este rezultatul testului masinii liniare cu cate o ramura pentru fiecare posibila clasa din nod. LMDT poate manipula instante descrise de variabile simbolice sau numerice, din care pot lipsi anumite valori. LMDT codifica fiecare variabila simbolica intr-una numerica, iar variabilele simbolice si numerice codate sunt  normnalizate automat la fiecare nod. Fiecare informatie codata este evaluata in mod dinamic in fiecare nod si este retinuta in arbore pentru a clasifica instante.

Voi prezenta pe scurt modul in care functioneaza algoritmul:

1.      Daca toate instantele provin de la o singura  clasa atunci seteaza Tree sa fie un nod frunza continand numele clasei ca fiind cel al singurei clase apoi Return.

2.      Altfel seteaza Tree sa fie un nod de decizie care contine un test construit antrenand o masina liniara.

3.      Daca testul imparte instantele in 2 sau mai multe subseturi, atunci pentru fiecare subset  construieste un subarbore recursiv, Return

4.      Altfel, seteaza Tree sa fie  un nod frunza avand clasa numita dupa numele celei mai des intalnite clase, Return.

 

 

 

 

2.     Instalarea si rularea algoritmului LMDT

 

      Se dezarhiveaza sub UNIX fisierul lmdt.tar.Z  cu uncompress lmdt.tar iar apoi se dezarhiveaza folosind comanda tar xf lmdt.tar. Pentru a crea fisierul imagine LMDT se foloseste MAKE.

  Pentru a rula acest utilitar trebuie specificata linia de comanda precum si anumite optiniuni necesare cum ar fi:

 Ex: LMDT -f train.data -t test.data -r prune.data           

 unde  -f <fisiere de antrenament>  este optiune necesara iar urmatoarele optiuni pot lipsi:

-a <annealrate>            (valoarea implicita este  0.995)

 -k                                (pentru a nu se pierde trasaturile, implicit este DSBE)

 -l <log file>      (Rezultatele. implicit <training file>.log)

 -r <prune file>             (reducerea arborelui folosind pruning-ul pentru reducerea erorilor)

 -s <intr>                      (samanta pentru functia random, folosit pentru antrenament)

 -t <test file>                 (numele fisierului cu instantele test)

 -v                                (verbose flag, scrie la iesire statisticele arborelui)

 -y                                (folosirea criteriului de acuratete, implicit este raportul informatie-                    castig)

-z                                (setarea costului la zero dupa fiecare eliminare, implicit : NOT zero)

                               

 

 

3.Exemple folosite pentru exemplificarea algoritmului     

 

 

In pachetul LMDT descarcat, precum si in documentatia aferenta, exista 2 exemple pe care le voi prezenta in cele ce urmaeaza:

>LMDT -f train.data -t test.data -s 200

Care ruleaza utilitarul LMDT folosint TRAIN>DATA pentru a forma arborele LMDT. Acest exemplu initializeaza samanta pentru functia RANDOM la valoarea 200, iar acesta scrie acuratetea lui TEST.DATA alaturi de celelalte statistici in fisierul TRAIN.LOG care este primit ca si parametru .

 

  > LMDT -f train.data -t test.data -r prune.data -l train.log

Celalalt exemplu folosit in documentatie este acesta prezentat mai sus si care ruleaza utilitarul  LMDT folosind TRAIN.DATA  pentru formarea arborelui LMDT, si care foloseste pentru reducerea erorilor PRUNE.DATA, si scrie statisticile in fisierul TRAIN.LOG.

 

 

 

4.Datele de iesire ale LMDT

 

 

Utilitarul  LMDT afiseaza anumite statistici privind rularea in fisierul log. Daca utilizatorul nu specifica in mod expres  acest nume (folosind optiunea –l <fisier>) atunci statisticile vor fi scrise intr-un fisier de tipul <fisierul training>.log .                               In acest fisier sunt scrise urmatoarele:

            Number Epochs : <real>

            Num Insts seen: <integer>

            Num Insts trnd: <integer>

            Number nodes  : <integer>

            Number of LVs : <integer>

            Unique vars   : <integer>

            Ave. vars/LM  : <real>

            Train accuracy: <real>

            Test accuracy : <real>

            Train errors  | <real>

            Test errors   | <real>

            Time          :  <integer>

unde, 

            Number Epochs – numarul instantelor pentru modificarea marimii divizate la numarul total de instante de tip training.

            Num Insts seen  – numarul instantelor urmarite pe durata parcurgerii.

            Num Insts trnd – numarul instantelor folosite pentru modificarea costului pe parcursul antrenamentului.

            Number of nodes – numarul masinilor lineare din arbore.

            Number of leaves – numarul nodurilor frunza din arbore.

            Unique vars – numarul anumitor caracteristici folosite in arbore.

            Ave. vars/LM – media aritmetica a caracteristicilor per LMs.

            Train accuracy – acuratetea rborelui pentru datele de tip training.

            Test accuracy – acuratetea arborelui pentru datele de tip test.

Train errors – numarul instantelor de tip training care au fost clasificate incorrect.

Test errors - numarul instantelor de tip training care au fost clasificate incorrect.

Time -  numarul secundelor cpu folosite pentru contructia arborelui.

In completarea fisierului LOG, LMDT va printa un fisier arbore: <training file>.tree.

De notat este ca ordinea atribuitelor din acest fisier este inversa fata de modul in care au fost specificate in fisierele de intrare. Daca se doreste o versiune tiparita a arborelui atunci se specifica in linia de comanda optiunea –v. Daca LMDT nu poate face deosebire intre un set de instante dintr-un nod atunci le va printa intr-un fisier numit LMDT.DUMP.

 

 

 

5.Fisierul de iesire-Formatul

 

 

Programul asteapta ca fisierele de date sa fie necomprimate si in directorul curent. Toate fisierele de date trebuie sa aiba urmatorul format:          Prima linie va contine numele atributelor. Acestea trebuie sa fie separate prin virgula  si sa se termine cu “.” Iar urmatoarea linie sa fie goala. Restul fisierului trebuie sa contina instante, cate una pe fiecare linie. Formatul fiecarei instante trebuie sa fie: valoarea fiecarei instante trebuie s fie in aceeasi ordine ca si linia atributelor si trebuie sa fie separate de virgule. Ultimul element de pe linie este numele clasei, iar instanta se termina cu “.”. Daca instanta depasteste lungimea unei linii din fisier atunci nu va trebui sa se foloseasca nici un TAB sau intreruperi in fisier.  Fisierul nu trebuie s acontina nici un spatiu la sfarsitul sau. Valorile lipsa trebuie specificate prin semnul “?”.  Valorile pentru fiecare atribut trebuie s fie de un singur tip(deci de acelasi tip), iar tipurile permise sunt numerice si simbolice. Valorile numerice pot fi fie intregi fie reale.   Nu pot fi citite valori cu exponent. De exemplu 1.2e3 va trebui reprezentat: 1200 altfel va aparea o eroare.

De exemplu :

attr1,attr2,....,attrn.

val1,val2,...,valn,class.

val1,val2,...,valn,class.

.

.

 

 

6.Structura LMDT

 

 

LMDT este compus din urmatoarele module:

Utils.c – contine functii pentru alocarea stringurilor, a spatiului de memorie si parsarea intrarii pentru utilizarea anumitor optiuni.

Tree.c – rutine pentru construirea arborelui LMDT.

Test.c – rutine pentru clasificare,statistici.

Pruning.c -  pessimistic pruning & reduced error pruning.

Print.c – printeaza rutinele pentru sistemul LMDT.

Load.c – citeste din fisierele de date.

LM.c construieste masina liniara pentru diecare clasa.

Encode.c – codificarea variabilelor.