(NatComp) Clasificarea documentelor

Contents

(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:

navigarea ghidată în "marea" de documente; ghidajul referindu-se la faptul că ar avea la dispoziţie o "busolă" care să îi indice direcţia spre care o ia navigarea, mai mult chiar, o busolă cu mai multe ace, fiecare idicând spre un anumit domeniu, indicând practic întretăierea domeniilor;
evaluarea din punct de vedere calitativ al conţinutului, mai exact gradul de adecvare şi acurateţe a faptelor şi afirmaţiilor prezentate în lucrarea în discuţie;
sumarizarea din punct de vedere semantic al conţinutului, pentru extragerea esenţei celor prezentate;

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:

sisteme de recomandare bazate pe conţinut (content based recommender systems), în care atribuirea unui document la o clasă (domeniu) se face în mod exclusiv pe baza conţinutului său;
sisteme de recomandare colaborative (collaborative recommender systems), unde conţinutul este ignorat, atribuirea fiind realizată pe baza ???? (feedback) utilizatorilor;
sisteme de recomandare hibride ce încearcă combinarea avantajelor celor două direcţii;

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:

intrări: o colecţie de documente (evident în format electronic, eventual eterogen); precum şi o colecţie de clase (domenii) deja descoperite şi elementele sale definitorii; (aceste intrări din urmă sunt opţionale;)
ieşiri: atribuirea fiecărui document la un set de clase (domenii);

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:

nu există o colecţie predefinită de clase, sistemul trebuind să le detecteze în mod automat;
clasele ar trebui să constituie un arbore reprezentând modul în care un domeniu îşi conţine subdomeniile;
fiecare document poate fi atribuit mai multor clase (domenii), ponderate cu probabilitate;
întregul sistem trebuie să fie nesupervizat;

De asemenea este necesară şi identificarea terminologiei specifice:

în primul rând vom utiliza în cele ce urmează în mod interschimbabil următorii termeni: "clasă", "categorie", "domeniu" sau (uneori) "prototip";
document poate avea înţeles dublu, atât ca şi lucrare în format electronic, cât şi ca reprezentare abstractă a conţinutului acesteia în funcţie de necesităţile diferiţilor algoritmi;

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ă:

algoritmii în sine nu utilizează textual documentele, ci reprezentări numerice, vectoriale;
pentru aceasta documentele sunt trecute printr-o fază de preprocesare, proces prin care fiecărui document îi este ataşat un vector caracteristic, format din frecvenţa cuvintelor (sau a unui subset de cuvinte) din textul original;
din setul global de vectori obţinut anterior, se selectează (de regulă în mod aleator) un set de antrenare suficient de mare;
utilizând setul de antrenare se identifică un set de clase, reprezentate tot prin vectori numerici, ce pot fi interpretate ca documente prototip pentru respectiva categorie;
în procesul de antrenare, se utilizează o funcţie de distanţă ce încearcă să aproximeze apartenenţa unui document la o anumită categorie (în general se numeşte funcţie de similaritate);

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:

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;
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:

pragul de vigilenţă;

rata de învăţare --

latex error! exitcode was 2 (signal 0), transscript follows:

;

numărul de iteraţii;

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

varianta A -- clasică --

latex error! exitcode was 2 (signal 0), transscript follows:

;

varianta B -- tot clasică, însă pretabile pentru seturi de date spaţiale --
```
latex error! exitcode was 2 (signal 0), transscript follows:
```
;
varianta C -- adaptată aplicaţiei de faţă pentru a lua în considerare similaritatea între document şi clasă, în schimbul distanţei euclidiene --
```
latex error! exitcode was 2 (signal 0), transscript follows:
```
;

, unde:

latex error! exitcode was 2 (signal 0), transscript follows:

reprezintă vectorul caracteristic al clasei;

latex error! exitcode was 2 (signal 0), transscript follows:

reprezintă vectorul caracteristic al documentului;

latex error! exitcode was 2 (signal 0), transscript follows:

reprezintă funcţia de disimilaritate cosinus;

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:

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);
pentru fiecare clasă se identifică documentele care sunt cel mai apropiate de el, şi se constituie o listă;
se recalculează vectorul caracteristic ai fiecărei clase, ca centrul documentelor ce au fost identificate la pasul anterior;
se determină suma deplasărilor tuturor claselor în urma pasului precedent;
î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ţă):

distanţa euclidiană

latex error! exitcode was 2 (signal 0), transscript follows:

;

distanţa "cosinus", dată de formula:

latex error! exitcode was 2 (signal 0), transscript follows:

;

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

latex error! exitcode was 2 (signal 0), transscript follows:

;

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

validare externă -- ce se bazează pe o partiţionare cunoscută anterior;
validare internă -- care ia în considerare doar setul de date (vectorii caracteristici) şi nu depinde (ca şi în cazul anterior) de nici o partiţionare cunoscută;

Î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:

validarea externă se bazează pe subiectivitatea umană, măsurând (din punct de vedere calitativ) cât de mult se apropie clasificatorul automat, de modul în care un om ar clasifica (în mod subiectiv) documentele; astfel chiar dacă o astfel de verificare este esenţială în probleme în care fiecare punct din setul de date reprezintă o instanţă clară a unei clase, în cazul unei clasificări de documente ea se poate dovedi inadecvată, deoarece nu se poate realiza o clasificare obiectivă, fiecare dintre noi privind în mod subiectiv un anumit set de documente;
validarea internă se bazează exclusiv pe calităţile claselor rezultate în urma clasificării; în acest sens această verificare fiind mult mai adecvată problemei de faţă, deoarece va testa doar proprietăţile claselor în sine, verificând dacă acestea sunt echilibrate, atât din punctul de vedere al documentelor ce aparţin, cât şi din punct de vedere al depărtării faţă de alte categorii;

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

Rand statistic:

latex error! exitcode was 2 (signal 0), transscript follows:

;

Jaccard coefficient:

latex error! exitcode was 2 (signal 0), transscript follows:

;

Folkes and Mallows index:

latex error! exitcode was 2 (signal 0), transscript follows:

;

, unde:

```
latex error! exitcode was 2 (signal 0), transscript follows:
```
reprezintă numărul de perechi de documente ce aparţin aceloraşi categorii şi partiţii;
```
latex error! exitcode was 2 (signal 0), transscript follows:
```
reprezintă numărul de perechi de documente ce aparţin aceloraşi categorii, însă unor partiţii diferite;
```
latex error! exitcode was 2 (signal 0), transscript follows:
```
... ce aparţin aceloraşi partiţii, dar unor categorii diferite;
```
latex error! exitcode was 2 (signal 0), transscript follows:
```
... ce aparţin atât la clustere diferite, dar şi la partiţii diferite;

latex error! exitcode was 2 (signal 0), transscript follows:

;

latex error! exitcode was 2 (signal 0), transscript follows:

este numărul total de documente;

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

entropia:

latex error! exitcode was 2 (signal 0), transscript follows:

, unde

latex error! exitcode was 2 (signal 0), transscript follows:

;

puritatea:

latex error! exitcode was 2 (signal 0), transscript follows:

, unde

latex error! exitcode was 2 (signal 0), transscript follows:

;

, unde:

latex error! exitcode was 2 (signal 0), transscript follows:

reprezintă numărul de clase;

latex error! exitcode was 2 (signal 0), transscript follows:

reprezintă numărul de partiţii cunoscute a-priori;

latex error! exitcode was 2 (signal 0), transscript follows:

reprezintă numărul de documente ce aparţin clasei

latex error! exitcode was 2 (signal 0), transscript follows:

;

latex error! exitcode was 2 (signal 0), transscript follows:

reprezintă numărul de documente ce se află în partiţia

latex error! exitcode was 2 (signal 0), transscript follows:

şi au fost repartizate clasei

latex error! exitcode was 2 (signal 0), transscript follows:

;

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

latex error! exitcode was 2 (signal 0), transscript follows:

, unde:

latex error! exitcode was 2 (signal 0), transscript follows:

reprezintă vectorul caracteristic al unui document;

latex error! exitcode was 2 (signal 0), transscript follows:

;

latex error! exitcode was 2 (signal 0), transscript follows:

;

latex error! exitcode was 2 (signal 0), transscript follows:

;

```
latex error! exitcode was 2 (signal 0), transscript follows:
```
reprezintă centrul geometric (media) vectorilor caracteristici a documentelor;
```
latex error! exitcode was 2 (signal 0), transscript follows:
```
reprezintă o funcţie de distanţă (în cazul nostru funcţia de disimilaritate "cosinus");
```
latex error! exitcode was 2 (signal 0), transscript follows:
```
reprezintă o funcţie de similaritate (în cazul nostru funcţia de similaritate "cosinus");

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:

Putem observa astfel următoarele componente:

clasificatorul nesupervizat (unsupervized classifier): reprezintă rezultatul direct al activităţii desfăşurate în acest proiect, el având scopul clasificării (sau reclasificării) documentelor cu ajutorul unor tehnici nesupervizate; o descriere mai amplă este expusă în următoarele secţiuni;
clasificatorul colaborativ (collaborative classifier): componentă ce ar trebui să aducă în cadrul procesului de clasificare şi expertiza umană, pe baza feedback-ului utilizatorilor; (această componentă poate fi implementată ca o extensie;)
sistemul de recomandare (recommender system): acesta joacă rolul de mediator între cele două sisteme de clasificare (nesupervizat şi supervizat), coroborând rezultatele acestora două; precum şi inferenţe legate de profilul unui anumit utilizator pe baza istoricului navigării; (ca şi în cazul componentei precedente, el reprezintă o componentă opţională);
baza de date (database): punctul central al întregii aplicaţii în ceea ce priveşte stocarea datelor şi comunicarea între componente; se poate observa că prototipul nostru se depărtează (practic, nu principial) de metodologia SOA prin utilizarea unei baze de date (în locul omniprezentelor servicii web) în ceea ce priveşte comunicaţia; această alegere a fost motivată de faptul că (potenţialele) mesaje schimbate între diversele componente prezintă un caracter determinist şi permanent, acestea reprezentând rezultate finale sau intermediare ale clasificării sau procesării; de asemenea utilizarea unei baze de date ca intermediar înlesneşte şi comunicarea asincronă sau în loturi;
???? (document loader): joacă rolul pre-procesorului de documente şi transformarea acestora în intrări specifice clasificatoarelor (în cazul nostru vectori caracteristici);
portalul web (web portal): reprezintă una dintre interfeţele posibile între utilizatorii direcţi şi componentele sistemului;

Fluxul activităţilor în vederea clasificării

...

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

???? (document loader): acesta intră primul în joc:
- culegând fişierele brute (în format PDF sau PS pentru moment, însă putând fi cu uşurinţă adaptat pentru alte formate, ODF (Open Document), sau OOXML (Open Office XML));
- extrăgând doar informaţia textuală din documente şi stocarea lor în text ASCII (plain text);
- analizând lexical textul rezultat în vederea obţinerii de cuvinte;
- reducând toate cuvintele la rădăcina lor lexicală (nu neaparat cea literară);
- construind tabelele de frecvenţă a rădăcinilor;
- construind vectorii caracteristici pe baza frecvenţelor;
clasificatorul nesupervizat: se va baza pe vectorii caracteristici în vederea determinării categoriilor şi atribuirea fiecărui vector (deci document) la una sau mai multe categorii;
baza de date: fiecare pas prezentat anterior îşi preia intrările dintr-o anumită bază de date, şi asemănător ieşirile sunt stocate în altele;

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:

transformarea documentelor PDF sau PS în text s-au utilizat unelte deja existente pdftotext şi pstotext;
determinarea cuvintelor cu ajutorul expressilor regulate ce considerau cuvinte orice înlănţuire de cel puţin 2 litere (mici sau mari);
extragerea rădăcinilor lexicale conform lucrării <<Cite(5)>>; (trebui remarcat faptul că tehnica descrisă în lucrarea citată se aplică doar limbii engleze; existând totuşi alternative şi pentru alte limbi, inclusiv română, <<Cite(6)>>;)
construirea tabelei de frecvenţă a rădăcinilor pentru fiecare document;

Generarea vectorilor caracteristici

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

au fost eliminate toate cuvintele de legătură (stop words), conform unei liste predefinite;
toate rădăcinile ce apar în mai puţin de 0.5% (1/200) din documente sunt eliminate; (deoarece ar putea genera mai mult de 200 de categorii;)
toate rădăcinile ce apar în mai mult de 20% (1/5) din documente sunt eliminate; (deoarece nu ar putea determina (distinge) decât maxim categorii;)

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:

şi fiecare rădăcină se calculează coeficientul frecvenţei acesteia conform formulei:
```
latex error! exitcode was 2 (signal 0), transscript follows:
```
;
după care vectorul frecvenţelor este normalizat pentru a elimina diferenţele de lungime ale documentelor;

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

K -- reprezintă numărul colecţiilor identificate; (de remarcat că în cazul lui K-means aceasta reprezintă o intrare;)
R -- Rand statistic;
J -- Jaccard coefficient;
FM -- Folkes and Mallows index;
E -- entropia;
P -- puritatea;

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:

atât varianta clasică (A) cât şi cea adaptată de noi (C) a algoritmului ART este comparabilă cu K-means;
varianta noastră (C) se dovedeşte puţin mai bună decât cea clasică (datorită luării în considerare a măsurii de similaritate);
se observă comportamentul bun al algoritmilor pe prima colecţie (CISI+Cran+Med), deoarece documentele din colecţiile în sine sunt foarte diferite în ceea ce priveşte conţinutul;
pe de altă parte, pentru colecţia News20, se observă un comportament mai slab (în ceea ce priveşte indici de validare externi), deoarece partiţiile au fost create pe alte considerente decât cele de conţinut; în cazul de faţă partiţiile se identifică cu lista de discuţii pe care a fost trimis un anumit email, astfel putem observa că toate email-urile în care se vinde (sau cumpără) ceva, algoritmii le pun într-o singură categorie, pe când în listele de discuţii se află împrăştiate în funcţie de domeniul produsului (sport, calculatoare, etc.)

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}
}