LUCRARE DE LICENȚĂ Sistem automat de identificare a...
45
Universitatea Politehnica Bucureşti Facultatea de Automatică şi Calculatoare Departamentul de Automatică şi Ingineria Sistemelor LUCRARE DE LICENȚĂ Sistem automat de identificare a cerințelor în cadrul proiectelor Absolvent Radu Andrei Coordonator Ș.l. Dr. Ing. Sacală Ioan
Transcript of LUCRARE DE LICENȚĂ Sistem automat de identificare a...
Universitatea Politehnica Bucureşti
Facultatea de Automatică şi Calculatoare
Departamentul de Automatică şi Ingineria Sistemelor
LUCRARE DE LICENȚĂ
Sistem automat de identificare a cerințelor în
cadrul proiectelor
Absolvent
Radu Andrei
Coordonator
Ș.l. Dr. Ing. Sacală Ioan
2
Cuprins
Cuprins ...................................................................................................................................................... 2
1. Introducere ........................................................................................................................................ 3
2. Stadiul actual ..................................................................................................................................... 5
3. Tehnologiile folosite .......................................................................................................................... 6
3.1 Mediul Eclipse ............................................................................................................................... 6
3.2 Stanford Parser .............................................................................................................................. 7
3.3 Wordnet ...................................................................................................................................... 10
3.4 Weka............................................................................................................................................ 12
4. Metode de clasificare existente ...................................................................................................... 12
4.1 Arbori decizionali ......................................................................................................................... 13
4.2 Clasificatori bazati pe reguli ........................................................................................................ 14
4.3 Clasificatorul Bayesian naiv ......................................................................................................... 16
4.4 Metoda celor mai apropiați K vecini ........................................................................................... 18
4.5 Rețelele neuronale ...................................................................................................................... 19
4.6 Mașini cu suport vectorial ........................................................................................................... 25
5. Descrierea aplicației ........................................................................................................................ 28
5.1 Interfața aplicației ....................................................................................................................... 31
5.2 Extragerea atributelor pentru clasificare .................................................................................... 35
5.3 Structura fișierului Attribute-Relation File Format ..................................................................... 37
5.4 Identificarea cerințelor ce aparțin contextului ........................................................................... 38
6 Studiu de caz ................................................................................................................................... 40
7 Anexa 1 ............................................................................................................................................ 43
3
1. Introducere
Ingineria cerintelor este procesul de stabilire a serviciilor cerute sistemului de catre client,
precum si a constrangerilor sub care acesta va fi dezvoltat si va opera (Sommerville,2004).
Avand in vedere ca dezvoltarea sistemelor se bazeaza pe cerintele identificate si dezvoltate ale
proiectului, este important ca acestea sa acopere cu acuratete nevoile clientului.
În 1994 compania Standish Group a facut un studio a peste 350 de companii ce au initiat
peste 8000 de proiecte software. S-a observat că 31% dintre proiecte au fost abandonate înainte
de a fi terminate. Mai mult, în marile companii, doar 9% au fost livrate la timp şi la costul la care
au fost contractate, iar în companiile mici procentul s-a ridicat doar la 16%. În urma cercetărilor
efectuate s-a dovedit ca mai mult de 50% din probleme sunt datorate cerintelor neadecvate
(intelegere partial sau eronata a cerintelor, documentare si management deficitar). Proiectul nu
poate fi de success cand are loc construirea unui sistem care rezolvă o problemă pusă greşit, care
nu funcţionează după aşteptări, sau care este greu de înţeles şi de utilizat de către clienţi.
Ingineria cerintelor cuprinde dezvoltarea si managementul acestora. Cerintele pornesc de la
afirmatii abstracte de nivel inalt, pana la specificatii matematice functionale detaliate. Astfel ele
pot fi organizate ierarhic, de la cerintele clientului, la cerintele functionale ale modulelor
produsului dezvoltat. Astfel se poate verifica daca nevoile clientului sunt acoperite de catre
functionalitatile produsului. Aceasta organizare ierarhica este prezentata in figura 1.1.
Clienți
Cerințele
clienților
Cerințele
modulelor
produsului
Cerințele
produsului
Puncte
acoperite
Figura 1.1 – Structura ierarhică a cerințelor
4
Dezvoltarea cerințelor se aplică fiecărui nivel al figurii 1.1, de la nivelul cerințelor clientului
până la cerințele modulelor produsului. Astfel, în fiecare ciclu al dezvoltării se desfășoară
activitațile: extragerea cerințelor, analiza și negocierea cerințelor, documentarea cerințelor și
validarea cerințelor. Aceste activități ce se execută iterativ sunt puse în evidență pe parcursul
proiectului de către modelul Kotonya-Sommerville (figura 1.2) :
Specificaţiile sunt documente de referinţă cu ajutorul cărora se evaluează dezvoltarea
programului. În cadrul acestor specificații, cerințele sunt prezentate sub formă de text, limbaj
formal sau grafic. În această lucrare se va trata cazul cerințelor aflate sub formă de limbaj natural
(text), aceasta fiind forma preferată a clienților.
Specificarea cerințelor sub formă de limbaj natural are anumite avantaje și dezavantaje.
Acestea sunt ușor de citit și ințeles, ușor de scris. Cu toate acestea, ele nu pot fi scrise întotdeauna
corect din punct de vedere al managementului cerințelor. O serie de probleme pot fi întâmpinate,
cele mai dese fiind cerințele ambigue, inconsistente sau ce se contrazic. Totodata, cerințele
prezentate sub forma de limbaj natural sunt greu de analizat și extras (automat).
Sursă: Kotonya and Sommerville (1998, pg. 35)
Figura 1.2 – modelul Kotonya Sommervile
5
Un document specificație ce conține cerințe sub formă textuală trebuie analizat manual,
rând cu rând. Această activitate poate fi solicitantă este este foarte susceptibilă erorilor. Un
exemplu de astfel de document este prezentat în figura 1.3.
2. Stadiul actual
Problema managementului de cerințe a fost abordată de diferite companii în moduri
similare. Au fost dezvoltate numeroase aplicații pentru managementul cerințelor ce oferă
posibilitatea de analiză, verificare, validare, urmărire și corectă documentare a acestora pe tot
parcursul proiectului. Soluțiile oferite ajută prin organizarea si definirea cerințelor, centralizarea
acestora pentru a ușura accesul si pentru a păstra o ordine ierarhică sau în funcție de prioritate.
Soluții populare sunt oferite de către IBM („Rational RequisitePro”, „Rational Requirements
Composer”, „DOORS”), HP („HP Requirements Management”, „HP Application Lifecycle
Management”, „HP Quality Center software”).
Toate aceste soluții au funcții similare pentru urmărirea cerințelor, analiză, securitate,
accesibilitate , portabilitate, versionare, stocare, documentare și afișare în diverse moduri.
Urmărirea cerințelor definește legaturile acestora cu proiectul, si cum reflectă orice modificare a
proiectului cerințele initiale sau invers. Prin analiza cerințelor se pot defini diverse atribute ale
acestora, precum gradul de prioritate, dificultate sau daca cerința respectivă este implementă. Prin
securitate si accesibilitate se poate oferi, modifica sau opri accesul diferiților utilizatori la
cerințele proiectului. Portabilitatea asigură interfațarea cu diferite medii de procesare si stocare de
date, precum MS Office baze de date. Prin funcția de versionare se pot observa care au fost
modificările aduse cerințelor pe parcursul proiectului și stabili o versiune curentă a lor.
Documentarea oferă posibilitatea de a captura cerințele din diverse formate de documente.
Figura 1.3 – Exemplu de document cu specificații
6
De precizat este că cerințele trebuie marcate în prealabil în diferite tipuri de documente
pentru a putea fi recunoscute si capturate cu ușurință de aplicațiile menționate mai sus. În funcție
de aplicația folosită, cerințele pot fi: introduse manual în mediul de dezvoltare, marcate în
documente manual sau după anumite cuvinte cheie specificate. Marcarea cerințelor se face de
obicei manual si necesită mult timp si o atenție deosebită. Acest lucru predispune întregul proces
la erori umane, ce daca nu sunt descoperite într-o fază incipientă se propagă în sistem si devin tot
mai greu și mai costisitor de remediat. Anumite soluții oferite de competitorii de top pe piața
ingineriei și managementului cerințelor au implementate mecanisme ce pot ajuta utilizatorul la
recunoașterea și marcarea cerințelor. Aceste mecanisme sunt destul de primitive, nu includ decât
sublinierea, colorarea sau căutarea anumitor termeni specificați de către utilizator.
În această lucrare se pune baza unui sistem automat de identificare a cerințelor ce are
scopul de a diminua eventualele erori umane. De menționat este că scopul identificării automate a
cerințelor nu este de a înlătura complet factorul uman din acest pas, ci de a oferi acestuia o
verificare sau sugestii în identificarea si marcarea corectă a cerințelor.
3. Tehnologiile folosite
Platforma pentru identificarea automată a cerințelor a fost dezvoltată integral în Java, în
mediul de dezvoltate ”Eclipse”. Aceasă alegere a fost facută pentru folosirea și integrarea în
proiect cu ușurință a unor resurse ce vor fi menționate mai jos. Aplicației i-a fost construită o
interfață pentru a oferi un mod de lucru cât mai intuitiv, dar se poate integra cu ușurință în funcție
de caz în diferite alte aplicații sau medii de dezvoltare.
Am redus problema identificării cerințelor la una de clasificare a textului în doua clase
predefinite, cerințe si non-cerințe. Pentru o mai buna analiză a textului au fost utilizate două
resurse disponibile publicului, de precizie bună si foarte folosite în general, ”Stanford Parser” si
”Wordnet”. Acestea oferă o interfață de programare accesibilă din Java, lucru ce a permis
integrarea lor cu ușurință în aplicația dezvoltată.
3.1 Mediul Eclipse
Eclipse este o comunitate Open Source – servicii oferite gratuit utilizatorilor si
organizațiilor, ce îşi concentrează eforturile în crearea unei platforme de dezvoltare a aplicaţiilor
alcătuită din framework-uri extensibile, unelte şi medii de rulare pentru dezvoltarea şi întreţinerea
7
de aplicaţii1. Eclipse oferă suport pentru o mare varietate de limbaje de programare (C, C++,
Java), inclusiv pentru dezvoltarea de aplicaţii web, sau pentru modelare similară UML-ului.
Cu ajutorul acestui mediu de dezvoltare a fost posibilă integrarea resurselor ”Stanford
Parser” si ”Wordnet” în proiect. Pe tot parcursul dezvoltării aplicației, Eclipse a oferit un mediu
de programare ușor de urmărit, având toate beneficiile si funcționalitațile altor medii de
dezvoltare integrate.
3.2 Stanford Parser
”Stanford Parser” este o aplicație oferită de către ”The Stanford Natural Language
Processing Group” (organizație a universitații Stanford), ce analizează structura sintactică a unei
propoziții. Este un interpretor probabilistic ce folosește cunoștințele de limbă dobândite din fraze
analizate manual pentru a produce cea mai probabilă analiză a propoziției. Ca orice interpretor
statistic, are unele erori, dar în general performanțele sunt destul de bune.
Stanford Parser-ul oferă un pachet cu o implementare Java a analizatorului statistic al
limbajului natural dezvoltat, un interpretor PCFG (Probabilistic context free grammar – parser
probabilistic independent de context) foarte bine optimizat și un interpretor de dependențe
lexicale. Precizez că Stanford Parser-ul nu ține cont de valoarea cuvintelor (care sunt ele) în
propoziție, ci doar de un model general al poziției, ordinii acestora și presupuse legături.
Rezultatul analizei interpretorului este oferit într-o structură arborescentă pentru a pune în
evidență legaturile între părțile de propoziție. Un exemplu de analiză a propoziției ”The quick
brown fox jumps over the lazy dog.” este prezentat mai jos:
(ROOT
(S
(NP (DT the) (JJ quick) (JJ brown) (NN fox))))
(VP (VBZ jumps)
(PP (IN over)
(NP (DT The) (JJ lazy) (NN dog))
1 Conform descrierii oferite de către Fundația Eclipse
8
(. .)))
Etichetele oferite în rezultatul analizei sunt (în ordinea apariției lor):
ROOT: radăcina structurii arbore
S: propoziție
NP: frază substantiv
DT: determinant
JJ: adjectiv
NN: substantiv, singular sau mulțime
VP: frază verbală
VBZ: verb, persoana a 3-a, singular, prezent
PP: frază prepozițională
IN: prepoziție sau conjuncție subordonată
O descriere mai detaliată a tuturor etichetelor posibile și ce legături implică acestea se
găsește în Anexa 1.
De remarcat este că interpretorul ”Stanford Parser”, în această versiune a lui, poate fi
aplicat doar limbii engleze. Acest lucru se datoreaza ordinii diferite a cuvintelor în propoziție în
cele doua limbi – de exemplu: adjectivul se poziționeaza după substantiv în limba română, iar în
limba engleză este invers (”merele roșii” – față de ”the red apples”).
Aceeași propoziție analizată mai sus, tradusă în limba română (”Vulpea iute și maro sare
peste câinele leneș.”) este interpretată de către ”Stanford Parser” astfel:
ROOT
S
VP .
. VB PP
NP
DT JJ NN
dog lazthe
jumpThe quick fox brown
DT JJ NN JJ
NP IN
ove
Figura 3.1.1
9
(ROOT
(S
(NP (NNP Vulpea) (NN iute) (NN si) (NN maro))
(VP (VBP sare)
(NP (JJ peste) (NN cainele) (NNS lenes)))
(. .)))
Etichete noi apărute:
NNP: substantiv propriu, singular
VBP: verb, nu la persoana a 3-a, singular, prezent
NNS: substantiv, plural
Se poate observa cu ușurință că analiza facută de către interpretor este greșită (Figura
5.1.3).
O aplicație de analiză sintactică a limbii române este ”UAIC Romanian Part of Speech
Tagger” dezvoltat de către Institutul de Cercetări în Inteligenţă Artificială al Academiei Române
ROOT
S
VP .
. VBP
NP
JJ NN NNS
leneș căinele peste
sare Vulpea iute maro și
NNP NN NN NN NP
Figura 3.1.2
10
(Tufiş, 1999; Ion, 2006). Lucrări de menționat sunt și ”POS-tagger hibrid2” și ”Graphical
grammar studio as a constraint grammar solution for part of speech tagging3” (Radu Simionescu
2011).
3.3 Wordnet
”Wordnet-ul” reprezintă o mare bază de date a limbii engleze dezvoltată de către o echipă
condusă de George A. Miller, membrii ai Laboratorului de Ştiinţe Cognitive al Universităţii
Princeton. Platforma este oferită public către descărcare si utilizare și este foarte folositoare
procesării de limbaj natural și lingvisticii computaționale. Este larg utilizată în prezent, putând fi
accesată si integrata în diferite medii de dezvoltare cu mare ușurintă. Wordnet grupează
substantivele, verbele, adjectivele şi adverbele limbii engleze în serii de sinonime numite
synseturi, fiecare reprezentând un concept diferit, o abstractizare a înțelesului comun al grupului4.
Synseturile sunt interconectate prin intermediul unor relații conceptuale-semantice și lexicale.
Legăturile nu sunt doar între formele cuvintelor, ci și între sensuri specifice ale cuvintelor.
Această proprietate are ca rezultat faptul că două cuvinte apropiate ca distanță în rețeaua formată
sunt dezambiguizate semantic. Wordnet etichetează totodata și relațiile semantice dintre cuvinte.
Principala relație între cuvinte folosită de Wordnet este cea de sinonimie – cuvinte ce
denotă același concept și sunt interschimbabile în multe contexte, aceste sinonime fiind grupate
într-un set neordonat numit synset. În versiunea 3.0 al bazei de date, noiembrie 2012, s-au
înregistrat 155287 de cuvinte organizate în 117659 de synseturi (conform statisticilor oferite de
Laboratorul de Ştiinţe Cognitive al Universităţii Princeton). Fiecare dintre cele 155287 de cuvinte
sunt interconectate printr-un număr de relații conceptuale. Synseturile oferă și o definiție scurtă a
conceptului și în majoritatea cazurilor sunt date și definiții scurte (ca propoziții) pentru a ilustra
modul în care sunt folosiți termenii ce aparțin mulțimii. Cea mai frecventă relație între synset-uri
este relația superior-subordonat numite și hipernimie sau hiponimie. Această relație leagă
synseturi mai generale, de unele mai specifice. Un synset ”x” este în relație de hipernimie cu un
synset ”y” atunci cănd ”y” reprezintă un caz particular al lui ”x”. În acelasi caz se poate spune că
”y” este în relație de hiponimie cu ”x” (de exemplu: cuvântul ”mobilă” este în relație de
hipernimie cu cuvântul ”dulap”).5 De menționat este că anumite cuvinte nu mai pot fi puse în
relație de hiponimie cu nici un alt cuvănt. Acestea se află la radăcina unui arbore ierarhic și se pot
2 Radu Simionescu, POS-tagger hibrid. 2011
3 Radu Simionescu, Graphical grammar studio as a constraint grammar solution for part of speech tagging. 2011
4 Christiane Fellbaum, Representation of Wordnet, 1998
5 Christiane Fellbaum, Representation of Wordnet, 1998
11
numi ”cuvinte de vârf”. Totodată exisă și cuvinte ce nu mai pot fi puse în relație de hipernimie cu
nici un alt cuvânt. Acestea se află printre frunzele unui arbore ierarhic și se pot numi ”instanțe”.
O altă relație existentă în Wordnet este meronimia. Aceasta face legatura între synseturi
ce pot fi considerate parte – întreg, un concept și parți ce îi aparțin (de exemplu ”scaun” –
”spătar”, ”picioare”). Această relație nu este pusă în evidență ierarhic în jos(într-o structură de tip
arbore), ci invers. Se poate spune că un ”scaun” nu conține un ”spătar”, ci că un ”spătar” aparține
unui ”scaun”. Acest lucru se datorează faptului că un ”spătar” poate aparține si altor obiecte.
Synseturile pot fi și verbale, organizate și ele ierarhic într-o structură arborescentă.
Verbele poziționate spre frunzele arborelui exprimă evenimente din ce în ce mai specifice față de
cele cu poziție superioară. Această specificitate este caracterizată de câmpul semantic din care
face parte verbul. Alte moduri în care este evaluată specificitatea pot fi: viteză (pentru verbe ce
exprimă o mișcare), intensitate, volum (verbe ce exprimă cantitate diferită, precum ”vorbește”,
”șoptește”).
Adjectivele sunt organizate în funcție de antonimie, se pune accentul pe relația semantică
dintre antonime. Se poate spune despre două adjective ce sunt în relație de antonimie cu un
același al treilea adjectiv că sunt semantic similare. Această proprietate nu este considerată ca
fiind la fel de accentuată ca cea de antonimie. Aceast tip de synseturi conține si adjective
relaționale, substantivale, ce indică substantivul din care sunt derivate.
Wordnet construiește relații între aceleași părți de vorbire. Astfel, se formează patru
rețele, pentru fiecare dintre cele patru principale părți de vorbire, substantiv, verb, adjectiv și
adverb. Cu toate acestea, se formează relații și la nivel morfologic, numite în ”Representation of
Wordnet” relații morfosemantice. Acestea leagă cuvintele similare semantic, mai preciz acele
părți de vorbire derivate. Astfel se poate pune în evidență care este rădăcina unui cuvânt derivat și
cărei categorii aparține ea.6
O platformă similară Wordnetului pentru limba română a fost dezvoltată de către Dan
Tufiș în proiectul Balkanet ( 2004), ce implementează o nouă rețea de wordneturi pentru cinci
limbi balcanice (turcă, greacă, bulgară, română şi sârbă). Cele cinci limbi au putut fi integrate
datorită faptului că în majoritatea cazurilor relațiile ierarhice se păstrează, chiar dacă nu au
aceeași densitate de concepte peste tot.7
6 Christiane Fellbaum, Representation of Wordnet, 1998
7 Dan Cristea, Resurse lingvistice şi tehnologiile limbajului natural. Cazul limbii române. 2010
12
3.4 Weka
WEKA (Mediul Waikato pentru analiza cunoștințelor) este o platformă populară ce
implementează o colecție de algoritmi de invățare. Weka a fost dezvoltat de către Universitatea
Waikato din Noua Zeelanda și este oferit ca un software open source. Contine instrumente pentru
preprocesarea datelor, clasificare, regresie, reguli de asociere si pentru vizualizare, toate acestea
puând fi facute din interfața oferită, sau folosite direct în alt proiect. Fiind dezvoltat în Java,
Weka a putut fi integrat cu ușurința în aplicația dezvoltată și a oferit un mare avantaj odată cu
accesul la clasificatorii deja implementați.
Metodele de clasificare în capitolul 4 au fost testate cu ajutorul platformei Weka, iar în
funcție de rezultate am ales clasificatorul cel mai optim acestui caz particular. Pe lângă accesul la
clasificatori, Weka oferă si metode de evaluare a unei clasificări, evaluare ce este folosită deseori
în aplicație.
4. Metode de clasificare existente
Problema identificării cerințelor in cadrul proiectelor se reduce în final la una de
clasificare a textului în mai multe clase predefinite (în acest caz: cerințe și non-cerințe).
Clasificarea textului este un subiect ce aparține procesării de limbaj natural, foarte studiat in
mineritul de date, inteligența artificiala, învațare automată, baze de date și extragerea
informațiilor, iar aplicații ale acestuia se regăsesc in domenii diverse , precum: marketing,
medicină, știri, filtrare de e-mailuri si organizare de documente. Conceptul de clasificare a fost
introdus pentru prima oară de către Aristotel, în viziunea căruia categoriile sunt entități discrete
caracterizate de un set de proprietăți însușite de toți membrii ce îi aparțin. Totuși, odată cu
apariția și dezvoltarea internetului și a bazelor de date cu dimensiuni din ce in ce mai mari,
clasificarea a devenit o provocare (clasificarea manuală nu mai este fezabilă).
Problema clasificării se poate defini astfel: Se dă un set de date deja clasificate pentru
antrenare: D = {X1,X2....Xn}, fiecare entitate aparținând unei clase dintr-un set de K clase diferite.
Datele de antrenare sunt folosite pentru a construi un model de clasificare ce leagă anumite
atribute ale entitaților din D cu clasele corespunzătoare. Modelul de clasificare construit anterior
se folosește impreuna cu un nou set de date (de testare) pentru a prezice cărei clase îi aparțin
aceste noi entitați. In funcție de modelul de clasificare, clasa entitaților este prezentată in diferite
moduri: direct ca apartenență, ca probabilitate de apartenență, ca opțiuni ordonate de apartenență
sau alocarea mai multor clase8.
8 S. Gopal, Y. Yang. Multilabel classification with meta-level features 2010.
13
Pentru clasificarea textului au fost adaptate o varietate de metode, printre care cele mai
cunoscute sunt: arbori decizionali, clasificatori bazați pe tipar (folosesc reguli predefinite),
clasificatori SVM (Vector Support Machine), clasificatori ce folosesc o rețea neuronală și
clasificatorul Bayesian. Textul poate fi interpretat ca un set de date cantitativ cu o frecvență si
poziție a fiecărui cuvânt, dar având in vedere că unele cuvinte cheie pot fi rare, cu o frecvență
scăzută, este important ca metoda de clasificare aleasa sa poată fi adaptată pentru a lua în
considerare aceste caracteristici.
4.1 Arbori decizionali
Arborii decizionali sunt clasificatori formați dintr-o structură de tip arbore ce asigura un
model predictiv usor de interpretat. Fiecare frunză a structurii reprezintă o clasă de apartenență,
iar nodurile reprezintă diferite teste ce sunt aplicate unui singur atribut al instanței clasificate.
Arborii decizionali se folosesc la clasificare, fiind parcurși de la rădăcină către frunze, setul de
date fiind împărțit recursiv intr-o serie de subseturi până când se ajunge la frunze de un anumit
număr de ori și tot textul este alocat unei clase de apartenență9.
Clasificarea în acest caz poate fi considerată astfel: se pun un șit de întrebări, șir în care
fiecare întrebare este formulată în funcție de răspunsul primit la precedenta (răspunsurile fiind de
obicei valori binare de adevăr). Nodurile reprezentând teste verifică de obicei existența anumitor
cuvinte cheie in text (definite ca atribute ale textului). Diferite variații ale algoritmului de
construire a arborelui au fost dezvoltate de-alungul timpului, cele mai frecvente fiind ID3
(Iterative Dichotomiser 3), C4.5 (extensie a lui ID3) sau algoritmi foarte asemănători acestora.
Acești algoritmi iau în calcul caștigul de informație ce se obține din alegerea anumitor
atribute pentru a fi testate relativ la celelalte atribute. Calculul acestui caștig de informatie se
bazează pe teoria informației dezvoltată de Claude E. Shannon. Problema alegerii arborilor
decizionali pentru clasificarea textului constă in faptul că arborele poate recunoaște atribute
nerelevante, dar cu frecvență mare, ca fiind esențiale pentru clasificare. Textul fiind o formă de
9 Chris Manning & Hinrich Schütze, Foundations of Statistical Natural Language Processing 1999
14
date ce conține atribute cheie cu frecvență mică, împraștiate spectral, poate introduce erori
aleatoare in arborele de decizie, definite ca zgomot. O altă problemă constă in alegerea numărului
de noduri ce trebuie adăugați arborelui si care sunt aceștia. Un nou nod test poate sa nu
imbunatațeasca precizia arborelui de clasificare, ci chiar sa o scada semnificativ. O soluție pentru
combaterea acestor probleme este prelucrarea anterioară a setului de date pentru a asocia
atributelor o valoare de relevanță statistică astfel încăt să eliminăm testarea atributelor cu
probabilitate mare de a fi irelevante. O altă soluție este cea de cross-validation10
(validarea
încrucișată), ce alege submulțimi aleatorii ale setului de date pentru a se determina cat de bine
acestea ar fi clasificate utilizând modelul clasificator construit, iar la sfârșit se deduce o medie a
rezultatelor.
Arborii decizionali sunt ușor de înțeles si interpretat, forma lor grafică reprezentând un
atu puternic în acest sens. Ei necesita un volum mic de pregătire a datelor in raport cu alte tehnici.
Logica deciziei poate fi urmarită ușor, regulile de clasificare fiind la vedere. Rezultatele obținute
sunt bune pentru muțimi mari de date, dar în cazul unui număr prea mare de clase acesta se poate
deteriora. Totuși, in cazul clasificării textuale, arborii decizonali au de obicei precizie mai scăzută
față de alte metode de clasificare mai robuste precum clasificatorul Bayesian naiv sau rețelele
neuronale11
.
4.2 Clasificatori bazati pe reguli
Clasificatori bazati pe reguli sunt asemănători arborilor de decizie, ce caută legături
între entitățile unui set de date. Aceștia sunt formați dintr-un set de reguli (condiții) ce trebuiesc
indeplinite pentru ca entitatea text sa aparțină unei anume clase. Clasa finală de apartenență este
determinată apoi ca o funcție de clasele determinate de fiecare dintre reguli. Aceste reguli sunt de
tip premisă – concluzie, unde premisa este o condiție cu rezultat de adevar binar, iar concluzia
reprezintă apartenența la o clasă. In cazul clasificării textuale, aceasta condiție specificată este de
obicei formulată prin existența unui cuvânt sau a unor seturi de cuvinte cheie. Se poate folosi si
absența unor cuvinte ca condiție, dar de obicei nu se obțin rezultate satisfăcătoare (nu se obține
un câștig de informație relevant). Intersecția condițiilor in aceeasi regulă este deseori folosită, dar
reuniunea acestora nu, lucru datorat faptului că împarțirea acestor reguli in reguli separate poate
aduce mai mult câștig de informație separate decât reunite. In funcție de tipul setului de date
clasificat se pot face un număr de observații (măsuri impuse) pentru cum ar trebui alese regulile
de clasificare. De exemplu, intr-un set de date de dimensiuni mari, aduce mai mult câștig de
10
Ron Kohavi, A study of cross-validation and bootstrap for accuracy estimation and model selection 1995 11
F. Provost and P. Domingos, Tree induction for probability based ranking. 2003
15
informație o regulă ce este indeplinita de o majoritate de entitați, decât o minoritate. Printr-o
astfel de colecție de reguli setul de date poate fi clasificat in generalele clase, iar in cazul in care
acesta nu a fost clasificat, el poate fi desemnat unei clase minoritare. O alta măsură (denumită in
practică “încredere”) poate fi definită ca: o condiție este necesară si îndeplinită de un set de date,
dar este aceasta și suficientă pentru a clasifica acel set de date. Aceasta măsura din urmă verifică
ponderea unei reguli asupra luării deciziei de clasificare.
În pasul de antrenare al clasificatorului bazat pe reguli, se iau in considerare măsurile
prezentate mai sus pentru a se construi toate regulile. Se testeaza apoi regulile dezvoltate pe un
set de date de testare pentru a identifica care sunt cele relevante acestui nou caz. Regulile pot
desemna setul de date unei clase de apartenență, dar în practică cel mai des întâlnit caz este cel in
care exista contradicții intre reguli. O varietate de metode au fost dezvoltate pentru a trata acest
caz12
si a putea fi identificată cea mai relevantă clasă.
O astfel de metodă poate fi ordonarea regulilor dupa masura de suficiență a lor de a
clasifica setul de date (“încredere”) și prezentate către evaluare primele N reguli (N definit în
funcție de caz). Evaluarea identifică apoi doar care este clasa cel mai des recunoscută de aceste
reguli.
O altă metodă de clasificare bazată pe reguli a fost propusă în ”Automated Learning of
Decision Rules for Text Categorization, ACM Transactions on Information Systems” (C. Apte, F.
Damerau, S. Weiss)13
. Se folosește un algoritm iterativ ce identifică cea mai relevantă regulă
(bazându-se pe măsura de “încredere”) și o înlatură pe aceasta și entitațile corespondente din
setul de date folosit pentru antrenare. Acest pas se execută din nou până când nu se mai găsesc
reguli puternic relevante, astfel dezvoltându-se un model de clasificare format doar din cele mai
importante reguli extrase.
Una din cele mai des răspândite tehnici a fost dezvoltată de către W. Cohen și Y.
Singer14,15
sub numele de RIPPER. În acest caz se determină cele mai frecvente combinări de cuvinte ce
sunt asociate unei clase. S-a dovedit ca această metodă are rezultate foarte bune în special pe un
set de date de antrenare de dimensiuni mici 16
.
12
Guoqing Chen, Hongyan Liu, Lan Yu, Qiang Wei, Xing Zhang , A new approach to classification based on association rule mining 2010 13
C. Apte, F. Damerau, S. Weiss. Automated Learning of Decision Rules for Text Categorization, ACM Transactions on Information Systems 1994. 14
W. Cohen. Learning rules that classify e-mail 1996 15
W. Cohen, Y. Singer. Context-sensitive learning methods for text categorization. 1999 16
W. Cohen, H. Hirsh. Joins that generalize: text classification using Whirl. 1998
16
De menționat este și o tehnică prezentată in “Using and combining predictors that
specialize”17
, denumită “sleeping experts“. Spre deosebire de metodele prezentate anterior,
“sleeping experts“ ia în considerare poziția anumitor cuvinte din diferite fraze. Acestor cuvinte li
se atribuie o pondere cu ajutorul căreia, împreună cu regulile îndeplinite pentru setul de date de
testare se determină clasa de apartenență.
4.3 Clasificatorul Bayesian naiv
Clasificatorul Bayesian naiv este un clasificator simplu, dar foarte des întalnit ce
modeleaza distribuția entitaților din setul de date în setul de clase de apartenență printr-un model
probabilistic ce consideră atributele alese complet independente intre ele. Acest tip de clasificator
ignoră poziția cuvintelor in text și ia în considerare doar frecvența sau apariția acestora. Așadar, o
entitate din setul de date este considerata un “sac de cuvinte“, fiecare cu o diferita frecvență. Des
întâlnite si de menționat sunt doua modele ale clasificatorului Bayesian, diferența dintre ele fiind
dacă se ține cont de frecvența cuvintelor, sau daca acestea se consideră doar ca fiind valori de
adevăr (boolene), unde se verifică doar existența sau inexistența cuvintelor in entitatea testată.
Cele doua modele menționate sunt: Modelul multivariat Bernoulli – cuvintelelor considerate
atribute li se alocă valori binare de adevăr; Modelul multinomial – cel ce ține cont de frecvența
cuvintelor și calculeaza probabilitatea de apartenență la o clasa ca un produs al probabilitaților
atributelor ce aparțin acelei clase. Ambele modele folosesc teorema lui Bayes: fiind date două
evenimente A şi B, se numeşte “probabilitatea evenimentului A condiţionat de evenimentul B”,
notată:
( | ) ( )
( )
Modelul multivariat Bernoulli aplicat cazului textual consideră fiecare cuvânt o valoare
de adevăr binară – un termen poate doar exista sau nu, nu se ține cont de frecvența sau poziția
lui18
. Se consideră un text ce trebuie clasificat, reprezentat ca un “sac de cuvinte“. Acesta conține
mulțimea de termeni M = {t1, t2, ...tn}. Termenii acestei mulțimi sunt cautați in mulțimea de
atribute ale clasificatorului si este construit ⃗ ⟨ ⟩ , unde fiecare xi reprezinta o
valoare binară ce arată daca textul conține sau nu cuvintele cheie din clasificator. Se poate
observa că se păstrează independența atributelor. Pentru fiecare atribut se calculează
probabilitatea de apartenență la fiecare clasă Q cu ajutorul formulei:
17
Y. Freund, R. Schapire, Y. Singer, M. Warmuth, Using and combining predictors that specialize. 1997 18
D. Lewis, The independence assumption in information retrieval 1998
17
( ⃗| ) ∏ ( | )
∏ ( | )
( ( | ))
Modelul multinomial Bernoulli, spre deosebire de cel anterior, ține cont de frecvența cuvintelor.
Textul ce trebuie clasificat este considerat tot ca un “sac de cuvinte“, dar acestora le sunt alocate
frecvențele aferente. Se folosesc următoarele denumiri:
( | ) – probabilitatea posterioară
( ) – probabilitatea apriorică
( | ) – verosimilitate
( ) – evidență
Comform acestor denumiri, formula Bayes poate fi scrisă astfel:
Probabilitate posterioara =
Se consideră un set de date care urmează a fi clasificate utilizând clasificatorul bayesian. Se
consideră atributele, reprezentând cuvintele setului de date, ca variabile aleatoare. Setul de date
cu atributele {A1, A2, ...Ap} se propune sa se clasifice în clasa Qi. Clasificarea este corectă atunci
când probabilitatea condiționată ( | ) este maximă. Problema concretă constă în a
estima direct din date această probabilitate, în vederea maximizării sale. Probabilitățile
posterioare ( | ) se calculeaza pentru toate clasele Qi utilizând formula:
( | ) ( | ) ( )
( )
Se alege apoi clasa Qi care maximizează ( | ), adică clasa Qi care maximizează
( | ) ( ). Clasificatorul Bayesian presupune independența evenimentelor. În
cazul de față se presupune independența reciprocă a atributelor. Pentru o clasa Qi această
independență se rezuma la : ( | ) ( | ) ( | ) ( | ). Se
estimează apoi probabilitățile ( | ) pentru toate atributele Ak si clasele Qi, astfel încât un nou
set de date de test, va fi clasificat în clasa Qj daca probabilitatea corespunzătoare acestei clase:
( ) ∏ ( | )
18
, este maximă față de celelalte. În cazul clasificării textuale, probabilitatea ( | )
, unde
nij este notat ca numarul de apariții ale cuvântului (asociat atributului Aj) în clasa Qi, iar ni
numărul de cuvinte din clasa Qi. Notând cu n numărul total de cuvinte din Q, se obține:
( )
Clasificarea bayesiană naivă prezintă o serie de avantaje. Se obține o robustețe în ceea ce privește
izolarea zgomotului din date, în cazul valorilor lipsă se ignoră atributul respectiv în timpul
estimării probabilităților și este robustă la atribute irelevante19
.
4.4 Metoda celor mai apropiați K vecini
Metoda celor mai apropiați K vecini (K – nearest neighbor) clasifică un nou set de date pe
baza cazurilor similare cele mai apropiate din setul folosit pentru antrenare. Se asociază setului de
date de antrenare o funcție distanță și o funcție de alegere a clasei de apartenență determinată de
clasele de apartenență a vecinilor cei mai apropiați. Algoritmul are ca parametru numărul k de
vecini. Se dă un set de enități a căror clasă de apartenență este cunoscută (x,Q(x)), unde Q(x),
este clasa căreia îi aparține estitatea x. Pentru o nouă entitate y, se determină cele mai apropiate,
în sensul distanței, k obiecte și se combină clasele cărora le aparțin într-o clasă Q, care este clasa
de apartenență a lui y. Pentru alegerea distanței, în cazul valorilor continue se folosește formula:
( ) | |
, dar în general se lucrează cu distanța normalizată:
( ) | |
, unde d este distanța maximă între două numere reale din domeniul considerat. În cazul a doi
vectori cu p caracteristici x = (x1, x2,...,xp) și y = (y1, y2,...,yp), se calculează distanțele între
caracteristici di(xi,yi) și apoi se definesc:
( ) √ ( ) ( )
sau
( ) ( )
( )
19
Marina Gorunescu, Belciug S., Data Mining: Modele predictive şi de clasificare 2012
19
Metoda celui mai apropiat vecin (k=1) poate fi descrisă astfel: “Având de clasificat un
obiect y, alegem cel mai apropiat obiect (în sensul distanței) din eșantionul dat, obiect a cărui
apartenență o cunoaștem si atribuim lui y aceeași clasă.” S-a dovedit experimental că o bună
alegere a parametrului k este numărul cu 1 mai mare decât numărul atributelor. Pentru
clasificarea entității y, se determină (x1, Q(x1)),..., (xk, Q(xk)) cele mai apropiate k entități si
clasele cărora le aparțin. Pentru a găsi cărei clase îi aparține y, există anumite variante. Prima este
de a alege clasa majoritară. Se poate alege și clasa majoritară ponderată. Fiecărei clase i se
atribuie o anumită pondere (în general daca xi este vecinul considerat, ponderea atribuită clasei
Q(xi) este invers proporțională cu distanța dintre obiectul y si obiectul xi). Este posibila si
folosirea masurii de încredere, aceasta fiind definită în clasa atribuită lui y ca raportul dintre
numărul de apariții al clasei alese și k.
Metoda celor mai apropiați k vecini are avantajul că se pot introduce în setul de date
considerat inițial noi entități, ceea ce îmbunatațește rezultatele și nu necesită modificarea
modelului. Dezavantajele acestei metode de clasificare sunt timpul de clasificare, în general
mare, datorita calculelor ce se efectuează în timpul clasificării și faptul ca se stochează în
memorie întreg setul de date.
4.5 Rețelele neuronale
Rețelele neuronale apar ca o tehnologie practică, proiectată pentru rezolvarea cu succes a
multor probleme din varii domenii. Ele pot fi aplicate în modelare, analiza seriilor temporale,
recunoașterea formelor, procesarea semnalelor, teoria controlului datorită caracteristicii lor
fundamentale, abilitatea de a învăța din datele de antrenament cu sau făra supervizare. Cu toate că
acționează pe principiul cutiei negre și nu se poate observa direct modul de funcționare, eficiența
lor in domeniile prezentate mai sus este de necontestat. Sintetic vorbind, rețelele neuronale
reprezintă sisteme neprogramare de procesare adaptivă a informației. Ele pot fi considerate ca un
tip de arhitectuă masivă de calcul paralel, o paradigmă a procesării informației, bazată pe modelul
de procesare a cunoștințelor specific creierului biologic.
În principiu, asemănarea cu modul de acțiune a creierului se poate condensa în
urmatoarele două aspecte: cunoștințele sunt achiziționate de către rețea prin intermediul
procesului de învățare, iar intensitațile conexiunilor inter-neuronale, cunoscute ca ponderi
(sinaptice), sunt utilizate pentru stocarea cunoștințelor câștigate. Rețeaua neurnală procesează
informația în același fel ca și creierul uman, mod care a stat la baza construirii lor. Făcând recurs
la neurologie, fiecare neuron este o celulă specializată a creierului care poate propaga un semnal
electrochimic. În creierul uman, un neuron tip colectează semnale de la alți neuroni vecini printr-
o structură de conexiuni, numite dendrite. Neuronul transmite apoi semnale, ca rezultat al
20
activitații electrico-chimice interioare, prin intermediul unui canal de comunicație numit axon,
care se divide în mii de ramuri. La capătul fiecărei aceste ramuri există o structură numită
sinapsă, care proceseaza semnalul transmis prin axon, transformandu-l într-un efect electric care
inhibă sau excită activitatea de la axon la neuronul la care este conectat. Atunci când un neuron
primește o intrare suficient de puternică (în raport cu pragul de inhibiție), numită intrare de
excitație, el va trimite un semnal electrochimic de-a lungul axonului. Învațarea apare prin
schimbarea modului de acțiune a sinapselor, adică influența neuronului asupra celorlalți neuroni,
conectați cu el.
Rezumând cele de mai sus, neuronul primește informație de la ceilalți neuroni prin
intermediul dendritelor, o procesează, apoi trimite semnale răspuns prin intermediul axonului,
moment în care sinapsele, prin modeificarea unor praguri de inhibiție/excitație, controlează
acțiunea asupra neuronului conectat. Prin reglarile fine de la nivelul sinapselor, pe baza învățării
din experiența acumulată, se obțin ieșiri optime ca răspunsuri la intrările primite. Un neuron este
astfel fie inhibat, fie excitat, în funcție de semnalul primit de la alt neuron, iar, în raport de acesta,
va răspunde sau nu, influențând acțiunea neuronilor conectați în rețea.
Un neuron artificial, privit ca un singur mecanism, are un anumit număr p de intrări,
privite ca valori reale xi, ponderate cu ponderile wi, care sunt însumate și apoi introduse într-o
funcție de activare φ, pentru a produce o anumită ieșire, depinzând de un anumit prag T. La fel
ca si cazul unui sistem nervos natural, rețeaua neuronală artificială este compusă dintr-un număr
mare de elemente de procesare – neuronii artificiali – puternic interconectați și lucrând în paralel
pentru rezolvarea unei anumite probleme. În consecință, se consideră neuronul artificial drept
componenta de bază a unei rețele neuronale și nu ca un mecanism singular, lucând independent.
Astfel, într-o rețea neuronală, o intrare reală xi care ajunge la intrarea sinapsei i, conectată
cu neuronul j, va fi înmulțită cu ponderea sinaptică wji. În acest model neuronal matematic,
intrările xi reprezintă tocmai nivelele de activitate ale altor neuroni, care sunt conectați la
neuronul în cauză, iar ponderile wji reprezintă constrângerile interconexiunilor (sinapselor) între
neuroni. De remarcat este că, spre deosebire de sinapsele din creier, ponderile sinaptice ale unui
neuron artificial pot aparține unui interval care să conțină și valori negative. Din punct de vedere
matematic, „activitatea” neuronului j al rețelei neuronale poate fi descrisă prin următoarea
ecuație:
∑
,unde x = (x1, x2, ..., xp) reprezintă vectorul intrare, iar wj = (wj1, wj2, ..., wjp) reprezintă vectorul
ponderilor (sinaptice), iar uj este ieșirea corespunzătoare intrării x.
21
Activitatea de declanșare a neuronului este dată de ecuația:
( ) {
unde reprezintă deplasarea, este funcția de activare (în general, o funcție monotonă), iar
este semnalul-ieșire al neuronului. Uzual, pragul este ales egal cu zero.
Funcția de activare definește ieșirea neuronului artificial pe baza unei combinații liniare u,
numită și output combinator liniar. Dintre cele mai cunoscute tipuri de funcții de activare trebuie
menționate următoarele:
1. Funcția de activare Heaviside:
{
Cazul acesta, cunoscut totodată ca și modelul McCulloch-Pitts (MCP), prezintă un output binar și
descrie proprietatea all-or-none a unui MCP. Alternativa la funcția de activare Heaviside este
dată de:
{
O generalizare simplă a funcției prag este reprezentată de funcția de activare treaptă, dată de
următoarea formulă:
{
2. Funcția de activare liniară pe porțiuni:
{ | |
3. Funcția de activare liniară:
( )
4. Funcția de activare gaussiană:
( ) (
)
5. Funcția de activare sigmoidă:
Funcția de activare sigmoidă este o funcție cu o reprezentare grafică de tip ”S”, fiind cea mai
utilizată funcție de activare în NN. De exemplu, o astfel de funcție este reprezentată de funcția
logistică care aplică intervalul (-∞,∞) peste intervalul (0, 1):
22
( )
( )
unde a este parametrul pantă al sigmoidei.
De remarcat este faptul că modelul neuronal descris mai sus este unul determinist,
comportamentul intrare/ieșire este determinat pentru toate intrările. Există totodată și o
alternativă stochastică a modelului, în care decizia de declanșare este probabilistă.
Modelul perceptronului Rosenblatt
Modelul de bază al unui neuron artificial, cunoscut și ca modelul McCulloch-Pitts, are
așa cum s-a observat ponderi fixe și ieșire binară, fără posibilitatea de învățare sau adaptare.
Pasul următor a fost reprezentat de modelul perceptronului Rosenblatt. Astfel, plecând de
la modelul inițial, perceptronul a fost dotat cu un mecanism simplu de învățare, bazat pe
feedback-ul diferenței între ieșirea obținută și cea dorită. Numele de perceptron provine de la
scopul originar al lui Rosenblatt, acela de a distinge imagini alb negru ale unor forme geometrice,
ultilizând intrări binare primite de la foto-senzori și funcția de activare treaptă.
Scopul utilizării perceptronului este acela de clasificare corectă a unui set de stimuli
externi într-una din două categorii decizionale (clase) și .
Regula decizională pentru problema de clasificare este aceea de a atribui punctul x,
reprezentat de vectorul ( ), clasei dacă ieșirea perceptronului este +1 și clasei
, dacă ieșirea este -1.
În forma cea mai simplă a unui perceptron există două regiuni de decizie în spațiul (p+1),
regiuni separate de un hiperplan dat de formula:
∑
adică două regiuni liniar separabile. Concret există un vector pondere w, astfel încât:
pentru orice vector de intrare x aparținând clasei
pentru orice vector de intrare x aparținând clasei
Ponderile sinaptice pot fi adaptate utilizând diferite proceduri.
Perceptronul reprezintă o rețea cu un singur strat de ponderi sinaptice, care utilizează doar
date de intrare primare, neprelucrate, și care în consecință are capacitate foarte limitată.
23
Deoarece scopul utilizării algoritmului de învățare al perceptronului este acela de a
produce un sistem efectiv de clasificare, este natural să definim o funcție eroare în termeni de
numărul total de clasificări eronate raportate la datele de antrenament.
Perceptronul reprezintă o formă simplă de NN, utilizată pentru a clasifica modelele liniar
separabile.
În principiu, el constă într-un singur neuron artificial cu ponderi sinaptice ajustabile.
Perceptronul construit pe baza unui singur neuron artificial este limitat cu privire la capabilitatea
clasificării de modele aparținând la mai mult de două clase.
Astfel, prin extinderea stratului de ieșire pentru a putea include mai mult de un neuron,
modelele aparținând la mai mult de două clase se pot clasifica. Aproape în același timp în care
Rosenblatt dezvolta teoria perceptronului, Wildrow și colaboratorii săi lucrau în aceeași direcție,
utilizând un sistem numit ADALINE (Adaptive Linear Element) care utilize un algoritm de
învățare mult mai bun a cărui extensie era folosită în cadrul perceptronului multi-strat, deși avea
aceeași formă ca și perceptronul.
În perioada în care perceptronul a fost studiat experimental, în 1960, s-a constatat că el
poate rezolva eficient multe probleme.
Dificultatea reală în cadrul utilizării perceptronului este aceea potrivit căreia elementele
de procesare sunt fixate de la început, neputând fi ajustate problemei particulare considerate.
Tipuri de rețele neuronale artificiale
Următorul pas în explicarea felului în care se construiește o rețea neuronală este
reprezentat de modul în care mai mulți neuroni pot fi interconectați cu scopul de a crea o
structură funcțională și complexă apropiată de o rețea neuronală adevărată.
Elementele de bază ale acestei construcții sunt: unitățile de intrare alimentate cu
informații din lumea exterioară, unitățile din interiorul rețelei, neuroni ascunși ce controlează
acțiunile din interiorul rețelei, și unitățile de ieșire ce sintetizează răspunsul rețelei. Acești
neuroni trebuie interconectați pentru a face rețeaua complet funcțională.
Pentru a clasifica modelele NN, se folosește arhitectura lor specifică, modul de operare,
cât și stilul de învățare astfel:
Arhitectura NN face referire la organizarea topologică a neuronilor, constând în numărul
acestora, numărul straturilor de neuroni, structura straturilor, direcția semnalului și
reciprocitatea
Modul de operare face referire la natura activităților din timpul procesării informației
24
Stilul de învățare face referire la modul în care NN își însușește cunoștințe din datele de
antrenament
Așa numitul feedback, prezent sau nu în astfel de sisteme, reprezintă o chestiune de bază
în acest context. Într-un anumit sistem dinamic există feedback în momentul în care datele de
ieșire ale unui element din sistem au o anumită influență asupra datelor de intrare ale acelui
element, prin intermediul circuitului de reacție.
O NN are o structură de tip feedforward dacă semnalul acesteia circulă de la intrare spre
ieșire, totodată trecând prin toate unitățile ascunse ale rețelei, datele de ieșire ale neuronilor
trecând prin straturile următoare și nu spre cele precedente. Aceste rețele au proprietatea că datele
de ieșire pot fi exprimate ca funcții deterministe de date de intrare. Un set de valori aplicat la
intrarea în rețea se transmite prin intermediul funcțiilor de activare de-a lungul rețelei spre ieșirea
acesteia prin procesul de propagare înainte. O astfel de rețea are un comportament stabil în
funcționare.
Spre deosebire de NN de tip feedforward, există și rețele în care există circuite de reacție,
rețele numite NN recurente.
În ceea ce privește arhitectura NN pot fi menționate 3 categorii fundamentale de astfel de rețele:
NN feedforward cu un singur strat. În acest caz, există un strat intrare al nodurilor sursă
urmat de stratul de ieșire al nodurilor de calcul.
NN feedforward multistrat. Spre deosebire de rețeaua anterioară, în acest caz există unul
sau mai multe straturi ascunse ale căror elemente se numesc neuroni ascunși, rolul lor
fiind acela de a acționa între stratul de intrare și cel de ieșire, cu scopul de a îmbunătăți
performanța rețelei. Schematic, prin stratul de intrare se introduce informația din exterior,
care se constituie în datele de intrare aplicate neuronilor din stratul al doilea.
NN recurente. Acest tip de rețea se deosebește de celelalte prin existența a cel puțin unui
circuit de reacție. Prezența unui astfel de circuit are o importanță mare atât în modul de
învățare al rețelei, cât și în performanța acesteia.
Învățarea, privită în contextul NN, este reprezentată de procesul de adaptare la mediul
exterior al rețelei printr-un proces de stimulare din partea mediului. Schematic, aceasta
funcționează astfel: mediul stimulează rețeaua, parametrii sistemului capătă anumite valori ca
reacție la acești stimuli, urmând ca NN să răspundă mediului exterior bazat pe noua sa
configurație.
Datorită faptului că există mai multe moduri de reglare a parametrilor rețelei, există și mai
multe tipuri de învățare. De menționat sunt următoarele reguli de învățare:
25
Învățarea cu corectarea erorii, ce se bazează pe un mecanism de control al diferenței
dintre răspunsul corect și cel real al rețelei
Învățarea bazată pe memorie ce utilizează memorarea explicită a datelor de antrenament
Învățarea hebbiană ce se bazează pe considerații neurobiologice
Învățarea competitivă
Învățarea Boltzmann, bazată pe idei din mecanica statistică
În cazul curent, de clasificare a textului, intrările rețelei neuronale sunt reprezentate de
vectorul Xi, ce conține frecvențele cuvintelor din setul de date i. Anumite implementări ale
rețelelor neuronale au fost dezvoltate pentru cazul clasificarii textuale. Acestea pot fi găsite în:
„A Neural Network Approach to Topic Spotting” (E. Wiener, J. O. Pedersen, A. S. Weigend)20
,
“Feature selection, perceptron learning, and a usability case study for text categorization.” (H. T.
Ng, W. Goh, K. Low)21
, “Mistake-driven Learning in Text Categorization” (I. Dagan, Y. Karov,
D. Roth)22
. Se încearcă în general să se reducă numarul de calcule necesare pentru antrenarea
rețelei neuronale. Pentru adaptarea la caracterul rar și distribuit spectral al atributelor datelor de
tip text, se folosesc mai multe straturi de neuroni. Totuși, rezultatele obținute nu sunt mult
îmbunătațite, iar cu comparativ cu căt de mult crește timpul de antrenare, soluția nu este una
ideală.
4.6 Mașini cu suport vectorial
O clasă specială de rețele universale de tip feedforward este reprezentată de așa-numitele
mașini cu suport vectorial (Support Vector Machines – SVM), ulilizate intens în probleme de
clasificare a formelor și regresie neliniară. SVM-urile sunt bazate pe teoria învățării statistice
(SLT).
O SVM reprezintă o mașină liniară înzestrată cu caracteristici deosebite, ce are la bază
principiile minimizării riscului structural (SRM) și teoria învățării statistice.
În consecință, o SVM poate produce o performanță bună a generalizării în cazul
recunoașterii formelor, fără a încorpora cunoștințe despre domeniul problemei, fapt ce îi conferă
o caracteristică unică printre modelele de învățare.
20
E. Wiener, J. O. Pedersen, A. S. Weigend. A Neural Network Approach to Topic Spotting. 1995 21
H. T. Ng, W. Goh, K. Low. Feature selection, perceptron learning, and a usability case study for text
categorization.1997 22
I. Dagan, Y. Karov, D. Roth. Mistake-driven Learning in Text Categorization 1997
26
Din prezentarea anterioară a NN, rezultă următoarea dilemă: Perceptronul, în ciudat
algoritmului simplu și eficient de învățare, are o putere limitată de clasificare, din cauza faptului
că învață doar frontierele de decizie liniare în spațiul datelor de intrare. Rețelele multi-strat au o
putere mai mare de clasificare dar sunt dificil de antrenat din cauza multitudinii de minime locale
și a dimensiunii ridicate a spațiului ponderilor.
O soluție la această problemă poate veni din partea mașinilor cu nucleu (kernel machines)
care posedă algoritmi de antrenare eficienți și care pot reprezenta frontiere neliniare, complexe.
Conceptual, funcționarea SVM-urilor se bazează pe următorii doi pași:
Aplicarea neliniară a spațiului datelor de intrare într-un spațiu de dimensiune mare –
spațiul caracteristicilor – spațiu ascuns atât pentru datele de intrare cât și pentru cele de
ieșire;
Construirea unui hiperplan de separație pentru caracteristicile obținute la pasul anterior;
Din punct de vedere teoretic, primul pas are la bază teorema lui Cover privind
separabilitatea modelelor, în timp ce al doilea se bazează pe principiile minimizării riscului
structural.
Din punct de vedere tehnic, construcția hiperplanului de separație se bazează pe evaluarea
nucleului unui produs scalar.
Principiile care stau la baza construcției și funcționării SVM-urilor se evidențiază prin
următoarele: considerăm mulțimea de antrenament * +, în care
reprezintă modelele datelor de intrare, iar datele de ieșire corespunzătoare. Presupunem că cele
două clase = 1 (modelele pozitive) și = -1 (modelele negative) sunt liniar separabile.
În acest caz, ecuația hiperplanului de separație este dată de:
unde x este vectorul datelor de intrare, w este vectorul pondere ajustabil, iar b deplasarea.
Pentru un vector pondere w dat și deplasarea b cunoscută, separarea definitivă de
hiperplan prin formulele de mai sus, între punctele cele mai apropiate din cele două regiuni, se
numește marginea separării. Scopul utilizării SVM-urilor este acela de a găsi acel hiperplan
pentru care marginea să fie maximă. În acest caz, suprafața de decizie se numește hiperplan
optimal.
27
Punctele particulare ( , ) ce satisfac cele două ecuații corespunzătoare și se află pe
dreptele ce delimitează marginea se numesc vectori suport. De aici provine și denumirea
modelului – mașini cu suport vectorial.
Acești vectori se găsesc pe frontierele de decizie, separând cele două categorii, ei fiind cel
mai dificil de clasificat. Pe aceștia se bazează modul concret prin care se separă cele două
categorii, suportul vectorial al actului de decizie.
SVM-urile sunt privite ca modele ce provin din principiile minimizării riscului structural
și cele din teoria învățării statistice. Din teoria învățării statistice se cunoaște faptul că
dimensiunea VC (Vapnik și Chervonenkis) a unei mașini de învățat determină modul în care o
structură în serie de funcții de aproximare poate fi utilizată. Totodată, se cunoaște și faptul că
dimensiunea VC a unui set de hiperplane de separație într-un spațiu m dimensional este m+1.
Pentru a aplica metoda minimizării riscului structural, este nevoie să se construiască un
set de hiperplane de separație de dimensiune VC variabilă, astfel încât riscul empiric și
dimensiunea VC să fie minimizate simultan.
Clasificarea a trei tipuri de SVM-uri în funcție de nucleu:
Mașină polinomială de învățare având nucleul de forma K(x, ) = ( ) , unde
parametrul p este specificat a priori de către utilizator.
Rețea cu funcție radial-basis – având nucleul gaussian de forma K(x, ) = (
|| || ), unde dispersia , comună tuturor nucleelor, este specificată a priori de către
utilizator.
MPL cu un singur strat ascuns, cunoscut și ca rețea de tip perceptron cu două straturi, având
nucleul de forma K(x, ) = ( ), de parametri și ce trebuie aleși cu
grijă pentru a găsi soluția optimă.
28
5. Descrierea aplicației
Platforma pentru identificarea automată a cerințelor a fost dezvoltată integral în Java, în
mediul de dezvoltate ”Eclipse”. Aceasă alegere a fost facută pentru folosirea și integrarea în
proiect cu ușurință a resurselor ”Stanford Parser” și ”Wordnet”. Aplicației i-a fost construită o
interfață pentru a oferi un mod de lucru cât mai intuitiv, dar se poate integra cu ușurință în funcție
de caz în diferite alte aplicații sau medii de dezvoltare. Am redus problema identificării cerințelor
la una de clasificare a textului în două clase predefinite, cerințe si non-cerințe. Am recurs la
această metodă pentru a pune în evidență nu doar relațiile dintre cerințe si informația conținută de
acestea, dar și relațiile dintre non-cerințe și informații ce nu trebuie catalogate drept cerințe.
Fig. XX - Structura unei SVM
Fig. 4. - Structura unei SVM
29
Clasificarea textului se face cu un clasificator Bayesian naiv antrenat pe o bază de date a
cerințelor marcate anterior. Pentru rezultate bune se propune folosirea aplicației în cadrul
aceluiași proiect, sau aceluiași document.
În figura 5.1 este prezentată diagrama de funcționare a aplicației. Pentru a antrena
clasificatorul, este necasară o bază de date a documentelor cu cerințe identificate anterior. În
această variantă a aplicației, pot fi interpretate doar documente text, deci este necesară extragerea
informației de tip text din documentele cu cerințele marcate. Această extragere se face în partea
de preprocesare si este dependentă de tipul de document ce se analizează. Datorită acestui lucru,
preprocesarea nu este inclusă în aplicație, dar în funcție de caz se poate implementa cu ușurință.
Odată terminată preprocesarea rezultă două documente în format text, unul ce cuprinde toate
cerințele marcate, iar al doilea non-cerințele. Aceste documente sunt analizate în faza de
extragere a atributelor, se caută cele mai relevante atribute, iar în funcție de acestea se analizează
fiecare cerință si non-cerință. Rezultatul final al etapei de extragere a atributelor este generarea
unui fișier cu formatul ARFF, ce poate fi interpretat cu ușurință de către clasificator. Acest fișier
ARFF pastrează o listă a atributelor identificate și valorile cerințelor si non-cerințelor relative la
atribute. Antrenarea clasificatorului se face asupra fișierului ARFF generat anterior, iar rezultatul
este modelul clasificatorului, ce va fi salvat într-un format corespunzător (.model).
Identificarea cerințelor folosind modelul salvat al unui clasificator se face asupra unui
fișier în format text. Iarăși este necesară o parte de preprocesare pentru a extrage toată informația
de tip text din documentul ce conține specificația cu cerințe. În faza de clasificare (utilizare a
modelului clasificatorului) se citesc din modelul clasificatorului atributele asupra cărora a fost
antrenat. Se generează temporar un fișier ARFF ce conține valorile propozițiilor extrase din
documentul text relative la atributele identificate în modelul clasificatorului. În final, modelul
clasificatorului atribuie fiecărei propoziții o probabilitate de apartenență la cele două clase,
cerințe și non-cerințe. Dacă aceste probabilități trec peste un anumit grad de certitudine, ele sunt
marcate în interfață ca fiind cerințe sau non-cerințe. În această etapă se pot modifica manual
marcările propozițiilor, sau se pot identifica automat cerințele aflate în același context cu cele
deja marcate.
30
Format dorit de stocare a
cerințelor
(text,xml)
Reprezentare marcată a
cerințelor si non-cerințelor
identificate
Documente cu specificații
- conține cerințele ce
trebuie identificate
Document cu textul
specificației
(format text)
Model al clasificatorului
(nume.model)
Fișier ARFF
(interpretabil de
clasificator)
Documente cu specificații
ce conțin cerințele
marcate anterior
Documente separate
de cerințe și non-cerințe
-set de antrenare
(format text)
Preprocesare, extragere a informației text
Extragerea atributelor cele mai semnificative,
generare ARFF
Antrenarea clasificatorului
Export
Clasificare
e
Corectare manuală, identificare
a cerințelor din același context
Preprocesare, extragere
a informației text
Figura 5.1 – diagrama de funcționare a aplicației
31
5.1 Interfața aplicației
Interfața aplicației este simplistă și intuitivă (Figura 5.1):
Panoul principal al interfeței cuprinde un chenar de text editabil, patru butoane în partea
de jos și două butoane de tip meniu în partea de sus a interfeței. Chenarul de text editabil are
scopul de a afișa textul analizat, acesta putând fi modificat cu ușurintă de către utilizator. O
funcție importantă a chenarului este de a reprezenta diferența dintre cerințe si non-cerințe.
Identificarea unei propoziții ca cerință sau ca non-cerință se poate face manual sau de către
program în mod automat și poartă numele de ”marcare”.
Marcarea manuală se face mutând cursorul în dreptul propoziției dorite si apăsându-se
butonul ”Tag” sau ”Untag”. Acțiunea are ca efect imediat schimbarea culorii rândului în funcție
de butonul apăsat si de starea precedentă a propoziției. Totodată se schimbă si valoarea
variabilelor din memoria programului ce memorează clasa în care este clasificată propoziția.
Astfel, cerințele vor fi marcate cu verde, iar non-cerințele cu roșu. Propozițiile ce nu au fost
marcate nici ca cerințe, nici ca non-cerințe, nu au trecut peste un prag de certitudine al aplicației
în deciderea asupra cărei clase aparțin. Aceste propoziții pot fi marcate manual, iar în cazul în
care sunt lăsate nemarcate, vor fi considerate non-cerințe la sfârșitul evaluării.
Figura 5.1.1 – interfața dezvoltată
32
Pentru a putea utiliza butoanele de marcare, ”Tag” și ”Untag” , cât și butonul ”Parse”,
trebuie să fie introdus text în chenarul editabil, fie de către utilizator manual, fie încărcat direct
dintr-un fișier. Daca textul a fost introdus manual, trebuie apăsat butonul ”Indent”, ce împarte
textul aflat în chenarul editabil în propoziții sau fraze, fiecare pe un singur rând. Astfel ele pot fi
marcate cu ușurință ca cerințe și non-cerințe, iar reprezentarea grafică a diferenței este ușor
observată. În cazul în care textul nu este introdus manual, ci este încărcat dintr-un fișier,
împărțirea propozițiilor pe rânduri se face automat și nu mai este necesară apăsarea butonului
”Indent”. Butonul ”Parse” are funcția de a analiza cerințele marcate și de a identifica cerințele din
același context.
Din meniul aplicației, butonul sus stânga, ”File”, se extinde o listă cu 4 opțiuni, ”Use
Classifier”, ”Train Classifier”, ”Test Classifier” și ”Exit”. Din acestea 4, ”Train Classifier”
deschide la rândul ei alte trei opțiuni, ”Train on Attribute-Relation file” și ”Train on
Requirements File”, respectiv ”Create testing instance” și ”Test classifier”. Toate aceste butoane
schimbă panoul principal al interfeței și îi acordă utilizatorului acces la alte resurse.
Panoul aferent butonului ”Use Classifier” prezintă două câmpuri de text editabil, unde
trebuie introdusă calea către fișierul cu propozițiile dintre care trebuie identificate cerințele (Data
File), respectiv calea către modelul clasificatorului ce urmează să fie folosit (Classifier file). În
Figura 5.1.2 – exemplu de marcare în interfață
33
versiunea curentă fișierul cu propozițiile este suportat doar daca este de tip text (.txt). De
menționat este că fișierul cu modelul clasificatorului (.model) trebuie construit și salvat anterior
dintr-unul din panourile din ”Train Classifier”. Odată aleasă calea catre fișierul cu propoziții și
către modelul clasificatorului, se poate utiliza butonul ”Use Classifier”, ce va încărca propozițiile
în panoul principal și le va marca ca cerințe sau non-cerințe pe cele ce trec peste un grad de
certitudine în deciderea asupra cărei clase aparțin. Schimbarea către panoul principal va fi facută
automat odată ce s-a încheiat clasificarea. Această clasificare facută automat poate fi modificată
manual de către utilizator, iar cu ajutorul butonului ”Parse” se inițializează alt pas al identificării
automate de cerințe ce analizează iarăși textul și marchează cerințele ce nu au trecut pragul de
certitudine al algoritmuli (această ultimă identificare se face în funcție de context).
Din submeniul ”Train Classifier” sunt posibile trei opțiuni, ”Train on Attribute-Relation
file”, ”Train on Requirements file” și ”Create an Attribute-Relation file”. Pentru a pune în
evidență structura unui fișier de tip Attribute-Relation file (.ARFF) voi trata mai întâi cazul
”Train on Requirements file”. Alegerea acestei opțiuni are ca efect schimbarea panoului principal
cu cel de antrenare a clasificatorului cu ajutorul a două fișiere separate, de cerințe si de non-
cerințe, (Figura 5.1.3).
Odată aleasă calea către fișierele ce conțin propozițiile, va putea fi accesat butonul ”Train
classifier” și cursorul ”Number of features”. Acest cursor are rolul de a permite utilizatorului să
aleagă numărul de atribute cu care va fi antrenat clasificatorul. Numărul de atribute de antrenare
are un rol foarte important cu efecte evidente asupra preciziei de clasificare. În funcție de
Figura 5.1.3 – panoul de antrenare al clasificatorului
34
numărul de cerințe și non-cerințe folosite pentru antrenare aplicația alege inițial un număr optim
de atribute, dacă acesta va fi schimbat sau nu, rămâne la latitudinea utilizatorului.
Primul pas de antrenare a clasificatorului, este de a analiza cerințele și non-cerințele, iar în
funcție de numărul N de atribute alese, se vor identifica cele mai semnificative N cuvinte ce
deosebesc cerințele de non-cerințe. Un fișier de tip Attribute-Relation (.ARFF) este generat, unde
sunt scrise atributele alese anterior, împreună cu: valorile fiecărei propoziție pentru acele atribute
și categoria din care face parte acea propoziție. Acest fișier ARFF este formatul ce poate fi
evaluat de către clasificator. La sfârșitul antrenării trebuie salvat modelul clasificatorului cu
terminația ”.model”. O opțiune este prezentată și pentru salvarea fișierului ARFF ce a fost
generat în timpul antrenării. Cu ajutorul acestuia se poate genera iarași clasificatorul, sau se poate
testa performanța altui clasificator. Totodată, se vor prezenta în același panou câteva date
generale despre clasificatorul ce a fost antrenat și o evaluare a performanțelor acestuia.
Opțiunile ”Train on Requirements file” și ”Create an Attribute-Relation file” ale
submeniului ”Train Classifier” au aceeași funcționalitate prezentată mai sus, dar în doi pași. Se
poate crea mai întâi fișierul ARFF, cu un număr de atribute dat, apoi construit un clasificator pe
baza lui. Panourile sunt similare cu cel prezentat în figura 5.1.3 și nu vor mai fi explicate.
Submeniul ”Test Classifier” permite evaluarea performanțelor unui clasificator asupra
unui set de date. În acest set de date, trebuie știută clar diferența dintre cerințe si non-cerințe
pentru a putea fi comparată cu analiza clasificatorului. Astfel, panoul aferent butonului ”Test
Classifier” prezintă trei câmpuri editabile de text pentru calea către trei fișiere, fișierul text cu
cerințe, fișierul text cu non-cerințe și modelul clasificatorului ce urmează să fie folosit. În urma
apăsării butonului ”Test classifier”, o evaluare va fi facută si prezentată în chenarul din partea de
jos a panoului (Figura 5.1.4).
35
5.2 Extragerea atributelor pentru clasificare
Extragerea atributelor relevante este un pas deosebit de important în procesul de
clasificare, ce are influențe directe asupra preciziei. Performanțele clasificatorului sunt afectate de
către numărul de atribute, și concret care sunt acestea.
Ca atribute sunt considerate cuvintele cele mai relevante în procesul de clasificare.
Problema constă în identificarea acestora în cadrul setului de date de tip text. Folosind un
clasificator Bayesian naiv, am considerat setul de date drept un ”sac de cuvinte” (concept explicat
în Capitolul 4), fiecare cuvânt avănd o frecvență de apariție în text.
Figura 5.1.4 – evaluare a unui clasificator
36
Primul pas în extragerea atributelor este determinarea numărului acestora. Un număr prea
mare de atribute alese poate introduce un zgomot în modelul clasificatorului, pe când un număr
prea mic de atribute pot să nu fie găsite în textul ce trebuie clasificat, iarăși fiind afectate
performanțele. Experimental s-a descoperit că numărul de atribute trebuie sa fie proporțional cu
mărimea bazei de date pe care se face antrenarea. Aplicația permite utilizatorului ca acesta să
schimbe numărul de atribute selectat, dar inițial acesta este ales la jumătate din numărul de
propoziții pe care se face antrenarea.
Experimental am identificat că cele mai relevante cuvinte, ce pot fi alese ca atribute, sunt
substantivele. Acest lucru este dovedit de următoarea presupunere: tratând textul ca o descriere
(descriere a unui produs), se pot în general organiza propozițiile ierarhic, plecând de la obiectul
descris către cele mai mici trăsături ale acestuia. Legăturile dintre propoziții sunt facute prin
intermediul substantivelor, ce identifică diferite părți ale obiectului descris. Verbele, adjective și
restul părților de vorbire pot aparține fiecărei componente ale obiectului, dar substantivele în
general (desemnând părți ale obiectului) pot fi organizate într-o structură ierarhică. Nu este de
interes cum sunt trăsăturile obiectului descris, ci care sunt acestea.
Al doilea pas în extragerea atributelor este identificarea substantivelor cu ajutorul
interpretorului Stanford Parser (Capitolul 3.2). Astfel se ajunge de la un ”sac de cuvinte” la un
”sac de substantive”, pentru fiecare calculandu-se frecvența de apariție în text. Urmează alegerea
celor mai relevante cuvinte.
Iarăși marimea bazei de date pe care se face antrenarea are un rol important. O metodă
prezentată în capitolul 4 este de a alege cele mai frecvente cuvinte. În general această modalitate
are rezultate bune, dar sunt cazuri când un cuvânt poate avea frecvență mare de apariție, dar acea
frecvență de apariție este aceeași și în cerințe și în non-cerințe. În cazul utilizării unei baze de
date de dimensiune mică sau medie pentru antrenare, se recomandă utilizarea acestei metode, de
a alege cele mai frecvente cuvinte. Cu cât baza de date crește în dimensiuni, pot apărea tot mai
multe cuvinte cu frecvență crescută, dar irelevante clasificării. Astfel, se propune următoarea
metodă. Cuvintele nu vor mai fi caracterizate de frecvența lor de apariție în text, ci de diferența
frecvențelor de apariție în cele două clase. Pentru a trata faptul că cele două clase pot avea
dimensiune semnificativ diferită, această diferență nu este facută direct, ci ponderată cu raportul
celor două clase. Această metodă utilizată tinde să aleagă ca atribute cuvinte ce aparțin mai mult
unei clase, decât celeilalte, așadar poate fi impus numărul de atribute ce vor caracteriza fiecare
clasă. Acesta poate fi considerat jumătate din numărul total de atribute, dar poate fi și optimizat
pentru a îmbunătați precizia clasificatorului.
De menționat este faptul că un substantiv poate fi prezent în text sub forme diferite, cu
articulații diferite. Pentru corecta identificare am folosit resursa WordNet (Capitolul 3.3). Cu
ajutorul WordNet-ului am redus toate substantivele la forma de bază pe parcursul identificării
37
pentru a putea face comparațiile corecte. O altă problema a cărei soluție a fost tot WordNet este
folosirea sinonimelor în diferite propoziții. Cu toate că au același concept, două substantive ar fi
fost identificate separat, cu frecvențe separate. Gruparea sinonimelor cu ajutorul WordNet-ului
sub același cuvânt a ajutat la corecta calculare a frecvențelor substantivelor.
5.3 Structura fișierului Attribute-Relation File Format
Un fișier ARFF este un document de tip text ce descrie o listă instanțe (în acest caz
propoziții) ce au în comun aceleași atribute.23
Are două secțiuni diferite, secțiunea antet și
secțiunea cu date.
Secțiunea antet cuprinde o listă cu atributele utilizate si forma sub care este exprimată
valoarea lor (ex: numeric, șir de caracter, dată). Formatul sub care sunt oferite atributele este
următorul:
@attribute <nume-atribut> <tip-atribut>
Un exemplu de astfel de secțiune este:
@ATTRIBUTE sepallength NUMERIC
@ATTRIBUTE sepalwidth NUMERIC
@ATTRIBUTE petallength NUMERIC
@ATTRIBUTE petalwidth NUMERIC
@ATTRIBUTE class {Iris-setosa,Iris-versicolor,Iris-virginica}
Secțiunea de date începe cu identificatorul ”@DATA”. Aceasta conține diferitele valori
ale propozițiilor pentru atributele specificate în secțiunea antet, aranjate fiecare pe un rând
(simbolul ce indică sfârșitul rândului indică și sfârșitul datelor pentru propoziția respectivă). La
sfârșitul rândului este trecută valoarea pentru atributul clasă, ce specifică cărei clase aparține
propoziția. O valoare necunoscută pentru unul din atribute, inclusiv pentru cel aferent clasei este
trecută cu semnul ”?”. Un exemplu de secțiune de date este prezentat mai jos. De menționat este
faptul că exemplul de secțiune de date de mai jos corespunde exemplului de antet prezentat
anterior. Se observă legătura dintre atributele din antet și valorile lor pentru fiecare propoziție din
secțiunea de date.
@DATA
23
Conform descrierii oferite pe site-ul Weka
38
5.1,3.5,1.4,0.2,Iris-setosa
4.9,3.0,1.4,0.2,Iris-setosa
4.7,3.2,1.3,0.2,Iris-setosa
4.6,3.1,1.5,0.2,Iris-setosa
5.0,3.6,1.4,0.2,Iris-setosa
5.4 Identificarea cerințelor ce aparțin contextului
Identificarea cerințelor ce aparțin contextului este un pas important ce se poate efectua în
urma clasificării, sau în urma marcării manuale a cerințelor și non-cerințelor. Scopul este de a
căuta în text propozițiile ce nu au trecut pragul de certitudine al clasificării, dar care aparțin
contextului. Experimental am dedus că aceste propoziții ce au legătură directă cu cerințele deja
marcate sunt la rândul lor cerințe.
Acest lucru este verificat de următoarea presupunere: tratând textul ca o descriere
(descriere a unui produs), se pot în general organiza propozițiile ierarhic, plecând de la obiectul
descris către cele mai mici trăsături ale acestuia. Legăturile dintre propoziții sunt facute prin
intermediul substantivelor, ce identifică diferite părți ale obiectului descris. Verbele, adjective și
restul părților de vorbire pot aparține fiecărei componente ale obiectului, dar substantivele în
general (desemnând părți ale obiectului) pot fi organizate într-o structură ierarhică. Nu este de
interes cum sunt trăsăturile obiectului descris, ci care sunt acestea. Pentru a face această legătura
directă, substantivele propozițiilor marcate ca cerințe sunt căutate printre subiectele propozițiilor
nemarcate. Astfel este pusă în evidență organizarea ierarhică și legaturile între substantivele
prezente în text prin apariția lor în propoziții comune.
Primul pas al identificării cerințelor ce aparțin contextului este de a pleca de la premisa că
cerințele marcate sunt în proporție de 100% cerințe, iar non-cerințele în proporție de 100% non-
cerințe, adică clasificarea textului a fost facută corect sau, marcarea cerințelor și non-cerințelor a
fost facută manual. Datorită acestui pas, se recomandă ca clasificarea să fie verificată manual, iar
eventualele greșeli să fie corectate. Fiecărei propoziții i se alocă un scor de apartenență la
context, iar algoritmul ce urmează să fie prezentat este unul iterativ și reprezină pasul doi al
acestei etape. Se identifică substantivele aflate în propozițiile marcate ca cerințe. Pentru fiecare
propoziție nemarcată, se verifică de câte ori subiectul este găsit ca un substantiv în propoziții
marcate ca cerințe sau propoziții ce posibil aparțin contextului și se incrementează scorul ei cu
acest număr. În acest pas, propozițile ce posibil aparțin contextului sunt considerate cele ce au
scorul de apartenență la context peste raportul mediei scorurilor tuturor propozițiilor la o
39
constantă determinată. Odată terminat acest pas, propozițiile ce posibil aparțin contextului sunt
marcate ca cerințe și se reia algoritmul de la început. Această iterație poate fi efectuată până nu
mai sunt propoziții marcate ca cerințe. Pe toată durata acestei etape de identificare a cerințelor din
context, propozițiile marcate ca non-cerințe sunt complet ignorate.
De menționat este faptul că un substantiv poate fi prezent în text sub forme diferite, cu
articulații diferite. Pentru corecta identificare am folosit resursa WordNet (Capitolul 3.3). Cu
ajutorul WordNet-ului am redus toate cuvintele analizate la forma de bază pe parcursul
identificării pentru a putea face comparațiile corecte.
O prezentare a algoritmului în pseudocod este prezentată mai jos:
1. pentru fiecare propoziție ”i” marcată ca cerință sau cu scorul > media scorurilor/constantă1
1. pentru fiecare propoziție ”j” nemarcată, mai puțin propoziția ”i”
1. pentru fiecare substantiv ”s” al propoziției ”i”
1. daca ”s” == ”subiectul propoziției j”
1. scorul propoziției ”j” ++;
2. pentru fiecare propoziție ”i”
1. daca scorul propoziției ”i” > media scorurilor/constantă2
1. marchează propoziție ”i” ca cerință
3. reia primul pas al propoziției pastrând scorurile actuale
40
6 Studiu de caz
Se va prezenta un studiu de caz pentru identificarea cerințelor în cadrul unor exemple de foi
de specificații ce apartin proiectului pentru dezvoltarea unui sistem de airbag.
Diagrama proiectului este prezentată în Figura 6.1, modulul fiind unul real, implementat.
Datorită confidențialitații produsului, va fi prezentată foaia de specificații doar pentru o parte a
modulului ”Squib Driver”. Această foaie de specificații este prezentată în Anexa 2.Cerințele
foilor de specificații tuturor modulelor prezente în diagramă au fost identificate manual. În cadrul
Figura 6.1 – diagrama modulară a sistemului airbag
41
acestui proiect, folosind cerințele identificate anterior în diferite module, am identificat noile
cerințe ale modulului ”Squib Driver”.
Identificarea cerințelor s-a facut utilizănd diagrama de funcționare a aplicației (Figura 5.1)
pas cu pas. Documentele cu specificații ce conțin cerințele marcate au fost stocate sub formă xml.
În pasul de preprocesare, pentru a extrage informația text (cerințele și non-cerințele) a fost utilizat
un script scris în limbajul ”Perl”. Cu ajutorul acestuia, în funcție de marcările făcute, am extras
cerințele și non-cerințele și am generat cele două documente în format text. Datorită dimesiunii
reduse a specificației modulului ”Squib Driver”, s-au extras cele mai semnificative atribute
ținănd cont doar de frecvența acestora. Urmatorul pas a fost generarea fișierului ARFF pe baza
atributelor extrase. Cu ajutorul acestuia s-a antrenat și salvat clasificatorul.
Performanțele clasificatorului asupra setului de antrenare sunt prezentate în figura 6.2.
Informația sub formă de text a fost preluată din documentul cu specificații prezentat în
anexa 2 cu același script scris în limbajul ”Perl” folosit în pasul de preprocesare. Identificarea
cerințelor folosind clasificatorul antrenat anterior are următoarele rezultate (Figura 6.3):
Figura 6.2 – performantele clasificatorului asupra datelor
de antrenare
42
Urmatorul pas a constat în căutarea cerințelor aflate în același context cu cele deja marcate.
După o reanaliză a textului, aplicația a identificat trei cerințe corecte, iar non-cerința de pe rândul
doi nu a fost marcată. Aceste rezultate sun prezentate în figura 6.4.
Fiugura 6.3 – rezultatele clasificării
Fiugura 6.4 – rezultatele identificării
cerințelor din context
43
7 Concluzii
Folosirea informației și structurii cerințelor identificate anterior poate ajuta la
identificarea de noi cerințe în cadrul aceluiași proiect sau a modulelor similare. Această tehnică
poate fi folosită ca modalitate de verificare a cerințelor deja marcate, pentru a fi observate
eventuale erori, ca identificare automată de cerințe (pot apărea erori neasteptate), sau doar pentru
a identifica zonele de interes ale documentului, ce pot fi cerințe. Funcția de pastrare a contextul
de asemenea poate fi folosită pentru identificarea acestor zone de interes.
8 Anexa 1
Anexa 1 reprezintă o lista alfabetică a etichetelor folosite de către Stanford Parser,
conform proiectului ”Penn Treebank” (Departamentul de Calculatoare și știința informației,
Universitatea Pennsylvania).
Etichetă Descriere
CC Conjuncție coordinatoare
CD Număr cardinal
DT Determinant
EX There
FW Cuvânt străin
IN Prepoziție sau conjuncție subordinatoare
JJ Adjectiv
JJR Adjectiv comparativ
JJS Adjectiv superlativ
LS Marcator de listă de obiecte
MD Modal
NN Substantiv, singular sau de masă
NNS Substantiv plural
NNP Substantiv propriu singular
NNPS Substantiv propriu plural
PDT Predeterminant
POS Terminație de posesie
PRP Pronume personal
PRP$ Pronume de posesie
RB Adverb
44
RBR Adverb de comparație
RBS Adverb superlativ
RP Participiu
SYM Simbol
TO To
UH Interjecție
VB Verb timpul prezent
VBD Verb la timpul trecut
VBG Verb la gerunziu sau participiu prezent
VBN Verb la participiu trecut
VBP Verb la persoana I sau IIa singular prezent
VBZ Verb la persoana a IIIa singular prezent
WDT Determinator de Wh
WP Pronume de Wh
WP$ Pronume posesiv de Wh
WRB Advert de Wh
45
Anexa 2
1.1 Functional Description This chapter describes the hardware included in the ASSP to provide the current required for deployment. It
also describes the conditions that should be applied externally in order to implement deployment current
limitation.
[FeatureId = Module_main_101, ParentId = SANDBOX1:283, P_7.12.15]
The TLExyz includes eleven independent high-side
driver
circuits between pins SquibSupply_xy and SquibFeed_x and eight independent low-side driver circuits between pins SquibReturn_x and SquibGround_xy. [FeatureId = Module _main_102, ParentId = ]The TLExyz is divided into modules, where each module contains two
deployment channels with the necessary pins to the outside world. The required diagnostic elements are also
distributed in the separate the modules. [FeatureId = Module_main_002, ParentId = SANDBOX1:302]Requirement changed ! - Each driver is independently
controlled by a digital regulation loop. Several external hardware inputs together with SPI commands issued by the
main microcontroller (µC) control the status of the driver; in either diagnosis or firing mode. = SANDBOX1:302]
[Module_main_003] The device provides two operating modes selectable via SPI: diagnosis mode and deployment
mode.[Module_main_003] [Module_main_004] Two deployment conditions can be selected via SPI. The output switches are sized so that
they can withstand all the specified deployment conditions (See to ).[Module_main_004]
Any combination of
channels can be deployed with any timing sequence into a resistive load of between 50 to 100 Ohms, or into a pyrotechnic device.[Module_main_ 005] The output of the Firing Window Timer and the 11 Deployment Fire Timers are
mapped in a Status Register accessible through SPI.[Module_main_005]
[FeatureId = Module_main_006, ParentId = SANDBOX1:285]After powering up the device, the default selected mode is diagnosis
mode. [FeatureId = Module_main_006, ParentId = SANDBOX1:285]
