Universitatea babeş-bolyai cluj-napoca facultatea de matematicǎ Şi informaticǎ specializarea informatică

Analiză și proiectare

Propunem utilizarea clasificatorului naiv Bayes pentru conceperea sistemului destinat clasificării documentelor de tip text.

După cum am precizat și anterior în descrierea comportamentului acestui clasificator, avem nevoie de un spațiu al instanțelor , care să descrie toate documentele de tip text existente, precum și de un set de date de antrenament corespunzătoare unor funcții target necunoscute f(x) care pot lua orice valoare dintr-un anume set finit . Scopul sistemului este acela de a învăța pe baza acestor date de antrenament să prezică valoarea funcției țintă, adică denumirea categoriei din care face parte un document nou, oferit spre clasificare.

În ceea ce privește raportarea acestei probleme de categorizare textuală la utilizarea concretă a clasificatorului naiv Bayes, intervin două aspecte importante care țin de proiectare. În primul rând, trebuie să decidem cum vom reprezenta un document text sub forma unor atribute, iar în al doilea rand trebuie să identificăm o modalitate de estimare a probabilităților necesare clasificatorului.

În cazul de față, pentru un anumit document, atributele vor fi definite pentru fiecare poziție a unui cuvânt, valoarea acestora fiind reprezentată tocmai de către cuvintele corespunzătoare. Este ușor de intuit faptul că pentru anumite documente, care au o lungime foarte mare și numărul de atribute va fi ridicat. Totuși acest detaliu nu ne va cauza probleme, după cum vom putea observa în cele ce urmează.

Pentru a putea ilustra modul de lucru al clasificatorului naiv Bayes în contextul actual, vom lua un exemplu concret, pe baza căruia vom creiona anumite caracteristici esențiale, urmând să prezentăm și beneficiile suplimentare pe care le va avea utilizatorul pe lângă posibilitatea de antrenare și testare a sistemului respectiv. Presupunem că avem la dispoziție un set de 600 de documente pentru antrenament corespunzătoare unei anumite categorii cu numele: C1 și alte 400 de documente corespunzătoare unei alte categorii: C2. În conformitate cu scopul nostru, în urma procesului de antrenare vom dori, cel mai probabil, să clasificăm un document nou, în una dintre cele două categorii. Pentru realizarea acestui lucru, clasificatorul va trebui să instanțieze următoarea formulă:

Practic, clasificarea naivă maximizează probabilitatea de a observa acele cuvinte care au fost găsite în document, datorită presupunerii naive de independență a cuvintelor, conform căreia probabilitățile cuvintelor de pe o anumită poziție sunt independente de cele ale cuvintelor care apar pe alte poziții. Această presupunere poate fi considerată însă incorectă. De exemplu: probabilitatea de observare a cuvântului „learning” pe o anumită poziție ar trebui să fie mai mare în cazul în care pe poziția precedentă s-ar afla cuvântul „machine”. Totuși, această abordare ne este necesară pentru reducerea numărului de probabilități calculate, iar clasificatorul naiv Bayes reușește să obțină performanțe ridicate în ciuda acestui compromis.

Pentru calcularea avem nevoie de probabilitățile inițiale , care pot fi estimate pentru fiecare categorie în parte prin calcularea raportului dintre: numărul de documente dintr-o anumită categorie și numărul total de documente (în cazul nostru pentru categoria C1, respectiv pentru categoria C2).

Estimarea probabilităților condiționale este însă mai problematică, deoarece necesită calcularea unui astfel de termen probabilistic pentru fiecare combinație a pozițiilor din text, a cuvintelor și a valorii funcției țintă.

Să presupunem că luăm în considerare vocabularul englez în care există aproximativ 50000 de cuvinte distincte și nu folosim conceptul de independență condițională, rămânând în rest aceleași setări ca mai sus (adică avem la dispoziție două categorii și i poziții în cadrul unui anumit document). Va trebui deci, să estimăm termeni. În cazul în care documentul are 100 de poziții (adică dacă ) vom obține termeni, o valoare mult prea mare pentru a putea fi luată în considerare.

Acesta este și motivul pentru care vom considera independența condițională a atributelor și distribuția identică a acestora, obținând în acest caz pe același exemplu de termeni probabilistici diferiți, de i ori mai puțini.

În continuare, trebuie să alegem o metodă de estimare a probabilităților. Vom folosi tehnica m-estimare cu proirități uniforme, unde m va fi egal cu dimensiunea vocabularului de cuvinte. Astfel, estimarea parametrului va fi obținută cu ajutorul formulei:



reprezintă numărul total de poziții ale cuvintelor din toate documentele pentru antrenare a căror valoare țintă este , este numărul de apariții al cuvântului pe aceste poziții, iar reprezintă numărul total de cuvinte distincte din cadrul setului de date de antrenament.

Pașii prezentați anterior corespund procesului de antrenare al sistemului, respectiv clasificare a unor documente noi. Având estimările probabilităților condiționale, următorul pas constă în realizarea testării, astfel încât să ne putem raporta la calitatea acestuia prin compararea rezultatelor obținute. Pentru a realiza acest lucru, sistemului ii vor fi oferite spre clasificare documente noi (care nu au fost folosite în procesul de antrenare) și în funcție de rezultatele obținute se va calcula acuratețea algoritmului după formula .

Desigur, pentru ca sistemul să fie ușor de utilizat și cât mai aproape de cerințele utilizatorului, îi vor fi atribuite mai multe funcționalități, care pot fi observate și în cadrul diagramelor care urmează:

• 
  Diagrama cazurilor de utilizare:
  

• 
  Diagrama corespondențelor dintre pachete:
  

Pentru realizarea acestei aplicații am utilizat arhitectura Model-View-Controller, ce reprezintă un şablon arhitectural folosit în industria de software development. Această modalitate de lucru reuşeşte cu succes să izoleze partea logică de interfaţa proiectului, rezultând aplicaţii extrem de uşor de modificat. În această organizare, modelul reprezintă informaţia (datele) de care are nevoie aplicaţia, view-ul corespunde elementelor de interfaţă iar controller-ul reprezintă sistemul comunicativ şi decizional ce procesează datele informaţionale, făcând legătură între model şi view.

• 
  Diagrama de clase, împărțită pe pachete:
  

• 
  Diagrama de clase, corespunzătoare logicii aplicației (cuprinde clasele din pachetele: model, utile, service, dao)
  

3.