(NatComp) Clasificarea documentelor

Problema clasificării documentelor

Contextul general

Una dintre problemele (de natură intelectuală) cu care se confruntă omenirea (cel puţin în ultimii ani) o constituie supra-saturarea informaţională (information overload), deoarece dezvoltarea tehnologică rapidă a contribuit în mod semnificativ la generarea şi acumularea de cunoştiinţe în volume din ce în ce mai mari (se presupune că informaţia disponibilă pe Internet creşte exponenţial în fiecare an) precum şi la diseminarea lor în arii cât mai extinse, încât momentul de faţă, datorită Internet-ului, aria de răspândire este globală.

Un alt factor ce a dus la explozia informaţională l-a constituit forma de distribuire, care a evoluat de la hârtie cu un cost semnificativ de tipărire (sau multiplicare), diseminare (transport şi distribuţie), stocare (şi de ce nu cu impact asupra mediului), şi a ajuns la forma virtuală, electronică, al cărei cost de duplicare, distribuire şi stocare este (practic vorbind) egal cu zero, precum şi uşurinţa de procesare şi transformare (fapt ce a adus în sine o problemă, deoarece aceeaşi lucrare se poate afla în forme multiple însă nu identice, ceea ce implică dificultatea identificării echivalenţei din punct de vedere semantic).

Astfel acum nu mai putem vorbi de biblioteci sau colecţii de documente (lucrări ştiinţifice, cărţi, ziare, etc.) ci avem o "găleată" globală (Internetul) ce conţine toată informaţia acumulată de omenire.

Contextul problemei

Printre principalele domenii afectate de a ceastă explozie informaţională, se află şi mediul academic, mai exact mediul de cercetare. Spre exemplu dacă cineva doreşte să îşi îndrepte atenţia spre un anumit domeniu, cu greu va putea să descopere care sunt documentele cele mai reprezentative pentru respectiva arie. Mai mult, dacă doreşte să descopere documentele care se află la întrepătrunderea a două domenii, acest lucru este şi mai greu fără o cunoaştere substanţială a celor două direcţii distincte.

Această situaţie este îngreunată de asemenea şi de lipsa unor instrumente care să faciliteze:

Dacă cea de a doua problemă nu poate fi rezolvată decât în mod exclusiv subiectiv şi manual, celelalte probleme pot avea o soluţionare automată, sau cel puţin construind un punct de plecare.

Clasificarea documentelor

Soluţia pentru problema generică a navigării o reprezintă clasificarea documentelor (document clustering), şi anume atribuirea unui document la una sau mai multe clase (domenii).

Această clasă de probleme formează o subramură distinctă a ???? (information retrieval) sau ???? (data mining), şi nu reprezintă în sine o descoperire recentă, însă se constituie într-un domeniu de cercetare actual şi activ, şi atinge ca domenii de suport de la metode statistice, procesarea limbajului natural, până la algoritmi inspiraţi din natură (direcţie în care noi ne-am îndreptat).

Ca produse directe al acestui domeniu îl constituie sistemele de recomandare, anume:

Este evident faptul că fiecare dintre direcţiile de mai sus au avantajele şi dezavantajele lor, fiecare încercând să menţină un echilibru între calitatea clasificării (privită prin prisma perceperii umane), complexitatea şi responsivitatea sistemului. Ca direcţie aleasă de noi, ne încadrăm în prima categorie, anume a sistemelor de recomandare bazate pe conţinut, a cărui timp de răspuns (timpul scurs de la intrarea în sistem a unui document şi până la clasificarea lui) este minim, iar acurateţea clasificării este bună.

Desigur -- după cum se va putea observa în paragraful dedicat prototipului implementat -- în arhitectura finală a sistemului s-a luat în considerare îmbinarea clasificatorului automat cu cel bazat pe expertiza umană.

Cerinţele problemei în sine

Pornind de la cele descrise mai sus, putem formaliza (pe scurt) problema clasificării documentelor în felul următor:

Prin urmare, ne-am propus implementarea unui sistem de clasificare automată a documentelor, mai mult, acesta încercând să se integreze într-o suită de aplicaţii ce servesc necesităţii de navigare a unei biblioteci de documente ştiinţifice.

Revenind la descrierea problemei, după cum se observă aceasta este destul de laxă, lăsând multă libertate de interpretare şi implementare, de aceea noi ne-am propus atingerea următoarelor puncte adiţionale:

De asemenea este necesară şi identificarea terminologiei specifice:

Metode utilizate în clasificare

Introducere

Înainte de prezentarea prototipului creat, vom face o scurtă trecere în revistă a metodelor specifice problemei, anume algoritmi de clasificare (clustering).

În mare parte toţi algoritmii de clasificare urmează următoarea schemă:

De asemenea vom face o precizare pe marginea cerinţelor problemei. Anume, în paragraful dedicat acestui subiect, am precizat că fiecare document trebuie să poată fi asignat la mai multe categorii, ponderate cu probabilităţi. Totuşi pentru prima fază a prototipului (ceea ce descriem aici) am ales să renunţăm la această cerinţă, astfel fiecare document trebuie să fie asignat la exact o singură categorie. Trebuie remarcat însă că această alegere afectează doar procesul de antrenare, mai exact spus de determinare a claselor, existând posibilitatea ca la navigare ori vizualizare, apartenenţa fiecărui document la mai multe categorii să fie determinată pe baza similarităţii acestuia cu fiecare dintre categoriile existente.

ART

ART (Adaptive Resonance Theory) este o reţea neuronală adaptată pentru clustering, şi a fost descrisă în detaliu în lucrarea <<Cite(1)>>. Aceasta se încadrează în categoria reţelelor neuronale nesupervizate.

Algorimul în linii mari urmează următorii paşi:

  1. pentru fiecare document identificăm categoria ce se apropie cel mai mult;
    1. dacă apropierea (similaritatea) se află peste un anumit prag de vigilenţă (prestabilit), ajustăm vectorul caracteristic al categoriei, utilizând o rată de învăţare (prestabilită), conform formulelor de mai jos;
    2. în caz contrar, se crează o nouă clasă, utilizând ca vector caracteristic însuşi documentul curent;
  2. se iterează întregul proces de una numit număr de ori (prestabilit);

Putem observa astfel că procesul de antrenare este influenţat de trei parametrii, de a căror alegere depinde calitatea clasificării:

Referitor la funcţia de ajustare, în lucralea originală se precizează două variante, iar în plus o variantă proprie adaptată:

, unde:

K-means

De asemenea am luat în considerare şi varianta clasică a algoritmului K-means, care deşi nu se încadrează cerinţelor aplicaţiei (anume clasificare nesupervizată), poate fi utilizat în compararea rezultatelor obţinute cu clasificatorul ART.

Vom descrie astfel în mare doar algoritmul general:

  1. se porneşte de la un număr (prestabilit) de clase (al căror vectori caracteristici fie sunt generaţi aleator, fie sunt consideraţi vectorii caracteristici ai unor documente alese la întâmplare);
  2. pentru fiecare clasă se identifică documentele care sunt cel mai apropiate de el, şi se constituie o listă;
  3. se recalculează vectorul caracteristic ai fiecărei clase, ca centrul documentelor ce au fost identificate la pasul anterior;
  4. se determină suma deplasărilor tuturor claselor în urma pasului precedent;
  5. în cazul în care deplasarea se află peste un prag prestabilit se reia întregul proces de la pasul al doilea;

Metrici

După cum am precizat şi în paragrafele anterioare, în general algoritmii de clasificare au nevoie de o funcţie care să determine "distanţa" între un document şi o clasă, (sau chiar între două documente sau două clase), precum şi una specifică determinării "apropierii".

Funcţiile din prima categorie poartă numele generic de "distanţe", cele mai des întâlnite funcţii fiind (în contextul problemei de faţă):

Funcţiile din a doua categorie se numesc generic "similarităţi", şi cea folosită de noi este "inversa" distanţei "cosinus":

Validare

O altă problemă esenţială strâns legată cu ceea ce şi-a propus prototipul, este determinarea calităţii clasificării. Dificultatea în această instanţă este determinarea aceste calităţi, fără a necesita intervenţia (clasificarea) umană, în caz contrar, utilitatea clasificării automate reducându-se la zero.

În acest scop am încercat identificarea unor metode specifice, acestea fiind regăsite într-una din următoarele categorii <<Cite(2)>>:

Înainte de a trece în revistă soluţiile găsite pentru ambele categorii, vom sublinia încă o dată diferenţa majoră între cele două clase de metode:

Un prim set de indicii de validare externă identificaţi, sunt descrişi în <<Cite(2)>>:

, unde:

Un alt set de indici, tot externi, se pot găsi şi în <<Cite(3)>>:

, unde:

În schimb pentru indici de validare internă, am putut identifica doar unul singur PBM, descris în <<Cite(3)>>:

, unde:

Sistemul dezvoltat

Arhitectura

Sistemul dezvoltat este în fapt prototipul unui sistem mai cuprinzător, punctul de plecare pentru dezvoltarea ulterioară în această direcţie.

Prototipul se încadrează în sistemele bazate pe servici (SOA -- Service Oriented Architecture), în care fiecare componentă are exact un singur rol, singurele interacţiuni bazându-se pe comunicarea între componente prin intermediul unor interfeţe bine stabilite. În mare arhitectura sistemului trebuie să reiasă din următoarea imagine:

architecture.png

Putem observa astfel următoarele componente:

Fluxul activităţilor în vederea clasificării

...

workflow.png

În diagrama precedentă pot fi surprinse în acţiune trei dintre componentele esenţiale ale sistemului (prototipului):

Cei mai importanţi paşi sunt procesarea documentelor, obţinerea vectorilor caracteristici şi clasificarea în sine, paşi ce vor fi descrişi în secţiunile următoare.

Încărcarea documentelor

În vederea preprocesării documentelor s-au utilizat următoarele tehnici:

Generarea vectorilor caracteristici

Acest pas a necesitat un pas intermediar pentru "curăţarea" acelor rădăcini considerate nerelevante conform următoarelor euristici:

Trebuie menţionat că euristicile prezentate anterior (cu excepţia primei), au fost determinate experimental, având în vedere balansarea, pe de-o parte, a reducerii numărului de caracteristici (ce impactează viteza de execuţie a clasificatorului), iar, pe de altă parte, păstrarea unui număr suficient de caracteristici cu entropie mare (ce impactează acurateţea clasificatorului). Astfel s-a redus cu până la 80% dimensiunea vectorilor caracteristici.

Pentru fiecare document:

Studii de caz

Seturi de date

Pentru validarea experimentală a clasificatorului nesupervizat sunt necesare seturi de date representative pentru problema de faţă, şi prin urmare am ales utilizarea unor colecţii clasice din ???? (information retrieval), precum şi un set creat de către noi pentru a vedea comportamentul pe date reale.

Proprietăţile seturilor de date alese sunt descrise în tabelul de mai jos. Este important de remarcat reducerea semnificativă (de 6 până la 10, sau chiar 45 de ori) a numărului de cuvinte utilizate în clasificare, reducere datorată euristicii alese, prezentate în paragraful anterior.

Colecţie

Componenţă

Documente

Cuvinte (rădăcini)

Lungime vector caracteristic

Cisi+Cran+Med

Cisi <<Cite(7)>>, Cranfield <<Cite(8)>> şi Medline <<Cite(9)>> concatenate

3887

13494

1590

News20

News20 <<Cite(10)>>

18846

91013

2842

Reuters

Reuters <<Cite(11)>>

18781

28499

1350

Files

o colecţie de articole PDF şi PS

706

60204

11474

Parametrizare algoritmi

De asemenea vom prezenta şi parametrii utilizaţi pentru antrenarea celor doi algoritmi. În general parametrii se păstrează pentru toate colecţiile, însă -- în cazul algoritmului ART -- pentru fiecare variantă a algoritmului a fost nevoie de o mică ajustare a unora dintre ei.

Parametrii pentru algoritmul ART:

Variantă

prag de vigilenţă

rată de învăţare

număr de iteraţii

A

0.2

0.2

3

C

0.2

1.0

3

În cazul algoritmului K-means să decis rularea lui până când deplasarea minimă se afla sub pragul de 0.001.

Valori indici de validare

Colecţie

Algoritm

K

R

J

FM

E

P

Cisi+Cran+Med

ART var. A

3

0.94

0.84

0.91

0.16

0.96

Cisi+Cran+Med

ART var. C

3

0.94

0.86

0.92

0.16

0.96

Cisi+Cran+Med

K-means

3

0.98

0.95

0.97

0.05

0.99

News20

ART var. A

19

0.92

0.17

0.30

0.52

0.48

News20

ART var. C

20

0.91

0.18

0.31

0.63

0.38

News20

K-means

20

0.92

0.22

0.37

0.53

0.45

Reamintim pe scurt identificatorii indicilor (pentru mai multe informaţii se poate referi paragraful dedicat acestor indici de validare):

Observaţii

Din testele rulate (şi din cifrele de mai sus) se pot trage câteva concluzii (în linii mari) în ceea ce priveşte adecvarea algoritmilor la problema clasificării documentelor:

Referinţe

@article{1,
    title = {Constructive feedforward ART clustering networks. I},
    author = {Baraldi, A. and Alpaydin, E.},
    journal = {Neural Networks, IEEE Transactions on},
    year = {2002},
    month = {May},
    volume = {13},
    number = {3},
    pages = {645-661},
    keywords = {ART neural nets, feedforward neural nets, fuzzy neural nets, pattern clustering, self-organising feature maps, unsupervised learningARTMAP, Fuzzy ART neural network, GART, Gaussian ART, S-Fuzzy ART, adaptive Hamming net, computation time, constructive feedforward ART clustering networks, fully self-organizing SART, memory storage, simplified adaptive resonance theory network, supervised learning, symmetric Fuzzy ART, unsupervised online learning clustering networks},
    doi = {10.1109/TNN.2002.1000130},
    ISSN = {1045-9227},
    bibsource = {http://ieeexplore.ieee.org/},
}

@article{2,
    author = {Maria Halkidi and Yannis Batistakis and Michalis Vazirgiannis},
    title = {Cluster validity methods: part I},
    journal = {SIGMOD Rec.},
    volume = {31},
    number = {2},
    year = {2002},
    issn = {0163-5808},
    pages = {40--45},
    doi = {http://doi.acm.org/10.1145/565117.565124},
    publisher = {ACM},
    address = {New York, NY, USA},
    bibsource = {http://portal.acm.org/},
}

@inproceedings{3,
    author = {Marta V. Modenesi and Myrian C. A. Costa and Alexandre Evsukoff and Nelson F. F. Ebecken},
    title = {Parallel Fuzzy c-Means Cluster Analysis},
    booktitle = {VECPAR},
    year = {2006},
    pages = {52-65},
    ee = {http://dx.doi.org/10.1007/978-3-540-71351-7_5},
    crossref = {DBLP:conf/vecpar/2006},
    bibsource = {DBLP, http://dblp.uni-trier.de},
}

@inproceedings{3,
    title = {Parallel Fuzzy c-Means Cluster Analysis},
    author = {Marta V. Modenesi and Myrian C. A. Costa and Alexandre Evsukoff and Nelson F. F. Ebecken},
    booktitle = {VECPAR},
    crossref = {conf/vecpar/2006},
    editor = {Michel J. Daydé and José M. L. M. Palma and Alvaro L. G. A. Coutinho and Esther Pacitti and João Correia Lopes},
    pages = {52-65},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    url = {http://dblp.uni-trier.de/db/conf/vecpar/vecpar2006.html#ModenesiCEE06},
    volume = {4395},
    year = {2006},
    biburl = {http://www.bibsonomy.org/bibtex/2a18f0db28976881e77b88cd24cb091db/dblp},
    description = {dblp},
    ee = {http://dx.doi.org/10.1007/978-3-540-71351-7_5},
    isbn = {978-3-540-71350-0},
    date = {2007-09-13},
    keywords = {dblp},
    bibsource = {http://www.bibsonomy.org/},
}

@techreport{4,
    author = {Ying Zhao and George Karypis},
    title = {Criterion functions for document clustering: Experiments and analysis},
    year = {2001},
}

@misc{5,
    title = {The Porter Stemming Algorithm},
    url = {http://tartarus.org/martin/PorterStemmer/index.html},
}

@misc{6
    title = {The English (Porter2) stemming algorithm},
    url = {http://snowball.tartarus.org/algorithms/english/stemmer.html},
}

@misc{7,
    title = {Cisi collection},
    url = {http://ir.dcs.gla.ac.uk/resources/test_collections/cisi},
}

@misc{8,
    title = {Cranfield collection},
    url = {http://ir.dcs.gla.ac.uk/resources/test_collections/cran},
}

@misc{9,
    title = {Medline collection},
    url = {http://ir.dcs.gla.ac.uk/resources/test_collections/medl},
}

@misc{10,
    title = {20 Newsgroups collection},
    url = {http://people.csail.mit.edu/jrennie/20Newsgroups},
}

@misc{11,
    title = {Reuters-21578 collection},
    url = {http://www.daviddlewis.com/resources/testcollections/reuters21578}
}