Proiect la disciplina Inteligenta Artificiala

Linear Machine Decision Trees (LMDT)

Student:Vatavu Andrei

Specializarea: Calculatoare

Sectia: Romana

Grupa: 3241

1.Prezentare generala. 3

6.Rezultatele LMDT. 4

7.Formatul fisierului de intrare. 5

8.Modificari efectuate. 6

9.Structura utilitarului LMDT. 6

10.Propunere de proiect 7

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

Programul foloseste ca intrare un set de date “de antrenament”, unul pe care se aplica arborele de decizie si unul pentru a reduce erorile folosind niste date de pruning. Rezultatele (statisticele) vor fi scrise intr-un fisier .log

LMDT ruleaza pe masini UNIX. Optiunile de rulare se specifica in linia de comanda, unele fiind optionale, altele – obligatorii.

2.Algoritmul LMDT

Algoritmul LMDT construeste un arbore de decizie pe mai multe clase, folosind o abordare TOP-DOWN. Pentru fiecare nod de decizie algoritmul “antreneaza” o masina lineara, bazandu-se pe un subset de variabile de intrare, care mai apoi vor servi ca un test multivariat pentru nodul de decizie. O masina liniara este un discriminant multiclasa linear care el insusi clasifica o instanta. Numele clasei este rezultatul testului efectuat de masina lineara cu o ramura pentru fiecare clasa posibila in nodul respectiv. Pentru a clasifica o instanta, aceasta trebuie codificata dupa modul de codificare local pastrat in nodul de decizie si urmarind ramura indicata de masina lineara.

3.Instalare LMDT

Se dezarhiveaza fisierul lmdt.tar: tar xf lmdt.tar

Se foloseste utilitarul MAKE pentru crearea fisierului imagine LMDT

4.Rulare LMDT

Se introduce numele fisierului imagine creat si optiunile necesare:

./LMDT <optiuni_obligatorii> <alte optiuni>

Optiuni obligatorii:

-f <training file> - numele fisierului de antrenament

Alte optiuni:

-a <annealrate> (implicit 0.995)

-k (pentru a pastra toate caracteristicele, implicit este DSBE)

-l <log file> (Fisierul cu rezultate. implicit <training file>.log)

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

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

-t <test file> (numele fisierului test. Contine instantele test)

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

-y (folosirea criteriului de acuratete)

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

5.Exemple

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

Ruleaza programul lmdt folosind train.data pentru formarea arborelui LMDT, initializeaza samanta pentru functia random la 200(pentru alegerea instantelor), scrie acuratetea lui test.data ca si celelalte statistici in fisierul primit ca parametru train.log.

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

Ruleaza programul lmdt folosind train.data pentru formarea arborelui LMDT,

folosind reducerea erorilor cu prune.data, scrie statisticile arborelui in fisierul train.log.

6.Rezultatele LMDT

Programul LMDT afiseaza statistici privind rularea in fisierul de tip log. Daca utilizatorul nu specifica explicit acest nume (folosind optiunea –l <fisier>) atunci statisticile vor fi scrise intr-un fisier al carui nume este 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 costului divizat 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 afara de fisierul log, este generat fisierul <training file>.tree. Ordinea atributelor acestui fisier este inverse ordinii atributelor fisierului de intrare. Pentru listarea unei versiuni ale arborelui LMDT se foloseste ca parametru: -v.

Atunci cand LMDT discrimineaza un set de instante dintr-un nod, acesta este listat intr-un disier lmdt.dump.

7.Formatul fisierului de intrare

Datele asteptate de program trebuie sa fie dezarhivate si situate in directorul current, din care ruleaza programul.

Toate fisierele de date (train, test si prune) vor avea urmatorul format:

- prima linie din fisier va contine numele atributelor. Ele trebuiesc separate prin virgula iar sfarsitul liniei sa fie terminat cu “.”

- a doua linie va fi blank.

- restul fisierului va trebui sa contina instante pe fiecare linie.

- formatul fiecarei instante este:

o valorile pentru fiecare instanta vor fi in aceeasi ordine ca si atributile din prima linie.

o Fiecare instanta se termina cu “.”

o Daca instanta este mai lunga de un rand atunci nu va trebui folosit nici un TAB sau Itrerupere

- Fisierul nu va trebui sa contina nici o linie blanc la sfarsit.

- Valorile lipsa se specifica prin “?”.

- Valorile pentru fiecare atribut trebuie sa fie de acelasi tip.

- Tipurile premise sunt simbolice si numerice.

- Valorile numerice pot fi intregi sau reale.

- Nu pot fi citite valori cu exponent. Deexemplu 1.2e3 va trebui reprezentat: 1200.

Exemplu:

attr1,attr2,....,attrn.

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

Exemple rulate:

exemplu1

exemplu2

8.Modificari efectuate

a) S-a modificat continutul fisierului makefile. Compilatorul CC a fost inlocuit cu GCC.

CC = gcc

all: plmdt

plmdt: er.o lm.o load.o print.o tree.o utils.o test.o discard.o encode.o prune.o

$(CC) -o lmdt er.o lm.o load.o print.o test.o tree.o encode.o utils.o discard.o

………………………………………………………………..

b)Am creat un exemplu mic, pentru a intelege mai bine implementarea algoritmului LMDT, modul de rulare, trasarea arborelui si generarea statisticilor.

9.Structura utilitarului 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.

10.Propunere de proiect

Construirea unui sistem pentru definirea anumitor concepte.De exemplu: pentru definirea conceptului de “om supraponderal” avem nevoie de unele atribute ca “Inaltime”, “Greutate”. Pentru aceste attribute se pot construi mai multe instante. Iar un nod va contine o masina liniara care va face discriminare intre instante. Astfel daca se va ajunge la o “frunza” din arborele LMDT format, se va stabili clasa din care face parte instanta, acuratetea stabilita la nivelul clasei(conceptului ales), si statisticele privind arborele de decizie.

Sistemul se va compune din doua parti:

1) Invatarea si antrenarea mashinei liniare, construirea arborelui de decizie.

2) Clasificarea datelor de intrare la unul din conceptele “invatate” la pasul 1.