phd thesis

Upload: mihaisan3846

Post on 16-Jul-2015

214 views

Category:

Documents


0 download

TRANSCRIPT

UNIVERSITATEA DE VEST DIN TIMISOARA FACULTATEA DE MATEMATICA SI INFORMATICA DEPARTAMENTUL DE INFORMATICA

TEZA DE DOCTORAT

SISTEME INTELIGENTE PENTRU MODELAREA SI EXTRAGEREA CUNOSTINTELOR

Conductor tiintic: a s Prof. Dr. Stefan MARUSTER

Candidat: Daniel POP

Iunie 2006

Familiei mele

CuprinsAbstract Multumiri Introducere 1 Reprezentarea cunotintelor s 1.1 Modele de reprezentare a cunotintelor . . . . . . . . . . . s 1.2 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 1.3 Reguli de productie . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Bazele teoretice ale regulilor de productie . . . . . 1.3.2 Reguli de productie folosite problema clasicrii n a 1.4 Arbori de decizie . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Bazele teoretice ale arborilor de decizie . . . . . . 1.4.2 Algoritmi pentru constructia arborilor de decizie . 1.5 Tabele de decizie . . . . . . . . . . . . . . . . . . . . . . . 1.6 Extensii ale modelelor clasice . . . . . . . . . . . . . . . . 1.6.1 Extensii pentru arborii de decizie . . . . . . . . . . 1.6.2 Extensii pentru tabelele de decizie . . . . . . . . . 1.7 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 11 13 17 17 20 22 22 24 28 29 33 38 41 41 46 49

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

2 Echivalenta reprezentrilor a 2.1 Regiunea de experient . . . . . . . . . . . . . . . . . . . . . . . . . a 2.1.1 Caracterizarea regiunii de experient . . . . . . . . . . . . . . a 2.1.2 Descoperirea regulilor de asociere . . . . . . . . . . . . . . . . 2.1.3 Algoritmi secventiali pentru descoperirea regulilor de asociere 2.1.4 Exemplu de generare a PFD folosind regulile de asociere . . . 2.2 Echivalenta reprezentrilor regiunea de experient . . . . . . . . . a n a 2.3 Selectarea atributului de separare . . . . . . . . . . . . . . . . . . . . 2.3.1 Msura Voting . . . . . . . . . . . . . . . . . . . . . . . . . . a 2.3.2 Agregarea tabelei de incident din seturi mari de date . . . . a 2.4 Reducerea arborilor de decizie . . . . . . . . . . . . . . . . . . . . . . 2.5 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

51 . . . . . . . 51 . . . . . . . 53 . . . . . . . 60 . . . . . . . 63 . . . . . . . 67 . . . . . . . 69 . . . . . . . 73 . . . . . . . 77 . . . . . . . 78 . . . . . . . 82 . . . . . . . 83

3 Mediu pentru dezvoltarea sistemelor bazate pe cunotinte s 3.1 Motivatie, scop i istoric . . . . . . . . . . . . . . . . . . . . . s 3.2 Arhitectura sistemului i descrierea modulelor componente . . s 3.3 Editoarele bazei de cunotinte . . . . . . . . . . . . . . . . . . s 3.4 Integrarea bazei de cunotinte sistemul bazat pe cunotinte s n s 3.5 Achizitia cunotintelor . . . . . . . . . . . . . . . . . . . . . . s 3.6 Gestionarea versiunilor . . . . . . . . . . . . . . . . . . . . . . 3.7 Comunicarea cu bazele de date relationale . . . . . . . . . . . 3.7.1 Descrierea detaliat a modulelor subsistemului KBDB a 3.7.2 Functionarea KBDB . . . . . . . . . . . . . . . . . . . 3.8 Generarea documentatiei interne . . . . . . . . . . . . . . . . 3.9 Metodologia dezvoltrii sistemelor cu Expert System Creator a 3.10 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Platform multi-agent pentru descoperirea cunotintelor a s 4.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Analiza i proiectarea sistemului . . . . . . . . . . . . . . . s 4.2.1 Analiza sistemului . . . . . . . . . . . . . . . . . . . 4.2.2 Proiectarea sistemului . . . . . . . . . . . . . . . . . 4.2.3 Ontologia KDD . . . . . . . . . . . . . . . . . . . . . 4.2.4 Detalii despre implementarea agentilor . . . . . . . . 4.3 Evaluarea calitii sistemelor bazate pe cunotinte . . . . . at s 4.3.1 Calitatea modelelor de cunotinte . . . . . . . . . . . s 4.4 Studiu de caz: CoverType . . . . . . . . . . . . . . . . . . . 4.5 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Generarea automat a documentelor juridice a A.1 Introducere . . . . . . . . . . . . . . . . . . . . . . A.2 Analiza problemei . . . . . . . . . . . . . . . . . . A.3 Achizitia cunotintelor specice domeniului . . . . s A.4 Proiectarea i implementarea sistemului . . . . . . s A.5 Vericarea, validarea i evaluarea sistemului . . . . s A.5.1 Vericarea sistemului . . . . . . . . . . . . . A.5.2 Validarea sistemului . . . . . . . . . . . . . A.5.3 Evaluarea sistemului . . . . . . . . . . . . . A.6 Documentarea sistemului . . . . . . . . . . . . . . A.7 Intretinerea, exploatarea i actualizarea sistemului s A.8 Concluzii . . . . . . . . . . . . . . . . . . . . . . . B Detalierea ontologiei KDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85 85 88 90 97 100 101 104 106 108 109 112 112 115 116 120 121 124 129 131 138 143 146 148 149 149 151 152 153 156 157 157 158 159 159 160 163

Lista tabelelor1.1 1.2 1.3 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 4.1 4.2 4.3 4.4 4.5 4.6 Modele de reprezentare a cunotintelor . . . . . . . . . . . . . . . . . . . . . . . . s Tipuri de reguli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Forma general a tabelei de decizie . . . . . . . . . . . . . . . . . . . . . . . . . . a Regulile de asociere extrase din setul de antrenament pentru Garvan ES1 Matricea pentru determinarea K1 . . . . . . . . . . . . . . . . . . . . . . Algoritmi pentru descoperirea regulilor de asociere . . . . . . . . . . . . . Tabela de incident . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a Tabela de incident i valorile msurilor pentru atributul Nivel debit . . . a s a Selectia atributului de separare . . . . . . . . . . . . . . . . . . . . . . . . Tabela de incident pentru atributul Regiune . . . . . . . . . . . . . . . . a Algoritmi de reducere a arborilor de decizie . . . . . . . . . . . . . . . . . Tabela capabilitilor . . . . . . . . . . . . . . . . at Tabela de interactiuni pentru agentul expert . . . Matricea de calitate pentru baza de cunotinte . s Matricea de calitate pentru modulul de inferent a Matricea de calitate pentru modelul task . . . . . Estimarea calitii modelelor . . . . . . . . . . . at . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 23 39 59 60 68 74 76 76 80 83 125 126 142 142 142 147

A.1 Reprezentarea cunotintelor faza de achizitie . . . . . . . . . . . . . . . . . . . 153 s n

5

Lista gurilor1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 2.1 2.2 2.3 2.4 2.5 2.6 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 4.1 4.2 4.3 4.4 Ierarhia cunotintelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . s Date de antrenament i setul de reguli de productie corespunztor . . . . . . s a Graf de dependent extins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a Exemplu de arbore de decizie . . . . . . . . . . . . . . . . . . . . . . . . . . . Metoda lui Hunt a) Arbori de decizie binari b) Arbori de decizie multi-ci . . a Ilustrarea structurii arborelui de decizie spatiul de valori . . . . . . . . . . n Tabela de decizie ( form orizontal ) . . . . . . . . . . . . . . . . . . . . . n a a Tabela de decizie ( form vertical) . . . . . . . . . . . . . . . . . . . . . . . n a a Reducerea unui subarbore (a) arborele original (b) arborele urma reducerii n Exemplu de tabel de decizie extins ( Expert System Creator) . . . . . . . a a n . . . . . . . . . . . . . . . . . . . . 18 25 26 29 32 34 39 40 43 47 57 62 63 63 78 79 89 91 93 95 96 99 101 104 106 110 111 122 123 123 127

Constructia PFD-urilor folosind descoperirea regulilor de asociere . . . . . . . . . (a) Baza de date (b) Seturile frecvente de articole cu un suport minim de 50% (c) Regulile de asociere (minconf=100%) . . . . . . . . . . . . . . . . . . . . . . . . . (a) Laticea seturilor de articole (b) Dispunerile orizontal i vertical . . . . . . . as a Generarea regulilor de asociere . . . . . . . . . . . . . . . . . . . . . . . . . . . . Metoda Voting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rezultate experimentale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Arhitectura Expert System Creator . . . . . . Editorul de reguli de productie . . . . . . . . Editorul de tabele de decizie . . . . . . . . . . Editorul de arbori de decizie . . . . . . . . . . Desenarea bazat pe informatie ESC . . . a n Gestionarul de dictionare . . . . . . . . . . . Nod de achizitie conditional . . . . . . . . . a Exploratorul de versiuni . . . . . . . . . . . . Arhitectura KBDB . . . . . . . . . . . . . . . Arhitectura generatorului de documentatie . Exemplu de documentatie generat automat . a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Metodologia pentru analiza i proiectarea sistemelor multi-agent . . . s Diagrama de utilizare . . . . . . . . . . . . . . . . . . . . . . . . . . . Diagrama agentilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Publicarea/regsirea agentilor constructori folosind un agent facilitator a 7

8 4.5 4.6 4.7 4.8 4.9 4.10 Agentul traductor pentru accesul la o baz de date relational . . . a a Ontologia KDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Diagrama de actiuni pentru agentul expert . . . . . . . . . . . . . Implementarea agentului expert Expert System Creator (extras) n Modelul de calitate ISO 9126 . . . . . . . . . . . . . . . . . . . . . Metodologia de msurare a calitii SBC . . . . . . . . . . . . . . . a at

INTRODUCERE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 132 133 134 139 140

A.1 Arhitectura sistemului LDDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A.2 Exemplu de regul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 a A.3 Regulile LDDS arcate ESC, Lex Browser i Lex Engine . . . . . . . . . . . 156 nc n s B.1 Ontologia KDD. Task-uri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 B.2 Ontologia KDD. Surse de date i metode de rezolvare task . . . . . . . . . . . . . 165 s B.3 Ontologia KDD. Modele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

AbstractSintagme precum economie bazat pe cunotinte, organizatii bazate pe cunotinte, educatie a s s bazat pe cunotinte sunt des utilizate zilele noastre, cnd Internetul schimb pe zi ce trece a s n a a lumea care trim iar n a mbriarea erei digitale este o provocare pentru toate organizatiile. Dar at s locul cunotintelor utile, organizatiile au la dispozitie uriae cantiti de date primare stocate n s s at baze de date, sisteme de iere sau diverse sisteme de arhivare. Astfel, migrarea de la datele n s primare la reprezentri bogate semantic, capitalizarea cunotintelor la nivelul organizatiilor i a s s protectia i securizarea acestora sunt provocrile actuale pentru aceste organizatii. acest s a In sens, lucrarea de fat sunt analizate, formalizate i n a s mbuntite modelele de reprezentare a at a cunotintelor, este prezentat implementarea unui mediu vizual pentru reprezentarea i opes a s rarea cunotintelor i este propus o arhitectur multi-agent pentru asistarea utilizatorilor s s a a n procesul de descoperire a cunotintelor din seturile mari de date. Sistemele propuse se bazeaz s a pe tehnologii i abordri moderne, cum ar rationamentul orientat task, sistemele multi-agent, s a platformele software portabile.

9

10

INTRODUCERE

Multumiri primul rnd, a dori s aduc multumirile mele domnului Prof. Dr. Stefan Mruter In a s a a s pentru sustinerea programul doctoral i pentru atitudinea de rigoare tiintic pe care mi-a n s s a inspirat-o aceti ani. Aceast lucrare nu ar fost posibil fr n s a a a a ndrumarea domnului Prof. Dr. Viorel Negru ale crui sfaturi, a ncurajri i expertiz tiintic artate de-a lungul studiia s as a a lor doctorale au fost cruciale pentru nalizarea cu success a acestei lucrri. Sunt recunosctor a a tuturor membrilor Departamentului de Informatic al Facultii de Matematic din cadrul Unia at a versitii de Vest din Timioara pentru sugestiile i at s s ncurajrile lor. Deasemenea, multumirile a mele se ndreapt ctre Dr. Clin Sandru pentru observatiile i sugestiile constructive legate a a a s de analiza i proiectarea sistemului multi-agent. Tin s multumesc i tuturor colaboratorilor s a s mei activitatea de cercetare, colegilor de la Optsol.ro i din cadrul departamenului IT S&D n s al Alcatel Romnia, pentru elegerea i sprijinul artate de-a lungul acestei perioade i pena nt s a s tru cooperarea fructuoas. Multumesc comisiei pentru reviziile fcute i pentru observatiile de a a s mbuntire aduse pe marginea acestui material. a at nal, dar nu ultimul rnd, multumesc familiei mele pentru sprijinul, elegerea i In n a nt s ncrederea artate. a

Timioara, Romnia s a Iunie, 2006

Daniel Pop

11

12

INTRODUCERE

IntroducereSintagme precum economie bazat pe cunotinte, organizatii bazate pe cunotinte, educatie a s s bazat pe cunotinte sunt des utilizate zilele noastre, cnd Internetul schimb pe zi ce trece lua s n a a mea care trim, iar n a mbriarea erei digitale este o provocare pentru toate organizatiile. Dar at s locul cunotintelor utile, organizatiile au la dispozitie uriae cantiti de date primare stocate n s s at baze de date, sisteme de iere sau diverse sisteme de arhivare. Astfel, migrarea de la datele n s primare la reprezentri bogate semantic, capitalizarea cunotintelor la nivelul organizatiilor i a s s acest protectia i securizarea acestora sunt provocrile actuale pentru aceste organizatii. In s a sens, lucrarea de fat sunt analizate, formalizate i n a s mbuntite modelele de reprezentare a at a cunotintelor, este prezentat implementarea unui mediu vizual pentru reprezentarea i opes a s rarea cunotintelor i este propus o arhitectur multi-agent pentru asistarea utilizatorilor s s a a n procesul de descoperire a cunotintelor din seturile mari de date. Sistemele propuse se bazeaz s a pe tehnologii i abordri moderne, cum ar rationamentul orientat task, sistemele multi-agent s a sau platformele software portabile. Primul capitol prezint cele mai cunoscute modele de reprezentare a cunotintelor sistea s n mele bazate pe cunotinte regulile de productie, arborii i tabelele de decizie i sunt propuse s s s unele mbuntiri ale acestora scopul unei mai bune integrri i exploatri. sectiunea 1.1, a at n a s a In este realizat o sintez a celor mai populare tipuri de cunotinte i sunt evidentiate cele mai a a s s importante caracteristici ale modelelor de reprezentare a cunotintelor (rezultate sintetizate s i [Pop00a]), timp ce sectiunea 1.2 sunt formalizate din punct de vedere matematic s n n n aceste reprezentri. Sectiunea 1.3 trateaz reprezentarea bazat pe reguli de productie, descrie a a a din punct de vedere formal acest model i-l particularizeaz pentru problemele de clasicare s a a s a n (sectiunea 1.3.2). O contributie original relativ la acest model i detaliat [PN02b, PN03] este graful de dependent extins pentru un set de reguli de productie, o a mbuntire a graa at fului de dependent clasic cruia sunt adugate i dependentele de tipul regul atribut, a a i a s a beneciul principal ind acela c este facilitat depistarea unor probleme de proiectare a bazei a a de cunotinte la un nivel mult mai detaliat dect modelul clasic. Sectiunea 1.4 analizeaz s a n a sintetic modelul arbore de decizie: construiete un formalism pentru reprezentarea acestuia, s prezint schema de constructie automat a arborelui din seturi de date i sintetizeaz prina a s a cipalele avantaje i dezavantaje ale modelului. sectiunea 1.4.2 este prezentat o sintez a s In a a celor mai cunoscuti algoritmi secventiali de constructie i actualizare incremental a arborilor s a de decizie, inclus in extenso [Pop02c, Pop02d]. Sectiunea 1.5 analizeaz modelul tabel de a n a a decizie, este prezentat un scurt istoric i sunt evidentiate principalele proprieti ale modelului. s at Sectiunea 1.6 trateaz dou contributii originale asupra modelelor arbore de decizie i tabel de a a s a 13

14

INTRODUCERE

decizie [Pop06b]: suportul pentru noduri/celule de actiune i suportul pentru rationament s n conditii de incertitudine i este demonstrat echivalenta modelelor extinse propuse. Prima dintre s a ele nodurile/celulele interne de actiune faciliteaz integrarea modelului cu modulele externe, a fr a diminua puterea de expresie, performantele sau claritatea modelului. Cea de-a doua aa extensie, reprezentat prin suportul, suportul relativ i precizia nodului/celulei, faciliteaz ima s a plementarea unui rationament aproximativ pentru modelul arbore/tabel de decizie. Extensiile a aduse arborilor i tabelelor de decizie sunt implementate mediul de dezvoltare Expert System s n Creator (capitolul 3), platform utilizat i la ilustrarea implementrii modelelor prezentate. a as a capitolul 2 este investigat echivalenta modelelor de reprezentare a cunotintelor preIn a s zentate primul capitol. Pentru a reduce dimensiunea obiectelor translatate se utilizeaz o n a caracterizare a regiunii de experint. Sectiunea 2.1 denete regiunea de experient i analizeaz a s a s a cauzele aparitiei fenomenului inationist observat la conversia dintr-o reprezentare ntr-alta. In a a sectiunea 2.1.1 este propus o nou caracterizare a acesteia folosind regulile de asociere [Pop06a] i sunt prezentate rezultatele obtinute pentru sistemul expert Garvan ES1, iar sectiunea 2.1.4 s n se prezint un studiu de caz pe un exemplu. Formalizarea matematic a problemei descoperirii a a regulilor de asociere este introdus sectiunea 2.1.2, iar sectiunea 2.1.3 sintetizeaz i coma n a s par cei mai uzitati algoritmi pentru descoperirea regulilor de asociere. sectiunea 2.2 sunt a In prezentate adaptri ale algoritmilor de conversie a ntre modele, lund considerare consistenta a n propozitiilor elementare regiunea de experient. Etapa de selectare a atributului de separare n a a algoritmului de conversie a tabelei de decizie arbore de decizie este studiat detaliu n a n n a a a sectiunea 2.3. Este propus o nou metod de selectare (sectiunea 2.3.1) a atributului de sepa rare, rezultatele obtinute aceast sectiune ind detaliate [PN02a, PJN05]. Metoda a fost n a n implementat mediul Expert System Creator iar rezultatele experimentale sunt prezentate a n n sectiunea 2.3.2 este propus o nou metod de agregare a tabelei de incident, ce Tabela 2.6. In a a a a st la baza calculelor din metoda Voting, pe baza cuburilor OLAP [PJN05]. ultima sectiune a In a capitolului (2.4) sunt studiate metodele de generalizare a arborelui de decizie i este prezentat s un sumar comparativ al acestora. Capitolul 3 prezint mediul de dezvoltare al sistemelor bazate pe cunotinte Expert System a s Creator. Focalizarea principal a mediului este pe uurint exploatare, testarea i depanarea a s a n s modelelor construite, versionarea modelelor i integrarea componentelor. sectiunea 3.1 sunt s In punctate motivatia i obiectivele platformei, extrase din [PN00]. Sectiunea 3.2 prezint arhi s a tectura sistemului i principalele module constituente, rezultate prezentate lucrrile [Pop00a, s n a Pop00b, PN02b]. Sectiunea urmtoare descrie detaliu editoarele modelelor de cunotinte a n s care ofer o interfat grac pentru faciliti de editare, depanare, trasare, vizualizare avansat a a a at a i vericare a corectitudinii, rezultate publicate mai multe lucrri [PN02a, PN03, Pop00a, s n a Pop02a, PN04]. Sectiunea 3.4 propune o solutie bazat pe generatoare de cod vederea in a n tegrrii nivelelor unui sistem bazat pe cunotinte [PN02b, PN02c, Pop01]. Reutilizarea codului a s existent (C++/Java) este facilitat prin intermediul gestionarului de dictionare, iar shell-urile a de sisteme expert (JESS/CLIPS) sunt suportate ca motoare de inferent pentru seturile de rea guli de productie create. Sectiunile urmtoare descriu alte functionaliti ale sistemului, precum a at managementul versiunilor sistemului (3.6) [Pop02b], accesul i rationamentul pe baza datelor s primare stocate baze de date relationale (3.7) [PNP02] i suportul pentru generarea automat n s a a documentatiei (interne) sistemului (3.8). sectiunea 3.9 este descris metodologia de dezvol In a tare a sistemelor de cunotinte folosind acest mediu [PN03]. anexa A este propus prototipul s In

INTRODUCERE

15

unui sistem bazat pe cunotinte pentru generarea automat a documentelor juridice. s a capitolul 4 este prezentat un sistem de asistare a utilizatorilor procesului de descoperire In a cunotintelor din bazele de date folosind o arhitectur multi-agent i un rationament orientat s a s sectiunea introductiv sunt identicate cele mai task detaliat [SNP98, SNP01b, SNP01a]. In n a importante probleme ale procesului de descoperire de cunotinte i sunt analizate abordrile s s a continuare, sunt sumarizate obiectivele platformei, avantajele oferite de un moprecendente. In del multi-agent [SNP01b] i este denit scenariul pentru rezolvarea problemei de descoperire de s cunotinte. Sectiunea 4.2.1 descrie etapa de analiz a sistemului care s a ncepe cu realizarea diagramei de utilizare, continu cu diagrama agentilor i identicarea principalele tipuri de agenti a s i se s ncheie cu identicarea capabilitilor i interactiunilor at s ntre agenti, detaliate i [PNS06]. s n a a Sectiunea 4.2.2 prezint unele aspecte ale proiectrii sistemului folosind platforma multi-agent JADE, cum ar facilitarea agentilor [SNP05] i reprezentarea bazei de cunotinte a sistemului. s s sectiunea 4.2.3 este prezentat o ontologie original pentru modelarea procesului de descoIn a a perire de cunotinte. Principalele diferente fat de ontologiile propuse anterior sunt modelarea s a etapelor procesului CRISP-DM i includerea unui model de calitate pentru modelele create. s In sectiunea 4.2.4 sunt furnizate detalii despre interactiunile dintre agenti i implementarea aces s tora. Sectiunea 4.3 analizeaz problema evalurii calitii sistemelor bazate pe cunotinte i a a at s s este propus un model de calitate original pentru modelul arbore de decizie, bazat pe metrici a de calitate. Sectiune 4.4 prezint un studiu de caz asupra evolutiei sistemului la extragerea cunotintelor dintr-un set de date real. Ultima sectiune a capitolului prezint concluziile i s a s directiile viitoare de dezvoltare ale platformei. anexa A este descris procesul de dezvoltare i prototipul (dezvoltat integral folosind In s mediul i metodologia de dezvoltare Expert System Creator) unei aplicatii pentru redactarea s asistat a documentelor juridice, realizat ca un sistem bazat pe cunotinte. anexa B sunt a a s In detaliate cteva din diagrame UML pentru ontologia procesului de descoperire de cunotinte din a s bazele de date. Cele mai importante contributii originale se refer la: denirea i studiul grafului de a s dependent extins pentru seturi de reguli de productie; suportul arborii i tabelele de dea n s cizie pentru interactiunea cu sistemele externe; metoda Voting de selectare a atributului de separare; reprezentarea regiunii de experient folosind reguli de asociere; analiza, proiectarea a i implementarea unui mediu vizual de dezvoltare pentru sistemele bazate pe cunotinte (Exs s pert System Creator); propunerea unei arhitecturi multi-agent (AgentDiscover [PNS06]) pentru asistarea utilizatorilor descoperirea de cunotinte din bazele de date i modelarea bazat pe n s s a ontologii a procesului de descoperire a cunotintelor. Rezultatele teoretice au fost validate prin s realizarea unor prototipuri domeniile: medii de dezvoltare sisteme inteligente, descoperirea de n cunotinte din baze de date, modele multi-agent, e-commerce, interfete inteligente pentru calcul s tiintic, arhitectura multi-agent pentru asistarea descoperirea cunotintelor, e-learning etc. s n s Dintre acestea amintesc: PCB Marketplace ([SNP01a]), SLINK ([SNP03]), NESS ([SNP01b]), INTENSE, MATOPS ([NSP05, SNP05]), LDDS (anexa A). Directiile i perspectivele de cercetare i s s mbuntire a modelelor propuse sunt prea at zentate nalul ecrui capitol i pot sumarizate evolutii asupra grafului de dependent n a s n: a extins, mbuntiri asupra metodei Voting, integrarea la nivel de componente binare a modelelor a at de cunotinte realizate cu Expert System Creator i realizarea practic a sistemului multi-agent. s s a

16

INTRODUCERE

Capitolul 1

Reprezentarea cunotintelor s Sintagme precum economie bazat pe cunotinte, organizatii bazate pe cunotinte, educatie a s s bazat pe cunotinte sunt des utilizate zilele noastre, cnd Internetul schimb pe zi ce trece a s n a a lumea care trim, iar n a mbriarea erei digitale este o provocare pentru toate organizatiile, at s de la rme mici sau mijlocii pn la nivel continental. De exemplu, programul eEurope reprea a zint schema Uniunii Europene pentru ghidarea procesului de tranzitie la era digital i pentru a as modernizarea sistemului educational vederea asigurrii tiintei de carte digitale generatiilor n a s viitoare. Astfel, unele dintre cele mai importante bogii ale organizatiilor zilele noastre au at n devenit cunotintele i know-how-ul existente cadrul lor. De aici rezult o nou provocare s s n a a creia trebuie s-i fac fat: implementarea unui sistem bazat pe cunotinte care s permit a a a a s a a utilizarea, capitalizarea i protectia cunotintelor la nivelul s s ntregii organizatii. Acest capitol va aborda problema obtinerii i reprezentrii cunotintelor sistemele de calcul. s a s n Prima sectiune a acestui capitol trece revist cele mai cunoscute modele de reprezen n a tare a cunotintelor, prezentnd avantajele i dezavantajele ecrei abordri. Sectiunea a doua s a s a a introduce fundamentele teoretice ale reprezentrii datelor primare (instante i atribute) i ale a s s cunotintelor (propozitii elementare, clasicatori) sistemele de calcul. Sectiunea urmtoare s n a este dedicat modelului set de reguli. Pentru a nceput sunt introduse bazele teoretice ale modelului, dup care este descris graful de dependent extins i proprietile acestuia. Modelul a a s at arbore de decizie este prezentat detaliu sectiunea a patra; dup introducerea fundamentele n n a teoretice sunt trecuti revist cei mai cunoscuti algoritmi de constructie automat a arborilor n a a din seturi de date, sectiunea ncheindu-se cu scoaterea evident a constructiei incremenn a tale. Sectiunea urmtoare descrie detaliu modelul tabel de decizie. sectiunea a asea a n a In s sunt prezentate principalele extensii (noduri/celule de actiune i suportul pentru rationamentul s aproximativ) aduse modelelor clasice. In ncheiere sunt prezentate concluziile i directiile de s cercetare viitoare.

1.1

Modele de reprezentare a cunotintelor s

Figura 1.1 prezint ierarhia cunotintelor. La nivelul cel mai de jos se a datele primare a s a (eventual perturbate de zgomote, erori, incertitudine, valori lips etc.) stocate de obicei baze a n de date. Nivelul urmtor realizeaz o structurare a datelor primare informatii bazate pe a a n 17

18

REPREZENTAREA CUNOSTINTELOR

Meta CunostinteSisteme bazate pe cunostinte

Management Information Systems

Cunostinte despre cunostinte Cunostinte Reprezentarea unui domeniu Aplicabilitate in rezolvarea problemelor Informatie Volum mai scazut, Valoare mai ridicata Cu inteles, Bazat pe Context

Baze de date

Date (eventual cu zgomote) Volum mare, Valoare scazuta, Fara inteles Pot contine articole irelevante care "ascund" datele importante

Figura 1.1: Ierarhia cunotintelor s context. Nivelele cunotintelor i meta-cunotintelor alctuiesc sistemele bazate pe cunotinte, s s s a s care datele primare au fost prelucrate, curate i sintetizate structuri de nivel superior. n at s n Sistemele bazate pe cunotinte sunt sisteme care efectueaz un task (sarcin) prin aplicarea s a a unor reguli empirice unei reprezentri simbolice a cunotintelor (Jackson [Jac99]). O denitie a s mai larg a sistemelor bazate pe cunotinte este urmtoarea: sistemele bazate pe cunotinte sunt a s a s sisteme software complexe care sunt programate s imite modul uman de rezolvare a problemelor a folosind mijloace specice inteligentei articiale i avnd acces la o baz de cunotinte despre s a a s In s un subiect particular1 . cadrul acestor sisteme sunt codicate mai multe tipuri de cunotinte [Neg96b]: cunotinte procedurale (cum s rezolvm o problem): reguli, strategii, agende, proceduri s a a a i functii; s s a cunotinte declarative (ce este cunoscut despre problem): concepte, obiecte, fapte; cunotinte bazate pe motenire (descriu organizarea cunotintelor): pot de dou tipuri: s s s a ne-structurate: retele semantice structurate: cadre, reprezentri centrate obiect a meta-cunotinte (cunotinte despre cunotinte): informatia de care este nevoie pentru a s s s alege cea mai bun alternativ rezolvarea unei probleme; a a n euristicile2 (reguli-de-aur care ghideaz rationamentul): criterii, metode sau principii pena tru a decide care dintre mai multe alternative de naintare a actiunii promite a cea mai cf. Wikipedia, http://en.wikipedia.org/wiki/Knowledge-based systems Euristic vine din greac (euriskein - a descoperi) i a s nseamn cazul nostru: proces semi-intuitiv ce conduce a n alegerea dintre diferite posibiliti functie de cunotinte empirice at n s 2 1

1.1 MODELE DE REPREZENTARE A CUNOSTINTELOR ecace vederea atingerii unei anumite inte [Pea85]. n t

19

Pentru reprezentarea cunotintelor se folosesc diverse modele, dintre care amintesc: sisteme s bazate pe reguli [Jac99, Nil80, DK77, BFK85], retele semantice [HTT87, Fin79, Tho92] i sis s teme bazate pe cadre [Min75], reprezentarea centrat obiect [Neg96b, Cor88, Fer89] i diverse a s tipuri de rationament logic (propozitional, calcul predicativ sau logic fuzzy) [And86, Qui79]. a Tripletele obiect-atribut-valoare sunt cunotinte declarative ce concretizeaz fapte cunoscute s a despre problema de rezolvat. Faptele pot de mai multe tipuri: mono-valorice, multi-valorice, fapte incerte sau fuzzy. Regulile [Jac99, Nil80, DK77, BFK85] sunt cunotinte procedurale de s tipul Premise Consecinte i vor descrise detaliu sectiunea 1.3. Retelele semantice s n n [HTT87, Fin79, Tho92] sunt grafuri care nodurile semnic obiecte iar arcele sunt relatiile n a dintre obiecte. Cadrele (frame-uri) [Min75] sunt structuri de date nrudite cu conceptul de clas din programarea orientat obiect i reprezint cunotinte comune obiectelor din sistem. a a s a s Reprezentarea centrat obiect [Neg96b, Cor88, Fer89] combin elemente de programare oriena a tat obiect cu modul de reprezentare bazat pe frame-uri, toate unitile de cunotinte ind a at s accesibile direct i pot exploatate prin aplicarea de inferente (ltrare, proceduri, clasicare s a s s etc). Logica [And86, Qui79] este cea mai veche form de reprezentare a cunotintelor i poate propozitional (avnd la baz operatorii logici AND (), OR (), NOT (), IMPLIES (), a a a EQUIVALENCE ()), calcul predicativ (adaug logicii propozitionale predicate i argumente, a s variabile de cuanticare i cuanticatorii universal () i cel existential ()) sau logic fuzzy. s s a Avntul luat anii 90 de domeniul data mining a contribuit la aparitia unor noi modele a n de reprezentare a cunotintelor sau la revitalizara unor modele mai vechi, cum ar arborii s a de decizie [BFOS84, Qui86, Qui93], reprezentrile bazate pe instante (de exemplu, metoda k n Nearest Neighbor) [WF00], clusterele [JMF00, WXS03, DLJ00] sau retelele neuronale ( cazul problemelor de regresie neliniar spre exemplu) [Bis03, Ska96, WF05]. Pentru data mining au a fost propuse mai multe denitii, dintre care amintesc dou: a Denitia 1.1.1. Data mining este procesul de descoperire a diferitelor modele, informatii agre gate i valori derivate dintr-o colectie de date dat. (Kantardzic, 2003 [Kan03]) s a Denitia 1.1.2. Data mining este procesul de a extrage tendinte sau abloane din date i este s s sarcina esential a procesului mai larg, de descoperire a cunotintelor bazele de date (KDD), a s n denit prin: extragerea netrivial a informatiilor implicite, necunoscute i potential utile din a s date. (Frawley W.J., Piatetsky-Shapiro & Matheus, 1991 [FPSM91]) Cele mai populare modele de reprezentare a cunotintelor sunt arborii de decizie, tabelele s de decizie i seturile de reguli, toate sintetizate Tabela 1.1 [Pop00a]. Pentru ecare model s n sunt prezentate avantajele oferite, precum i problemele pe care le ridic. timp ce expertul s a In uman si reprezint mai uor propriile cunotinte sub forma seturilor de reguli, tabelele de decizie a s s ofer posibilitatea analizei automate a sistemului, vericarea consistentei [PN02a] sau analiza a vulnerabilitii bazei de cunotinte la erori de msurare [Col92]. Arborii de decizie sunt structuri at s a de date pentru care exist numeroi algoritmi de construire, cu performante foarte bune, precum a s i algoritmi de traversare i conversie limbaje de programare de nivel s s n nalt (C, C++, Pascal, Java sau SQL [AGI+ 92, Qui86, Qui82]). Un dezavantaj al arborilor de decizie constituie l faptul c nu ofer o reprezentare accesibil expertilor umani, schimb ofer, de exemplu, o a a a n a

20Reprezentarea cunotintelor s Tabele de decizie Caracteristici

REPREZENTAREA CUNOSTINTELOR

Arbori de decizie

Seturi de reguli reguli de productie, de asociere, cu exceptii, meta-reguli, reguli incerte etc. Clustere

Analiza automat a corectitudinii a Form compact de reprezentare a a Uor de vizualizat i eles de ctre un expert uman s s nt a Uor de reprezentat i generat limbaje de programare de nivel s s n nalt Pot construiti automat din seturi mari de date folosind algoritmi speci de inductie Sunt robuti chiar i cazul care setul de antrenament contine s s n n erori sau valori lips a Trateaz att atribute categoriale ct i continue a a a s Uor de construit i asimilat de ctre expertii umani s s a Exist numeroase sisteme functionale, de dimensiuni mari a

Construite folosind algoritmi de aare nesupervizat nvt a Folosesc tehnici de vizualizare a datelor De obicei sunt transformate arbori de decizie n nainte de generarea lor ntr-un limbaj de nivel nalt

Tabela 1.1: Modele de reprezentare a cunotintelor s acuratete ridicat fat de alte modele [LLS97, Mur95]. [PN00] sunt prezentate pe scurt cele a a In mai importante caracteristici ale acestor modele.

1.2

Fundamente teoretice

aceast sectiune sunt prezentate bazele teoretice ale modelelor de clasicare (arbori de In a decizie, seturi de reguli i tabele de decizie) [Pop02c]. Modelele prezentate mai sus sunt create s pe baza datelor primare care sunt prezentate sub forma unei multimi de cazuri (instante). Un caz reprezint un exemplu independent al unui concept general. Fiecare caz este caracterizat a printr-un set de atribute care msoar diferite aspecte ale unui caz. Cu toate c atributele sunt a a a de cele mai diferite tipuri (numerice, caractere, iruri de caractere, de tip dat calendaristic, s a a imagini, sunete, video etc.), problemele de inteligent articial i data mining opereaz cu dou a as a a grupe importante de atribute: continue (numerice, cantitative) i categoriale (calitative). s Denitia 1.2.1. Fie A un atribut. Prin domeniul atributului A (notat prin dom(A)) se elege nt multimea valorilor valide pentru acest atribut. Pentru atributele continue dom(A) = R, adic multimea de valori este innit, iar pentru a a cele categoriale dom(A) = {v1 , v2 , . . . , vk }, cu alte cuvinte atributul poate lua valori dintr-un set nit i bine precizat de valori. Pentru simplitate vom nota elementele unui domeniu categorial s prin {1, 2, . . . , k}. Un atribut A se numete boolean dac Card(A) = 2, iar valorile sale sunt s a denumite {adevrat, fals}. a

1.2 FUNDAMENTE TEORETICE

21

Denitia 1.2.2. Modelarea predictiv folosete modele pentru prezicerea valorilor unui atribut a s (sau a mai multor atribute), numit atribut int, pe baza valorilor atributelor dintr-un set de t a atribute numite atribute predictoare. Dac atributul prezis este categorial, atunci problema se a numete clasicare iar dac este de tip continuu atunci problema se numete regresie. s a s Clasicarea i regresia au fost studiate pe larg domenii precum statistica [Bra99, DHMS02, s n BH99], recunoaterea formelor (pattern recognition) [DG96, Kei90, Bis03], machine learning s [Mit97, BH99, MMM+ 83], retele neuronale [BH99, Bis03, Ska96], regresie liniar i regresie li as a a niar generalizat [BFOS84, Gro03]. Aceast sectiune nu si propune s detalieze aceste subiecte, a a ci doar s prezinte conceptele i rezultatele de baz necesare derivrii rezultatelor originale prea s a a zentate aceast lucrare. n a Denitia 1.2.3. Un clasicator este o functie d : dom(A1 ) . . . dom(Am ) dom(C) Fie AC = dom(A1 ) . . . dom(Am ) dom(C) i P : AC [0, 1] o distributie de probabis litate, adic o functie care asigneaz probabiliti evenimentelor de tipul: < t.A1 , . . . , t.Am > a a at dom(A1 ) . . . dom(Am ) t.C dom(C). Valorile acestor probabiliti sunt obtinute e de at la un expert uman domeniul respectiv, e din observatii empirice ale fenomenului modelat. n De exemplu, P (< debit = ridicat, f orma angajare = independent, risc = mare >) = 0.8, adic o persoan arcinat va a a ns a ntotdeauna de sex feminin. Denitia 1.2.4. Un element t =< t.A1 , . . . , t.Am , t.C > AC se numete caz. Prin set de s antrenament D se elege o multime de cazuri alese mod aleator din multimea AC. nt n Aadar, setul de antrenament este constituit dintr-o multime de cazuri despre care tim clasa s s creia acestea apartin, cu o anumit certitudine. a a Denitia 1.2.5. Se numete rata de clasicare greit Rd a clasicatorului d, probabilitatea s s a P (d(< t.A1 , . . . , t.Am >) = t.C). Rata de clasicare greit a unui clasicator reprezint probabilitatea ca, pentu un caz, clasa s a a estimat de clasicator s e diferit de cea real. a a a a Denitia 1.2.6. Vom numi propozitie elementar relatia pij : Ai = vij , unde vij dom(Ai ) iar o a propozitie elementar asociat cu atributul int se numete propozitie elementar de clasicare a a t a s a (cj : C = vj , unde vj dom(C)). continuare vom nota cu pi multimea propozitiilor elementare asociate cu atributul Ai i In s cu c multimea propozitiilor elementare de clasicare. Multimea tuturor propozitiilor elementare asociate cu toate atributele Ai se numete multimea propozitiilor elementare cauzale. s Propozitia 1.2.1. Negatia unei propozitii elementare este o disjunctie de propozitii elementare. Demonstratie. a) Fie Ai un atribut categorial i pij : Ai = vij o propozitie elementar. Dac s a a nu este adevarat, atunci a nseamna c Ai = vij , aadar exist un v dom(Ai )\vij astfel at a s a nc Ai = v. De aici rezult c a a pij pik [Ai = vik ]k=j k=j

22

REPREZENTAREA CUNOSTINTELOR

b) Fie Ai un atribut continuu. acest caz, dom(Ai ) ind innit vom considera o discretizare In nit a sa. Vom deni valorile vij , j = 1, N , ca subintervale disjuncte ale domeniului felul a n urmtor: a vij = , j = 1, N ; vij vik = , j, k = 1, N ; N j=1 vij

= dom(Ai ).

Deoarece acest caz vij sunt multimi (subintervale), vom redeni propozitia elementar n a nlocuind relatia de egalitate cu cea de apartenent la un interval, adic pij : Ai vij . a a Cu aceste modicri, demonstratia de la cazul categorial (punctul a) se aplic nemodicat a a a pentru cazul continuu.

1.3

Reguli de productie

Setul de reguli reprezint unul dintre cele mai folosite modele de reprezentare a cunotintelor. a s Exist mai multe tipuri de reguli, dintre care amintesc reguli de productie, reguli de productie a cu exceptii i reguli de asociere (tabela 1.2 sintetizeaz principalele caracteristici ale acestor s a reguli). continuarea acestei sectiuni vor prezentate detaliu regulile de productie. In n

1.3.1

Bazele teoretice ale regulilor de productie

Regulile de productie sunt un formalism utilizat la nceput teoria automatelor, limbajele n n formale i proiectarea limbajelor de programare. anii 40, Post [Pos43] a prezentat o prim s n In a formalizare a sistemelor bazate pe reguli care va succint prezentat i aceast sectiune. a s n a Aceste sisteme au fost introduse modelele psihologice pentru prima dat anul 1972 de ctre n a n a Newell i Simon [NS72], iar modelarea sistemelor expert de ctre Buchanan i Feigenbaum s n a s 1978 [BF78]. teoria sistemelor expert se mai numesc i reguli conditie-actiune i sunt n In s s din punct de vedere formal reguli gramaticale pentru manipularea irurilor de simboluri, adic s a reguli de rescriere. Post [Pos43] a formalizat teoria sistemelor bazate pe reguli, pe care le-a numit sisteme canonice, ca ind sisteme bazate pe un alfabet A (din care sunt construite irurile), un set s de axiome (o axiom este un ir peste alfabetul A) i un set de reguli de rescriere forma a s s n 1 $1 . . . m $m 1 $1 . . . n $n , unde: i i i sunt iruri xe, 1 i m ind de obicei null s s s unele (sau toate) iruri i sau i pot null s $i este un ir variabil care poate null s ecare $i este nlocuit cu un $i

1.3 REGULI DE PRODUCTIE

23

Tip regul a Regul de productie a

Regul de productie a cu exceptii

Caracteristici construite manual de ctre a experti sunt executate de ctre moa toare de inferent specice (ex: a JESS, CLIPS, OPS5 etc.) construite manual de ctre a experti exist motoare de inferent a a care le suport a construite manual de ctre a experti exist motoare de inferent a a care le suport a

Exemplu if Forma angajare=Independent then Nivel risc=Mare

if Forma angajare=Salariat then Nivel risc=Sczut unless Nivel dea bit=Ridicat

Regul de productie a Fuzzy

Regul de asociere a

construite automat folosind algoritmi specici nu exist motoare de inferent a a pentru executia lor, ele avnd a doar un rol descriptiv

if (temperatura mare) then modica temperatura putin (CF 0.8), unde temperatura i modics a temperatura sunt variabile Fuzzy, iar CF reprezint factorul de certia tudine al regulii if Baze de date i Arbori de decizie s then Data Mining (c=0.9, s=0.05) i se citete: 90% dintre cititos s rii care au mprumutat crti despre a baze de date i arbori de decizie au s mprumutat i crti despre Data Mis a ning, iar acetia reprezint 5% din s a totalul cititorilor(c - condenta, s suportul)

Tabela 1.2: Tipuri de reguli

24

REPREZENTAREA CUNOSTINTELOR

Partea stng a unei reguli de rescriere (1 $1 . . . m $m ) se numete antecedent, iar para a s tea dreapt (1 $1 . . . n $n ) se numete consecint. Aadar, forma general a unei reguli de a s a s a productie este: if antecedent then consecint. a De exemplu, sistemul canonic A = {a, b}, axiome = {ab} i reguli = {(P 1)$ a$b} va s genera multimea {an bn , n 1}. Cu toate c sistemele canonice par triviale, ele se regsesc a a toate calculele logicii i matematicii ind de fapt nite seturi de reguli care denesc modul n s s care sunt manipulate simbolurile. exemplul anterior, pornind de la axioma ab se poate n In deduce, prin aplicarea regulii P 1 teorema aabb. Semantica simbolurilor alfabetului A depinde de problema/teoria modelat. Mai mult chiar, Minsky [Min72] a demonstrat c orice sistem a a formal poate realizat ca un sistem canonic.

1.3.2

Reguli de productie folosite problema clasicrii n a

Regulile de productie folosite sistemele expert difer de regulile de rescriere prezentate mai n a sus cateva aspecte superciale, a principiile fundamentale i formale rmn neschimbate. n ns s a a De exemplu, nu suntem interesati de gramatica structurilor simbolice per se, ci mai degrab a construirea unei reprezentri a problemei i transformarea ei pn cnd satisface un criteriu n a s a a a care s spun Aceasta este o solutie pentru problema cauz. Setul de reguli de productie a a n a (numit i sistem de productie) este o colectie de una sau mai multe reguli de productie. s cazul seturilor de reguli de productie folosite sistemele expert, alfabetul A sistemului In n canonic este nlocuit de un vocabular format din simboluri sau atomi care reprezint: a multimea O, a numele obiectelor din domeniu; multimea P , a numele proprietilor care reprezint atributele obiectelor; at a multimea V , a valorilor admisibile pentru proprietile din P . at Gramatica folosit sistemele expert folosete de obicei triplete de forma obiect-atributa n s valoare, adic (o, p, v), unde o O, p P i v V . terminologia sistemelor expert a s In aceste triplete se mai numesc i fapte, iar faptele initiale (de pornire) ale sistemului expert s sunt echivalentul axiomelor din sistemele canonice. Pentru a reduce numrul faptelor care rea prezint proprietile unui obiect (notat cu o) se folosete unele sisteme forma generalizat a at s n a (o, p1 , v1 , . . . , pn , vn ). sistemele moderne bazate pe reguli (JESS [FH] or CLIPS [Gia93]), fapIn tele care au aceleai atribute (de exemplu toate faptele ce denesc cursurile ce se predau la o s universitate) sunt prezentate ca instante ale unor structuri de date ce reunesc aceste atribute, numite abloane (template). s Regulile de productie sunt construite din propozitii elementare, clasicri i o multime de a s propozitii elementare intermediare. Propozitiile elementare intermediare pot utiliza atribute intermediare, adic atribute diferite de cele care intervin clasicare i reprezentarea sisa n s n temului. Antecedentul unei reguli este o conjunctie de propozitii elementare (cauzale sau in termediare) sau negatii ale propozitiilor elementare (cauzale sau intermediare). Consecinta (consequent) unei reguli este o propozitie elementar de clasicare sau intermediar. a a Pentru nceput, vom prezenta un scurt exemplu: evaluarea nivelului de risc al unui credit pentru un client al unei bnci. Acesta este evaluat de ctre expertii bancari pe baza ctorva a a a indicatori, cum ar : nivelului debitelor, nivelului veniturilor i forma de angajare ale clientului. s

1.3 REGULI DE PRODUCTIE Nr 1 2 3 4 5 6 7 8 9 10 R1: if Forma R2: if Forma R3: if Forma risc=Sczut a Nivel debit Nivel venit Form angajare Nivel risc a Ridicat Ridicat Independent Mare Ridicat Ridicat Salariat Mare Ridicat Sczut a Salariat Mare Sczut a Sczut a Salariat Scazut Sczut a Sczut a Independent Mare Sczut a Ridicat Independent Mare Sczut a Ridicat Salariat Scazut Mediu Ridicat Independent Mare Mediu Ridicat Salariat Scazut Mediu Scazut Salariat Scazut angajare=Independent then Nivel risc=Mare angajare=Salariat and Nivel debit=Ridicat then Nivel risc=Mare angajare=Salariat and Nivel debit=(Sczut or Mediu) then Nivel a

25

Figura 1.2: Date de antrenament i setul de reguli de productie corespunztor s a Aceti indicatori vor forma setul de atribute predictoare. Atributul prezis va valoarea pentru s nivelul de risc al creditului. Cele trei atribute plus nivelul de risc vor deni i cele patru s abloane ce modeleaz sistemul nostru. Fiecrui ablon vom putea ataa ulterior informatiile s a a s i s suplimentare de care avem nevoie vederea realizrii unor reguli mai complexe. De exemplu, n a ablonului forma de angajare putem ataa ulterior informatii referitoare la perioada/durata s i s acestei forme, tipul angajatorului (dac acesta exist) rm de mici dimensiuni, corporatie a a a multi-national, institutie public denumirea angajatorului etc. Folosind un set de date de a a antrenament care sunt cunoscute att valorile pentru atributele predictoare ct i pentru n a a s nivelul de risc, expertul uman va construi un set de reguli de productie precum cel din Figura 1.2. vederea analizei i formalizrii puterii de expresie a unui set de reguli, Apt et al. [ABW88] In s a introduce notiunea de graf de dependent. a Denitia 1.3.1. Graful de dependent pentru un set de reguli este denit ca perechea (N, A), a unde: a N este multimea de noduri, un nod ind reprezentat de o regul a setului de reguli; A este multimea de arce, un arc ind denit cu sursa nodul N 1 i destinatia nodul n2 n s n cnd consecinta regulii corespunztoare nodului n1 apare atecendentul regulii nodului a a N 2. Pentru exemplul de set de reguli prezentat Figura 1.2, graful de dependent va contine n a trei noduri (corespunztoare regulilor R1 - R3) iar multimea de arce va vid deoarece nici a a unul dintre atributele ce apar antecedentul celor trei reguli (Form angajare i Nivel debit) n a s nu apare consecinta nici uneia dintre reguli. vederea n In mbogirii informatiei exprimate at n graful de dependent, lucrarea de fat este propus o extensie a acestuia, i anume graful a n a a s de dependent extins (prezentat [PN02b, PN03] sub numele de graf semantic). a n Inainte de

26

REPREZENTAREA CUNOSTINTELOR

Figura 1.3: Graf de dependent extins a introducerea acestuia, vom face urmtoarea observatie: orice atribut poate reprezentat printra un ablon prin urmtoarea constructie (prezentat sintax JESS): s a a n a (deftemplate AttributeName (slot value)) continuarea acestei sectiuni vom folosi termenul de ablon pentru a desemna e un atribut In s simplu, e o structur de date complex. a a Denitia 1.3.2. Graful de dependent extins (GDE) pentru un set de reguli este denit ca a perechea (N, A), unde: N este multimea de noduri, un nod ind reprezentat de o regul sau un ablon din sistem; a s A este multimea de arce; un arc este denit cu sursa nodul n1 i destinatia nodul n2 dac s a una din urmtoarele conditii este a ndeplinit: a consecinta regulii corespunztoare nodului n1 este folosit ablonul corespunztor n a s a nodului n2 dac ablonul corespunztor nodului n1 este folosit atecendentul regulii nodului a s a n n2. Figura 1.33 prezint GDE pentru exemplul din Figura 1.2. GDE aduce informatii suplimena tare asupra structurii semantice a ntregului sistem deoarece nu se limiteaz doar la reprezentarea a relatiile dintre reguli, ci i prin ce abloane se face comunicare dintre dou reguli. De exemplu, s s a ntre dou reguli pot exista dou relatii de dependent realizate prin abloane diferite. Dac a a a s a modelul standard al grafului de depedent aceast informatie se pierde, GDE va pune n a a n evident aceast situatie. Aadar, GDE dezvluie proiectantilor bazei de cunotinte cteva tia a s a s a puri de reguli interesante, precum: reguli izolate, reguli originator, reguli terminale sau reguli pseudo-recurente.3

Aceasta este o captur de ecran obtinut timpul rulrii aplicatiei Expert System Creator (vezi capitolul 3) a a n a

1.3 REGULI DE PRODUCTIE

27

Denitia 1.3.3. Fie n N un nod al grafului de dependent extins. Vom nota cu in(n) = a {(, n) A}, respectiv out(n) = {(n, ) A} multimea de arce care intr nodul n, respectiv a n care ies din nodul n. continuare, sunt analizate cteva situatii speciale care se pot aa nodurile GDE. In a n Dac Card(in(n)) = 0 i Card(out(n)) = 0, atunci nodul n va denumit izolat. Dac a s a nodul are asociat o regul, atunci regula nu comunic cu alte reguli sau abloane ale sisa a a s temului. De exemplu, astfel de reguli pot rezulta urma reproiectrii bazei de cunotinte, n a s iar eliminarea lor va mri claritatea bazei de cunotinte. Dac nodul are asociat un ablon a s a s nseamn c acel ablon este nefolosit regulile sistemului (cu toate acestea, ablonul ar a a s n s putea folosit structurile procedurale - de tipul functiilor - ale sistemului). n Dac Card(in(n)) = 0 i Card(out(n)) > 0, atunci nodul n va denumit originator. Dac a s a nodul are asociat o regul, atunci avem de-a face e cu o regul de pornire a sistemului, a a a care este activat implicit la pornirea motorului de inferent, e cu o regul ce nu va a a a activat niciodat, numit i regul moart. Dac nodul are asociat un ablon, atunci a a as a a a s respectivul ablon abstactizeaz faptele initiale ale sistemului (axiomele). s a Dac Card(in(n)) > 0 i Card(out(n)) = 0, atunci nodul n va denumit terminal. Dac a s a nodul are asociat o regul atunci regula nu va inuenta/activa alte reguli, ea ind activat a a a anumite conditii i va executa sarcini precum: scrierea n s ntr-un ier, accesul la o baz de s a date, area de mesaje informative utilizatorilor etc. Dac nodul are asociat un ablon, sa a s acesta va reprezenta de obicei rezultatele nale ale executiei sistemului. Alte informatii utile despre structura bazei de cunotinte se pot obtine din studiul ciclurilor s din graf. O cale ntr-un graf este o traversare de la un nod la altul, unde la ecare pas se folosete s un arc al grafului, adic formal: a Denitia 1.3.4. O cale (directionat) este o secvent de noduri din N {n1 , n2 , . . . , nk } astfel a a at i = 1, k 1 : (ni , ni+1 ) A. Un ciclu este este o cale nc nchis, adic una care n1 = nk . a a n Numrul de arce dintr-o cale (ciclu) se numete lungimea cii (ciclului). a s a Dac exist un ciclu de lungime 2 GDE a a n nseamn c graful contine dou noduri, n i n a a a s astfel at exist un arc de la n la n i un alt arc ce pleac din nodul n i ajunge n. Din nc a s a s n denitia GDE rezult c unul dintre noduri va avea asociat o regul iar cellalt un ablon, a a a a a s ntre cele dou noduri existnd o dependent bidirectional. Vom denumi regula implicat aceast a a a a a n a relatie regul pseudo-recurent, deoarece modicndu-i propriile premise de intrare, regula va a a a s putea cauza o auto-activare. O atentie deosebit trebuie acordat acestor reguli deoarece ele a a pot cauza bucle innite sau blocaje functionarea sistemului. n Propozitia 1.3.1. Orice ciclu a GDE are lungime par. a Demonstratie. Presupunem c exist un ciclu de lungime impar GDE, {n1 , n2 , n3 , n1 }. Pre a a a n supunem c a nodul n1 are asociata o regula. (1.3.1)

28

REPREZENTAREA CUNOSTINTELOR

Din denitia GDE (denitia 1.3.2) rezult c nodul n2 are asociat cu el un ablon (deoarece un a a s arc al GDE conecteaz o regul cu un ablon, sau invers). Similar, nodul n3 va avea asociat a a s a cu el o regul, i nodul n1 un ablon, ceea ce este contradictie cu presupunerea initial 1.3.1. a s s n a Dac presupunem c nodul n1 are asociat un ablon, printr-un rationament similar vom a a s ajunge tot la o contradictie. Se observ c un ciclu de lungime 4 evidentiaz o dependent ciclic a a a a a ntre dou reguli ale a sistemului. Denitia 1.3.5. Un graf care nu contine nici un ciclu se numete aciclic, adic n N nu s a exist nici o cale nevid care s inceap i s se termine n. a a a as a n Denitia 1.3.6. Un set de reguli se numete bine-format dac graful de dependent (extins) s a a este aciclic. Un alt concept introdus literatur, tot pe baza grafului de dependent, este cel de sistem n a a straticat (Apt et al. [ABW88]), i anume: un arc din A este etichetat pozitiv sau negativ dup s a cum consecinta regulii r1 apare ca un literal pozitiv sau negativ antecedentul lui r2. Prin n denitie, un sistem straticat nu are cicluri cu arce negative, dar poate avea cicluri formate doar din arce pozitive. Aadar, conceptul de bine-formare introdus denitia 1.3.6 este mai tare s n dect cel de straticare din [ABW88]. [Col99] se arat c pentru orice sistem propozitional a In a a straticat exist un sistem cu graful de dependent aciclic care are acelai model. a a s

1.4

Arbori de decizie

Arborii de decizie (denumiti alternativ i arbori de clasicare) constituie una dintre cele mai s populare i bine formalizate abordri pentru problema clasicrii. continuarea acestui capitol s a a In sunt prezentate fundamentele teoretice ale arborilor de decizie, precum i cei mai cunoscuti s algoritmi pentru construirea arborilor de decizie din seturi mari de date cu unele mbuntiri a at aduse acestora. Un exemplu de arbore de decizie este prezentat Figura 1.44 , i anume arborele de decizie n s echivalent cu sistemul de reguli din Figura 1.2. Acest arbore de decizie poate construit e de ctre expertul uman, e mod automat folosind unul din algoritmii descrii aceast sectiune. a n s n a acest exemplu, algoritmul pentru constructia arborelului de decizie a determinat c atriIn a butul cel mai semnicativ pentru predictia riscului este Forma angajare. Ca urmare, prima ramicare in arbore este fcut dup acest atribut. Nodul cu {Forma angajare = Independent} a a a este nod frunz deoarece toate exemplele din acest nod sunt clasicate mod unic, i anume a n s Mare. Cellalt nod, corespunztor {Forma angajare = Salariat} nu este nod frunz deoarece a a a are dou exemple clasicate ca Mare i patru ca Sczut. Prin urmare, pe aceast directie este a s a a nevoie de stabilirea unei noi ramicatii i aceasta este fcut dup atributul Nivel debit. s a a a4

Aceasta este o captur de ecran obtinut timpul rulrii aplicatiei Expert System Creator (vezi capitolul 3) a a n a

1.4 ARBORI DE DECIZIE

29

Figura 1.4: Exemplu de arbore de decizie

1.4.1

Bazele teoretice ale arborilor de decizie

Arborii de decizie sunt folositi ca modele predictionale probleme de clasicare, timp n n aceast sectiune vor prezentate fundamentele ce arborii de regresie cele de regresie. In n a matematice ale arborilor de decizie [Pop02c]. Fie deci C atributul categorial int (cel ale crui t a a valori vor prezise de arborele de decizie) i {Ai | i = 1 . . . m} atributele predictoare. s Denitia 1.4.1. Se numete arbore de decizie un graf aciclic directionat care realizeaz functia s a unui clasicator. Formal, un arbore de decizie AD este format din perechea {N, A} cu urma toarele proprieti: at N = {ni | i = 1 . . . k} se numete multimea de noduri ale arborelui s A = {(n1 , n2 ) | n1 , n2 N } se numete multimea de arce ale arborelui s !R N astfel at Card({(m, R) A}) = 0 i se numete nodul rdcin al arborelui nc s s a a a n N, n = R Card({(m, n) A}) = 1 Dac (n1 , n2 ) A, nodul n1 se numete nod printe iar n2 se numete nod u. Rdcina a s a s a a unui arbore (notat cu R denitia 1.4.1) este unic pentru un arbore i este nodul care nu a n a s are nici un nod printe. Orice alt nod are exact un printe i zero, unul sau mai multi i. Se a a s numete nod frunz un nod fr nici un u. Orice alt nod diferit de nodul rdcin i nodurile s a aa a a as frunz se numete nod intern (sau nod de decizie). Fiecare nod frunz al unui arbore de decizie a s a are asociat o propozitie elementar de clasicare (eticheta clasei corespunztoare clasicrii a a a a efectuate de calea de la rdcin pn la el). Un nod de decizie (intern) al unui arbore de a a a a a decizie nu poate contine un singur u deoarece acest caz nu ar mai avea loc nici o clasicare. n Un arbore de decizie se numete binar dac oricare nod al su are maximum doi i. s a a

30

REPREZENTAREA CUNOSTINTELOR

Denitia 1.4.2. O secvent de arce C = (n1 , n2 ), (n2 , n3 ), . . . , (nk1 , nk ) se numete cale a s n arbore de la nodul n1 la nodul nk de lungime k 1. Dac nk este un nod frunz, atunci calea a a se numete cale de clasicare. s Propozitia 1.4.1. Dac a ntre nodurile n1 i nk exist o cale, atunci aceasta este unic. s a a Demonstratie. Presupunem c exist C i C dou ci distincte de la n1 la nk . Prin urmare, a a s a a nj C nj c nj = nj , adic exist cel putin dou noduri distincte cele dou ci. Din a a a n a a a a s a a denitia 1.4.2 rezult c sunt arce (nj , nj+1 ) i (nj , nj+1 ) ale arborelui T . De aici rezult c nodul nj+1 are doi printi, ceea ce este contradictie cu denitia arborelui de decizie 1.4.1 a n (punctul 4). continuare, ecare nod intern n este etichetat cu un atribut predictor An numit atribuIn tul de separare (splitting attribute) i are asociat o multime de predicate de separare Qn = s a qnm | m = 1, M . Un predicat de separare qnm (splitting predicate) este denit astfel: dac An este un atribut numeric, qnm este de forma An am , unde am a se numete punct de separare pentru nodul n (split point) s dom(An ) i s

dac An este un atribut categorial, qnm este de forma An Sm , unde Sm dom(An ) i a s se numete multime de separare pentru nodul n (splitting subset). s Observatia 1.4.1. Pentru un atribut categorial, predicatul de separare qnm este o disjunctie de propozitii elementare pnj : An = vnj (vezi denitia 1.2.6). In a Observatia 1.4.2. vederea asigurrii consistentei arborelui, pentru un atribut categorial, sub multimile de separare Sm trebuie s e disjuncte. a Atributul de separare mpreun cu multimea predicatelor de separare formeaz a a mpreun a aa numitul criteriu de separare (splitting criterion) pentru nodul intern n. s Fiecare arc al arborelui are ca nod printe un nod de decizie p (sau nodul rdcin) i are a a a a s asociat un predicat de separare qpj apartinnd multimii de predicate de separare asociate nodului a printe. a continuare este introdus functia numit predicatul nodului astfel: In a a Denitia 1.4.3. Fiecrui nod n T vom asocia functia numit predicatul nodului a i a fn : dom(A1 ) . . . dom(Am ) dom(C) {true, f alse} astfel: fn (a1 , . . . , am , c) = true fp qpj dac n este nodul rdcin, a a a a dac n este nod u al lui p a

unde qpj este predicatul de separare corespunztor arcului (p, n) (qpj Qp ). a Informal, fn pentru un nod reprezint conjunctia predicatelor de separare a tuturor arcelor a de pe calea de la rdcin pn la acel nod. Deoarece ecare nod frunz este etichetat cu numele a a a a a a unei clase, acesta codic o regul de clasicare de forma fn c, unde c reprezint eticheta a a a nodului n. Astfel, ecare arbore T codic un clasicator sub forma functiei T : dom(A1 ) . . . a dom(Am ) dom(C) numit clasicator de tip arbore de decizie.

1.4 ARBORI DE DECIZIE

31

Denitia 1.4.4. Conjunctia tuturor predicatelor de separare asociate arcelor unei ci se numete a s regula cii. a Deoarece ecare predicat de separare este o disjunctie de propozitii elementare (observa ia 1.4.1) rezult c regula unei ci poate scris folosind propozitii elementare astfel: t a a a a k k k

pC i=1

qai ji i=1 j

paij i=1 j

[Ai = vij ]

Denitia 1.4.5. Se numete familie de cazuri asociate nodului n T (notat cu Fn ) multimea s a Fn = {t D | fn (t) = true} Cu alte cuvinte, Fn este multimea de cazuri din setul de antrenament D care urmeaz calea a de la rdcin la nodul n, atunci cnd sunt procesate de arbore. a a a a Denitia 1.4.6. Un arbore de decizie se numete complet dac s a n nod intern, predicatele de separare asociate acoper toate valorile domeniul atributului a de separare; n nod frunz, propozitia asociat cu el este adevrat. a a a a Cu alte cuvinte, arborele este complet dac pentru ecare propozitie elementar asociat cu a a a atributul de separare al unui nod intern exist un arc arbore. a n Problema constructiei unui arbore de decizie poate denit mod formal felul urmtor: a n n a ind dat un set de antrenament D (vezi denitia 1.2.4), s se gseasc un clasicator sub forma a a a unui arbore de decizie T astfel at rata clasicrilor greite RT (P ) s e minim. Hyal i nc a s a a s a n Rivest [HR76] demonstrau c problema construirii unui arbore de decizie optimal ( sensul minimizrii numrului de teste necesare clasicrii unui caz nou) este una NP-complex (NPa a a a dicil). Ei mai artau deasemenea c nu exist algoritmi ecienti pentru construirea acestor a a a a arbori optimali i prin urmare este necesar gsirea unor metode euristice pentru construirea s a a arborilor de decizie aproape optimali. fapt, din 1976 pna astzi numeroase metode i alIn a a s goritmi bazati pe euristice au fost propuse literatur pentru construirea arborilor de decizie. n a a a a s S.K. Murthy face [Mur98] o sintez inter-disciplinar (statistic, recunoaterea formelor, pron cesarea semnalelor, machine learning i retele neuronale) a metodelor de constructie automat s a a arborilor de decizie din multimi de date. continuarea acestei sectiuni va prezentat metoda Growing-Pruning, care denete scheIn a s letul pe care se bazeaz majoritatea metodelor de constructie automat a arborilor de decizie. a a Algoritmul general presupune dou faze constructia arborelui: a n faza de cretere: din setul de date de antrenament se construiete un arbore de decizie s s cuprinztor, de dimensiune mare; a faza de reducere (pruning): se determin dimensiunea nal a arborelui astfel at rata a a nc clasicrilor greite RT s e minim. a s a a

32

REPREZENTAREA CUNOSTINTELOR

TDTree(RootNode n, partition D, split selection method CL) Apply CL to D to nd the splitting criterion for n; if (n splits) then Use best split to partition D into D1 , D2 ; Create children n1 and n2 of n; TDTree(n1 , D1 , CL); TDTree(n2 , D2 , CL); endif

TDTree(RootNode n, partition D, split selection method CL) Apply CL to D to nd the splitting criterion for n; Let k be the number of children of n; if (k > 0) then Use best split to partition D into D1 , . . . , Dk ; Create k children n1 , . . . , nk of n; for all nk do TDTree(nk , Dk , CL); endif

Figura 1.5: Metoda lui Hunt a) Arbori de decizie binari b) Arbori de decizie multi-ci a Algoritmul de cretere a arborelui (prima faz) este unul de tip greedy care construiete s a s top-down arborele de decizie astfel: 1. se examineaz a ntregul set de antrenament D i pe baza unei metode (msuri) de separare s a se selecteaz din multimea de atribute prezente D atributul de separare A; a n 2. se creeaz l noduri u (unde l = Card(dom(A)) reprezeint numrul de valori distincte a a a ntre nodurile u; ale atributului de separare) i se s mparte setul de antrenament D 3. se proceseaz recursiv ecare u pn cnd este satisfcut un criteriu de oprire. a a a a a Tehnica de mai sus poart numele de metoda lui Hunt [Qui93] i este reprezentat Fia s a n gura 1.5 att pentru arbori binari ct i pentru arbori multi-ci. Intrarea o reprezint setul a a s a a de date de antrenament D iar ieirea arborele de decizie avnd rdcina nodul n. Datorit s a a a a examinrilor repetate ale setului de antrenament, faza de cretere a arborelui este una mare a s consumatoare de timp [SAM96, MAR96, GRG98]. Factorii determinanti pentru performantele aceastei faze sunt: alegerea punctelor de separare (acestea denesc testele pentru nodurile interne ale arborelui); a a a odat gsit un astfel de punct, cum se partitioneaz setul de antrenament pentru continuarea algoritmului. Detalii despre despre alegerea punctelor de separare pot gsite sectiunea 2.3, iar redua n cerea arborilor de decizie este tratat sectiunea 2.4. Din punct de vedere computational, faza a n de cretere este mult mai costisitoare dect cea de reducere (care are nevoie de doar 1% din s a timpul total de construire al arborelui) deoarece prima faz setul de date este parcurs de mai n a multe ori pentru construirea arborelui, timp ce faza de reducere actioneaz asupra arborelui n a din memorie. Trebuie mentionate i abordri care cele dou faze nu sunt delimitate exact, s a n a ele ntreptrunzndu-se. O astfel de abordare este algoritmul PUBLIC [RS98] care cele dou a a n a faze se ntreptrund astfel: criteriul de oprire este calculat a din faza de cretere a arborelui a nc s pentru a inhiba construirea prtilor arborelui care nu sunt semnicative i care ar trebuit a s eliminate cea de-a doua faz. n a Dintre avantajele arborilor de decizie amintesc urmtoarele: a

1.4 ARBORI DE DECIZIE

33

1. Arborii de decizie sunt utili primele faze ale procesului de analiz a datelor deoarece n a pun evident foarte clar atributele importante; cu ct un atribut este mai apropiat de n a a rdcin el are un rol mai important pentru setul respectiv de date; atributele care nu apar a a a arbore sau apar rar i apropierea nodurilor frunze au o important redus pentru n s n a a setul de date. 2. Euristicile bazate pe ctigul de informatie (information gain) evit cutarea as a a ntr-un spatiu de cutare de foarte mari dimensiuni. a 3. Arborii de decizie suport date lips, date cu zgomote, mixajul a a ntre atribute continue i s categoriale. 4. Arborii de decizie sunt folositi cel mai adesea problemele de clasicare , dar sunt utilizati n cu succes i problemele de regresie. s n 5. Arborii de decizie sunt uor de folosit, nenecesitnd cunotinte suplimentare despre domes a s niu. continuare vor amintite cteva dintre dezavantajele modelului arbore de decizie: In a 1. Bazndu-se pe aproximri rectangulare ale domeniului de valori, acetia nu functioneaz a a s a corect cazul altor tipuri de partitionri (vezi gura 1.6) n a 2. Utiliznd relatia de ordine a ntre valorile atributelor i ignornd complet diferentele absolute s a dintre aceste valori (adic 1 < 10 < 100 este la fel cu 0.99 < 1 < 1.01), arborii de a decizie nu sunt potriviti pentru problemele care distanta dintre dou valori (obiecte) n a este important. a 3. Un alt tip de aplicatii pentru care arborii de decizie nu se comport foarte bine sunt a aplicatiile care numrul de atribute semnicative pentru luarea unei decizii este redus n a comparatie cu cel al atributelor de important sczut pentru luarea unei decizii. n a a a Cu toate aceste neajunsuri arborii de decizie rmn una dintre cele mai puternice tehnici a a utilizate machine learning i data mining. Diverse strategii folosite cele dou faze au n s n a dus la aparitia unui numr impresionant de algoritmi pentru constructia automat a arborilor a a de decizie din seturi de date de mari dimensiuni. Sectiunea care urmeaz prezint cele mai a a a semnicative abordri [Pop02d], marea lor majoritate urmnd metoda Hunt. a

1.4.2

Algoritmi pentru constructia arborilor de decizie

ID3, C4/C4.5/C5 Poate cel mai semnicativ algoritm pentru constructia arborilor de decizie este cel dezvoltat de ctre Ross Quinlan de-a lungul a dou decenii (prima sa variant ID3 ind prezentat a a a a pentru prima oar 1986, lucrarea Induction of Decision Trees [Qui86]). Versiunea actual, a n n a C5 propus 1996, este o a n mbuntire a versiunilor anterioare C4.5/C4/ID3 [Qui93]. Algoa at ritmul consider toate testele care pot separa setul de date i alege pe acela care ofer cel a s l a mai bun ctig informational. Pentru atributele categoriale se consider un test cu attea ieiri as a a s

34x1 B da

REPREZENTAREA CUNOSTINTELOR x2=c2 C

x1 > c1 nu

x1=c1 A nu x2 > c2 da A

B

C

x2

Figura 1.6: Ilustrarea structurii arborelui de decizie spatiul de valori n

cte valori distincte exist pentru atributul considerat = Card(dom(Ai )). Pentru ecare atribut a a continuu (numeric) se consider teste binare pentru ecare valoare distinct disponibil ( faza a a a n de constructie) a atributului. Pentru a determina mod ecient ctigul entropic corespunztor n as a a a a acestor teste binare, familia de cazuri Fn asociat nodului n este sortat dup valorile atributului, dup care a ntr-o singur parcurgere a setului de date sortat sunt determinate ctigurile a as entropice pentru toate testele binare. Acest proces este repetat pentru ecare atribut numeric. Pe lng tratarea atributelor continue, C4.5 trateaz i valorile lips: e a a a s a nlocuiete valoarea s lips cu cea mai frecevent valoare pentru atributul respectiv nodul dat (adic multimea a a n a n Fn ), e face unele calcule probabilistice pe baza celorlaltor cazuri vederea determinrii valorii n a lips. O alt idee inovatoare introdus C4.5 este reduced-error pruning, care arborele creat a a a n n faza de cretere este simplicat folosind diveri euristici, apoi este testat pe un subset de n s s cazuri de validare (proces numit validare ncruciat) i dac performantele arborelui simplicat s a s a sunt mai bune dect ale celui original, atunci versiunea simplicat este pstrat. Detalii despre a a a a implementarea acestor algoritmi pot gasite [Col96, Mon97, Dav95]. n SLIQ, SPRINT Algoritmul SLIQ a fost propus 1996 de Mehta, Agrawal i Rissanen [MAR96] iar o variant n s a imbuntit numit SPRINT a fost propus acelai an de Shafer, Agrawal i Mehta [SAM96]. a at a a a n s s Aceti doi algoritmi s mbuntesc algoritmul C5 prin evitarea sortrilor la nivelul ecrui nod a at a a printr-o pre-sortare a atributelor numerice la nceputul algoritmului. SPRINT contruiete arbos rele de decizie folosind o tehnic breadth-rst i o singur pre-sortare pentru a reduce tima s a pul necesar evalurii atributelor numerice. Astfel, pentru ecare atribut se construiete la a s nceput o list a atributului compus din: valoarea atributului, eticheta clasei din care face a a parte nregistrarea i identicatorul s nregistrrii (rid). Aceste liste sunt salvate pe disc dac a a dimensiunea lor depete memoria disponibil. Listele pentru atributele numerice sunt sortate as s a initial dup valoarea atributului, iar listele pentru atributele categoriale rmn nesortate. La e a a a

1.4 ARBORI DE DECIZIE

35

care ramicare a arborelui subarbori, listele atributelor sunt la rndul lor divizate sub-liste n a n corespunztoare nodurilor u. Prin pstrarea ordinii a a nregistrrilor sub-listele partitionate, a n acestea nu necesit nici o resortare. Pentru alegerea atributului de separare algoritmul SPRINT a folosete indexul Gini introdus [BFOS84]. Acesta este calculat prin scanarea listelor de atris n but corespunztoare unui nod i calcularea distributiei claselor ambele prti ale valorii de a s n a separare (histrogramele below i above). Atributul cu valoarea minim a indexului Gini i vas a s loarea de separare corespunztoare acestui atribut sunt alese pentru partitionarea setului de a date i pentru construirea unui nou nod. [MRA95] se arat c SLIQ/SPRINT produc arbori s In a a de decizie mai mici ca dimensiune i a cror acuratete este similar sau chiar mai bun dect cea s a a a a obtinut cu ajutorul algoritmilor CART [BFOS84] sau C4.5 [Qui93]. Algoritmii SLIQ/SPRINT a au fost propui i implementati pentru constructia arborilor binari, dar pot adaptati pentru s s cazul generic al arborilor multi-ci. a Platforma RainForest (RF-Write, RF-Read, RF-Hybrid, RF-Vertical) i BOAT s [GRG98] Gehrke et al. prezint un cadru general, denumit RainForest, pentru clasicatorii In a de tip arbori de decizie care aspectele legate de scalabilitatea algoritmilor de constructie a n arborilor sunt separate de facilitile centrale care determin calitatea arborelui. Acest cadru at a general poate instantiat cu algoritmi existenti literatur (precum CDP [AIS93], ID3/C4.5 n a [Qui93], CART [BFOS84], SLIQ/SPRINT [MAR96, SAM96], CHAID [Mag93], QUEST [LS97]). Autorii propun deasemenea patru noi algoritmi (RF-Write, RF-Read, RF-Hybrid, RF-Vertical) care exploateaz beneciile listelor AVC (atribut-valoare-clas). a a Algoritmul BOAT (Bootstrapped Optimistic Algorithm for Tree Construction) propus de Gehrke et al. [GRGL99] construiete cteva nivele a arborelui doar dou parcurgeri a setului s a n a de date de antrenament, obtinndu-se astfel performante cu pn la 300% mai bune dect a a a a n algoritmii anteriori. Cheia acestei performante este o abordare optimist a construirii arbo a relui, care arborele initial este construit pe baza unui subset de mici dimensiuni a datelor n de antrenament, arbore care este ranat apoi pn la forma sa nal. Orice diferent fat de a a a a a arborele real (adic arborele care ar fost construit cu metoda Hunt clasic) este detectat a a a i corectat. Pasul de corectie necesit uneori o parcurgere suplimentar a unor subseturi ale s a a a setului de date de antrenament. BOAT este primul algoritm scalabil care are abilitatea de a actualiza mod dinamic arborele atunci cnd noi n a nregistrri sunt adugate sau terse din setul a a s de date. Aceast proprietate este esential medii dinamice, precum depozitele de date (data a a n warehouses), care setul de date de antrenament se modic timp. Operatia de actualizare n a n a arborelui este mult mai putin costisitoare ca timp dect o reconstructie complet a arborelui, a a iar rezultatul obtinut este identic cu cel produs prin reconstructie. Observatii asupra metodei lui Hunt Metoda lui Hunt (i toti algoritmii derivati din ea) sufer de un dezavantaj major - miopia, s a n sensul c nici una din msurile prezentate nu este capabil s prezic efectul aplicrii unui set a a a a a a de atribute mpreun, i nu doar a unui singur atribut. Odat un atribut selectat ca atribut de a s a separare, el este exclus din lista de atribute candidate testele viitoare ceea ce face ca metoda n lui Hunt s e susceptibil de convergent minimele locale. S-ar putea ca loc s alegem a a a n n a ca atribut de separare atributul care minimizeaz entropia un alt atribut s obtinem un arbore a a mai performant (cu noduri sau nivele mai putine). Metoda lui Hunt reprezint de fapt apli a

36

REPREZENTAREA CUNOSTINTELOR

carea principiului logic Occams Razor (sau al parcimoniei) la constructia arborelui de decizie. Acest principiu logic, atribuit lui William of Occam (aprox. 1285-1349), postuleaz c: trebuie a a s facem minimum de supozitii/ipoteze necesare pentru a explica ceva. Sunt de mentionat a cteva lucrri [MP94, Web96] care analizeaz oportunitatea aplicrii acestui principiu cona a a a n textul constructiei arborilor de decizie. [Web96], G.I. Webb prezint dovezi experimentale In a mpotriva utilizrii principiului parcimoniei constructia arborilor de decizie folosind algorita n mul C4.5. Cu toate c eliminnd acest principiu se obtin arbori mai compleci, acetia au o a a s s acuratete mai bun dect cei obtinuti prin aplicarea algoritmului standard. Cu toate acestea, a a n practic s-au impus arborii mai simpli deoarece pot mai uor interpretati de expertii umani, a s pentru seturi foarte mari de date sunt mai rapizi i ofer performante foarte bune. O alt lucrare s a a a a n a [FKY96] dedicat eliminrii miopiei procesul de constructie a arborilor de decizie prezint o abordare care se elimin necesitatea construirii arborelui de decizie avans. Constructia n a n se face pentru ecare caz de clasicat parte, situatie care pentru alegerea atributului de n n separare se cunoate, pe lng setul de date de antrenament, i valorile din cazul care trebuie s a a s clasicat. Constructia i actualizarea incremental a arborilor de decizie s a Din punctul de vedere al disponibilitii setului de antrenament alnim dou posibiliti: 1) at nt a at ntreg setul de antrenament este disponibil momentul constructiei arborelui de decizie; 2) n datele din setul de antrenament sosesc treptat timp. Pentru cazul 1), odat ce arborele este n a construit, rmne neschimbat i sarcina construirii sale s-a a a s ncheiat (algoritmii care functioneaz a cel de-al doilea caz, exist dou optiuni: acest fel se numesc algoritmi non-incrementali). In n a a n n s a. momentul care un nou set de antrenament este disponibil se reconstruiete arborele de decizie de la zero pe baz a ntregului nou set de antrenament; b. se revizuiete arborele existent pe baza noilor informatii disponibile. s Algoritmii corespunztori punctului b) sunt cunoscuti sub numele de algoritmi incrementali a pentru constructia arborilor de decizie. Desigur c este de dorit ca algoritmii incrementali s a a produc aceeiai arbori de decizie ca algoritmii non-incrementali pentru acelai set de date de a s s antrenament, indiferent dac aceste date sunt disponibile a n ntregime la momentul constructiei arborelui sau sosesc fragmentat timp. Ideal, un algoritm de constructie incremental a arbon a rilor de decizie ar trebui s le a ndeplineasc urmtoarele criterii: a a 1. Costul actualizrii incrementale a arborelui de decizie trebuie s e mult mai redus dect a a a costul construirii unui arbore nou. Oricum nu e necesar ca suma tuturor costurilor de actualizare (update) incremental s e mai redus, pentru c intereseaza doar costul a a a a aducerii arborelui la zi. 2. Costul actualizrii incrementale trebuie s e independent de numrul instantelor de ana a a trenare pe care se bazeaz arborele. a 3. Arborele rezultat urma aplicrii algoritmului incremental trebuie s depind de setul n a a a de instante din arbore, nu i de secventa care acestea au fost introduse. s n 4. Algoritmul trebuie s accepte att atribute categoriale ct i numerice. a a a s

1.4 ARBORI DE DECIZIE 5. Algoritmul trebuie s poat gestiona clase multiple. a a 6. Algoritmul nu trebuie s eueze la primirea unor instante de antrenare inconsistente. a s

37

7. Algoritmul nu trebuie s favorizeze o anumit variabil pentru c are o plaja de valori a a a a mai mare. 8. Algoritmul trebuie s e ecient timp i spatiu. a n s 9. Algoritmul trebuie s suporte instante cu valori lips. a a 10. Este necesar ca algoritmul s evite efectul de supra-potrivire (overtting). a 11. Algoritmul trebuie s poat gsi teste compuse. a a a 12. Algoritmul trebuie s poat grupa valorile unei variabile. a a De-a lungul timpului s-a acordat o atentie deosebit inductiei incrementale, a ncepnd cu a studiile lui Samuel (1959) i algoritmul lui Michalski (1975). Abordarea lui Friedman [Fri77] s folosete caracteristici adaptive pentru unele noduri de separare. Un nod de separare adaps tiv depinde de eantionul de antrenament pe care separ (adic familia de cazuri Fn coress l a a punztoare vezi denitia 1.4.5), de exemplu prin testarea valorii medii a atributului. Fisher a propune [Fis87] un algoritm de inductie a arborilor de decizie (COBWEB) care integreaz un n a caz ntr-un arbore de decizie existent prin trecerea cazului de-a lungul unei ci compus din a a nodurile cu cea mai bun potrivire. Spre deosebire de metodele conventionale de predictie a n care eroarea de clasicare se msoar prin diferenta dintre valoarea prezis i cea real, Sutton a a as a a (1988) [Sut88] propune msurarea erorii de clasicare prin diferenta dintre predictii succesive temporal algoritmul de aare a diferentei temporale. Utgo et al. a propus algoritmul Innvt cremental Tree Inducer (ITI) pentru crearea i actualizarea incremental a arborilor de decizie s a a s n att cazul arborilor univariate [Utg89, Utg94, UBC97] ct i cazul multivariate5 [UB90]. O a n versiune incremental a binecunoscutului algoritm CART care folosete praguri de semnicatie a s pentru a evita restructurrile frecvente ale arborelui a fost propus de ctre Crawford [Cra89]. a a a Mai recent, Gehrke et al. [GRGL99] propun un algoritm (BOAT) foarte rapid, scalabil i cu s abiliti de actualizare incremental a arborelui construit. Cheia facilitilor oferite de BOAT at a at (Bootstrapped Optimistic Decision Tree) o constituie o abordare optimist care arborele a n initial este construit folosind o submultime de dimensiune redus a setului de antrenament i a s apoi este ranat pentru a obtine performantele dorite. Esenta algoritmului o constituie tocmai buna abilitate de actualizare incremental a arborelui. Guetova et al. propune [GSH02] a n att versiunea non-incremental ct i pe cea incremental a unui algoritm pentru constructia a a a s a arborilor de decizie fuzzy, iar abordri de ultim or (Stanley [Sta]) se utilizeaz arborii de n a a a a decizie pentru modelarea fenomenelor dinamice (concept drift). O sintez recent apartind lui a a a Rokach [RM05] prezint cele mai cunoscute implementri i probleme, respectiv solutii care au a a s aprut de-a lungul timpului constructia arborilor de decizie. a n Univariate nseamn c un nod de decizie este separat pe baza unui singur atribut de separare. cazul a a In multivariate, mai multe atribute contribuie la stabilirea criteriului de separare al unui nod de decizie.5

38

REPREZENTAREA CUNOSTINTELOR

1.5

Tabele de decizie

Tabela de decizie reprezint o form de reprezentare a cunotintelor compact i uor de a a s a s s 6 , o tabel de decizie este un mod precis i interpretat de operatorul uman. Conform Wikipedia a s compact pentru a modela logica complex a unui algoritm. Cu toate c spatele tabelelor a a n de decizie se a o teorie riguros bazat pe principii matematice [Mor82, RSY87], aceast a a n a lucrare acestea vor introduse din punct de vedere semantic i legatur cu celelalte modele s n a de reprezentare a cunotintelor (arbori de decizie i seturi de reguli). tabela de decizie se s s In [Pop00a] se mentioneaz cteva dintre asociaz conditii cu actiuni ce urmeaz a executate. In a a a a avantajele modelului tabel de decizie, cum ar posibilitatea analizei automate a consistentei, a completitudinii i corectitudinii sistemului i impunerea unei riguroziti tratarea tuturor s s at n cazurilor posibile. majoritatea cazurilor, tabelele de decizie sunt construite de expertii umani In i generarea lor din seturi de date nu este o tehnic uzual, dar nu este imposibil. Conform s a a a unei anecdote, dup o a ncercare euat de a descrie logica unui program pentru un sistem de s a ntretinere a ierelor pe parcursul a 6 ani-om, o echip de patru oameni a rezolvat problema s a folosind tabele de decizie patru sptmni. n a a a La nceput tabelele de decizie au aprut ca o tehnic folosit de programatori pentru codia a a carea logicii unui algoritm cazul care numrul alternativelor era mare i dicil de urmrit. n n a s a Interesul primordial perioada de n nceput (anii 60 - 80) [Fis66, Pol62], cu un numr mediu a de 30 de publicatii pe an i un maxim de 67 lucrri 1971, era conversia acestor tabele s a n n cod program [KJ75, Lew78]. Dup aceea, tabelele au devenit larg utilizate diverse domenii, a n iar interesul s-a mutat ctre proiectarea unor metode i denirea unei metodologii consistente a s pentru constructia tabelelor de decizie, folosit cu precdere reprezentarea cunotintelor i a a n s s In sistemele pentru suportul deciziilor [HC00, JY00, Fra00] (decision support systems). zin lele noastre, tabelele de decizie cunosc o larg rspndire in cele mai diverse domenii, de la a a a modelarea regulilor afaceri [Van04], la studii medicale [SDD+ 99], la aplicatii agricultur n n a sau domeniul legislatiei (de exemplu, ca suport la n ntocmirea actelor juridice [BVS+ 93]). Un rezumat extins privind evolutia tabelelor de decizie pn anul 2000 - i metodologii a a n s nrudite - a fost realizat de ctre Moreno Garcia, Verhelle i Vanthienen [GVV00]. a s Popularitatea tabelelor de decizie a dus la aparitia multor utilitare i unelte pentru constructia s lor vizual, pentru validarea i vericarea lor sau pentru generarea automat a codului, cum ar a s a : Expert System Creator [PN03], ILOG JRules [ILO05], QuickRules [Tec05], MineSet [Ins] sau PROLOGA (PROcedural LOGic Analyzer) [VD94]. La nivel national, probabil c cea mai cunoscut lucrare despre tabele de decizie este cartea a a lui Liviu Dumitracu i Ioachim Alexandru, Generating FORTRAN Programs from Decision s s Tables [DA90]. Cartea prezint toate aspectele legate de tabele de decizie i a s ncepe prin clasicarea acestora mpreun cu un numr de tehnici similare, cum ar regulile i ow charts. a a s Apoi, este prezentat utilizarea tabelelor de decizie analiza i proiectarea sistemelor infora n s matice i sunt discutate pe larg metode pentru constructia, validarea i comprimarea tabelelor s s partea a patra autorii vorbesc despre conversia tabelelor de decizie arbori de de decizie. In n decizie i ow chart. Partea a cincea acoper domeniul generrii automate a codului din tabele s a a de decizie prin intermediul preprocesoarelor i este fcut o analiz comparativ a diferitelor s a a a a6

http://en.wikipedia.org/wiki/Decision table

1.5 TABELE DE DECIZIEConditii Actiuni Valorile conditiilor Intrri actiuni a

39

Tabela 1.3: Forma general a tabelei de decizie a Regula Nivel debit Nivel venit Form a jare angaActiune (Nivel risc) Mare Mare Sczut a

Regula 1 Regula 2 Regula 3

Ridicat Sczut a Mediu

or

-

Independent Salariat Salariat

Figura 1.7: Tabela de decizie ( form orizontal ) n